2025/8/1215.4.1橢圓曲線密碼體制簡(jiǎn)介5.4橢圓曲線密碼體制（略）在1985年，由NealKoblitz和VictorMiller分別獨(dú)立的提出了可以在低要求的計(jì)算環(huán)境里做到高強(qiáng)度加密的公鑰算法，即橢圓曲線密碼體制（ECC）。從1998年起，一些國(guó)際標(biāo)準(zhǔn)化組織開始了對(duì)橢圓曲線密碼的標(biāo)準(zhǔn)化工作。橢圓曲線密碼算法在與RSA算法相同安全性的情況下，其密鑰短較短，160比特長(zhǎng)的密鑰相當(dāng)于RSA算法密鑰長(zhǎng)1024比特的安全性，因而有利于容量受限的存儲(chǔ)設(shè)備如智能卡等在安全領(lǐng)域的使用。加拿大的Certicom公司是一家ECC密碼技術(shù)公司，Certicom已經(jīng)對(duì)上百家企業(yè)應(yīng)用ECC密碼技術(shù)進(jìn)行授權(quán)，包括知名企業(yè)Cisco、摩托羅拉等。在我國(guó)，國(guó)家密碼管理局2010年12月提出了SM2橢圓曲線公鑰密碼算法，同時(shí)，還要求升級(jí)并重新修改已有的RSA算法的電子認(rèn)證系統(tǒng)和應(yīng)用系統(tǒng)等。中國(guó)國(guó)家密碼管理局發(fā)布了SM2橢圓曲線公鑰密碼算法標(biāo)準(zhǔn)。為滿足電子認(rèn)證服務(wù)系統(tǒng)等應(yīng)用需求，該標(biāo)準(zhǔn)推薦了一條256位的隨機(jī)橢圓曲線。NIST在標(biāo)準(zhǔn)FIPS186-2中，推薦了美國(guó)政府使用的15個(gè)不同安全級(jí)別的橢圓曲線。其包括5條二進(jìn)制域上的隨機(jī)橢圓曲線、5條二進(jìn)制域上的Koblitz曲線和5條素域上的隨機(jī)橢圓曲線。FIPS186-3中，對(duì)于橢圓曲線的參數(shù)選擇有進(jìn)一步的介紹.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實(shí)現(xiàn)。顯然該曲線關(guān)于x軸對(duì)稱。

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

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

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

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

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

y2≡x3+ax+b(modp)

(a,b∈GF(p),4a3+27b2(modp)≠0)定義的曲線，簡(jiǎn)單表示為Ep(a,b)。2025/8/1213例5-5：y2≡x3+x+6(mod11)是有限域GF(11)上的橢圓曲線，可以表示為E11(1,6)。下面看看y2≡x3+x+6(mod11)上的離散的點(diǎn)。由平方剩余的定義，容易知道，1，3，4，5，9是模11的平方剩余。求該曲線上離散的點(diǎn)可以通過令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……其他的點(diǎn)可以按這個(gè)方式求出。由前面的分析可知，該橢圓曲線上一共有12個(gè)點(diǎn)。

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

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

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

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

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

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

-公開密鑰:點(diǎn)Q

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

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

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

解：先要確定E中的點(diǎn)，以減少計(jì)算過程。對(duì)每個(gè)x∈Z11，首先計(jì)算z=x3+x+6mod11，然后再求同余方程y2≡zmod11的解來實(shí)現(xiàn)。由5.2.7的計(jì)算，可以得知，E中有13個(gè)點(diǎn)。選取r=(2,7)，計(jì)算2r。首先計(jì)算：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

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

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

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

類似地，還可以計(jì)算出nr，n≥1，計(jì)算結(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是一個(gè)循環(huán)群。2025/8/1225

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

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

加密運(yùn)算是：e(m,k)=(k(2,7),m+k(7,2))0≤k≤12,m是要加密的消息解密運(yùn)算是：d(c1,c2)=c2-7c1假設(shè)A要加密明文m=(10,9)(這是E上的一個(gè)點(diǎn))，如果隨機(jī)選擇k=3,A計(jì)算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收到密文后，解密計(jì)算如下：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)的時(shí)間是20世紀(jì)70年代，到現(xiàn)在已經(jīng)30多年了。

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

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

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

其他非對(duì)稱密碼體制簡(jiǎn)介（略）

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

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

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

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

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

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

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