摘 要： 橢圓曲線密碼（ECC）是迄今為止具有最高強(qiáng)度的密碼系統(tǒng)。隨著集成電路、智能卡技術(shù)的發(fā)展以及嵌入式系統(tǒng)大規(guī)模的應(yīng)用，其安全性也受到了邊信道攻擊的威脅。差分錯(cuò)誤攻擊（DFA）是旁路攻擊中的一種新的攻擊方式，攻擊者通過(guò)物理手段影響智能卡，從而在解密過(guò)程中誘導(dǎo)出錯(cuò)誤信息，再結(jié)合差分分析恢復(fù)出私鑰信息。立足于國(guó)內(nèi)外對(duì)公鑰密碼故障分析研究的基礎(chǔ)上，在攻擊方法和防御方法兩方面對(duì)ECC算法的故障分析進(jìn)行了研究概述，并指出了每個(gè)攻擊方法的優(yōu)缺點(diǎn)，預(yù)測(cè)了未來(lái)的研究方向。

關(guān)鍵詞： 橢圓曲線密碼； 差分錯(cuò)誤攻擊； 智能卡； 防御

中圖分類號(hào)： TN915.08?34； TP309.7 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）19?0063?04

Abstract： The elliptic curve cryptogram （ECC） is a cryptosystem with the highest intensity so far. With the development of the integrated circuit and smart card technology， and large?scale applications of the embedded systems， the security of ECC is threatened by side channel attack. The differential fault attack （DFA） is a new attack mode of side channel attack， by which the attacker can influence on the smart card with physical means， so as to induce the error message in decrypting process， and then the private key information is recovered in combination with differential analysis. On the basis of the study and analysis of public key cryptography failure at home and abroad， the fault analysis using ECC algorithm is researched and reviewed in the aspects of attack methods and defense methods. The advantages and disadvantages of each attack method are pointed， and the future development trend is predicted.

Keywords： elliptic curve cryptogram； differential fault attack； smart card； defense

0 引 言

隨著通信、計(jì)算機(jī)網(wǎng)絡(luò)、集成電路等技術(shù)的飛速發(fā)展，信息安全問(wèn)題受到各行各業(yè)的廣泛關(guān)注。1985年，Neal Koblitz和Victor Miller各自提出了橢圓曲線密碼（Elliptic Curve Cryptogram，ECC）[1?2]，其安全性是基于橢圓曲線離散對(duì)數(shù)問(wèn)題，在公鑰密碼學(xué)中獲得更多的關(guān)注與認(rèn)可。與RSA等公鑰密碼算法相比，ECC具有計(jì)算量小、處理速度快、存儲(chǔ)空間占用小、帶寬要求低且安全性更高等優(yōu)點(diǎn)。因此，更適合資源受限的設(shè)備（例如智能卡）。在許多的實(shí)際應(yīng)用中，橢圓曲線密碼的私鑰存儲(chǔ)在智能卡中，因?yàn)榧用芎秃灻倪^(guò)程都是在卡內(nèi)完成的，如果不破壞芯片，很難知道其中隱藏的密鑰信息。

邊信道攻擊（Side Channel Attack，SCA）[3]又稱側(cè)信道攻擊，針對(duì)加密電子設(shè)備在運(yùn)行過(guò)程中的時(shí)間消耗、功率消耗或電磁輻射之類的側(cè)信道信息泄露而對(duì)加密設(shè)備進(jìn)行攻擊的一類方法。這類新型攻擊的有效性遠(yuǎn)高于密碼分析的數(shù)學(xué)方法，因此給密碼設(shè)備帶來(lái)了嚴(yán)重的威脅。1996年Boneh在歐密會(huì)上首次提出了故障攻擊（Fault Attacks）[4]的概念。其主要思想是主動(dòng)向密碼設(shè)備中注入錯(cuò)誤，通過(guò)錯(cuò)誤計(jì)算攻擊公鑰密碼的代數(shù)結(jié)構(gòu)，從而得到設(shè)備的秘密信息。原始的攻擊方法依賴模運(yùn)算的代數(shù)特性，不能處理私鑰算法復(fù)雜的位操作，所以原始的這種攻擊方法只能應(yīng)用于公鑰密碼體制，不能攻擊私鑰密碼，例如DES加密標(biāo)準(zhǔn)。錯(cuò)誤攻擊是對(duì)RSA公鑰密碼體制的新型攻擊方法。相比于能量攻擊，故障攻擊具有良好的抗噪聲性能，因而在安全領(lǐng)域具有廣泛的應(yīng)用前景。

錯(cuò)誤攻擊的類型主要分為以下幾種：

（1） 通過(guò)控制錯(cuò)誤的位置，分為三種：無(wú)控制（No Control），錯(cuò)誤誘導(dǎo)的位置是任意的；輕控制（Loose Control），選擇一種變量作為攻擊目標(biāo)；完全控制（Complete Control），選擇的密鑰位都作為攻擊的目標(biāo)。

（2） 通過(guò)控制時(shí)間，分為三種：無(wú)控制，即引誘發(fā)生錯(cuò)誤的時(shí)間不受控制；輕控制，即錯(cuò)誤被引誘進(jìn)裝置中只需一小部分操作的時(shí)鐘；精確控制，即錯(cuò)誤引誘的時(shí)間是非常精確的。

（3） 錯(cuò)誤影響密鑰位的數(shù)量，分為三類：?jiǎn)我诲e(cuò)誤位（Single Faulty Bit）；部分錯(cuò)誤（Few Faulty Bit）；隨機(jī)數(shù)量的錯(cuò)誤（Random Number Of Faulty Bit）。

（4） 錯(cuò)誤注入后的影響，分為瞬時(shí)錯(cuò)誤和永久錯(cuò)誤。

2 研究進(jìn)展

1997年，Biham和Shamir將這種攻擊方法應(yīng)用于對(duì)稱密碼體制，首次提出了差分錯(cuò)誤攻擊的概念[5]，并成功地攻擊了DES算法。DES是將64 b的輸入數(shù)據(jù)通過(guò)16輪的迭代運(yùn)算，得到長(zhǎng)度同樣是64 b的輸出數(shù)據(jù)。其錯(cuò)誤注入點(diǎn)位于倒數(shù)第二輪的中間狀態(tài)，采用比特位作為單位來(lái)處理數(shù)據(jù)。這樣做只需要較少的密文就可恢復(fù)密鑰，減小了運(yùn)算的復(fù)雜度。此后研究人員提出了各種不同的故障攻擊方法，成功攻擊了多種密碼體制，包括RSA?CRT算法、橢圓曲線算法、流密碼等。

2000年，來(lái)自Bell通信實(shí)驗(yàn)室的三位學(xué)者Biehl等首先提出了對(duì)ECC密碼體制的差分錯(cuò)誤攻擊[6]，該故障分析從位于安全的橢圓曲線上的輸入點(diǎn)中引入故障，使得錯(cuò)誤的點(diǎn)位于一個(gè)較弱的橢圓曲線上，進(jìn)而通過(guò)分析較弱的橢圓曲線獲取安全橢圓曲線密鑰[7]?；谶@種思想人們對(duì)IEEE 802.15制定的加密方案（ECDH，SCIES和ECMQV）和采用蒙哥馬利方法實(shí)現(xiàn)點(diǎn)乘的橢圓曲線密碼進(jìn)行了攻擊。這類方法的主要缺點(diǎn)是攻擊效率較低且比較容易防御。

2005年，Ciet等提出了在確定錯(cuò)誤植入位置的情況下恢復(fù)密鑰的方法[8]。通常，安全的橢圓曲線密碼體制是已知的，并且其密鑰[d∈Z]存儲(chǔ)在抗篡改、不可讀的設(shè)備中，當(dāng)輸入橢圓曲線上的點(diǎn)[P]時(shí)，該設(shè)備計(jì)算并輸出[d?P]。針對(duì)ECC的故障分析根據(jù)故障位于輸入點(diǎn)[P]和系統(tǒng)參數(shù)不同而不同。

（1） 當(dāng)基點(diǎn)[P]發(fā)生故障時(shí)。第一種情況是沒(méi)有檢查輸入點(diǎn)與輸出點(diǎn)是否在安全的橢圓曲線上，可能導(dǎo)致輸入點(diǎn)[P（x，y）?E，]使得[a′6=y2+a1xy+a3y-x3-][a2x2-a4x。]元組[a1，a2，a3，a4，a′6]確定了新的橢圓曲線[E，]該橢圓曲線的階[ord（E）]含有小因子[r，]并且[ord（P）=r。]因此，橢圓曲線的對(duì)數(shù)問(wèn)題可以歸結(jié)到由[P∈E]生成的階為[r]的子群上的離散對(duì)數(shù)問(wèn)題，由點(diǎn)[P，d?E]可以計(jì)算出[d mod r。]通過(guò)選擇不同的點(diǎn)[P]重復(fù)上述過(guò)程，根據(jù)中國(guó)剩余定理（CRT）即可求出密鑰[d。]第二種情況是對(duì)輸入點(diǎn)進(jìn)行檢查，假設(shè)進(jìn)行上述檢測(cè)后點(diǎn)乘運(yùn)算開(kāi)始時(shí)，寄存器中產(chǎn)生了錯(cuò)誤，出錯(cuò)后的點(diǎn)[P]與輸入點(diǎn)[P]只有1 b不同，密碼芯片不再檢測(cè)輸入點(diǎn)是否在[E]上，計(jì)算輸出[d?P，且d?P]依賴于由[P]確定的[E=a1，a2，a3，a4，a′6，]這樣又把[E]上的DL問(wèn)題轉(zhuǎn)換到[E]上的DL問(wèn)題。首先計(jì)算[E]上點(diǎn)的數(shù)目[ord（E），]如果[ord（E）]具有小因子[r，]則可根據(jù)點(diǎn)[ord（E）r?P′E]和[d?ord（E）r?P′E]解決DL問(wèn)題。最后根據(jù)不同的因子[r]和中國(guó)剩余定理重復(fù)上述過(guò)程恢復(fù)密鑰[d。]

針對(duì)ECC故障分析的防御方法主要是通過(guò)設(shè)計(jì)一種硬件檢測(cè)裝置，檢查每一個(gè)輸出點(diǎn)是否在安全的橢圓曲線上；檢查所有用于計(jì)算輸出的中間點(diǎn)以及最終的輸出是否在橢圓曲線上。若上述兩點(diǎn)有一個(gè)不能成立，則阻止輸出任何點(diǎn)。對(duì)于改進(jìn)的新型攻擊方法，硬件防御不能有效地檢測(cè)出故障點(diǎn)。所以在今后的研究過(guò)程中，軟件防御算法將是一個(gè)新的研究熱點(diǎn)。

2006年，Johannes Bl?mer和Martin Otto等人提出符號(hào)變換故障攻擊（Sign Fault Attacks，SFA）[9]，并采用二進(jìn)制非相鄰表示型（Non?Adjacent Form，NAF）[10]方法實(shí)現(xiàn)運(yùn)算的橢圓曲線進(jìn)行了攻擊。攻擊者通過(guò)誘導(dǎo)密碼芯片出錯(cuò)，改變特殊輸出點(diǎn)[Q]的[y]坐標(biāo)符號(hào)，即[Q=-Q=（x，-y）]。與以往的攻擊方法不同，錯(cuò)誤輸出點(diǎn)偏離了安全曲線，轉(zhuǎn)換成在弱的橢圓曲線上計(jì)算離散對(duì)數(shù)問(wèn)題。而符號(hào)變換攻擊的錯(cuò)誤輸出點(diǎn)在橢圓曲線上是有效點(diǎn)，密鑰可在多項(xiàng)式時(shí)間內(nèi)恢復(fù)。一般的輸出點(diǎn)檢測(cè)裝備不能檢測(cè)出錯(cuò)誤的發(fā)生，符號(hào)變換攻擊的故障點(diǎn)不易被防御裝置檢測(cè)出來(lái)，因而具有攻擊有效性。

橢圓曲線一般定義在兩種域中，二進(jìn)制域[GF（2m）]和素?cái)?shù)域[GFp]。當(dāng)符號(hào)攻擊素?cái)?shù)域[（p>3）]時(shí)，基點(diǎn)[P]被攻擊后的坐標(biāo)點(diǎn)為[（x，-y）；]若符號(hào)變換攻擊二進(jìn)制域，基點(diǎn)[P]被攻擊后的坐標(biāo)為[（x，x-y）]。當(dāng)前，符號(hào)變換攻擊假定橢圓曲線[E]被定義在素?cái)?shù)域中，且在相同的輸入條件下重復(fù)增加攻擊次數(shù)以至少[12]的概率恢復(fù)密鑰[d。]目前，標(biāo)量乘運(yùn)算實(shí)現(xiàn)方式主要有二進(jìn)制NAF方法（從左至右或從右至左）、蒙哥馬利二進(jìn)制方法。

Bl?mer提出的二進(jìn)制NAF算法成功地以至少[12]的概率恢復(fù)了密鑰[d。]蒙哥馬利二進(jìn)制算法[11]若其密鑰位是非零的，則運(yùn)算中既有加法也有倍加；若其密鑰位是零，則運(yùn)算中只有倍加。這種算法易受時(shí)間和能量攻擊的影響。所以不能同時(shí)抵抗多種側(cè)信道攻擊。

2008年，Pierre?Alain Fouque和Reynald Lercier提出蒙哥馬利階方法[13]攻擊橢圓曲線。此種方法的優(yōu)點(diǎn)是不使用[y]坐標(biāo)僅需較少的錯(cuò)誤即可恢復(fù)密鑰，此時(shí)它并不關(guān)心特殊點(diǎn)是在原來(lái)的橢圓曲線上還是在轉(zhuǎn)換后的橢圓曲線（Twist of an Elliptic Curve）上，結(jié)果算法對(duì)于點(diǎn)[（x：y：z）∈E]仍然有效，只是[y∈Fp2]代替了簡(jiǎn)單的[y∈Fp。]而且特殊點(diǎn)從強(qiáng)橢圓曲線到弱曲線上時(shí)也不會(huì)被偵查出來(lái)，所以恢復(fù)密鑰的成功率大大提高。同時(shí)，對(duì)于安全抵抗簡(jiǎn)單能量分析蒙哥馬利也是一種有效的方法。

2009年，Alexey 提出了新的錯(cuò)誤攻擊橢圓曲線標(biāo)量乘算法[14]。提出假設(shè)，假定攻擊者可以誘導(dǎo)中間點(diǎn)[Q]的[x]坐標(biāo)值發(fā)生錯(cuò)誤，錯(cuò)誤發(fā)生的時(shí)間可以精確的選擇。其錯(cuò)誤誘導(dǎo)算法過(guò)程如下：

這種改進(jìn)的標(biāo)量乘算法經(jīng)過(guò)計(jì)算分析表明，對(duì)于廣泛的橢圓曲線，它的適用性和有效性都比以前的攻擊方案優(yōu)越，而且可以在可實(shí)行的時(shí)間內(nèi)恢復(fù)密鑰。其不足在于算法有點(diǎn)小復(fù)雜，要求誘導(dǎo)的錯(cuò)誤數(shù)量是線性的且多項(xiàng)式時(shí)間復(fù)雜度被要求不超過(guò)[O1N，]其中[N]是初始域[K]的階。

隨著技術(shù)逐漸趨于成熟，錯(cuò)誤攻擊成功攻擊了私鑰密碼體制、公鑰密碼體制。后來(lái)的研究學(xué)者們基于以上的攻擊方法也做出了許多的改進(jìn)。針對(duì)橢圓曲線算法及符號(hào)變換攻擊的原理，提出了改進(jìn)的符號(hào)變換攻擊方案，即二進(jìn)制方法點(diǎn)乘的橢圓曲線密碼故障攻擊[15]。該算法通過(guò)改變錯(cuò)誤注入位置，減少故障對(duì)私鑰的數(shù)值依賴，有效解決了原算法中出現(xiàn)的“零塊失效”問(wèn)題。又例如控制電路的有限狀態(tài)機(jī)跳變故障模型，2011年朱巍巍提出了橢圓曲線的一種新故障攻擊方法[16?18]，對(duì)帶點(diǎn)檢測(cè)防御能力的二進(jìn)制NAF型橢圓曲線進(jìn)行了理論分析。與符號(hào)攻擊方法相比，該方法產(chǎn)生的故障還在原來(lái)的曲線上，并通過(guò)增加預(yù)計(jì)算，提高了攻擊效率。

3 總結(jié)與展望

錯(cuò)誤攻擊是側(cè)信道攻擊方式的一種，也是近幾年的研究熱點(diǎn)。本文針對(duì)橢圓曲線加密算法概述了差分錯(cuò)誤攻擊的幾種常見(jiàn)技術(shù)。主要包括二進(jìn)制NAF算法、蒙哥馬利算法、符號(hào)變換攻擊。橢圓曲線的加密體制是基于復(fù)雜的離散對(duì)數(shù)問(wèn)題，前兩種方法都是把在強(qiáng)橢圓曲線上解決離散對(duì)數(shù)的問(wèn)題轉(zhuǎn)換成在弱橢圓曲線上的離散對(duì)數(shù)問(wèn)題，這種攻擊方法可以通過(guò)自檢裝置進(jìn)行防御。而符號(hào)攻擊是另一種錯(cuò)誤誘導(dǎo)方法，計(jì)算仍然在原橢圓曲線上，所以其攻擊有效性提高了?？墒峭ǔ５挠布烙胧?duì)其是無(wú)效的，針對(duì)符號(hào)攻擊的防御算法[19?20]有待下一步的改進(jìn)優(yōu)化。

國(guó)內(nèi)外提出的錯(cuò)誤分析防御方法都是針對(duì)特定某一攻擊，無(wú)法同時(shí)防御其他多種邊界信道攻擊。近期，多邊界信道攻擊被廣泛地應(yīng)用到密碼分析領(lǐng)域，取得了單一邊界信道無(wú)法達(dá)到的攻擊效果。期望一種算法，可以在注入較少錯(cuò)誤的前提下，運(yùn)算簡(jiǎn)單、攻擊效率高。因此，研究不同密碼體制如何防御多信道攻擊[21]已經(jīng)成為該領(lǐng)域的研究熱點(diǎn)。對(duì)ECC等公鑰密碼體制的邊界信道攻擊算法研究具有廣泛的研究和發(fā)展前景。

參考文獻(xiàn)

[1] KOBLITZ N. Elliptic curve cryptosystems [J]. Mathematics of computation， 1987， 48（177）： 203?209.

[2] MILLER V S. Use of elliptic curve in cryptography [C]// Proceeding of 1985 Advances in Cryptology?Crypto. Berlin： Sprin?ger?Verlag， 1985： 417?426.

[3] IZU T， TAKAGI T. A fast parallel elliptic curve multiplication resistant against side channel attacks [C]// Proceedings of 2002 5th International Workshop on Practice and Theory in Public Key Cryptosystems. Paris： Springer Berlin Heidelberg， 2002： 280?296.

[4] DAN B， DEMILLO R A， LIPTON R. On the importance of checking cryptographic protocols for fault [C]// Proceedings of 1997 International Conference on the Theory and Application of Cryptographic. Konstanz： Springer?Verlag， 1997： 37? 51.

[5] BIHAM E， SHAMIR A. Differential fault analysis of secret key cryptosystems [C]// Proceedings of 17th Annual International Cryptology Conference. Santa Barbara： Springer?Verlag， 1997： 513?525.

[6] BIEHL I， MEYER B， MüLLER V. Differential fault attacks on elliptic curve cryptosystems [C]// Proceedings of 20th Annual International Cryptology Conference. Santa Barbara： Springer Berlin Heidelberg， 2000： 131?146.

[7] DAN B， DEMILLO R A， LIPTON R J. On the importance of eliminating errors in cryptographic computations [J]. Journal of cryptology， 2001， 14（1）： 101?119.

[8] CIET M， JOYE M. Elliptic curve cryptosystems in the pre?sence of permanent and transient faults [J]. Designs， codes and cryptography， 2005， 36（1）： 33?43.

[9] BL?MER J， OTTO M， SEIFERT J P. Sign change fault attacks on elliptic curve cryptosystems [C]// Proceedings of 2006 Third International Workshop on Fault Diagnosis and Tole?rance in Cryptography. Yokohama： Springer?Verlag， 2006： 36?52.

[10] BECKER A. Methods of fault analysis attacks on elliptic curve cryptosystems [D]. Darmstadt： Darmstadt University of Technology， 2006.

[11] JOYE M. Fault?resistant calculations on elliptic curves： US 8457303 [P]. 2010?07?22.

[12] 祝力.公鑰密碼及其故障分析研究[D].上海：上海交通大學(xué)，2007.

[13] FOUQUE P A， LERCIER R， REAL D， et al. Fault attack on elliptic curve with Montgomery ladder implementation [C]// Proceedings of 2008 Fifth International Workshop on Fault Diagnosis and Tolerance in Cryptography. Washington， D. C.：IEEE， 2008： 92?98.

[14] CHILIKOV A， TARASKIN O. New fault attack on elliptic curve scalar multiplication [EB/OL]. [2009?05?28]. http：//eprint.iacr.org/2009/528.pdf.

[15] 張金中，寇應(yīng)展，陳財(cái)森，等.二進(jìn)制方法點(diǎn)乘的橢圓曲線密碼故障攻擊[J].計(jì)算機(jī)工程，2011（20）：100?102.

[16] ZHU Weiwei， YAN Yingjian， LIU Kai. State machine skip fault attacks on elliptic curve scalar multiplication [J]. Journal of Information Engineering University， 2011（4）： 159?161.

[17] 朱巍巍，嚴(yán)迎建.基于隨機(jī)故障感染運(yùn)算的橢圓曲線點(diǎn)乘算法[J].計(jì)算機(jī)工程，2011（24）：112?113.

[18] 嚴(yán)迎建，李志強(qiáng)，段二朋，等.橢圓曲線點(diǎn)乘的抗故障攻擊FSM控制器設(shè)計(jì)[J].計(jì)算機(jī)應(yīng)用，2012（1）：86?88.

[19] 張偉.智能卡中ECC標(biāo)量乘模板攻擊研究[D].西安：西安電子科技大學(xué)，2013.

[20] 張濤.面向密碼芯片的旁路攻擊關(guān)鍵技術(shù)研究[D].成都：電子科技大學(xué)，2008.

[21] 王家良，錢琦鋒，韋磊，等.ECC算法軟件優(yōu)化的研究綜述[J].智能電網(wǎng)，2012（2）：131?136.