ＧＦ（ｐ）上橢圓曲線密碼的并行基點選取算法研究

摘要：提出一種GF(p)上橢圓曲線密碼系統的并行基點選取算法，該算法由并行隨機點產生算法和并行基點判斷算法兩個子算法組成，給出了算法性能的理論分析和實驗結果。結果表明:各并行處理器單元具有較好的負載均衡特性;當執行并行基點判斷算法，其標量乘的點加計算時間是點倍數計算時間的三倍時，算法的并行效率可達90%。因此該算法可用于橢圓曲線密碼（Elliptic Curve Cryptography，ECC）中基點的快速選取，從而提高ECC的加/解密速度。關鍵詞：橢圓曲線密碼; 橢圓曲線; 標量乘; 并行算法; 基點

中圖分類號：TN918.1文獻標志碼：A

文章編號：10013695(2007)04003304

0引言

自1976 年斯坦福大學的Diffie和Hellman首次提出公開密鑰體制(又稱為非對稱密鑰系統)以來^[1]，公開密鑰系統的研究已成為信息安全領域中一個引人矚目的研究課題。迄今為止，只有三類公開密鑰密碼體制被證明是安全和有效的，這些體制根據它們所依據的數學問題，可分為整數因式分解體制(RSA)、離散對數體制(如ELGamal體制、DSA)以及橢圓曲線密碼體制(ECC)。所有這些公開密鑰密碼體制的安全性均依賴于其相應數學問題的難解性^[2]。在安全性相同的情況下，ECC較RSA具有更小的密鑰尺寸^[3]，可以實現更快的加/解密速度，節省更大的寬帶和獲得更高的存儲效率，因此ECC在智能卡和無線網絡等許多重要應用中具有明顯優勢。ECC的安全性依賴于橢圓曲線離散對數問題的難解性，要構造基于離散對數的密碼體制，必須找出橢圓曲線加法群的大素因子子群的一個生成元，即基點。因此研究大素數域GF(p)上橢圓曲線的快速基點選取算法對于提高橢圓曲線密碼系統的效率具有重要意義。

選取基點首先要尋找橢圓曲線上任意一個隨機點，然后利用隨機點計算標量乘，再判斷標量乘以確定橢圓曲線的基點。文獻[2]采用分布式并行算法改進了文獻[4]的串行基點選取算法，但是文獻[2]提出的并行算法分別使用前后兩部分處理器尋找橢圓曲線上的隨機點和判斷隨機點是否為基點。計算標量乘是基點選取的主要開銷，因此會出現判斷隨機點是否為基點的處理器一直計算，而尋找隨機點的處理器很快就會把公共表寫滿而長時間處于空閑狀態的情況，從而導致了處理器負載不均衡。同時文獻[2]的并行選取基點算法是通過標準二進制表示來加速標量乘的，這也限制了基點選取效率的提高。

本文改進文獻[2]的基點選取算法，使用2m（m∈N，m≥1)個處理器和m個循環緩存，提出一種GF(p)上橢圓曲線的并行基點選取算法。該算法由并行隨機點產生算法和并行基點判斷算法兩個子算法組成。本算法改進了文獻[2]中算法的不足，使用全部處理器，同時尋找隨機點并判斷基點，這樣保證了各并行處理單元具有較好的負載均衡特性;在實現并行基點判斷算法時采用文獻[5]中的標量乘算法，它與其他的以點倍數和方法為基礎的方法相比，能以最快的速度完成標量乘，因此能提高ECC中基點的選取效率。

1ECC中基點選取的相關研究

1.1ECC的基點選取

ECC的基點選取是實現ECC的基礎，GF(p)上ECC的基點選取首先是生成橢圓曲線的任意一個隨機點，然后利用隨機點計算標量乘，再判斷標量乘以確定橢圓曲線的基點。文獻[4]給出了串行GF(p)上ECC的基點選取算法。

設#E(GF(p))=hk(k是橢圓曲線E的階的大素因子)，下面給出GF(p)上ECC的串行基點選取算法^[4]。

算法1GF(p)上ECC的串行基點選取算法

輸入:一個素數p>3，GF(p)上橢圓曲線E的參數a和b、h、k，#E(GF(p))=hk

輸出:E上階為k的點G

（1）隨機選取x(0 ≤x< p)。

（2）α=x3+ax+b(mod p)。

（3）如果α= 0，將點(x，0)保存到公共表中;如果α≠0，利用模p的平方根方法求α的一個平方根或判斷它不存在。如果沒有平方根存在，通知其他處理器不能選此點，并返回（1）；否則求出一個整數β，0＜β＜p，使得β2≡α(mod p)，生成一個隨機比特μ，令y=(-1)μβ并將點P=(x，y)保存到公共表中。

（4）在公共表中隨機選一個點P。

（5）G=hP。

（6）如果G=(x，y)滿足橢圓曲線方程y2=x3+ax+b(mod p)，即G ≠ 0，則輸出G;

否則在公共表中刪掉點P，并返回（4）。

實際上可以將算法分為兩大步驟完成：（1）～（3）屬于第一階段，產生橢圓曲線上的隨機點;（4）～（6）屬于第二階段，判斷隨機點是否是橢圓曲線的基點。

將實現第一階段的算法稱為隨機點產生算法，第二階段的算法稱為基點判斷算法。

1.2ECC基點選取中的標量乘

GF(p)上橢圓曲線基點選取的關鍵步驟和ECC的基本操作是標量乘，即用一整數乘以橢圓曲線上給定的點P^[6]。可用一系列點和(Point Addition:ECADD)與點倍數(Point Doublings:ECDBL)操作，即倍數和(DoubleandAdd)方法計算標量乘。TECADD和TECDBL分別表示點和與點倍數操作的時間。對于n位標量k，如果采用NAF表示，那么計算標量乘kP的平均時間是n/3TECADD+nTECDBL，其中P是GF(p)上橢圓曲線的點^[7]。

算法2給出了計算標量乘kP的DoubleandAdd 算法^[7]，k為標量，P是橢圓曲線的點。

算法2DoubleandAdd Algorithm

輸入:點P，整數k=∑n-1i=0ki2i，ki∈{0，1}

輸出: Q=kP

(1)Q=P; R=0;

(2)For i=0 to n-1

①If ki=1then R=R+Q

②Q=2Q;

Return R

并行計算點運算可以實現更快的標量乘算法。算法2的①和②相互獨立沒有依賴關系，因此可以對它們進行并行操作。 速度、內存和對SCA(Side Channel Attack)的防御會限制標量乘的實現。Mller Bodo^[8]提出了并行標量乘算法，算法不但能快速計算標量乘，而且還能有效防御SCA。當采用適當的坐標系統時，執行標量乘的時間為nTECDBL+2(2w-1)TECADD并分配2w額外的內存。其中，w≥2，k=∑n-1i=0bi2i，bi∈{0，1，…，2w-1}。Tetsuya I.等人^[9]提出的Montgomey標量乘算法在雙處理器系統的執行時間為(n-1)max(TECADD，TECDBL)，這個算法也能安全防御SCA。

Ansari Bijan等人^[5]提出了一種并行計算橢圓曲線密碼體制的標量乘的算法。算法采用兩個處理器和一個循環緩存實現，其雙處理器系統結構如圖1所示。兩個處理器共享循環緩存和一個計數器。這個緩存是標準循環緩存，具有空和滿的標志位，其中一個處理器用于ECDBL操作，另一個用于ECADD操作，兩個處理器可以異步運行。ECDBL處理器計算2iP，并把結果寫到循環緩存中，ECADD處理器從循環緩存中讀取數據并求和。循環緩存用于兩個處理器間的通信，以減少標量乘的平均時間為nTECDBL。

圖1雙處理器系統結構

2GF(p)上ECC的并行基點選取算法

本節采用2m(m∈N，m≥1)個處理器PR0，…，PR2m-1和m個循環緩存buffer(u) (0≤u≤m-1)分兩個步驟實現GF(p)上橢圓曲線的并行基點選取算法:并行隨機點產生算法和并行基點判斷算法。把2m個處理器分成m個處理器對，即PRu和PRu+m(0≤u≤m-1)。首先所有處理器都選取GF(p)上橢圓曲線的隨機點，并把隨機點寫入所有處理器都能訪問的共享公共表GT中。當處理器對PRu和PRu+m中任一處理器選取到隨機點，寫入所有處理器都能訪問的共享公共表GT中，然后通知對方調用基點判斷算法對其進行判斷。若它們同時選取到隨機點，則兩個處理器任意選取同一個隨機點進行判斷。實現本算法的偶數處理器系統結構如圖2所示。

圖2偶數處理器系統結構

21GF(p)上橢圓曲線的并行隨機點產生算法

全局變量:i，buffer(u)，GT。其中buffer(u)表示第u對處理器對共享的緩存Buffer。

算法3GF(p)上橢圓曲線的并行隨機點產生算法

輸入:一個素數p>3，GF(p)上橢圓曲線E的參數a和b

輸出:E上的隨機點P=(x，y)保存到公共表GT中(無窮遠點除外)

Begin

For all PRi and PRi+m where 0≤i≤m-1 do

隨機選取x(0≤x< p);

α=x3+ax+b(mod p);

If (α=0 ) then 

將點(x，0)保存到公共表GT中;并通知其他處理器不要再選此點;

Else 

利用模p的平方根方法求a的一個平方根q;

If (q不存在) then 通知其他處理器不要再選擇此點并返回1;

Else

求β，0＜β＜p且β2≡α(mod p);生成一個隨機比特μ;y=(-1)μβ;

將點P=(x，y)保存到公共表GT中;

End

假設每2m個點中才有一個點是隨機點，在最壞的情況下串行選取隨機點就要選取2m次才能找到一個隨機點，而2m個處理器并行選取隨機點只要選取一次就可以找到一個隨機點，所以，并行隨機點產生算法的效率是串行的2m倍。

22GF(p)上橢圓曲線的并行基點判斷算法

GF(p)上橢圓曲線基點選取的基點判斷算法首先計算標量乘，然后通過判斷標量乘是否等于零來確定該隨機點是否為基點。算法中m個處理器對PRu和PRu+m(0≤u≤m-1)分別采用文獻[5]中的并行標量乘算法求解標量乘，然后由PRu+m處理器判斷隨機點是否為基點，并輸出基點。

PR0，…，PRm-1處理器計算2iP，并把結果寫到循環緩存中；PRm，…，PR2m-1處理器從循環緩存中讀取數據并求和；PRm，…，PRm-1處理器首先讀取點P，然后開始不斷運行倍數操作。當檢查到非零的hi且緩存沒有滿時就把2iP寫到緩存中去。如果PRm，…，PR2m-1沒有讀取緩存中的數據時，緩存就會被寫滿，這時PR0，…，PRm-1處理器就要等待，直到緩存中有空的單元。若h的二進制表達式中沒有足夠的1，緩存很快就會變空，那么PRm，…，PR2m-1處理器也需要等待，直到PR0，…，PRm-1處理器寫數據到緩存。PRm，…，PR2m-1處理器只從緩存中讀取數據輸入，當緩存中有多個數據時，就讀取PR0，…，PRm-1處理器最先寫入的數據。PRm，…，PR2m-1處理器讀取數據并立即把該數據從緩存中刪除。當PR0，…，PRm-1處理器停止計算并寫入數據到緩存且PRm，…，PR2m-1處理器已經讀取了緩存中的所有數據時，就得到了標量乘，然后判斷該隨機點是否為基點，并輸出基點。 

算法4給出了具體實現并行判斷隨機點是否為基點的過程，P是橢圓曲線上的點。

算法4GF(p)上橢圓曲線的并行基點判斷算法

輸入:一個素數p>3，GF(p)上橢圓曲線E的參數a和b、h、k，#E(GF(p))=hk，GT

輸出: E上階為k的點G

Begin

If ( GT is not NULL ) then

For all PRi and PRi+m where 0≤i≤m-1 do

從GT中選取同一個隨機點P;

//PR0，…，PRm-1處理器用于ECDBL操作，實現下面算法

For all PRu where 0≤u≤m-1 do 

Q=P; i=0;

While i

If hi=1 then

If (buffer(u) is full) then (wait);

Elsewrite Q into buffer(u);

Q=2Q; i=i+1;

//PRm，…，PR2m-1處理器用于ECADD操作，實現下面算法

For all PRu+m where 0≤u≤m-1 do 

G=0; i=0;

While i

If (buffer(u) is not empty) then

Read 2iP from buffer(u); G=G+2iP;

erase 2iP from buffer(u);

Else (wait); 

If(G=(x，y)滿足橢圓曲線方程y2=x3+ax+b (mod p)) then輸出G;

Else 

在公共表中刪掉點P; 通知PRu處理器判斷另一隨機點；

Else

For all PRi where 0≤i≤2m-1 doPerform 算法3;

End

并行基點判斷算法的關鍵步驟是計算標量乘， 計算標量乘是算法的主要開銷。因此求解標量乘的效率決定了整個基點判斷算法的性能。算法采用m個循環緩存用于處理器對之間的通信，從而減少了標量乘的平均執行時間。 m個處理器對同時判斷m個隨機點，因為所有處理器都參與了計算，所以不但提高了算法的效率，而且還提高了處理器的利用率，從而改進了文獻[2]中算法的不足。

3性能分析和實驗結果

本文提出的GF(p)上橢圓曲線的并行基點選取算法由兩個算法完成，算法的開銷主要在于基點判斷算法。所以基點判斷算法的性能決定了整個GF(p)上橢圓曲線密碼系統的并行基點選取算法的性能。本文中并行基點判斷算法所采用的并行標量乘算法比其他以點倍數和方法為基礎的方法完成標量乘的速度最快。表1給出了現有多種標量乘算法的性能比較。

表1現有標量乘算法性能的比較

計算標量乘方法平均執行時間是否防御SCA

Blake I.F.^[7]nTECDBL+(n/3) TECADD是

Mller Bodo^[8]nTECDBL+2(2w-1)TECADD是

Tetsuya I.^[9](n-1)max(TECADD，TECDBL)是

Ansari B.^[5]nTECDBL是

本文采用的并行標量乘算法性能取決于比率r=TECADD/TECDBL(假定r≥1)和非零數字在標量k的二進制表達式中出現的頻率。假設常用的單處理器方法和本文提出的算法都采用k的NAF形式，借助MIRACL(Multiprecision Integer and Rational Arithmetic C/C++ Library)^[10] 系統利用標準C語言實現的實驗結果如表2所示。表中n是k的二進制長度，n的值選擇當前橢圓曲線密碼體制流行的實現范圍:150、200、250和300^[5]，r=TECADD/TECDBL，Tnew表示用本文提出的并行基點選取算法的執行時間，TNAF是采用標準NAF方法在單處理器上實現基點選取的時間。 

結果顯示當點加的執行時間是點倍數操作時間的三倍時達到最大加速比。此時，循環緩存大小必須是4或是更大足以存儲四個橢圓曲線點。表2顯示增加緩存的大小不會提高算法的性能。

本文提出的并行選取橢圓曲線的基點算法的實現過程中，所有處理器都用于并行產生橢圓曲線上的隨機點并判斷隨機點是否為橢圓曲線的基點，這樣不但提高了算法的效率，而且保證了所有處理器單元的負載均衡。算法使用公共表和處理器對共享的循環緩存以減少處理器間的通信，總的通信開銷為2(m-1)。通過MIRACL，系統采用標準C語言成功實現了并行GF(p)上安全橢圓曲線基點的選取，實驗結果表明該算法加快了橢圓曲線基點的選取。當計算標量乘的r=TECADD/TECDBL=3時， GF(p)上橢圓曲線的并行基點選取算法的效率可達90%。

表2GF(p)上ECC并行基點選取算法的實驗結果

可擴展性的恒等效率(Isoefficiency)函數^[11]:

W=E/（1-E）T0(W，p)=KT0(W，p)(1)

其中，W為問題的規模，E為算法的效率，K為常數，p為處理器規模，T0是處理器數p與工作負載W的函數。p的冪越小，并行系統的可擴展性就越大(系統包括算法和結構的組合)。

由式（1）可得本算法的恒等效率函數為W=K（n/m）。因此，為保持效率固定，可以實現所需的工作負載與機器規模的相對關系。

4結束語

在深入分析現有橢圓曲線基點選取算法的基礎上，本文提出了一種GF(p)上橢圓曲線的并行基點選取算法，包括并行隨機點產生算法和并行基點判斷算法。在實現基點選取時，2m個處理器均同時并行尋找隨機點和并行判斷隨機點是否為基點，改進了文獻[2]中算法的不足，同時采用文獻[5]的并行標量乘算法。本算法不僅保證了各并行處理器單元具有較好的負載均衡特性，還提高了GF(p)上橢圓曲線的基點選取效率，實現了ECC中基點的快速選取，從而可以提高整個ECC加/解密的效率。

此外，利用文獻[4]提出的GF(p)上安全橢圓曲線的選取算法生成安全橢圓曲線后，再通過本文的并行基點選取算法選取基點，即可快速實現ECC的加/解密。對本算法在使用更多處理器時的可擴展性研究，對于提高ECC的整體效率具有相當重要的理論和實際意義。標量乘運算是ECC的主要開銷，因此加速標量乘，從而提高ECC的效率是目前研究ECC的一個重要課題。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。