基于分拆窗口NAFw標(biāo)量乘的抗功耗分析方案

鄔 迎 高 靜

(中原工學(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標(biāo)量乘中僅考慮提高運算效率的問題，卻未施加任何抗邊信道攻擊的相關(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)等。

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

1 NAFw標(biāo)量乘算法

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

(1)

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

算法1NAFw

輸入：標(biāo)量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編碼標(biāo)量乘算法

輸入：標(biāo)量k，長度為n比特，窗口寬度w。

輸出：Q=kP。

1. 令i=0，Q=O；

2. 預(yù)計算uP；

3. 當(dāng)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抗功耗分析方案

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

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

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

輸出：Q=kP。

1. 令i=0，Q=O；

2. 預(yù)計算uP；

3. 當(dāng)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)，雖然較長的密鑰可以大幅提高密碼算法的安全性，但同時也降低標(biāo)量乘法運算的實現(xiàn)效率。表1給出了密鑰長度為160 bit時不同窗口寬度下所需的理論計算量。可以看出，增加的運用量導(dǎo)致采用分拆窗口的標(biāo)量乘運用效率要比采用較小整體窗口的標(biāo)量乘運算效率更低。當(dāng)w=4,8時，標(biāo)量乘法運算不需要額外的計算量，而當(dāng)w=5,6時，則需要更多的運算量，但w=4時需要的存儲空間更大。

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

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

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

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

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

4 結(jié) 語

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