橢圓加密算法的改進(jìn)算法研究與分析

王玲麗

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

關(guān)鍵詞：橢圓曲線;橢圓曲線加密;可視化工具;加密與解密

中圖分類號(hào)：TP311? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? 文章編號(hào)：1009-3044（2019）01-0054-03

本文主要是研究在安全性、計(jì)算效率方面有很大優(yōu)勢(shì)的一種公鑰密碼[1]體制——橢圓曲線加密算法及其應(yīng)用。其研討工作主要有以下幾個(gè)方向：HTML5+ jQuery框架 Web前端開發(fā)技術(shù)，橢圓曲線加密算法與數(shù)學(xué)有著密切的關(guān)系，尤其是對(duì)在有限域上的橢圓曲線形成的循環(huán)子群[2]、生成元的生成算法進(jìn)行了詳細(xì)的研究，因?yàn)樗鼈儗?duì)于實(shí)際的 ECC加密算法的實(shí)現(xiàn)非常關(guān)鍵。相關(guān)的算法和實(shí)現(xiàn)細(xì)節(jié)也在論文中進(jìn)行了展示;并改進(jìn)了雙點(diǎn)計(jì)算的方法[9]，從而提高了橢圓曲線密碼的加密和解密過程的速度。點(diǎn)nP的標(biāo)量運(yùn)算的時(shí)間復(fù)雜度從O（n）提高到log（n）。

1 橢圓曲線群運(yùn)算及可視化工具開發(fā)

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

1.1 橢圓曲線的可視化工具的開發(fā)

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

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

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

標(biāo)量乘法也稱為雙點(diǎn)運(yùn)算，即計(jì)算。當(dāng)變量n很大時(shí)，計(jì)算的時(shí)間復(fù)雜度也會(huì)變大。 圖1-3（a）是橢圓曲線上不相同的兩個(gè)點(diǎn)的相加; 圖1-3（ b）顯示了兩個(gè)相互反向元素的點(diǎn)的相加，即通過該點(diǎn)的橢圓的正切，切線和橢圓曲線交點(diǎn)處的對(duì)稱點(diǎn)是添加兩個(gè)相同點(diǎn)的結(jié)果; 圖1-3（ b）和1-3（ c）表示添加兩個(gè)相同的點(diǎn)（ P+ P）具有點(diǎn) P的雙標(biāo)量乘法（2 P）的結(jié)果在幾何上是一致的。

1.3 有限域GF（p）上橢圓曲線群點(diǎn)集的計(jì)算

假設(shè)有橢圓曲線[E97（2，3）：y2=x3+2x+3（mod97）]，其上有 P（3，6），如果在 P上執(zhí)行標(biāo)量乘法計(jì)算，你會(huì)發(fā)現(xiàn)結(jié)果只有五個(gè)不同的值（ O， P，2 P，3 P，4 P），并且循環(huán)出現(xiàn)。 可以證明的是純量乘法在加法運(yùn)算下是出于封閉狀態(tài)下的，換句話說，通過在有限域上的橢圓曲線的點(diǎn) P上迭代地執(zhí)行標(biāo)量乘法而獲得的一組點(diǎn)構(gòu)成循環(huán)子組。 P稱為循環(huán)子群的生成元（ generator）或基元（ base point）。

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

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

2 橢圓曲線加密算法的改進(jìn)與優(yōu)化

2.1 對(duì)橢圓曲線群純量乘法的優(yōu)化與改進(jìn)過程

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

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

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

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

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

② 計(jì)算該橢圓曲線的階N;

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

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

2.2 橢圓曲線加密解密算法

2.2.1 ECC的密鑰生成算法

假如通信雙方為A，B，發(fā)送方為A，接收方為B，要生成一個(gè)用戶B的公鑰、私鑰對(duì)的算法如下：

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

（2） 在Ep（a， b）中挑選生成元G=（x0，y0）， G應(yīng)使得滿足nG=O的最小n （n是G的階）是一個(gè)非常大的素?cái)?shù);

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

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

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

2.2.2 AàB實(shí)現(xiàn)保密通信，發(fā)送端A的加密算法

step1：將明文消息編碼成一個(gè)數(shù)m<p，將m鑲嵌到曲線上得點(diǎn)Pm=（xm，ym），再對(duì)點(diǎn)Pm做加密變換。

step2：在[1， n-1]內(nèi)選取一個(gè)隨機(jī)整數(shù)k， 計(jì)算點(diǎn)P1=kG。k是保密的，但接收端無須知道。

step3：根據(jù)B的公鑰PB， 計(jì)算點(diǎn)P2=kPB。

step4：A端傳送加密數(shù)據(jù)Cm={P1， Pm+P2}，其為2個(gè)點(diǎn)。

2.2.3 AàB實(shí)現(xiàn)保密通信，接收端B的解密算法

step1：接收方B接收到的是2個(gè)點(diǎn)kG， Pm+kPB ，其用自己的私鑰nB做如下計(jì)算：Pm+P2- nBP1即可解密，因?yàn)镻m+kPB- nBkG= Pm+knBG- nBkG=Pm。

step2：根據(jù)Pm，接收端再根據(jù)發(fā)送方的明文編碼的鑲嵌方法即可得到明文編碼m，進(jìn)一步得到明文。

2.3 橢圓曲線加解密算法的實(shí)現(xiàn)與結(jié)果分析

橢圓曲線密碼體制是基于有限域GF（89）上的E89（-1，0）： y2=x3-x mod 89，根據(jù)文獻(xiàn) [3]中的Schoof算法計(jì)算該橢圓曲線群的階為N=80，N的所有因子為n=1， 2， 4， 5， 8， 10， 16， 20， 40， 80。對(duì)于N的每個(gè)因子n=1， 2， 4， 5， 8， 10， 16， 20， 40， 80，計(jì)算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且其為素?cái)?shù)，計(jì)算其協(xié)因子h=N/n=16。隨機(jī)選擇橢圓曲線上一個(gè)P（12，5）且滿足hP=16P=（68，85）≠O，則選擇G=（68，85）作為用于橢圓曲線加密的循環(huán)子群的生成元。很顯然其階為n=5，因?yàn)閚G=5G=5*16P=80P=O。

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

發(fā)送端A加密時(shí)選擇一個(gè)秘密整數(shù)k=2，對(duì)明文消息“hello！”的加密過程及加密結(jié)果（密文）如下：

[明文 編碼 分組m 將m映射到橢圓曲線上的點(diǎn)Pm（xm， ym）， 取r=30， j=0…r-1 加密結(jié)果={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） ]

一個(gè)明文分組映射為橢圓曲線上的點(diǎn)加密之后的密文是兩個(gè)橢圓曲線的點(diǎn)，因此橢圓曲線加密傳輸?shù)男蕿?0%。

3 結(jié)論

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

參考文獻(xiàn)：

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

[2] 于偉. 橢圓曲線密碼學(xué)若干算法研究[D].中國科學(xué)技術(shù)大學(xué)，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] 陳少云.拉格朗日中值定理的應(yīng)用實(shí)例[J].河南教育學(xué)院學(xué)報(bào)（自然科學(xué)版），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] 劉建成，楊曉靜，張玉.基于改進(jìn)歐幾里德算法的（n，1，m）卷積碼識(shí)別[J].探測(cè)與控制學(xué)報(bào)，2012，34（1）：64-68.

[7] 劉麗濤，王刃峰.基于JavaScript+jQuery的網(wǎng)站設(shè)計(jì)與實(shí)現(xiàn)[J].電腦編程技巧與維護(hù)，2018（8）：40-41+53

[8] 易澤順. 基于Web的數(shù)據(jù)可視化工具設(shè)計(jì)與實(shí)現(xiàn)[D].華中師范大學(xué)，2017.

[9] 李明. 橢圓曲線和超橢圓曲線上標(biāo)量乘的快速計(jì)算[D].山東大學(xué)，2012.

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