2025/8/1215.4.1橢圓曲線密碼體制簡介5.4橢圓曲線密碼體制（略）在1985年，由NealKoblitz和VictorMiller分別獨立的提出了可以在低要求的計算環(huán)境里做到高強度加密的公鑰算法，即橢圓曲線密碼體制（ECC）。從1998年起，一些國際標(biāo)準(zhǔn)化組織開始了對橢圓曲線密碼的標(biāo)準(zhǔn)化工作。橢圓曲線密碼算法在與RSA算法相同安全性的情況下，其密鑰短較短，160比特長的密鑰相當(dāng)于RSA算法密鑰長1024比特的安全性，因而有利于容量受限的存儲設(shè)備如智能卡等在安全領(lǐng)域的使用。加拿大的Certicom公司是一家ECC密碼技術(shù)公司，Certicom已經(jīng)對上百家企業(yè)應(yīng)用ECC密碼技術(shù)進行授權(quán)，包括知名企業(yè)Cisco、摩托羅拉等。在我國，國家密碼管理局2010年12月提出了SM2橢圓曲線公鑰密碼算法，同時，還要求升級并重新修改已有的RSA算法的電子認證系統(tǒng)和應(yīng)用系統(tǒng)等。中國國家密碼管理局發(fā)布了SM2橢圓曲線公鑰密碼算法標(biāo)準(zhǔn)。為滿足電子認證服務(wù)系統(tǒng)等應(yīng)用需求，該標(biāo)準(zhǔn)推薦了一條256位的隨機橢圓曲線。NIST在標(biāo)準(zhǔn)FIPS186-2中，推薦了美國政府使用的15個不同安全級別的橢圓曲線。其包括5條二進制域上的隨機橢圓曲線、5條二進制域上的Koblitz曲線和5條素域上的隨機橢圓曲線。FIPS186-3中，對于橢圓曲線的參數(shù)選擇有進一步的介紹.ECC和RSA安全性能比較2025/8/1245.4.2橢圓曲線（選講）橢圓曲線是指由Weierstrass方程：y2+a1xy+a3y=x3+a2x2+a4x+a6所確定的曲線。在公鑰密碼學(xué)中，主要用到兩種橢圓曲線：（1）素域Fp(p>3)上的橢圓曲線，可以表示為：y2=x3+ax+b(modp)其中a,b為整數(shù)，其判別式4a3+27b2≠0（2）域F(2n)(n≥1)上的橢圓曲線，可以表示為：y2+xy=x3+ax2+b1.橢圓曲線的定義2025/8/125圖5-1y2≡x3+x+6所表示的曲線本章的介紹以第一種橢圓曲線為主，如圖5-1是y2≡x3+x+6所表示的曲線，該圖可以用matlab實現(xiàn)。顯然該曲線關(guān)于x軸對稱。

2025/8/1262．橢圓曲線的加法

在橢圓曲線所在的平面上，定義一個稱為無窮遠點的元素，記為O，把它定義為加法的單位元。也即橢圓曲線上的點P和它相加：P+O=P。橢圓曲線的加法定義如下：如果橢圓曲線上的3個點位于同一直線上，則者三個點的和為O。設(shè)P1，P2為兩個關(guān)于x軸對稱的橢圓曲線上的點即P1=(x,y),P2=(x,-y)，則它們互為加法逆元。

由上面的加法定義，P1P2的連線的延長線為無窮遠，故P1，P2，O三點共線，由加法定義容易得：P1+P2+O=O，P1=-P2。2025/8/127設(shè)P和Q是橢圓曲線上x坐標(biāo)不同的兩個點，R=P+Q定義為：畫一條通過P,Q的直線與橢圓曲線交于P1,由加法的定義：

P+Q+R1=O。則P+Q=-R1=R，如圖5-2。圖5-2R=P+Q示意圖2025/8/128

點P的倍點定義為：過P點做橢圓曲線的切線，設(shè)與橢圓曲線交于R1,則P+P+R1=O,故2P=-R1=R。如圖5-3。圖5-3R=2P示意圖2025/8/129對于上述加法，可以通過以下方式理解：設(shè)橢圓曲線的方程為y2≡x3+ax+b，橢圓曲線上有點P(x1,y1),Q(x2,y2)，見圖5-2。則過Q和R點的直線的斜率為k=(y2-y1)/(x2-x1)，該直線可以表示為y=kx+c。通過把直線方程代人橢圓曲線方程，可以求得第三個交點的坐標(biāo)，取第三個點關(guān)于x軸的對稱點即為所求。圖5-2R=P+Q示意圖2025/8/1210對于倍點運算，則通過P(x1,y1)點做橢圓曲線的切線(見圖5-3)，則該切線的斜率可以如下求得:對y2≡x3+ax+b兩邊求導(dǎo)數(shù)得：2yy’=3x2+a,k=y’=(3x2+a)/2y通過P點的橢圓曲線的切線就可以表示為y=kx+c,通過把直線方程代入橢圓曲線方程，可以求得直線與橢圓曲線的另一個交點的坐標(biāo)，取該點關(guān)于x軸的對稱點即為所求。圖5-3R=2P示意圖2025/8/1211通過以上推導(dǎo)，可以得出橢圓曲線y2=x3+ax+b上的點的加法運算規(guī)則，這個規(guī)則可以定義為：2025/8/12125.4.3有限域上的橢圓曲線有限域GF(p)上的橢圓曲線是由方程：

y2≡x3+ax+b(modp)

(a,b∈GF(p),4a3+27b2(modp)≠0)定義的曲線，簡單表示為Ep(a,b)。2025/8/1213例5-5：y2≡x3+x+6(mod11)是有限域GF(11)上的橢圓曲線，可以表示為E11(1,6)。下面看看y2≡x3+x+6(mod11)上的離散的點。由平方剩余的定義，容易知道，1，3，4，5，9是模11的平方剩余。求該曲線上離散的點可以通過令x=0,1,…,10,求得y2≡6,8,5,3,8,4,8,4,9,7,4(mod11).故該橢圓曲線上的有(2,4)(2,7)(3,5)(3,6)(5,2)(5,9)(7,2)(7,9)(8,3)(8,8)(10,2)(10,9)。-求解方法舉例如下：當(dāng)x=0,y2≡6mod11，6不是模11的平方剩余，無解；當(dāng)x=1,y2≡8mod11，8不是模11的平方剩余，無解；當(dāng)x=2,y2≡8+2+6≡5mod11,5是模11的平方剩余，y≡±4mod11……其他的點可以按這個方式求出。由前面的分析可知，該橢圓曲線上一共有12個點。

這12個點的分布如圖5-4所示，圖5-4中左下標(biāo)起點是(0,0)點。對于同一條橢圓曲線，y2≡x3+ax+b，p取不同的值，點的分布也不同。圖5-4y2≡x3+x+6(mod11)所表示的曲線2025/8/1215通過比較y2≡x3+x+6在平面的曲線（見圖5-1所示）和y2≡x3+x+6(mod11)在平面上的點（如圖5-4所示），直觀感覺沒有太多的聯(lián)系。圖5-1y2≡x3+x+6所表示的曲線圖5-4y2≡x3+x+6(mod11)所表示的曲線2025/8/1216對于同一條橢圓曲線，在不同的有限域上（即p取不同的值），點的個數(shù)是有差別的，當(dāng)p很大時，雖然離散點的個數(shù)是確定的，離散點的分布情況看上去也沒有什么規(guī)律。

2025/8/1217以y2≡x3+x+6(mod11)為例子，選取P=(2,7)，計算2P。首先計算：k=(3×22+1)(2×7)-1mod11≡8于是，x3=82-2-2mod11≡5,y3=8×(2-5)-7mod11≡2因此，2P=(5,2)。再計算：3P=2P+P=(5,2)+(2,7)，

先計算k=(7-2)(2-5)-1mod11≡2。于是，x3=22-5-2mod11≡8,y3=2×(5-8)-2mod11≡3因此，3P=(8,3)。

計算完畢后，可以通過把2P=(5,2),3P=(8,3)代入到y(tǒng)2≡x3+x+6(mod11)中驗證等式成立否，

如果不成立，則要檢查計算過程的錯誤。橢圓曲線密碼體制-原理-橢圓曲線離散對數(shù)問題

已知橢圓曲線E和點P，隨機生成一個整數(shù)d，容易計算:Q=d*P，但給定Q和P,計算d就相對困難。（1）ECC密碼體制的建立選取:一個基域GF(p);定義在該基域上的橢圓曲線Ep(a,b);E上的一個擁有素數(shù)階n的點P。其中有限域GF(p)，橢圓曲線參數(shù)a,b，點P和階n都是公開信息。（2）密鑰的生成在區(qū)間[1,n-1]中隨機選取一個整數(shù)d計算:Q=d*P實體的

-公開密鑰:點Q

-實體的私鑰:整數(shù)d待發(fā)送消息（A→B）：M-①查找B的公開密鑰：Q-②將消息M表示成一個域元素:m-③在區(qū)間[1,n-1]中隨機選取一個整數(shù)k（3）加密過程-④計算點:(x1,y1)=kP-⑤計算點:(x2,y2)=kQ，如果x2=0，則返回第③步-⑥計算:c=mx2-⑦傳送加密數(shù)據(jù)(x1,y1,c)給B

當(dāng)實體B解密從A收到的密文(x1,y1,c)時，執(zhí)行步驟：-使用私鑰d，計算點:(x2,y2)=d(x1,y1)-計算，恢復(fù)出消息m（4）解密過程2025/8/12215.4.4橢圓曲線上的ElGamal密碼體制（選講）（1）先由系統(tǒng)選取一條橢圓曲線，該橢圓曲線上的點形成了循環(huán)群E，G∈E是橢圓曲線上的一個點，N是點G在循環(huán)群E的階，即NG=O。（2）用戶選擇一個整數(shù)a，0<a<N，計算β=aG,a保密，但將β公開。即{a,G}是私鑰，{a,β}是公鑰，所選擇的橢圓曲線也是公開的。（3）假定把明文消息m嵌入到群E的點Pm上。當(dāng)消息發(fā)送者欲向A發(fā)送m，可求得一對數(shù)偶(C1,C2)，其中C1=kG,C2=Pm+kβ,k是隨機產(chǎn)生的整數(shù)。（4）A收到(C1,C2)后，計算C2-aC1得到消息Pm，因為C2-aC1=(Pm+kβ)－a(kG)=Pm。

可以看到，如同ElGamal密碼體制一樣，它也是一個不確定性算法，對于一個消息m，加密過程中k的選取不一樣，則加密所得的密文也不同。另外，該密碼體制也有密文“信息擴展”問題。2025/8/12235.4.5算法舉例例5-12：設(shè)p=11，E是由y2≡x3+x+6(mod11)所確定的有限域Z11上的橢圓曲線。

解：先要確定E中的點，以減少計算過程。對每個x∈Z11，首先計算z=x3+x+6mod11，然后再求同余方程y2≡zmod11的解來實現(xiàn)。由5.2.7的計算，可以得知，E中有13個點。選取r=(2,7)，計算2r。首先計算：k=(3×22+1)(2×7)-1mod11≡8于是，x3=82-2-2mod11≡5,y3=8×(2-5)-7mod11≡2因此，2r=(5,2)。2025/8/1224

再計算3r=2r+r=(5,2)+(2,7)，首先計算k=(7-2)(2-5)-1mod11≡2。

于是，x3=22-5-2mod11≡8,y3=2×(5-8)-2mod11≡3

因此，3r=(8,3)。

類似地，還可以計算出nr，n≥1，計算結(jié)果如下： r=(2,7)2r=(5,2)3r=(8,3)4r=(10,2) 5r=(3,6)6r=(7,9)7r=(7,2)8r=(3,5) 9r=(10,9)10r=(8,8)11r=(5,9)12r=(2,4) 13r=σ

因此，r=(2,7)是E的生成元，E是一個循環(huán)群。2025/8/1225

由上面的討論，可以確定E中的所有點，但這只是在例題中，實際應(yīng)用中，由于給定的橢圓曲線上的點數(shù)太多，無法完全列舉E中所有的點，也沒有必要列舉E中所有的點。

要確定z是否是一個模p的平方剩余，可以利用Euler準(zhǔn)則來實現(xiàn)，即如果p是一個奇素數(shù)，則z是模p平方剩余當(dāng)且僅當(dāng)z(p-1)/2≡1modp。當(dāng)p≡3mod4時，如果x是一個模p的平方剩余，則±z(p+1)/4≡1modp就是z的兩個模p的平方根，這是因為： (±z(p+1)/4)2≡z(p+1)/2modp≡zz(p-1)/2≡zmodp完成上面運算后，下面看例題。2025/8/1226例5-13：假設(shè)選取r=(2,7)，B的私鑰是7，有β=7r=(7,2).

加密運算是：e(m,k)=(k(2,7),m+k(7,2))0≤k≤12,m是要加密的消息解密運算是：d(c1,c2)=c2-7c1假設(shè)A要加密明文m=(10,9)(這是E上的一個點)，如果隨機選擇k=3,A計算c1=3r=3(2,7)=(8,3),c2=m+3β=(10,9)+3(7,2)=(10,9)+(3,5)

=9r+8r=17r=4r=(10,2)A發(fā)送（(8,3),(10,2)）給B.B收到密文后，解密計算如下：m=(10,2)-7(8,3)=(10,2)-21r=(10,2)-8r=(10,2)+5r=4r+5r=9r=(10,9)，于是恢復(fù)了明文。2025/8/12275.5

RSA、ElGamal及橢圓曲線密碼比較

RSA密碼體制是基于大數(shù)分解難題的，出現(xiàn)的時間是20世紀(jì)70年代，到現(xiàn)在已經(jīng)30多年了。

經(jīng)過比較長時間的使用和學(xué)者們的研究，從算法和計算角度看是安全的，只是隨著人類計算能力的提高，RSA算法中選取的參數(shù)(p,q)越來越大，現(xiàn)在普遍認為，n=pq的取值為2048比特是安全的，這相當(dāng)于600位的十進制整數(shù)。這也導(dǎo)致了加解密的運算量和存儲空間的增加，影響了其在便攜產(chǎn)品如手機/PDA等中的使用。

國際上一些標(biāo)準(zhǔn)化組織ISO,ITU及SWIFT等均己接受RSA體制作為標(biāo)準(zhǔn)。在Internet中所采用的PGP中也將RSA作為傳送會話密鑰和數(shù)字簽字的標(biāo)準(zhǔn)算法。由于RSA是簡單且，比較成熟的一種公鑰密碼體制，許多公司及研究團體都對它進行了實現(xiàn)。

ECC和RSA安全性能比較2025/8/1229ElGamal密碼體制是基于離散對數(shù)難題的，很多密碼算法如著名的密鑰交換算法DH(Diffie-Hellman)密鑰交換算法，以及后面學(xué)到的美國的數(shù)字簽名標(biāo)準(zhǔn)（DSA）就是基于離散對數(shù)問題的。ElGamal密碼體制在加密的時候要完成兩次模冪運算，密文的長度是消息長度的兩倍，在一定程度上影響了其廣泛使用。橢圓曲線密碼是ElGamal密碼體制在橢圓曲線上的應(yīng)用，優(yōu)點是在同等安全程度下，其密鑰比RSA和ElGamal要短得多。由現(xiàn)有的資料可知，ECC的密鑰長度為160比特時的安全強度與RSA的密鑰長度為1024比特時相當(dāng)，這對于存儲和通信帶寬受限時的應(yīng)用是一個很重要的優(yōu)點，比如PDA，IC卡，無線設(shè)備等，而且160比特的ECC的運算速度比1024比特的模運算快?；跈E圓曲線離散對數(shù)的加密算法和簽名算法被很多標(biāo)準(zhǔn)采用。2025/8/12305.6

其他非對稱密碼體制簡介（略）

除了前面介紹的基于大數(shù)分解難題的RSA密碼算法，基于離散對數(shù)難題的ELGamal密碼算法，基于橢圓曲線離散對數(shù)難題的橢圓曲線密碼算法外，在密碼學(xué)的發(fā)展歷史上，還有一些其他的非對稱密碼算法，對于非對稱密碼體制的發(fā)展產(chǎn)生了重大影響。-背包公鑰密碼體制背包算法，公鑰密碼體制的第一個算法是有Mercle和Hellman開發(fā)的背包算法，其安全性基于背包難題，這是一個NP完全問題。盡管這個算法后來發(fā)現(xiàn)是不安全的，但由于它證明了如何講NP完全問題用于公鑰密碼學(xué)，在公鑰密碼學(xué)的發(fā)展史上有過重大的影響。-Rabin公鑰密碼體制-NTRU公鑰密碼體制NTRU(NumberTheoryResearchUnit)公鑰密碼體制是由布朗大學(xué)3位數(shù)學(xué)家JeffreyHoffstein，J.Pipher和J.H.Silverman于1996年提出后，經(jīng)過幾年的迅速發(fā)展與完善，該算法在密碼學(xué)領(lǐng)域中受到了高度的重視，并在實際應(yīng)用中取得了良好的效果。NTRU公鑰算法的安全性不是基于傳統(tǒng)的困難問題，而是基于格基歸約的困難性,建立在多項式環(huán)的基礎(chǔ)之上的，從現(xiàn)有技術(shù)來看，在量子計算機中本算法仍是安全的。因此，從理論上來說為公鑰密碼體制開辟了一個新的領(lǐng)域。在以后的兩年中，DonCoppersmith，JohanHastad,AndrewOdlyzko,和AdiShamir等一些密碼學(xué)界的資深專家對算法進行了深入的安全性分析，均沒有發(fā)現(xiàn)NTRU算法存在有大的安全問題。在1998年，JeffreyHoffstein、JillPipher和JosephSilverman正式發(fā)表了論文“NTRU:ANewHighSpeedPublicKeyCrypto-system”。1999年,A.May和P.Nguyen于對該體制提出了一些攻擊方法，在2000年，JeffreyHoffstein和JosephSilverman在對原有NTRU算法進行了改進，在不降低算法安全強度的情況下，進一步提高了算法的運算速度。到目前為止，有很多討論NTRU算法安全性。但還沒有哪一種分析方法能破譯該密碼體制。在改進算法的同時，人們又開始研究NTRU簽名算法，由于NTRU的獨特特性，其不能象RSA之類的公鑰算法直接用于構(gòu)造簽名算法，因此借助于NTRU格的困難性，提出了多種NTRU簽名算法，如：NSS，R-NSS和NTRUSign等。

自2000年開始，美國IEEE標(biāo)準(zhǔn)化組織起草專門針對NTRU的標(biāo)準(zhǔn)P1363.1。在實際應(yīng)用方面，NTRU公司已對NTRU算法進行軟硬件實現(xiàn)，并已作出產(chǎn)品，銷售量很好。當(dāng)前，NTRU公司還看好的三個項目“手機/PDA”、“無線LAN”和“IC卡”其中，IC卡方面的應(yīng)用被放在了首位。

目前，在IC卡加密方面，主流方式是通用密鑰方式“DES”，但是這種方式“密鑰長度較短，而且一旦通用密鑰被盜則風(fēng)險相當(dāng)大”，因此NTRU認為市場上存在著向該公司開發(fā)的公開密鑰加密方式過渡的需求。注1：NTRU的安全性基于多項式、不同?；旌线\算的相互作用和從一個非常大的維數(shù)格中尋找最短向量的困難性。對現(xiàn)有的RSA、DSA等公鑰密碼體制而言，由于涉及到大數(shù)的模指運算，此運算所需存儲空間大、速度慢。NTRU只使用了簡單的模乘法和模求逆運算,因而它具有密鑰產(chǎn)生容易,加、解密速度快等特點。2025/8/1240

-基于有限自動機的公鑰密碼算法，這是由中國密碼學(xué)家陶仁冀提出的，該算法基于有限自動機理論。如同分解兩個大素數(shù)的乘積很困難一樣，要分解兩個有限自動機的合成也很困難。

-McEliece算法，該算法由McEliece在1978年提出，是一種基于代數(shù)編碼理論的公開密鑰密碼系統(tǒng)。其思想是構(gòu)造一個Goppa碼并將其偽裝成普通的線性碼。不過該算法的公開密鑰太龐大，加密后的密文長度為明文的兩倍，在一定程度上影響了它的廣泛應(yīng)用，故而研究的人也比較少。注2：就目前來說，NTRU的安全性和目前最有影響的RSA算法、橢圓曲線密碼體制(ECC)等算法是一樣安全的，且具有與RSA同等程度的安全性，能抵抗量子運算攻擊。

2025/8/1241多變量公鑰密碼體制（MultivariatePublicKeyCryptosystem，MPKC）被認為是這樣一種有希望的選擇。近年來，多變量公鑰密碼體制逐漸成為現(xiàn)代密碼學(xué)研究的熱點。多變量公鑰密碼體制的安全性是建立在求解有限域上隨機多變量多項式方程組是NP困難問題的論斷上。由于運算都是在較小的有限域上進行，所以多變量公鑰密碼體制中的計算速度非?？?。到目前為止，已經(jīng)研究出很多新的多變量公鑰密碼體制，這些多變量公鑰密碼體制當(dāng)中一些非常適用于諸如無線傳感器網(wǎng)絡(luò)和動態(tài)RFID標(biāo)簽等計算能力有限能力的設(shè)備。

2003年，一個多變量簽名體制——SFLASH已經(jīng)被歐洲NESSIE密碼計劃接受用于低耗智能卡的推薦算法。目前