橢圓加密算法的改進算法研究與分析

王玲麗

摘要：隨著移動互聯網技術、物聯網、電子商務等各種應用的急速發展，針對計算機安全、網絡安全、信息安全的威脅越來越嚴重，信息安全的重要性越來越得到人們的重視，橢圓曲線加密技術目前在TLS、PGP和SSH等中應用廣泛，在有限域 GF（p）上包括橢圓曲線點加法運算及其可視化，在有限域 GF（p）上橢圓曲線標量乘法運算及其可視化，橢圓曲線點對實數域 R的加法運算及其幾何意義，都將在本論文中展開研究。

關鍵詞：橢圓曲線;橢圓曲線加密;可視化工具;加密與解密

中圖分類號：TP311? ? ? 文獻標識碼：A? ? ? 文章編號：1009-3044（2019）01-0054-03

本文主要是研究在安全性、計算效率方面有很大優勢的一種公鑰密碼[1]體制——橢圓曲線加密算法及其應用。其研討工作主要有以下幾個方向：HTML5+ jQuery框架 Web前端開發技術，橢圓曲線加密算法與數學有著密切的關系，尤其是對在有限域上的橢圓曲線形成的循環子群[2]、生成元的生成算法進行了詳細的研究，因為它們對于實際的 ECC加密算法的實現非常關鍵。相關的算法和實現細節也在論文中進行了展示;并改進了雙點計算的方法[9]，從而提高了橢圓曲線密碼的加密和解密過程的速度。點nP的標量運算的時間復雜度從O（n）提高到log（n）。

1 橢圓曲線群運算及可視化工具開發

橢圓曲線加密一直都廣泛地在TLS、PGP和SSH中運用。橢圓曲線加密算法在數學領域中也可以靈活運用，例如橢圓曲線幾何、集合論、阿貝爾群、有限域等。這些運算不僅抽象，而且計算量也很大。故本文利用HTML5和css、jQuery框架等相結合的想法，利用研究有限域橢圓曲線的可視化工具進行開發研究。

1.1 橢圓曲線的可視化工具的開發

為了更好地理解橢圓曲線上的點的各種操作及其幾何意義，有必要直觀地理解橢圓曲線，例如奇異曲線。 因此，本文開發了實際場和有限域中的橢圓曲線可視化工具軟件。 b的值在真實場上給出了各種不同的橢圓曲線。

1.2 橢圓曲線Abel群的定義及幾何意義的可視化

為了點加運算更加清晰地展現出來，本文開發了可視化工具軟件顯示其代數計算的結果以及其幾何意義：橢圓曲線連接到兩個不同點P和Q的和，并且PQ的延長線和曲線相對于x軸的交點稱為橢圓的切線。 圖1-2（ a）是橢圓曲線上的兩個點 P（1，2）， Q（3， 4）相加得到點 R（-3，2）以及其幾何意義，點 R（-3， 2）是 PQ延長線和橢圓曲線的交點（-3，-2）的對稱點。 圖1-2（a）還驗證了橢圓曲線下的組的定義： 在橢圓曲線上，三個非單位點 P， Q，- R以直線連接，并且它們的和為 P+ Q+ （- R）= O.圖1-2（ b）說明了在橢圓曲線上定義組的另一個規則： 若 P、 Q互為逆元，即 P與 Q關于 x軸對稱或者說 Q=- P，則 P+ Q= O，它也表達了一個無限點。

標量乘法也稱為雙點運算，即計算。當變量n很大時，計算的時間復雜度也會變大。 圖1-3（a）是橢圓曲線上不相同的兩個點的相加; 圖1-3（ b）顯示了兩個相互反向元素的點的相加，即通過該點的橢圓的正切，切線和橢圓曲線交點處的對稱點是添加兩個相同點的結果; 圖1-3（ b）和1-3（ c）表示添加兩個相同的點（ P+ P）具有點 P的雙標量乘法（2 P）的結果在幾何上是一致的。

1.3 有限域GF（p）上橢圓曲線群點集的計算

假設有橢圓曲線[E97（2，3）：y2=x3+2x+3（mod97）]，其上有 P（3，6），如果在 P上執行標量乘法計算，你會發現結果只有五個不同的值（ O， P，2 P，3 P，4 P），并且循環出現。 可以證明的是純量乘法在加法運算下是出于封閉狀態下的，換句話說，通過在有限域上的橢圓曲線的點 P上迭代地執行標量乘法而獲得的一組點構成循環子組。 P稱為循環子群的生成元（ generator）或基元（ base point）。

子群的階：由P生成的橢圓曲線上的子群的階是指一個最小的正整數n，滿足nP=O。例如在圖1-4中，橢圓曲線[E97（2，3）：y2=x3+2x+3（mod97）]上的一個點P（12，3）生成的子群的階是50。

因此，在有限域上GF（p）上橢圓曲線兩個點相加P+Q=R的幾何意義是：首先由P、Q確定斜率為m的一組平行線（滿足線性方程y=mx+c （mod p）），如果橢圓曲線的點集合中的某個離散點R落在某一條平行線上，則R關于x軸的對稱點R就是P+Q的計算結果。例如在圖1-5中，橢圓曲線C上的兩個點P（16，20）， Q（41，120）進行點加運算，計算斜率C，c=83，得到滿足方程C的一組平行線，在點集合中容易驗證R=（86， 46）滿足該方程，則R的逆元R=（86， -46）=（86，-46+127）=（86， 81）即為點P與Q相加的結果。

2 橢圓曲線加密算法的改進與優化

2.1 對橢圓曲線群純量乘法的優化與改進過程

除了進行點加法之外，還有另外一種運算叫點乘運算[4]：cP=P+P+...+P，其意義為計算cP需要執行n-1次加法，其點乘運算的時間復雜度為O（n）。如果用k位二進制表示，即c=bk-1…b1b0，則算法的時間復雜度為O（2k），可以利用倍加運算（double and add operations.）進行快速計算，如果n表示為二進制，則該二進制表示可以轉化為2的冪和。然后，我們取n的每一個二進制數，乘以它的2次方。

[n=i=0…k-1bi?2i]

（1） 若倍加操作的運算為O（1），則該算法的復雜度為O（logn），運用此優化改進之后其復雜度O（n）。計算151P，則將151用二進制表示則為100110111，151P=（1*27+0*26+0*25+1*24+0*23+1*22+1*21+1*20）P，最終計算出151P的結果需要通過7次的“加倍運算”與4次“相加運算”即可實現，運算的時間復雜度明顯降低。

（2） 給定一個有限域橢圓曲線，要利用其實現橢圓曲線加密算法，那么橢圓曲線群生成元P的選擇及其階的計算至關重要。本文中采用的方法不是首先選擇一個生成元，然后計算基于該生成元的子群，而是尋找一個生成元使其生成的循環子群具有高階。所采用的方法如下：

① 選擇一個橢圓曲線Ep（a，b）： y2=x3+ax+b mod p;

② 計算該橢圓曲線的階N;

③ 如果G=hP是單位元O，則轉到第（4）步重新選擇一個點P，否則就找到了一個具有階n和輔因子h的循環子群的生成元G=hP。

（3） 例如，根據本文在第4章開發的可視化工具的計算，橢圓曲線y2=x3?x+3 （mod 37）的階為N=42，N的因子有n=1 ， 2， 3， 6， 7， 14， 21，42，選擇n=7（素數）作為子群的階，隨機選擇橢圓曲線的一個點P=（2， 3），h=N/n=42/7=6，計算hP=6P=（2，34）≠O，因此得到用于橢圓曲線加密的循環子群，其生成元是G（2， 34），階為n=7。

2.2 橢圓曲線加密解密算法

2.2.1 ECC的密鑰生成算法

假如通信雙方為A，B，發送方為A，接收方為B，要生成一個用戶B的公鑰、私鑰對的算法如下：

（1） 選擇一個橢圓曲線E：y2=x3+ax+b（mod p），構造一個橢圓Abel群Ep（a， b）;

（2） 在Ep（a， b）中挑選生成元G=（x0，y0）， G應使得滿足nG=O的最小n （n是G的階）是一個非常大的素數;

（3） 選擇一個小于n的整數nB作為私鑰，公鑰為PB=nBG， 即：

用戶B的public key=（n， G， PB， Ep（a， b））。

用戶B的secure key=nB（小于n）。

2.2.2 AàB實現保密通信，發送端A的加密算法

step1：將明文消息編碼成一個數m<p，將m鑲嵌到曲線上得點Pm=（xm，ym），再對點Pm做加密變換。

step2：在[1， n-1]內選取一個隨機整數k， 計算點P1=kG。k是保密的，但接收端無須知道。

step3：根據B的公鑰PB， 計算點P2=kPB。

step4：A端傳送加密數據Cm={P1， Pm+P2}，其為2個點。

2.2.3 AàB實現保密通信，接收端B的解密算法

step1：接收方B接收到的是2個點kG， Pm+kPB ，其用自己的私鑰nB做如下計算：Pm+P2- nBP1即可解密，因為Pm+kPB- nBkG= Pm+knBG- nBkG=Pm。

step2：根據Pm，接收端再根據發送方的明文編碼的鑲嵌方法即可得到明文編碼m，進一步得到明文。

2.3 橢圓曲線加解密算法的實現與結果分析

橢圓曲線密碼體制是基于有限域GF（89）上的E89（-1，0）： y2=x3-x mod 89，根據文獻 [3]中的Schoof算法計算該橢圓曲線群的階為N=80，N的所有因子為n=1， 2， 4， 5， 8， 10， 16， 20， 40， 80。對于N的每個因子n=1， 2， 4， 5， 8， 10， 16， 20， 40， 80，計算nP。

1P=（68，4）， 2P=（21，42）， 4P=（68，85）， 5P=O， 8P=（21，47）， 10P=O， 16P=（68，4）， 20P=O， 40P=O， 80P=O。

易知，滿足nP=O的最小的n=5且其為素數，計算其協因子h=N/n=16。隨機選擇橢圓曲線上一個P（12，5）且滿足hP=16P=（68，85）≠O，則選擇G=（68，85）作為用于橢圓曲線加密的循環子群的生成元。很顯然其階為n=5，因為nG=5G=5*16P=80P=O。

選擇小于n的整數dB=3作為接收端B的私鑰（Private Key），計算B的公鑰（Public Key）PB=dBG=3（68，85）=（21，42）。

發送端A加密時選擇一個秘密整數k=2，對明文消息“hello！”的加密過程及加密結果（密文）如下：

[明文 編碼 分組m 將m映射到橢圓曲線上的點Pm（xm， ym）， 取r=30， j=0…r-1 加密結果={P1，P3}，k=2.

P1=kG=2（68，85）=（21，47）， P2=kPKB=2（21，42）=（68，85）

P3=Pm+P2=Pm+（68，85） h 68 26 （77， 8）， j=9 {（21，47），（15，45）} e 65 06 （12， 5）， j=10 {（21，47），（51，41）} l 6c 21 （17， 1）， j=10 {（21，47），（72，55）} l 6c 44 （1， 0）， j=16 {（21，47），（15，45）} o 6f 27 （37， 8）， j=28 {（21，47），（65，66）} ！ 21 06 （12， 5）， j=10 {（21，47），（51，41）} 60 （37， 8）， j=17 {（21，47），（65，66）} 33 （25， 5）， j=14 {（21，47），（32，42）} 密文{（P1，P3）} （21，47）（15，45），（21，47）（51，41），（21，47）（72，55），（21，47）（15，45），（21，47）（65，66），（21，47）（51，41），（21，47）（65，66），（21，47）（32，42） ]

一個明文分組映射為橢圓曲線上的點加密之后的密文是兩個橢圓曲線的點，因此橢圓曲線加密傳輸的效率為50%。

3 結論

雖然還有很多不足，并且已經提出了大量的隱私保護方法，但仍然需要更多的研究，有許多挑戰需要克服。其中最重要的可能是對用戶隱私的適當保護的ECC算法。因此，本文提出改進了ECC的精確度，并使得橢圓曲線密碼的加密和解密過程的速度得到提高、點的純量乘法nP的計算時間復雜度提高，并力爭達到工業級別的ECC加解密教學演示系統、數字簽名教學演示系統。

參考文獻：

[1] Carron， L.P.， Morse Code： The Essential Language. Radio amateur's library. Vol. 69. 1986： American Radio Relay League.

[2] 于偉. 橢圓曲線密碼學若干算法研究[D].中國科學技術大學，2013.

[3] R. Schoof： Elliptic Curves over Finite Fields and the Computation of Square Roots mod p. Math. Comp.， 44（170）：483–494.Available at http：//www.mat.uniroma2.it/～schoof/ctpts.pdf

[4] 陳少云.拉格朗日中值定理的應用實例[J].河南教育學院學報（自然科學版），2017，26（3）：54-57.

[5] Chengwei Wang. Linear singular blending rational spline curve[P]. Computing， Control and Industrial Engineering （CCIE）， 2011 IEEE 2nd International Conference on，2011.

[6] 劉建成，楊曉靜，張玉.基于改進歐幾里德算法的（n，1，m）卷積碼識別[J].探測與控制學報，2012，34（1）：64-68.

[7] 劉麗濤，王刃峰.基于JavaScript+jQuery的網站設計與實現[J].電腦編程技巧與維護，2018（8）：40-41+53

[8] 易澤順. 基于Web的數據可視化工具設計與實現[D].華中師范大學，2017.

[9] 李明. 橢圓曲線和超橢圓曲線上標量乘的快速計算[D].山東大學，2012.

[10] 張曉軍.基于HTML5+CSS3.0+jQuery在移動電商APP開發中的應用[J].通訊世界，2015（6）：57.