李芳菊

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

0 引 言

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

1 橢圓曲線密碼標(biāo)量乘算法

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

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

(1)

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

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

E：y2=x3+ax+b

(2)

其中，a,b∈K。橢圓曲線E上點(diǎn)的集合及一個(gè)無(wú)窮遠(yuǎn)點(diǎn)O可以構(gòu)成一個(gè)阿貝爾群。

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

(3)

橢圓曲線密碼的標(biāo)量乘法運(yùn)算如下式(4)所示：

(4)

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

(5)

標(biāo)量乘算法采用二進(jìn)制編碼可以將標(biāo)量乘運(yùn)算分解為點(diǎn)加運(yùn)算與倍點(diǎn)運(yùn)算，如下式(6)所示：

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

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

(6)

則采用二進(jìn)制編碼的標(biāo)量乘算法如下面算法1所示。

算法1 二進(jìn)制編碼的標(biāo)量乘算法

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

輸出：Q=kP。

(1) 令Q=O，其中O無(wú)窮遠(yuǎn)點(diǎn)；

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

①Q(mào)=2Q；

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

(3) 返回Q。

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

2 功耗攻擊及其防御

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

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

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

(2) 測(cè)量每一個(gè)輸入的明文對(duì)應(yīng)的功耗曲線；

(3) 計(jì)算猜測(cè)的中間值；

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

(5) 計(jì)算猜測(cè)的模擬功耗值與實(shí)際測(cè)量功耗的統(tǒng)計(jì)相關(guān)性。

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

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

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

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

3 橢圓曲線同種理論

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

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

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

(7)

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

4 基于同種映射的標(biāo)量乘算法

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

(8)

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

(9)

則可用如下同種映射模型來(lái)等價(jià)變換計(jì)算標(biāo)量乘運(yùn)算Q=[k]P，如圖1所示。

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

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

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

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

輸出：Q=kP。

(2) 計(jì)算點(diǎn)P的同種映射P′=φ(P)；

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

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

(6) 返回Q。

5 效率及安全性分析

6 結(jié) 語(yǔ)

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