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

梁　芳　沈濟南,2

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

?

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

梁芳1沈濟南1,2

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

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

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

0　引　言

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

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

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

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

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

(1)

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

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

(2)

(3)

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

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

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

輸入：l，s，P；

輸出：Q=lP。

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

2. 構造預計算表Pi；

4. 計算奇系數梳狀編碼系數li；

5. 令Q=O；

6. 對于i從t-1到0，重復執行：

6.1Q=2Q；

6.2Q=Q+liP；

7. 返回輸出值：

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

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

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

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

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

(4)

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

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

輸入：l，P；

輸出：Q=lP。

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

2.R=random()

5. 計算奇系數梳狀編碼系數li；

6. 令Q=R；

7. 對于i從t-1到0，重復執行：

7.1Q=2Q；

7.2Q=Q+liP；

8. 返回輸出值：

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

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

3　算法性能分析

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

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

從表1可以看出，所給算法2比WBRIP抗功耗攻擊算法所需的存儲空間小。然而，WBRIP抗功耗攻擊算法比所給的算法2多執行了(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抗功耗攻擊算法所需預計算大的多，然而由于預計算表可以預先存儲到密碼芯片中，因而需要考慮主要是主循環運算，算法2的主循環運算效率比WBRIP抗功耗攻擊算法的主循環運算效率提高了60.04%，比BR抗功耗攻擊算法的主循環運算效率提高了74.71%，而WBRIP抗功耗攻擊算法的主循環運算效率比BR抗功耗攻擊算法只提高了36.70%。由此可知，所給算法2可以同時兼顧安全和效率兩個方面，進一步提高密碼芯片的運算效率，能夠很好地滿足資源受限的各類應用環境中。

4　結　語

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

[1] 李浪,李仁發,ShaEHM.安全SoC抗功耗攻擊研究綜述[J].計算機科學,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模塊設計及其VLSI實現[J].電子學報,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的方法及其應用[J].計算機應用,2013,33(7):1870-1874.

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

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

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

[16] 王玉璽,張串絨,張柄虹,等.基于素數域上復合運算的快速標量乘算法[J].計算機應用研究,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。國家自然科學基金面上項目(612720 72)。梁芳，講師，主研領域：云計算，數據安全，訪問控制。沈濟南，講師。

TP309

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