基于奇系數(shù)Comb的橢圓曲線密碼抗功耗攻擊方案

梁　芳　沈濟(jì)南,2

1(湖北民族學(xué)院理學(xué)院　湖北 恩施 445000)2(華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　湖北 武漢 430074)

?

基于奇系數(shù)Comb的橢圓曲線密碼抗功耗攻擊方案

梁芳1沈濟(jì)南1,2

1(湖北民族學(xué)院理學(xué)院湖北 恩施 445000)2(華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院湖北 武漢 430074)

針對(duì)資源受限的密碼芯片在抵抗功耗攻擊中存在效率和安全兩個(gè)方面的矛盾。通過將標(biāo)量采用奇系數(shù)梳狀算法進(jìn)行編碼，然后結(jié)合預(yù)計(jì)算表將橢圓曲線標(biāo)量乘法運(yùn)算轉(zhuǎn)化為一組小標(biāo)量乘法運(yùn)算，并利用基點(diǎn)掩碼技術(shù)實(shí)施抗功耗攻擊，提出一種基于奇系數(shù)Comb的橢圓曲線密碼抗功耗攻擊方案。算法性能分析結(jié)果表明：與傳統(tǒng)的抗功耗攻擊方案相比，給出的抗功耗攻擊方案不僅可以抵抗簡(jiǎn)單功耗攻擊、差分功耗攻擊、零值寄存器功耗攻擊和零值點(diǎn)功耗攻擊，并且能夠在存儲(chǔ)空間和主循環(huán)運(yùn)算量基本保持不變的情況下具有更高效的運(yùn)算效率，在各種資源受限的應(yīng)用系統(tǒng)中具有較好的實(shí)際應(yīng)用價(jià)值。

橢圓曲線密碼功耗攻擊奇系數(shù)梳狀算法預(yù)計(jì)算表基點(diǎn)掩碼

0　引　言

密碼芯片由于資源受限，使得其在實(shí)施抗功耗攻擊過程中存在效率和安全的矛盾，尤其是功耗攻擊技術(shù)的出現(xiàn)對(duì)密碼芯片的安全造成了嚴(yán)重威脅。功耗攻擊技術(shù)是1998年由PaulKocher率先提出的一種利用芯片工作時(shí)泄露的功耗信息來獲取密鑰信息的密碼分析方法，這種攻擊方法實(shí)現(xiàn)簡(jiǎn)單，攻擊成功率高，比傳統(tǒng)的數(shù)學(xué)攻擊方法具有更大的威脅[1-4]。根據(jù)攻擊手段不同，可分為簡(jiǎn)單功耗分析SPA(SimplePowerAttack)和差分功耗分析DPA(DifferentialPowerAttack)。由于橢圓曲線密碼算法ECC(EllipticCurveCryptogram)與其他的傳統(tǒng)公鑰密碼算法相比，在相同安全性條件下具有所需要的密鑰更短，存儲(chǔ)空間更小的優(yōu)點(diǎn)，更適合于密碼芯片等資源受限的設(shè)備，所以目前出現(xiàn)了大量針對(duì)橢圓曲線密碼的功耗攻擊，主要有零值寄存器功耗分析ZPA(Zero-valuePowerAnalysis)和零值點(diǎn)功耗分析RPA(RefinedPowerAnalysis)[5-7]。

同時(shí)，國內(nèi)外文獻(xiàn)也出現(xiàn)了針對(duì)橢圓曲線密碼的抗功耗攻擊分析研究。文獻(xiàn)[8]提出了一種基于窗口隨機(jī)化初始點(diǎn)WBRIP(Window-BasedRandomInitialPoint)的橢圓曲線密碼抗功耗攻擊算法，其主要思想是通過將橢圓曲線密碼標(biāo)量的二進(jìn)制編碼進(jìn)行窗口化，從而掩蓋在一個(gè)窗口內(nèi)執(zhí)行點(diǎn)加操作和倍點(diǎn)操作運(yùn)算的次數(shù)，使得攻擊者無法根據(jù)中間結(jié)果猜測(cè)運(yùn)算過程中執(zhí)行的具體操作，該算法雖然能夠抵抗多種功耗攻擊，但在運(yùn)算效率方面需要進(jìn)一步改進(jìn)。文獻(xiàn)[9]對(duì)上述算法進(jìn)行改進(jìn)，給出了一種固定窗口寬度為w的非鄰接形式表示算法FWNAF(FractionalWidth-wNonAdjacentFrom)的橢圓曲線密碼抗功耗攻擊方案，通過優(yōu)化編碼減少添加偽操作次數(shù)，以提高改進(jìn)方案的運(yùn)算效率。文獻(xiàn)[10]提出了一種高效的窗口隨機(jī)化初始點(diǎn)EBRIP(Efficient-BasedRandomInitialPoint)橢圓曲線密碼抗功耗攻擊算法，通過將窗口寬度為w的非鄰接表示形式分成整數(shù)部分和分?jǐn)?shù)部分實(shí)現(xiàn)抗SPA攻擊，然后將基點(diǎn)分成固定部分和可變部分實(shí)現(xiàn)DPA、ZPA和RPA攻擊，并且可以有效提高運(yùn)算效率。奇系數(shù)梳狀算法是橢圓曲線標(biāo)量乘法運(yùn)算的一種快速計(jì)算方法，通過將添加偽操作和基點(diǎn)掩碼技術(shù)應(yīng)用在奇系數(shù)梳狀算法中，給出一種基于奇系數(shù)Comb算法OCM(Odd-onlyCombMethod)的橢圓曲線密碼抗功耗攻擊方案，與WBRIP和EBRIP算法比較，給出的抗功耗攻擊算法具有相同的抗功耗安全性，且有更高的運(yùn)算效率。

1　橢圓曲線標(biāo)量乘快速算法

橢圓曲線密碼的標(biāo)量乘快速算法主要有雙基數(shù)系統(tǒng)編碼算法[11]、階乘展開式編碼算法[12]和整數(shù)拆分表示形式編碼算法[13]等。奇系數(shù)梳狀算法是常用的橢圓曲線標(biāo)量乘快速算法，與其他快速算法相比具有存儲(chǔ)空間小和運(yùn)算效率高的優(yōu)點(diǎn)。下面給出橢圓曲線標(biāo)量乘奇系數(shù)梳狀快速算法的具體描述。

首先，給出橢圓曲線密碼的標(biāo)量乘法運(yùn)算如式(1)所示：

(1)

其中，標(biāo)量k采用二進(jìn)制編碼，n為編碼長(zhǎng)度，ki為編碼系數(shù)。

通過對(duì)橢圓曲線密碼的正奇數(shù)標(biāo)量采用奇系數(shù)梳狀算法進(jìn)行重新編碼，則有橢圓曲線密碼標(biāo)量的奇系數(shù)梳狀形式編碼如式(2)所示：

(2)

(3)

其中，Pi為預(yù)計(jì)算點(diǎn)，通過預(yù)計(jì)算可以構(gòu)造出預(yù)計(jì)算表，且有Pi=(u(s-1)2(s-1)t+…+ui2it+…+u12t+1)·P，且ui∈{0,1}。

將所給已知標(biāo)量進(jìn)行奇數(shù)化，即如果標(biāo)量k是正奇數(shù)，則有l(wèi)=k+1；然而如果標(biāo)量k是正偶數(shù)，則有l(wèi)=k+2。因?yàn)閷?duì)原標(biāo)量k進(jìn)行了奇數(shù)化，所以在返回結(jié)果Q時(shí)需要增加一次后處理：如果標(biāo)量k是奇數(shù)，則需增加操作Q=Q-2P；如果標(biāo)量k是偶數(shù)，則需增加操作Q=Q-P。則如果橢圓曲線密碼標(biāo)量經(jīng)過重新編碼后，奇系數(shù)梳狀標(biāo)量乘法運(yùn)算如算法1所示[14]：

算法1奇系數(shù)梳狀橢圓曲線密碼標(biāo)量乘快速算法

輸入：l，s，P；

輸出：Q=lP。

1. 令m為奇數(shù)化標(biāo)量l的二進(jìn)制比特長(zhǎng)度；

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

4. 計(jì)算奇系數(shù)梳狀編碼系數(shù)li；

5. 令Q=O；

6. 對(duì)于i從t-1到0，重復(fù)執(zhí)行：

6.1Q=2Q；

6.2Q=Q+liP；

7. 返回輸出值：

7.1 如果k是偶數(shù)，則返回Q=Q-P;

7.2 如果k是奇數(shù)，則返回Q=Q-2P。

2　基于OCM的抗功耗攻擊方案

算法1中，由于奇系數(shù)編碼系數(shù)li均不為0，所以在執(zhí)行步驟6的過程中，總是執(zhí)行相同的操作順序，即每執(zhí)行一次倍點(diǎn)操作就需要執(zhí)行一次點(diǎn)加操作，具有相同的能量圖譜，沒有明顯的功耗差異，使得攻擊者無法利用功耗差異信息猜測(cè)密鑰信息，并且在步驟7中都執(zhí)行了一次點(diǎn)加操作運(yùn)算，所以也不會(huì)泄露所給已知標(biāo)量的奇偶性，因此算法1可以有效抵抗SPA攻擊。然而，由于基點(diǎn)P是已知的，使得中間結(jié)果與輸入之間存在相關(guān)性，攻擊者可以利用中間結(jié)果信息猜測(cè)密鑰信息，而且所給已知的基點(diǎn)中同時(shí)也存在有特殊點(diǎn)被攻擊者利用實(shí)施ZPA和RPA攻擊，所以算法1無法抵抗DPA、ZPA和RPA攻擊。

通過結(jié)合掩碼技術(shù)[15]，引入一個(gè)隨機(jī)點(diǎn)，將每一個(gè)小標(biāo)量乘法運(yùn)算的基點(diǎn)進(jìn)行隨機(jī)化，以掩蓋小標(biāo)量和功耗之間的相關(guān)性，從而使得攻擊者無法通過多次猜測(cè)獲取密鑰信息。則有引入隨機(jī)點(diǎn)R后，基于奇系數(shù)Comb編碼標(biāo)量乘法運(yùn)算Q=lP變換為如式(4)所示：

(4)

由于引入了一個(gè)隨機(jī)點(diǎn)，所以在返回結(jié)果Q時(shí)，需要再增加一次后處理進(jìn)行恢復(fù)：如果標(biāo)量k是奇數(shù)，則需增加操作Q=Q-2P-R；如果標(biāo)量k是偶數(shù)，則需增加操作Q=Q-P-R。下面給出基于奇系數(shù)梳狀算法的橢圓曲線密碼抗功耗攻擊方案，如算法2所示：

算法2奇系數(shù)梳狀橢圓曲線密碼抗功耗攻擊算法

輸入：l，P；

輸出：Q=lP。

1. 令m為奇數(shù)化標(biāo)量l的二進(jìn)制比特長(zhǎng)度；

2.R=random()

5. 計(jì)算奇系數(shù)梳狀編碼系數(shù)li；

6. 令Q=R；

7. 對(duì)于i從t-1到0，重復(fù)執(zhí)行：

7.1Q=2Q；

7.2Q=Q+liP；

8. 返回輸出值：

8.1 如果k是偶數(shù)，則返回Q=Q-P-R;

8.2 如果k是奇數(shù)，則返回Q=Q-2P-R。

3　算法性能分析

算法2中，通過引入隨機(jī)點(diǎn)R，將預(yù)計(jì)算表中的Pi進(jìn)行隨機(jī)化，從而可以消除中間結(jié)果與功耗之間的相關(guān)性信息，并且不會(huì)存在可以被攻擊者利用的特殊點(diǎn)，所以給出的算法2可以抵抗DPA、ZPA和RPA攻擊。同時(shí)，由于算法2沒有系數(shù)為0的系數(shù)，因而不存在功耗差異操作，從而具有相同的能量消耗圖譜，本身具有抵抗SPA攻擊的能力。另外，算法2通過執(zhí)行兩次后處理操作：一方面可以掩蓋原標(biāo)量的奇偶性，進(jìn)一步增強(qiáng)算法的安全性；另一方面通過減去引入的隨機(jī)點(diǎn)，可以恢復(fù)出真實(shí)的返回值。

表1　算法2與BR和WBRIP抗功耗攻擊算法的性能比較

從表1可以看出，所給算法2比WBRIP抗功耗攻擊算法所需的存儲(chǔ)空間小。然而，WBRIP抗功耗攻擊算法比所給的算法2多執(zhí)行了(2s-1-2)次點(diǎn)加操作運(yùn)算和(2s-1+s-2)次倍點(diǎn)操作。所以算法2在存儲(chǔ)空間減少的情況下，具有相同的抗功耗攻擊能力，且有更高效的運(yùn)算效率。目前，一般認(rèn)為橢圓曲線密碼512比特的密鑰是安全的，即t=512。令s=4，有t=128。另外，文獻(xiàn)[16]給出在仿射坐標(biāo)系下，倍點(diǎn)運(yùn)算D=24M，點(diǎn)加運(yùn)算A=23M，M表示模乘運(yùn)算。表2給出了算法2與BR抗功耗攻擊算法和WBRIP抗功耗攻擊算法的運(yùn)算效率比較。

表2　算法2與BR和WBRIP抗功耗攻擊算法的運(yùn)算效率比較

從表2可以看出，所給算法2的總運(yùn)算效率比BR抗功耗攻擊算法提高34.98%，比WBRIP抗功耗攻擊算法提高2.36%。其中，算法2比WBRIP抗功耗攻擊算法所需預(yù)計(jì)算大的多，然而由于預(yù)計(jì)算表可以預(yù)先存儲(chǔ)到密碼芯片中，因而需要考慮主要是主循環(huán)運(yùn)算，算法2的主循環(huán)運(yùn)算效率比WBRIP抗功耗攻擊算法的主循環(huán)運(yùn)算效率提高了60.04%，比BR抗功耗攻擊算法的主循環(huán)運(yùn)算效率提高了74.71%，而WBRIP抗功耗攻擊算法的主循環(huán)運(yùn)算效率比BR抗功耗攻擊算法只提高了36.70%。由此可知，所給算法2可以同時(shí)兼顧安全和效率兩個(gè)方面，進(jìn)一步提高密碼芯片的運(yùn)算效率，能夠很好地滿足資源受限的各類應(yīng)用環(huán)境中。

4　結(jié)　語

橢圓曲線密碼算法是密碼安全芯片中的主流加密算法，而奇系數(shù)梳狀算法是橢圓曲線密碼中的一種快速標(biāo)量乘算法。由于功耗攻擊的出現(xiàn)，使得密碼安全芯片的安全性受到比較大的威脅，因而通過結(jié)合奇系數(shù)梳狀快速標(biāo)量乘算法和基點(diǎn)掩碼技術(shù)給出的抗功耗攻擊算法，可以有效抵抗多種功耗攻擊，并且同其他傳統(tǒng)抗功耗攻擊算法相比，所給算法可以進(jìn)一步有效提高運(yùn)算效率，很好地解決了資源受限的密碼芯片效率和安全的矛盾問題。因而所給算法可以很好地應(yīng)用各種資源受限的應(yīng)用系統(tǒng)中，具有很好的理論研究意義和實(shí)際推廣應(yīng)用價(jià)值。

[1] 李浪,李仁發(fā),ShaEHM.安全SoC抗功耗攻擊研究綜述[J].計(jì)算機(jī)科學(xué),2009,36(6):16-18.

[2]KocherP,JaffeJ,JunB.Differentialpoweranalysis[C]//ProceedingsofAdvancesinCRYPTO99,LNCS1666,Springer-Verlag,BerlinHeidelberg,1999:388-397.

[3]WuK,LiH,YuF.Retrievinglostefficiencyofscalarmultiplicationsforresistingagainstside-channelattacks[J].Journalofcomputers,2010,5(12):1878-1884.

[4] 王正義,趙俊閣.ECC抗功率分析攻擊的等功耗編碼算法[J].計(jì)算機(jī)工程,2012,38(10):111-113.

[5]GoronJS.Resistanceagainstdifferentialpoweranalysisforellipticcurvecryptosystems[C]//CryptographicHardwareandEmbeddedSystems(CHES’04),LNCS1717,Springer-Verlag,Berlin,1999:292-302.

[6] 汪鵬君,郝李鵬,張躍軍.防御零值功耗攻擊的AESSubByte模塊設(shè)計(jì)及其VLSI實(shí)現(xiàn)[J].電子學(xué)報(bào),2012,40(11):2183-2187.

[7]GobinL.Arefinedpoweranalysisattackonellipticcurvecryptosystems[C]//PublicKeyCryptography2003,LNCS2567,Springer-Verlag,2003.

[8]MamiyaH,MiyajiA,MorimotoH.EfficientcountermeasuresagainstRPA,DPA,andSPA[C]//CryptographicHardwareandEmbeddedSystems(CHES’04),LNCS3156,Springer-Verlag,2004:343-356.

[9] 張濤.Smartcard上橢圓曲線密碼算法的能量攻擊和防御[J].計(jì)算機(jī)工程,2007,33(14):125-127.

[10]ZhangTao,FanMingyu,ZhengXiaoyu.Secureandefficientellipticcurvecryptographyresistsside-channelattacks[J].JournalofSystemsEngineeringandElectronics,2009,20(3):660-665.

[11]DimitrovVS,JullienGA,MillerWC.Theoryandapplicationsforadouble-basenumbersystem[J].IEEETransactionsonComputers,1999,48(10):1098-1106.

[12] 賴忠喜,張占軍,陶東婭.橢圓曲線中直接計(jì)算7P的方法及其應(yīng)用[J].計(jì)算機(jī)應(yīng)用,2013,33(7):1870-1874.

[13] 石潤(rùn)華,葛麗娜,鐘誠.橢圓曲線密碼體制上一種快速kP算法[J].計(jì)算機(jī)工程與科學(xué),2004,26(4):55-58.

[14] 蔣輝芹.標(biāo)量乘法底層域快速算法研究[J].湖州師范學(xué)院學(xué)報(bào),2013,35(3):36-40.

[15] 李起瑞,胡曉波,趙靜,等.針對(duì)改進(jìn)的Masking方法的差分功耗攻擊[J].北京電子科技學(xué)院學(xué)報(bào),2011,19(4):35-41.

[16] 王玉璽,張串絨,張柄虹,等.基于素?cái)?shù)域上復(fù)合運(yùn)算的快速標(biāo)量乘算法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(11):3385-3387.

RESISTINGPOWERANALYSISATTACKSSCHEMEFORELLIPSECURVECRYPTOGRAPHYBASEDONODD-ONLYCombMETHOD

LiangFang1ShenJi’nan1,2

1(School of Science,Hubei Minzu University,Enshi 445000,Hubei,China)2(School of Computer Science and Technology,Huzhong University of Science and Technology,Wuhan 430074,Hubei,China)

Thecontradictionsbetweenefficiencyandsecurityliesinthecryptographicchipswithlimitedresourcewhenresistingpoweranalysisattacks.Inlightofthis,wecodedthescalarwiththeodd-onlycombalgorithmandthenconvertedtheellipsecurvescalarmultiplicationoperationtoagroupofsmallscalarmultiplicationoperationsincombinationwiththepre-computationtable,andutilisedthemasktechnologytoexertpoweranalysisattacksresistance,throughthesewepresentedanodd-onlyComb-basedresistingpoweranalysisattacksschemeforellipsecurvecryptography.Performanceanalysisresultofthealgorithmshowedthatcomparedwithtraditionalresistingpowerattackscheme,theproposedschemecouldresistthesimplepoweranalysisattack,thedifferentialpoweranalysisattack,thezero-valueregistermasktechnologypowerattackandthezero-valuepointpoweranalysisattack.Besides,italsohadmoreefficientoperationefficiencyinthecircumstanceofkeepingthestoragespaceandmainloopoperationloadbasicallyunchanged,andhadbetterpracticalappliedvalueinavarietyofapplicationsystemswithlimitedresource.

EllipsecurvecryptographyPoweranalysisattackOdd-onlycombalgorithmPre-computationtableBasicpointmask

2014-07-03。國家自然科學(xué)基金面上項(xiàng)目(612720 72)。梁芳，講師，主研領(lǐng)域：云計(jì)算，數(shù)據(jù)安全，訪問控制。沈濟(jì)南，講師。

TP309

ADOI:10.3969/j.issn.1000-386x.2016.03.068