殷 守 軍

(北京聯(lián)合大學(xué) 工科綜合實驗教學(xué)示范中心，北京 100101)

0 引 言

功耗攻擊給密碼芯片的安全帶來了極大的威脅，但由于密碼芯片自身資源限制，造成其在采取防御功耗攻擊措施后，將降低密碼芯片運算效率，致使產(chǎn)生效率與安全的矛盾，如何解決這一矛盾則成為密碼芯片抗功耗攻擊研究的熱點問題[1-2]。功耗攻擊是Paul Kocher在1998年首先提出的密碼分析方法，主要工作原理是密碼芯片運行時，不同操作產(chǎn)生的功耗不同，通過采集這些泄露的功耗信息，并分析功耗之間的差異即可獲取相關(guān)密鑰信息。而且功耗分析具有易于實現(xiàn)、成功率高等諸多良好攻擊特性，因而相較于傳統(tǒng)數(shù)學(xué)攻擊方法而言，功耗分析對密碼芯片所帶來的安全威脅更嚴重[3-4]。一般來說，功耗攻擊因攻擊手段不同主要分為：簡單功耗攻擊技術(shù)(Simple Power Attack, SPA)和差分功耗攻擊技術(shù)(Differential Power Attack, DPA)。其中，由于密碼芯片中的主流算法大都是采用橢圓曲線密碼(Elliptic Curve Cryptogram, ECC)算法，使得出現(xiàn)了一些列針對ECC的功耗攻擊，包括零值寄存器攻擊(Zero-value Power Attack, ZPA)與零值點攻擊(Refined Power Attack, RPA)[5]。

國內(nèi)外學(xué)者關(guān)于密碼芯片的抗功耗攻擊方面做了大量研究工作[6-7]。Mamiya等[8]給出了一種基于窗口隨機化初始點的ECC抗功耗攻擊方案(Window-Based Random Initial Point, WBRIP)，基本思想是通過將標量的二進制編碼進行窗口化，在一個窗口內(nèi)實現(xiàn)掩蓋所執(zhí)行的點加運算與倍點運算次數(shù)的目的，致使攻擊者無法從中間值猜測運算過程中所執(zhí)行的具體操作及相關(guān)步驟，盡管WBRIP可以抵抗多種功耗攻擊，但是其運算效率需進一步提高。張濤等[9]給出了一種固定窗口寬度為w的非鄰接表示形式的ECC抗功耗攻擊算法(Fractional Width-wNon Adjacent From, FWNAF)，主要思想是利用二進制的非鄰接表示形式來優(yōu)化編碼，減少在抵抗功耗攻擊過程中所需添加偽操作的次數(shù)，從而實現(xiàn)運算效率的提升。文獻[10]中給出一種高效的窗口隨機化初始點ECC抗功耗攻擊算法(Efficient-Based Random Initial Point, EBRIP)，主要思想是將標量的二進制編碼表示成窗口寬度是w的非鄰接表示形式，并將其分成整數(shù)部分與分數(shù)部分實現(xiàn)抵抗SPA。接著再將基點分成固定部分與可變部分可實現(xiàn)抵抗DPA、ZPA與RPA，并且也可提升運算效率。奇系數(shù)Comb算法是ECC標量乘法運算的一種快速計算方法，為保證算法能夠抵抗功耗攻擊并進一步有效提升運算效率，本文通過在奇系數(shù)Comb標量乘算法中結(jié)合添加偽操作與基點掩碼技術(shù)，給出了一種密碼芯片上基于奇系數(shù)Comb算法的ECC抗功耗攻擊算法，同BR、WBRIP及FWNAF算法相比，所給抗功耗攻擊算法不僅有相同的抗功耗攻擊安全性，而且具有更高的運算效率。

1 奇系數(shù)Comb標量乘算法

ECC標量乘快速算法主要有兩類:一類是通過提高底層域運算來實現(xiàn);另一類是對標量進行重新編碼來實現(xiàn)。其中，奇系數(shù)Comb標量乘算法屬于第二類快速算法，同時也是常用的ECC標量乘快速算法，與其他同類快速算法(諸如雙基數(shù)系統(tǒng)快速算法[11]、階乘展開式快速算法[12]和整數(shù)拆分表示形式快速算法[13]等)相比，具有所需存儲空間較小,運算效率更高等優(yōu)點。下面給出ECC的奇系數(shù)Comb標量乘快速算法實施過程：

ECC標量乘的運算為

其中:k為標量，采用二進制編碼表示;n是二進制編碼的長度,則有標量k的表示形式如下：

，ki∈{0,1}

(1)

通過利用奇系數(shù)Comb算法對ECC的正奇數(shù)標量進行重新編碼，則標量k的奇系數(shù)Comb形式編碼如下：

…+lt-12t-1

(2)

式中:li表示標量k的奇系數(shù)Comb算法編碼系數(shù)，且有l(wèi)i≠0;t表示li的編碼長度，且有t=

n/s

，s表示li的二進制編碼長度,n表示k的二進制編碼長度。下面對li進行二進制編碼可得：

(3)

(4)

則ECC標量乘法的運算形式可轉(zhuǎn)換為如下形式：

(5)

式中，Pi為預(yù)計算點，且有各預(yù)計算點

Pi=(u(s-1)2(s-1)t+…+ui2it+…+u12t+1)·P

ui∈{0,1}

然后根據(jù)已預(yù)計算出的各預(yù)計算點生成預(yù)計算表。

需要把已知標量k奇數(shù)化，且令奇數(shù)化后的標量為l。即如果k為正奇數(shù)，則l=k+1；但如果k是正偶數(shù)，則l=k+2。由于對k進行了奇數(shù)化，所以需在返回Q值時增加后處理操作：若k為奇數(shù)，則要增加一次Q=Q-2P操作；若k為偶數(shù)，則要增加一次Q=Q-P操作。所以ECC標量重新編碼之后，奇系數(shù)Comb標量乘運算的具體過程如下。

算法1ECC的奇系數(shù)Comb標量乘快速算法。

輸入：k,s,P；

輸出：Q=kP。

(1) 對標量k進行奇數(shù)化變換成l；

(2) 令m表示l的二進制長度；

(3) 生成預(yù)計算表Pi；

(4) 計算奇系數(shù)Comb編碼長度t=

m/s

；

(5) 計算奇系數(shù)Comb編碼系數(shù)li；

(6) 令Q=O；

(7) 對于i從t-1到0，重復(fù)執(zhí)行：①Q(mào)=2Q；②Q=Q+liP；

(8) 返回輸出值Q：①k為偶數(shù)，返回Q=Q-P;②k為奇數(shù)，返回Q=Q-2P。

2 新算法設(shè)計

在算法1中，由于標量的奇系數(shù)編碼系數(shù)li都不為0，因而在步驟(6)中總是執(zhí)行同樣的操作步驟和順序。也即是，每當(dāng)執(zhí)行一次倍點運算后就接著也執(zhí)行一次點加運算，所獲得的能耗圖譜基本沒有出現(xiàn)顯著的功耗曲線差異，這樣也就使攻擊者不能根據(jù)功耗的差異來猜測相關(guān)的密鑰信息。并且無論所給標量是奇數(shù)還是偶數(shù)，在步驟(8)中都會執(zhí)行一次點加運算，因此所給標量的奇偶性也不會被泄露。因而算法1能夠防御SPA。然而，因為已知的基點P致使運算中間值和輸入之間具有一定的相關(guān)性，這就使得攻擊者能夠利用運算過程的中間值來推測出相關(guān)的密鑰信息，因而算法1不能防御DPA。與此同時，所給的基點中可能存在有可以被攻擊者利用的特殊點，從而使得算法1不能抵抗ZPA與RPA。

文中采用了基點掩碼技術(shù)，即通過在標量乘運算中引入隨機點將基點隨機化，同時再結(jié)合預(yù)計算的方法可實現(xiàn)多標量乘法運算中各分基點的隨機化，以此即可掩蓋每個小標量乘法運算同功耗之間的相關(guān)性，這樣就致使攻擊者無法利用統(tǒng)計分析的方法，通過多次猜測來獲取有效的密鑰信息。所以，基于奇系數(shù)Comb編碼標量乘運算Q=kP在引入隨機點R之后可轉(zhuǎn)化成如下形式：

(6)

式中，因為引入了隨機點R，使得在返回Q時，需增加后處理操作來進行恢復(fù)：若k為奇數(shù)，則增加操作Q=Q-2P-R；若k為偶數(shù)，則增加操作Q=Q-P-R。所給基于奇系數(shù)Comb的標量乘抗功耗攻擊算法具體過程如算法2所示。

算法2基于奇系數(shù)Comb的標量乘抗功耗攻擊算法。

輸入：k,P；

輸出：Q=kP。

(1) 對標量k進行奇數(shù)化變換成l；

(2) 令m為奇數(shù)化標量l的二進制長度；

(3)R=random()；

(5) 計算奇系數(shù)Comb編碼長度t=

m/s

；

(6) 計算奇系數(shù)Comb編碼系數(shù)li；

(7) 令Q=R；

(8) 對于i從t-1到0，重復(fù)執(zhí)行：①Q(mào)=2Q；②Q=Q+liP；

(9) 返回輸出值Q：①k為偶數(shù)，返回Q=Q-P-R;②k為奇數(shù)，返回Q=Q-2P-R。

3 性能分析

在算法2中，因為不存在系數(shù)為0的系數(shù)，使得其沒有功耗差異的操作，所以其能耗圖譜是相同的，這也表明其本身具備抵抗SPA的能力。同時，由于引入了隨機點R，使得預(yù)計算表中分基點Pi和功耗之間的相關(guān)性被掩藏，進而也可隱藏可被利用的某些特殊點，因而算法2能防御DPA、ZPA與RPA。最后，算法2執(zhí)行了兩次后處理操作，這主要是實現(xiàn)兩個方面的目的：一方面是用于掩蓋原標量自身的奇偶性，有效提升了算法的安全性；另一方面是可減去引入的隨機點，從而恢復(fù)真實的返回值。由上述分析可知，所給抗功耗攻擊算法的功耗差異被隱藏，且不存在特殊點被攻擊者利用，因此所給算法能夠抵御SPA、DPA、ZPA與RPA多種功耗攻擊。

n/s

，n為奇數(shù)化標量的二進制長度。表1給出了算法2和BR算法(二進制)、WBRIP算法以及FWNAF算法的運算效率比較。其中，w表示窗口寬度，且有w=4。此外，w0和w1分別為FWNAF抗功耗攻擊算法中窗口w的整數(shù)部分和碎片部分，且有，w1=w-(w0-1)[14]。

表1 算法2和BR、WBRIP以及FWNAF的運算效率比較

w0=

w

由表1可知，算法2需要的存儲空間要比WBRIP和FWNAF小。但是，WBRIP比算法2要多執(zhí)行了(2s-1-2)次點加操作和(2s-1+s-2)次倍點操作，而FWNAF算法比算法2多執(zhí)行了(w0-1)次倍點操作，執(zhí)行的點加操作次數(shù)基本相似。由此可以看出，算法2不僅能夠保持同樣抗功耗攻擊能力，同時還能夠在降低存儲空間的情況下提升運算效率。當(dāng)前ECC中512 bit的密鑰一般被認為是安全的，即n=512。令s=4，w=4，則t=128，w0=4，w1=1。在仿射坐標系下[15]，A=23M，D=24M，M表示模乘運算,則有BR、WBRIP、FWNAF的總運算量分別為24 064M、16 025M、15 766M，而算法2的總運算量為15 671M。因此，算法2比BR的運算效率提升了34.88%，比WBRIP提升了2.21%，與FWNAF的總運算量基本相似。盡管算法2所需的預(yù)計算量要比WBRIP算法和FWNAF算法大得多，但是預(yù)計算表能夠預(yù)先存儲到密碼芯片中。然而，僅僅對于主循環(huán)運算來說，算法2比WBRIP算法與FWNAF算法的運算效率均提升了60.04%左右。由此可知，算法2可以同時兼顧到安全和效率兩個方面，可以較好地用于各種資源受限的應(yīng)用環(huán)境中。

4 結(jié) 語

ECC是密碼安全芯片中主流的密碼算法，廣泛應(yīng)用于各類安全環(huán)境中，而其中基于奇系數(shù)梳狀算法的標量乘運算則是ECC中的一種快速標量乘算法，但是,因為近年來出現(xiàn)的功耗分析技術(shù)致使密碼安全芯片遭遇了非常大的安全風(fēng)險和挑戰(zhàn)。文中結(jié)合奇系數(shù)Comb快速標量乘算法與基點掩碼技術(shù)，給出了一種改進的ECC抗功耗攻擊算法。該算法與BR、WBRIP以及FWNAF抗功耗攻擊算法相比，不僅同樣能夠有效抵抗多種功耗攻擊，同時具有更高的運算效率。由此可知，所給算法能較好地解決密碼芯片等類似系統(tǒng)因資源受限而存在效率和安全兩方面矛盾的問題，能夠較好地用于各類自身資源受限的應(yīng)用系統(tǒng)中。

參考文獻(References)：

[1] 郭 彬, 孫忠廷, 王 勇, 等. 抗能量分析攻擊的階乘展開式標量乘算法[J]. 科技通報, 2016, 32(6): 149-155.

[2] 王正義, 趙俊閣. ECC抗功率分析攻擊的等功耗編碼算法[J]. 計算機工程, 2012, 38(10): 111-113.

[3] Pang S C, Tong S Y, Cong F Z,etal. A efficient elliptic curve scalar multiplication algorithm against side channel attacks [C]//Proceedings of the 2010 International Conference on Computer, Mechatronics, Control and Electronic Engineering (CMCE2010), Berlin: Springer-Verlag, 2010: 361-364.

[4] 張友橋, 周武能, 申 曄, 等. 橢圓曲線密碼中抗功耗分析攻擊的標量乘改進方案[J]. 計算機工程與科學(xué), 2014, 36(4): 644-648.

[5] 梁 芳, 沈濟南. 基于奇系數(shù)Comb的橢圓曲線密碼抗功耗攻擊方案[J]. 計算機應(yīng)用與軟件統(tǒng), 2016, 33(3): 288-290.

[6] 閆 娜. 基于帶符號整數(shù)拆分形式的抗功耗攻擊方案[J]. 中國電子科學(xué)研究院學(xué)報, 2017, 12(4): 438-442.

[7] 趙樹林, 王正義, 陳 璐, 等. 基于帶符號階乘展開式的抗功耗方案算法[J]. 計算機與數(shù)字工程, 2014, 42(6): 924-926.

[8] Mamiya H, Miyaji A, Morimoto H. Efficient countermeasures against RPA, DPA, and SPA [C]//Cryptographic Hardware and Embedded Systems(CHES’04), LNCS 3156, NY: Springer-Verlag, 2004: 343-356.

[9] 張 濤, 范明鈺, 王光衛(wèi), 等. Smartcard上橢圓曲線密碼算法的能量攻擊和防御[J]. 計算機工程, 2007, 33(14): 125-127.

[10] Zhang Tao, Fan Mingyu, Zheng Xiaoyu. Secure and efficient elliptic curve cryptography resists side-channel attacks [J]. Journal of Systems Engineering and Electronics, 2009, 20(3): 660-665.

[11] Dimitrov V S, Jullien G A, Miller W C. Theory and applications for a double-base number system [J]. IEEE Transactions on Computers, 1999, 48(10): 1098-1106.

[12] 賴忠喜, 張占軍, 陶東婭. 橢圓曲線中直接計算7P的方法及其應(yīng)用[J]. 計算機應(yīng)用, 2013, 33(7): 1870-1874.

[13] 石潤華, 葛麗娜, 鐘 誠. 橢圓曲線密碼體制上一種快速kP算法[J]. 計算機工程與科學(xué), 2004, 26(4): 55-58.

[14] 尹 恒, 蔣朝惠, 付 威. 抗邊信道攻擊的高效多基標量乘算法[J]. 計算機應(yīng)用, 2014, 34(11): 3287-3290.

[15] 王玉璽, 張串絨, 張柄虹, 等. 基于素數(shù)域上復(fù)合運算的快速標量乘算法[J]. 計算機應(yīng)用研究, 2013, 30(11): 3365-3387.