熊莉英，王 玉，李 強，李慧云

(1.西南科技大學信息工程學院，四川綿陽621010;2.中國科學院深圳先進技術研究院集成技術研究所深圳電動汽車動力平臺與安全技術重點實驗室，深圳518055)

0 引言

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

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

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

然而，由于模運算同余的特性，文獻[4，7]的作者承認上述適用于RSA模運算的選擇明文攻擊方法不能推廣至ECC類型的密碼算法，因為ECC中沒有模運算同余操作.本文提出一種針對ECC的選擇明文攻擊方法:利用在域運算中，無窮遠點和接近原點在點倍點加的標量乘法中的特殊性，可以區(qū)分點倍與點加.

1 ECC概述

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

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

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

式中:a，b∈ K.

橢圓曲線上所有點加上一個特殊的無窮遠點O，可以用下面給出的加法運算構成一個阿貝爾群結構.

當 charK≠ 2，3時的加法操作為:令點P=(x1，y1)≠O，－P=(x1，－y1).令點 Q=(x2，y2)≠O 且 Q≠－P，則和 P+Q=(x3，y3)可計算如下

其中

減去點P=(x，y)，可以用加上點 －P運算來代替.如果P≠Q，則運算 P+Q稱為點加運算;如果P=Q則該運算稱為點倍運算.圖1說明了使用二進制算法自右向左(right-to-left)進行標量乘操作的過程.

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

2 ECC二進制算法的選擇明文與簡單功耗攻擊

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

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

對輸入 Py→0進行點倍運算:Q=2Py→0，會致使該點接近無窮遠點，如圖2所示.也就是說點的坐標值(xQ，yQ)變得極大，這將導致功耗的顯著增大.本文中把這樣的無窮遠點Q記為Q∞.

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

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

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

其中

下面對A、D1、D2操作進行進一步分析:

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

因此，x3－D1和 y3－D1為顯著大值，且 x3－D1遠大于 y3－D1.

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

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

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

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

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

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

3 結論

本文提出了針對橢圓曲線算法的一種新型的基于選擇明文的簡單功耗分析攻擊方法.所選擇的特殊輸入點P接近橫軸或縱軸，是為了利用無窮遠點或接近坐標軸的點的標量乘的特性:對坐標值小的點進行點加和點倍操作，會得到很大的坐標值變化.本攻擊方法適用于所有的ECC標準二進制算法實現(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].計算機應用研究，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]姚劍波，張濤.抗側信道攻擊的橢圓曲線密碼算法[J].計算機應用與軟件，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)