第4章-公鑰密碼

1、現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC第第4章章 公鑰密碼公鑰密碼1.公鑰密碼體制簡(jiǎn)介公鑰密碼體制簡(jiǎn)介2. 數(shù)論簡(jiǎn)介數(shù)論簡(jiǎn)介3. RSA算法算法4. Rabin密碼體制密碼體制5. 橢圓曲線密碼體制橢圓曲線密碼體制現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC對(duì)稱算法對(duì)稱算法 知道如何加密知道如何加密=知道如何解密知道如何解密 知道如何驗(yàn)證，就基本知道如何假冒知道如何驗(yàn)證，就基本知道如何假冒 知其然就知其所以然知其然就知其所以然 加密和解密過(guò)程中的密鑰是一致的加密和解密過(guò)程中的密鑰是一致的加密算法明文密文不安全信道解密算法明文密鑰密鑰現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC對(duì)稱算法不適合于大規(guī)模使用對(duì)稱算法不

2、適合于大規(guī)模使用 未曾謀面，缺少以前的聯(lián)系未曾謀面，缺少以前的聯(lián)系 難以密鑰協(xié)商難以密鑰協(xié)商 用戶數(shù)目增多用戶數(shù)目增多 分發(fā)和管理密鑰（分發(fā)和管理密鑰（Key Management） 困難（多，變）困難（多，變） 安全性問(wèn)題（密鑰泄露）安全性問(wèn)題（密鑰泄露） 性能問(wèn)題（瓶頸）性能問(wèn)題（瓶頸）現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC密鑰交換協(xié)議m1m2skskAlice BobOscar 我們將討論我們將討論Alice 和和Bob怎樣通過(guò)交換協(xié)議共享一個(gè)密鑰怎樣通過(guò)交換協(xié)議共享一個(gè)密鑰.現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTCDiffie-Hellman密鑰交換密鑰交換 Diffie-Hellman密鑰

3、交換密鑰交換 公開(kāi)參數(shù)：大素?cái)?shù)公開(kāi)參數(shù)：大素?cái)?shù)P，本原元，本原元a 協(xié)議安全的基本思想?yún)f(xié)議安全的基本思想: 如果敵手能攻破某協(xié)議的安全性如果敵手能攻破某協(xié)議的安全性, 那么我們可以利用該敵手攻破一公認(rèn)的數(shù)學(xué)難題那么我們可以利用該敵手攻破一公認(rèn)的數(shù)學(xué)難題. 現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC非對(duì)稱算法非對(duì)稱算法/公鑰算法公鑰算法 非對(duì)稱密碼（公鑰密碼）算法想法的提出非對(duì)稱密碼（公鑰密碼）算法想法的提出 1976年，年，Diffie、Hellman在在密碼學(xué)的新方向密碼學(xué)的新方向（New Directions in Cryptography）一文中提）一文中提出來(lái)）出來(lái)） 非對(duì)稱密碼，也稱為公鑰

4、密碼算法。非對(duì)稱密碼，也稱為公鑰密碼算法。 Asymmetrical cryptography Public key cryptography現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC非對(duì)稱算法非對(duì)稱算法/公鑰算法公鑰算法 知道加密，但不知道解密知道加密，但不知道解密 原理：數(shù)學(xué)計(jì)算巨大（原理：數(shù)學(xué)計(jì)算巨大（RSA） 提供數(shù)字簽名提供數(shù)字簽名 提供秘密密鑰的密鑰管理提供秘密密鑰的密鑰管理 公開(kāi)公鑰，秘密保存私鑰公開(kāi)公鑰，秘密保存私鑰現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC2021-11-188 公鑰密碼體制的原理公鑰體制(Public key system) (Diffie和Hellman,1976)

5、每個(gè)用戶都有一對(duì)選定的密鑰(公鑰k1；私鑰k2)，公開(kāi)的密鑰k1可以像電話號(hào)碼一樣進(jìn)行注冊(cè)公布。主要特點(diǎn)： 加密和解密分開(kāi) 多個(gè)用戶加密的消息只能由一個(gè)用戶解讀，（用于公共網(wǎng)絡(luò)中實(shí)現(xiàn)保密通信） 只能由一個(gè)用戶加密消息而使多個(gè)用戶可以解讀（可用于認(rèn)證系統(tǒng)中對(duì)消息進(jìn)行數(shù)字簽字）。 無(wú)需事先分配密鑰?，F(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC2021-11-189 公鑰體制加密 公鑰體制加、解密公鑰體制加、解密 mm=D D ( (c c)=)=D DSKBSKB ( (E EPKBPKB( (mm) )安全保障安全保障從公開(kāi)鑰從公開(kāi)鑰PKPKB B和密文和密文c c要推出明文要推出明文mm或解密鑰或解密

6、鑰SKSKB B在計(jì)算上是在計(jì)算上是不可行的。不可行的。由于任一用戶都可用用戶由于任一用戶都可用用戶B B的公開(kāi)鑰的公開(kāi)鑰PKPKB B 向他發(fā)送機(jī)密消息，向他發(fā)送機(jī)密消息，因而密文因而密文c c不具有認(rèn)證性。不具有認(rèn)證性。發(fā)送者A加密算法PKB密鑰源SKB解密算法接收者B密碼分析員mcmmSKB現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC基于公鑰的加密過(guò)程基于公鑰的加密過(guò)程現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC1.1 公鑰密碼體制簡(jiǎn)介公鑰密碼體制簡(jiǎn)介對(duì)稱密碼體制：對(duì)稱密碼體制：保密性，運(yùn)算速度快，適合加密保密性，運(yùn)算速度快，適合加密 大量數(shù)據(jù)大量數(shù)據(jù)公鑰密碼體制：公鑰密碼體制：保密性，密鑰分配，認(rèn)證；

7、運(yùn)算保密性，密鑰分配，認(rèn)證；運(yùn)算 速度慢，適合加密少量數(shù)據(jù)。如：速度慢，適合加密少量數(shù)據(jù)。如： 用公鑰密碼加密傳送分組密碼的密鑰。用公鑰密碼加密傳送分組密碼的密鑰。(1) 公鑰密碼體制與對(duì)稱密碼體制比較公鑰密碼體制與對(duì)稱密碼體制比較:現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC公鑰密碼的理論基礎(chǔ)公鑰密碼的理論基礎(chǔ): 陷門單向函數(shù)陷門單向函數(shù)單向函數(shù)單向函數(shù): 已知已知x, 計(jì)算計(jì)算y使得使得y=f(x)容易容易; 已知已知y, 計(jì)算計(jì)算x使得使得y=f(x)是難解的。是難解的。陷門單向函數(shù)陷門單向函數(shù): t是與是與f有關(guān)的一個(gè)參數(shù)有關(guān)的一個(gè)參數(shù) 已知已知x, 計(jì)算計(jì)算y使得使得y=f(x)容易容易;

8、如果不知道如果不知道t，已知已知y, 計(jì)算計(jì)算x使得使得y=f(x)是難的，是難的， 但知道但知道t時(shí)，已知時(shí)，已知y, 計(jì)算計(jì)算x使得使得y=f(x)是容易的。是容易的。 參數(shù)參數(shù)t稱為陷門稱為陷門?，F(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC公鑰密碼算法應(yīng)滿足以下要求公鑰密碼算法應(yīng)滿足以下要求: 接收方接收方B產(chǎn)生密鑰對(duì)（產(chǎn)生密鑰對(duì)（PKB和和SKB）在計(jì)算上是在計(jì)算上是容易的。容易的。 發(fā)方發(fā)方A對(duì)消息對(duì)消息m加密以產(chǎn)生加密以產(chǎn)生密文密文c，即即c=EPKBm在計(jì)算上是容易的。在計(jì)算上是容易的。 收方收方B用自己的秘密鑰對(duì)用自己的秘密鑰對(duì)c解密，即解密，即m=DSKBc在在計(jì)算上是容易的。計(jì)算上

9、是容易的。公鑰密碼算法應(yīng)滿足的要求公鑰密碼算法應(yīng)滿足的要求現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC 敵手?jǐn)呈钟捎蒔KB求求SKB在計(jì)算上是不可行的。在計(jì)算上是不可行的。 敵手由敵手由密文密文c和和PKB恢復(fù)明文恢復(fù)明文m在計(jì)算上是不可在計(jì)算上是不可行的。行的。以上要求的本質(zhì)之處在于要求一個(gè)陷門單向函數(shù)。以上要求的本質(zhì)之處在于要求一個(gè)陷門單向函數(shù)。因此，研究公鑰密碼算法就是要找出合適的陷門單因此，研究公鑰密碼算法就是要找出合適的陷門單向函數(shù)。向函數(shù)?，F(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC （1）大整數(shù)分解問(wèn)題（）大整數(shù)分解問(wèn)題（factorization problem） 若已知兩個(gè)大素?cái)?shù)若已知兩個(gè)大

10、素?cái)?shù)p和和q，求，求n = pq是容易的，是容易的，只需一次乘法運(yùn)算，而由只需一次乘法運(yùn)算，而由n，求，求p和和q則是困難的，則是困難的，這就是大整數(shù)分解問(wèn)題。這就是大整數(shù)分解問(wèn)題。 （2）離散對(duì)數(shù)問(wèn)題（）離散對(duì)數(shù)問(wèn)題（discrete logarithm problem） 給定一個(gè)大素?cái)?shù)給定一個(gè)大素?cái)?shù)p，p 1含另一大素?cái)?shù)因子含另一大素?cái)?shù)因子q，則可構(gòu)造一個(gè)乘法群，它是一個(gè)則可構(gòu)造一個(gè)乘法群，它是一個(gè)p 1階循環(huán)群。設(shè)階循環(huán)群。設(shè)g是的一個(gè)生成元，是的一個(gè)生成元，1gp 1。已知。已知x，求，求y=gx mod p是容易的，而已知是容易的，而已知y、g、p，求，求x使得使得y=gx mod

11、p成立則是困難的，這就是離散對(duì)數(shù)問(wèn)題。成立則是困難的，這就是離散對(duì)數(shù)問(wèn)題。幾個(gè)困難問(wèn)題幾個(gè)困難問(wèn)題現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC （3）多項(xiàng)式求根問(wèn)題）多項(xiàng)式求根問(wèn)題 有限域有限域GF（p）上的一個(gè)多項(xiàng)式：）上的一個(gè)多項(xiàng)式： 已知已知 , p和和x，求，求y是容易的，而已知是容易的，而已知y, ，求，求x則是困難的，這就是多項(xiàng)式求則是困難的，這就是多項(xiàng)式求根問(wèn)題。根問(wèn)題。 011,.,naaa011,.,na aa1110( )modnnnyf xxaxa xap現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC （4）二次剩余問(wèn)題（）二次剩余問(wèn)題（quadratic residue problem）

12、 給定一個(gè)合數(shù)給定一個(gè)合數(shù)n和整數(shù)和整數(shù)a，判斷，判斷a是否為是否為mod n的二次剩余，這就是二次剩余問(wèn)題。在的二次剩余，這就是二次剩余問(wèn)題。在n的分解未知時(shí)，求的分解未知時(shí)，求 a mod n的解也是一個(gè)的解也是一個(gè)困難問(wèn)題。困難問(wèn)題。電子科技大學(xué)電子科技大學(xué)2x現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC （5）背包問(wèn)題（）背包問(wèn)題（knapsack problem） 給定向量給定向量A= ( ) ( 為正整數(shù)為正整數(shù))和和x = ( ) ( 0,1)，求和式：，求和式： 是容易的，而由是容易的，而由A和和S，求，求x則是困難的，這就則是困難的，這就是背包問(wèn)題，又稱子集和問(wèn)題。是背包問(wèn)題，又稱子

13、集和問(wèn)題。1 122( )nnsf xa xa xa x12,.,naaaia12,.,nxxxix現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC4.2 RSA密碼算法密碼算法 MIT三位年青學(xué)者三位年青學(xué)者Rivest，Shamir和和Adleman 在在1978年發(fā)現(xiàn)了一種用數(shù)論構(gòu)造雙鑰體制的方法，年發(fā)現(xiàn)了一種用數(shù)論構(gòu)造雙鑰體制的方法，稱作稱作MIT體制，后來(lái)被廣泛稱之為體制，后來(lái)被廣泛稱之為RSA體制。體制。 它既可用于加密、又可用于數(shù)字簽名。它既可用于加密、又可用于數(shù)字簽名。 RSARSA算法的安全性基于數(shù)論中大整數(shù)分解的困難算法的安全性基于數(shù)論中大整數(shù)分解的困難性性。現(xiàn)代密碼理論現(xiàn)代密碼理論-

14、UESTC現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC一個(gè)數(shù)學(xué)題一個(gè)數(shù)學(xué)題 求求3801的最后兩位數(shù)。的最后兩位數(shù)。現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC(1). 費(fèi)爾瑪定理費(fèi)爾瑪定理定理定理1 (Fermat)若若p是素?cái)?shù)，是素?cái)?shù)，a是正整數(shù)且是正整數(shù)且gcd(a, p)=1，則則ap-11 mod p。Fermat定理也可寫成如下形式：定理也可寫成如下形式： 設(shè)設(shè)p是素?cái)?shù)，是素?cái)?shù)，a是是任一正整數(shù)，則任一正整數(shù)，則apa mod p。(2). 歐拉函數(shù)歐拉函數(shù)設(shè)設(shè)n是一正整數(shù)，是一正整數(shù)，小于小于n且與且與n互素的正整數(shù)的個(gè)數(shù)互素的正整數(shù)的個(gè)數(shù)稱為稱為n的歐拉函數(shù)

15、的歐拉函數(shù)，記為，記為(n)。例如：例如： (6)=2 ，(7)=6 ，(8)=4。若若n是素?cái)?shù)，則顯然有是素?cái)?shù)，則顯然有(n)=n-1?，F(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC例如：例如： 由由21=37，得，得(21)=(3)(7)=26=12。(3). 歐拉定理歐拉定理定理定理3.（Euler） 若若a和和n互素，則互素，則a(n)1 mod n。歐拉函數(shù)的求法：歐拉函數(shù)的求法： （1）如果）如果n是素?cái)?shù)，則是素?cái)?shù)，則?(n)=n-1 （2）npq，其中，其中p，q為素?cái)?shù)，則為素?cái)?shù)，則?(n)=(p-1)(q-1) （3）12111( )(1)(1).(1)ipppnn現(xiàn)代密碼理論現(xiàn)代密碼理

16、論-UESTC4.3.1 算法描述算法描述-密鑰生成密鑰生成 選取兩互異大素?cái)?shù)選取兩互異大素?cái)?shù)p p和和q q 計(jì)算計(jì)算 n n=p pq q 和其歐拉函數(shù)值和其歐拉函數(shù)值 ( (n n)=()=(p p1)(1)(q q1) 1) 選一整數(shù)選一整數(shù)e e，1 1 e e ( (n n) )，使得，使得 gcd(gcd( ( (n n), ), e e)=1)=1 在模在模 ( (n n) )下，計(jì)算下，計(jì)算e e的逆元的逆元d d. . 即求即求d, d, 使得使得 e ed d 1 1 mod mod ( (n n) ) 以以( (n n，e e ) )為公鑰。為公鑰。d d 為秘密鑰。為

17、秘密鑰。 ( (p p, , q q不再需要，可以銷毀。不再需要，可以銷毀。) ) 現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC 加密 將明文分組，各組對(duì)應(yīng)的十進(jìn)制數(shù)mn, 計(jì)算 c =E(m) me mod n 解密 m = D(c) cd mod n現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTCRSA算法算法解密過(guò)程的正確性解密過(guò)程的正確性。證明：證明： 由加密過(guò)程知由加密過(guò)程知cme mod n，所以所以cd mod nmed mod n mk(n)+1 mod n分兩種情況：分兩種情況： m與與n互素互素，則由，則由Euler定理得定理得m(n)1 mod n,mk(n)1 mod n,mk(n)+1m

18、 mod n即即cd mod nm。加密：加密： cme mod n解密：解密：mcd mod n現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC由由gcd(m,q)=1及及Euler定理得定理得m(q)1 mod q，所以所以mk(q)1 mod q,mk(q)(p)1 mod q, mk(n)1 mod q因此存在一整數(shù)因此存在一整數(shù)r，使得使得mk(n)=1+rq，兩邊同乘以兩邊同乘以m=cp得得mk(n)+1=m+rcpq=m+rcn即即mk(n)+1m mod n，所以所以cd mod nm。(證畢證畢)qcnm 1 ,1 gcd(m,n)1, 不妨設(shè)不妨設(shè) m=cp，現(xiàn)代密碼理論現(xiàn)代密碼理論-

19、UESTC例例: p=7, q=17. n=pq=119, (n)=(p-1)(q-1)=96。取取e=5，滿足滿足1e(n)，且且gcd(n),e)=1。確定滿足確定滿足de=1 mod 96且小于且小于96的的d，因?yàn)橐驗(yàn)?75=385=496+1，故，故d=77。因此公鑰為因此公鑰為5, 119，私鑰為，私鑰為77, 119。設(shè)明文設(shè)明文m=19，則由加密過(guò)程得密文為則由加密過(guò)程得密文為c195 mod 1192476099 mod 11966解密為解密為6677mod 11919現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC1. RSA的加密與解密過(guò)程的加密與解密過(guò)程 RSA的加密、解密過(guò)程都為

20、求一個(gè)的加密、解密過(guò)程都為求一個(gè)整數(shù)的整數(shù)次整數(shù)的整數(shù)次冪冪，再取模再取模。如果按其含義直接計(jì)算，則中間結(jié)果。如果按其含義直接計(jì)算，則中間結(jié)果非常大，有可能超出計(jì)算機(jī)所允許的整數(shù)取值范圍。非常大，有可能超出計(jì)算機(jī)所允許的整數(shù)取值范圍。而用模運(yùn)算的性質(zhì)：而用模運(yùn)算的性質(zhì)：(ab) mod n=(a mod n)(b mod n) mod n就可減小中間結(jié)果。就可減小中間結(jié)果。4.3.2 RSA算法中的計(jì)算問(wèn)題算法中的計(jì)算問(wèn)題現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC 再者，考慮如何提高加、解密運(yùn)算中指數(shù)運(yùn)算的再者，考慮如何提高加、解密運(yùn)算中指數(shù)運(yùn)算的有效性。例如求有效性。例如求x16，直接計(jì)算的話需做

21、直接計(jì)算的話需做15次乘法。次乘法。然而如果重復(fù)對(duì)每個(gè)部分結(jié)果做平方運(yùn)算即求然而如果重復(fù)對(duì)每個(gè)部分結(jié)果做平方運(yùn)算即求x，x2，x4，x8，x16則只需則只需4次乘法。次乘法。求求am可如下進(jìn)行，其中可如下進(jìn)行，其中a，m是正整數(shù)：是正整數(shù)： 將將m表示為二進(jìn)制形式表示為二進(jìn)制形式bk bk-1b0，即即因此因此12012222kkkbbbbbmaaaaaa 現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTCd=1；For i=k downto 0 do d=(dd) mod n;if bi=1 then d=(da) mod nreturn d.m=bk2k+bk-12k-1+b12+b012012222k

22、kkbbbbbmaaaaaa 快速指數(shù)算法快速指數(shù)算法現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC2. RSA密鑰的產(chǎn)生密鑰的產(chǎn)生(1) 兩個(gè)大素?cái)?shù)兩個(gè)大素?cái)?shù)p、q的選取。的選取。 Miller-Rabin算法算法;(2) e的選取和的選取和d的計(jì)算。的計(jì)算。 選取滿足選取滿足1e0. 則則存在唯一的整數(shù)存在唯一的整數(shù)q, r使得使得 a=bq+r, 0 rb現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC定理定理 整數(shù)整數(shù)a, b互素互素 存在整數(shù)存在整數(shù) s, t 滿足滿足 s a + t b =1證證: 必要性顯然必要性顯然。充分性：已知充分性：已知s a + t b =1，則則a, b互素互素 設(shè)設(shè) d=

23、(a, b), 則則d|a, d|b, 有有d | s a + t b =1，則則d=1, 故故a, b互素互素 求乘法逆元：求乘法逆元：如果如果gcd(a, b)=1 ，則則b在在mod a下有乘法逆元下有乘法逆元, 即即存在一存在一x (xa)，使得使得bx1 mod a?，F(xiàn)代密碼理論現(xiàn)代密碼理論-UESTCRSA的安全性的安全性是基于是基于分解大整數(shù)的困難性假定分解大整數(shù)的困難性假定，如，如果果RSA的模數(shù)的模數(shù)n被成功地分解為被成功地分解為pq，則立即獲得則立即獲得(n)=(p-1)(q-1)，從而能夠確定從而能夠確定e模模(n)的乘法逆元的乘法逆元d，即即de-1 mod (n)，因

24、此攻擊成功。因此攻擊成功。4.3.3 RSA的安全性的安全性現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC 隨著人類計(jì)算能力的不斷提高，原來(lái)被認(rèn)為是不隨著人類計(jì)算能力的不斷提高，原來(lái)被認(rèn)為是不可能分解的大數(shù)已被成功分解?？赡芊纸獾拇髷?shù)已被成功分解。RSA129于于1994年年4月被成功分解月被成功分解RSA130于于1996年年4月被成功分解月被成功分解RSA140于于1999年年2月被成功分解月被成功分解RSA155于于1999年年8月被成功分解月被成功分解模數(shù)長(zhǎng)度應(yīng)該介于模數(shù)長(zhǎng)度應(yīng)該介于1024bit到到2048bit之間之間現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC是否有不通過(guò)分解大整數(shù)的其他攻擊途徑？

25、是否有不通過(guò)分解大整數(shù)的其他攻擊途徑？證明：證明： 由由n直接確定直接確定(n)對(duì)對(duì)n的分解的分解。（作業(yè)）。（作業(yè)）由此可見(jiàn)，由此可見(jiàn)，不對(duì)不對(duì)n進(jìn)行因式分解而直接計(jì)算進(jìn)行因式分解而直接計(jì)算(n)并不比對(duì)并不比對(duì)n進(jìn)行因式分解更容易。進(jìn)行因式分解更容易?，F(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC為保證算法的安全性，還對(duì)為保證算法的安全性，還對(duì)p和和q提出以下要求：提出以下要求： （1） |p-q|要大。要大。（2）p和和q的長(zhǎng)度應(yīng)該相差不多。的長(zhǎng)度應(yīng)該相差不多。（3） p-1和和q-1都應(yīng)有大素因子。都應(yīng)有大素因子。（4） gcd(p-1, q-1)應(yīng)該很小。應(yīng)該很小?，F(xiàn)代密碼理論現(xiàn)代密碼理論-U

26、ESTC（1） |p-q|要大要大由由 ，如果，如果|p-q|小，則小，則 也小，因此也小，因此 稍大于稍大于 n ， 稍大于稍大于 ?？傻谩？傻胣的如下分解步驟：的如下分解步驟： 順序檢查大于順序檢查大于 的每一整數(shù)的每一整數(shù)x，直到找到一，直到找到一個(gè)個(gè)x使得使得x2-n是某一整數(shù)（記為是某一整數(shù)（記為y）的平方。）的平方。 由由x2-n=y2，得，得n=(x+y)(x-y)。222444pqpqpqnpq24pq24pq2pqnn現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC（2） p-1和和q-1都應(yīng)有大素因子都應(yīng)有大素因子這是因?yàn)檫@是因?yàn)镽SA算法存在著可能的重復(fù)加密攻擊算法存在著可能的重復(fù)加

27、密攻擊法。設(shè)攻擊者截獲密文法。設(shè)攻擊者截獲密文c，可如下進(jìn)行重復(fù)加密：，可如下進(jìn)行重復(fù)加密：2223111modmodmodmodtttttteeeeeeeeeeeeeeeecmmncmmncmmncmmn現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC若若 ，即即 ，則有則有 ，即即 ，所以在上述重復(fù)加密的倒數(shù)第所以在上述重復(fù)加密的倒數(shù)第2步就已恢復(fù)出明文步就已恢復(fù)出明文m，這種攻擊法只有在，這種攻擊法只有在t較小時(shí)才是可行的。為抵較小時(shí)才是可行的。為抵抗這種攻擊，抗這種攻擊，p、q的選取應(yīng)保證使的選取應(yīng)保證使t很大。很大。1m odtemcn modteemcnmodtemmn1modtecmn現(xiàn)代密

28、碼理論現(xiàn)代密碼理論-UESTC設(shè)設(shè)m在模在模n下階為下階為k，由，由 得得 ，所以，所以k|(et-1)，即，即et1(mod k)，t取為滿足上式的最小值（為取為滿足上式的最小值（為e在模在模k下的階）。又下的階）。又當(dāng)當(dāng)e與與k互素時(shí)互素時(shí)t|(k)。為使。為使t大，大，k就應(yīng)大且就應(yīng)大且(k)應(yīng)應(yīng)有大的素因子。又由有大的素因子。又由k|(n)，所以為使，所以為使k大，大，p-1和和q-1都應(yīng)有大的素因子。都應(yīng)有大的素因子。modtemmn11 modtemn現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC1. 共模攻擊共模攻擊 在實(shí)現(xiàn)在實(shí)現(xiàn)RSA時(shí)，為方便起見(jiàn)，可能給每一用戶相時(shí)，為方便起見(jiàn)，可能給

29、每一用戶相同的模數(shù)同的模數(shù)n，雖然加解密密鑰不同，然而這樣做是雖然加解密密鑰不同，然而這樣做是不行的。不行的。4.3.4 對(duì)對(duì)RSA的攻擊的攻擊現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC設(shè)兩個(gè)用戶的公開(kāi)鑰分別為設(shè)兩個(gè)用戶的公開(kāi)鑰分別為e1和和e2，且且e1和和e2互素，互素，明文消息是明文消息是m，密文分別是密文分別是敵手截獲敵手截獲c1和和c2后，可如下恢復(fù)后，可如下恢復(fù)m。用推廣的用推廣的Euclid算法求出滿足算法求出滿足re1+se2=1的兩個(gè)整數(shù)的兩個(gè)整數(shù)r和和s，其中一個(gè)為負(fù)，設(shè)為其中一個(gè)為負(fù)，設(shè)為r。再次用再次用推廣的推廣的Euclid算法求出算法求出 ，由此得由此得11 cnmccc

30、csrsrmod)(21121 nmcnmceemodmod2121 現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC2. 低指數(shù)攻擊低指數(shù)攻擊 將將RSA同時(shí)用于多個(gè)用戶，然而每個(gè)用戶的同時(shí)用于多個(gè)用戶，然而每個(gè)用戶的加密加密指數(shù)指數(shù)都很小。設(shè)都很小。設(shè)3個(gè)用戶的模數(shù)分別為個(gè)用戶的模數(shù)分別為ni(i=1,2,3)，當(dāng)當(dāng)ij時(shí)，時(shí)，gcd(ni, nj)=1，否則通過(guò)否則通過(guò)gcd(ni, nj)有可能有可能得出得出ni 和和nj 的分解。設(shè)明文消息是的分解。設(shè)明文消息是m，密文分別是密文分別是c1m3(mod n1)c2m3(mod n2)c3m3(mod n3)由中國(guó)剩余定理可求出由中國(guó)剩余定理可求出

31、m3(mod n1 n2 n3 )。由于由于m3 n1 n2 n3 ，可直接由可直接由m3開(kāi)立方根得到開(kāi)立方根得到m?，F(xiàn)代密碼理論現(xiàn)代密碼理論-UESTCRSA是是確定性的加密算法確定性的加密算法, 不能抵御不能抵御選擇密文攻擊選擇密文攻擊。3. 選擇密文攻擊選擇密文攻擊假設(shè)攻擊者得到了假設(shè)攻擊者得到了RSA公鑰公鑰(n,e)，截獲到某個(gè)密文，截獲到某個(gè)密文c1，假設(shè)其明文為，假設(shè)其明文為m1,即即 11modecmn然后，攻擊者選取明文然后，攻擊者選取明文m，構(gòu)造新密文，構(gòu)造新密文c2：21modeccmn攻擊者讓解密者對(duì)攻擊者讓解密者對(duì)c2解密，獲得明文解密，獲得明文m2，則計(jì)算，則計(jì)算

32、：21modmmnm現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC1. RSA算法步驟算法步驟2. 加解密的計(jì)算簡(jiǎn)化加解密的計(jì)算簡(jiǎn)化3. p, q的選取的選取4. 攻擊方法攻擊方法5. 安全性基于大數(shù)分解的困難性安全性基于大數(shù)分解的困難性RSA密碼體制的知識(shí)要點(diǎn)密碼體制的知識(shí)要點(diǎn)現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTCRabin密碼體制是對(duì)密碼體制是對(duì)RSA的一種修正，它有以下兩的一種修正，它有以下兩個(gè)特點(diǎn)：個(gè)特點(diǎn)： 它不是以一一對(duì)應(yīng)的單向陷門函數(shù)為基礎(chǔ)，對(duì)同它不是以一一對(duì)應(yīng)的單向陷門函數(shù)為基礎(chǔ)，對(duì)同一密文，可能有兩個(gè)以上對(duì)應(yīng)的明文一密文，可能有兩個(gè)以上對(duì)應(yīng)的明文;破譯該體制等價(jià)于對(duì)大整數(shù)的分解破譯該體制等

33、價(jià)于對(duì)大整數(shù)的分解。 RSA中選取的公開(kāi)鑰中選取的公開(kāi)鑰e滿足滿足1e(n)，且且gcd(e,(n)=1。Rabin密碼體制則取密碼體制則取e=2。4.4 Rabin密碼體制密碼體制現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC證證 （1）存在性）存在性 （2）唯一性）唯一性7現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC例例4.4 由以下方程組求由以下方程組求x。1mod22mod33mod55mod7xxxx 3042701052107532:4321MMMMm解解 47mod35mod13mod12mod144133122111MMMMMMMM(105 1 1 70 1 242 3 330 4 5)mod2

34、10173173mod210 xx 即 現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC1. 密鑰的產(chǎn)生密鑰的產(chǎn)生隨機(jī)選擇兩個(gè)大素?cái)?shù)隨機(jī)選擇兩個(gè)大素?cái)?shù)p、q，滿足滿足pq3 mod 4，即即這兩個(gè)素?cái)?shù)形式為這兩個(gè)素?cái)?shù)形式為4k+3； 計(jì)算計(jì)算n=pq。以以n作為公開(kāi)鑰，作為公開(kāi)鑰，p、q作為秘密鑰。作為秘密鑰?，F(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC2. 加密加密cm2 mod n其中其中m是明文分組，是明文分組，c是對(duì)應(yīng)的密文分組。是對(duì)應(yīng)的密文分組。2modxcn即解 22(mod )(mod )xcpxcq qmxpmxmodmod3. 解密解密 qmxpmxmodmod qmxpmxmodmod qmx

35、pmxmodmod qmxpmxmodmod密文對(duì)應(yīng)的明密文對(duì)應(yīng)的明文不惟一?？晌牟晃┮?。可在在m中加入中加入A, B的身份號(hào)、日的身份號(hào)、日期、時(shí)間等。期、時(shí)間等?，F(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC下面證明，當(dāng)下面證明，當(dāng)pq3 mod 4，兩個(gè)方程兩個(gè)方程x2c mod p, x2c mod q的平方根都可容易地求出。的平方根都可容易地求出。由由p3 mod 4得，得，p+1=4k，即即(p+1) /4是一整數(shù)。因是一整數(shù)。因c是模是模p的平方剩余，故的平方剩余，故所以所以 和和 是方程是方程x2c mod p的兩個(gè)根。的兩個(gè)根。41 pc41 pcp(1)/21(mod )pcp212

36、1(1)/24modpppcccccp現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC同理同理 和和 是方程是方程x2c mod q的兩個(gè)根。的兩個(gè)根。41 qc41 qcq現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC1. 密鑰產(chǎn)生密鑰產(chǎn)生: 隨機(jī)選擇大素?cái)?shù)隨機(jī)選擇大素?cái)?shù)p、q，pq3 mod 4，計(jì)算計(jì)算n=pq。以以n作為公開(kāi)鑰，作為公開(kāi)鑰，p、q作為秘密鑰。作為秘密鑰。2. 加密加密: cm2 mod n3. 解密解密: qcxpcxqpmodmod4141 qcxpcxqpmodmod4141 qcxpcxqpmodmod4141 qcxpcxqpmodmod4141Rabin密碼體制總結(jié)密碼體制總結(jié)破譯

37、破譯Rabin密碼體制的困難程度等價(jià)于大整數(shù)密碼體制的困難程度等價(jià)于大整數(shù)n的分解。的分解?，F(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC定理定理 已知已知n為兩個(gè)素?cái)?shù)乘積為兩個(gè)素?cái)?shù)乘積, a是模是模n的平方剩余，則的平方剩余，則求解方程求解方程x2a mod n與分解與分解n是等價(jià)的。是等價(jià)的。(1)已知已知n的分解的分解n=pq，且且a是模是模n的平方剩余，的平方剩余，就可求得就可求得a mod n的的4個(gè)平方根個(gè)平方根由中國(guó)剩余定理可求得由中國(guó)剩余定理可求得a mod n的的4個(gè)平方根，記為個(gè)平方根，記為u mod n和和w mod n，且且uw mod n。 qzxpyxmodmod qzxpy

38、xmodmod qzxpyxmodmod qzxpyxmodmodnaxmod2 qaxpaxmodmod22 qzxpyxmodmod現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC(2) 已知已知a mod n的兩個(gè)不同的平方根（的兩個(gè)不同的平方根（u mod n和和w mod n，且且uw mod n），），就可分解就可分解n。由由u2w2 mod n,得得(u+w)(u-w)0 mod n，但但n不能整不能整除除u+w也不能整除也不能整除u-w，所以必有所以必有p|(u+w), q|(u-w)或或 p|(u-w), q|(u+w)所以所以 gcd(n, u+w)=p, gcd(n, u-w)=q或

39、或gcd(n, u-w)=p, gcd(n, u+w)=q因此得到了因此得到了n的分解式。的分解式?，F(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC離散對(duì)數(shù)離散對(duì)數(shù)設(shè)設(shè)p是素?cái)?shù)，是素?cái)?shù)，a是是p的的本原根本原根。即即a1,a2,ap-1在在 mod p下產(chǎn)生下產(chǎn)生1到到p-1的所有值，所的所有值，所以對(duì)以對(duì)b1,p-1，有惟一的有惟一的i1,p-1使得使得bai mod p。稱稱 i 為 模為 模 p 下 以下 以 a 為 底為 底 b 的 離 散 對(duì) 數(shù) ， 記 為的 離 散 對(duì) 數(shù) ， 記 為 ilogab(mod p)。已知已知a、p、i時(shí)，容易地求出時(shí)，容易地求出b，已知已知a、b和和p，求求i則

40、非常困難。則非常困難。2133explnln lnOpp現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC算法復(fù)雜性算法復(fù)雜性 多項(xiàng)式時(shí)間算法是指時(shí)間復(fù)雜性為多項(xiàng)式時(shí)間算法是指時(shí)間復(fù)雜性為O(nt)的算法。的算法。n是輸入長(zhǎng)度，是輸入長(zhǎng)度，t是常數(shù)是常數(shù) 指數(shù)時(shí)間算法是指時(shí)間復(fù)雜性為指數(shù)時(shí)間算法是指時(shí)間復(fù)雜性為O(th(n)的算法。的算法?，F(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC類別類別復(fù)雜性復(fù)雜性n=106時(shí)時(shí)的運(yùn)算次數(shù)的運(yùn)算次數(shù)實(shí)際時(shí)間實(shí)際時(shí)間多項(xiàng)式多項(xiàng)式 常數(shù)常數(shù) 線性線性 二次二次 三次三次指數(shù)指數(shù)O(1)O(n)O(n2)O(n3)O(2n)11061012101810301,0301微秒微秒1秒秒1

41、1.6天天32,000年年約約3*10301016年年現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC4.5 ElGamal密碼體制密碼體制1. 密鑰產(chǎn)生過(guò)程：密鑰產(chǎn)生過(guò)程： 選擇一素?cái)?shù)選擇一素?cái)?shù)p以及小于以及小于p的隨機(jī)的隨機(jī)數(shù)數(shù)x， g是是p的原根的原根,計(jì)算計(jì)算ygx mod p。 (y, g, p)作為公開(kāi)密鑰，作為公開(kāi)密鑰，x作為秘密密鑰作為秘密密鑰。2. 加密過(guò)程：加密過(guò)程： 明文消息明文消息M，隨機(jī)選一整數(shù)隨機(jī)選一整數(shù) kp-1，計(jì)算計(jì)算 C1gk mod p, C2ykM mod p，密文為密文為C=(C1,C2)。3. 解密過(guò)程：解密過(guò)程： 21modxCMpC21modmodmodmo

42、dkkxkxkCy My MpppMpCgy現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTCElGamal密碼體制：密碼體制：1. 安全性基于有限域上的離散對(duì)數(shù)的難解性安全性基于有限域上的離散對(duì)數(shù)的難解性2. 加密算法是概率算法加密算法是概率算法3. 不能抵御選擇密文攻擊不能抵御選擇密文攻擊現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTCElGamal密碼的安全性密碼的安全性 參數(shù)要求：參數(shù)要求：p應(yīng)為應(yīng)為150位以上十進(jìn)制數(shù)，位以上十進(jìn)制數(shù)， p-1應(yīng)有應(yīng)有大素?cái)?shù)因子。大素?cái)?shù)因子。 K必須保密而且必須是一次性的。必須保密而且必須是一次性的。 K泄露，則敵手可計(jì)算出泄露，則敵手可計(jì)算出yk從而可以計(jì)算出從而可以計(jì)算出

43、M 使用同一使用同一k加密不同的明文加密不同的明文M，M，如果敵手知道，如果敵手知道M就可由就可由C2/C2=M/M求出求出M現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC 為保證為保證RSA算法的安全性，它的密鑰長(zhǎng)度需一再算法的安全性，它的密鑰長(zhǎng)度需一再增大，使得運(yùn)算負(fù)擔(dān)越來(lái)越大。相比之下，橢圓曲增大，使得運(yùn)算負(fù)擔(dān)越來(lái)越大。相比之下，橢圓曲線密碼體制線密碼體制ECC（elliptic curve cryptography）可可用短得多的密鑰獲得同樣的安全性，因此具有廣泛用短得多的密鑰獲得同樣的安全性，因此具有廣泛的應(yīng)用前景。的應(yīng)用前景。4.6 橢圓曲線密碼體制橢圓曲線密碼體制RSA/DSA512768

44、1024204821000ECC106132160211600ECC和和RSA/DSA體制在保持同等安全的條件下各自所需的密鑰的長(zhǎng)度體制在保持同等安全的條件下各自所需的密鑰的長(zhǎng)度現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC橢圓曲線的方程是以下形式的橢圓曲線的方程是以下形式的三次方程：三次方程： y2+axy+by=x3+cx2+dx+e (4.1)其中其中a，b，c，d，e是滿足某些是滿足某些簡(jiǎn)單條件的實(shí)數(shù)簡(jiǎn)單條件的實(shí)數(shù)。定義中包括一個(gè)稱為定義中包括一個(gè)稱為無(wú)窮遠(yuǎn)點(diǎn)的元素，記為無(wú)窮遠(yuǎn)點(diǎn)的元素，記為O。圖圖1 是橢圓曲線的兩個(gè)例子。是橢圓曲線的兩個(gè)例子。4.6.1 橢圓曲線橢圓曲線現(xiàn)代密碼理論現(xiàn)代密碼理

45、論-UESTC圖圖1 橢圓曲線的兩個(gè)例子橢圓曲線的兩個(gè)例子(b) y2=x3+x+1-10231-2 RQ P1-P123-21-10-4-224QR P1 - P1(a) y2=x3-x-4-224現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC點(diǎn)加法運(yùn)算點(diǎn)加法運(yùn)算： 如果其上的如果其上的3個(gè)點(diǎn)位于同一直線上，個(gè)點(diǎn)位于同一直線上，那么它們的和為那么它們的和為O。橢圓曲線上的加法律：橢圓曲線上的加法律： O為加法單位元，即對(duì)橢圓曲線上任一點(diǎn)為加法單位元，即對(duì)橢圓曲線上任一點(diǎn)P，有有P+O=P。 設(shè)設(shè)P1=(x,y)是橢圓曲線上的一點(diǎn)，它的加法逆元是橢圓曲線上的一點(diǎn)，它的加法逆元定義為定義為P2=-P1=(

46、x, -y)。 這是因?yàn)檫@是因?yàn)镻1、P2的連線延長(zhǎng)到無(wú)窮遠(yuǎn)時(shí)，得到橢的連線延長(zhǎng)到無(wú)窮遠(yuǎn)時(shí)，得到橢圓曲線上的另一點(diǎn)圓曲線上的另一點(diǎn)O，即橢圓曲線上的即橢圓曲線上的3點(diǎn)點(diǎn)P1、P2，O共線，所以共線，所以P1+P2+O=O，P1+P2=O，即即P2=-P1。由由O+O=O，還可得還可得O=-O現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC 設(shè)設(shè)Q和和R是是x坐標(biāo)不同的兩點(diǎn)，坐標(biāo)不同的兩點(diǎn)，Q+R的的定義定義： 畫一畫一條通過(guò)條通過(guò)Q、R的直線與橢圓曲線交于的直線與橢圓曲線交于P1。由由Q+R+P1=O 得得Q+R=-P1。 點(diǎn)點(diǎn)Q的倍數(shù)：的倍數(shù)： 在在Q點(diǎn)做橢圓曲線的一條切線，設(shè)點(diǎn)做橢圓曲線的一條切線，設(shè)

47、切線與橢圓曲線交于點(diǎn)切線與橢圓曲線交于點(diǎn)S，定義定義2Q=Q+Q=-S。類似類似地可定義地可定義3Q=Q+Q+Q+，等。等。 以上定義的加法具有加法運(yùn)算的一般性質(zhì)，如交以上定義的加法具有加法運(yùn)算的一般性質(zhì)，如交換律、結(jié)合律等。換律、結(jié)合律等?，F(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC密碼中普遍采用的是密碼中普遍采用的是有限域上有限域上的橢圓曲線，是指曲的橢圓曲線，是指曲線方程定義式中，所有系數(shù)都是某一線方程定義式中，所有系數(shù)都是某一有限域有限域GF(p)中的元素（中的元素（p為一大素?cái)?shù)）。其中為一大素?cái)?shù)）。其中最為常用的是由最為常用的是由方程方程y2x3+ax+b(mod p)(a,bGF(p),4

48、a3+27b20(modp)(4.2)定義的曲線。定義的曲線。4.6.2 有限域上的橢圓曲線有限域上的橢圓曲線現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC例例 p=23，a=b=1，4a3+27b2(mod 23)80 ，方程方程(4.2)為為y2x3+x+1，其圖形是連續(xù)曲線。其圖形是連續(xù)曲線。(b) y2=x3+x+1 RQ P1-P123-21-10-4-224,0),(mod1| ),(),(32OyxpyxpxxyyxbaEp為整數(shù)為整數(shù)且且 (0,1)(0,22)(1,7)(1,16)(3,10)(3,13)(4,0)(5,4)(5,19)(6,4)(6,19)(7,11)(7,12)(9

49、,7)(9,16)(11,3)(11,20) (12,4)(12,19) (13,7)(13,16) (17,3)(17,20) (18,3)(18,20)(19,5)(19,18)點(diǎn)集點(diǎn)集E23(1,1)現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC一般來(lái)說(shuō)，一般來(lái)說(shuō)，Ep(a,b)由以下方式產(chǎn)生：由以下方式產(chǎn)生： 對(duì)每一對(duì)每一x(0 xp且且x為整數(shù)），計(jì)算為整數(shù)），計(jì)算x3+ax+b(mod p)。 決定中求得的值決定中求得的值在模在模p下是否有平方根下是否有平方根，如果，如果沒(méi)有，則曲線上沒(méi)有與這一沒(méi)有，則曲線上沒(méi)有與這一x相對(duì)應(yīng)的點(diǎn)；如果有，相對(duì)應(yīng)的點(diǎn)；如果有，則求出兩個(gè)平方根（則求出兩個(gè)平方

50、根（y=0 時(shí)只有一個(gè)平方根）。時(shí)只有一個(gè)平方根）?，F(xiàn)代密碼理論現(xiàn)代密碼理論-UESTCEp(a,b)上的加法定義如下：上的加法定義如下： 設(shè)設(shè)P, QEp(a,b)，則則 P+O=P。 如果如果P=(x,y)，那么那么(x, y)+(x, -y)=O，即即 (x, -y)是是P的加法逆元，表示為的加法逆元，表示為-P。由由Ep(a,b)的產(chǎn)生方式知，的產(chǎn)生方式知，-P也是也是Ep(a,b)中的點(diǎn)，如中的點(diǎn)，如上例，上例，P=(13,7)E23(1,1)，-P=(13, -7)，而而 -7mod 2316，所以所以-P=(13, 16)，也在也在E23(1,1)中。中。現(xiàn)代密碼理論現(xiàn)代密碼理論

51、-UESTC 設(shè)設(shè)P=(x1,y1)，Q=(x2,y2)，P-Q，則則P+Q=(x3,y3)由以下規(guī)則確定：由以下規(guī)則確定：x32-x1-x2(mod p)y3(x1-x3)-y1(mod p)其中其中212121132yyPQxxxaPQy現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC例例 以以E23(1,1)為例，設(shè)為例，設(shè)P=(3,10)，Q=(9,7)，則則所以所以P+Q=(17,20)，仍為仍為E23(1,1)中的點(diǎn)。中的點(diǎn)。2337 103111mod239362113910917mod2311(3 17) 1016420mod23xy 現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC若求若求2P則則所

52、以所以2P=(7,12)。22333 31516mod232 10204633307mod236(37) 103412mod23xy 現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC倍點(diǎn)運(yùn)算仍定義為重復(fù)加法，如倍點(diǎn)運(yùn)算仍定義為重復(fù)加法，如4P=P+P+P+P。 可以看出，加法在可以看出，加法在E23(1,1)中是封閉的，且能驗(yàn)中是封閉的，且能驗(yàn)證還滿足交換律。對(duì)一般的證還滿足交換律。對(duì)一般的Ep(a,b)，可證其上的加可證其上的加法運(yùn)算是法運(yùn)算是封閉封閉的、滿足的、滿足交換律交換律，同樣還能證明其上，同樣還能證明其上的的加法逆元加法逆元運(yùn)算也是封閉的，所以運(yùn)算也是封閉的，所以Ep(a,b)是一個(gè)是一個(gè)Ab

53、el群群?，F(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC4.6.3 明文消息嵌入到橢圓曲線上明文消息嵌入到橢圓曲線上 設(shè)明文消息為m, k是一個(gè)足夠大的整數(shù)，使得將明文消息鑲嵌到橢圓曲線上時(shí)，錯(cuò)誤概率是2-k。如取k=30，對(duì)明文m，如下計(jì)算一系列x:,0,1,2,30,301,302,xmkj jmmm直到x3+ax+b(modp)有平方根，則得到點(diǎn)3),(xxax b反過(guò)來(lái)，從橢圓曲線點(diǎn)(x,y)得到明文消息m,只需求出3 0 xm現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC橢圓曲線上的數(shù)學(xué)困難問(wèn)題橢圓曲線上的數(shù)學(xué)困難問(wèn)題在橢圓曲線構(gòu)成的在橢圓曲線構(gòu)成的Abel群群Ep(a,b) :PEp(a,b), P的

54、階是一個(gè)非常大的素?cái)?shù)，的階是一個(gè)非常大的素?cái)?shù)，P的階是的階是滿足滿足nP=O的最小正整數(shù)的最小正整數(shù)n。Q=kP，(1) 已知已知k和和P易求易求Q;(2) 已知已知P、Q求求k則是困難的則是困難的這就是這就是橢圓曲線上的離散對(duì)數(shù)問(wèn)題橢圓曲線上的離散對(duì)數(shù)問(wèn)題，可應(yīng)用于構(gòu)造，可應(yīng)用于構(gòu)造公鑰密碼體制。公鑰密碼體制。Diffie-Hellman密鑰交換和密鑰交換和ElGamal密碼體制可推密碼體制可推廣到橢圓曲線來(lái)實(shí)現(xiàn)。廣到橢圓曲線來(lái)實(shí)現(xiàn)。4.6.4 橢圓曲線上的密碼橢圓曲線上的密碼現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC1. Diffie-Hellman密鑰交換密鑰交換 W.Diffie和M.Hel

55、lman1976年提出 算法的安全性基于求離散對(duì)數(shù)的困難性用戶B用戶A選擇隨機(jī)數(shù)xp計(jì)算YA= gx mod p選擇隨機(jī)數(shù)yp計(jì)算YB= gy mod pYB計(jì)算K=YA y = gxy mod p計(jì)算K=YB x = gxy mod pYAp是大素?cái)?shù)，是大素?cái)?shù)，g g是是p的本原根，的本原根，p和和g g公開(kāi)公開(kāi)Diffie-Hellman密鑰交換密鑰交換現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC首先取一素?cái)?shù)首先取一素?cái)?shù)p2180和兩個(gè)參數(shù)和兩個(gè)參數(shù)a、b，則得方程則得方程(4.2)表達(dá)的橢圓曲線及其上面的點(diǎn)構(gòu)成的表達(dá)的橢圓曲線及其上面的點(diǎn)構(gòu)成的Abel群群Ep(a,b)。第第2步，取步，取Ep(

56、a,b)的一個(gè)生成元的一個(gè)生成元G(x1,y1)，要求要求G的的階是一個(gè)非常大的素?cái)?shù)，階是一個(gè)非常大的素?cái)?shù)，G的階是滿足的階是滿足nG=O的最小的最小正整數(shù)正整數(shù)n。Ep(a,b)和和G作為公開(kāi)參數(shù)。作為公開(kāi)參數(shù)。 移植到橢圓曲線上移植到橢圓曲線上：現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC兩用戶兩用戶A和和B之間的密鑰交換如下進(jìn)行：之間的密鑰交換如下進(jìn)行： A選一選一小于小于n的整數(shù)的整數(shù)nA，作為秘密鑰，并由作為秘密鑰，并由PA=nAG產(chǎn)生產(chǎn)生Ep(a,b)上的一點(diǎn)作為公鑰。上的一點(diǎn)作為公鑰。 B類似地選取自己的秘密鑰類似地選取自己的秘密鑰nB和公開(kāi)鑰和公開(kāi)鑰PB。 A、B分別由分別由K=nAP

57、B和和K=nBPA產(chǎn)生出雙方共享產(chǎn)生出雙方共享的秘密鑰。的秘密鑰。這是因?yàn)檫@是因?yàn)镵=nAPB=nA(nBG)=nB(nAG)=nBPA。 攻擊者若想獲取攻擊者若想獲取K，則必須由則必須由PA和和G求出求出nA，或或由由PB和和G求出求出nB，即需要求橢圓曲線上的離散對(duì)數(shù)，即需要求橢圓曲線上的離散對(duì)數(shù)，因此是不可行的。因此是不可行的。現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC用戶用戶A選擇一隨選擇一隨機(jī)數(shù)機(jī)數(shù)nAn計(jì)算計(jì)算PA= nA G計(jì)算計(jì)算K= nA PB 用戶用戶B選擇一隨選擇一隨機(jī)數(shù)機(jī)數(shù)nBn計(jì)算計(jì)算PB= nB G計(jì)算計(jì)算K= nB PA PBPAGF(p), a 公開(kāi)公開(kāi), a本原本原Ep(a,b), G公開(kāi)公開(kāi), G的的階為階為n現(xiàn)代密碼理論現(xiàn)代密碼理論-UESTC例例 p=211，Ep(0,-4)，即橢圓曲線為即橢圓曲線為y2x3-4。G=(2,2)是是E211(0,-4)的階為的階為241的一個(gè)生成元，即的一個(gè)生成元，即241G=O。A的秘密鑰取的秘密鑰取nA=121，公開(kāi)鑰為公開(kāi)鑰為PA=121(2,2)=(115,48)。B的秘密鑰取的秘密鑰取nB=203，公開(kāi)鑰為公開(kāi)鑰為PB=203(2,2)=(130,203)。共享密鑰為共享密鑰為121(130,203)=203(115,48)=(161,169)。即共享密鑰是一對(duì)數(shù)。即共享密鑰是一對(duì)數(shù)。