梁　芳　沈濟南,2

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

?

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

梁芳1沈濟南1,2

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

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

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

0　引　言

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

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

1　橢圓曲線標量乘快速算法

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

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

(1)

其中，標量k采用二進制編碼，n為編碼長度，ki為編碼系數(shù)。

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

(2)

(3)

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

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

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

輸入：l，s，P；

輸出：Q=lP。

1. 令m為奇數(shù)化標量l的二進制比特長度；

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

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

5. 令Q=O；

6. 對于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í)行一次倍點操作就需要執(zhí)行一次點加操作，具有相同的能量圖譜，沒有明顯的功耗差異，使得攻擊者無法利用功耗差異信息猜測密鑰信息，并且在步驟7中都執(zhí)行了一次點加操作運算，所以也不會泄露所給已知標量的奇偶性，因此算法1可以有效抵抗SPA攻擊。然而，由于基點P是已知的，使得中間結(jié)果與輸入之間存在相關(guān)性，攻擊者可以利用中間結(jié)果信息猜測密鑰信息，而且所給已知的基點中同時也存在有特殊點被攻擊者利用實施ZPA和RPA攻擊，所以算法1無法抵抗DPA、ZPA和RPA攻擊。

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

(4)

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

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

輸入：l，P；

輸出：Q=lP。

1. 令m為奇數(shù)化標量l的二進制比特長度；

2.R=random()

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

6. 令Q=R；

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

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

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

表2　算法2與BR和WBRIP抗功耗攻擊算法的運算效率比較

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

4　結(jié)　語

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

[1] 李浪,李仁發(fā),ShaEHM.安全SoC抗功耗攻擊研究綜述[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].計算機工程,2012,38(10):111-113.

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

[6] 汪鵬君,郝李鵬,張躍軍.防御零值功耗攻擊的AESSubByte模塊設(shè)計及其VLSI實現(xiàn)[J].電子學(xué)報,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].計算機工程,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] 賴忠喜,張占軍,陶東婭.橢圓曲線中直接計算7P的方法及其應(yīng)用[J].計算機應(yīng)用,2013,33(7):1870-1874.

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

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

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

[16] 王玉璽,張串絨,張柄虹,等.基于素數(shù)域上復(fù)合運算的快速標量乘算法[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é)基金面上項目(612720 72)。梁芳，講師，主研領(lǐng)域：云計算，數(shù)據(jù)安全，訪問控制。沈濟南，講師。

TP309

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