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

徐明，史量

（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）。近年來，隨著分布式計算以及量子技術(shù)的日趨成熟，對密碼系統(tǒng)的安全性要求也急劇提升，導(dǎo)致 RSA密鑰長度隨著保密性提高而迅速增長的缺點被不斷放大。這使密鑰長度較短的橢圓曲線密碼系統(tǒng)的應(yīng)用領(lǐng)域越來越廣，在無線傳感器網(wǎng)絡(luò)[4]、智能芯片卡[5]以及虛擬貨幣[6]的加密中都有比較成熟的應(yīng)用。美國國家安全局建議，384位橢圓曲線密碼系統(tǒng)足以保護(hù)美國軍方最高機密[7]。

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

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

針對上述問題，本文在保證安全性的前提下，通過對橢圓曲線密碼系統(tǒng)進(jìn)行分層優(yōu)化來提高橢圓曲線密碼系統(tǒng)的整體效率。該方案兼容二元域和素數(shù)域，適用于任意橢圓曲線。針對群運算層，本文提出基于偽四維坐標(biāo)的群運算，通過在標(biāo)準(zhǔn)雅可比坐標(biāo)上引入新參數(shù)aZ4，使坐標(biāo)由(X,Y,Z)變?yōu)?X,Y,Z,aZ4)，實現(xiàn)對群運算的優(yōu)化，并推導(dǎo)出基于偽四維投射坐標(biāo)的倍點運算、三倍點運算、五倍點運算的計算式和算法。針對標(biāo)量乘運算層，本文對多基鏈生成算法中的貪心策略進(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)的曲線。一般最常用的有限域是素數(shù)域GF(p)和二元域GF(2m)。素數(shù)域兼容性較高，幾乎適用于所有橢圓曲線密碼系統(tǒng)的應(yīng)用，而在FPGA等單片機環(huán)境中，二元域有著較高的運算效率。

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

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

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

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

2.2.1 域運算層

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

2.2.2 群運算層

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

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

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

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

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

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

圖2 橢圓曲線群運算幾何意義示意

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

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

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

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

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

1) 盡可能提高aj倍點的運算效率；2)b1盡可能小；

3) 鏈長n盡可能短。

針對上述原則，本文通過基于偽四維投射坐標(biāo)的快速群運算和基于偽四維投射坐標(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)的快速群運算

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

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

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

3.2 基于偽四維坐標(biāo)的倍點運算

其中，

算法1 基于偽四維坐標(biāo)的倍點運算

輸入

輸出

初始化

1)

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

3.3 基于偽四維坐標(biāo)的三倍點運算

其中，

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

輸入

輸出

初始化

1)

2)

3)

4)

返回

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

3.4 基于偽四維坐標(biāo)的五倍點運算

其中，

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

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

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

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ù)列，則可以提取公因式，簡化計算。具體實現(xiàn)過程如算法3多基鏈生成算法[20]所示。

算法3 多基鏈生成算法

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

已知

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

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

針對以上問題，本文使用拉格朗日乘數(shù)法建立數(shù)學(xué)模型并對算法3中的貪心算法進(jìn)行優(yōu)化，找到最合適的倍點、三倍點和五倍點個數(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)化策略，可以將多基鏈生成算法的時間復(fù)雜度降為O(n)，提高了系統(tǒng)的整體效率。

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

在本文提出的多基鏈生成算法的優(yōu)化策略中，用到了最小值系數(shù)c1、c2、c3。本節(jié)將通過最短鏈存在定理證明調(diào)整最小值系數(shù)c1、c2、c3可以使鏈長最短。此外，通過運算給出常見密鑰位數(shù)的最短鏈長以及最小值系數(shù)c1、c2、c3的取值，在實際應(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)一定存在駐點，即證畢。

4.2.2 最短鏈表

定理1證明了最短鏈的存在，并且證明了最短鏈的三重極限可化為累次極限，所以可以通過計算機進(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；基點P∈E(Fp)。

輸出Q=kP∈E(Fp)

1)R←random()//生成E(Fp)上的隨機點

2)Q←基于雅克比坐標(biāo)點加(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)五倍點(Q')

10) end for

11) fork=1 tovdo

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

13) end for

14) forl=1 toudo

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

16) end for

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

18) ifsm?i+1= 1 then

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

20) else

21)Q←基于雅克比坐標(biāo)點加(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)點加(Q,R)

29) returnP

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

5 系統(tǒng)效率分析與實驗

5.1 群運算效率分析

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

表2 群運算效率比較

5.1.1 離散群運算效率比較

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

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

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

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

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

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

圖4 二元域群運算開銷比較

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

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

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

由表3可知，當(dāng)密鑰長度為160位時，本文算法的總開銷比文獻(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]的算法只能運用于二元域，其余算法既可以運用于二元域，也可以運用于素數(shù)域。

5.3 能量分析攻擊實驗

5.3.1 實驗環(huán)境搭建

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

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

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

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

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

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

5.3.3 抵御DPA攻擊

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

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

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

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

6 結(jié)束語

本文建立了基于偽四維投射坐標(biāo)的快速群運算并推導(dǎo)出基于偽四維投射坐標(biāo)的多基鏈標(biāo)量乘法，在群運算層和標(biāo)量乘運算層對橢圓曲線密碼系統(tǒng)進(jìn)行了優(yōu)化。為了對多基鏈生成算法進(jìn)行優(yōu)化，建立了基于拉格朗日乘數(shù)法的貪心策略，提出最短鏈存在定理并推導(dǎo)出最短鏈表。能量分析攻擊實驗表明，本文提出的分層優(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)量乘實現(xiàn)算法[J]. 通信學(xué)報, 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.