閆 娜

(永城職業(yè)學(xué)院 電子信息工程系，河南 永城 476600)

基于帶符號整數(shù)拆分形式的抗功耗攻擊方案

閆 娜

(永城職業(yè)學(xué)院 電子信息工程系，河南 永城 476600)

為抗功耗攻擊橢圓曲線密碼算法的運算效率，文中給出一種基于整數(shù)拆分形式的抗功耗攻擊方案。通過將標(biāo)量進(jìn)行帶符號的整數(shù)拆分形式編碼，同時結(jié)合預(yù)計算和標(biāo)量分割的方法將標(biāo)量乘運算轉(zhuǎn)化為一組橢圓曲線上的點加運算，然后采用基點掩碼實施抗功耗攻擊。算法安全性及性能分析結(jié)果表明，所給方案的運算效率與傳統(tǒng)的抗功耗攻擊方法相比明顯提高，能夠較好地滿足安全芯片等資源受限的應(yīng)用系統(tǒng)。

橢圓曲線密碼；功耗攻擊分析；帶符號的整數(shù)拆分；多標(biāo)量乘算法；標(biāo)量分割

0 引 言

1998年，Paul Kocherr率先提出功耗攻擊方法[1]，它是一種利用密碼芯片在運作時泄露的功率消耗信息而獲得密鑰有關(guān)信息的非常有效的密碼破解技術(shù)，這種攻擊技術(shù)具備實現(xiàn)簡易，攻擊成功率大的優(yōu)勢，同傳統(tǒng)的數(shù)學(xué)攻擊技術(shù)具備更大的威脅[2-3]。根據(jù)攻擊者實施攻擊采用的攻擊方式不同，主要能夠分成簡單功耗攻擊(Simple Power Attack, SPA)與差分功耗攻擊(Differential Power Attack, DPA)等。因把橢圓曲線密碼算法與其它的傳統(tǒng)公鑰密碼算法進(jìn)行比較來說，在同樣的安全級別條件下具備所需密鑰長度更短、存儲空間更小等優(yōu)點，更加適用于密碼芯片等資源受限設(shè)備，因此存在許多針對橢圓曲線密碼的功耗攻擊。當(dāng)前，橢圓曲線功耗攻擊的方式主要包括零值寄存器功耗分析攻擊(Zero-value Power Attack, ZPA)與零值點功耗分析攻擊(Refined Power Attack, RPA)等[4-5]。

通過將標(biāo)量利用帶符號整數(shù)拆分(signed integer splitting , SIS)形式進(jìn)行編碼[6]，把大標(biāo)量乘法運算轉(zhuǎn)化成一組帶系數(shù)的由固定且已知標(biāo)量的小標(biāo)量乘運算的累加和的形式，然后利用標(biāo)量分割的隨機化技術(shù)，同時結(jié)合預(yù)計算表的方法，提出了一種高效安全的基于整數(shù)拆分形式的橢圓曲線密碼抗功耗分析攻擊方案，所給方面不僅能夠抵御各種功耗攻擊方法，而且可以有效大幅提升橢圓曲線密碼抗功耗攻擊算法的計算效率，所以能夠同時兼顧效率與安全兩個方面的需要，因而所給的抗功耗攻擊方案能夠滿足加解密芯片等資源受限制的密碼系統(tǒng)中，具有重要的研究意義與實用價值。

1 帶符號整數(shù)拆分標(biāo)量乘快速算法

(1)

(2)

算法1 基于SIS的標(biāo)量乘快速算法

輸入：k，P；

輸出：Q=kP。

1. 計算(um,um-1,…,u1)；

2. 構(gòu)造出預(yù)計算表Pi；

3. 令Q=O；

4. 對于i從1到n，重復(fù)執(zhí)行：

4.1 若ui=1，則Q=Q+Pi；

4.2 若ui=-1，則Q=Q-Pi；

5. 返回Q。

其中，構(gòu)造的預(yù)計算表Pi=a(i)P是固定的且已知的，詳細(xì)的構(gòu)造算法描述如算法2所示：

算法2 預(yù)計算表Pi的生成算法

輸入：n，P；

輸出：預(yù)計算表Pi。

1. 令Q=O；

2. 對于i從1到n，重復(fù)執(zhí)行：

2.1S=2Q；

2.2Pi=S+P；

2.3Q=Pi+Q；

3. 返回Pi。

2 SIS標(biāo)量乘潛在的功耗攻擊威脅

(1)算法1的步驟4循環(huán)操作中，盡管僅執(zhí)行點加運算，但是對于整體的循環(huán)過程依然有功耗差異，拆分系數(shù)ui=±1時，執(zhí)行了一次點加操作，ui=0時，僅執(zhí)行空操作。攻擊者可根據(jù)點加操作執(zhí)行順序和次數(shù)，能夠推測出標(biāo)量的拆分系數(shù)ui，進(jìn)而可以較為容易地獲取全部的密鑰信息，所以算法1易遭受SPA攻擊。

(2)因為基點P是固定的，它的密鑰信息同輸入之間存在相關(guān)性。攻擊者推測拆分系數(shù)ui錯誤時，在進(jìn)行了多次功耗統(tǒng)計分析后，執(zhí)行空操作與點加操作之間的功耗差異界限不明顯；攻擊者推測拆分系數(shù)ui正確時，在進(jìn)行了多次功耗統(tǒng)計分析后，出現(xiàn)了明顯的功耗差異界限，因而攻擊者能夠推測獲得拆分系數(shù)與類基間的關(guān)系，進(jìn)而能夠推斷出全部的密鑰信息，所以算法1易遭受DPA攻擊。

(3)算法1的標(biāo)量乘法運算中，基點P為固定的，攻擊者能夠利用算法中的特殊點(零值點或是零值寄存器)來進(jìn)行攻擊，進(jìn)而獲得密鑰的有關(guān)信息，所以算法1易遭受RPA和ZPA攻擊。

3 基于SIS的標(biāo)量乘抗功耗攻擊方案

根據(jù)標(biāo)量的拆分表示形式可知，對于所有的不大于所給標(biāo)量的整數(shù)皆能夠由同樣個數(shù)的類基表示，所以能夠利用標(biāo)量分割技術(shù)，不僅可用于抵御功耗攻擊，同時通過引入一個隨機整數(shù)，把大標(biāo)量乘法運算轉(zhuǎn)換成為一組小標(biāo)量乘法運算，并通過共用一個較小的預(yù)計算表，從而可進(jìn)一步提升計算效率。標(biāo)量分割技術(shù)[8]是橢圓曲線標(biāo)量乘運算中用來抵御功耗攻擊的一種盲乘數(shù)的隨機化技術(shù)，通過采用加上隨機數(shù)r的乘數(shù)k′=k+r以代替標(biāo)量k來進(jìn)行標(biāo)量乘運算，即轉(zhuǎn)換為多標(biāo)量乘運算，下面則給出基于標(biāo)量分割技術(shù)的標(biāo)量乘運算的一般形式，如式(3)所示：

kP=(xk+pr)(uP)+(yk+qr)(vP)

(3)

式中，r是隨機整數(shù)，x,y,p,q,u,v是標(biāo)量分割系數(shù)。為有效提升標(biāo)量乘運算的效率，通常會令x,y,p,q,u,v∈{-2,-1,0,1,2}，標(biāo)量的分割次數(shù)能根據(jù)所選的快速算法和安全性需求來確定。

因為當(dāng)基點固定時，預(yù)計算表具有反復(fù)可利用性的特點，因而把大標(biāo)量分割為一組小標(biāo)量，共用同一張較小的預(yù)計算表。采用一次分割為例，假定x=u=q=v=1,p=-1,y=0，則標(biāo)量乘運算kP=(k-r)P+rP。式中通過減去隨機數(shù)r，掩飾了原始標(biāo)量信息與功耗之間的相關(guān)性，所以能夠抵御DPA攻擊。但是攻擊者仍能采用拆分系數(shù)是0和1時執(zhí)行不同操作所產(chǎn)生的功耗差異來實施SPA攻擊，然而采用添加偽操作方法抵御SPA攻擊將造成非必要的效率損失。經(jīng)分析可知，添加偽操作的位與拆分系數(shù)是0的位有關(guān)，可通過將兩個拆分系數(shù)相加而得到一個和系數(shù)li，減少ui和vi單獨是0的位，以此減少須要添加偽操作的數(shù)目，最終實現(xiàn)降低效率損失的目的。同時也可以將和系數(shù)ki看作是一個窗口，窗口的寬度是標(biāo)量分割的次數(shù)的和[9]，因而基于SIS的標(biāo)量乘法運算kP能變化為如式(4)所示：

kP=(k-r)P+rP=

l1P1+l2P2+…+ltPt=

(4)

式中，r是所引入的一個隨機整數(shù)，ui,vi分別是小標(biāo)量(k-r)和r的拆分系數(shù)，t,s分別是小標(biāo)量(k-r)和r的拆分?jǐn)?shù)列的個數(shù)，并且有t≥s，vs+1=vs+2=…=vt=0，所以新構(gòu)造出的預(yù)計算表Pi的長度是t，li是已給標(biāo)量k在進(jìn)行一次分割后的兩個拆分系數(shù)的和系數(shù)，而且有l(wèi)i∈{-2，-1，0，1，2}。因為所得窗口寬度是2，因而有e∈{1，2}，并且可得Qe=∑i:li=ePi。

根據(jù)式(4)可知，標(biāo)量乘法運算轉(zhuǎn)換為一個窗口寬度為2的基于SIS標(biāo)量乘運算，然后結(jié)合抵御SPA攻擊的偽操作方法，下面給出了同時能夠兼顧效率與安全兩方面的基于整數(shù)拆分形式的橢圓曲線密碼抗功耗攻擊的方案。下面算法3給出了基于SIS的橢圓曲線密碼抗功耗攻擊算法的詳細(xì)描述過程：

算法3 基于SIS的快速標(biāo)量乘抗功耗攻擊算法

輸入：k，P；

輸出：kP。

1.r=random(),h=k-r；

2. 計算SIS(h)=(ut,ut-1,…,u1)；

3. 計算SIS(r)=(vt,vt-1,…,v1)；

4. 計算和系數(shù)li=(lt,lt-1,…,l1)；

5. 構(gòu)造出預(yù)計算表Pi；

6. 令Q=O，E=O；

7. 對于e從2到1，重復(fù)執(zhí)行：

7.1 對于i從1到t，重復(fù)執(zhí)行：

7.1.1 若li=e，則E=E+Pi；

7.1.2 若li=-e，則E=E-Pi；

7.1.3 否則li=0，則T=E+P；

7.2Q=Q+E；

8. 返回Q。

4 仿真及性能分析

4.1 安全性分析

可以通過采用文獻(xiàn)[10]給出的功耗仿真實驗平臺對所給抗功耗攻擊方案進(jìn)行抗功耗攻擊實驗仿真，如圖1所示。實驗對象為IC卡智能芯片，其內(nèi)嵌CPU為32位的ARM處理器，并利用VHDL語言對所給設(shè)計方案完成硬件描述；然后選用一個合適的單片機將設(shè)計方案綜合到FPGA開發(fā)板上進(jìn)行模擬仿真，通過選用相關(guān)參數(shù)執(zhí)行指定的加密或解密功能；最后則根據(jù)在VSS與地之間所串聯(lián)的電阻來測量單片機在執(zhí)行加解密運算指令時的功率消耗波形，并把采樣所獲得的數(shù)據(jù)信息存儲到示波器中，接著則通過采用通訊軟件把得到的數(shù)據(jù)傳輸?shù)絇C機上，同時應(yīng)用Matlab等有關(guān)數(shù)據(jù)處理軟件實施數(shù)據(jù)的處理和分析。

圖1 功耗數(shù)據(jù)采集實驗平臺

首先，對算法1的基于SIS標(biāo)量乘算法實施功耗仿真，可以得到未施加任何抗功耗攻擊措施的功耗軌跡波形圖譜，如圖2所示。

圖2 基于SIS標(biāo)量乘算法功耗軌跡

算法3中，通過使用標(biāo)量分割的技術(shù)，把標(biāo)量減去一個隨機的整數(shù)，從而把密鑰信息隨機化，使得攻擊者不能夠獲取中間運算結(jié)果與已給輸入之間的相關(guān)性信息，因此所給的方案能抵御DPA攻擊。并且由于參與標(biāo)量乘運算的標(biāo)量已被隨機化，使得攻擊者無法找到特殊點加以利用，因而所給算法也能夠抵抗ZPA和RPA攻擊。在步驟7循環(huán)操作中，因為和系數(shù)li依然能夠是0，因此在步驟7.1.3中添加偽操作，從而使得每次循環(huán)運算中皆執(zhí)行兩次點加操作，使其能量圖譜不存在功耗差異，從而攻擊者無法獲得相關(guān)信息來進(jìn)行密鑰猜測，因而所給算法能夠抵御SPA攻擊。對算法3的基于SIS標(biāo)量乘抗功耗攻擊算法進(jìn)行功耗仿真實驗，能夠得到施加抗功耗攻擊措施之后的功耗軌跡波形圖譜，如圖3所示。

圖3 基于SIS標(biāo)量乘抗功耗攻擊算法功耗軌跡

從圖2和圖3能夠看出，在沒有施加抗功耗攻擊措施的基于SIS標(biāo)量乘算法，其功耗軌跡波形的圖譜具有明顯的可分辨性，執(zhí)行點加操作和空操作在圖譜上具有明顯的界限，所以攻擊者能夠?qū)嵤┕墓?。然后，在實施抗功耗攻擊的措施之后，算?的功耗軌跡波形圖譜卻沒有明顯地波形起伏，攻擊者可對大量功耗軌跡曲線進(jìn)行統(tǒng)計分析卻無法得到相關(guān)性的信息，所以攻擊者無法對算法3實施功耗分析攻擊。

4.2 效率分析

算法3中，步驟1、2、3和4所需運算量能夠忽略不計。因為預(yù)計算表已知且固定，能夠預(yù)先存儲到應(yīng)用系統(tǒng)中，不再需要重復(fù)進(jìn)行計算。步驟7中的主循環(huán)運算所需的運算量是tA。其中，D是倍點運算，A是點加運算，c是大標(biāo)量的二進(jìn)制編碼長度，t是進(jìn)行一次標(biāo)量分割后的小標(biāo)量的SIS編碼長度，w是窗口寬度，一般令w=4，b=?c/w」。通常認(rèn)為橢圓曲線密碼512比特的密鑰是安全的，也即c=512。在進(jìn)行了一次標(biāo)量分割后，則有小標(biāo)量的整數(shù)拆分形式的最大編碼長度是t=323。文獻(xiàn)[11]中給出在仿射坐標(biāo)系下，倍點運算是D=11M，點加運算是A=6M，M是模乘運算。下面的表1則給出了算法3和WBRIP算法、EBRIP算法[12]三種抗功耗攻擊方案在執(zhí)行效率方面的分析比較。

從表1能夠看出，算法3與WBRIP算法和EBRIP算法功耗攻擊方案相比，效率分別提高了69.72%和10.94%，這將在很大程度上滿足芯片等便攜式設(shè)備的高效性需求，同時也說明在固定基點的標(biāo)量乘運算中，所給新方案具有更優(yōu)良的性能。另外，還能夠根據(jù)安全和效率的需求實施多次標(biāo)量分割。根據(jù)性能分析的結(jié)果表明：所給方案能夠滿足安全和效率兩個方面的需要，尤其是能夠適用于對于存儲空間要求不是很高的密碼加密部件等應(yīng)用系統(tǒng)中。

表1 算法3和WBRIP算法、EBRIP算法抗功耗攻擊方案的執(zhí)行效率比較分析

5 結(jié) 語

通過結(jié)合基于帶符號的整數(shù)拆分形式多標(biāo)量乘快速算法和標(biāo)量分割隨機化技術(shù)所給出的橢圓曲線密碼抗功耗攻擊方案，能夠抵抗多種功耗攻擊，并且具有更加高效的計算效率。同時因為所給新方案構(gòu)造生成的預(yù)計算表為固定的且已知的，因而能夠預(yù)先存儲到應(yīng)用系統(tǒng)中，不再需要重新計算，接下來就僅需考慮主循環(huán)的加密運算。新方案可以更好地應(yīng)用在安全芯片等一些資源受限的各類便攜式系統(tǒng)中，具有很好的理論研究和實際應(yīng)用價值。

[1] Kocher P,Jaffe J, Jun B. Introcuction to differential power analysis and related attacks [EB/OL]. http://www.Cryptography.com/dpa/technical,1998.

[2] Kocher P,Jaffe J,Jun B. Differential power analysis [C]. Advanced in Cryptology-CRYPTO’99. Cali- fornia, USA：Springer Verlag，1999：388-397．

[3] 張友橋，周武能，申曄，等．橢圓曲線密碼中抗功耗分析攻擊的標(biāo)量乘改進(jìn)方案[J]．計算機工程與科學(xué)，2014，36(4)：644-648．

[4] 姚建波，張濤．抗側(cè)信道攻擊的安全有效橢圓加密算法[J]．計算機應(yīng)用研究，2012，29(12)：4639-4643．

[5] 王正義，趙俊閣．基于帶符號雙基數(shù)系統(tǒng)的抗功耗攻擊方案算法[J]．計算機應(yīng)用，2011，31(11)：2973-2974．

[6] 張亮．改進(jìn)的基于整數(shù)拆分形式標(biāo)量乘快速算法[J]．中國電子科學(xué)研究院學(xué)報，2016，11(5)：56-59．

[7] 石潤華，鐘誠．一種快速的橢圓曲線標(biāo)量乘方法[J]．計算機工程與應(yīng)用，2006，(2)：156-158．

[8] 童蓮，劉寧，錢江．改進(jìn)的抗能量分析的橢圓曲線標(biāo)量乘算法[J]．計算機工程與應(yīng)用，2011，47(33)：68-70．

[9] 陳厚友，馬傳貴．橢圓曲線密碼中一種多標(biāo)量乘算法[J]. 軟件學(xué)報，2011，22(4)：782-788．

[10]羅鵬，馮登國，周永彬．功耗分析攻擊中的功耗與數(shù)據(jù)相關(guān)性模型[J]．通信學(xué)報，2012，33(z1)：276-281．

[11]王玉璽，張串絨，張柄虹，等．基于素數(shù)域上復(fù)合運算的快速標(biāo)量乘算法[J]．計算機應(yīng)用研究，2013，30(11)：3365-3387．

[12]Mamiya H. Efficient countermeasures against RPA, DPA and SPA [C]. Proc of Cryptographic Hardware and Embedded System. 2004：343-356．

Resisting Power Attacks Scheme Based on Signed Integer Splitting Form

YAN Na

(Department of Electronic Information Engineering, Yongcheng Vocational College, Yongcheng 476600, China)

The contradiction between efficiency and security lies in the scheme of resisting power analysis attack for ellipse curve cryptography due to the limited resource of security chip. Combining with the method of the pre-computation table and scalar division, scalar multiplication was turned into a set of point addition of ellipse curve by coding the scalar with signed integer splitting form. And then a scheme based on Signed Integer Splitting Form was presented by basic point masking algorithm. Security and performance analysis shows that the improved scheme has higher efficiency comparing with other resisting power analysis attacks and could be used in the limited resource system preferably.

Ellipse Curve Cryptography (ECC); power analysis attack; Signed Integer Splitting (SIS); multiple scalar multiplication algorithm; scalar division

10.3969/j.issn.1673-5692.2017.04.020

2017-05-27

2017-07-01

河南省科技發(fā)展計劃項目(152102210039)

閆 娜(1982—)，女，河南人，碩士，講師，主要研究方向為計算機應(yīng)用;

E-mail:xinlinzh2@163.com

TP309

A

1673-5692(2017)04-438-05