鄔可可，張平安，延霞

（深圳信息職業(yè)技術(shù)學(xué)院 計算機學(xué)院，廣東 深圳 518172）

橢圓曲線密碼芯片安全與效率的博弈

鄔可可，張平安，延霞

（深圳信息職業(yè)技術(shù)學(xué)院 計算機學(xué)院，廣東 深圳 518172）

橢圓曲線密碼被廣泛應(yīng)用于便攜式密碼設(shè)備中，比如金融IC卡和網(wǎng)銀USB Key等。雖然橢圓曲線密碼具有很高的安全級別，但在密碼設(shè)備的實現(xiàn)上則很容易受到側(cè)信道攻擊。國內(nèi)外對ECC的側(cè)信道分析技術(shù)的研究主要集中在發(fā)現(xiàn)新的攻擊方法和新的防御方法上。本文綜述了這些防御措施的安全性與計算效率，并基于橢圓曲線本身具有的豐富的代數(shù)特性，提出對未來研究方向的展望。

橢圓曲線密碼；側(cè)信道攻擊；密碼芯片

在密碼學(xué)界，安全與效率往往是背道而馳，現(xiàn)有的國內(nèi)外研究成果往往是靠犧牲一部分效率來達(dá)到安全的目的。針對計算資源相對豐富的大型計算機系統(tǒng)或互聯(lián)網(wǎng)的安全性，通常不在意因安全性需求而犧牲一部分效率。然而，對于計算資源非常有限的橢圓曲線密碼設(shè)備，研究防御側(cè)信道攻擊（Side Channel Attacks,SCA）的方法同時，又要保持橢圓曲線密碼（Elliptic Curve Cryptosystems,ECC）原本的高效性，是必要且迫切的。本文歸類總結(jié)了近年來國內(nèi)外對ECC的側(cè)信道分析技術(shù)，主要圍繞“攻擊”和“防御”這兩條線索展開，分析了各類防御技術(shù)的計算效率。發(fā)現(xiàn)這些防御方法都是以犧牲計算效率來達(dá)到安全的目的，從而影響了ECC在計算資源非常有限的密碼芯片上的實現(xiàn)。鑒于此，本文最后探討了一條新的防御方法思路，而不增加其計算開銷。

1 橢圓曲線密碼

橢圓曲線密碼（Elliptic Curve Cryptosystems,ECC）是迄今被實踐證明安全有效的三類公鑰密碼體制之一，以高效著稱，由Neal Koblitz[1]和Victor Miller[2]于1985年分別獨立地提出,并在近年開始得到重視。ECC可以提供與RSA密碼體制類似的功能。RSA密碼的安全性是建立在整數(shù)因子分解的困難性之上，而ECC的安全性建立在更加復(fù)雜的橢圓曲線離散對數(shù)問題（ECDLP）的困難性之上。求解整數(shù)因子分解問題有亞指數(shù)時間算法，與此不同,ECDLP最好的算法具有全指數(shù)時間復(fù)雜度。這意味著為達(dá)到期望的安全程度，ECC可以使用較RSA密碼更短的密鑰，160位的ECC可以提供相當(dāng)于1024位RSA密碼的安全程度。由于密鑰短而獲得的優(yōu)點包括加解密速度快、節(jié)省能源、節(jié)省帶寬和節(jié)省存儲空間等。因此，ECC尤其適用于計算資源受限的密碼設(shè)備，特別是帶有安全芯片的金融IC卡、網(wǎng)銀USB Key設(shè)備等。所以，ECC在安全性和計算效率方面相對于其它公鑰密碼系統(tǒng)的優(yōu)勢，已經(jīng)得到越來越廣泛的應(yīng)用，并被許多國家和國際標(biāo)準(zhǔn)組織采納為公鑰密碼算法標(biāo)準(zhǔn)，其安全性問題自然得到人們的廣泛關(guān)注和研究，尤其是基于計算資源受限的加密芯片中ECC密碼算法引擎的計算效率和安全性的研究。

2 側(cè)信道攻擊技術(shù)

傳統(tǒng)的密碼分析理論認(rèn)為，對密碼設(shè)備的分析僅依賴于輸入明文和輸出密文的值。而在實際應(yīng)用中，分析人員可以獲得密碼設(shè)備的算法操作過程中的功耗或電磁輻射信號。對于輸入不同的明文而產(chǎn)生不同的功耗或電磁輻射信號，可以獲取密鑰的信息，這種密碼分析方式稱為側(cè)信道攻擊（Side Channel Attacks,SCA）。SCA是一種新的密碼分析技術(shù)，最早由美國學(xué)者Paul Korcher于1996年提出[3]，它利用密碼設(shè)備工作時所泄露的側(cè)信道（Side Channel）信息（如時間、功耗或電磁信號等[4，5]）來破解密鑰，從而給密碼設(shè)備的安全性提出了新的考驗。SCA方法大致可以分為兩大類：簡單側(cè)信道分析（Simple Side Channel Analysis,SSCA）和差分側(cè)信道分析（Differential Side Channel Analysis,DSCA）。SSCA主要是通過肉眼觀察一條或若干條采集到的側(cè)信道曲線來破解密鑰，需要了解密碼算法流程。如圖1所示，只需采集一條經(jīng)典的點乘方法，即可破解ECC密鑰。DSCA需要集采數(shù)千條或更多的側(cè)信道信號曲線，利用概率統(tǒng)計的方法將需要的某種側(cè)信道信息差異放大，將無關(guān)信息過濾掉，從而找到側(cè)信道信息與密鑰數(shù)據(jù)的相關(guān)性。密碼算法通常都是通過增加密鑰的長度來增加其安全性，而SCA不因密鑰長度越長而越難破解。SCA只與密碼算法本身和集成電路的實現(xiàn)有關(guān)。如果密碼算法及其軟硬件實現(xiàn)未采取保護(hù)措施，則可能只需要很小的代價就可以實現(xiàn)破解密鑰。例如功耗與電磁分析通常只需要數(shù)千美元的成本。

圖1 SSCA攻擊ECC點乘方法Fig.1 fig.1.SSCA attacks ECC point multiplication method

3 SCA攻擊ECC的方法

由于ECC被大量地應(yīng)用于智能卡等密碼設(shè)備中，且ECC密鑰的每個比特位都對應(yīng)著ECC側(cè)信道較長的軌跡部分，產(chǎn)生了密鑰與側(cè)信道信息的高度相關(guān)性，從而使SCA成為ECC最具威脅的攻擊手段，受到了學(xué)術(shù)界和工業(yè)界的高度關(guān)注。國內(nèi)外的解決方案通常是以犧牲ECC的計算效率來達(dá)到防御側(cè)信道攻擊的目的，從而影響了ECC在金融IC卡等計算資源非常有限的密碼設(shè)備上的實現(xiàn)。1999年，Coron首次提出采用SSCA破解經(jīng)典的ECC點乘Double-and-add方法[6]，并給出對應(yīng)的防御方法（Double-and-add-always）。而另一種更強的DSCA則采用統(tǒng)計的方法來執(zhí)行程序多次來破解密鑰。Messerges等人最先將該方法應(yīng)用于公鑰密碼系統(tǒng)，指出大數(shù)指數(shù)運算的傳統(tǒng)算法是不能抵抗DSCA的[7]。1999年，Coron首次將DSCA應(yīng)用在ECC上[6]，其思想和Messerges等人相類似，但針對ECC采用了其他的一些統(tǒng)計測試。Goubin于2003年提出了針對橢圓曲線的精細(xì)功耗攻擊（Refined Power Attack,RPA）[8]，RPA利用一個零值取到一個特殊的橢圓曲線點來破解密鑰，RPA能攻破Coron的防御措施。RPA后來進(jìn)一步被擴展到更強的零值點攻擊（Zero-value Point Attack,ZPA）[9]。Dupuy和Kunz-Jacques于2005年提出選擇密文的側(cè)信道攻擊NIST橢圓曲線的點乘，包括選擇密文的簡單側(cè)信道攻擊和差分側(cè)信道攻擊[10]。Gebotys等人也于2005年首次提出電磁攻擊（EMA）基于JAVA實現(xiàn)的ECC密碼設(shè)備，分別采用了簡單電磁攻擊（SEMA）和差分電磁攻擊（DEMA）[11]。Fan等人于2011年提出了合成攻擊（combined attacks），把簡單側(cè)信道攻擊（SSCA）和引入錯誤攻擊（Fault attack）結(jié)合起來攻擊做了簡單和差分防御的ECC點乘[12]。

4 防御方法及計算效率

國內(nèi)外對防御SCA攻擊的ECC安全方法研究，通常做法是對ECC點乘dP運算的側(cè)信道曲線的不平衡性，采用添加“砝碼”（冗余）的方法來平衡ECC的核心操作點乘的3個級別操作（點乘算法級別、群運算級別和域運算級別），由此帶來了額外的計算開銷。通常的防御措施有兩個過程：第一步是使得SSCA攻擊不可行，第二步是使得DSCA攻擊不可行。

4.1 防御SSCA攻擊

對于Weierstrass形式的橢圓曲線，兩種最基礎(chǔ)的群運算（點加、點倍）是完全不同的，而且二者的計算復(fù)雜度相差也較大，通常在1.3～2.5倍之間。這給SSCA以用武之地，通常密碼分析者只需采集1條側(cè)信道信號曲線，即可破解ECC密鑰。于是，十余年來，密碼研究人員對防御SSCA的ECC安全方法進(jìn)行了大量研究。這些方法通常歸為如下3類：

點乘操作的統(tǒng)一化：Coron提出的ECC點乘dP運算的規(guī)則化，基于阿貝爾群運算，Joye提出了一種高規(guī)則的點乘運算的循環(huán)迭代，即冗余算法double-and-add-always方法[6,13]。在點乘運算中的每一步都進(jìn)行點加和點倍運算，而無論是否需要。即通過插入額外的點加操作使得無論在比特“1”還是比特“0”的情況下，點乘dP都是由“點加-點倍”重復(fù)循環(huán)迭代完成。適用性廣是該算法的突出優(yōu)點，而缺點在于它引入了過多的不必要的計算，增加了大約33%計算開銷。Wu等人提出的標(biāo)量折半模型[14]是先通過折半密鑰d來減少四分之一的點加操作次數(shù)，再通過增加點加操作來統(tǒng)一化點乘dP運算來防御SSCA攻擊，但最終也增加了12.5%的計算開銷。除了能防御SSCA，該標(biāo)量折半模型最大的優(yōu)點是容易并行化。因此，Wu等人對該標(biāo)量折半模型做了并行化處理[15]，以適應(yīng)多核的安全芯片。

點加點倍公式的同一化：Brier和Joye提出的Weierstrass形式曲線上點加和點倍的同一化公式[16]。清華大學(xué)的劉鐸和戴一奇等人研究了該公式在各種坐標(biāo)系統(tǒng)下的表現(xiàn)形式，并給出了Montgomery形式曲線上的同一化點運算公式[17]。Smart和Joye等人提出了使用非Weierstrass形式曲線的Hessian形式橢圓曲線來使用同一個過程（并不是同一個公式）來計算點加和點倍[18,19]，且Ghosh等人于2013年給出了這種算法的實現(xiàn)[20]。Liardet等人提出將一條橢圓曲線表現(xiàn)成兩個二次型的交，其上的點加和點倍可以通過同一個公式進(jìn)行計算[21]。同一化公式或同一個過程來計算點加和點倍，都需要增加額外的冗余橢圓曲線域操作，都增加了大約20～30%的計算開銷。

側(cè)信道原子塊：通過插入額外的域操作來劃分程序為循環(huán)執(zhí)行的語句原子塊，使得程序呈現(xiàn)相同的側(cè)信道曲線循環(huán)模式[22,23]。同樣，因增加冗余的橢圓曲線域操作，也增加了大約20～30%的計算開銷。

圖2清楚地闡明了上述各類防御SSCA的ECC點乘方法比經(jīng)典的ECC點乘方法（二進(jìn)制方法）要高出大約15～30%的計算開銷。

圖2 SSCA安全方法與二進(jìn)制方法的計算開銷比較fig.2 The computational cost comparation between SSCA secure methods and binary method

4.2 防御DSCA攻擊

即使一個ECC點乘dP法能防御SSCA，它也可能不再防御更強的DSCA的攻擊。目前防御DSCA的方法主要包括2種隨機化技術(shù)，這些方法也都增加了大約15～30%的計算開銷。

密鑰的隨機化：當(dāng)d作為固定的密鑰時，如果每次都用同樣的過程計算，則攻擊者可以不斷選取不同的點，甚至是一些特殊的點或是“偽點”P，通過對計算點乘dP的時間和能耗進(jìn)行的大量的統(tǒng)計，可以恢復(fù)d的一些比特甚至于全部比特。1999年，Coron提出了基于密鑰的隨機化技術(shù)[6]，選取一個隨機數(shù)r與橢圓曲線上點E的階#E相乘，來隱藏標(biāo)量d，達(dá)到防御DSCA攻擊ECC目的；另外還有一些作品[24,25,26]，是以隨機參數(shù)來劃分密鑰比特串來防御DSCA；這些方法都是采用增加冗余的點乘運算。

點的隨機化：如果在計算過程中出現(xiàn)了可以被竊聽者得到的特殊信息（比如除法分子為0產(chǎn)生的意外）將使系統(tǒng)的安全性大幅降低甚至于喪失，因而要讓計算過程中的每個對象盡可能隨機。有一類做法是對于橢圓曲線點進(jìn)行隨機化處理。1999年，Coron[6]提出了采用增加一個秘密隨機點來隱藏點乘運算，或者利用一個隨機非零值來隨機化處理輸入點的投影坐標(biāo)表達(dá)式，來達(dá)到防御DSCA目的。類似地，Okeya和Takagi提出了使用Jacobi坐標(biāo)的點隨機化方法[27]。Okeya和Sakura提出基于Montgomery曲線和算法的ECC實現(xiàn)方案[28]，在該方案中首先對Montgomery曲線上的點進(jìn)行了隨機化處理。Joye和Tymen于2001年提出了曲線同構(gòu)和域同構(gòu)的隨機化技術(shù)來防御DSCA[29]，但為了求同構(gòu)的逆運算而增加了近1倍的點乘運算。Taverne等人于2011年提出了基于NIST曲線ECC的隨機化處理來防御DSCA[30]。Lee等人于2012年提出了通過隨機化Montgomery操作來防御相關(guān)性功耗分析攻擊雙域ECC的處理器[31]。Mulder等人又于2013年提出了雖然這些方法在目前的DSCA攻擊技術(shù)條件下，從理論上有很好的防御效果，但這些方法的安全性都來自對點乘dP計算效率的犧牲。

5 總結(jié)展望

綜上所述，現(xiàn)有的防御簡單側(cè)信道攻擊（SSCA）和差分側(cè)信道攻擊（DSCA）的安全方法都是在ECC點乘的基礎(chǔ)上增加額外操作來達(dá)到側(cè)信道安全的目的。這大大增加了計算開銷，從而影響ECC在資源有限的密碼設(shè)備上的計算效率。盡管在十余年的時間內(nèi)，對ECC密碼設(shè)備的側(cè)信道攻擊與防御技術(shù)這一嶄新課題的研究已有了一定的研究成果，但在研究安全方法的同時保持ECC高效率的研究，卻仍然不夠。

相對于RSA簡單的數(shù)學(xué)結(jié)構(gòu)，橢圓曲線是虧格（genus）為1的代數(shù)曲線，從理論上講有無窮多種橢圓曲線的具體表示，具有豐富的代數(shù)特性，因此可以基于橢圓曲線群和域上的代數(shù)結(jié)構(gòu)理論（如同種、有理映射），建立ECC等價變換模型，來防御SSCA和DSCA而不增加ECC的計算開銷，將會是未來的新熱點方向。

（References）

[1]N.Koblitz,Elliptic curve cryptosystems,Mathematics of Computation,1987,48(177),pp.203-209.

[2]V.S.Miller.Use of elliptic curves in cryptography,Advances in Cryptology-CRYPTO 1985,LNCS 218,Springer-Verlag,pp.417-426.

[3]P.C.Kocher,Timing attacks on implementations of Diffie-Hellman,RSA,DSS,and other systems,International Cryptology Conference on Advances in Cryptology,1996,Santa Barbara,USA.

[4]P.C.Kocher,J.Jaffe,B.Jun,Differential power analysis,Advances in Cryptology-CRYPTO'99,LNCS 1666,Springer-Verlag,1999,pp.388-397.

[5]J.J.Quisquater,D.Samyde,Simple Electromagnetic analysis for Smart Cards:New Results,Rump session talk at Cyrpto 2000.

[6]J.S.Coron,Resistance against differential power analysis for elliptic curve cryptosystems,Cryptographic hardware and embedded systems-CHES 1999,LNCS 1717,pp.292-302.

[7]T.S.Messerges,E.A.Dabbish,and R.H.Sloan,Power analysis attacks of modular exponentiation in smartcards,Cryptographic Hardware and Embedded Systems-CHES 1999,LNCS1717,pp.144-157.

[8]L.Goubin,A refined power analysis on elliptic curve cryptosystems,Public Key Cryptography-PKC 2003,LNCS 2567,pp.199-211.

[9]T.Akishita,T.Takagi, Zero-value Point Attacks on Elliptic Curve Cryptosystem,ICS2003,Lecture Notes in Computer Science,Springer-Verlag,2003,pp.218-233.

[10]W.Dupuy,S.Kunz-Jacques,Resistance of Randomized Projective Coordinates Against Power Analysis,Cryptographic Hardware and Embedded Systems-CHES 2005,LNCS 3659,pp.1-14.

[11]C.H.Gebotys,S.Ho,and C.C.Tiu,EM Analysis of Rijndael and ECC on a Wireless Java-Based PDA,Cryptographic Hardware and Embedded Systems-CHES 2005,LNCS 3659,pp.250-264.

[12]J.Fan,B.Gierlichs,and F.Vercauteren,To Infinity and Beyond:Combined Attack on ECC Using Points of Low Order,Cryptographic Hardware and Embedded Systems -CHES 2011,LNCS 6917,pp.143-159.

[13]Marc Joye,Highly Regular Right-to-Left Algorithms for Scalar Multiplication,Cryptographic Hardware and Embedded Systems-CHES 2007,LNCS 4727,pp.135-147.

[14]K.Wu,H.Li,D.Zhu,F.Yu,“Efficient solution to secure ECC against side-channel attacks”,Chinese Journal of Electronics,Volume 20,Issue 3,2011,pp.471-475.

[15]K.Wu,H.Li,D.Zhu,“Fast and scalable parallel processing of scalar multiplication in elliptic curve cryptosystems”,Security and Communication Networks,Volume.5,Issue 6,June 2012,pp.648-657.

[16]E.Brier,M.Joye.Weierstrass elliptic curves and sidechannel attacks,Public Key Cryptography 2002,Heidelberg,Germany:Springer Berlin,2002,pp.335-345.

[17]劉鐸,戴一奇,Brier-Joye點加公式的幾點討論,2003中國計算機大會論文集,北京,清華大學(xué)出版社,2003,pp.221-226.D.Liu，Y.Dai,Remarks on Brier-Joye addition formula,Proceedings of Chinese National Conference of Computer 2003,Beijing,Tsinghua University Press,2003,pp.22l～226.(in Chinese)

[18]N.P.Smart,The Hessian for of an elliptic curve,Cryptographic Hardware and Embedded Systems-CHES 2001,LNCS 2162,pp.118-125.

[19]M.Joye,J.J.Quisquater,Hessian elliptic curves and sidechannel attacks,Cryptographic Hardware and Embedded Systems-CHES 2001,LNCS 2162,pp.402-410.

[20]Santosh Ghosh,Amit Kumar,Amitabh Das,and Ingrid Verbauwhede,On the Implementation of Unified Arithmetic on Binary Huff Curves,Cryptographic Hardware and Embedded Systems-CHES 2013,LNCS 8086,pp.349-364.

[21]P.Y.Liardet,N.P.Smart,Preventing SPA/DPA in ECC systems using the Jacobi form,Cryptographic Hardware and Embedded Systems-CHES 2001,LNCS 2162,pp.391-401.

[22]B.Chevallier-Mames,M.Ciet and M.Joye,Low-cost solutions for preventing simple side-channel analysis:side-channel atomicity,IEEE Trans.Computers,2004,53(6),pp.760-768.

[23]P.K.Mishra,Pipelined computation of scalar multiplication in elliptic curve cryptosystems,IEEE Transactions on Computers,2006,55(8),pp.1000-1010.

[24]S.Chari,C.S.Jutla,J.R.Rao and P.Rohatgi,Towards sound approaches to counteract power-analysis attacks,CRYPTO 1999,LNCS 1666,pp.398-412.

[25]C.Clavier,M.Joye,Universal exponentiation algorithm:A first step towards provable SPA-resistance,Cryptographic Hardware and Embedded Systems-CHES 2001,LNCS 2162,pp.300-308.

[26]E.Trichina,A.Bellezza,Implementation of elliptic curve cryptography with built-in countermeasures against side channel attacks,Cryptographic Hardware and Embedded Systems-CHES 2002,LNCS2523,pp.98-113.

[27]K.Okeya,T.Takagi,The width-w NAF method provides small memory and fast elliptic scalar multiplications secure against side channel attacks,CT-RSA 2003,New York:Springer-Verlag,2003,pp.328-343.

[28]K.Okeya,K.Sakura,Power analysis breaks elliptic curve cryptosystems even secure against the timing attack,INDOCRYPT2000,New York:Springer-Verlag,2001,pp.178-l90.

[29]M.Joye,J.J. Quisquater,Protections against differential analysis for elliptic curve cryptography,Cryptographic Hardware and Embedded Systems-CHES 2001,LNCS 2162,pp.377-390.

[30]J.Taverne,A.Faz-Hernandez,D.F.Aranha,F.Rodriguez-Henriquez,D.Hankerson,and J.Lopez,Software Implementation of Binary Elliptic Curves:Impact of the Carry-Less Multiplier on Scalar Multiplication,Cryptographic Hardware and Embedded Systems-CHES 2011,LNCS 6917,pp.108-123.

[31]J.W.Lee,S.C.Chung,H.C.Chang,and C.Y.Lee,An Efficient Countermeasure against Correlation Power-Analysis Attacks with Randomized Montgomery Operations for DF-ECC Processor,Cryptographic Hardware and Embedded Systems-CHES 2012,LNCS 7428,pp.548-564.

The trade-off between security and efficiency in chips of Elliptic curve cryptosystems

WU Keke,ZHANG Pingan,YAN Xia
（Shenzhen Institute of Information Technology,School of Computers,Shenzhen 518172,P.R.China）

Elliptic curve cryptosystems (ECC) have been widely used in the portable cryptographic equipment,such as financial IC cards and USB Keys.Although the security level for the ECC is high,but in the implementation of cryptographic devices are vulnerable to side channel attacks (SCA).On the ECC side channel analysis technology research focuses on finding new methods of attacks and defenses.This paper analyzes and summarizes the security and the computation efficiency of these defensive measures,the rich algebraic properties based on elliptic curve itself has,put forward the prospects for future research directions.

elliptic curve cryptosystems;side channel attacks;cryptographic chips.

TN918.1

：A

1672-6332（2014）03-0018-06

【責(zé)任編輯：高潮】

2014-08-30

鄔可可（1980-），男（漢），江西九江人，高級工程師，博士。主要研究方向：信息安全與密碼算法設(shè)計。E-mail:wukk@sziit.com.cn