基于分拆窗口NAFw標量乘的抗功耗分析方案

鄔 迎 高 靜

(中原工學(xué)院信息商務(wù)學(xué)院 河南 鄭州 450007)

0 引 言

橢圓曲線密碼(Elliptic curve cryptography,ECC)構(gòu)建的高安全性主要基于橢圓曲線離散對數(shù)難題，尤其是針對一些特殊橢圓曲線所構(gòu)建的橢圓曲線密碼大都具有亞指數(shù)甚至多項式時間算法。在通常情況下，160 bit密鑰的ECC算法與1 024 bit密鑰的RSA算法具有同級別的安全性[1-2]。ECC具有密鑰長度短、基于有限域運算次數(shù)遠小于傳統(tǒng)離散對數(shù)、易在計算機軟硬件上實現(xiàn)加法運算等優(yōu)點。同時ECC也有高復(fù)雜度、處理速度低的不足，所以國內(nèi)外研究人員提出了一系列諸如二進制編碼算法、2w編碼算法、滑動窗口編碼算法等多種優(yōu)化算法[3]。然而，在大多數(shù)優(yōu)化的ECC標量乘中僅考慮提高運算效率的問題，卻未施加任何抗邊信道攻擊的相關(guān)措施。邊信道攻擊(Side channel attack,SCA)[4-5]是近年來針對橢圓曲線密碼進行攻擊最具威脅的手段之一，其主要工作原理是在密碼算法執(zhí)行過程中通過監(jiān)聽一些諸如算法執(zhí)行時間、固定步驟能耗等相關(guān)信息，然后攻擊者從這些通過監(jiān)聽所獲取的信息中收集一些與密鑰具有相關(guān)性的信息，從而獲知密碼算法內(nèi)在的工作情況，進而可以猜測出相關(guān)密鑰信息。其中，功耗分析是邊信道攻擊中被廣泛運用的攻擊方法之一。功耗分析[6]主要通過獲取密碼系統(tǒng)工作中的能耗信息來得到與密鑰相關(guān)中間值信息，該方式實現(xiàn)簡單且成功率高。功耗分析通常包括簡單功耗分析(Simple power analysis, SPA)與差分功耗分析(Differential power analysis, DPA)等。

由于增加抗功耗分析措施會降會低標量乘的運算效率，使得橢圓曲線密碼存在安全與效率的矛盾。因此，為同時兼顧橢圓曲線密碼算法的安全和效率，提出了一種基于分拆窗口NAFw的標量乘抗功耗分析方案(FW-NAFw)。該方案首先采用基于窗口的二元非相鄰形式編碼方法(NAFw)對標量進行編碼，從而實現(xiàn)橢圓曲線密碼標量乘算法;通過分析NAFw的各種改進方案，給出一種改進的NAFw;用標量乘算法提高橢圓曲線密碼的執(zhí)行效率，最后在所給改進NAFw標量乘算法的基礎(chǔ)上采用分拆窗口方法實施抗功耗分析。

1 NAFw標量乘算法

二元非相鄰形式(Non-adjacent form, NAF)[7]是對ECC中的標量k進行重新編碼的一種方式，具體指k的NAF編碼中的比特位包含0、1、-1三種元素，且不會存在相鄰的非零元素。即標量k的NAF編碼形式為k=(km-1,…,ki,…,k1,k0)NAF，其中ki∈{-1,0,1}，且有km-1≠0，具體表示形式如下：

(1)

為了進一步提高NAF標量乘算法的效率，國內(nèi)外研究人員提出了基于窗口的NAFw。由Okeya等[8]提出的NAFw編碼方法具有更好的運算效率，如算法1所示。

算法1NAFw

輸入：標量k，長度為n比特，窗口寬度w。

輸出：k=(km-1,…,ki,…,k1,k0)NAFw。

1. 令i=0；

2. 如果k≠1，則重復(fù)執(zhí)行：

3.u=(kmod2w+1)-2w；

4.kw[i]=u;kw[i+1]=0;…;kw[i+w+1]=0；

6.kw[i]=1;kw[i+1]=0;…;kw[i+w+1]=0；

7. 返回(km-1,…,ki,…,k1,k0)NAFw。

算法2從左到右基于改進NAFw編碼標量乘算法

輸入：標量k，長度為n比特，窗口寬度w。

輸出：Q=kP。

1. 令i=0，Q=O；

2. 預(yù)計算uP；

3. 當i>w時，則重復(fù)執(zhí)行：

4.u=k[i-1→i-w]‖1

//k[i→j]表示從k推出的比特串，

//從j位開始到i位結(jié)束；

5. 若k[i]=0且i

6.Q=2wQ；

7.Q=Q+uP；

8.i=i-w;

9.u=k[i-1→0]；

10. 若k[i]=0且i

11.Q=2iQ；

12.Q=Q+uP；

13. 返回Q。

2 FW-NAFw抗功耗分析方案

未施加抗功耗分析措施的橢圓曲線標量乘算法都易遭受攻擊。目前，抵抗功耗分析的方案主要包括基于固定程序方法、基于隨機加法鏈方法、基于統(tǒng)一公式方法等。其中，基于固定程序方法主要指在執(zhí)行標量乘時，當標量的二進制位為0和1時執(zhí)行相同的操作程序，從而致使標量乘的點加操作和倍點操作不可區(qū)分，目前已有典型的基于固定程序方法的抗功耗分析方案主要包括Coron冗余方案[9]、Montgomery階梯方案[10]和M?ller方案[11]?；陔S機加法鏈方法主要指嘗試利用多種加法鏈來抵抗SPA與DPA，目前典型的基于隨機加法鏈方法的抗功耗分析方案主要包括隨機窗口方案[12]與隨機加減鏈方案[13]。基于統(tǒng)一公式方法主要指通過減少ECC標量乘中點加操作和倍點操作的差異來抵抗功耗分析，該方案盡管能掩蓋非零位元素在編碼序列中的位置，然而攻擊者仍可以利用私鑰中的漢明重量信息實施傳統(tǒng)攻擊[14]。因此，為有效抵抗功耗分析，在算法2的NAFw編碼標量乘算法基礎(chǔ)上，采用分拆窗口的方法來抵抗功耗分析，從而給出一種兼顧安全和效率的橢圓曲線密碼標量乘方案。下面給出基于拆分窗口NAFw的ECC標量乘抗功耗分析算法，如算法3所示。

算法3基于拆分窗口NAFw的抗功耗分析算法

輸入：標量k，長度為n比特，窗口寬度w，b∈B的概率p。

輸出：Q=kP。

1. 令i=0，Q=O；

2. 預(yù)計算uP；

3. 當i≥w時，則重復(fù)執(zhí)行：

4.x=k[i-1→i-w]‖1；

5.y=k[i-1→i-w+1]‖1；

//k[i→j]表示從k推出的比特

//串，從j位開始到i位結(jié)束

6. 如果k[i]=0且i

7.x=x-2w；

8.y=y-2w-1；

9. 如果|x|<2w-1，則引入隨機數(shù)r，且有0≤r≤1；

10. 如果r

11. 如果r≥p，則執(zhí)行u=y，r=w-1；

12. 如果|x|∈B，則執(zhí)行u=x，r=w；

13. 如果|x|?B，則執(zhí)行u=y，r=w-1；

14.Q=2rQ，Q=Q+uP，i=i-r；

15. 如果k[i]=0，則執(zhí)行u=u-2i；

16.Q=2rQ，Q=Q+uP；

17. 返回Q。

3 性能分析

通常密碼算法的安全性與密鑰長度相關(guān)，雖然較長的密鑰可以大幅提高密碼算法的安全性，但同時也降低標量乘法運算的實現(xiàn)效率。表1給出了密鑰長度為160 bit時不同窗口寬度下所需的理論計算量?？梢钥闯觯黾拥倪\用量導(dǎo)致采用分拆窗口的標量乘運用效率要比采用較小整體窗口的標量乘運算效率更低。當w=4,8時，標量乘法運算不需要額外的計算量，而當w=5,6時，則需要更多的運算量，但w=4時需要的存儲空間更大。

表1 密鑰長度為160 bit時不同窗口寬度下所需理論計算量

表2 算法3的運算量小于算法2的運算量時所取的γ最小值

當算法3抵抗簡單功耗分析時，即算法3執(zhí)行過程中點加操作的運算量近似于倍點操作的運算量，則在Jacobian坐標系下可計算得到γ=1.66，其中：S≈0.8M，S表示平方運算的運算量，M表示模乘運算的運算量[15]。這說明當w=5,6,9,10,11,12,13時，基于分拆窗口NAFw的抗功耗分析算法的運算效率低于基于整體窗口NAFw的標量乘算法的運算效率；當w=3,7,14,15時，所給基于分拆窗口NAFw的抗功耗分析算法的運算效率高于基于整體窗口NAFw的標量乘算法的運算效率。而在射影坐標系下，可計算得到γ=2.25。這說明當w=3,6,7時，所給基于分拆窗口NAFw的抗功耗分析算法的運算效率高于在v=3時整體窗口NAFw的標量乘算法的運算效率；同樣地，當w=13,14,15時，基于分拆窗口NAFw的抗功耗分析算法的運算效率也高于在v=4時整體窗口NAFw的標量乘算法的運算效率。

當算法3抵抗簡單功耗分析及差分功耗分析時，在Jacobian坐標系下，可計算得到γ=2.33，此時當w=3,6,7,13,14,15時，算法3的運算效率更高，同時結(jié)合隨機坐標技術(shù)即可實現(xiàn)抵抗簡單功耗分析及差分功耗分析。在射影坐標系下，可計算得到γ=3，此時當w=3,6,7,12,13,15時，算法3具有更高的運算效率且可抵抗簡單功耗分析以及差分功耗分析。

當算法3抵抗簡單功耗分析及二階差分功耗分析時，在Jacobian坐標下，素數(shù)域上橢圓曲線密碼標量乘算法的運算量為17M+7S，則可計算得到γ=3.14，此時查表可知當w=3,6,7,12,13,14,15，算法3具有更高的運算效率，且能夠抵抗簡單功耗分析以及二階差分功耗分析。在射影坐標系下，二元域上橢圓曲線密碼標量乘算法的運算量為15M，則可計算得到γ=3.75，此時查表可知當w=3,6,7，所給基于分拆窗口NAFw抗功耗分析算法的運算效率高于在v=3時整體窗口NAFw的標量乘算法的運算效率；同樣地，當w=12,13,14,15時，所給基于分拆窗口NAFw的抗功耗分析算法的運算效率也高于在v=4時整體窗口NAFw的標量乘算法的運算效率，且均可抵抗簡單功耗分析和二階差分功耗分析。

4 結(jié) 語

橢圓曲線密碼算法是應(yīng)用最為廣泛的密碼算法之一，但是功耗分析技術(shù)嚴重威脅橢圓曲線密碼算法的安全，施加抗功耗分析措施的同時將會降低橢圓曲線密碼算法的運算效率。為同時保證橢圓曲線密碼算法的安全和效率，給出了一種基于拆分窗口的NAFw的抗功耗分析方案。本文方案一方面通過改進NAFw算法來提高橢圓曲線密碼標量乘算法效率，另一方面采用拆分窗口的方法實現(xiàn)抗功耗分析，且該方案可根據(jù)實際情況選取窗口寬度。算法性能分析表明，本文算法可以同時兼顧安全和效率，具有靈活高效、安全性較高、占用空間小等優(yōu)點，非常適用于智能芯片等存儲資源受限的密碼設(shè)備中，因此具有較好理論研究價值和實際推廣應(yīng)用價值。