橢圓曲線密碼中抗功耗分析攻擊的標(biāo)量乘改進(jìn)方案＊

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

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

橢圓曲線密碼中抗功耗分析攻擊的標(biāo)量乘改進(jìn)方案＊

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

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

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

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

1 引言

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

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

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

2 橢圓曲線密碼

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

2.1 橢圓曲線密碼原理

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

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

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

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

2.2 橢圓曲線標(biāo)量乘法

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

算法1二進(jìn)制展開法

2.3 滑動窗口法

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

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

算法2有符號滑動窗口法

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

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

3.1 功耗分析攻擊

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

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

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

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

3.2 抗功耗攻擊的二進(jìn)制展開法

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

對算法1的改進(jìn)如算法3所示，采取基點(diǎn)掩碼的方式增強(qiáng)算法的抗功耗分析攻擊能力。

算法3抗功耗攻擊的二進(jìn)制展開法［9］

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

3.3 改進(jìn)的滑動窗口法

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

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

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

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

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

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

4 算法效率分析與比較

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

算法4中計算過程為倍點(diǎn)和點(diǎn)加，根據(jù)表1計算可知，選用Chudnovsky Jacobian坐標(biāo)系總的計算量最小。算法4共進(jìn)行l(wèi)次倍點(diǎn)運(yùn)算及（l＋2)次點(diǎn)加計算，在Chudnovsky Jacobian坐標(biāo)系下總的計算量為：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 不同坐標(biāo)系點(diǎn)加和倍點(diǎn)計算量

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

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

預(yù)計算中進(jìn)行2w－1－1次點(diǎn)加計算及一次倍點(diǎn)計算（Affine坐標(biāo)系下)，主循環(huán)進(jìn)行2＊l/（w＋2)次（2w＋2R＋S)計算（Jacobian＋Affine混合坐標(biāo)系)和一次點(diǎn)加計算（Jacobian坐標(biāo)系)，算法4總的計算量為：

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

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

Table 2 Amount of calculation表2 計算量

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

5 結(jié)束語

本文研究了抗功耗分析攻擊的橢圓曲線標(biāo)量乘快速算法，采用有符號滑動窗口算法提高計算效率，基于密鑰掩碼方法實(shí)現(xiàn)抗攻擊性能。隨機(jī)化密鑰的方法使算法輸入與密鑰無直接相關(guān)性，能有效抵抗功耗分析攻擊但增加了計算量，后續(xù)應(yīng)重點(diǎn)研究更高效的抗功耗分析攻擊方法，以提高橢圓曲線標(biāo)量乘計算效率。

［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)

附中文參考文獻(xiàn)：

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

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

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

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

［12］ 馬博，包斯剛，戴顯英.智能卡中ECC抗功耗攻擊方案的效率改進(jìn)［J］.計算機(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

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

通訊地址：201620上海市松江區(qū)人民北路2999號2號學(xué)院樓424

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

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

張友橋（1988-)，男，湖北大悟人，碩士生，研究方向?yàn)槊艽a算法和智能卡安全。E-mail：36xyz88＠163.com

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