對ECC的小整數(shù)n階點(diǎn)進(jìn)行選擇明文攻擊*

熊莉英 ，李慧云 ，李家會(huì)

(1.西南科技大學(xué) 信息工程學(xué)院，四川 綿陽621010；2.中國科學(xué)院深圳先進(jìn)技術(shù)研究院集成技術(shù)研究所，廣東 深圳518055)

與對稱密鑰密碼體系相比，公鑰密碼體系允許更靈活的密鑰管理。目前，應(yīng)用最廣泛的兩種公鑰密碼算法是RSA以及橢圓曲線密碼(ECC)算法[1-2]。與RSA相比，ECC具有更短的密鑰長度、更快的運(yùn)算(諸如內(nèi)存、能量消耗以及帶寬存儲(chǔ))，從而在學(xué)術(shù)與工程領(lǐng)域引起持續(xù)增長的興趣。

側(cè)信道分析(如時(shí)序、功耗、電磁輻射)攻擊已經(jīng)對公鑰密碼體制的硬件實(shí)現(xiàn)產(chǎn)生了威脅。簡單功耗分析SPA(Simple Power Analysis)攻擊已被證明可有效攻擊一些公鑰密碼算法[3]。該技術(shù)主要涉及對運(yùn)行公鑰加密算法的設(shè)備功耗進(jìn)行檢查分析。RSA實(shí)現(xiàn)中的模方和模乘運(yùn)算是可以被區(qū)分開的，使得對方可以獲得密鑰。ECC中點(diǎn)加和倍點(diǎn)操作類似于RSA中的模方和模乘操作。如果可以區(qū)分ECC實(shí)現(xiàn)中的點(diǎn)加和倍點(diǎn)操作，那么攻擊者就可以獲取ECC密鑰。

目前大多數(shù)的RSA算法都使用相同的序列進(jìn)行模乘和模方操作，大多數(shù)ECC算法也使用相同的序列進(jìn)行點(diǎn)加和倍點(diǎn)運(yùn)算，這增大了對差異的區(qū)分難度。RSA中“一貫的模乘和模方操作”以及ECC中“一貫的點(diǎn)加和倍點(diǎn)操作”似乎成為了對抗SPA攻擊的有效手段。為了從功耗波形中獲得更強(qiáng)的信息泄露，針對特殊輸入數(shù)據(jù)的RSA的選擇明文攻擊方法得以提出[4-7]，以及采取更為復(fù)雜的原子化平衡操作[9]和蒙哥馬利方法[10]等，但都使得在SPA攻擊時(shí)得不到點(diǎn)加和倍點(diǎn)運(yùn)算的顯著功耗變化。

為了在功耗波形中獲得增強(qiáng)的信息泄露，本文提出了一種針對ECC算法的選擇明文側(cè)信道攻擊方法，該方法利用了2階或者其他小整數(shù)階點(diǎn)作為特殊輸入點(diǎn)P，以增強(qiáng)點(diǎn)和倍點(diǎn)操作中的顯著變化。

1 ECC概述

1.1 橢圓曲線

ECC算法把現(xiàn)有的離散對數(shù)問題轉(zhuǎn)化為橢圓曲線上的連續(xù)問題。一個(gè)生成元為g的n階循環(huán)群G的離散對數(shù)問題指的是找出群G上使y=gx成立的x。橢圓曲線上的離散對數(shù)比其他有限域上的群(諸如乘法群)要困難得多。令E(EP)為一個(gè)定義在有限域FP上的橢圓曲線，令P為一個(gè)E(EP)上的點(diǎn)。素?cái)?shù)p、橢圓曲線方程FP、點(diǎn)P以及其階數(shù)n是公共的域參數(shù)。私鑰是一個(gè)從區(qū)間[1，n-1]上均勻隨機(jī)選取的整數(shù)d，其相應(yīng)的公鑰是Q=dP。私鑰d的確定問題就是橢圓曲線上的離散對數(shù)問題(ECDLP)。

橢圓曲線就是由滿足定義在F上的Weierstrass方程：

其中ai∈F，這些解的點(diǎn)組成一個(gè)平面曲線。如果F的特征值(char)F≠2，3，Weierstrass方程可變成y2=x3+ax+b，a，b∈F。橢圓曲線上的所有點(diǎn)加上一個(gè)特殊的無窮遠(yuǎn)點(diǎn)O，可以由下面給出的加法運(yùn)算構(gòu)成一個(gè)阿貝爾群結(jié)構(gòu)，當(dāng)F≠2，3 時(shí)的加法方程式：令點(diǎn)P=(x1，y1)≠O，-P=(x1，-y1)。令點(diǎn)Q=(x2，y2)≠O且Q≠-P， 則和P+Q=(x3，y3)可 計(jì)算如 下：

其中，

如果P≠Q(mào)，則運(yùn)算P+Q稱為點(diǎn)加運(yùn)算(A)；如果P=Q則該運(yùn)算稱為倍點(diǎn)運(yùn)算(D)，顯然，二者在方程中是不同的。圖1說明了ECC的點(diǎn)和倍點(diǎn)運(yùn)算。

圖1 ECC中的點(diǎn)和倍點(diǎn)運(yùn)算

1.2 ECC算法ECIES-1簡介

依據(jù) IEEE P1363a/D9和 ANSI X9．63-2001，公鑰加解密算法ECIES-1描述如下：橢圓曲線E的基點(diǎn)為G，階為n，解密者 B的公鑰為點(diǎn)PB=[d]G，私鑰為d，M為1 bit的待加密信息。KDF為密鑰派生函數(shù)，MAC為消息認(rèn)證碼算法，p1、p2為加密者與解密者預(yù)先共有的填充碼，M為明文。

(1)加密算法

為了對明文M進(jìn)行加密，作為加密者的用戶A進(jìn)行以下操作：

①隨機(jī)產(chǎn)生u∈[1，n-1]，計(jì)算V=(x，y)=[u]PB。

②計(jì)算R=[u]G。

③計(jì)算K=KDF(V，p1)=K1||K2。其中K1的長度為 1 bit，K2的長度為k2 bit。

④計(jì)算C=M?K。

⑤計(jì)算T=MACK2(C||p2)。

⑥發(fā)送(R，C，T)給用戶 B。

(2)解密算法

為了對密文C進(jìn)行解密，作為解密者的用戶B執(zhí)行以下操作：

①計(jì)算V=(x，y)=[d]R。

②計(jì)算K=KDF(V，p1)=K1||K2。其中K1的長度為 1 bit，K2的長度為k2 bit。

③計(jì)算T′=MACK2(C||p2)，若T′≠T則報(bào)錯(cuò)退出，否則繼續(xù)。

④計(jì)算M=C?K，M即為恢復(fù)出的信息。

1.3 橢圓曲線階的理論分布情況

點(diǎn)P的階數(shù)指的是滿足[n]P=0的最小正整數(shù)n，具有如下性質(zhì)：

定理 1(Hasse定理)：設(shè)E(Fq)是定義在域Fq上的橢圓曲線，E(Fq)上點(diǎn)的個(gè)數(shù)用 #E(Fq)表示，則：

2 攻擊ECC的選擇消息SPA二進(jìn)制算法

由于目前絕大多數(shù)的標(biāo)量乘法都采用相同的指令序列來進(jìn)行點(diǎn)和倍點(diǎn)運(yùn)算，因此在SPA攻擊中，點(diǎn)和倍點(diǎn)的區(qū)別不是很明顯。為了從功率波中獲得更強(qiáng)的信息泄露，而提出采用特殊輸入數(shù)據(jù)的選擇消息ECC攻擊法。這個(gè)方法的基本概念是采用特殊的輸入數(shù)據(jù)，例如階數(shù)為2、3或更小的點(diǎn)P。點(diǎn)P的階數(shù)指的是滿足[n]P=0的最小正整數(shù)n。為了找到階數(shù)為2的點(diǎn)，令 2P=0，即P=-P。如果P=(x，y)，則-P=(x，-y)。當(dāng)P=-P，則有y=0。因此選擇接近x軸的點(diǎn)(本文中記為Px)來增強(qiáng)點(diǎn)和倍點(diǎn)操作的差別。如點(diǎn)Q=2Px的倍點(diǎn)運(yùn)算會(huì)產(chǎn)生一個(gè)接近無窮大的點(diǎn)，也即坐標(biāo)值(xQ，yQ)非常大，這樣就會(huì)產(chǎn)生顯著的功耗。本文把這種接進(jìn)無窮大的點(diǎn)Q記為Q∞。

根據(jù)從右至左的二進(jìn)制算法，點(diǎn)加和倍點(diǎn)操作可以歸納為 3種類型：點(diǎn)加（A），點(diǎn)加后倍點(diǎn)（D1）和倍點(diǎn)后的倍點(diǎn)（D2）。由方程式“P+Q”可知，D2操作比 D1或者A操作產(chǎn)生更大的功耗。由此可見，即使原子化防御措施對標(biāo)量乘實(shí)現(xiàn)中的點(diǎn)加和倍點(diǎn)操作進(jìn)行了功率平衡，如圖2所示，所選擇的特殊輸入點(diǎn)P仍然會(huì)使得操作D2與D1和A相比能顯著也區(qū)分開來。以2階輸入點(diǎn)P為例，由于 2P=O，則有：

因?yàn)镈2僅在正處理的密鑰位為“0”時(shí)出現(xiàn)，所以通過SPA就可以確定密鑰位的順序。

該方法通過選擇特殊的階數(shù)為2的輸入點(diǎn)P，放大了點(diǎn)倍與點(diǎn)加操作的功耗差。通過該方法，可以對ECC實(shí)現(xiàn)中的從左至右或從右至左二進(jìn)制算法進(jìn)行有效攻擊。

圖2 特殊選擇的接近X軸的輸入點(diǎn)P的點(diǎn)和倍點(diǎn)運(yùn)算

如果輸入點(diǎn)P的階數(shù)為3，則具有連續(xù)兩位1的密鑰操作，如下例所示。但Q=3P=O時(shí)，功耗波形與其他操作有顯著差異，能夠被識(shí)別出。

或者，具有…1001…的密鑰位形式，也能夠被識(shí)別出。同理，還有如下所示的其他組合。只要出現(xiàn)nP=O，結(jié)合前后的功耗波形，就能判斷出相鄰2或更多位的邏輯值。

3 攻擊步驟

為了應(yīng)用上述的選擇消息攻擊方法，攻擊者應(yīng)按照下面的步驟進(jìn)行操作：

(1)確認(rèn)該橢圓曲線上存在階數(shù)為小整數(shù)的點(diǎn)；

(2)證明有階數(shù)為小整數(shù)的點(diǎn)存在；

(3)找到該拐點(diǎn)；

(4)進(jìn)行選擇明文攻擊。

為了找到階數(shù)為 2的點(diǎn)，令 2P=O(即 P=-P)。如果P=（x，y），則-P=（x，-y）。 當(dāng) P=-P 時(shí)，有 y=0，即該點(diǎn) P就是階數(shù)為2的點(diǎn)，存在于x軸上。

要在橢圓曲線y2=x3+ax+b上找到階數(shù)為3的點(diǎn)，令3P=O，則 2P=-P：

由倍點(diǎn)公式可得：

如果 2 P1=-P1，則有：

或者：

則有：

因此，該階數(shù)為3的點(diǎn)在x軸上的值為：

尋找其他階數(shù)點(diǎn)的方法可以進(jìn)一步閱讀參考文獻(xiàn)[10-12]。

本文提出了一種新的選擇明文的簡單功耗分析攻擊法。在該方法中，選擇階數(shù)為2或者其他小整數(shù)階點(diǎn)作為特殊點(diǎn)P，是為了利用其在無限域上的特殊性。該方法放大了點(diǎn)倍與點(diǎn)加操作的功耗差。通過該方法，可以對ECC實(shí)現(xiàn)中的從左至右或從右至左二進(jìn)制算法進(jìn)行有效攻擊。

[1]MILLER V S.Use of elliptic curves in cryptography[C].Advances in Cryptology，CRYPTO’85 Proceedings，1986，218：417-426.

[2]KOBLITZ N.Elliptic curve cryptosystems[J].Mathematics of Computation，1987，48(177)：203-209.

[3]KOCHER P，JAFFE J，JUN B.Timing attacks on implementations of Diffie-Hellman，RSA，DSS，and other systems[C].Proceedings of 16th International Advances in Cryptology Conference，CRYPTO’96，1996，1109：104-113.

[4]MIYAMOTO A，HOMMA N，AOKI T，et al.Enhanced power analysis attack using chosen message against RSA hardware implementations[C].IEEE Intrnational Symposium on Circuits and Systems，ISCAS 2008，2008：3282-3285.

[5]NOVAK R.SPA-based adaptive chosen-ciphertext attack on RSA implementation[C].International Workshop on Practice and Theory in Public Key Cryptography，LNCS，2002，2274：252-262.

[6]BOER B D，LEMKE K，WICKE G.A DPA attack against the modular reduction within a CRT implementation of RSA[C].International Workshop on Cryptographic Hardware and Embedded Systems，CHES 2002，LNCS，2003，2523：228-243.

[7]YEN S M，LIEN W C，MOON S J，et al.Power analysis by exploiting chosen message and internal collisions-vulnerability of checking mechanism for RSA-decryption[J].Proceedings of Progress in Cryptology，Mycrypt 2005，2005，3715：183-195.

[8]Chen Tingding，Li Huiyun，Wu Keke，et al.Countermeasure of ECC against side-channel attacks：balanced point addition and point doubling operation procedure[C].Asia-Pacific Conference on Information Processing,APCIP 2009，2009，2：465-469.

[9]KIHARA S.On the rank of elliptic curves with a rational point of order 4[J].Proceedings of the Japan Academy，Series A，Mathematical Sciences，2004，80(4)：21-34.

[10]KIHARA S.On the rank of elliptic curves with three rational points of order 2.Ⅲ[J].Proceedings of the Japan Academy，Series A，Mathematical Sciences，2004，80(3)：13-20.

[11]KIHARA S.On the rank of elliptic curves with a rational point of order 4.Ⅱ[J].Proceedings of the Japan Academy，Series A，Mathematical Sciences，2004，80(8)：151-168.

[12]Li Huiyun，Wu Keke，Xu Guoqing，et al.Simple power analysis attacks using chosen message against ECC hardware implementations[C].World Congress on Internet Security，2011：68-72.