基于同種映射的抗功耗攻擊標量乘算法

李芳菊

(中原工學院信息商務學院，河南 鄭州 450007)

0 引 言

橢圓曲線密碼(Elliptic Curve Cryptography, ECC)是于1985年分別由Koblitz N和Miller V獨立提出來的，與其它公鑰密碼算法相比，可以采用更短的密鑰實現(xiàn)相同的安全級別，所以橢圓曲線密碼既可以提高加解密速度且可以節(jié)省計算資源，非常適用于諸如智能卡、安全芯片等各類資源受限的密碼設備中[1-2]。其中，標量乘算法是橢圓曲線密碼最關鍵但也是最耗時的操作。但是功耗攻擊針對標量乘算法具有較好的攻擊效果，所以已成為當前標量乘算法的主要威脅之一。功耗攻擊最早是由Paul Kocher于1998年最早提出的，主要通過測量密碼裝備運行時所泄露的功耗信息來實施攻擊的，具有實現(xiàn)簡單、成功率高等優(yōu)勢[3-4]。目前，標量乘算法抵御功耗攻擊的主要措施大都是采用增加冗余操作的手段[5-7]。文獻[8]提出一種基于帶符號雙基數(shù)系統(tǒng)的抗功耗攻擊標量乘算法，該算法通過引入隨機點對基點進行掩碼來實現(xiàn)抗功耗攻擊，然后采用帶符號雙基數(shù)系統(tǒng)對標量編碼以優(yōu)化運算效率。文獻[9]提出一種基于帶符號階乘展開式抗功耗攻擊標量乘算法，該算法通過引入隨機點進行基點掩碼及添加偽操作來實現(xiàn)抗功耗攻擊，然后采用帶符號階乘展開式對標量編碼以優(yōu)化運算效率。文獻[10]提出了一種基于帶符號整數(shù)拆分形式的抗功耗攻擊標量乘算法，該算法通過引入隨機點進行基點掩碼及標量分割來實現(xiàn)抗功耗攻擊，然后采用帶符號整數(shù)拆分形式對標量編碼以優(yōu)化運算效率。上述方案均是通過增加冗余操作來實現(xiàn)抗功耗攻擊，雖然通過采用更高效的編碼方式能夠在一定程度上提升標量乘算法的效率，但與未施加抗功耗攻擊措施的標量乘算法相比，仍然增加了計算開銷。文中根據(jù)橢圓曲線同種映射理論，給出一種基于同種映射的抗功耗攻擊標量乘算法(resisting power attack algorithm of scalar multiplication based on Homogeneous Mapping, HM)，通過變換橢圓曲線密碼標量乘算法的形式來消除標量乘運算與泄露功耗信息的相關性，因此可以在不增加冗余操作的基礎上實現(xiàn)抗功耗攻擊。

1 橢圓曲線密碼標量乘算法

定義1：假設存在域K，在其上定義一個橢圓曲線E：

E：y2+a1xy+a3y=x3+a2x2+a4x+a5

(1)

其中，ai∈K。式(1)也稱為Weierstrass方程。

如果域K的特征不等于2或3，則通過變量的相容性變換，式(1)可變換為如下曲線方程：

E：y2=x3+ax+b

(2)

其中，a,b∈K。橢圓曲線E上點的集合及一個無窮遠點O可以構成一個阿貝爾群。

在橢圓曲線E上定義兩個不同的點P=(x1,y1)與Q=(x2,y2)，且P≠±Q。則這兩個點相加可得P+Q=(x3,y3)的表達式如下所示：

(3)

橢圓曲線密碼的標量乘法運算如下式(4)所示：

(4)

其中，k為標量，一般采用二進制編碼表示，且編碼長度為n比特，則可知標量k二進制編碼表示形式如下式(5)所示：

(5)

標量乘算法采用二進制編碼可以將標量乘運算分解為點加運算與倍點運算，如下式(6)所示：

Q=kP=(kn-12n-1+kn-22n-2+…+k12+k0)·P=

2{…2[2(2kn-1P+kn-2P)+kn-3P]+…+k1P}+k0P

(6)

則采用二進制編碼的標量乘算法如下面算法1所示。

算法1 二進制編碼的標量乘算法

輸入：整數(shù)k，橢圓曲線上一點P；

輸出：Q=kP。

(1) 令Q=O，其中O無窮遠點；

(2) 對于變量i從n-1到0，則重復執(zhí)行：

①Q(mào)=2Q；

② 如果ki=1，則有Q=Q+P；

(3) 返回Q。

由算法1可知，當ki=0時，執(zhí)行倍點運算；當ki=1時，執(zhí)行點加運算，由于倍點運算與點加運算的功耗不同，所以執(zhí)行標量乘算法過程中會出現(xiàn)功耗差異，從而使得攻擊者可以實施功耗攻擊，根據(jù)功耗曲線與中間值的相關性獲取密鑰信息。

2 功耗攻擊及其防御

簡單功耗攻擊通過測量密碼算法的功耗信息差異來猜測所執(zhí)行的操作及其次數(shù)，以此獲取對應的密鑰信息。抵御簡單功耗攻擊的主要方法是在ki=0時添加一次冗余點加操作，使標量乘算法在每一次循環(huán)運算均執(zhí)行相同的操作，以此來消除功耗差異與密鑰的相關性，實現(xiàn)抗功耗攻擊的目的。

差分功耗攻擊是采用功耗統(tǒng)計分析方法，首先根據(jù)測量的大量功耗曲線猜測密鑰值，然后根據(jù)某個函數(shù)將這些曲線劃分到兩個集合中，并分別求平均來消除噪聲，最后差分曲線，如果差分后的曲線有尖峰，說明猜測密鑰正確，反之，則重新猜測密鑰。其攻擊過程主要為以下5個步驟[11]：

(1) 在密碼算法執(zhí)行過程中選擇一個中間值；

(2) 測量每一個輸入的明文對應的功耗曲線；

(3) 計算猜測的中間值；

(4) 采用某種功耗模型將猜測中間值映射成猜測的模擬功耗值；

(5) 計算猜測的模擬功耗值與實際測量功耗的統(tǒng)計相關性。

防御差分功耗攻擊的方法主要有以下3種：

(1) 選擇一個隨機數(shù)與初始值進行異或，使得參與密碼運算的是未知初始值，以掩蓋原始初始值。

(2) 選擇一個隨機數(shù)與初始密鑰進行異或，使得參與密碼運算的是未知密鑰，以掩蓋初始密鑰。

(3) 選擇一個隨機數(shù)與密碼算法執(zhí)行過程中的某個中間值進行異或，使得獲取的中間值是未知的，以掩蓋中間值與密鑰的相關性。

3 橢圓曲線同種理論

定義2：如果存在橢圓曲線E1和E2，那么E1到E2的同種是一個同態(tài)，即φ:E1→E2滿足φ(O)=O。

由于橢圓曲線是阿貝爾群，因此橢圓曲線間的映射構成了群。則從橢圓曲線E1橢圓曲線到E2的同種映射集合為：

H(E1,E2)={isogeniesE1→E2}

(7)

其中，isogeniesE1表示E1的同種橢圓曲線。兩個同種橢圓曲線的求和為(φ+ψ)(P)=φ(P)+ψ(P)，所以φ+ψ為同態(tài)，也為同種。

4 基于同種映射的標量乘算法

根據(jù)定義2，假設在K域上的兩條橢圓曲線E與E′為一個非常值同態(tài)φ:E→E′，那么同種φ的次數(shù)可表示為：

(8)

假設φ為K域上橢圓曲線E和橢圓曲線E′之間次數(shù)為m的同種映射。其中，E：y2=x3+ax+b，E′：y2=x3+a′x+b′。令橢圓曲線點P為大素數(shù)，且有gcd(m,ordEP)=1(即m是ordEP可逆的)，定義r≡k/m(modordEP)。則可得橢圓曲線標量乘運算Q=[k]P的變換計算方式，如下式(9)所示。

(9)

則可用如下同種映射模型來等價變換計算標量乘運算Q=[k]P，如圖1所示。

圖1 橢圓曲線同種映射模型

由橢圓曲線同種映射模型可知，僅采用少量的域運算即可實現(xiàn)橢圓曲線上點的同種映射計算，通過隨機選擇一個隨機同種映射來完成標量乘法運算，可以實現(xiàn)掩蓋標量乘法運算的計算過程，攻擊者無法獲得與密鑰信息相關的中間值，從而達到抵抗功耗攻擊的目的。則下面給出基于同種映射的抗功耗攻擊標量乘算法(HM算法)，如算法2所示。

算法2 基于同種映射的抗功耗攻擊標量乘算法(HM算法)

輸入：整數(shù)k，橢圓曲線E上一點P；

輸出：Q=kP。

(2) 計算點P的同種映射P′=φ(P)；

(3) 按照公式r≡k/m(modordEP)計算出r的值；

(4) 在橢圓曲線E′：y2=x3+a′x+b′上，按照算法1的步驟計算同種映射后的標量乘運算Q′=rP′；

(6) 返回Q。

5 效率及安全性分析

6 結 語

現(xiàn)有的橢圓曲線密碼抗功耗攻擊方案為了能夠同時兼顧安全和效率，一方面是通過增加冗余操作(如添加偽操作、引入隨機數(shù)等)來實現(xiàn)橢圓曲線密碼的抗功耗攻擊，另一方面則利用新的標量編碼方法(如帶符號的雙基數(shù)系統(tǒng)、帶符號的階乘展開式、帶符號整數(shù)拆分形式)來降低標量乘法運算的計算開銷。而所給基于同種映射的抗功耗攻擊標量乘算法(HM算法)根據(jù)橢圓曲線同種理論，將原始標量乘法運算變換為同種橢圓曲線上的標量乘法運算，再根據(jù)對偶同種恢復原始標量乘法運算結果。所給M算法在執(zhí)行過程中沒有泄露與密鑰相關的功耗信息，因此所給HM算法可以有效抵抗功耗攻擊，并且沒有增加冗余操作，另外也可以利用各類橢圓曲線密碼標量乘快速算法來提升算法的整體運算效率。