抗SPA攻擊的橢圓曲線NAF標(biāo)量乘實(shí)現(xiàn)算法

王敏，吳震

(成都信息工程學(xué)院 網(wǎng)絡(luò)工程學(xué)院，四川 成都 610000)

1 引言

1985年，Miller和Kibitz首次將橢圓曲線應(yīng)用于密碼系統(tǒng)后，橢圓曲線密碼系統(tǒng)(elliptic curve cryptography, ECC)[1]已受到越來越多的關(guān)注。ECC具有安全性高、計(jì)算量小、處理速度快、存儲空間占用小、帶寬要求低的特點(diǎn)。與RSA公鑰體制相比，ECC非常適合于資源有限的嵌入式移動環(huán)境，如Smartcard上的密碼芯片。

由于NAF標(biāo)量乘法[2,3]運(yùn)算效率高，所以當(dāng)前橢圓曲線標(biāo)量乘的實(shí)現(xiàn)大多采用此算法，但NAF標(biāo)量乘法最易受到邊信道攻擊(SCA, side channel attack)。SCA是在1996年由P. Kocher提出的一種利用加密過程中的計(jì)算時(shí)間或能量消耗來分析秘密消息的攻擊方法，基本上分為2類，簡單能量分析(SPA, simple power analysis)和差分能量分析(DPA, differential power analysis)。所謂簡單能量分析是指分析一個(gè)設(shè)備上一次密碼操作所消耗的能量。因?yàn)閷Σ煌牟僮饔胁煌芰肯模@樣對應(yīng)不同的能量消耗，攻擊者可以判斷以什么樣的順序進(jìn)行了什么樣的操作。當(dāng)將多種監(jiān)聽數(shù)據(jù)與概率的分析工具結(jié)合在一起時(shí)，攻擊的成功率更高，即為差分能量分析。

為了既能發(fā)揮NAF標(biāo)量乘法運(yùn)算效率高的優(yōu)點(diǎn)，又能很好地抵抗SPA攻擊，本文提出一種新的標(biāo)量乘實(shí)現(xiàn)算法——平衡能量NAF標(biāo)量乘法。平衡能量NAF標(biāo)量乘法不僅很好地繼承了NAF標(biāo)量乘法運(yùn)算效率高的優(yōu)點(diǎn)，并且通過對功耗信息的實(shí)際分析驗(yàn)證，平衡能量NAF標(biāo)量乘法還能夠有效地抵抗SPA攻擊。

2 橢圓曲線NAF標(biāo)量乘法

標(biāo)量乘kP是橢圓曲線密碼算法的核心，并且標(biāo)量乘的運(yùn)算效率直接關(guān)系到整個(gè)橢圓曲線密碼算法的實(shí)現(xiàn)效率。標(biāo)量乘的實(shí)現(xiàn)算法很多，主要有二進(jìn)制標(biāo)量乘法、NAF標(biāo)量乘法等。其中，NAF標(biāo)量乘法對密鑰k進(jìn)行了NAF編碼，使得密鑰k的漢明重量減少，使得運(yùn)算效率相對于二進(jìn)制標(biāo)量乘法有了很大的提高，因此在橢圓曲線標(biāo)量乘中得到了廣泛的應(yīng)用。

2.1 二元非相鄰形式

二元非相鄰形式(NAF, non-adjacent form)是對標(biāo)量乘kP中密鑰k進(jìn)行轉(zhuǎn)換，表示為類似于二進(jìn)制數(shù)序列的形式，但是序列中每個(gè)位置除了1和0以外，也會有-1，并且在k的表示序列中不會有相鄰的非零元素出現(xiàn)，即且，亦即

計(jì)算一個(gè)正整數(shù)k的二元NAF算法如算法1所示。

算法1 二元NAF算法

輸入：k

輸出：NAF(k)

二元NAF具有以下性質(zhì)。

1) NAF(k)在k的所有帶符號表示序列中非零位個(gè)數(shù)最少。

2) NAF(k)的長度最多比k的二進(jìn)制表示形式的長度大1。

3) k具有唯一的NAF。

4) 所有長度為m的NAF中非零元素的平均個(gè)數(shù)約為m/3。

2.2 二元NAF范例

設(shè)k=0x12345，根據(jù)算法1所示二元NAF算法可算出k的二元NAF編碼如表1所示。

表1 k=0x12345對應(yīng)二元NAF編碼

由表1可知k=0x12345進(jìn)行NAF編碼后k=(1,0,1,0,0,0,1,0,-1,0,1,0,0,1,0,0,1)NAF。

2.3 NAF標(biāo)量乘法

NAF標(biāo)量乘法是首先按照算法1將密鑰k進(jìn)行NAF編碼，然后再進(jìn)行標(biāo)量乘運(yùn)算，標(biāo)量乘算法如算法2所示。

算法2 NAF標(biāo)量乘算法

輸入：k，P

輸出：kP

2.4 NAF標(biāo)量乘法效率分析

設(shè)密鑰k的二進(jìn)制表示序列長度為l1，二元NAF表示序列長度為l2，一次倍點(diǎn)的運(yùn)算時(shí)間為t1，由于點(diǎn)加和點(diǎn)減運(yùn)算時(shí)間相差無幾，所以設(shè)一次點(diǎn)加或點(diǎn)減的運(yùn)算時(shí)間均為t2。

一般情況下，k的二進(jìn)制序列中1的個(gè)數(shù)約為l1/2，則一次二進(jìn)制標(biāo)量乘算法的運(yùn)算時(shí)間T1約為l1次倍點(diǎn)運(yùn)算與l1/2次點(diǎn)加運(yùn)算所消耗時(shí)間的總和。

又由二元NAF的性質(zhì)可知l2≤l1+1，將l2≤l1+1與式(1)代入式(2)后得

由式(4)可知NAF標(biāo)量法相對于二進(jìn)制標(biāo)量乘法在效率上有很大提高。

3 針對NAF標(biāo)量乘法的SPA攻擊

針對NAF標(biāo)量乘法的SPA攻擊，是通過采集密碼芯片在進(jìn)行NAF標(biāo)量乘運(yùn)算過程的功耗波形，利用密鑰與運(yùn)算間的相關(guān)性從功耗波形中對密鑰進(jìn)行分析提取。由算法2可知整個(gè)NAF標(biāo)量乘運(yùn)算主要包括2QQ←、QQP←+和QQP←-這3種運(yùn)算，且當(dāng)ik取值不同所進(jìn)行的運(yùn)算類型也不同，如表2所示。

表2 ki取值與運(yùn)算類型對應(yīng)關(guān)系

由于密鑰k較長，為便于分析說明，對密鑰進(jìn)行簡化，只取密鑰k的低8bit為0xF1，其余比特均為0，即k=0xF1，對密鑰k進(jìn)行NAF編碼后為k′= (1000 -10001)NAF，從功耗分析平臺采集一次密碼芯片標(biāo)量乘運(yùn)算的功耗波形如圖1所示。

圖1 一次NAF標(biāo)量乘法功耗波形

由圖1可知，一次NAF標(biāo)量乘運(yùn)算主要包括預(yù)處理和乘法運(yùn)算2部分，預(yù)處理中進(jìn)行一些乘法運(yùn)算前的操作，乘法運(yùn)算部分為與密鑰k′有關(guān)的部分，由于k′長度為9，最高比特81k′=且只做賦值操作，因此與k′有關(guān)的功耗波形部分為乘法運(yùn)算部分的前8bit，將其放大后如圖2所示。

圖2 與k’相關(guān)運(yùn)算功耗波形

圖3 k’=0時(shí)相關(guān)運(yùn)算功耗波形

當(dāng)ki′=1時(shí)，進(jìn)行Q←2Q與Q←Q+P運(yùn)算，即一次倍點(diǎn)運(yùn)算和一次點(diǎn)加運(yùn)算，如圖4所示。

當(dāng)ki′=-1時(shí)，進(jìn)行Q←2Q與Q←Q+P運(yùn)算，即一次倍點(diǎn)運(yùn)算和一次點(diǎn)減運(yùn)算，如圖5所示。

圖4 k’=1時(shí)相關(guān)運(yùn)算功耗波形

圖5 k’=-1時(shí)相關(guān)運(yùn)算功耗波形

由以上分析可知，當(dāng)密鑰ki′=0時(shí)只進(jìn)行一次倍點(diǎn)運(yùn)算，當(dāng)ki′非0時(shí)除了一次倍點(diǎn)運(yùn)算還需要進(jìn)行一次點(diǎn)加或點(diǎn)減運(yùn)算，在功耗波形中，0與非0很容易分辨出，1和-1的區(qū)別在于當(dāng)ki′=1時(shí)進(jìn)行了一次點(diǎn)加運(yùn)算，當(dāng)ki′=-1時(shí)進(jìn)行一次點(diǎn)減運(yùn)算，點(diǎn)加與點(diǎn)減的功耗波形從圖4與圖5中可看出明顯的區(qū)別，基于以上分析對圖2所示功耗波形進(jìn)行SPA攻擊，結(jié)果如圖6所示。

圖6 對圖2所示波形進(jìn)行SPA攻擊

根據(jù)圖6所示分析結(jié)果k′=(1000-1000)NAF，又k′最高一位k8′=1，所以k′的SPA攻擊結(jié)果為k′=(1000-10001)NAF，然后根據(jù)NAF編碼原理，對k進(jìn)行分析，得出k=0xF1，與真實(shí)密鑰相同，因此SPA攻擊結(jié)果正確。

4 平衡能量NAF標(biāo)量乘法

NAF標(biāo)量乘法相對于二進(jìn)制標(biāo)量乘法雖然在運(yùn)算效率上有很大提高，但是從對NAF標(biāo)量乘法的SPA攻擊中可知NAF標(biāo)量乘法不能很好地抵抗SPA攻擊，對于信息的安全構(gòu)成很大的威脅。

4.1 平衡能量NAF標(biāo)量乘法的提出

為了使得NAF標(biāo)量乘法在運(yùn)算效率上表現(xiàn)出很好特性的同時(shí)，又能抵抗SPA攻擊，增強(qiáng)私鑰運(yùn)算的安全性，在此需對NAF標(biāo)量乘的實(shí)現(xiàn)算法以及對NAF標(biāo)量乘的SPA攻擊原理進(jìn)行分析。對于NAF標(biāo)量乘的SPA攻擊點(diǎn)主要在于ik′在不同值的時(shí)候進(jìn)行不同操作，且這些不同的操作在功耗曲線中表現(xiàn)出不同的特性，于是根據(jù)密鑰ik′與功耗波形間的相關(guān)性對ik′進(jìn)行分析。為了掩蓋這種相關(guān)性，本文提出一種新的既不損失NAF標(biāo)量乘法運(yùn)算效率，又能很好地抵抗SPA攻擊的NAF標(biāo)量乘實(shí)現(xiàn)算法——平衡能量NAF標(biāo)量乘法。

4.2 平衡能量NAF標(biāo)量乘法實(shí)現(xiàn)原理

為了消除ki′與功耗曲線間的相關(guān)性，由以上對NAF標(biāo)量乘的SPA攻擊分析可知在功耗中表現(xiàn)的區(qū)別在于點(diǎn)加運(yùn)算（Q←Q+P）與點(diǎn)減運(yùn)算（Q←Q-P）在功耗波形中表現(xiàn)出不同的特性。根據(jù)有限域運(yùn)算法則可知Q-P=Q+(-P)，于是對NAF標(biāo)量乘實(shí)現(xiàn)算法進(jìn)行修改，在每次標(biāo)量乘運(yùn)算之前做一次求-P的預(yù)處理，將時(shí)進(jìn)行的運(yùn)算Q←Q-P改為Q←Q+(-P)，使得無論當(dāng)ki′=1或者ki′=-1時(shí)都進(jìn)行點(diǎn)加運(yùn)算，進(jìn)而使得時(shí)的功耗波形相同，隱藏密鑰ki′在非零時(shí)與運(yùn)算的相關(guān)性，以至于攻擊者無法從功耗波形中分辨出1和-1，提高標(biāo)量乘法抵抗SPA攻擊的能力。

平衡能量NAF標(biāo)量乘算法如算法3所示。

算法3 平衡能量NAF標(biāo)量乘算法

輸入：k，P

輸出：kP

4.3 平衡能量NAF標(biāo)量乘法抗SPA攻擊分析

為了驗(yàn)證平衡能量NAF標(biāo)量乘法抵抗SPA攻擊的作用，同樣取密鑰k=0xF1，對k進(jìn)行NAF編碼后，采集在密碼芯片中運(yùn)行一次平衡能量NAF標(biāo)量乘運(yùn)算的功耗波形，并對與k′相關(guān)的功耗波形部分進(jìn)行截取放大后，如圖7所示。

圖7 與k′相關(guān)的平衡能量NAF標(biāo)量乘運(yùn)算功耗波形

根據(jù)SPA攻擊原理對圖7所示功耗波形進(jìn)行SPA攻擊，攻擊結(jié)果如圖8所示。

由圖8所示可知，密鑰k′的攻擊結(jié)果為k′=(100010001)NAF，對k′進(jìn)行NAF譯碼后k=0x 111，攻擊結(jié)果與真實(shí)密鑰k=0xF1不同，SPA攻擊失敗，由此可知平衡能量NAF標(biāo)量乘法能夠很好地抵抗SPA攻擊。

圖8 對圖7進(jìn)行SPA分析攻擊

4.4 效率損失分析

平衡能量NAF標(biāo)量乘法相對于NAF標(biāo)量乘法只是將點(diǎn)減運(yùn)算（Q←Q-P）替換為點(diǎn)加運(yùn)算（Q←Q+(-P)），且在標(biāo)量乘運(yùn)算前多進(jìn)行一次求-P的操作，由于點(diǎn)加與點(diǎn)減的運(yùn)算量相差無幾，且一次求-P的運(yùn)算量也很小，可以忽略不計(jì)，因此平衡能量NAF標(biāo)量乘法相對于NAF標(biāo)量乘法沒有效率的損失，保留了NAF標(biāo)量乘法運(yùn)算效率高的特點(diǎn)。

根據(jù)以上分析，平衡能量NAF標(biāo)量乘法不僅繼承了NAF標(biāo)量乘法運(yùn)算效率高的特點(diǎn)，而且能夠很好地抵抗SPA攻擊。

5 結(jié)束語

密碼算法雖然需要考慮運(yùn)算效率的問題，盡可能地減少加解密時(shí)間，但是更重要的是要確保密碼算法的安全性。NAF標(biāo)量乘法相對于二進(jìn)制標(biāo)量乘法雖然有了運(yùn)算效率的提高，但是通過對NAF標(biāo)量乘法的SPA攻擊分析可知，利用SPA攻擊方法很容易就可獲取密鑰k，對信息的安全構(gòu)成很大的威脅。平衡能量NAF標(biāo)量乘法很好地解決了NAF標(biāo)量乘法安全性弱的問題。平衡能量NAF標(biāo)量乘法不僅繼承了NAF標(biāo)量乘法運(yùn)算效率高的優(yōu)點(diǎn)，并且通過實(shí)測波形驗(yàn)證，平衡能量NAF標(biāo)量乘法能夠很好地抵抗SPA攻擊。

[1] KOBLITZ N. Elliptic curve cryptosystems[J]. Mathematics of Computation, 1987, 48(177): 203-209.

[2] ZHAO Q J, LI X P, DAI Z B, etal. Research for parallel computation on NAF scalar multiplication[J]. Application of Electronic Technique,2010.160-164.

[3] LIU D, DAI Y Q. A new algorithm of elliptic curve multi-scalar multiplication[J]. Chinese Journal of Computers, 2008.1131-1137.

[4] WANG M, WU Z. Simple power analysis attack on random pseudo operations[J]]. Journal on Communications, 2012,33(5):138-142.

[5] WU Z, CHEN Y, CHEN J, etal. Exponential information’s extraction from power traces of modulo exponentiation implemented on FPGA[J].Journal on Communications, 2010,31(2):17-21.