橢圓曲線密碼的選擇明文側(cè)信道攻擊方法

熊莉英，王 玉，李 強(qiáng)，李慧云

(1.西南科技大學(xué)信息工程學(xué)院，四川綿陽(yáng)621010;2.中國(guó)科學(xué)院深圳先進(jìn)技術(shù)研究院集成技術(shù)研究所深圳電動(dòng)汽車動(dòng)力平臺(tái)與安全技術(shù)重點(diǎn)實(shí)驗(yàn)室，深圳518055)

0 引言

隨著公鑰密碼系統(tǒng)的迅速發(fā)展，許多基于數(shù)學(xué)困難問(wèn)題的密碼算法得以發(fā)明.公鑰密碼體制根據(jù)其所依據(jù)的難題一般分為三類:大整數(shù)分解問(wèn)題類、離散對(duì)數(shù)問(wèn)題類、橢圓曲線類.橢圓曲線上所有的點(diǎn)外加一個(gè)叫做無(wú)窮遠(yuǎn)點(diǎn)的特殊點(diǎn)構(gòu)成的集合連同一個(gè)定義的加法運(yùn)算構(gòu)成一個(gè)Abel群.在等式mP=P+P+…+P=Q中，已知m和點(diǎn)P求點(diǎn)Q比較容易，反之已知點(diǎn) Q和點(diǎn) P求m卻是相當(dāng)困難的，這個(gè)問(wèn)題稱為橢圓曲線上點(diǎn)群的離散對(duì)數(shù)問(wèn)題.橢圓曲線密碼體制正是利用這個(gè)困難問(wèn)題設(shè)計(jì)而來(lái).1985年，Miller[1]和Koblitz[2]分別提出將橢圓曲線應(yīng)用到密碼學(xué)上，稱為橢圓曲線密碼算法(Elliptic curve cryptosystems，ECC).與其他的公鑰密碼算法如RSA相比，ECC需要較短的密鑰長(zhǎng)度即可達(dá)到相同的安全級(jí)別.RSA要求密鑰長(zhǎng)度至少為1024位，使其大數(shù)因數(shù)分解計(jì)算十分困難.相對(duì)而言，ECC只要求160位的密鑰即可達(dá)到相同的安全級(jí)別.當(dāng)RSA的密鑰使用2048位時(shí)，與ECC的密鑰使用234位獲得的安全級(jí)別相當(dāng)，而密鑰長(zhǎng)度卻相差9倍，當(dāng)密鑰長(zhǎng)度增加時(shí)，相同安全級(jí)別的RSA與ECC密鑰長(zhǎng)度之間的差距更大.ECC具有密鑰短的顯著優(yōu)點(diǎn)，因此引起業(yè)界日益增長(zhǎng)的研究和應(yīng)用興趣.

即使一些密碼算法在理論上是計(jì)算性安全(Computationally secure)的，但通過(guò)側(cè)信道(例如，時(shí)序、功耗、電磁輻射)可能泄漏密鑰相關(guān)信息，因此密碼算法可以通過(guò)側(cè)信道分析進(jìn)行攻擊.在公鑰密碼算法范圍內(nèi)，簡(jiǎn)單功耗分析(SPA)[3]攻擊是一種被普遍采用的技術(shù):根據(jù)對(duì)密碼設(shè)備在運(yùn)算時(shí)的功耗進(jìn)行分析獲取密鑰信息.當(dāng)運(yùn)行公鑰算法的設(shè)備進(jìn)行不同密鑰位操作時(shí)，其即時(shí)功耗也會(huì)發(fā)生相應(yīng)的變化.已有實(shí)驗(yàn)證明，標(biāo)準(zhǔn)RSA二進(jìn)制實(shí)現(xiàn)中的模方操作和模乘操作可以通過(guò)SPA分析被區(qū)分開(kāi)，模方操作對(duì)應(yīng)密鑰位0，相鄰的模乘操作與平方操作對(duì)應(yīng)密鑰位1，這樣使得攻擊者可以獲得密鑰.ECC標(biāo)準(zhǔn)二進(jìn)制算法中的點(diǎn)加和點(diǎn)倍操作類似RSA中的模方和模乘操作.同理，如果可以區(qū)分ECC實(shí)現(xiàn)中的點(diǎn)加和點(diǎn)倍操作，那么攻擊者就可以獲取ECC密鑰.

為了克服這一缺點(diǎn)，目前大多數(shù)的RSA算法通過(guò)插入啞操作的方式:遵循相同指令順序來(lái)執(zhí)行模乘和模方操作，即在模方操作中也加入啞模乘(Dummy multiply).這種方法被認(rèn)為是有效的簡(jiǎn)單功耗攻擊(SPA)防御方法.許多ECC算法也遵循了這一思想，按照相同的指令順序執(zhí)行點(diǎn)加和點(diǎn)倍操作.因此，很難區(qū)分隨機(jī)輸入的點(diǎn)加和點(diǎn)倍差異.為了從功耗波形中獲得更強(qiáng)的信息泄露，文獻(xiàn)[4-7]提出了RSA的特殊選擇明文攻擊方法.Yen提出[7]利用輸入“－1”作為明文來(lái)攻擊上述使用啞乘運(yùn)算的RSA算法.除了－1，同理可以使用輸入值為X和 －X作為選擇明文，該方法的基本概念是使用了－1這一特殊的輸入數(shù)據(jù)，使得模乘和模方操作的差異得以強(qiáng)化，從而使得標(biāo)準(zhǔn)二進(jìn)制RSA實(shí)現(xiàn)的所有密鑰位都可以被清晰地獲得.

然而，由于模運(yùn)算同余的特性，文獻(xiàn)[4，7]的作者承認(rèn)上述適用于RSA模運(yùn)算的選擇明文攻擊方法不能推廣至ECC類型的密碼算法，因?yàn)镋CC中沒(méi)有模運(yùn)算同余操作.本文提出一種針對(duì)ECC的選擇明文攻擊方法:利用在域運(yùn)算中，無(wú)窮遠(yuǎn)點(diǎn)和接近原點(diǎn)在點(diǎn)倍點(diǎn)加的標(biāo)量乘法中的特殊性，可以區(qū)分點(diǎn)倍與點(diǎn)加.

1 ECC概述

橢圓曲線是一組滿足K域上的二元三次齊次方程解的點(diǎn)(x，y)的集合，方程如下

式中:ai∈K，該方程定義了一個(gè)K域上的橢圓曲線.方程(1)稱為Weierstrass方程.

如果域 K的特征不等于2或3，方程(1)可以變換為

式中:a，b∈ K.

橢圓曲線上所有點(diǎn)加上一個(gè)特殊的無(wú)窮遠(yuǎn)點(diǎn)O，可以用下面給出的加法運(yùn)算構(gòu)成一個(gè)阿貝爾群結(jié)構(gòu).

當(dāng) charK≠ 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ì)算如下

其中

減去點(diǎn)P=(x，y)，可以用加上點(diǎn) －P運(yùn)算來(lái)代替.如果P≠Q(mào)，則運(yùn)算 P+Q稱為點(diǎn)加運(yùn)算;如果P=Q則該運(yùn)算稱為點(diǎn)倍運(yùn)算.圖1說(shuō)明了使用二進(jìn)制算法自右向左(right-to-left)進(jìn)行標(biāo)量乘操作的過(guò)程.

圖1 標(biāo)量乘——二進(jìn)制算法(right-to-left)Fig.1 Binary algorithm of scalar multiplication(right-to-left)

2 ECC二進(jìn)制算法的選擇明文與簡(jiǎn)單功耗攻擊

為了防御簡(jiǎn)單功耗攻擊，目前大多數(shù)標(biāo)量乘都采用相同的指令序列來(lái)實(shí)現(xiàn)點(diǎn)加和點(diǎn)倍，比如引入啞操作，使得無(wú)論密鑰位是1還是0，總是執(zhí)行點(diǎn)加與點(diǎn)倍操作(Double-and-add-always)，或者采取更為復(fù)雜的原子化平衡操作[8]、蒙哥馬利方法等.這樣一來(lái)，使得在SPA攻擊時(shí)得不到點(diǎn)加和點(diǎn)倍運(yùn)算的顯著功耗變化[9-12].為了在功耗波形中獲得增強(qiáng)的信息泄露，本文提出選擇特殊輸入，其基本概念是利用一個(gè)輸入點(diǎn)接近坐標(biāo)軸，也就是說(shuō)該特殊選取的點(diǎn)(xp，yp)作為輸入，xp或yp值很小.例如，利用點(diǎn)P接近橫軸(本文中記為Py→0)，或者接近縱軸(本文中記為 Px→0)來(lái)強(qiáng)化點(diǎn)加和點(diǎn)倍操作的差異.本文主要以接近橫軸的點(diǎn)為例進(jìn)行討論，其他具有相同特性的點(diǎn)，同樣適用于選擇明文的SPA攻擊.

圖2 ECC中靠近橫軸的特殊選擇點(diǎn)P的點(diǎn)加和點(diǎn)倍Fig.2 Point addition and point doubling in ECC with specially chosen input P close to X-axis

對(duì)輸入 Py→0進(jìn)行點(diǎn)倍運(yùn)算:Q=2Py→0，會(huì)致使該點(diǎn)接近無(wú)窮遠(yuǎn)點(diǎn)，如圖2所示.也就是說(shuō)點(diǎn)的坐標(biāo)值(xQ，yQ)變得極大，這將導(dǎo)致功耗的顯著增大.本文中把這樣的無(wú)窮遠(yuǎn)點(diǎn)Q記為Q∞.

由圖1所示的二進(jìn)制算法(right-to-left)可知，點(diǎn)加和點(diǎn)倍操作可以歸納為三種類型:(A)點(diǎn)加，(D1)點(diǎn)加后的點(diǎn)倍，(D2)點(diǎn)倍后的點(diǎn)倍.(D2)操作僅當(dāng)正處理的密鑰位為“0”時(shí)才發(fā)生.

假設(shè)P(x1，y1)為特殊選擇明文，即y1趨于0，Q(x2，y2)為普通明文.

P+Q=(x3，y3)可計(jì)算如下

其中

下面對(duì)A、D1、D2操作進(jìn)行進(jìn)一步分析:

因此，x3－A和 y3－A不為顯著小或顯著大值.

因此，x3－D1和 y3－D1為顯著大值，且 x3－D1遠(yuǎn)大于 y3－D1.

由于 λD2，x1－D1和 y1－D1都是較大值或顯著大值.在芯片計(jì)算過(guò)程中，大數(shù)值運(yùn)算需要頻繁進(jìn)行存儲(chǔ)器讀寫，相對(duì)小數(shù)操作，功耗較大.因此，計(jì)算 x3－D2和 y3－D2比計(jì)算 x3－D1和 y3－D1的功耗更大.

另外 x3－D2為較大值，而 y3－D2不為顯著大值，符合ECC代數(shù)幾何圖示中，特殊點(diǎn)的點(diǎn)倍后點(diǎn)倍的結(jié)果不為特殊點(diǎn)的直觀認(rèn)識(shí).

由上述分析有，D2相比D1或A會(huì)消耗更大的功率.因此，即使原子化防御措施對(duì)標(biāo)量乘實(shí)現(xiàn)中的點(diǎn)加和點(diǎn)倍操作進(jìn)行了功率平衡，特殊選擇的輸入點(diǎn)Py→0仍然會(huì)使得D2明顯地與D1或A區(qū)分開(kāi)來(lái).圖3以側(cè)信道軌跡模式示意D1、D2和A操作之間的差異.

圖3 特殊選擇輸入時(shí)的D1、D2和A操作比較Fig.3 Comparison between doubling(D1，D2)and addition(A)side-channel

因?yàn)镈2僅在正處理的密鑰位為“0”時(shí)出現(xiàn)，所以通過(guò)SPA就可以確定密鑰位的順序.以密鑰位(部分)順序“10100”為例，也即該密鑰位形式如下:k=1zzz…00101|2，z表示1或0.表1是對(duì)密鑰(部分)進(jìn)行的二進(jìn)制right-to-left算法.

表1 部分密鑰位為“00101”從右到左的標(biāo)量乘操作Tab.1 The scalar multiplication operation of the key with“00101”(right-to-left)

3 結(jié)論

本文提出了針對(duì)橢圓曲線算法的一種新型的基于選擇明文的簡(jiǎn)單功耗分析攻擊方法.所選擇的特殊輸入點(diǎn)P接近橫軸或縱軸，是為了利用無(wú)窮遠(yuǎn)點(diǎn)或接近坐標(biāo)軸的點(diǎn)的標(biāo)量乘的特性:對(duì)坐標(biāo)值小的點(diǎn)進(jìn)行點(diǎn)加和點(diǎn)倍操作，會(huì)得到很大的坐標(biāo)值變化.本攻擊方法適用于所有的ECC標(biāo)準(zhǔn)二進(jìn)制算法實(shí)現(xiàn)，即自右向左與自左向右算法.

[1]Miller V S.Use og elliptic curves in cryptography[C].Advances in Cryptology-CRYPTO’85 Proceedings.Berlin:Springer，1986:417-426.

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

[3]Kocher P C.Timing attacks on implementations of Diffie-Hellman，RSA，DSS，and other systems[C].Proceedings of 16th International Advances in Cryptology Conference-CRYPTO’96.Berlin:Springer，1996:104-113.

[4]Miyamoto A，Homma N，Aoki T，et al.Enhanced power analysis attack using chosen message against RSA hardware implementations[C].IEEE International Symposium on Circuits and Systems(ISCAS).USA:IEEE，2008:3282-3285.

[5]Novak R.SPA-based adaptive chosen-ciphertext attack on RSA implementation[J]. ComputerScience，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[J].Computer Science，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].Computer Science，2005(3715):183-195.

[8]Chen T，Li H，Wu K，et al.Countermeasure of ECC against side-channel attacks:balanced point addition and point doubling operation procedure[C].Asia-Pacific Conference on Information Processing，2009:465-469.

[9]Coron J S.Resistance against differential power analysis for elliptic curve cryptosystems[J].Computer Science，1999(1717):292-302.

[10]Li H，Wu K，Xu G，et al.Simple power analysis attacks using chosen message against ECC hardware implementations[C].World Congress on Internet Security(WorldCIS-2011).London:IEEE，2011:68-72.

[11]李浪，楊柳，李肯立，等.一種橢圓曲線密碼算法ECC旁路攻擊方法研究[J].計(jì)算機(jī)應(yīng)用研究，2013，30(3):889-890.Li Lang，Yang Liu，Li Kenli，et al.Research on sidechannel attack methods of ECC[J].Application Research of Computers，2013，30(3):889-890.(in Chinese)

[12]姚劍波，張濤.抗側(cè)信道攻擊的橢圓曲線密碼算法[J].計(jì)算機(jī)應(yīng)用與軟件，2013，30(5):203-205.Yao Jianbo，Zhang Tao.ECC algorithm for preventing side-channel attck[J].Computer Application and Software，2013，30(5):203-205.(in Chinese)