基于奇系數(shù)梳狀算法的ECC抗功耗攻擊算法

殷 守 軍

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

0 引 言

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

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

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

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

ECC標(biāo)量乘的運(yùn)算為

其中:k為標(biāo)量，采用二進(jìn)制編碼表示;n是二進(jìn)制編碼的長(zhǎng)度,則有標(biāo)量k的表示形式如下：

，ki∈{0,1}

(1)

通過(guò)利用奇系數(shù)Comb算法對(duì)ECC的正奇數(shù)標(biāo)量進(jìn)行重新編碼，則標(biāo)量k的奇系數(shù)Comb形式編碼如下：

…+lt-12t-1

(2)

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

n/s

，s表示li的二進(jìn)制編碼長(zhǎng)度,n表示k的二進(jìn)制編碼長(zhǎng)度。下面對(duì)li進(jìn)行二進(jìn)制編碼可得：

(3)

(4)

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

(5)

式中，Pi為預(yù)計(jì)算點(diǎn)，且有各預(yù)計(jì)算點(diǎn)

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

ui∈{0,1}

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

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

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

輸入：k,s,P；

輸出：Q=kP。

(1) 對(duì)標(biāo)量k進(jìn)行奇數(shù)化變換成l；

(2) 令m表示l的二進(jìn)制長(zhǎng)度；

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

(4) 計(jì)算奇系數(shù)Comb編碼長(zhǎng)度t=

m/s

；

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

(6) 令Q=O；

(7) 對(duì)于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è)計(jì)

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

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

(6)

式中，因?yàn)橐肓穗S機(jī)點(diǎn)R，使得在返回Q時(shí)，需增加后處理操作來(lái)進(jìn)行恢復(fù)：若k為奇數(shù)，則增加操作Q=Q-2P-R；若k為偶數(shù)，則增加操作Q=Q-P-R。所給基于奇系數(shù)Comb的標(biāo)量乘抗功耗攻擊算法具體過(guò)程如算法2所示。

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

輸入：k,P；

輸出：Q=kP。

(1) 對(duì)標(biāo)量k進(jìn)行奇數(shù)化變換成l；

(2) 令m為奇數(shù)化標(biāo)量l的二進(jìn)制長(zhǎng)度；

(3)R=random()；

(5) 計(jì)算奇系數(shù)Comb編碼長(zhǎng)度t=

m/s

；

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

(7) 令Q=R；

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

n/s

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

表1 算法2和BR、WBRIP以及FWNAF的運(yùn)算效率比較

w0=

w

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

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)(References)：

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

[2] 王正義, 趙俊閣. ECC抗功率分析攻擊的等功耗編碼算法[J]. 計(jì)算機(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] 張友橋, 周武能, 申 曄, 等. 橢圓曲線密碼中抗功耗分析攻擊的標(biāo)量乘改進(jìn)方案[J]. 計(jì)算機(jī)工程與科學(xué), 2014, 36(4): 644-648.

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

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

[7] 趙樹(shù)林, 王正義, 陳 璐, 等. 基于帶符號(hào)階乘展開(kāi)式的抗功耗方案算法[J]. 計(jì)算機(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]. 計(jì)算機(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] 賴(lài)忠喜, 張占軍, 陶東婭. 橢圓曲線中直接計(jì)算7P的方法及其應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用, 2013, 33(7): 1870-1874.

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

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

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