楊 蘇，楊穎輝

(河南牧業(yè)經(jīng)濟(jì)學(xué)院 a.實(shí)踐教學(xué)設(shè)備管理處； b.信息與電子工程學(xué)院，鄭州 450044)

一種高效的安全SoC芯片抗功耗攻擊方案

楊 蘇a，楊穎輝b

(河南牧業(yè)經(jīng)濟(jì)學(xué)院 a.實(shí)踐教學(xué)設(shè)備管理處； b.信息與電子工程學(xué)院，鄭州 450044)

安全芯片有資源受限的問(wèn)題，這致使橢圓曲線密碼算法抵抗功耗攻擊的方案在效率和安全兩方面產(chǎn)生了矛盾。首先利用帶符號(hào)的整數(shù)拆分形式對(duì)標(biāo)量進(jìn)行編碼，并采用預(yù)計(jì)算和標(biāo)量分割技術(shù)把標(biāo)量乘運(yùn)算變換成一組橢圓曲線上的點(diǎn)的點(diǎn)加運(yùn)算，進(jìn)而利用基點(diǎn)掩碼實(shí)現(xiàn)橢圓曲線密碼的抗功耗攻擊。算法安全性及性能分析結(jié)果表明，基于整數(shù)拆分的抗功耗攻擊方案的運(yùn)算效率與傳統(tǒng)的抗功耗攻擊方法相比明顯提高，可以很好地滿足安全芯片等資源受限的應(yīng)用系統(tǒng)。

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

0 引 言

功耗攻擊技術(shù)是1998年由Paul Kocher率先提出的一種利用芯片工作時(shí)泄露的功耗信息來(lái)獲取密鑰信息的密碼分析方法，這種攻擊方法實(shí)現(xiàn)簡(jiǎn)單，攻擊成功率高，比傳統(tǒng)的數(shù)學(xué)攻擊方法具有更大的威脅[1-4]。根據(jù)攻擊手段不同，可分為簡(jiǎn)單功耗分析(Simple Power Attack, SPA)與差分功耗分析(Differential Power Attack, DPA)。由于橢圓曲線密碼算法(Elliptic Curve Cryptogram, ECC)與其他傳統(tǒng)公鑰密碼算法相比，在相同安全級(jí)別下需要的密鑰更短，存儲(chǔ)空間更小的優(yōu)點(diǎn)，更適合密碼芯片等資源受限的設(shè)備，所以出現(xiàn)大量針對(duì)橢圓曲線密碼的功耗攻擊。目前，主要有零值寄存器功耗分析(Zero-value Power Analysis, ZPA)和零值點(diǎn)功耗分析(Refined Power Analysis, RPA)[5-8]。本文通過(guò)對(duì)標(biāo)量進(jìn)行帶符號(hào)整數(shù)拆分形式編碼(signed integer splitting form, SISF)，將大標(biāo)量乘運(yùn)算轉(zhuǎn)換成一組帶系數(shù)的由固定且已知標(biāo)量的小標(biāo)量乘運(yùn)算累加和的形式，然后利用標(biāo)量分割隨機(jī)化技術(shù)，并結(jié)合預(yù)計(jì)算表方法，提出一種橢圓曲線密碼的抗功耗攻擊方案，可以滿足密碼芯片等資源受限系統(tǒng)兼顧效率和安全的需求。

1 背景知識(shí)介紹

(1)

式中:n為任意正整數(shù)；ui表示拆分系數(shù)；a(i)為拆分?jǐn)?shù)列。

文獻(xiàn)[6]中根據(jù)數(shù)學(xué)模型抽象出了拆分?jǐn)?shù)列a(n)的定義，即有

其中a(1)=1,n≥2，并且使用歸納法對(duì)于該定理的正確性進(jìn)行了證明，同時(shí)也具體描述了整數(shù)k的帶符號(hào)整數(shù)拆分形式編碼算法。通過(guò)將整數(shù)拆分表示形式應(yīng)用于橢圓曲線密碼標(biāo)量乘法運(yùn)算中，并利用預(yù)計(jì)算方法，可以將大標(biāo)量乘法運(yùn)算變換成一組橢圓曲線上的點(diǎn)的點(diǎn)加運(yùn)算形式，所以標(biāo)量乘kP的形式能轉(zhuǎn)化成：

u1·a(1)P+u2·a(2)P+…+un·a(n)P=

u1·P1+u2·P2+…+un·Pn

(2)

算法1基于SISF的橢圓曲線標(biāo)量乘算法。

輸入：k,P；

輸出：Q=kP。

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

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

3.令Q=O；

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

4.1 如果ui=1，則Q=Q+Pi；

4.2 如果ui=-1，則Q=Q-Pi；

5.返回Q。

其中，預(yù)計(jì)算表Pi=a(i)P是固定并且也是已知的，其詳細(xì)的構(gòu)造算法為：

算法2預(yù)計(jì)算表Pi生成算法。

輸入：n,P；

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

1.令Q=O；

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

2.1S=2Q；

2.2Pi=S+P；

2.3Q=Pi+Q；

3.返回Pi。

2 新方案設(shè)計(jì)

算法1步驟4循環(huán)操作中，雖然只執(zhí)行點(diǎn)加操作，然而在整個(gè)循環(huán)過(guò)程中仍然存在功耗差異，當(dāng)拆分系數(shù)ui=±1時(shí)，需實(shí)施一次點(diǎn)加運(yùn)算，而當(dāng)ui=0時(shí)，執(zhí)行空操作。由于基點(diǎn)P固定，致使密鑰信息與輸入之間具有相關(guān)性，從而導(dǎo)致標(biāo)量乘法運(yùn)算中存在有特殊點(diǎn)。所以算法1易遭受SPA、DPA、RPA和ZPA攻擊。根據(jù)標(biāo)量的拆分表示形式可知，對(duì)于所有不大于該標(biāo)量的整數(shù)都可以由相同個(gè)數(shù)的類基表示，則可以利用標(biāo)量分割的方法，不僅可以用來(lái)抵抗功耗攻擊，而且通過(guò)引入一個(gè)隨機(jī)整數(shù)，將大標(biāo)量化為一組小標(biāo)量，共用一張較小的預(yù)計(jì)算表，能夠進(jìn)一步提高運(yùn)算效率。標(biāo)量分割法是橢圓曲線標(biāo)量乘運(yùn)算中用于抵抗功耗攻擊的一種盲乘數(shù)隨機(jī)化技術(shù)，利用加上隨機(jī)數(shù)r的乘數(shù)k′=k+r來(lái)替代標(biāo)量k進(jìn)行標(biāo)量乘運(yùn)算，轉(zhuǎn)化為多標(biāo)量乘運(yùn)算，基于標(biāo)量分割方法的標(biāo)量乘運(yùn)算一般形式為[7-10]：

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

(3)

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

由于基點(diǎn)固定時(shí)，預(yù)計(jì)算表具有反復(fù)可利用性，所以將大標(biāo)量分割成一組小標(biāo)量，共用同一張較小的預(yù)計(jì)算表。以一次分割為例，令x=u=q=v=1,p=-1,y=0，則有標(biāo)量乘運(yùn)算kP=(k-r)P+rP。通過(guò)減去隨機(jī)數(shù)r，掩蓋了原始標(biāo)量信息與功耗的相關(guān)性，因而可以抵抗DPA攻擊。然而攻擊者仍可利用拆分系數(shù)為0和1時(shí)執(zhí)行不同操作而產(chǎn)生的功耗差異實(shí)施SPA攻擊，而通過(guò)添加偽操作抵抗SPA攻擊會(huì)造成不必要的效率損失。經(jīng)分析可知，添加偽操作的位與拆分系數(shù)為0的位有關(guān)，可通過(guò)將兩個(gè)拆分系數(shù)相加得到一個(gè)和系數(shù)li，減少ui和vi單獨(dú)為0的位，以減少需要添加偽操作的個(gè)數(shù)，從而降低效率損失。同時(shí)可以將和系數(shù)ki看作一個(gè)窗口，窗口寬度為標(biāo)量分割的次數(shù)的和[12]，則有基于SISF標(biāo)量乘法運(yùn)算kP可變換為：

kP=(k-r)P+rP=

(u1·a(1)P+u2·a(2)P+…+ua·a(t)P)+

(v1·a(1)P+v2·a(2)P+…+vt·a(t)P)=

(u1·P1+u2·P2+…+ut·Pt)+

(v1·P1+v2·P2+…+vt·Pt)=

(u1+v1)P1+(u2+v2)P2+…+(ut+vt)Pt=

(4)

根據(jù)式(4)可知，標(biāo)量乘法運(yùn)算轉(zhuǎn)化為一個(gè)窗口寬度為2的基于SISF標(biāo)量乘運(yùn)算，結(jié)合抵抗SPA攻擊的偽操作法，給出兼顧效率與安全的橢圓曲線密碼抗功耗攻擊方案?；赟ISF的ECC抗功耗攻擊算法的詳細(xì)過(guò)程描述為：

算法3基于SISF的橢圓曲線密碼抗功耗攻擊算法。

輸入：k,P；

輸出：kP。

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

2.計(jì)算SISF(h)=(ut,ut-1,…,u1)；

3.計(jì)算SISF(r)=(vt,vt-1,…,v1)；

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

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

6.令Q=O,E=O；

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

7.1 對(duì)于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。

3 方案性能分析

算法3中，通過(guò)采用標(biāo)量分割的方法，將標(biāo)量減去一個(gè)隨機(jī)整數(shù)，使得密鑰信息隨機(jī)化，攻擊者無(wú)法獲得中間結(jié)果與輸入之間的相關(guān)性信息，因而該方案可抵抗DPA攻擊。且由于參與標(biāo)量乘法運(yùn)算的標(biāo)量已被隨機(jī)化，使得攻擊者無(wú)法找到特殊點(diǎn)可以利用，所以該算法也可以抵抗ZPA和RPA攻擊。在步驟7的循環(huán)運(yùn)算中，由于此時(shí)的和系數(shù)li仍然可為0，故在步驟7.1.3添加偽操作，從而每次循環(huán)運(yùn)算中都執(zhí)行兩次點(diǎn)加操作，使其能量圖譜不存在功耗差異，因此，攻擊者無(wú)法獲取相關(guān)信息進(jìn)行密鑰猜測(cè)，故該算法可以抵抗SPA攻擊。

表1 算法3與WBRIP算法、EBRIP算法抗功耗攻擊方案效率分析比較

從表1可以看出，算法3與WBRIP算法和EBRIP算法功耗攻擊方案相比效率分別提高了69.72%和10.94%，這會(huì)大大滿足芯片等便攜式設(shè)備的高效性需求，說(shuō)明固定基點(diǎn)標(biāo)量乘運(yùn)算中，所給方案具有更好的性能。另外，該方案還可以根據(jù)安全和效率需求進(jìn)行多次標(biāo)量分割。由性能分析結(jié)果表明：該方案可以滿足安全和效率兩方面的需求，尤其適用于對(duì)存儲(chǔ)空間要求不高的密碼加密部件等應(yīng)用系統(tǒng)中。

4 結(jié) 語(yǔ)

通過(guò)結(jié)合基于帶符號(hào)整數(shù)拆分形式多標(biāo)量乘快速算法和標(biāo)量分割隨機(jī)化方法，從而給出了一種新的ECC抗功耗攻擊方案，既能抵御多種功耗攻擊，同時(shí)也有更高的運(yùn)算效率。并且由于該方案所構(gòu)造生成的預(yù)計(jì)算表是固定且已知的，所以可以預(yù)先存儲(chǔ)到應(yīng)用系統(tǒng)中，不需要再重新計(jì)算，這樣就只需要考慮主循環(huán)加密運(yùn)算，能夠更好地應(yīng)用于安全芯片等資源受限的便攜式系統(tǒng)中，具有較好理論研究和實(shí)際應(yīng)用價(jià)值。

[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.California, USA: Springer Verlag, 1999: 388-397.

[3] Coron J S.Resistance against differential power analysis for elliptic curve cryptosystems[J].Crypt- ographic Hardware and Embedded Systems, 1999, 292-302.

[4] 王正義, 趙俊閣.基于帶符號(hào)雙基數(shù)系統(tǒng)的抗功耗攻擊方案算法[J].計(jì)算機(jī)應(yīng)用, 2011, 31(11): 2973-2974.

[5] 陳 俊, 陳 運(yùn).抗功耗分析攻擊的橢圓曲線梳狀優(yōu)化算法[J].成都信息工程學(xué)院學(xué)報(bào), 2010, 25(4): 341-344.

[6] 石潤(rùn)華, 鐘 誠(chéng).一種快速的橢圓曲線標(biāo)量乘方法[J].計(jì)算機(jī)工程與應(yīng)用, 2006(2): 156-158.

[7] 張 寧.能量分析攻擊下安全的橢圓曲線標(biāo)量乘法[D].西安：西安電子科技大學(xué), 2007.

[8] 劉 鐸, 戴一奇.計(jì)算橢圓曲線上多標(biāo)量乘的快速算法[J].計(jì)算機(jī)學(xué)報(bào), 2008, 31(7): 1131-1137.

[9] 賴 暉.橢圓曲線密碼體制中的快速點(diǎn)乘算法[J].微計(jì)算機(jī)信息, 2007, 23(3): 228-229.

[10] 馬 博.基于ECC算法的智能卡抗功耗攻擊研究[D].西安：西安電子科技大學(xué), 2010.

[11] Knudsen E.Elliptic scalar multiplication using point halving [C]//Advances in Cryptology-ASIACRYPT’99.New Youk: Springer-Verlag, 1999, 1716(274): 135-149.

[12] Morain F, Olivos J.Speeding up the computations on an elliptic curve using addition-subtraction chains [J].Theoretical Informatics and Applications, 1990, 24(6): 120-126.

[13] Purohit G N, Rawat S A, Kumar M.Elliptic curve point multiplication using MBNR and point halving [J].International Journal of Advanced Networking and Applications, 2012, 3(5): 1329-1337.

[14] 王玉璽，張串絨，張柄虹．一種改進(jìn)的固定基點(diǎn)標(biāo)量乘快速算法[J]．計(jì)算機(jī)科學(xué)，2013，40(10)：135-138．

[15] Fong K, Hankerson D, Lopez J, et al.Field inversion and point halving revisited[J].IEEE Transactions on Computers, 2004, 53(8): 1047-1059.

[16] Barua R, Pandey S K, Pankaj R.Efficient window-based scalar multiplication on elliptic curves using double- base number system [C]//Lecture Notes in Computer Science.Berlin: Springer-Verlag, 2007: 351-360.

ASecurityandEfficiencySchemeofResistingPowerAttacksforSoC

YANGSua,YANGYinghuib

(a.Practice Teaching Equipment Management Office； b.School of Information and Electronic Engineering, Henan University of Animal Husbandry and Economy, Zhengzhou 450044, 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.Firstly, 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 can be used in the limited resource system preferably.

ellipse curve cryptography; power analysis attack; integer splitting form; multiple scalar multiplication algorithm

TP 309

A

1006-7167(2017)10-0149-04

2017-01-12

楊 蘇(1982-)，男，河南商丘人，學(xué)士，實(shí)驗(yàn)師，主要從事計(jì)算機(jī)網(wǎng)絡(luò)及安全研究。Tel.: 18037277061; E-mail: 59732376@qq.com