1、1Rabin與與McEliece2011-03-312公鑰密碼公鑰密碼Rabin（基于二次剩余）（基于二次剩余）l Rabin密碼系統(tǒng)，是由密碼系統(tǒng)，是由M. Rabin設(shè)計(jì)的，是設(shè)計(jì)的，是RSA密密碼系統(tǒng)的一種改進(jìn)。碼系統(tǒng)的一種改進(jìn)。l RSA是基于指數(shù)同余的；是基于指數(shù)同余的；Rabin是基于二次同余。是基于二次同余。l Rabin密碼系統(tǒng)可以認(rèn)為是密碼系統(tǒng)可以認(rèn)為是e和和d為定值的為定值的RSA密碼密碼系統(tǒng)：系統(tǒng)：e = 2 ，d = 1/2。l 即，加密是即，加密是 c = m2 mod n，解密是解密是 m = c(1/2) mod n。 3Rabin的密鑰生成的密鑰生成l 選擇兩個(gè)

2、大的素?cái)?shù)選擇兩個(gè)大的素?cái)?shù)p和和q，要求，要求p和和q都是都是4的倍數(shù)加的倍數(shù)加3。l 計(jì)算計(jì)算n=pq。l Bob的公鑰是的公鑰是n，對(duì)外公布。，對(duì)外公布。l Bob的私鑰是（的私鑰是（p，q），自己私藏。），自己私藏。4Rabin的加密過程的加密過程l Alice欲發(fā)送明文欲發(fā)送明文m給給Bob，其中，其中0mn 。l Alice用用Bob的公鑰的公鑰n，計(jì)算：，計(jì)算：c=m2(modn)。l c為密文。為密文。5Rabin的解密過程的解密過程l Bob 收到密文收到密文c后，后，用自己的私鑰（用自己的私鑰（p，q）計(jì)算：）計(jì)算：).(mod);(mod4141qcmpcmqqpp6l 計(jì)算

3、：計(jì)算：m1， m2， m3， m4，l 滿足：滿足：0m1n；0m3n；0m2n； 0m4n；l m1(modp)=mp； m1(modq)=mq； m2(modp)=mp； m2(modq)=q-mq；m3(modp)=p-mp； m3(modq)=mq；m4(modp)=p-mp； m4(modq)=q-mq 。（4個(gè)數(shù)的計(jì)算使用孫子定理（中國(guó)剩余定理）。）7l 于是，真正的明文于是，真正的明文m一定就是一定就是4個(gè)數(shù)個(gè)數(shù) m1， m2， m3， m4 之中的一個(gè)。之中的一個(gè)。l 觀察觀察4個(gè)數(shù)，排除那些沒有意義的個(gè)數(shù)，排除那些沒有意義的“亂碼課文亂碼課文”。哪個(gè)是有意義的課文，哪個(gè)就是

4、真正的明文哪個(gè)是有意義的課文，哪個(gè)就是真正的明文m。l 解密完畢。解密完畢。8Rabin的解密正確性的解密正確性因?yàn)橐驗(yàn)閚=pq是兩個(gè)不同的素?cái)?shù)的乘積，所以，關(guān)于未是兩個(gè)不同的素?cái)?shù)的乘積，所以，關(guān)于未知數(shù)知數(shù)x的二次方程的二次方程x2= c (modn)恰好有恰好有4個(gè)不同的根個(gè)不同的根x，分別有以下形狀：，分別有以下形狀：一個(gè)根的一個(gè)根的(modp)、(modq)值是值是mp、mq；一個(gè)根的一個(gè)根的(modp)、(modq)值是值是mp、q-mq；一個(gè)根的一個(gè)根的(modp)、(modq)值是值是p-mp、mq；一個(gè)根的一個(gè)根的(modp)、(modq)值是值是p-mp、q-mq 。9l 4

5、個(gè)根中有一個(gè)是明文個(gè)根中有一個(gè)是明文m。l 如果把如果把(modp)、(modq)值為值為mp、mq的根叫做的根叫做m，則則(modp)、(modq)值為值為p-mp、q-mq的根就是的根就是n-m。l 另外兩個(gè)根的和也等于另外兩個(gè)根的和也等于n。即如果把一個(gè)叫做。即如果把一個(gè)叫做m，則另一個(gè)就是則另一個(gè)就是n-m。l 那么，那么， 4個(gè)不同的根怎樣計(jì)算呢？個(gè)不同的根怎樣計(jì)算呢？如果僅僅知道如果僅僅知道n，而不知道分解式，而不知道分解式n=pq，則無法，則無法計(jì)算計(jì)算mp和和mq，因而無法計(jì)算這，因而無法計(jì)算這4個(gè)不同的根。個(gè)不同的根。10l 如果知道了如果知道了n的分解式的分解式n=pq，則

6、能夠計(jì)算，則能夠計(jì)算mp和和mq。再由再由mp和和mq計(jì)算計(jì)算4個(gè)根，使用的是著名的孫子定個(gè)根，使用的是著名的孫子定理（中國(guó)剩余定理）。理（中國(guó)剩余定理）。l 最后，要判斷哪一個(gè)根是真正的明文。最后，要判斷哪一個(gè)根是真正的明文。一般，真正的明文都具有語言含義，而其它的根一般，真正的明文都具有語言含義，而其它的根則是沒有語言含義的則是沒有語言含義的“亂碼課文亂碼課文”。當(dāng)然也有例。當(dāng)然也有例外，比如當(dāng)明文是一副圖象的編碼時(shí)，明文也是外，比如當(dāng)明文是一副圖象的編碼時(shí)，明文也是沒有語言含義的沒有語言含義的“亂碼課文亂碼課文”。11Rabin的安全性原理的安全性原理l 攻擊者攻擊者Eve截獲了密文截獲

7、了密文c。 Eve還知道還知道Bob的公鑰的公鑰n，也知道明文也知道明文m滿足方程滿足方程c=m2(modn)。l 但是他不知道但是他不知道n的分解式的分解式n=pq，無法計(jì)算，無法計(jì)算mp和和mq，進(jìn)一步無法計(jì)算進(jìn)一步無法計(jì)算4個(gè)根。個(gè)根。l 求求n的分解式的分解式n=pq是大數(shù)分解問題。是大數(shù)分解問題。12RSA與與Rabin比較比較比較項(xiàng)目RSARabin公鑰(n, e)n私鑰d(p, q)加密算法c=me(modn)c=m2(modn)解密算法m=cd(modn)若干步安全基礎(chǔ)大數(shù)分解問題的困難性大數(shù)分解問題的困難性13McEliece公鑰密碼（基于糾錯(cuò)碼）公鑰密碼（基于糾錯(cuò)碼）l 1

8、978年年McEliece提出利用糾錯(cuò)碼構(gòu)造公鑰密碼體制。提出利用糾錯(cuò)碼構(gòu)造公鑰密碼體制。l 由于糾錯(cuò)碼依賴多余度而造成數(shù)據(jù)擴(kuò)展，而密碼中由于糾錯(cuò)碼依賴多余度而造成數(shù)據(jù)擴(kuò)展，而密碼中則不希望這樣做，又由于其密鑰量太大，致使這類則不希望這樣做，又由于其密鑰量太大，致使這類體制未能得到廣泛研究。體制未能得到廣泛研究。l 當(dāng)有擾信道的安全受到威脅時(shí)，保密和糾錯(cuò)的組合當(dāng)有擾信道的安全受到威脅時(shí)，保密和糾錯(cuò)的組合可能會(huì)得到重視?？赡軙?huì)得到重視。14McEliece公鑰密碼公鑰密碼l 設(shè)設(shè)G 是二元是二元(n, k, d) Goppa碼的生成矩陣；碼的生成矩陣；其中其中n=2m， k=ntm=2mtm，

9、d=2t+1l G是是kn階矩陣階矩陣l 隨機(jī)選取隨機(jī)選取GF(2)上的上的k階可逆方陣階可逆方陣S和和n階置換矩陣階置換矩陣Pl 令令G = SGPl 則私鑰為：則私鑰為：S、G、P；公鑰為：公鑰為：G。15McEliece公鑰密碼公鑰密碼l 加密加密：c = mG+e，其中，其中e是重量為是重量為t的向量。的向量。l 解密解密：1. 計(jì)算計(jì)算c=cP-1=mSGPP-1 +e P-1 = mSG +e ；2. 對(duì)對(duì)c進(jìn)行糾錯(cuò)譯碼：進(jìn)行糾錯(cuò)譯碼： c=v+e ，其中其中v= mSG是碼字。是碼字。3. 求滿足求滿足v=mG 的的m，即，即m= mS。4. 計(jì)算計(jì)算m=mS-1。16McEli

10、ece的實(shí)現(xiàn)的實(shí)現(xiàn)l 建議碼長(zhǎng)為建議碼長(zhǎng)為1024，S為為500*500方陣，方陣，P是是1024*1024的置的置換方陣。換方陣。l 盡管盡管McEliece是最早的公鑰算法之一，該方案比是最早的公鑰算法之一，該方案比RSA快快三個(gè)數(shù)量級(jí)，至今未有攻擊成功的結(jié)果。三個(gè)數(shù)量級(jí)，至今未有攻擊成功的結(jié)果。l 然而，因其公鑰過于龐大，為然而，因其公鑰過于龐大，為1019比特長(zhǎng)，且密文擴(kuò)展比特長(zhǎng)，且密文擴(kuò)展過大，而不被接受。過大，而不被接受。l 它的貢獻(xiàn)：開拓了基于糾錯(cuò)碼的密碼。它的貢獻(xiàn)：開拓了基于糾錯(cuò)碼的密碼。17離散對(duì)數(shù)問題與離散對(duì)數(shù)問題與 ElGamal算法算法18離散對(duì)數(shù)問題離散對(duì)數(shù)問題離散對(duì)

11、數(shù)問題是指：離散對(duì)數(shù)問題是指：給定一個(gè)素?cái)?shù)給定一個(gè)素?cái)?shù)p，z*p上的一個(gè)生成元上的一個(gè)生成元g，及，及一個(gè)元素一個(gè)元素y，尋找整數(shù)，尋找整數(shù)x（0=x=p-2），使），使得得gx = ymod p。19離散對(duì)數(shù)問題離散對(duì)數(shù)問題續(xù)續(xù)l 給定一個(gè)素?cái)?shù)給定一個(gè)素?cái)?shù)p， z*p上的一個(gè)生成元上的一個(gè)生成元g， 及一個(gè)元素及一個(gè)元素y，l 尋找整數(shù)尋找整數(shù)x（0=x=p-2），），l 使得使得gx = ymod p。20DiffieHellman問題問題l 給定一個(gè)素?cái)?shù)給定一個(gè)素?cái)?shù)p，z*p上的一個(gè)生成元上的一個(gè)生成元g，及元，及元素素y1 ga mod p ， y2 gb mod p ，求：求： y

12、gab mod p。l DH問題顯而易見的難解性構(gòu)成了許多密碼體問題顯而易見的難解性構(gòu)成了許多密碼體制的安全性基礎(chǔ)。制的安全性基礎(chǔ)。21ElGamal公鑰密碼公鑰密碼ElGamal的密鑰生成的密鑰生成l 選擇一個(gè)大的素?cái)?shù)選擇一個(gè)大的素?cái)?shù)p。選擇選擇g，1g p。選擇選擇x，1x p-1。l 計(jì)算計(jì)算y=gxmod p。l Bob的公鑰是的公鑰是(p, g, y)，對(duì)外公布。，對(duì)外公布。Bob的私鑰是的私鑰是x，自己私藏。，自己私藏。22ElGamal的加密過程的加密過程l Alice欲發(fā)送明文欲發(fā)送明文m給給Bob，其中，其中0mp 。l Alice選擇隨機(jī)數(shù)選擇隨機(jī)數(shù)k，(k, p1)=1，

13、計(jì)算：，計(jì)算：y1=g kmodpl 再用再用Bob的公鑰的公鑰y，計(jì)算：，計(jì)算：y2=mykmod pl 密文由密文由y1、y2級(jí)連構(gòu)成，即密文級(jí)連構(gòu)成，即密文c=y1|y2。23ElGamal的解密過程的解密過程l Bob 收到密文收到密文c后，用自己的私鑰后，用自己的私鑰x計(jì)算計(jì)算 m=y2/y1x =myk/(gk)x =mgxk/gxk modp 。24ElGamal特性特性l 特點(diǎn)：密文由明文特點(diǎn)：密文由明文m和隨機(jī)數(shù)和隨機(jī)數(shù)k來定，來定，因而是非確定性加密，一般稱之為隨機(jī)化加密，因而是非確定性加密，一般稱之為隨機(jī)化加密，對(duì)同一明文由于不同時(shí)刻的隨機(jī)數(shù)對(duì)同一明文由于不同時(shí)刻的隨機(jī)數(shù)

14、k不同而給出不同而給出不同的密文。不同的密文。l 代價(jià)：使數(shù)據(jù)擴(kuò)展一倍。代價(jià)：使數(shù)據(jù)擴(kuò)展一倍。l 安全性：基于離散對(duì)數(shù)的困難性。安全性：基于離散對(duì)數(shù)的困難性。25ElGamal數(shù)字簽名數(shù)字簽名l密鑰生成：選擇一個(gè)大的素?cái)?shù)密鑰生成：選擇一個(gè)大的素?cái)?shù)p。選擇。選擇g為域?yàn)橛騁F(p)的本原元素。選擇正整數(shù)的本原元素。選擇正整數(shù)x。計(jì)算計(jì)算y=gx(modp)。lAlice的公鑰是（的公鑰是（p，g，y），）， 私鑰是私鑰是x。l設(shè)設(shè)Alice欲發(fā)消息欲發(fā)消息m給給Bob。26簽名簽名（1） Alice用用H將消息將消息m進(jìn)行處理，得進(jìn)行處理，得h=H(m)。（2） Alice選擇秘密隨機(jī)數(shù)選擇秘密

15、隨機(jī)數(shù)k，滿足，滿足0kp-1，且，且(k, p-1)=1，計(jì)算計(jì)算r=gk(modp)； s=(h-xr)k-1(mod (p1)。（3） Alice將將(m，r，s)發(fā)送給發(fā)送給Bob。27驗(yàn)證驗(yàn)證接收方接收到消息接收方接收到消息m和簽名和簽名(r,s)后：后：（1） 計(jì)算計(jì)算h=H(m)。（2） 用用Alice的公鑰，的公鑰，檢驗(yàn)是否檢驗(yàn)是否yrrs=gH(m) ( mod p)。若是則若是則(m，r，s)是是Alice發(fā)送的簽名消息。發(fā)送的簽名消息。28課程報(bào)告：課程報(bào)告：4月月19日日 交交或或4月月28號(hào)下午號(hào)下午5,6節(jié)交至三樓休息室節(jié)交至三樓休息室29通信網(wǎng)的安全與保密通信網(wǎng)的

16、安全與保密課程報(bào)告課程報(bào)告 論文要求：論文要求： 2000- 4000字：標(biāo)題字：標(biāo)題1+黑體，正文宋體黑體，正文宋體5號(hào)字。號(hào)字。 公式表格不能出現(xiàn)圖片粘貼。公式表格不能出現(xiàn)圖片粘貼。 頁面要求：頁面要求：A4紙，手寫或打??；紙，手寫或打??； 題目題目(中、英文中、英文)； 姓名、學(xué)號(hào)；姓名、學(xué)號(hào)； 中英文摘要；中英文摘要； 中英文關(guān)鍵詞；中英文關(guān)鍵詞； 對(duì)該課程或該課題的個(gè)人見解與心得體會(huì)；（不少于對(duì)該課程或該課題的個(gè)人見解與心得體會(huì)；（不少于500字）字） 正文；（討論該課題下的密碼學(xué)技術(shù)問題）正文；（討論該課題下的密碼學(xué)技術(shù)問題） 參考文獻(xiàn)。參考文獻(xiàn)。 30例例31論題舉例：論題舉例：

17、1、有關(guān)分組密碼、有關(guān)分組密碼(比如：搜集資料自學(xué)關(guān)于比如：搜集資料自學(xué)關(guān)于IDEA的的內(nèi)容，試比較內(nèi)容，試比較DES與與IDEA兩個(gè)分組加密標(biāo)準(zhǔn)的兩個(gè)分組加密標(biāo)準(zhǔn)的設(shè)計(jì)思想、輪函數(shù)、效率及安全性等方面的異設(shè)計(jì)思想、輪函數(shù)、效率及安全性等方面的異同。同。)2、序列密碼及其在安全通信中的應(yīng)用。、序列密碼及其在安全通信中的應(yīng)用。3、RFID中認(rèn)證協(xié)議的安全性與隱私保護(hù)。中認(rèn)證協(xié)議的安全性與隱私保護(hù)。4、RSA公鑰加密算法安全性討論。公鑰加密算法安全性討論。5、討論數(shù)字簽名的應(yīng)用。、討論數(shù)字簽名的應(yīng)用。32論題以下任選：論題以下任選：6、如何設(shè)計(jì)一個(gè)安全的可恢復(fù)消息的數(shù)字簽名方、如何設(shè)計(jì)一個(gè)安全的可

18、恢復(fù)消息的數(shù)字簽名方案。案。7、有關(guān)、有關(guān)AES算法的研究和討論。算法的研究和討論。8、Rabin體制如何做簽名？體制如何做簽名？9、如何實(shí)現(xiàn)三方或多方的、如何實(shí)現(xiàn)三方或多方的DiffieHellman密鑰交密鑰交換？換？10、分析、分析DiffieHellman密鑰交換可能會(huì)遭受什密鑰交換可能會(huì)遭受什么攻擊？如何避免？么攻擊？如何避免？11、課堂相關(guān)內(nèi)容自定論題。、課堂相關(guān)內(nèi)容自定論題。 33Test1、DES的分組長(zhǎng)度、密鑰長(zhǎng)度。一輪迭代的結(jié)構(gòu)。的分組長(zhǎng)度、密鑰長(zhǎng)度。一輪迭代的結(jié)構(gòu)。2、AES的分組長(zhǎng)度、密鑰長(zhǎng)度。的分組長(zhǎng)度、密鑰長(zhǎng)度。3、寫出、寫出RSA算法的密鑰生成、加密和解密各步驟。

19、算法的密鑰生成、加密和解密各步驟。4、寫出、寫出RSA數(shù)字簽名算法。數(shù)字簽名算法。（可以翻書，不能相互討論。）（可以翻書，不能相互討論。）34橢圓曲線公鑰密碼學(xué)橢圓曲線公鑰密碼學(xué)Elliptic Curve Cryptography35橢圓曲線公鑰密碼橢圓曲線公鑰密碼ECC 橢圓曲線橢圓曲線(Elliptic curve)作為代數(shù)幾何中的重要作為代數(shù)幾何中的重要問題已有問題已有100多年的研究歷史多年的研究歷史 1985年，年，N. Koblitz和和V. Miller獨(dú)立將其引入密獨(dú)立將其引入密碼學(xué)中，成為構(gòu)造公鑰密碼體制的一個(gè)有力工具。碼學(xué)中，成為構(gòu)造公鑰密碼體制的一個(gè)有力工具。 利用有限

20、域利用有限域GF(2n )上的橢圓曲線上點(diǎn)集所構(gòu)成的上的橢圓曲線上點(diǎn)集所構(gòu)成的群上定義的離散對(duì)數(shù)系統(tǒng)，可以構(gòu)造出基于有限群上定義的離散對(duì)數(shù)系統(tǒng)，可以構(gòu)造出基于有限域上離散對(duì)數(shù)的一些公鑰體制域上離散對(duì)數(shù)的一些公鑰體制-橢圓曲線離散對(duì)橢圓曲線離散對(duì)數(shù)密碼體制數(shù)密碼體制(ECDLC )，如，如Diffie-Hellman，ElGamal，Schnorr，DSA等。等。36續(xù)續(xù) 1010余年的研究，尚未發(fā)現(xiàn)明顯的弱點(diǎn)。余年的研究，尚未發(fā)現(xiàn)明顯的弱點(diǎn)。 獲得同樣的安全性，密鑰長(zhǎng)度較獲得同樣的安全性，密鑰長(zhǎng)度較RSARSA短得多短得多 被被IEEEIEEE公鑰密碼標(biāo)準(zhǔn)公鑰密碼標(biāo)準(zhǔn)P1363P1363采用采

21、用37橢圓曲線公鑰密碼橢圓曲線公鑰密碼ECCl 有限域上有限域上滿足方程滿足方程y2+axy+by=x3+cx2+dx+e的所有點(diǎn)的所有點(diǎn)P=(x, y)，加上一個(gè)，加上一個(gè)“無窮遠(yuǎn)點(diǎn)無窮遠(yuǎn)點(diǎn)”，構(gòu)成的，構(gòu)成的集合稱為一個(gè)集合稱為一個(gè)“橢圓曲線橢圓曲線”。（其中方程中的常數(shù)（其中方程中的常數(shù)a、b、c、d、e需要滿足一些簡(jiǎn)需要滿足一些簡(jiǎn)單的條件。）單的條件。）l 該該“橢圓曲線橢圓曲線”上的所有點(diǎn)之間可以定義一種特殊上的所有點(diǎn)之間可以定義一種特殊的的“加法加法”，記為，記為“+” ：P+Q=R。 “橢圓曲線橢圓曲線”上的點(diǎn)關(guān)于此上的點(diǎn)關(guān)于此“加法加法”構(gòu)成交換群（構(gòu)成交換群（Abel群）。群）

22、。38橢圓曲線加法的定義橢圓曲線加法的定義l 如果其上的如果其上的3個(gè)點(diǎn)位于同一直線上，那么它們的和個(gè)點(diǎn)位于同一直線上，那么它們的和為為O。l O為加法單位元，即對(duì)為加法單位元，即對(duì)ECC上任一點(diǎn)上任一點(diǎn)P,有有P+O=Pl 設(shè)設(shè)P1=(x,y)是是ECC上一點(diǎn)，加法逆元定義為上一點(diǎn)，加法逆元定義為P2= -P1=(x,-y)39橢圓曲線離散對(duì)數(shù)問題橢圓曲線離散對(duì)數(shù)問題 橢圓曲線上一個(gè)點(diǎn)橢圓曲線上一個(gè)點(diǎn)P的的k倍表示為倍表示為 P+P+（k個(gè)點(diǎn)個(gè)點(diǎn)P “相加相加”），記為），記為kP。 橢圓曲線上一個(gè)點(diǎn)橢圓曲線上一個(gè)點(diǎn)P的所有倍數(shù)點(diǎn)組成了橢圓曲線的子集，該的所有倍數(shù)點(diǎn)組成了橢圓曲線的子集，該子

23、集是該橢圓曲線關(guān)于該子集是該橢圓曲線關(guān)于該“加法加法”的循環(huán)子群。的循環(huán)子群。 給定給定“橢圓曲線橢圓曲線”上的點(diǎn)上的點(diǎn)P，給定整數(shù)，給定整數(shù)k，計(jì)算，計(jì)算“kP=？”是容是容易的。（折半相加）易的。（折半相加） 給定給定“橢圓曲線橢圓曲線”上的兩個(gè)點(diǎn)上的兩個(gè)點(diǎn)P和和Q，求整數(shù)，求整數(shù)“？P=Q”是困難是困難的。的。這個(gè)問題稱為這個(gè)問題稱為橢圓曲線上的離散對(duì)數(shù)問題橢圓曲線上的離散對(duì)數(shù)問題。40有限域上的橢圓曲線有限域上的橢圓曲線 曲線方程中的所有系數(shù)都是某一有限域曲線方程中的所有系數(shù)都是某一有限域GF( (p) )中中的元素的元素( (p為一大素?cái)?shù)為一大素?cái)?shù)) )，最為常用的曲線方程為，最為常

24、用的曲線方程為y2=x3+ax+b mod(p) (a,bGF(p),4a3+27b20 mod p) 我們感興趣的是在第一象限的整數(shù)點(diǎn)。我們感興趣的是在第一象限的整數(shù)點(diǎn)。 設(shè)設(shè)Ep(a,b)表示表示ECC上點(diǎn)集：上點(diǎn)集：(x,y)|0 xp,0 yp,且且x,y均為整數(shù)均為整數(shù) 并上并上 O. 41有限域上的橢圓曲線有限域上的橢圓曲線 例：例：p=23,a=b=1, 4a3+27b2=8 0 (mod23), (mod23),方程為方程為y2=x3+x+1 mod(mod(p) )，圖形為連續(xù)圖形。，圖形為連續(xù)圖形。42有限域上橢圓曲線點(diǎn)集產(chǎn)生方法有限域上橢圓曲線點(diǎn)集產(chǎn)生方法 對(duì)每一對(duì)每一x

25、(0 xp且且x為整數(shù)），計(jì)算為整數(shù)），計(jì)算S=x3+ax+b mod p 決定求出的值決定求出的值S在模在模p下是否有平方根，下是否有平方根，如果沒有則橢圓曲線上沒有與這一如果沒有則橢圓曲線上沒有與這一x對(duì)應(yīng)的點(diǎn)；對(duì)應(yīng)的點(diǎn)；如果有，則求出兩個(gè)平方根。如果有，則求出兩個(gè)平方根。43Ep(a,b)上加法上加法 如果如果P,Q EP,Q Ep p(a,b)(a,b) P+O=PP+O=P 如果如果P P(x,y),(x,y),則則(x,y)+(x,-y)(x,y)+(x,-y)OO P P(x(x1 1,y,y1 1),Q= (x),Q= (x2 2,y,y2 2),P-Q,P+Q=),P-Q,P

26、+Q= (x(x3 3,y,y3 3) ) x x3 3=l l2 2-x-x1 1-x-x2 2（mod pmod p） y y3 3=l l(x(x1 1-x-x3 3)-y)-y1 1 (mod p) (mod p)QPyaxQPxxyy121121223l44ECC上的密碼上的密碼 ECC上的離散對(duì)數(shù)問題上的離散對(duì)數(shù)問題 在在ECC構(gòu)成的交換群構(gòu)成的交換群Ep(a,b)上考慮方程上考慮方程QkP，P,QEp(a,b),kp. 由由k和和P求求Q容易，由容易，由P,Q求求k則是困難的。則是困難的。 由由ECC上離散對(duì)數(shù)問題可以構(gòu)造上離散對(duì)數(shù)問題可以構(gòu)造Diffie-Hellman密鑰交換

27、和密鑰交換和Elgamal密碼體制密碼體制45Diffie-HellmanDiffie-Hellman密鑰交換密鑰交換46橢圓曲線上的橢圓曲線上的D-HD-H密鑰交換密鑰交換 取一素?cái)?shù)取一素?cái)?shù)p2180,兩個(gè)參數(shù)兩個(gè)參數(shù)a,b,得到得到Ep(a,b). 取取Ep(a,b)的一個(gè)生成元的一個(gè)生成元G(x1,y1),要求要求G的階是的階是一個(gè)非常大的素?cái)?shù)。一個(gè)非常大的素?cái)?shù)。 Ep(a,b)和和G公開。公開。47橢圓曲線上的橢圓曲線上的D-HD-H密鑰交換密鑰交換 A選小于選小于n的整數(shù)的整數(shù)nA作為秘密鑰，并有作為秘密鑰，并有PA=nAG作為公鑰；作為公鑰；B秘密鑰秘密鑰nB，公鑰，公鑰PB =n

28、BG； A計(jì)算計(jì)算K=nAPB ，作為共享的秘密鑰，作為共享的秘密鑰 B計(jì)算計(jì)算KnBPA ，作為共享的秘密鑰，作為共享的秘密鑰 攻擊者如想獲得攻擊者如想獲得K，必須由，必須由PA和和G求出求出nA或或PB和和G求出求出nB 攻擊：攻擊：中間人攻擊中間人攻擊48中間人攻擊中間人攻擊A Eve B PA=nAG PE=nEG A Eve B PE=nEG PB=nBGA：K1nAPE nAnEG nEPAB：K2 nBPE nEPB49橢圓曲線密鑰協(xié)商橢圓曲線密鑰協(xié)商 橢圓曲線橢圓曲線Diffie-HellmanDiffie-Hellman密鑰協(xié)商；密鑰協(xié)商； 橢圓曲線橢圓曲線Diffie-He

29、llmanDiffie-Hellman問題問題(ECDHP)(ECDHP)：給定橢圓曲線上點(diǎn)給定橢圓曲線上點(diǎn)P P，aPaP，bPbP，計(jì)算，計(jì)算abPabP。 ECMQVKAECMQVKA：20032003年提出。年提出。50橢圓曲線密鑰協(xié)商橢圓曲線密鑰協(xié)商 AliceAlice和和BobBob約定共同的參數(shù)；約定共同的參數(shù)； AliceAlice的公私鑰對(duì)的公私鑰對(duì)(a(a，Q QA A) )，Q QA AaPaP； BobBob的公私鑰對(duì)的公私鑰對(duì)(b(b，Q QB B) )，Q QB BbPbP。 協(xié)議主要由兩步構(gòu)成協(xié)議主要由兩步構(gòu)成: :step1step1：交換會(huì)話密鑰；：交換會(huì)話

30、密鑰；step2step2：計(jì)算密鑰。：計(jì)算密鑰。51step1step1：交換會(huì)話密鑰：交換會(huì)話密鑰1)Alice1)Alice隨機(jī)選擇隨機(jī)選擇 ，計(jì)算，計(jì)算 ，并發(fā)送給并發(fā)送給BobBob；2)Bob2)Bob隨機(jī)選擇隨機(jī)選擇 ，計(jì)算，計(jì)算 ，發(fā)送給發(fā)送給AliceAlice；*qZa PaQA*qZb PbQB52step2step2：計(jì)算密鑰：計(jì)算密鑰lAliceAlice做如下計(jì)算：做如下計(jì)算：lBobBob做如下計(jì)算：做如下計(jì)算：);(AAQfu );(BAQfv ;mod)(qauasAA)(BABAQvQsK);(BBQfu );(ABQfv ;mod)(qbubsBB)(AB

31、ABQvQsKf是取是取x坐標(biāo)的函數(shù)坐標(biāo)的函數(shù)53Cont.Cont.l具備數(shù)據(jù)源認(rèn)證，可防止中間人攻擊；具備數(shù)據(jù)源認(rèn)證，可防止中間人攻擊；l能擴(kuò)展為多人密鑰協(xié)商系統(tǒng)。能擴(kuò)展為多人密鑰協(xié)商系統(tǒng)。54橢圓曲線公鑰加密橢圓曲線公鑰加密55ElGamal公鑰密碼公鑰密碼Bob的公鑰的公鑰(p, g, y)，私鑰，私鑰x。Alice選擇隨機(jī)數(shù)選擇隨機(jī)數(shù)k，(k, p1)=1，計(jì)算，計(jì)算y1=g kmodp，y2=mykmod p密文密文 c=y1|y2Bob 收到密文收到密文c后，計(jì)算后，計(jì)算m=y2/y1x=myk/(gk)x=mgxk/gxk modp 56ECDLP實(shí)例實(shí)例： Ep(a,b)，P，Q；問題：找到唯一的整數(shù)問題：找到唯一的整數(shù)k，使使 kP=Q。57ECC實(shí)現(xiàn)實(shí)現(xiàn)Elgamal密碼體制密碼體制 選取一條橢圓曲線，得到選取一條橢圓曲線，得到Ep(a,b)。將明文消息將明文消息通過編碼嵌入曲線上得到點(diǎn)通過編碼嵌入曲線上得到點(diǎn)Pm 取取Ep(a,b)的生成元的生成元G， Ep(a,b)和和G為公開參數(shù)為公開參數(shù) 用戶選取用戶選取nA為私鑰，為私鑰，PA=nAG為公鑰。為公鑰。 加密：選隨機(jī)正整數(shù)加密：選隨機(jī)正整數(shù)k，密文為：，密文為：Cm=