基于偽四維投射坐標的多基鏈標量乘法

徐明，史量

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

1 引言

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

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

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

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

2 基礎知識與相關工作

2.1 有限域中的橢圓曲線

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

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

2.2 橢圓曲線密碼系統的層次結構

橢圓曲線密碼系統可分為5層：物理層、域運算層、群運算層、標量乘運算層和應用層，如圖 1所示，其中，上層運算依賴于下層運算，而下層運算為上層運算提供服務。

圖1 橢圓曲線密碼系統層次結構

2.2.1 域運算層

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

2.2.2 群運算層

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

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

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

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

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

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

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

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

2.2.3 標量乘運算層

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

其中，為基的個數，n為鏈長，{bj}為單調遞減數列。

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

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

3) 鏈長n盡可能短。

針對上述原則，本文通過基于偽四維投射坐標的快速群運算和基于偽四維投射坐標的多基鏈標量乘法，對橢圓曲線密碼系統進行分層優化。

2.2.4 應用層

應用層搭載著基于橢圓曲線密碼系統的眾多應用，如基于橢圓曲線的密鑰交換和基于橢圓曲線的數字簽名等，這些都是橢圓曲線密碼系統的經典應用。

3 基于偽四維投射坐標的快速群運算

3.1 偽四維投射坐標的建立

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

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

3.2 基于偽四維坐標的倍點運算

其中，

算法1 基于偽四維坐標的倍點運算

輸入

輸出

初始化

1)

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

3.3 基于偽四維坐標的三倍點運算

其中，

算法2 基于偽四維坐標的三倍點運算

輸入

輸出

初始化

1)

2)

3)

4)

返回

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

3.4 基于偽四維坐標的五倍點運算

其中，

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

投射坐標的五倍點運算需要的域操作數為11M+12S。

圖3 偽四維投射坐標五倍點運算的域運算示意

4 基于偽四維投射坐標的多基鏈標量乘法

4.1 多基鏈生成算法的優化策略

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

算法3 多基鏈生成算法

輸入 大整數k，倍點最大值maxb，三倍點最大值maxt，五倍點最大值maxq，最小值系數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) 通過貪心算法找到最合適的整數| |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中設置了倍點、三倍點和五倍點的最大值，并且每一次都將求出來的倍點、三倍點和五倍點個數代入下一次遞歸，保證多基鏈是遞減的，方便接下來的標量乘運算。此外，為了防止基鏈過于冗長，算法 3引入了最小值系數c1、c2、c3來限制倍點、三倍點和五倍點個數的最小值來提高標量乘算法的運算效率。其數學模型如式(5)所示。

已知

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

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

針對以上問題，本文使用拉格朗日乘數法建立數學模型并對算法3中的貪心算法進行優化，找到最合適的倍點、三倍點和五倍點個數。首先，給出數學模型如下。

已知

求min

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

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

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

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

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

4.2.1 最短鏈存在定理

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

證明 根據算法3，可以將定理1抽象為函數

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

4.2.2 最短鏈表

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

表1 最短鏈表

4.3 基于偽四維投射坐標的多基鏈標量乘法

算法4詳細描述了本文提出的基于偽四維投射坐標的多基鏈標量乘法。

算法4 基于偽四維投射坐標的多基鏈標量乘法

輸入 整數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←基于雅克比坐標點加(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'←基于偽四維坐標五倍點(Q')

10) end for

11) fork=1 tovdo

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

13) end for

14) forl=1 toudo

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

16) end for

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

18) ifsm?i+1= 1 then

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

20) else

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

29) returnP

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

5 系統效率分析與實驗

5.1 群運算效率分析

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

表2 群運算效率比較

5.1.1 離散群運算效率比較

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

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

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

5.1.2 連續群運算效率比較

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

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

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

5.2 系統總開銷分析

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

表3 系統總開銷比較

由表3可知，當密鑰長度為160位時，本文算法的總開銷比文獻[14]降低了 57.79%，比文獻[13]降低了36.09%，比文獻[17]降低了26.82%，比文獻[16]降低了23.32%，比文獻[15]降低了12.94%，比文獻[18]降低了8.70%。此外，文獻[18]的算法只能運用于二元域，其余算法既可以運用于二元域，也可以運用于素數域。

5.3 能量分析攻擊實驗

5.3.1 實驗環境搭建

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

圖5 Chipwhisperer-Lite實驗平臺的體系結構示意

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

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

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

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

5.3.3 抵御DPA攻擊

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

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

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

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

6 結束語

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

[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標量乘實現算法[J]. 通信學報, 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.