徐雪蓮

（上海海事大學信息工程學院，上海 201306）

0 引言

量子計算機（Quantum Computer），是一種全新的基于量子理論的計算機，遵循量子力學規(guī)律進行高速數(shù)學和邏輯運算、存儲及處理量子信息的物理裝置。在后量子密碼學的前景中，許多已有方法將被淘汰，廣泛使用的RSA系統(tǒng)將會過時?；陔x散對數(shù)問題的橢圓曲線變量對量子分析不起作用，因此依賴于離散對數(shù)問題的任何機制都將變得很脆弱。目前，基于橢圓曲線的快速安全標量乘算法已經(jīng)提出了很多，例如，橢圓曲線Montgomery型高效標量乘算法[11]，利用多基鏈計算橢圓曲線標量乘[12]等。然而，由于超奇異橢圓曲線易受MOV、FR攻擊，此時離散對數(shù)問題會約減到一般有限域上的離散對數(shù)問題，因此，超奇異橢圓曲線曲線上的的快速標量乘算法沒有很多的研究。文獻[1]回顧了超奇異同源密碼交換算法（SIDH），這種類型的密鑰交換方案提供了前瞻性保密，量子系統(tǒng)的任何攻擊仍然需要指數(shù)級別的時間。構造這樣的密鑰系統(tǒng)需要超奇異橢圓曲線以及他們的同源曲線。使用這種方案有很多優(yōu)點，因為超奇異密鑰系統(tǒng)依賴于常用橢圓曲線密鑰系統(tǒng)實現(xiàn)中使用的許多相同的原語，因此現(xiàn)有系統(tǒng)可以非常方便的進行升級。另外，由于不受任何已知的專利的約束，可以對研究界保持自由和開放。超奇異橢圓曲線上的運算公式和標量乘計算方法也在不斷地發(fā)展和改進，與橢圓曲線密碼體制相比,超奇異橢圓曲線密碼體制在量子計算機發(fā)展的大趨勢與量子攻擊的前提下具有更高的安全性。另外，像已建立的橢圓曲線系統(tǒng)一樣，超奇異同源密碼交換與已建立的ECCDH方案相比，提供了類似的密鑰大小和計算效率。本文將在以下的內容中概述必要的數(shù)學概念，然后將橢圓曲線中的快速標量乘算法推廣到超奇異橢圓曲線中，使用有符號滑動窗口的方法對密鑰k進行編碼，改進超奇異橢圓曲線下的標量乘算法。此外，提出使用額外寄存器的改進方法，安全快速的對編碼k進行掃描。利用Frobenius自同態(tài)映射取代NAF算法中的倍增運算，并從硬件的角度考慮，并行的實施標量乘，使其具有能夠快速運算并能夠抵御能量分析攻擊的性質。研究表明，在使用橢圓曲線時,長度為160bits的操作數(shù)與1024bits長度的RSA密碼體制具有相同的安全性。因此，在滿足我們的安全需求的情況下，推薦在超奇異橢圓曲線上建立的群的階大小為2160，討論特征為2的超奇異橢圓曲線上的運算，這樣即可滿足要求。

1 數(shù)學概念

1.1 橢圓曲線

定義：橢圓曲線（Elliptic Curve）是指代數(shù)閉包F上虧格等于1的一條光滑代數(shù)曲線。一般講，由韋爾斯特拉（Weierstrass）方程：

確定的所有點的集合，外加一個無窮遠點ο，稱為橢圓曲線，參數(shù)a,b,c,d,e是滿足一定條件的實數(shù)[3]。

（1）ο為加法單位元，即對橢圓曲線上任意一點p，有 p+ο=p;ο+p=p。

（2）p=(x,y)是橢圓曲線上的一點，那么它的加法逆元為 ρ=( )

x,-y，因為兩點的連線可以延伸到無窮遠處，得到無窮遠點ο，所以 p,ρ,ο三點共線。

（3）設P和Q是橢圓曲線上坐標不同的兩個點，P+Q的定義物理描述如下：畫一條通過P、Q的直線與橢圓曲線交于 R'，交點唯一。由P+Q+R'=ο得P+Q=-R'。

（4）設P和Q是橢圓曲線上坐標相同的兩個點，那么兩點相加可以定義為點的倍數(shù)：在P點做橢圓曲線的一條切線，設切線與橢圓曲線交于R'，定義2P=P+P=-R'=R。

加法滿足正常的加法性質，一條橢圓曲線上的一點P被一個整數(shù)k相乘則被定義為k個P相加。（5）由Hass定理[3]可知：

1.2 超奇異橢圓曲線

定義：滿足以下條件之一的橢圓曲線稱為超奇異橢圓曲線，其中P為橢圓曲線的特征，t為橢圓曲線的跡[2]。

（1）p|t，E的跡t能夠被Fq的特征P所整除；

（2）p=2,3時，j(E)=0；p≥5，t=0；

例如，y2=x3+ax+b的 j不變量為 j(E)=1728?4a3/(4a3+27b2)，當其值為0時，橢圓曲線為超奇異橢圓曲線。超奇異橢圓曲線對比普通橢圓曲線，常規(guī)橢圓曲線允許次指數(shù)量子攻擊，而且在使用同源曲線的情況下，常規(guī)橢圓曲線速度很慢。

1.3 Frobenius映射

同源是一個重要的有理代數(shù)映射φ：兩個橢圓曲線之間的E1→E2，使得對于所有E1上的幾何點P,Q該映射也是一個群組同態(tài)，因為群組操作（加法/乘法）被保留并映射回同一組中的點。形成這樣一個同態(tài)的兩個橢圓曲線必須具有相同的點數(shù)。存在多項式時間算法用于對這些點進行計數(shù)。如果E是橢圓曲線，則[m]E是同源。一般情況下，基于有限域的橢圓曲線除了常數(shù)同態(tài)還有其他同態(tài)的。如果E：y2+cy=x3+ax+b是在特征p的有限域Fq上定義的橢圓曲線，F(xiàn)robinus映射 E→E(P),(x,y)p→(xp,yp)是一種非常數(shù)同態(tài)。我們稱橢圓曲線E具有復乘的屬性，如果橢圓曲線的自同態(tài)中除了常數(shù)同態(tài)還有其他的同態(tài)類型時。

定義：令 a∈{0,1},Ea(F2m)在代數(shù)閉域上的Frobenius映射是：

γ：Ea(F2m)→Ea(F2m

),γ(∞)= ∞,γ(x,y)=(x2,y2)

γ滿足方程 γ2-tγ+q=0，其中稱為自同態(tài) γ的跡，根據(jù) Hass定理，并且#E(Fp)表示曲線上點的個數(shù)。二元域上的平方在多項式基下只需在元素之間插入零,然后約簡，正則基下的所有運算只須循環(huán)移位.因此計算任何二元域元素的Frobenius映射是很快的。

2 快速標量乘法

2.1 特征為2的超奇異橢圓曲線

對于b∈{0 ,1}，m是與6互素的一個整數(shù)，選擇MOV安全指數(shù)為4的橢圓曲線：

滿足方程γ2-2(- 1)aγ+2=0。曲線E上的兩個點。按照1.1中橢圓曲線的群運算法則定義，-ο=ο，-P1=(x1,-y1)，P+ο=ο+P=P可以得到：

2.2 快速標量乘算法實現(xiàn)過程

算法1 NAF的編碼方式及算法描述[10]

（2）當m＞0：

②令m←m-u；

③將u添加到S中；

④令m←m/2。

（3）輸出NAF編碼方式。

算法2計算KP

Q←P

for i=m-2 down to 0 do

Q←2Q+eiP

Output Q

由2.1超奇異橢圓曲線公式可得：2P=(x4+1,x4+y4)，成立，考慮使用映射：υ：(x ,y) →(x+1,x+y)；ο→ο。利用Frobenius自同態(tài)和υ自同態(tài)，得到一種可以簡單計算的自同態(tài)：λ：(x,y)→(x4+1,x4+y4)，也就是 λ(P)=υ(φ2(P))。由于自同態(tài)的運算量與域中的計算量相比可以忽略不計，因此，上述算法二中的2Q步驟可以用自同態(tài)來代替。使用自同態(tài)快速算法的運算量僅僅為1/3n,運算效率提高75%[5]。

2.3 改進的快速標量乘算法

（1）有符號滑動窗口編碼方式

滑動窗口編碼可根據(jù)編碼方式的不同分為無符號滑動窗口算法和有符號滑動窗口算法，具體指用一個寬度為w（一般w≥2）的窗口對標量k重新編碼。接下來主要研究采用有符號滑動窗口大小為3的算法，并且以4位為窗口長度將k的二進制序列進行分組，當窗口的值為負數(shù)時，窗口的值用補碼表示并產(chǎn)生一個進位。例如：k=101111000110000101001110轉換后變?yōu)閗=03000-1000030000005000070。

算法3：

Input： 整數(shù) k

Output：k的有符號滑動窗口編碼方式

For j from 0 up to n-1 do：

由2.1超奇異橢圓曲線公式可得：3p、5p、7p的表達式，分別預計算出對應的倍點值。

預計算步驟：

①P1=P,P2=[2] P;

② i從1到2w-1-1計算P2i+1=P2i-1+P2;

③ i從1到2w-1-1置P2i+1=-P2i+1;

也可使用Frobenius自同態(tài)方法組合簡單的自同態(tài)計算出2p、4p、8p的運算公式，進而得出預計算表Pkj={p,3p,5p,7p…}，僅提供思路。由于，點之間相減的運算時間短于點加的時間。由此，我們可以得到：

①p1=p,p2=[]2 p;

②3p=4p-p;

③5p=8p-3p;

④7p=8p-p;

由超奇異橢圓曲線的的公式可得4p=(x16,1+y16)

主循環(huán)：掃描k時，由于窗口大小為4，選擇每4位計算一次。額外增加一個寄存器用m表示，初始值為4，用于記載每四位中0的個數(shù)。掃描次數(shù)可減少為一半，當掃描到非0位時根據(jù)m的大小進行相應次數(shù)的倍增，因此提高了運算速度。

當j＞=0時執(zhí)行：

① d000：Q=( )Q+Pkj 16 j=j-m,m=4;

②0d00：ki=0,Q=Q,j=j-1,m=m-1;

Q=( )

2Q+Pkj 8,j=j-m,m=4;

③00d0：ki=0,Q=Q,j=j-1,m=m-1;

Q=( )

4Q+Pkj 4,j=j-m,m=4;

④000d：ki=0,Q=Q,j=j-1,m=m-1;

Q=( )

8Q+Pkj 2,j=j-m,m=4;

⑤0000：ki=0,Q=Q,j=j-1,m=m-1;

Q=16Q,j=j-m,m=4;

其中d表示不為0的ki，j表示位移變量,Q=kp,初始值為O，其中4Q、8Q、16Q使用Frobenius映射代替點的倍乘。

3 抗功耗分析攻擊及防御的方案

簡單能量分析。SPA利用算法執(zhí)行期間基于正在處理數(shù)據(jù)的指令進行攻擊。顯然，二進制算法具有由整數(shù)ki調節(jié)的分支指令，因此它能夠揭示出秘密位ki。為了抵抗SPA，應該消除任意的標量乘算法中的分支指令。固定程序方法刪除由秘密指數(shù)d和基于窗口的方法調節(jié)的任何分支。算法3中，當ki=0時，采用Q=Q的方法，使攻擊者無法識別出ki位的值，因此算法3能夠抵抗簡單能量攻擊。

DPA使用能量消耗和特定密鑰位之間的相關性，攻擊者通過大量的數(shù)據(jù)分析能量消耗得到ki位取值。為了抵抗DPA，在每次新的點倍執(zhí)行時都應該改變功耗。主要有3種對策，隨機投影坐標法（RPC）、隨機曲線法（RC）和指數(shù)分解法（ES）。RPC使用雅可比或投影坐標來分別將P(x,y)隨機化為(r2x,r3y,r)或

對m，n進行窗口為w的有符號滑動窗口法重新編碼，m、n的長度相同，調用算法3分別計算mp、np。使用隨機化密鑰r的方式能夠有效的抵抗DPA。由于加密時使用的k是隨機變化的，攻擊者無法形成有效的能量曲線，無法從大量的數(shù)據(jù)中得到密鑰的有效信息，從而阻止了DPA攻擊。隨機化密鑰后每次r的取值不同，產(chǎn)生的編碼也不同，每次標量乘計算中標量的值與密鑰無直接關系。倍增運算由于采用Frobinus映射，也使得攻擊者無法判斷密鑰位。因此，采用隨機掩碼的方式計算標量乘可以抵抗RPA、ZPA攻擊。從硬件的角度來說，可以采取并行的方式同時計算mp和np兩個部分，運算效率得到進一步的提高。

4 效率分析與比較

比較算法3與已有的的二進制算法，NAF算法，算法3從多個方面降低了計算的復雜度，提高了運算效率。具體從整數(shù)k的表示方法、預計算表、k的編碼掃描累加賦值階段，硬件方面。k的有符號滑動窗口表示方法使得非0位個數(shù)減少，也就使得標量乘中點加的次數(shù)減少。傳統(tǒng)算法中需要L次倍點計算及不超過L+2次的點加計算。表1[9]列出不同坐標系下需要的計算復雜度。

在Chudnovsky Jacobian坐標下，總的計算量最小，整體的計算量約為：獻中[6]證明采用Affine和Jacobian混合坐標系計算算法中2wR+S的計算量最小為(4 w+3) S+(4w+9)M。利用超奇異橢圓曲線自同態(tài)映射進行倍點運算的效率比較傳統(tǒng)的倍點運算效率提高了75%，所以提高整體的計算量集中在減少點加運算次數(shù)上。文獻[7]中證明長度為Lbit的二進制標量k采用滑動窗口進行編碼后,非零位的平均個數(shù)為L/(w+2)，其中(w+2)為有符號滑動窗口編碼方法中的平均窗口寬度。安全性分析中取得隨機數(shù)時間及k的編碼時間可以忽略不計。

表1 不同坐標系點加和倍點計算量

假設點加和點倍運算相同以及密鑰長度為160bit，表2列出幾種算法在假設前提下需要計算的點加量。比較本文算法與傳統(tǒng)的二元法下的窗口算法、NAF算法的計算復雜性，具體從預計算和累加賦值兩階段進行比較。

表2 不同算法點加量

使用預計算表的方式使得標量乘過程中的點加運算可以查表獲得。不使用同源映射的情況下，預計算需要進行2w-1-1次的點加計算以及一次倍點運算，然后主循環(huán)部分進行次計算，一次點加計算。所以整個運算量為預計算與主循環(huán)部分之和主循環(huán)部分用額外寄存器的方法統(tǒng)計窗口大小的掃描單位中0的個數(shù)，使k的掃描次數(shù)減少一半。結合寄存器m中的值對2Q進行m次映射。因此，整體上是的標量乘的運算效率提高了80%左右。據(jù)分析，當L取160時，w取3的時候效率最高。表3列出幾種算法的計算量比較。

表3 計算量

5 結語

本文基于Frobenius映射給出了超奇異橢圓曲線上的一種改進算法，該算法使用有符號滑動窗口算法來減少標量乘計算中編碼k的非0位出現(xiàn)的次數(shù)，同時使用了預計算表來提高累加賦值階段的效率。由于改進算法采用額外的寄存器加快了0位的掃描速度，使用高效的Frobenius映射無須進行倍點運算，所以進一步提高了標量乘算法的效率。