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

閆 娜

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

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

閆 娜

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

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

橢圓曲線密碼；功耗攻擊分析；帶符號的整數拆分；多標量乘算法；標量分割

0 引 言

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

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

1 帶符號整數拆分標量乘快速算法

(1)

(2)

算法1 基于SIS的標量乘快速算法

輸入：k，P；

輸出：Q=kP。

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

2. 構造出預計算表Pi；

3. 令Q=O；

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

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

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

5. 返回Q。

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

算法2 預計算表Pi的生成算法

輸入：n，P；

輸出：預計算表Pi。

1. 令Q=O；

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

2.1S=2Q；

2.2Pi=S+P；

2.3Q=Pi+Q；

3. 返回Pi。

2 SIS標量乘潛在的功耗攻擊威脅

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

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

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

3 基于SIS的標量乘抗功耗攻擊方案

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

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

(3)

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

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

kP=(k-r)P+rP=

l1P1+l2P2+…+ltPt=

(4)

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

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

算法3 基于SIS的快速標量乘抗功耗攻擊算法

輸入：k，P；

輸出：kP。

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

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

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

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

5. 構造出預計算表Pi；

6. 令Q=O，E=O；

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

7.1 對于i從1到t，重復執(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 安全性分析

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

圖1 功耗數據采集實驗平臺

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

圖2 基于SIS標量乘算法功耗軌跡

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

圖3 基于SIS標量乘抗功耗攻擊算法功耗軌跡

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

4.2 效率分析

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

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

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

5 結 語

通過結合基于帶符號的整數拆分形式多標量乘快速算法和標量分割隨機化技術所給出的橢圓曲線密碼抗功耗攻擊方案，能夠抵抗多種功耗攻擊，并且具有更加高效的計算效率。同時因為所給新方案構造生成的預計算表為固定的且已知的，因而能夠預先存儲到應用系統(tǒng)中，不再需要重新計算，接下來就僅需考慮主循環(huán)的加密運算。新方案可以更好地應用在安全芯片等一些資源受限的各類便攜式系統(tǒ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] 張友橋，周武能，申曄，等．橢圓曲線密碼中抗功耗分析攻擊的標量乘改進方案[J]．計算機工程與科學，2014，36(4)：644-648．

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

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

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

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

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

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

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

[11]王玉璽，張串絨，張柄虹，等．基于素數域上復合運算的快速標量乘算法[J]．計算機應用研究，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—)，女，河南人，碩士，講師，主要研究方向為計算機應用;

E-mail:xinlinzh2@163.com

TP309

A

1673-5692(2017)04-438-05