橢圓曲線密碼中抗功耗分析攻擊的標量乘改進方案＊

張友橋，周武能，申 曄，劉玉軍

（1.東華大學信息科學與技術學院，上海 201620；2.上海華虹集成電路有限責任公司，上海 201203)

橢圓曲線密碼中抗功耗分析攻擊的標量乘改進方案＊

張友橋1，周武能1，申 曄2，劉玉軍2

（1.東華大學信息科學與技術學院，上海 201620；2.上海華虹集成電路有限責任公司，上海 201203)

橢圓曲線標量乘法運算是橢圓曲線密碼（ECC)體制中最主要的計算過程，標量乘法的效率和安全性一直是研究的熱點。針對橢圓曲線標量乘運算計算量大且易受功耗分析攻擊的問題，提出了一種抗功耗分析攻擊的快速滑動窗口算法，在雅可比和仿射混合坐標系下采用有符號滑動窗口算法實現橢圓曲線標量乘計算，并采用隨機化密鑰方法抵抗功耗分析攻擊。與二進制展開法、密鑰分解法相比的結果表明，新設計的有符號滑動窗口標量乘算法計算效率、抗攻擊性能有明顯提高。

橢圓曲線密碼；標量乘；功耗分析攻擊；滑動窗口算法；混合坐標系

1 引言

橢圓曲線密碼ECC（Elliptic Curve Cryptography)體系由于其安全性高、密鑰短、計算量小的優勢逐漸成為首選的公鑰加密方案，在智能卡、POS機等資源受限而安全性要求較高的領域里已經得到廣泛應用。橢圓曲線標量乘算法是ECC中最主要且最耗時的運算過程。已有大量學者對橢圓曲線標量乘快速算法做了研究，常用的有二進制展開法、滑動窗口法、NAF（Non Adjacent Form)［1］算法等。文獻［2，3］則研究了選擇不同坐標組合下的最優標量乘算法。

ECC標量乘法的計算是基于密鑰k的點加（ADD)和點倍（DBL)組成的。近年來一種新型的攻擊理論——功耗分析攻擊［4］的提出給智能卡等設備中的ECC算法帶來了巨大的威脅。攻擊者無需知道ECC硬件系統實際電路結構，僅僅通過統計和分析密鑰運算執行時的功耗與密鑰的相關性就能破解密鑰。因此，研究快速安全的標量乘算法成為橢圓曲線密碼應用中的一個重要問題。

本文的研究目標是提高橢圓曲線標量乘運算的效率且確保其抗功耗分析攻擊性能。基于橢圓曲線的點加及倍點計算在不同坐標系下運算速度不同，提出了一種在混合坐標系下采用有符號滑動窗口算法計算標量乘法的快速算法，結合隨機密鑰掩碼的方法能有效抵抗功耗分析攻擊。與常用算法對比表明，在安全性提升的情況下，計算效率有明顯提高。

2 橢圓曲線密碼

1985年，Koblitz N等人將橢圓曲線應用到密碼學中，在公鑰密碼體制研究中取得了重大突破，這就是橢圓曲線上的密碼體制ECC。基于ECC設計了橢圓曲線數字簽名算法ECDSA（Elliptic Curve Digital Signature Algorithm)、橢圓曲線密鑰 協 商 機 制 ECDH（Elliptic Curve Diffie-Hellman)及橢圓曲線綜合加密方案ECIES（Elliptic Curve Integrated Encryption Scheme)。ECC以其強大的“短密鑰”優勢正逐步走向公鑰密碼的主舞臺。

2.1 橢圓曲線密碼原理

一條橢圓曲線是在射影平面上滿足維爾斯特拉斯（Weierstrass)方程：

的所有點的集合，曲線上的每個點都是非奇異的，將X＝x＊Z、Y＝y＊Z代入齊次方程（1)得到：

也就是說，滿足方程（2)的光滑曲線加上一個無窮遠點O，組成了橢圓曲線。

橢圓曲線上所有的點和無窮遠點構成的集合，連同一個定義的加法運算（點加)構成一個Abel群。此群中的任何元素P1、P2滿足：P1＋P2＝P2＋P1。在等式kP＝P＋P＋…＋P＝Q中（P、Q為橢圓曲線上的兩點，k為整數，“＋”為定義的點加，共有k個P相加)，已知k和點P求點Q比較容易，反之已知點Q和點P求k卻是相當困難的。這個問題稱為橢圓曲線上點群的離散對數問題 ECDLP（Elliptic Curve Discrete Logarithm Problem)［5］。ECDLP是比整數因子分解問題IFP（Integar Factorization Problem)和離散對數問題DLP（Discrete Logarithm Problem)難得多的數學難題。橢圓曲線密碼體制正是利用這個難題設計而來的。

2.2 橢圓曲線標量乘法

標量乘法的計算是由一系列取決于密鑰k的比特序列的點加和點倍運算來完成的，它們也被稱為橢圓曲線操作。在橢圓曲線公鑰密碼體制中，加密、解密及簽名、驗證過程都需要用到標量乘法。標量有多種不同的表示方法，分別采用不同的運算方式。在智能卡等嵌入式設備中一般使用二進制表示標量。下面給出最常用的二進制展開法實現過程：

算法1二進制展開法

2.3 滑動窗口法

滑動窗口編碼是指用一個寬度為w（一般w≥2，后續滑動窗口法均默認窗口寬度為w)的窗口對標量k重新編碼。根據編碼方式的不同可將滑動窗口算法分為無符號滑動窗口算法（記為USW2，k)和 有 符 號 滑 動 窗 口 算 法 （記 為SSW2，k)［6］。如果采用USW2，k對標量進行編碼則k將被重新編碼成由集合｛0，1，3，…，2w－1｝中的元素組成的數字串。如整數k＝1234567810＝BC614E16＝1011110001100001010011102，取w ＝3，則k重新編碼（從左至右)后的結果為：

如果采用SSW2，k對標量進行編碼，則對k的二進制序列以（w＋1)位為窗口長度進行分組，當窗口中的最高位為l時，表示窗口的值為負數，此時窗口的值用其對應的補碼表示并產生一個進位。此時k的二進制序列編碼（從右至左)是由集合｛－2w＋1，…，－3，－1，0，1，3，…，2w－1｝中的元素組成的數字串。編碼過程中若最高位剛好有進位，即最后出現j的值大于l－1時，相應添加kj＝0。具體編碼示例如：

算法2有符號滑動窗口法

3 功耗分析攻擊及其防御方案

功耗攻擊主要是利用密碼芯片運算過程泄露的能量信息，結合密碼算法的特點并運用統計分析方法來推測加密系統的關鍵信息。標量乘是ECC的最主要運算過程且易于遭受功耗分析攻擊。功耗分析基本上分為兩大類［7］：一類是簡單功耗分析，包括一般的簡單功耗分析SPA（Simple Power Analysis)以及倍點攻擊DA（Doubling Attack)；一類是結合了統計學分析方法的差分功耗分析DPA（Differential Power Analysis)，DPA 又進一步延伸到高階功耗分析 HO-DPA（High-Order DPA)、修正功耗分析RPA（Refined Power Analysis)以及零值點攻擊ZPA（Zero-value Power Analysis)。

3.1 功耗分析攻擊

簡單功耗分析是根據測量加密系統的功率消耗軌跡，判斷加密設備在某一時刻執行的運算過程以及此運算所對應的操作數，從而恢復出密鑰信息。實施SPA需兩個基本條件：（1)知道加密設備所使用密碼算法的詳細信息；（2)能精確采集到加密設備密鑰運算的能量泄漏信息。一般有五種方法抵抗SPA：加入“虛”點加；使用已經歸一化的標量乘法；使得標量乘法具有相同的運算模式而不依賴于標量；使用“統一”過的點加和倍點運算公式；使用所謂元子法［8］等。

差分功耗分析利用密鑰參與計算來分析功耗差異和密鑰的相關性，攻擊者針對密鑰運算獲取大量功耗曲線來做統計分析。實施DPA的前提條件是加密設備密鑰計算過程功率消耗與密鑰值有相關性。抵抗DPA的方法主要是隨機化，包括隨機化密鑰、基點和曲線等方法。

修正功耗分析是一種改進的DPA方法，攻擊者選擇一些特殊的有一個“0”坐標的點，使得橢圓曲線的隨機映射和點的投影坐標隨機化以及同態隨機化無法對“0”坐標起作用。這樣攻擊者就能夠使用DPA方法來分析密鑰信息。抵抗RPA的主要方法是隨機盲化基點和標量的隨機分割。

零值點攻擊是另一種形式的RPA方法，ZPA利用一類所謂“0”值點的特殊性質，用DPA方法分析得出密鑰信息。與RPA類似，不能處理ECC坐標中“0”值的隨機化方法面對ZPA時不安全，抵抗ZPA的主要方法是隨機盲化基點和隨機分割標量。

3.2 抗功耗攻擊的二進制展開法

對算法1分析可知：運算是否執行橢圓曲線點加、倍點與密鑰位的值密切相關，無法抵抗SPA。算法2對密鑰進行了重新編碼，有一定的抗SPA效果，但無法抵抗DPA。需對算法進行改進以在保證計算效率的同時提高算法的安全性。

對算法1的改進如算法3所示，采取基點掩碼的方式增強算法的抗功耗分析攻擊能力。

算法3抗功耗攻擊的二進制展開法［9］

算法3首先選取了橢圓曲線上的一個隨機點，每步計算過程隨機點R都會參與運算。因每次運算過程產生的R會不同，因而不能靠統計功耗曲線分析密鑰信息，可以抗DPA攻擊。算法3的步驟3計算過程是倍點－點加的循環，與密鑰位的值無關，故可以抗SPA攻擊。因隨機點參與計算因而不可能固定出0值，因此算法也抗RPA、ZPA攻擊。

3.3 改進的滑動窗口法

目前已有許多研究者提出了對滑動窗口法進行改進的方案，文獻［2］中提出了一種基于混合坐標系快速運算（2R＋S)［10］的方法來直接計算（2wR＋S)的快速標量乘法。在滑動窗口算法中，運用此算法可以大大減少橢圓曲線的標量乘的計算量。本文設計了一種基于密鑰掩碼直接計算（2wR＋S)的抗功耗攻擊的滑動窗口算法。

算法4快速安全有符號滑動窗口法

選取一個隨機數r，r與k具有相同的二進制位數且選取r＞k，置 m＝2k－r，n＝r－k。kP＝［（2k－r)＋（r－k)］P＝mP＋nP。

對m、n進行窗口為w的有符號滑動窗口法重新編碼。編碼方法及預計算同算法3中描述的執行步驟相同，在此不作詳述。m、n有相同的長度，計算mP、nP的方法也完全相同。

分別計算出mP與nP后相加即可得到［k］P的值。

算法4采用隨機化密鑰的方法能有效抵抗DPA。DPA攻擊之所以有效是因為每次使用的密鑰都是相同的。如果加密時k是隨機變化的，便無法形成有效的差分能量曲線，從而阻止了DPA攻擊。首先選取了一個大于密鑰的隨機數，采用kP＝［（2k－r)＋（r－d)］P＝mP＋nP的方法來代替直接用k進行計算。每次生成的r隨機，因此每次計算中標量的值與密鑰無直接關系，無法得到算法輸入與功耗的相關性，也就不可能通過DPA得出密鑰。計算過程中將標量按有符號滑動窗口法重新編碼后，采用直接計算（2wR＋S)的快速算法，計算為固定模式，也無法由功耗曲線得出密鑰，故可以抗SPA。隨機化密鑰后每次r的不同會產生不同的編碼，可有效抵抗RPA、ZPA攻擊。總體上來說，采用隨機掩碼方式使計算過程標量與密鑰無直接相關性，能有效抵抗各種功耗分析攻擊方法。

4 算法效率分析與比較

在不同坐標系下橢圓曲線加法、倍點運算的計算量不同。文獻［8］中給出不同坐標系下橢圓曲線點加和倍點的計算量，如表1所示。根據實際應用，密鑰長度一般取S/M＝0.8，I/M 的值根據坐標系的選取及密鑰長度的不同在9～30，本文取中間值，統一設I/M＝20（S、M、I分別代表有限域中的平方、乘法、模逆運算)。

算法4中計算過程為倍點和點加，根據表1計算可知，選用Chudnovsky Jacobian坐標系總的計算量最小。算法4共進行l次倍點運算及（l＋2)次點加計算，在Chudnovsky Jacobian坐標系下總的計算量為：l＊（6S＋5 M)＋（l＋2)＊（3S＋11 M)＝23.2lM＋26.8 M。

Table 1 Calculation of point addition and point doubling based on different coordinates表1 不同坐標系點加和倍點計算量

文獻［8］中證明采用Affine加Jacobian混合坐標系直接計算（2wR＋S)最為快速，在此混合坐標系下直接計算（2wR＋S)的計算量為（4w＋3)S＋（4w＋9)M。

文獻［11］證明用滑動窗口法進行標量乘運算時，長度為l bit的二進制標量在采用USW2，k進行編碼后非零位的平均個數為l/（w＋1)。采用SSW2，k對一個l bits的二進制標量重新編碼后，其非零位的平均個數為l/（w＋2)，因此采用SSW2，k編碼方法后每次執行（2wR＋S)模式直接運算的窗口寬度平均為（w＋2)。算法4取隨機數及其SSW2，k編碼時間與橢圓曲線點乘相比可以忽略不計。

預計算中進行2w－1－1次點加計算及一次倍點計算（Affine坐標系下)，主循環進行2＊l/（w＋2)次（2w＋2R＋S)計算（Jacobian＋Affine混合坐標系)和一次點加計算（Jacobian坐標系)，算法4總的計算量為：

經分析計算，當橢圓曲線密鑰長度l分別取160、192、224、256時，w 取3、4、4、4時計算量最小。

表2中對比了算法4及算法3、文獻［12］中的密鑰分解法的標量乘的計算量，其中，文獻［12］在計算tpre時表述有誤，應為：tpre＝（n－1)＊（m/n)＊DBLJ＋（n－1)＊tJ→A＋（2n－1)＊ADDA。

Table 2 Amount of calculation表2 計算量

由表2分析可知，密鑰分解法在ECC密鑰長度大于224位時有優勢。一般說來，160位ECC密鑰與1 024位RSA密鑰安全等級相同，224位ECC密鑰與2 048位RSA密鑰安全等級相同。224位ECC密鑰足夠滿足需求。且文獻［12］在計算過程中采用加入隨機點抗功耗分析攻擊，未對密鑰進行保護，其抗攻擊性能遠比不上本文使用的密鑰掩碼方法。由表2可得，密鑰長度分別為160、192、224、256時算法效率分別平均提高13%、11.3%、9%、7%。總的說來，綜合考量計算效率與算法安全時，本文設計的算法與其它標量乘算法相比有明顯優勢。

5 結束語

本文研究了抗功耗分析攻擊的橢圓曲線標量乘快速算法，采用有符號滑動窗口算法提高計算效率，基于密鑰掩碼方法實現抗攻擊性能。隨機化密鑰的方法使算法輸入與密鑰無直接相關性，能有效抵抗功耗分析攻擊但增加了計算量，后續應重點研究更高效的抗功耗分析攻擊方法，以提高橢圓曲線標量乘計算效率。

［1］ Solinas J A.Efficient arithmetic on Koblitz curves［J］.Designs，Codes and Cryptography，2000，19（2-3)：195-249.

［2］ Adachi D，Hirata T.Combination of mixed coordinates strategy and direct computations for efficient scalar multiplications［C］∥Proc of the Communications，Computers and Signal Processing，2005：117-120.

［3］ Cohen H，Miyaji A，Ono T.Efficient elliptic curve exponentiation using mixed coordinates［C］∥Proc of the Advances in Cryptology（ASIACRYPT’98)，1998：51-65.

［4］ Kocher P，Jaffe J，Jun B.Differential power analysis［C］∥Proc of the 19th Annual International Cryptology Conference on Advances in Cryptology，1999：1.

［5］ Zhang Fang－guo，Chen Xiao-feng，Wang Yu-min.The status of attack on the discrete logarithm of elliptic curves［J］.Journal of Xidian University，2002，29（3)：399-402.（in Chinese)

［6］ Liu Shuang－gen，Li Ping，Hu Yu-pu.Improvement schemes for scalar multiplication algorithm in elliptic curve cryptography［J］.Computer Engineering，2006，32 （17)：28-29.（in Chinese)

［7］ Zhang Ning.Elliptic curve scalar multiplication secure against power analysis attack［D］.Xi’an：Xidian University，2007.（in Chinese)

［8］ Chevallier-MAMES B，Ciet M，Joye M.Low-cost solutions for preventing simple side-channel analysis：side-channel atomicity［J］.IEEE Transactions on Computers，2006，53（6)：760-768.

［9］ Tong Lian，Qian Jiang.Scalar multiplication algorithm against SPA and DPA attacks in ECC［J］.Computer Engineering and Applications，2010，46（35)：72-74.（in Chinese)

［10］ Mathieu C，Marc J，Kristin L，et al.Trading inversions for multiplications in elliptic curve cryptography［J］.Designs，Codes and Cryptography，2006，39（2)：189-206.

［11］ Phillips B J，Burgess N.Implementing 1024-bits RSA exponentiation on a 32-bits processor core［C］∥Proc of the Application Specific-Systems， Architecture and Processor，2000：127-137.

［12］ Ma Bo，Bao Si-gang，Dai Xian-ying.Efficiency improvement of ECC resisting power attack scheme in smart card［J］.Computer Engineering，2010，36（16)：113-115.（in Chinese)

附中文參考文獻：

［5］ 張方國，陳曉峰，王育民.橢圓曲線離散對數的攻擊現狀［J］.西安電子科技大學學報，2002，29（3)：399-402.

［6］ 劉雙根，李萍，胡予濮.橢圓曲線密碼中標量乘算法的改進方案［J］.計算機工程，2006，32（17)：28-29.

［7］ 張寧.能量分析攻擊下安全的橢圓曲線標量乘法 ［D］.西安：西安電子科技大學，2007.

［9］ 童蓮，錢江.橢圓曲線中抗SPA和DPA攻擊標量乘算法研究［J］.計算機工程與應用，2010，46（35)：72-74.

［12］ 馬博，包斯剛，戴顯英.智能卡中ECC抗功耗攻擊方案的效率改進［J］.計算機工程，2010，36（16)：113-115.

Improved scheme for scalar multiplication against power analysis attacks in elliptic curve cryptography

ZHANG You-qiao1，ZHOU Wu-neng1，SHEN Ye2，LIU Yu-jun2
（1.College of Information Science and Technology，Donghua University，Shanghai 201620；2.Shanghai Huahong Integrated Circuit Co.，Ltd.，Shanghai 201203，China)

Elliptic curve scalar multiplication is the main computing process in Elliptic Curve Cryptography（ECC)，and the efficiency and security of scalar multiplication is always the research hotspot.Aiming at the problem that elliptic curve scalar multiplication has a tremendous computation and is vulnerable to power analysis attacks，a fast sliding window algorithm against power analysis attacks is proposed.In Jacobian and Affine mixed coordinates，the signed sliding window algorithm strategy is used to perform elliptic curve scalar multiplication，and random keys method is applied against power analysis attacks.The analysis results show that，compared with binary expansion method and key assignment method，the improved signed sliding window scalar multiplication algorithm improves calculation efficiency and anti-attack performance significantly.

elliptic curve cryptography；scalar multiplication；power analysis attack；sliding window algorithm；mixed coordinates

TP309

A

10.3969/j.issn.1007-130X.2014.04.013

2012-09-17；

2012-12-30

國家自然科學基金資助項目（61075060)；上海市教育委員會科研創新項目（12zz064)

通訊地址：201620上海市松江區人民北路2999號2號學院樓424

Address：Room 424，2Academy Building，2999Renmin Rd North，Songjiang District，Shanghai 201620，P.R.China

1007-130X（2014)04-0644-05

張友橋（1988-)，男，湖北大悟人，碩士生，研究方向為密碼算法和智能卡安全。E-mail：36xyz88＠163.com

ZHANG You-qiao，born in 1988，MS candidate，his research interests include cryptographic algorithm，and smart card security.