抗SPA攻擊的橢圓曲線NAF標(biāo)量乘實現(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具有安全性高、計算量小、處理速度快、存儲空間占用小、帶寬要求低的特點。與RSA公鑰體制相比，ECC非常適合于資源有限的嵌入式移動環(huán)境，如Smartcard上的密碼芯片。

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

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

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

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

2.1 二元非相鄰形式

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

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

算法1 二元NAF算法

輸入：k

輸出：NAF(k)

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

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

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

3) k具有唯一的NAF。

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

2.2 二元NAF范例

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

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

由表1可知k=0x12345進行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進行NAF編碼，然后再進行標(biāo)量乘運算，標(biāo)量乘算法如算法2所示。

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

輸入：k，P

輸出：kP

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

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

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

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

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

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

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

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

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

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

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

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

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

當(dāng)ki′=1時，進行Q←2Q與Q←Q+P運算，即一次倍點運算和一次點加運算，如圖4所示。

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

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

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

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

圖6 對圖2所示波形進行SPA攻擊

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

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

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

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

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

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

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

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

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

輸入：k，P

輸出：kP

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

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

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

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

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

圖8 對圖7進行SPA分析攻擊

4.4 效率損失分析

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

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

5 結(jié)束語

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