徐明，史量

（1. 上海海事大學(xué)信息工程學(xué)院，上海 201306；2. 同濟(jì)大學(xué)電子與信息工程學(xué)院，上海 201804）

1 引言

公鑰密碼體制是密碼學(xué)的重要組成部分。目前基于公鑰密碼體制的密碼系統(tǒng)主要有 RSA密碼系統(tǒng)[1]和橢圓曲線密碼系統(tǒng)[2,3]（ECC, elliptic curve cryptosystem）。近年來，隨著分布式計(jì)算以及量子技術(shù)的日趨成熟，對密碼系統(tǒng)的安全性要求也急劇提升，導(dǎo)致 RSA密鑰長度隨著保密性提高而迅速增長的缺點(diǎn)被不斷放大。這使密鑰長度較短的橢圓曲線密碼系統(tǒng)的應(yīng)用領(lǐng)域越來越廣，在無線傳感器網(wǎng)絡(luò)[4]、智能芯片卡[5]以及虛擬貨幣[6]的加密中都有比較成熟的應(yīng)用。美國國家安全局建議，384位橢圓曲線密碼系統(tǒng)足以保護(hù)美國軍方最高機(jī)密[7]。

然而，橢圓曲線密碼系統(tǒng)的高安全性是建立在“黑盒攻擊”[8]的基礎(chǔ)上的，即攻擊者只知道算法的輸入和輸出，而對算法的內(nèi)部構(gòu)造一無所知。實(shí)際上，加密設(shè)備在運(yùn)行過程中不可避免地會泄露一些側(cè)信道信息[9]。Kocher[10]在1996年提出可以通過側(cè)信道泄露的信息，如運(yùn)算過程中各部分所用時(shí)間、電磁輻射量和消耗能量不同等信息，分析出保密信息的攻擊方法，使一些在數(shù)學(xué)理論上安全的加密手段也有被破解的可能。對于通過橢圓曲線密碼系統(tǒng)加密的單片機(jī)系統(tǒng)，由于其加密系統(tǒng)在運(yùn)行時(shí)功耗噪聲較小以及橢圓曲線密碼系統(tǒng)在標(biāo)量乘運(yùn)算中的相關(guān)特性，特別容易受到能量分析攻擊的威脅[11]。能量分析攻擊可以分為簡單能量分析（SPA, simple power analysis）攻擊[12]和差分能量分析（DPA, differential power analysis）攻擊[13]。

為了提高橢圓曲線密碼系統(tǒng)的整體效率和安全性，目前，主流方法從多個(gè)結(jié)構(gòu)層次對其進(jìn)行優(yōu)化。文獻(xiàn)[14]指出，在傳統(tǒng)雅可比坐標(biāo)下，倍點(diǎn)運(yùn)算開銷為4M+6S，其中，M為乘法運(yùn)算，S為平方運(yùn)算，三倍點(diǎn)運(yùn)算開銷為 6M+10S，五倍點(diǎn)運(yùn)算開銷為15M+10S；文獻(xiàn)[15]使用側(cè)信道原子法，在群運(yùn)算層抵御SPA，并且通過引入第四變量W簡化群運(yùn)算，使倍點(diǎn)運(yùn)算的開銷降低到6M+4S。文獻(xiàn)[16]在標(biāo)量乘運(yùn)算層采用經(jīng)過隨機(jī)基點(diǎn)坐標(biāo)處理的蒙哥馬利階梯法，可以抵御SPA和DPA，并根據(jù)蒙哥馬利階梯法的特點(diǎn)設(shè)計(jì)了復(fù)合群運(yùn)算，將點(diǎn)加和倍點(diǎn)的整體開銷降低到6M+5S。文獻(xiàn)[17]在使用NIST曲線的基礎(chǔ)上，將倍點(diǎn)運(yùn)算的開銷降低到4M+4S，并且在標(biāo)量乘運(yùn)算層上改進(jìn)了D&A（double and add）方法，使其系統(tǒng)可以抵御SPA和DPA。文獻(xiàn)[18]的方法與文獻(xiàn)[16]類似，使用MoTE曲線并改進(jìn)了投射坐標(biāo)，將點(diǎn)加和倍點(diǎn)的整體開銷降低到5M+4S。文獻(xiàn)[19]在標(biāo)量乘運(yùn)算層采用以2、3為基的雙基鏈法，在群運(yùn)算層通過完全平方變換將倍點(diǎn)運(yùn)算和三倍點(diǎn)運(yùn)算的開銷分別降低到1M+8S和5M+10S。文獻(xiàn)[20]在標(biāo)量乘運(yùn)算層采用以 2、3、5為基的多基鏈法，并且引入最小值系數(shù)c1、c2、c3縮短基鏈長度，在群運(yùn)算層加入變量U去除Y3的冗余運(yùn)算，與完全平方變換相結(jié)合，使五倍點(diǎn)運(yùn)算的開銷降低到12M+13S。文獻(xiàn)[21]利用二元域下域運(yùn)算層求逆運(yùn)算消耗較小的特點(diǎn)，在群運(yùn)算層中使用仿射坐標(biāo)系，同時(shí)在標(biāo)量乘運(yùn)算層中加入半點(diǎn)進(jìn)行多基運(yùn)算，使系統(tǒng)整體效率相比其他通用算法提高了3.91%～45.16%。由于橢圓曲線密碼系統(tǒng)經(jīng)常應(yīng)用到一些計(jì)算能力較低的系統(tǒng)中，并且許多應(yīng)用場景無法被開銷較低的對稱加密所代替（如信用卡身份驗(yàn)證）。因此，提高橢圓曲線密碼系統(tǒng)的運(yùn)算效率顯得非常重要。運(yùn)算效率的提高意味著單片機(jī)系統(tǒng)可以運(yùn)行的密鑰長度更長，即安全性更高。此外，由于文獻(xiàn)[17,18]使用了特殊橢圓曲線，文獻(xiàn)[16,21]僅適用于二元域，因此應(yīng)用場景具有局限性。

針對上述問題，本文在保證安全性的前提下，通過對橢圓曲線密碼系統(tǒng)進(jìn)行分層優(yōu)化來提高橢圓曲線密碼系統(tǒng)的整體效率。該方案兼容二元域和素?cái)?shù)域，適用于任意橢圓曲線。針對群運(yùn)算層，本文提出基于偽四維坐標(biāo)的群運(yùn)算，通過在標(biāo)準(zhǔn)雅可比坐標(biāo)上引入新參數(shù)aZ4，使坐標(biāo)由(X,Y,Z)變?yōu)?X,Y,Z,aZ4)，實(shí)現(xiàn)對群運(yùn)算的優(yōu)化，并推導(dǎo)出基于偽四維投射坐標(biāo)的倍點(diǎn)運(yùn)算、三倍點(diǎn)運(yùn)算、五倍點(diǎn)運(yùn)算的計(jì)算式和算法。針對標(biāo)量乘運(yùn)算層，本文對多基鏈生成算法中的貪心策略進(jìn)行優(yōu)化，提出最短鏈存在定理，并由最短鏈存在定理推導(dǎo)出最短鏈表，得出160、192、256和384位密鑰中最小值系數(shù)c1、c2、c3的最優(yōu)值。在安全性方面，本文通過平衡能量法與Masking方法相結(jié)合的方式，可以成功抵御SPA和DPA等常見能量分析攻擊。

2 基礎(chǔ)知識與相關(guān)工作

2.1 有限域中的橢圓曲線

橢圓曲線密碼系統(tǒng)基于橢圓曲線的離散對數(shù)問題，通常使用有限域內(nèi)的曲線。一般最常用的有限域是素?cái)?shù)域GF(p)和二元域GF(2m)。素?cái)?shù)域兼容性較高，幾乎適用于所有橢圓曲線密碼系統(tǒng)的應(yīng)用，而在FPGA等單片機(jī)環(huán)境中，二元域有著較高的運(yùn)算效率。

在運(yùn)算效率方面，素?cái)?shù)域和二元域最大的區(qū)別在于域運(yùn)算中求逆運(yùn)算的效率。素?cái)?shù)域求逆運(yùn)算消耗大約相當(dāng)于 80～100次乘法運(yùn)算[18]，所以通常采用雅可比投射坐標(biāo)消除求逆運(yùn)算。而二元域求逆運(yùn)算效率相比素?cái)?shù)域有很大提高，消耗僅為 8～10次乘法運(yùn)算[21]，所以通常在群運(yùn)算層采用仿射坐標(biāo)，并且在標(biāo)量乘運(yùn)算層采用連續(xù)相同群運(yùn)算的方法（如雙基鏈或多基鏈法）以減少求逆運(yùn)算。

2.2 橢圓曲線密碼系統(tǒng)的層次結(jié)構(gòu)

橢圓曲線密碼系統(tǒng)可分為5層：物理層、域運(yùn)算層、群運(yùn)算層、標(biāo)量乘運(yùn)算層和應(yīng)用層，如圖 1所示，其中，上層運(yùn)算依賴于下層運(yùn)算，而下層運(yùn)算為上層運(yùn)算提供服務(wù)。

圖1 橢圓曲線密碼系統(tǒng)層次結(jié)構(gòu)

2.2.1 域運(yùn)算層

域運(yùn)算又稱原子運(yùn)算，是有限域上最基本的運(yùn)算，即模運(yùn)算。橢圓曲線密碼系統(tǒng)會用到5種基本的域運(yùn)算——加法、取負(fù)、平方、乘法、求逆。文獻(xiàn)[22]中指出在分析算法效率時(shí)，加法、取負(fù)運(yùn)算因?yàn)檫\(yùn)算消耗相較其余3種運(yùn)算微乎其微，基本可以忽略，所以在分析效率時(shí)只需討論平方、乘法、求逆的運(yùn)算次數(shù)。

2.2.2 群運(yùn)算層

橢圓曲線在素?cái)?shù)域上的點(diǎn)可以組成一個(gè)循環(huán)群。對于橢圓曲線上的任意兩點(diǎn)，一定存在該橢圓曲線上的第三點(diǎn)為兩點(diǎn)之和。圖2描繪了橢圓曲線群運(yùn)算的幾何意義。

定義 1 如果橢圓曲線上三點(diǎn)共線，則它們的和為O，其幾何意義是無窮遠(yuǎn)點(diǎn)[22]。

由定義1可以推導(dǎo)出橢圓曲線上的加法定律。1)O為加法單位元，即P+O=O+P=P。

2) 設(shè)R1=(x,y)是橢圓曲線上的點(diǎn)，根據(jù)x軸對稱性可知，R2=(x,?y)也是橢圓曲線上的點(diǎn)，可以看作R1、R2與無窮遠(yuǎn)點(diǎn)三點(diǎn)共線，所以R1+R2+O=O，即R1=?R2。

3) 通過1)和2)可以看出，若橢圓曲線上P、Q、R三點(diǎn)共線，則橢圓曲線上相異兩點(diǎn)P、Q之和為?R，即P+Q=?R，幾何意義如圖2(a)所示。

4) 將3)中的Q無限逼近P，當(dāng)P、Q重合時(shí)，直線PR為橢圓曲線上的切線，即2P=?R，幾何意義如圖2(b)所示。

圖2 橢圓曲線群運(yùn)算幾何意義示意

上述3)和4)構(gòu)成了橢圓曲線群上的2個(gè)基本運(yùn)算：點(diǎn)加和倍點(diǎn)。

2.2.3 標(biāo)量乘運(yùn)算層

標(biāo)量乘運(yùn)算是橢圓曲線密碼系統(tǒng)最主要且消耗能量最大的運(yùn)算。橢圓曲線的基本群運(yùn)算只有點(diǎn)加和倍點(diǎn)。如果要實(shí)現(xiàn)乘法運(yùn)算，必須將乘法運(yùn)算轉(zhuǎn)換為點(diǎn)加和倍點(diǎn)的組合。橢圓曲線密碼系統(tǒng)常見的標(biāo)量乘法有D&A法[17]、NAF法[23]、蒙哥馬利階梯法[16,18]、雙基鏈標(biāo)量乘法[19]和多基鏈標(biāo)量乘法[14,20]。多基鏈標(biāo)量乘法的原理如式(1)所示。

其中，為基的個(gè)數(shù)，n為鏈長，{bj}為單調(diào)遞減數(shù)列。

從式(1)可以看出，在橢圓曲線標(biāo)量乘法中，使用多基鏈法計(jì)算kP，只需依次進(jìn)行bj次aj倍點(diǎn)運(yùn)算，然后再進(jìn)行n次點(diǎn)加，即可求出點(diǎn)Q。由此可知，多基鏈標(biāo)量乘法的優(yōu)化原則為：

1) 盡可能提高aj倍點(diǎn)的運(yùn)算效率；2)b1盡可能??；

3) 鏈長n盡可能短。

針對上述原則，本文通過基于偽四維投射坐標(biāo)的快速群運(yùn)算和基于偽四維投射坐標(biāo)的多基鏈標(biāo)量乘法，對橢圓曲線密碼系統(tǒng)進(jìn)行分層優(yōu)化。

2.2.4 應(yīng)用層

應(yīng)用層搭載著基于橢圓曲線密碼系統(tǒng)的眾多應(yīng)用，如基于橢圓曲線的密鑰交換和基于橢圓曲線的數(shù)字簽名等，這些都是橢圓曲線密碼系統(tǒng)的經(jīng)典應(yīng)用。

3 基于偽四維投射坐標(biāo)的快速群運(yùn)算

3.1 偽四維投射坐標(biāo)的建立

在2.1節(jié)中，群運(yùn)算的優(yōu)化原則是去除求逆運(yùn)算，盡量減少乘法運(yùn)算，平方運(yùn)算可以適當(dāng)增加。雅可比投射坐標(biāo)相比仿射坐標(biāo)增加了一個(gè)維度，將二維變?yōu)槿S，從而達(dá)到優(yōu)化運(yùn)算的目的。由于雅可比坐標(biāo)下的倍點(diǎn)、三倍點(diǎn)和五倍點(diǎn)計(jì)算式中有多個(gè)aZ4，若可以將aZ4通過變換獲得，則可以進(jìn)一步優(yōu)化倍點(diǎn)的效率。偽四維投射坐標(biāo)正是利用該原理，在雅可比投射坐標(biāo)上加一個(gè)維度參數(shù)aZ4，由(X,Y,Z)變?yōu)?X,Y,Z,aZ4)。由于坐標(biāo)中第三個(gè)和第四個(gè)參數(shù)并不獨(dú)立，因此它不是真正的四維坐標(biāo)，本文將其稱為“偽四維”。

文獻(xiàn)[15]在改進(jìn)雅可比坐標(biāo)的基礎(chǔ)上提出了一種基于側(cè)信道原子法的群運(yùn)算。該方法通過將群運(yùn)算拆分為若干個(gè)擁有相同的運(yùn)算順序和結(jié)構(gòu)的運(yùn)算單元，達(dá)到抵御SPA的目的。而本文在標(biāo)量乘運(yùn)算層中使用平衡能量法和Masking方法抵御SPA和DPA，因此在群運(yùn)算層不需要考慮側(cè)信道攻擊，使群運(yùn)算效率得到進(jìn)一步提升。此外，基于偽四維投射坐標(biāo)的群運(yùn)算并沒有用到特殊曲線（如NIST曲線[17]、MoTE曲線[18]和Edwards曲線[19]）的性質(zhì)，所以適用于所有的橢圓曲線。5.1節(jié)群運(yùn)算效率分析實(shí)驗(yàn)表明，偽四維投射坐標(biāo)在素?cái)?shù)域和二元域下的性能均高于對照算法，所以適用于二元域和素?cái)?shù)域，具有良好的兼容性。

3.2 基于偽四維坐標(biāo)的倍點(diǎn)運(yùn)算

其中，

算法1 基于偽四維坐標(biāo)的倍點(diǎn)運(yùn)算

輸入

輸出

初始化

1)

返回由算法1可以得出，基于偽四維坐標(biāo)的倍點(diǎn)運(yùn)算需要的域操作數(shù)為3M+5S。

3.3 基于偽四維坐標(biāo)的三倍點(diǎn)運(yùn)算

其中，

算法2 基于偽四維坐標(biāo)的三倍點(diǎn)運(yùn)算

輸入

輸出

初始化

1)

2)

3)

4)

返回

由算法2可以得出，基于偽四維坐標(biāo)的三倍點(diǎn)運(yùn)算需要的域操作數(shù)為7M+7S。

3.4 基于偽四維坐標(biāo)的五倍點(diǎn)運(yùn)算

其中，

根據(jù)式(4)，可以得出如圖3所示的偽四維投射坐標(biāo)五倍點(diǎn)運(yùn)算的域運(yùn)算示意。其中，表示加法，表示自取負(fù)表示平方，表示乘法。圖 3從輸入最 后 從輸 出由圖3可以計(jì)算出基于偽四維

投射坐標(biāo)的五倍點(diǎn)運(yùn)算需要的域操作數(shù)為11M+12S。

圖3 偽四維投射坐標(biāo)五倍點(diǎn)運(yùn)算的域運(yùn)算示意

4 基于偽四維投射坐標(biāo)的多基鏈標(biāo)量乘法

4.1 多基鏈生成算法的優(yōu)化策略

文獻(xiàn)[20] 提出了一種以2、3、5為基的多基鏈生成算法，將大整數(shù)k化為以2、3、5為基的和，即。若保證{bin}、{tri}和{pen}為單調(diào)遞減數(shù)列，則可以提取公因式，簡化計(jì)算。具體實(shí)現(xiàn)過程如算法3多基鏈生成算法[20]所示。

算法3 多基鏈生成算法

輸入 大整數(shù)k，倍點(diǎn)最大值maxb，三倍點(diǎn)最大值maxt，五倍點(diǎn)最大值maxq，最小值系數(shù)c1,c2,c3

輸出

1) if maxb=0&&maxt=0&&maxq=0then

2) returnk

3) end if

4)bin= maxb×c1

5)tri= maxt×c2

6)pen= maxq×c3

7) 通過貪心算法找到最合適的整數(shù)| |k?num和bin、tri、pen

8) ifk＞numthen

9)si=1

10) else

11)si=?1

12) end if

13) ifnum＞0 then

14)多基鏈生成算法(|k?num|,bin,tri,pen,c1,c2,c3)

15) end if

16) returnk

算法3中設(shè)置了倍點(diǎn)、三倍點(diǎn)和五倍點(diǎn)的最大值，并且每一次都將求出來的倍點(diǎn)、三倍點(diǎn)和五倍點(diǎn)個(gè)數(shù)代入下一次遞歸，保證多基鏈?zhǔn)沁f減的，方便接下來的標(biāo)量乘運(yùn)算。此外，為了防止基鏈過于冗長，算法 3引入了最小值系數(shù)c1、c2、c3來限制倍點(diǎn)、三倍點(diǎn)和五倍點(diǎn)個(gè)數(shù)的最小值來提高標(biāo)量乘算法的運(yùn)算效率。其數(shù)學(xué)模型如式(5)所示。

已知

求min(|A?axbycz|)以及此時(shí)滿足條件x、y、z的取值。其中，a,b,c∈N*為基，minbin,mintri,minpen,maxbin,maxtri,maxpen為已知常數(shù)。

可以看出，該策略保證了在文獻(xiàn)[20]的約束條件下，其多基鏈的鏈頭最大。然而，由于倍點(diǎn)、三倍點(diǎn)以及五倍點(diǎn)的群運(yùn)算開銷不同，所以鏈頭最大并不能保證整個(gè)系統(tǒng)的開銷最小。同時(shí)，若要實(shí)現(xiàn)算法3，關(guān)鍵在于如何求得min(|A?axbycz|)以及x、y、z的值，但文獻(xiàn)[20,21]均沒有提及相應(yīng)方法。如果采用枚舉法實(shí)現(xiàn)該算法，則時(shí)間復(fù)雜度為O(n× maxbin× maxtri× maxpen)，且大整數(shù)乘方運(yùn)算相當(dāng)復(fù)雜，所以該運(yùn)算會消耗大量的運(yùn)算資源。文獻(xiàn)[24]提出使用圖結(jié)構(gòu)解決雙基鏈的貪心算法問題。為了在雙基鏈中找到最合適的|k?num|，對應(yīng)算法3第7行的時(shí)間復(fù)雜度為O((logn)2)。如果應(yīng)用到多基鏈中，則算法3的時(shí)間復(fù)雜度為O(n(logn)3)。雖然該方法比枚舉法的時(shí)間復(fù)雜度明顯降低，但由于大整數(shù)運(yùn)算非常復(fù)雜，所以該時(shí)間復(fù)雜度仍然不夠理想。

針對以上問題，本文使用拉格朗日乘數(shù)法建立數(shù)學(xué)模型并對算法3中的貪心算法進(jìn)行優(yōu)化，找到最合適的倍點(diǎn)、三倍點(diǎn)和五倍點(diǎn)個(gè)數(shù)。首先，給出數(shù)學(xué)模型如下。

已知

求min

其 中 ，c1、c2、c3為 (0,1)的 已 知 常 數(shù) ，minbin,mintri, minpen,maxbin,maxtri, maxpen也為已知常數(shù)。根據(jù)拉格朗日乘數(shù)法，得到拉格朗日方程組為

將相關(guān)約束條件加上，若l、m、n超出取值范圍，則取其范圍內(nèi)的最值；若l、m、n在取值范圍內(nèi)，則分別將l、m、n進(jìn)行上下取整，最多可以得到=20種組合，并選擇min(Costbinx+Costtriy+Costpenz)為最終取值。

上述優(yōu)化將原本以鏈頭大小為優(yōu)先的貪心策略變?yōu)橐蚤_銷為優(yōu)先的貪心策略，使系統(tǒng)整體開銷減小。理論上，通過建立基于拉格朗日乘數(shù)法的優(yōu)化策略，可以將多基鏈生成算法的時(shí)間復(fù)雜度降為O(n)，提高了系統(tǒng)的整體效率。

4.2 最短鏈存在定理和最短鏈表

在本文提出的多基鏈生成算法的優(yōu)化策略中，用到了最小值系數(shù)c1、c2、c3。本節(jié)將通過最短鏈存在定理證明調(diào)整最小值系數(shù)c1、c2、c3可以使鏈長最短。此外，通過運(yùn)算給出常見密鑰位數(shù)的最短鏈長以及最小值系數(shù)c1、c2、c3的取值，在實(shí)際應(yīng)用中可以通過該表快速獲取最適合的最小值系數(shù)c1、c2、c3。

4.2.1 最短鏈存在定理

定理 1 以 2、3、5為底的多基鏈，?c1,c2,c3∈ (0,1)，使多基鏈的鏈長最短。

證明 根據(jù)算法3，可以將定理1抽象為函數(shù)

由于通過算法3的貪心算法可以找到最適合的bin、tri、pen，所以一定?x=c，使g'(x) = 0；根據(jù)對稱性，y、z同理。所以，多元函數(shù)g(x,y,z)一定存在駐點(diǎn)，即證畢。

4.2.2 最短鏈表

定理1證明了最短鏈的存在，并且證明了最短鏈的三重極限可化為累次極限，所以可以通過計(jì)算機(jī)進(jìn)行無限逼近求得當(dāng)鏈長達(dá)到最短極限的c1、c2、c3，得到如表1所示的最短鏈表。

表1 最短鏈表

4.3 基于偽四維投射坐標(biāo)的多基鏈標(biāo)量乘法

算法4詳細(xì)描述了本文提出的基于偽四維投射坐標(biāo)的多基鏈標(biāo)量乘法。

算法4 基于偽四維投射坐標(biāo)的多基鏈標(biāo)量乘法

輸入 整數(shù)bin1≥bin2≥…≥binm≥0，tri1≥tri2≥…≥trim≥0，pen1≥pen2≥ …≥penm≥ 0；基點(diǎn)P∈E(Fp)。

輸出Q=kP∈E(Fp)

1)R←random()//生成E(Fp)上的隨機(jī)點(diǎn)

2)Q←基于雅克比坐標(biāo)點(diǎn)加(P,R)

3)Q'←Q

4)u←binm

5)v←trim

6)w←penm

7) fori=m?1 to 1 do

8) forj=1 towdo

9)Q'←基于偽四維坐標(biāo)五倍點(diǎn)(Q')

10) end for

11) fork=1 tovdo

12)Q'←基于偽四維坐標(biāo)三倍點(diǎn)(Q')

13) end for

14) forl=1 toudo

15)Q'←基于偽四維坐標(biāo)倍點(diǎn)(Q')

16) end for

17)Q''← 求逆(Q')

18) ifsm?i+1= 1 then

19)Q←基于雅克比坐標(biāo)點(diǎn)加(Q,Q')

20) else

21)Q←基于雅克比坐標(biāo)點(diǎn)加(Q,Q'')

22) end if

23)u←bini?bini?1

24)v←trii?trii?1

25)w←peni?peni?1

26) end for

27)R← 求逆(R)

28)P←基于雅克比坐標(biāo)點(diǎn)加(Q,R)

29) returnP

在算法4中，由于多基鏈中每一個(gè)節(jié)點(diǎn)的次數(shù)都是單調(diào)遞減的，所以可以保證整個(gè)算法的倍點(diǎn)、三倍點(diǎn)和五倍點(diǎn)個(gè)數(shù)為bin1、tri1和pen1。此外，倍點(diǎn)、三倍點(diǎn)和五倍點(diǎn)運(yùn)算采用偽四維投射坐標(biāo)，點(diǎn)加運(yùn)算采用雅可比坐標(biāo)。為了抵御DPA攻擊，算法4對基點(diǎn)P采用Masking方法進(jìn)行了處理：在算法的第1行和第2行將基點(diǎn)P加上隨機(jī)點(diǎn)R，然后在算法 4的第 27行和第 28行將結(jié)果還原，即kP= (kP+R)?R。由于這里的R是隨機(jī)的，每次運(yùn)行的能量分析曲線也是隨機(jī)的，無法進(jìn)行DPA攻擊。為了抵御SPA攻擊，算法4的第17行先計(jì)算Q''，從而在第 18～第 22行中，無論sk= 1或sk=?1，都進(jìn)行一次點(diǎn)加，使能量平衡，攻擊者無法通過波形獲取si的取值，從而達(dá)到抵御SPA攻擊的目的。

5 系統(tǒng)效率分析與實(shí)驗(yàn)

5.1 群運(yùn)算效率分析

橢圓曲線群運(yùn)算作為標(biāo)量乘運(yùn)算的底層，對系統(tǒng)效率起到了決定性作用。本節(jié)將基于偽四維投射坐標(biāo)的群運(yùn)算效率與其他算法進(jìn)行對比，結(jié)果如表2所示。其中，N/A表示文獻(xiàn)中沒有涉及，I表示求逆運(yùn)算。

表2 群運(yùn)算效率比較

5.1.1 離散群運(yùn)算效率比較

文獻(xiàn)[18]指出，素?cái)?shù)域中求逆運(yùn)算的消耗非常大，當(dāng)密鑰長度為 160位時(shí)，其運(yùn)算開銷為11M+158S。所以使用雅可比投射坐標(biāo)消除求逆運(yùn)算是基于素?cái)?shù)域的橢圓曲線密碼系統(tǒng)的主流做法。文獻(xiàn)[17, 19, 20]以及偽四維投射坐標(biāo)均為雅可比投射坐標(biāo)的進(jìn)一步優(yōu)化。

文獻(xiàn)[14]指出，素?cái)?shù)域中的平方運(yùn)算與乘法運(yùn)算開銷的比值S/M為0.8，由表2可以看出，對比標(biāo)準(zhǔn)雅可比投射坐標(biāo)，偽四維投射坐標(biāo)倍點(diǎn)運(yùn)算的開銷降低了 26.67%，三倍點(diǎn)運(yùn)算的開銷降低了21.43%，五倍點(diǎn)運(yùn)算的開銷降低了15.38%。

相比其他算法，對于倍點(diǎn)和三倍點(diǎn)運(yùn)算，對照表2中開銷最小的文獻(xiàn)[19]，偽四維投射坐標(biāo)比文獻(xiàn)[19]倍點(diǎn)運(yùn)算開銷降低了 5.71%，三倍點(diǎn)運(yùn)算開銷降低了3.17%；對于五倍點(diǎn)運(yùn)算，對比表2中開銷最小的文獻(xiàn)[20]，偽四維投射坐標(biāo)比文獻(xiàn)[20]五倍點(diǎn)運(yùn)算開銷降低了8.74%。

5.1.2 連續(xù)群運(yùn)算效率比較

二元域中的求逆運(yùn)算較素?cái)?shù)域的求逆運(yùn)算有較大優(yōu)勢，其求逆運(yùn)算的開銷從素?cái)?shù)域中80～100次乘法減少為 8～10次乘法，開銷降低了10倍[21]，并且在文獻(xiàn)[21]的多基鏈運(yùn)算中，連續(xù)的倍點(diǎn)、三倍點(diǎn)和五倍點(diǎn)運(yùn)算較多，群運(yùn)算可以進(jìn)一步簡化，所以文獻(xiàn)[21]使用了仿射坐標(biāo)而非雅可比坐標(biāo)。從表2中不難看出，k越大，文獻(xiàn)[21]的群運(yùn)算效率越高。圖 4刻畫了隨著k增大文獻(xiàn)[21]的仿射坐標(biāo)和本文偽四維投射坐標(biāo)群運(yùn)算效率的對比效果。

如圖4(a)所示，在三倍點(diǎn)運(yùn)算中，偽四維投射坐標(biāo)的運(yùn)算開銷均低于仿射坐標(biāo)，并且當(dāng)k增大時(shí)，優(yōu)勢更為明顯。當(dāng)密鑰長度為160位時(shí)，根據(jù)實(shí)驗(yàn)樣本統(tǒng)計(jì)，k的數(shù)學(xué)期望= 15.771，所以根據(jù)表2，在仿射坐標(biāo)下的期望開銷= 240.794，而在偽四維投射坐標(biāo)下的期望開銷= 176.635。由此可得，在二元域中偽四維投射坐標(biāo)下的三倍點(diǎn)運(yùn)算比仿射坐標(biāo)下的三倍點(diǎn)運(yùn)算開銷降低了36.32%。同理，如圖4(b)所示，在五倍點(diǎn)運(yùn)算中，雖然從圖4中偽四維投射坐標(biāo)看似優(yōu)勢并不明顯，但密鑰長度為160位時(shí)，k的數(shù)學(xué)期望= 5.738，根據(jù)表2中文獻(xiàn)[21]的連續(xù)五倍點(diǎn)式，在仿射坐標(biāo)下的期望開銷= 122.622，而在偽四維投射坐標(biāo)下的期望開銷= 104.432。由此可得，在二元域中偽四維投射坐標(biāo)下的五倍點(diǎn)運(yùn)算比仿射坐標(biāo)下的五倍點(diǎn)運(yùn)算開銷降低了17.42%。

圖4 二元域群運(yùn)算開銷比較

5.2 系統(tǒng)總開銷分析

通過對橢圓曲線密碼系統(tǒng)層次結(jié)構(gòu)的分析，本文優(yōu)化了群運(yùn)算層和標(biāo)量乘運(yùn)算層，實(shí)現(xiàn)了系統(tǒng)整體效率的提升。表3就本文算法的系統(tǒng)總開銷（換算為乘法運(yùn)算次數(shù)）與對照算法的系統(tǒng)總開銷進(jìn)行了對比。由于本文所提的偽四維投射坐標(biāo)向下兼容雅可比坐標(biāo)（將aZ4舍去即可），可以計(jì)算出本文算法中一次點(diǎn)加運(yùn)算的開銷為7M+4S。此外，為了讓對比更為公正客觀，所有算法均未使用任何預(yù)計(jì)算。

表3 系統(tǒng)總開銷比較

由表3可知，當(dāng)密鑰長度為160位時(shí)，本文算法的總開銷比文獻(xiàn)[14]降低了 57.79%，比文獻(xiàn)[13]降低了36.09%，比文獻(xiàn)[17]降低了26.82%，比文獻(xiàn)[16]降低了23.32%，比文獻(xiàn)[15]降低了12.94%，比文獻(xiàn)[18]降低了8.70%。此外，文獻(xiàn)[18]的算法只能運(yùn)用于二元域，其余算法既可以運(yùn)用于二元域，也可以運(yùn)用于素?cái)?shù)域。

5.3 能量分析攻擊實(shí)驗(yàn)

5.3.1 實(shí)驗(yàn)環(huán)境搭建

本實(shí)驗(yàn)采用NewAE公司的Chipwhisperer-Lite實(shí)驗(yàn)平臺[25]。該實(shí)驗(yàn)平臺由2個(gè)部分組成：一部分為XMEGA開發(fā)板，供開發(fā)者編程；另一部分為采樣器，可以采樣開發(fā)板運(yùn)行時(shí)的能量消耗波形。通過該實(shí)驗(yàn)工具能清楚分析出算法遭受能量分析攻擊的情況。圖5為Chipwhisperer-Lite實(shí)驗(yàn)平臺的體系結(jié)構(gòu)示意。5.3.2 抵御SPA攻擊

圖5 Chipwhisperer-Lite實(shí)驗(yàn)平臺的體系結(jié)構(gòu)示意

由于不同的操作，處理器在不同時(shí)序上的能量消耗會體現(xiàn)出差異性。攻擊者通過觀察設(shè)備在進(jìn)行加密運(yùn)算的能量功耗曲線，對能量功耗曲線進(jìn)行直觀分析，找到能量功耗與操作的關(guān)系，達(dá)到獲取密鑰的目的。從算法4可以看出，標(biāo)量乘運(yùn)算每一次大循環(huán)都會經(jīng)過連續(xù)五倍點(diǎn)運(yùn)算、連續(xù)三倍點(diǎn)運(yùn)算，再連續(xù)倍點(diǎn)運(yùn)算，然后經(jīng)過點(diǎn)加及相關(guān)其他域操作進(jìn)入下一次大循環(huán)。為了檢測算法4是否可以抵御SPA攻擊，本文首先輸入160位的私鑰為

根據(jù)式(8)的輸入，在標(biāo)量乘運(yùn)算的過程中，采樣器會采集運(yùn)算時(shí)的能量消耗曲線。圖6描繪了采用平衡能量法前后能量波形對比。由于Chipwhisperer-Lite采樣范圍為26 000個(gè)時(shí)鐘周期，本文截取第一次循環(huán)結(jié)束至第二次循環(huán)開始的能量波形，如圖6(a)所示。其中，左邊虛線框?yàn)楸饵c(diǎn)操作，中間點(diǎn)線框?yàn)辄c(diǎn)加及相關(guān)域操作，右邊實(shí)線框?yàn)槲灞饵c(diǎn)操作。

圖6 采用平衡能量法前后能量波形對比

從圖6(a)可以看出，相同的域操作雖然會由于操作數(shù)不同及噪聲干擾，其振幅會有少許區(qū)別，但高低電位基本以周期的形式出現(xiàn)，從虛線框和實(shí)線框部分很容易看出倍點(diǎn)和五倍點(diǎn)操作的界限。將圖6(a)中點(diǎn)線框部分放大得到圖6(b)，由于在算法4中si∈ {1,? 1}，所以當(dāng)sk=?1時(shí)，則會進(jìn)行一次求逆運(yùn)算。由于求逆操作開銷極小（此處的求逆為2.2.2節(jié)中的群運(yùn)算求逆，不是2.2.1節(jié)中開銷極大的域運(yùn)算求逆），幾乎可以忽略不計(jì)，在圖6(b)中也不明顯。再將圖6(b)放大得到圖6(c)，圖 6(c)中實(shí)線框標(biāo)出的波形即一次求逆操作。而根據(jù)算法 3，上述k得到的sk=1，并不需要求逆運(yùn)算。所以如果沒有采用平衡能量法，其波形如圖6(d)所示，攻擊者即可通過波形差異獲得si的取值。而使用平衡能量法，則每一次點(diǎn)加之前都會出現(xiàn)一次求逆操作，使攻擊者無法通過能量波形獲取si的取值，即無法從能量曲線直觀地獲取私鑰信息。

5.3.3 抵御DPA攻擊

DPA攻擊的原理與SPA攻擊的原理類似，不同的是它采用大量樣本經(jīng)過糾錯(cuò)技術(shù)和統(tǒng)計(jì)方法，通過樣本之間的細(xì)微差別獲取密鑰信息。與SPA不同的是，DPA攻擊并不需要了解密碼系統(tǒng)實(shí)現(xiàn)的具體細(xì)節(jié)，并且對信噪比的要求比 SPA低。所以 DPA是目前能量分析攻擊中最強(qiáng)大的一種。抵御差分能量分析攻擊旨在利用隨機(jī)策略，使攻擊者無法通過多次運(yùn)行獲得統(tǒng)計(jì)數(shù)據(jù)。

本文采用Masking方法抵御DPA攻擊。采用Masking方法與未采用Masking方法的能量波形對比如圖7所示。

圖7 采用Masking方法前后能量波形對比

圖 7(a)描繪了未采用Masking方法的多次運(yùn)行能量波形?？梢钥闯觯恳淮芜\(yùn)行的波形差別微乎其微，曲線重合度很高，給DPA攻擊提供了條件。采用 Masking方法之后，其多次運(yùn)行的能量波形如圖 7(b)所示。由于每次標(biāo)量乘運(yùn)算之前基點(diǎn)都加上了一個(gè)隨機(jī)點(diǎn)，其能量波形無論在幅度和相位上都有差異，攻擊者無法通過DPA攻擊來獲取密鑰信息。

6 結(jié)束語

本文建立了基于偽四維投射坐標(biāo)的快速群運(yùn)算并推導(dǎo)出基于偽四維投射坐標(biāo)的多基鏈標(biāo)量乘法，在群運(yùn)算層和標(biāo)量乘運(yùn)算層對橢圓曲線密碼系統(tǒng)進(jìn)行了優(yōu)化。為了對多基鏈生成算法進(jìn)行優(yōu)化，建立了基于拉格朗日乘數(shù)法的貪心策略，提出最短鏈存在定理并推導(dǎo)出最短鏈表。能量分析攻擊實(shí)驗(yàn)表明，本文提出的分層優(yōu)化策略可以有效地提高橢圓曲線密碼系統(tǒng)的整體性能，并可抵御常見的能量分析攻擊。

[1] RIVEST R, SHAMIR A, ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1983, 26(1)∶ 96-99.

[2] KOBLITZ N. Elliptic curve cryptosystems[J]. Mathematics of Computation, 1987, 48(48)∶ 203-209.

[3] MILLER V. Use of elliptic curves in cryptography[J]. Lecture Notes in Computer Science, 1985, 218(1)∶ 417-426.

[4] SAQIB N. Key exchange protocol for WSN resilient against man in the middle attack[C]//IEEE International Conference on Advances in Computer Applications. 2017∶ 265-269.

[5] YEH H L, CHEN T H, SHIH W K. Robust smart card secured authentication scheme on SIP using elliptic curve cryptography[J]. Computer Standards &Interfaces, 2014, 36(2)∶ 397-402.

[6] SHENTU Q C, YU J P. A blind-mixing scheme for bitcoin based on an elliptic curve cryptography blind digital signature algorithm[J]. Computer Science, 2015∶ 1-17.

[7] GUERON S, KRASNOV V. Fast prime field elliptic-curve cryptography with 256-bit primes[J]. Journal of Cryptographic Engineering,2015, 5(2)∶ 141-151.

[8] IZU T, TAKAGI T. Exceptional procedure attack on elliptic curve cryptosystems[C]//International Workshop on Public Key Cryptography-pkc.2003∶ 224-239.

[9] MATHER L, OSWALD E. Pinpointing side-channel information leaks in Web applications[J]. Journal of Cryptographic Engineering, 2012,2(3)∶ 161-177.

[10] KOCHER P. Timing attacks on implementations of Diffie-Hellman,RSA, DSS, and other system[C]//International Cryptology Conference on Advances in Cryptology.1996∶ 104-113.

[11] MESSERGES T. Using second-order power analysis to attack DPA resistant software[J]. Springer Berlin Heidelberg, 2000, 1965∶238-251.

[12] 王敏, 吳震. 抗SPA攻擊的橢圓曲線NAF標(biāo)量乘實(shí)現(xiàn)算法[J]. 通信學(xué)報(bào), 2012, 33(S1)∶ 228-232.WANG M, WU Z. Algorithm of NAF scalar multiplication on ECC against SPA[J]. Journal on Communications, 2012, 33(S1)∶ 228-232.

[13] MAMIYA H, MIYAJI A, MORIMOTO H. Efficient countermeasures against RPA, DPA, and SPA[J]. Springer Berlin Heidelberg, 2014,3156∶ 343-356.

[14] MISHRA P, DIMITROV V. Efficient quintuple formulas for elliptic curves and efficient scalar multiplication using multibase number representation[C]//International Conference on Information Security.2007∶390-406.

[15] DANGER J, GUILLEY S, HOOGVORST P, et al. Improving the big mac attack on elliptic curve cryptography[J]. Springer Berlin Heidelberg, 2016∶ 374-386.

[16] LI L, LI S. High-performance pipelined architecture of elliptic curve scalar multiplication over GF(2m)[J]. IEEE Transactions on Very Large Scale Integration Systems, 2016, 24(4)∶ 1223-1232.

[17] DUBEUF J, HELY D, BEROULLE V. ECDSA passive attacks, leakage sources, and common design mistakes[J]. ACM Transactions on Design Automation of Electronic Systems, 2016, 21(2)∶ 1-24.

[18] LIU Z, HUANG X, HU Z, et al. On emerging family of elliptic curves to secure Internet of Things∶ ECC comes of age[J]. IEEE Transactions on Dependable & Secure Computing, 2017, 14(3)∶ 237-248.

[19] MELONI N, HASAN M. Efficient double bases for scalar multiplication[J]. IEEE Transactions on Computers, 2015, 64 (8)∶ 2204-2212.

[20] CHO S, GWAL S, CHANG H K, et al. Faster elliptic curve arithmetic for triple-base chain by reordering sequences of field operations[J].Multimedia Tools &Applications, 2016∶ 1-13.

[21] PUROHIT G, RAWAT A. Elliptic curve point multiplication using MBNR and point halving[J]. International Journal of Advanced Networking & Applications, 2012∶ 1329-1337.

[22] PAAR C, PELZL J. Understanding cryptography[J]. Springer Berlin Heidelberg, 2010∶ 519-551.

[23] HASAN AE, REYHANIMASOLEH A. New regular radix-8 scheme for elliptic curve scalar multiplication without pre-computation[J].IEEE Transactions on Computers, 2013, 64(2)∶ 438-451.

[24] BERNSTEIN D, CHUENGSATIANSUP C, LANGE T. Double-base scalar multiplication revisited[R]. IACR Cryptology ePrint Archive,2017∶ 1-38.

[25] O’FLYNN C, CHEN Z. ChipWhisperer∶ an open-source platform for hardware embedded security research[C]// International Workshop on Constructive Side-Channel Analysis and Secure Design. 2014∶243-260.