超奇異橢圓曲線標(biāo)量乘算法改進(jìn)

徐雪蓮

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

0 引言

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

1 數(shù)學(xué)概念

1.1 橢圓曲線

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

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

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

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

x,-y，因?yàn)閮牲c(diǎn)的連線可以延伸到無窮遠(yuǎn)處，得到無窮遠(yuǎn)點(diǎn)ο，所以 p,ρ,ο三點(diǎn)共線。

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

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

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

1.2 超奇異橢圓曲線

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

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

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

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

1.3 Frobenius映射

同源是一個(gè)重要的有理代數(shù)映射φ：兩個(gè)橢圓曲線之間的E1→E2，使得對(duì)于所有E1上的幾何點(diǎn)P,Q該映射也是一個(gè)群組同態(tài)，因?yàn)槿航M操作（加法/乘法）被保留并映射回同一組中的點(diǎn)。形成這樣一個(gè)同態(tài)的兩個(gè)橢圓曲線必須具有相同的點(diǎn)數(shù)。存在多項(xiàng)式時(shí)間算法用于對(duì)這些點(diǎn)進(jìn)行計(jì)數(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具有復(fù)乘的屬性，如果橢圓曲線的自同態(tài)中除了常數(shù)同態(tài)還有其他的同態(tài)類型時(shí)。

定義：令 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)表示曲線上點(diǎn)的個(gè)數(shù)。二元域上的平方在多項(xiàng)式基下只需在元素之間插入零,然后約簡(jiǎn)，正則基下的所有運(yùn)算只須循環(huán)移位.因此計(jì)算任何二元域元素的Frobenius映射是很快的。

2 快速標(biāo)量乘法

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

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

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

2.2 快速標(biāo)量乘算法實(shí)現(xiàn)過程

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

（2）當(dāng)m＞0：

②令m←m-u；

③將u添加到S中；

④令m←m/2。

（3）輸出NAF編碼方式。

算法2計(jì)算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)，得到一種可以簡(jiǎn)單計(jì)算的自同態(tài)：λ：(x,y)→(x4+1,x4+y4)，也就是 λ(P)=υ(φ2(P))。由于自同態(tài)的運(yùn)算量與域中的計(jì)算量相比可以忽略不計(jì)，因此，上述算法二中的2Q步驟可以用自同態(tài)來代替。使用自同態(tài)快速算法的運(yùn)算量?jī)H僅為1/3n,運(yùn)算效率提高75%[5]。

2.3 改進(jìn)的快速標(biāo)量乘算法

（1）有符號(hào)滑動(dòng)窗口編碼方式

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

算法3：

Input： 整數(shù) k

Output：k的有符號(hào)滑動(dòng)窗口編碼方式

For j from 0 up to n-1 do：

由2.1超奇異橢圓曲線公式可得：3p、5p、7p的表達(dá)式，分別預(yù)計(jì)算出對(duì)應(yīng)的倍點(diǎn)值。

預(yù)計(jì)算步驟：

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

② i從1到2w-1-1計(jì)算P2i+1=P2i-1+P2;

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

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

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

②3p=4p-p;

③5p=8p-3p;

④7p=8p-p;

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

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

當(dāng)j＞=0時(shí)執(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映射代替點(diǎn)的倍乘。

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

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

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

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

4 效率分析與比較

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

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

表1 不同坐標(biāo)系點(diǎn)加和倍點(diǎn)計(jì)算量

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

表2 不同算法點(diǎn)加量

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

表3 計(jì)算量

5 結(jié)語

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