(現(xiàn)代密碼學(xué)課件）04公鑰密碼

1、( (現(xiàn)代密碼學(xué)課件現(xiàn)代密碼學(xué)課件0404公鑰密碼公鑰密碼7費(fèi)馬小定理和歐拉定理費(fèi)馬小定理和歐拉定理n歐拉函數(shù)歐拉函數(shù)n設(shè)設(shè)n n為一正整數(shù)，小于為一正整數(shù)，小于n n且與且與n n互素的正整互素的正整數(shù)的個(gè)數(shù)稱(chēng)為數(shù)的個(gè)數(shù)稱(chēng)為n n的歐拉函數(shù)，記為的歐拉函數(shù)，記為j(n)j(n)n定理：假設(shè)定理：假設(shè)n n是兩個(gè)素?cái)?shù)是兩個(gè)素?cái)?shù)p p和和q q的乘積，那的乘積，那么么 j(n) j(n)j(p)j(q)=(p-1)(q-1)j(p)j(q)=(p-1)(q-1)n歐拉定理歐拉定理n假設(shè)假設(shè)a a和和n n互素互素, ,那么那么aj(n)=1 mod naj(n)=1 mod n8費(fèi)馬小定理練習(xí)費(fèi)

2、馬小定理練習(xí)n求求3201 (mod 11)9離散對(duì)數(shù)離散對(duì)數(shù)n求模下的整數(shù)冪求模下的整數(shù)冪n根據(jù)歐拉定理，假設(shè)根據(jù)歐拉定理，假設(shè)gcd(a,n)=1,那么那么aj (n) 1 mod n。考慮一般。考慮一般am 1 mod n, 如果如果a,n互素，至少有一個(gè)整數(shù)互素，至少有一個(gè)整數(shù)m滿(mǎn)足這一方滿(mǎn)足這一方程。稱(chēng)滿(mǎn)足這一方程的最小正整數(shù)程。稱(chēng)滿(mǎn)足這一方程的最小正整數(shù)m為為模模n下下a的階。的階。n例：例：a=7,n=19. 71 7 mod 19, 72 11 mod 19, 73 1 mod 19,所以所以7模模19的階為的階為3。從。從冪次為冪次為4開(kāi)始出現(xiàn)循環(huán)，循環(huán)周期與元素開(kāi)始出現(xiàn)循環(huán)

3、，循環(huán)周期與元素的階相同的階相同10離散對(duì)數(shù)離散對(duì)數(shù)n定理：設(shè)定理：設(shè)a的階為的階為m，那么，那么ak1(mod n)的充分的充分必要條件是必要條件是k是是m的倍數(shù)。的倍數(shù)。n推論：推論：a的階整除的階整除j(n)。n本原根：本原根：a的階的階m等于等于j(n)，a為為n的本原根。的本原根。n如果如果a是是n的本原根，的本原根，a1,a2,.,aj(n)在模在模n下互不下互不相同且與相同且與n互素。互素。n本原根不唯一。本原根不唯一。n并非所有元素都有本原根，僅有以下形式的整并非所有元素都有本原根，僅有以下形式的整數(shù)才有本原根：數(shù)才有本原根：2，4，pa,2pa,其中其中p是奇素?cái)?shù)是奇素?cái)?shù)11

4、離散對(duì)數(shù)離散對(duì)數(shù)n設(shè)設(shè)p p是素?cái)?shù)，是素?cái)?shù)，a a是是p p的本原根。對(duì)的本原根。對(duì)b1,p-1,b1,p-1,有唯一的有唯一的i1,p-1,i1,p-1,使使bai mod pbai mod p。稱(chēng)。稱(chēng)i i為模為模p p下以下以a a為底為底b b的的離散對(duì)數(shù)離散對(duì)數(shù)( (或者稱(chēng)為指標(biāo)或者稱(chēng)為指標(biāo)) )，記為，記為nilogab (mod p)ilogab (mod p)na,p,i,a,p,i,求求b b比較容易，以及比較容易，以及a,b,p,a,b,p,求求i i非非常困難常困難12離散對(duì)數(shù)離散對(duì)數(shù)(略略)n指標(biāo)指標(biāo)ny=ax(a0,a1)的逆函數(shù)稱(chēng)為以的逆函數(shù)稱(chēng)為以a為底的對(duì)數(shù)，為底

5、的對(duì)數(shù)，記為記為x=logayn設(shè)設(shè)p為素?cái)?shù)，為素?cái)?shù)，a是是p的本原根，那么的本原根，那么a0,a1,.,ap-1產(chǎn)生產(chǎn)生1到到p-1中所有值，且每個(gè)中所有值，且每個(gè)值只出現(xiàn)一次。對(duì)任一值只出現(xiàn)一次。對(duì)任一b1,p-1，都，都存在唯一的存在唯一的i(1i p)，使，使bai(mod p)。i稱(chēng)稱(chēng)為模為模p下以下以a為底為底b的指標(biāo)，記為的指標(biāo)，記為i=inda,p(d)13離散對(duì)數(shù)離散對(duì)數(shù)(略略)n指標(biāo)的性質(zhì)指標(biāo)的性質(zhì)ninda,p(1)=0ninda,p(a)=1ninda,p(xy)=inda,p(x)+ inda,p(y) mod j(p)ninda,p(yr)=rinda,p(y) m

6、od j(p)n 后兩個(gè)性質(zhì)基于以下結(jié)論后兩個(gè)性質(zhì)基于以下結(jié)論n 假設(shè)假設(shè)azaq mod p ,a和和p互素，那么互素，那么zq mod j(p)14離散對(duì)數(shù)離散對(duì)數(shù)例如：例如：p=19，a=3在在mod 19下的冪下的冪 ai (mod p)如下表如下表i12345678910 11 12 13 14 15 16 17 18ai39851572618 16 10 11 14412 17 131即即3的階為的階為18=j j(19)，所以所以3為為19的本原根。因此我的本原根。因此我們有離散對(duì)數(shù)們有離散對(duì)數(shù) ilogab (mod p) 如下表如下表b12345678910 11 12 13

7、 14 15 16 17 18logab 1871144863211 12 15 17 13510 16915離散對(duì)數(shù)練習(xí)離散對(duì)數(shù)練習(xí)n計(jì)算并證明計(jì)算并證明 2 也是也是 19 的本原根，并寫(xiě)出離的本原根，并寫(xiě)出離散對(duì)數(shù)表。散對(duì)數(shù)表。16設(shè)設(shè)n是一正整數(shù)，是一正整數(shù)，gcd(a,n)=1 ，稱(chēng)，稱(chēng)a是是n的平方的平方剩余，如果方程剩余，如果方程 x2a (mod n)有解。否那么稱(chēng)為非平方剩余。有解。否那么稱(chēng)為非平方剩余。二次互反律二次互反律17例如：例如：x21 mod 7有解有解x=1，x=6； x22 mod 7有解有解x=3，x=4； x23 mod 7無(wú)解；無(wú)解； x24 mod 7

8、有解有解x=2，x=5； x25 mod 7無(wú)解；無(wú)解； x26 mod 7無(wú)解。無(wú)解?？梢?jiàn)共有可見(jiàn)共有3個(gè)數(shù)個(gè)數(shù)1、2、4是模是模7的平方剩余，且的平方剩余，且每個(gè)平方剩余都有兩個(gè)平方根即例中的每個(gè)平方剩余都有兩個(gè)平方根即例中的x。二次互反律二次互反律18n容易證明，假設(shè)容易證明，假設(shè)p為奇素?cái)?shù)為奇素?cái)?shù)n模模p的平方剩余的個(gè)數(shù)與模的平方剩余的個(gè)數(shù)與模p的非平方剩余的的非平方剩余的個(gè)數(shù)相等，都有個(gè)數(shù)相等，都有(p-1)/2 個(gè)。個(gè)。n如果如果a是模是模p的一個(gè)平方剩余，那么的一個(gè)平方剩余，那么a恰有兩恰有兩個(gè)平方根個(gè)平方根x1和和x2，1x1(p-1)/2，(p-1)/2+1x2(p-1)，且

9、這兩個(gè)平方根，且這兩個(gè)平方根x1，x2中中的其中一個(gè)也是模的其中一個(gè)也是模p的平方剩余。的平方剩余。二次互反律二次互反律19定義定義4.1 設(shè)設(shè)p是素?cái)?shù)，是素?cái)?shù)，a是一整數(shù)，符號(hào)是一整數(shù)，符號(hào) 的的定義如下：定義如下：稱(chēng)符號(hào)稱(chēng)符號(hào) 為為L(zhǎng)egendre符號(hào)符號(hào)。ap011apaappap如果被整除如果是模的平方剩余如果是模的非平方剩余ap二次互反律二次互反律20例如：例如：對(duì)于奇素?cái)?shù)對(duì)于奇素?cái)?shù)p，我們有公式：，我們有公式：例如：例如：p=23，a=5，a(p-1)/2 (mod p)511 (mod p)=-1，所以所以5不是模不是模23的平方剩余。的平方剩余。 1241777 3561777

10、 (1) / 2modpaapp二次互反律二次互反律21Legendre符號(hào)有以下性質(zhì)：符號(hào)有以下性質(zhì)： 定理定理 設(shè)設(shè)p是奇素?cái)?shù)，是奇素?cái)?shù)，a和和b都不能被都不能被p除盡，除盡，那么那么 假設(shè)假設(shè)ab (mod p)，那么，那么abppababppp 21apapapp二次互反律二次互反律22Jacobi符號(hào)符號(hào)是是Legendre符號(hào)的推廣。符號(hào)的推廣。定義定義 設(shè)設(shè)n是正整數(shù)，且是正整數(shù)，且 ，定定義義Jacobi符號(hào)為符號(hào)為其中右端的符號(hào)是其中右端的符號(hào)是Legendre符號(hào)。符號(hào)。當(dāng)當(dāng)n為素?cái)?shù)時(shí)，為素?cái)?shù)時(shí)，Jacobi符號(hào)就是符號(hào)就是Legendre符號(hào)。符號(hào)。1212kaaaknp

11、pp 1212kaaakaaaapnpp 二次互反律二次互反律23Jacobi符號(hào)有以下性質(zhì)：符號(hào)有以下性質(zhì)： 定理定理 設(shè)設(shè)n為合數(shù)，為合數(shù)，a和和b是與是與n互素的整數(shù)，互素的整數(shù)，那么有那么有 假設(shè)假設(shè)ab (mod n)，那么，那么 abnn ababnnn 2abann anann二次互反律二次互反律24n Jacobi符號(hào)和符號(hào)和Legendre符號(hào)的本質(zhì)差異符號(hào)的本質(zhì)差異n Jacobi符號(hào)不表示方程符號(hào)不表示方程x2a (mod n)是否有是否有解。解。n比方比方n=p1p2，a關(guān)于關(guān)于p1和和p2都是非平方剩余都是非平方剩余，即，即x2a mod p1和和x2a mod p2

12、都無(wú)解，由都無(wú)解，由中國(guó)剩余定理知中國(guó)剩余定理知x2a mod n也無(wú)解。但是，也無(wú)解。但是，由于由于 ,所以所以 。即。即x2a mod n雖無(wú)解，但雖無(wú)解，但Jacobi符號(hào)符號(hào) 卻為卻為1。 an121papa 121aaanpp二次互反律二次互反律25定理定理(二次互反律二次互反律) 設(shè)設(shè)m、n均為大于均為大于2的奇數(shù)，的奇數(shù)，那么那么假設(shè)假設(shè)mn3 mod 4,那么那么 ;否那么否那么 . 1141mnmnnm mnnm mnnm二次互反律二次互反律 211281121,1,1nnnnn 對(duì)一些特殊的對(duì)一些特殊的a，Jacobi符號(hào)可如下計(jì)算符號(hào)可如下計(jì)算(后兩個(gè)等式后兩個(gè)等式要求要

13、求n是奇數(shù)是奇數(shù))：26 10531721317105105二次互反律二次互反律例子：例子：練習(xí)：計(jì)算以下練習(xí)：計(jì)算以下Legendre符號(hào)符號(hào) 6652, , 595310727定理定理 設(shè)設(shè)n=pq，當(dāng)，當(dāng)pq3 (mod 4)時(shí)，時(shí)， (1) 求解方程求解方程 x2a(mod n)與分解與分解n等價(jià)。等價(jià)。 (2) a mod n的兩個(gè)不同的平方根的兩個(gè)不同的平方根u和和w的的Jacobi符號(hào)有如下關(guān)系：符號(hào)有如下關(guān)系： uwnm 二次互反律二次互反律28二、計(jì)算數(shù)論根底二、計(jì)算數(shù)論根底l計(jì)算復(fù)雜性計(jì)算復(fù)雜性l素性檢驗(yàn)素性檢驗(yàn)29計(jì)算復(fù)雜性計(jì)算復(fù)雜性n對(duì)于一個(gè)密碼系統(tǒng)來(lái)說(shuō)，要求對(duì)于一個(gè)密

14、碼系統(tǒng)來(lái)說(shuō)，要求n加密算法和解密算法是加密算法和解密算法是“容易的容易的n未知密鑰時(shí)，推導(dǎo)出明文和密鑰是未知密鑰時(shí)，推導(dǎo)出明文和密鑰是“困難困難的的n如何描述一個(gè)計(jì)算問(wèn)題是容易的還是困難如何描述一個(gè)計(jì)算問(wèn)題是容易的還是困難的？的？n我們用解決這個(gè)問(wèn)題的算法的計(jì)算時(shí)間和我們用解決這個(gè)問(wèn)題的算法的計(jì)算時(shí)間和存儲(chǔ)空間來(lái)描述。這兩者分別稱(chēng)為算法的存儲(chǔ)空間來(lái)描述。這兩者分別稱(chēng)為算法的時(shí)間復(fù)雜度和空間復(fù)雜度，它們是算法輸時(shí)間復(fù)雜度和空間復(fù)雜度，它們是算法輸入數(shù)據(jù)入數(shù)據(jù)n的長(zhǎng)度的長(zhǎng)度k的函數(shù)。的函數(shù)。30計(jì)算復(fù)雜性計(jì)算復(fù)雜性n記記 f(k)=O(g(k)，如果存在常數(shù)，如果存在常數(shù)C0，使得，使得f(k)

15、Cg(k)。n例如假設(shè)例如假設(shè) f(k)=8k+10，那么，那么 f(k)=O(k)n一般地，假設(shè)一般地，假設(shè)f(k)=ackc+a1k+a0，那么，那么 f(k)=O(kc)n假設(shè)算法的時(shí)間復(fù)雜度假設(shè)算法的時(shí)間復(fù)雜度T=O(kc)，其中，其中c0為常數(shù)，那么稱(chēng)該算法是多項(xiàng)式時(shí)間的為常數(shù)，那么稱(chēng)該算法是多項(xiàng)式時(shí)間的;n假設(shè)算法的時(shí)間復(fù)雜度假設(shè)算法的時(shí)間復(fù)雜度T=O(c f(k)，其中，其中c1為常數(shù)，為常數(shù)，f(k)為多項(xiàng)式，那么稱(chēng)該算法為多項(xiàng)式，那么稱(chēng)該算法是指數(shù)時(shí)間的。是指數(shù)時(shí)間的。31計(jì)算復(fù)雜性計(jì)算復(fù)雜性n當(dāng)前的計(jì)算機(jī)的計(jì)算能力是有局限的當(dāng)前的計(jì)算機(jī)的計(jì)算能力是有局限的n稱(chēng)一個(gè)算法是有效

16、的，如果該算法可在多稱(chēng)一個(gè)算法是有效的，如果該算法可在多項(xiàng)式時(shí)間內(nèi)完成；否那么稱(chēng)該算法是無(wú)效項(xiàng)式時(shí)間內(nèi)完成；否那么稱(chēng)該算法是無(wú)效的。的。n稱(chēng)一個(gè)問(wèn)題是計(jì)算上可行的，如果存在多稱(chēng)一個(gè)問(wèn)題是計(jì)算上可行的，如果存在多項(xiàng)式時(shí)間的算法可以解決；否那么稱(chēng)為計(jì)項(xiàng)式時(shí)間的算法可以解決；否那么稱(chēng)為計(jì)算上不可行的。算上不可行的。32計(jì)算復(fù)雜性計(jì)算復(fù)雜性n數(shù)據(jù)大小數(shù)據(jù)大小n和數(shù)據(jù)長(zhǎng)度和數(shù)據(jù)長(zhǎng)度k的關(guān)系：的關(guān)系：n在算法中通常用在算法中通常用log(x)表示以表示以2為底的對(duì)數(shù)為底的對(duì)數(shù)n設(shè)正數(shù)設(shè)正數(shù)n在二進(jìn)制表示下的長(zhǎng)度是在二進(jìn)制表示下的長(zhǎng)度是k比特比特n我們有我們有k=log n+1，x 表示取整函數(shù)表示取整函數(shù)

17、n用前面的符號(hào)，我們有用前面的符號(hào)，我們有 k=O(log n)33計(jì)算復(fù)雜性計(jì)算復(fù)雜性n例子：計(jì)算兩個(gè)不大于例子：計(jì)算兩個(gè)不大于n的整數(shù)的四那么的整數(shù)的四那么運(yùn)算的時(shí)間復(fù)雜度運(yùn)算的時(shí)間復(fù)雜度T和空間復(fù)雜度和空間復(fù)雜度Sn加法運(yùn)算：加法運(yùn)算：T = O(k) = O(log n)n減法運(yùn)算：減法運(yùn)算：T = O(k) = O(log n)n乘法運(yùn)算：乘法運(yùn)算：T = O(k2) = O(log2n)n除法運(yùn)算：除法運(yùn)算：T = O(k2) = O(log2n)n1971年，年，Schnhage 和和 Strassen 給出目前給出目前為止最快的快速相乘算法，它的時(shí)間復(fù)雜為止最快的快速相乘算法，

18、它的時(shí)間復(fù)雜度度T = O(k log k log log k)34計(jì)算復(fù)雜性計(jì)算復(fù)雜性n例子：模運(yùn)算的時(shí)間復(fù)雜度例子：模運(yùn)算的時(shí)間復(fù)雜度n兩個(gè)小于兩個(gè)小于 n 的數(shù)模的數(shù)模 n 的加減乘運(yùn)算的時(shí)間的加減乘運(yùn)算的時(shí)間復(fù)雜度和前面兩個(gè)不大于復(fù)雜度和前面兩個(gè)不大于 n 的整數(shù)的加減的整數(shù)的加減乘運(yùn)算一樣。乘運(yùn)算一樣。n設(shè)設(shè) bn，那么計(jì)算，那么計(jì)算 bm (mod n) 的時(shí)間復(fù)雜的時(shí)間復(fù)雜度為度為 O(log m log2n)35計(jì)算復(fù)雜性計(jì)算復(fù)雜性n例子：多項(xiàng)式運(yùn)算的時(shí)間復(fù)雜度例子：多項(xiàng)式運(yùn)算的時(shí)間復(fù)雜度n兩個(gè)次數(shù)不大于兩個(gè)次數(shù)不大于d，系數(shù)都不大于，系數(shù)都不大于n的多項(xiàng)式的的多項(xiàng)式的相乘運(yùn)算

19、的時(shí)間復(fù)雜度為相乘運(yùn)算的時(shí)間復(fù)雜度為 O(d2log2n)n使用快速相乘算法可以將復(fù)雜度減少為使用快速相乘算法可以將復(fù)雜度減少為 O(d1+log1+n)，為任何正數(shù)。為任何正數(shù)。36素性檢驗(yàn)素性檢驗(yàn)n對(duì)于一個(gè)自然數(shù)對(duì)于一個(gè)自然數(shù)n，判斷它是素?cái)?shù)還是合數(shù)，判斷它是素?cái)?shù)還是合數(shù)n原始素性檢測(cè)算法：原始素性檢測(cè)算法：n對(duì)于從對(duì)于從1到根號(hào)到根號(hào)n的數(shù)的數(shù)a，計(jì)算，計(jì)算 n/a，如果其，如果其中有一個(gè)中有一個(gè)a整除整除n，那么它是合數(shù)；否那么，那么它是合數(shù)；否那么它是素?cái)?shù)它是素?cái)?shù)n算法的時(shí)間復(fù)雜度為算法的時(shí)間復(fù)雜度為 O(n1/2log2n)=O(2k/2k2) 是指數(shù)時(shí)間的！是指數(shù)時(shí)間的！37素性

20、檢驗(yàn)素性檢驗(yàn)nMiller-Rabin素性概率檢測(cè)法素性概率檢測(cè)法n引理：如果引理：如果p為大于為大于2的素?cái)?shù)，那么方程的素?cái)?shù)，那么方程x21 mod p的解只有和的解只有和x1和和x-1n引理的逆命題：假設(shè)方程引理的逆命題：假設(shè)方程x21 mod p有唯一有唯一解解x不為不為+1或或-1，p不是素?cái)?shù)不是素?cái)?shù)38n-1=bkbk-1b1b0for i=k downto 0 do xd; d(dd) mod n; if d=1 and (x1)and(xn-1) then return False if bi=1 the d(da) mod n if d 1 then return False;

21、 return True素性檢驗(yàn)素性檢驗(yàn)nMiller-Rabin素性概率檢測(cè)法素性概率檢測(cè)法nn為待檢測(cè)數(shù)，為待檢測(cè)數(shù)，a為小于為小于n的整數(shù)，將的整數(shù)，將n-1表示表示為二進(jìn)制形式為二進(jìn)制形式bkbk-1b0,d賦初值為賦初值為1，算，算法核心如下法核心如下n假設(shè)返回假設(shè)返回False,n不是素?cái)?shù)不是素?cái)?shù),假設(shè)返回假設(shè)返回True,有有可能是素?cái)?shù)。可能是素?cái)?shù)。39素性檢驗(yàn)素性檢驗(yàn)nMiller-Rabin素性概率檢測(cè)法素性概率檢測(cè)法n 該算法對(duì)該算法對(duì)s個(gè)不同的個(gè)不同的a，重復(fù)調(diào)用，如果每，重復(fù)調(diào)用，如果每次都返回次都返回true，那么，那么n是素?cái)?shù)的概率大于等是素?cái)?shù)的概率大于等于于1-2

22、-s40素性檢驗(yàn)素性檢驗(yàn)nAKS 素?cái)?shù)判別算法素?cái)?shù)判別算法2002年年n引理：引理：n2, gcd(a,n)=1，那么，那么n為素?cái)?shù)等價(jià)為素?cái)?shù)等價(jià)于于n (X+a)nXn+a (mod n)n直接用此等式驗(yàn)證需要對(duì)次數(shù)為直接用此等式驗(yàn)證需要對(duì)次數(shù)為n的多項(xiàng)式的多項(xiàng)式作運(yùn)算指數(shù)級(jí)別，為將計(jì)算量減少到作運(yùn)算指數(shù)級(jí)別，為將計(jì)算量減少到多項(xiàng)式級(jí)別，可以選擇次數(shù)比較小的多項(xiàng)式級(jí)別，可以選擇次數(shù)比較小的 r，對(duì)假設(shè)干個(gè)對(duì)假設(shè)干個(gè) a 驗(yàn)證以下等式驗(yàn)證以下等式n (X+a)nXn+a (mod Xr-1, n)41三、公鑰密碼根本概念三、公鑰密碼根本概念Basic Concept of Public Key

23、 Cryptography42公鑰密碼體制的原理公鑰密碼體制的原理公鑰體制公鑰體制(Public key system) (Diffie(Public key system) (Diffie和和Hellman,1976)Hellman,1976) 每個(gè)用戶(hù)都有一對(duì)選定的密鑰每個(gè)用戶(hù)都有一對(duì)選定的密鑰( (公鑰公鑰PKPK；私鑰；私鑰SK)SK)，公，公開(kāi)的密鑰開(kāi)的密鑰PKPK可以像可以像 號(hào)碼一樣進(jìn)行注冊(cè)公布。號(hào)碼一樣進(jìn)行注冊(cè)公布。主要特點(diǎn)：主要特點(diǎn)：加密和解密能力分開(kāi)加密和解密能力分開(kāi)多個(gè)用戶(hù)加密的消息只能由一個(gè)用戶(hù)解讀，用于公共網(wǎng)多個(gè)用戶(hù)加密的消息只能由一個(gè)用戶(hù)解讀，用于公共網(wǎng)絡(luò)中實(shí)現(xiàn)保密

24、通信絡(luò)中實(shí)現(xiàn)保密通信只能由一個(gè)用戶(hù)加密消息而使多個(gè)用戶(hù)可以解讀可用于只能由一個(gè)用戶(hù)加密消息而使多個(gè)用戶(hù)可以解讀可用于認(rèn)證系統(tǒng)中對(duì)消息進(jìn)行數(shù)字簽字。認(rèn)證系統(tǒng)中對(duì)消息進(jìn)行數(shù)字簽字。無(wú)需事先分配密鑰。無(wú)需事先分配密鑰。43公鑰體制加密體制公鑰體制加密體制加密解密：加密解密： c=EPKB(m), m=DSKB(c) c=EPKB(m), m=DSKB(c)平安保障：平安保障：從公開(kāi)鑰從公開(kāi)鑰PKBPKB和密文和密文c c要推出明文要推出明文m m或解密鑰或解密鑰SKBSKB在計(jì)算上是不在計(jì)算上是不可行的。可行的。由于任一用戶(hù)都可用用戶(hù)由于任一用戶(hù)都可用用戶(hù)B B的公開(kāi)鑰的公開(kāi)鑰PKBPKB向他發(fā)送機(jī)

25、密消息，向他發(fā)送機(jī)密消息，因而密文因而密文c c不具有認(rèn)證性。不具有認(rèn)證性。發(fā)送者A加密算法PKB密鑰源SKB解密算法接收者B密碼分析員mcmmSKB44公鑰密碼認(rèn)證體制公鑰密碼認(rèn)證體制 認(rèn)證算法：認(rèn)證算法： 用戶(hù)用戶(hù)A發(fā)送給用戶(hù)發(fā)送給用戶(hù)B：c=DSKA(m) B驗(yàn)證收到的信息：驗(yàn)證收到的信息：m=EPKA(c)平安保障：平安保障： 由于由于SKA是保密的，其他人都不可能偽造密文是保密的，其他人都不可能偽造密文c，可用，可用A的的 公開(kāi)鑰解密時(shí)得到有意義的消息公開(kāi)鑰解密時(shí)得到有意義的消息m。因此可以驗(yàn)證消息。因此可以驗(yàn)證消息m來(lái)來(lái)自自A而不是其他人，而實(shí)現(xiàn)了對(duì)而不是其他人，而實(shí)現(xiàn)了對(duì)A所發(fā)消

26、息的認(rèn)證。所發(fā)消息的認(rèn)證。發(fā)送者A加密算法SKA密鑰源PKA解密算法接收者B密碼分析員mcmSKA45公鑰保密和認(rèn)證體制公鑰保密和認(rèn)證體制為了要同時(shí)實(shí)現(xiàn)保密性和認(rèn)證性，要采用雙重加、為了要同時(shí)實(shí)現(xiàn)保密性和認(rèn)證性，要采用雙重加、解密解密用戶(hù)用戶(hù)A A用戶(hù)用戶(hù)B Bm保密保密認(rèn)證認(rèn)證EPKADSKBEPKBDSKAcmzz加密認(rèn)證算法：加密認(rèn)證算法： 用戶(hù)用戶(hù)A加密發(fā)送給用戶(hù)加密發(fā)送給用戶(hù)B：c=EPKB(DSKA(m) B B解密并驗(yàn)證收到的信息：解密并驗(yàn)證收到的信息：m=EPKA(DSKB(c)46公鑰密碼應(yīng)滿(mǎn)足的要求公鑰密碼應(yīng)滿(mǎn)足的要求n接收方接收方B B產(chǎn)生密鑰對(duì)在計(jì)算上是容易的產(chǎn)生密鑰對(duì)

27、在計(jì)算上是容易的n發(fā)送方發(fā)送方A A用收方的公開(kāi)鑰對(duì)消息用收方的公開(kāi)鑰對(duì)消息m m加密以產(chǎn)生密文加密以產(chǎn)生密文c c在在計(jì)算上是容易的。計(jì)算上是容易的。n收方收方B B用自己的秘密鑰對(duì)密文用自己的秘密鑰對(duì)密文c c解密在計(jì)算上是容易解密在計(jì)算上是容易的。的。n敵手由密文敵手由密文c c和和B B的公開(kāi)密鑰恢復(fù)明文在計(jì)算上是不的公開(kāi)密鑰恢復(fù)明文在計(jì)算上是不可行的。可行的。n敵手由密文敵手由密文c c和和B B的公開(kāi)密鑰恢復(fù)秘密密鑰在計(jì)算上的公開(kāi)密鑰恢復(fù)秘密密鑰在計(jì)算上是不可行的是不可行的n加解密次序可換，即加解密次序可換，即E EPKBPKBDDSKBSKB(m)=D(m)=DSKBSKBEEP

28、KBPKB(m) ,(m) ,不不是對(duì)任何算法都做此要求。是對(duì)任何算法都做此要求。47單向函數(shù)單向函數(shù)n設(shè)設(shè) f：AB 為可逆函數(shù)，假設(shè)它滿(mǎn)足：為可逆函數(shù)，假設(shè)它滿(mǎn)足：n 1o 對(duì)所有對(duì)所有xA，計(jì)算，計(jì)算f(x)“比較容易；比較容易；n 2o 對(duì)幾乎所有對(duì)幾乎所有xA，由，由f(x)計(jì)算計(jì)算x“極為困難；極為困難；n那么稱(chēng)那么稱(chēng)f為一個(gè)單向函數(shù)為一個(gè)單向函數(shù)(one-way function)。n定義中的計(jì)算上定義中的計(jì)算上“比較容易和比較容易和“極為困難極為困難可以用算法的時(shí)間復(fù)雜度來(lái)衡量。我們認(rèn)為多可以用算法的時(shí)間復(fù)雜度來(lái)衡量。我們認(rèn)為多項(xiàng)式時(shí)間的算法是項(xiàng)式時(shí)間的算法是“比較容易的，而指

29、數(shù)時(shí)比較容易的，而指數(shù)時(shí)間的算法是間的算法是“極為困難的。極為困難的。48限門(mén)單向函數(shù)限門(mén)單向函數(shù)n單向函數(shù)是求逆困難的函數(shù)，而陷門(mén)單向函數(shù)單向函數(shù)是求逆困難的函數(shù)，而陷門(mén)單向函數(shù)(trapdoor one-way function)(trapdoor one-way function)，是在不知陷，是在不知陷門(mén)信息下求逆困難的函數(shù)，當(dāng)知道陷門(mén)信息后，門(mén)信息下求逆困難的函數(shù)，當(dāng)知道陷門(mén)信息后，求逆是易于實(shí)現(xiàn)的。求逆是易于實(shí)現(xiàn)的。n陷門(mén)單向函數(shù)是一族可逆函數(shù)陷門(mén)單向函數(shù)是一族可逆函數(shù)fkfk，滿(mǎn)足，滿(mǎn)足nY=fk(X)Y=fk(X)易于計(jì)算當(dāng)易于計(jì)算當(dāng)k k和和X XnX Xf-1k(Y)f-1

30、k(Y)易于計(jì)算當(dāng)易于計(jì)算當(dāng)k k和和Y YnX Xf-1k(Y)f-1k(Y)計(jì)算上不可行計(jì)算上不可行Y Y但但k k未知未知n研究公鑰密碼算法就是找出適宜的單向限門(mén)函研究公鑰密碼算法就是找出適宜的單向限門(mén)函數(shù)數(shù)49四、四、RSA密碼體制密碼體制Rivest-Shamir-Adleman Cryptography50RSA密碼概況密碼概況n19781978年年 MIT MIT 三位年青數(shù)學(xué)家三位年青數(shù)學(xué)家 ，A.Shamir A.Shamir 和和 L.Adleman L.Adleman 發(fā)現(xiàn)了一種用數(shù)論構(gòu)造雙鑰的方法，發(fā)現(xiàn)了一種用數(shù)論構(gòu)造雙鑰的方法，稱(chēng)作稱(chēng)作MITMIT體制，后來(lái)被廣泛稱(chēng)之

31、為體制，后來(lái)被廣泛稱(chēng)之為RSARSA體制。體制。n它既可用于加密、又可用于數(shù)字簽字。它既可用于加密、又可用于數(shù)字簽字。nRSARSA算法的平安性基于數(shù)論中大整數(shù)分解的困算法的平安性基于數(shù)論中大整數(shù)分解的困難性。難性。51RSA合影照合影照52算法描述密鑰產(chǎn)生算法描述密鑰產(chǎn)生n獨(dú)立地選取兩大素?cái)?shù)獨(dú)立地選取兩大素?cái)?shù)p和和qn計(jì)算計(jì)算 n=pq，其歐拉函數(shù)值，其歐拉函數(shù)值j j(n)=(p-1)(q-1)n隨機(jī)選一整數(shù)隨機(jī)選一整數(shù)e，1 ej j(n)，gcd(j j(n),e)=1n在模在模j j(n)下下,計(jì)算計(jì)算e的逆元的逆元d=e-1 (mod j j(n) n以以e,n為公鑰為公鑰,d,n

32、為私鑰為私鑰。(p,q不再需要，不再需要，可以銷(xiāo)毀。可以銷(xiāo)毀。)53算法描述加密和解密算法描述加密和解密n加密加密將明文分組，各組對(duì)應(yīng)的十進(jìn)制數(shù)小于將明文分組，各組對(duì)應(yīng)的十進(jìn)制數(shù)小于n n c=me (mod n)n解密解密 m=cd (mod n)54解密正確性證明解密正確性證明ncd mod n med mod n mkj(n)+1 mod nn假設(shè)假設(shè)m與與n互素，由歐拉定理互素，由歐拉定理 mj(n)1 (mod n),得得 mkj(n)+1 mkj(n) m m (mod n)n假設(shè)假設(shè)gcd(m,n)1, m是是p的倍數(shù)或的倍數(shù)或q的倍數(shù)的倍數(shù),設(shè)設(shè)m=tp.此時(shí)此時(shí)gcd(m,q

33、)=1,由歐拉定理得到由歐拉定理得到nmkj(n) mj(q)kj(p) 1 (mod q)n 因此存在一整數(shù)因此存在一整數(shù)r，使，使mkj(n)1rq。兩邊同乘。兩邊同乘m=tp得到得到mkj(n)+1m+rtpq=m+rtn,即即nmkj(n)+1m (mod n)55RSA密碼例子密碼例子n選選p=7, q=17,那么那么n=pq=119, (n)=(p-1)(q-1)=96。取。取e=5，滿(mǎn)足，滿(mǎn)足1e (n)，且，且gcd(n),e)=1。確定滿(mǎn)足。確定滿(mǎn)足de=1 mod 96且且小于小于96的的d，求得，求得d為為77.n因此公鑰為因此公鑰為5,119，私鑰為，私鑰為77,119

34、。n設(shè)明文設(shè)明文m=19，那么加密得密文為，那么加密得密文為nc195 mod 11966n解密為解密為 m = 6677 (mod 119)19 56n RSA的加密、解密過(guò)程都為求的加密、解密過(guò)程都為求ar(mod n)n 如果先計(jì)算如果先計(jì)算ar再取模再取模n，那么中間結(jié)果非，那么中間結(jié)果非常大，有可能超出計(jì)算機(jī)所允許的整數(shù)取常大，有可能超出計(jì)算機(jī)所允許的整數(shù)取值范圍。如上例中解密運(yùn)算值范圍。如上例中解密運(yùn)算6677 mod 119。n 而用模運(yùn)算的性質(zhì)：而用模運(yùn)算的性質(zhì)：n(ab) mod n=(a mod n) (b mod n) mod nn用邊計(jì)算邊取模的方法就可減小中間結(jié)果用邊

35、計(jì)算邊取模的方法就可減小中間結(jié)果。快速指數(shù)計(jì)算問(wèn)題快速指數(shù)計(jì)算問(wèn)題57再者，考慮如何提高指數(shù)運(yùn)算的有效性。例再者，考慮如何提高指數(shù)運(yùn)算的有效性。例如求如求x16，直接計(jì)算的話需做，直接計(jì)算的話需做15次乘法。然而次乘法。然而如果重復(fù)對(duì)每個(gè)局部結(jié)果做平方運(yùn)算即求如果重復(fù)對(duì)每個(gè)局部結(jié)果做平方運(yùn)算即求x，x2，x4，x8，x16那么只需那么只需4次乘法。次乘法。快速指數(shù)計(jì)算問(wèn)題快速指數(shù)計(jì)算問(wèn)題58快速指數(shù)計(jì)算問(wèn)題快速指數(shù)計(jì)算問(wèn)題求求ar可如下進(jìn)行，其中可如下進(jìn)行，其中a，r是正整數(shù)：將是正整數(shù)：將r表示為二進(jìn)制形式表示為二進(jìn)制形式bk bk-1b0，即即r=bk2k+bk-12k-1+b12+b0因

36、此因此例如：例如：19=124+023+022+121+120，所以所以 a19=(a1)2a0)2a0)2a1)2a112012222kkkbbbbbraaaaaa 59其中其中d是中間結(jié)果，是中間結(jié)果，d的終值即為所求結(jié)果。的終值即為所求結(jié)果。c在這里的作用在這里的作用是表示指數(shù)的局部結(jié)果，其終值即為指數(shù)是表示指數(shù)的局部結(jié)果，其終值即為指數(shù)r。c=0; d=1；for i=k downto 0 do c=2c;d=(dd) mod n;if bi =1 then c=c+1;d=(da) mod nreturn d.快速指數(shù)計(jì)算問(wèn)題快速指數(shù)計(jì)算問(wèn)題22iibccbdd a從而可得以下從而可

37、得以下快速指數(shù)算法快速指數(shù)算法：60例例4.9 求求7560 mod 561。將將560表示為表示為1000110000，所以所以7560 mod 561=1?？焖僦笖?shù)計(jì)算問(wèn)題快速指數(shù)計(jì)算問(wèn)題22iibccbdd a61n 產(chǎn)生密鑰時(shí)，需要選取兩個(gè)大素?cái)?shù)產(chǎn)生密鑰時(shí)，需要選取兩個(gè)大素?cái)?shù)p和和qn 由于由于n=pq是公開(kāi)的，因此這兩個(gè)素?cái)?shù)應(yīng)該是公開(kāi)的，因此這兩個(gè)素?cái)?shù)應(yīng)該足夠大以保證平安性。足夠大以保證平安性。n 如果選取如果選取p和和q為為10100左右的大素?cái)?shù)，那么左右的大素?cái)?shù)，那么n的階為的階為10200，每個(gè)明文分組可以含有，每個(gè)明文分組可以含有664位位102002664，即，即83個(gè)個(gè)8

38、比特字節(jié)，這比特字節(jié)，這比比DES的數(shù)據(jù)分組的數(shù)據(jù)分組8個(gè)個(gè)8比特字節(jié)大得多比特字節(jié)大得多。n 因此如何有效地尋找大素?cái)?shù)是第一個(gè)需要因此如何有效地尋找大素?cái)?shù)是第一個(gè)需要解決的問(wèn)題。解決的問(wèn)題。密鑰素?cái)?shù)選取問(wèn)題密鑰素?cái)?shù)選取問(wèn)題62n尋找大素?cái)?shù)過(guò)程尋找大素?cái)?shù)過(guò)程n先隨機(jī)選取一個(gè)大奇數(shù)先隨機(jī)選取一個(gè)大奇數(shù)(例如用偽隨機(jī)數(shù)產(chǎn)例如用偽隨機(jī)數(shù)產(chǎn)生器生器)n然后用素性檢驗(yàn)算法然后用素性檢驗(yàn)算法(例如前面介紹的例如前面介紹的AKS算法算法)檢驗(yàn)這一奇數(shù)是否為素?cái)?shù)，檢驗(yàn)這一奇數(shù)是否為素?cái)?shù)，n如果不是那么選取另一大奇數(shù)，重復(fù)這一過(guò)如果不是那么選取另一大奇數(shù)，重復(fù)這一過(guò)程，直到找到素?cái)?shù)為止。程，直到找到素?cái)?shù)為止。n

39、可見(jiàn)尋找大素?cái)?shù)是一個(gè)比較繁瑣的工作。在可見(jiàn)尋找大素?cái)?shù)是一個(gè)比較繁瑣的工作。在RSA體制中，只有在產(chǎn)生新密鑰時(shí)才需執(zhí)行體制中，只有在產(chǎn)生新密鑰時(shí)才需執(zhí)行這一工作。這一工作。密鑰素?cái)?shù)選取問(wèn)題密鑰素?cái)?shù)選取問(wèn)題63RSA的平安性的平安性nRSA的平安性是基于分解大整數(shù)的困難性的平安性是基于分解大整數(shù)的困難性假定假定n如果分解如果分解n=pq，那么立即獲得，那么立即獲得(n)=(p-1)(q-1)，從而能夠確定，從而能夠確定e的模的模(n)乘法逆乘法逆dn由由n直接求直接求(n)等價(jià)于分解等價(jià)于分解n64RSA的平安性的平安性RSA編號(hào)編號(hào)十進(jìn)制位數(shù)十進(jìn)制位數(shù)懸賞獎(jiǎng)金懸賞獎(jiǎng)金分解日期分解日期分解者分解者

40、RSA-5761741萬(wàn)美元萬(wàn)美元2003年年J. Franke等等RSA-6401932萬(wàn)美元萬(wàn)美元2005年年J. Franke等等RSA-7042123萬(wàn)美元萬(wàn)美元-RSA-7682325萬(wàn)美元萬(wàn)美元2009年年T. Kleinjung等等RSA-8962707.5萬(wàn)美元萬(wàn)美元-RSA-102430910萬(wàn)美元萬(wàn)美元-RSA-153646315萬(wàn)美元萬(wàn)美元-RSA-204861720萬(wàn)美元萬(wàn)美元-1991年，年，RSA實(shí)驗(yàn)室提出了大數(shù)分解挑戰(zhàn)，實(shí)驗(yàn)室提出了大數(shù)分解挑戰(zhàn)，2007年截止。年截止。65RSA的平安性的平安性n密鑰長(zhǎng)度應(yīng)該介于密鑰長(zhǎng)度應(yīng)該介于1024比特到比特到2048比特比特

41、之間之間np和和q的位數(shù)應(yīng)該差不多的位數(shù)應(yīng)該差不多n|p-q|要比較大要比較大np-1和和q-1都應(yīng)該有大的素因子。都應(yīng)該有大的素因子。np+1和和q+1都應(yīng)該有大的素因子。都應(yīng)該有大的素因子。nd應(yīng)該大于應(yīng)該大于n1/466對(duì)對(duì)RSA的攻擊共模攻擊的攻擊共模攻擊n每一用戶(hù)有相同的模數(shù)每一用戶(hù)有相同的模數(shù)nn設(shè)用戶(hù)的公開(kāi)密鑰分別為設(shè)用戶(hù)的公開(kāi)密鑰分別為e1 1, ,e2 2, ,且且e1 1, ,e2 2互素，明互素，明文消息為文消息為m, ,密文為密文為n因?yàn)橐驗(yàn)? (e1 1, ,e e2 2)=1,)=1,用歐幾里德算法可求用歐幾里德算法可求re1 1+ +se2 2=1=1，設(shè)設(shè)r為負(fù)

42、數(shù)，進(jìn)而可計(jì)算出為負(fù)數(shù)，進(jìn)而可計(jì)算出( (c1-1) )-r c2s=m(mod (mod n) )nmcnmceemodmod212167對(duì)對(duì)RSA的攻擊低指數(shù)攻擊的攻擊低指數(shù)攻擊 設(shè)三用戶(hù)的加密鑰設(shè)三用戶(hù)的加密鑰e e均選均選3 3，而有不同的模，而有不同的模n1,n2, n1,n2, n3n3，假設(shè)有一用戶(hù)將消息，假設(shè)有一用戶(hù)將消息m m傳給三個(gè)用戶(hù)的密文分傳給三個(gè)用戶(hù)的密文分別為別為 c1=m3 (mod n1) mn1 c1=m3 (mod n1) mn1 c2=m3 (mod n2) mn2 c2=m3 (mod n2) mn2 c3=m3 (mod n3) mn3 c3=m3 (

43、mod n3) mn3 一般選一般選n1,n2,n3n1,n2,n3互素互素( (否那么可求出公因子，而否那么可求出公因子，而降 低 平 安 性降 低 平 安 性 ) ) ， 利 用 中 國(guó) 剩 余 定 理 ， 可 從， 利 用 中 國(guó) 剩 余 定 理 ， 可 從c1,c2,c3c1,c2,c3求出求出 m3=c (mod n1n2n3) m3=c (mod n1n2n3)。由。由mn1,mn2,mn3mn1,mn2,mn3，可得，可得m3n1n2n3m3n1n2n3，故有，故有3mc68RSA密碼練習(xí)密碼練習(xí)n用快速指數(shù)計(jì)算算法求用快速指數(shù)計(jì)算算法求 10500 mod 561n在在RSA密

44、碼體制中，設(shè)公鑰密碼體制中，設(shè)公鑰(e,n)為為(5,35)n如果明文如果明文M=10，求密文，求密文Cn如果密文如果密文C=10，求明文，求明文M69五、五、橢圓曲線密碼體制橢圓曲線密碼體制Elliptic Curve Cryptography70橢圓曲線密碼概述橢圓曲線密碼概述n橢圓曲線密碼體制橢圓曲線密碼體制(ECC)(ECC)利用有限域上的橢利用有限域上的橢圓曲線的代數(shù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)公鑰密碼圓曲線的代數(shù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)公鑰密碼n19851985年由年由 Neal Koblitz Neal Koblitz 和和 Victor S. Victor S. Miller Miller 這兩位數(shù)學(xué)家分別獨(dú)

45、立提出這兩位數(shù)學(xué)家分別獨(dú)立提出n獲得同樣的平安性，密鑰長(zhǎng)度較獲得同樣的平安性，密鑰長(zhǎng)度較RSARSA短得多短得多n被被IEEEIEEE公鑰密碼標(biāo)準(zhǔn)公鑰密碼標(biāo)準(zhǔn)P1363P1363采用采用71橢圓曲線橢圓曲線n橢圓曲線的曲線方程是以下形式的三次方程橢圓曲線的曲線方程是以下形式的三次方程y2=x3+ax+b其中判別式其中判別式=4a3+27b20。定義中還包含一個(gè)定義中還包含一個(gè)稱(chēng)為無(wú)窮遠(yuǎn)點(diǎn)的元素，記為稱(chēng)為無(wú)窮遠(yuǎn)點(diǎn)的元素，記為O。n橢圓曲線的所有點(diǎn)加上無(wú)窮遠(yuǎn)點(diǎn)橢圓曲線的所有點(diǎn)加上無(wú)窮遠(yuǎn)點(diǎn)O之后組成之后組成一個(gè)加法群。一個(gè)加法群。72橢圓曲線例子橢圓曲線例子73橢圓曲線的加法橢圓曲線的加法n如果其上

46、的如果其上的3 3個(gè)點(diǎn)位于同一直線上，個(gè)點(diǎn)位于同一直線上，那么定義那么定義它們的和為它們的和為O O。nO O為加法單位元，即對(duì)為加法單位元，即對(duì)ECEC上任一點(diǎn)上任一點(diǎn)P,P,有有P+O=PP+O=Pn設(shè)設(shè)P P1 1=(x,y)=(x,y)是是ECEC上一點(diǎn)，加法逆元定義為上一點(diǎn)，加法逆元定義為P P2 2= =- -P P1 1 =(x,=(x, y)y)nP P1 1,P,P2 2連線延長(zhǎng)到無(wú)窮遠(yuǎn)，得到連線延長(zhǎng)到無(wú)窮遠(yuǎn)，得到ECEC上另一點(diǎn)上另一點(diǎn)O,O,即即P P1 1,P,P2 2,O,O三點(diǎn)共線，所以三點(diǎn)共線，所以P P1 1+P+P2 2+O=O, P+O=O, P1 1+P+

47、P2 2=O, P=O, P2 2= =- -P P1 1nO OO OO,O=O,O=- -O O74橢圓曲線的加法橢圓曲線的加法nQ,RQ,R是是ECEC上上x(chóng) x坐標(biāo)不同的兩點(diǎn)，坐標(biāo)不同的兩點(diǎn)，Q+RQ+R定義為：畫(huà)定義為：畫(huà)一條通過(guò)一條通過(guò)Q,RQ,R的直線與的直線與ECEC交于交于P P1 1( (交點(diǎn)是唯一的，交點(diǎn)是唯一的，除非做的除非做的Q,RQ,R點(diǎn)的切線，此時(shí)分別取點(diǎn)的切線，此時(shí)分別取P P1 1=Q=Q或或P P1 1=R)=R)。由。由Q+R+PQ+R+P1 1=O,=O,得得Q+R=Q+R=- -P P1 1n點(diǎn)點(diǎn)Q Q的倍數(shù)定義如下：在的倍數(shù)定義如下：在Q Q點(diǎn)做點(diǎn)做

48、ECEC的一條切線，的一條切線，設(shè)切線與設(shè)切線與ECEC交于交于S,S,定義定義2Q=Q+Q=2Q=Q+Q=- -S S。類(lèi)似可定。類(lèi)似可定義義3Q=Q+Q+Q,3Q=Q+Q+Q, ,n上述加法滿(mǎn)足加法的一般性質(zhì)，如交換律、結(jié)上述加法滿(mǎn)足加法的一般性質(zhì)，如交換律、結(jié)合律等合律等75有限域上的橢圓曲線有限域上的橢圓曲線n密碼中普遍采用的是有限域上的橢圓曲線密碼中普遍采用的是有限域上的橢圓曲線n曲線方程中的所有系數(shù)都是某一有限域曲線方程中的所有系數(shù)都是某一有限域GF( (p) )中的元素中的元素( (p為大素?cái)?shù)為大素?cái)?shù)) )，即曲線方即曲線方程為程為y2=x3+ax+b (mod p) a,bGF

49、(p), =4a3+27b20 (mod p)n判別式不為零保證任何點(diǎn)判別式不為零保證任何點(diǎn)Q的切線總是存的切線總是存在，即在，即Q+Q總可以定義。總可以定義。76有限域上的橢圓曲線有限域上的橢圓曲線n例：例：p=23,a=b=1, 4a4a3 3+27b+27b2 2=8=80 (mod23),方程為方程為y2=x3+x+1 (modp)，曲線圖形如前面。因?yàn)槭悄＃€圖形如前面。因?yàn)槭悄的曲線，我們可以令的曲線，我們可以令0 xp,0yp0 xp,0yp 。設(shè)。設(shè)Ep(a,b)表示表示EC上點(diǎn)集上點(diǎn)集(x,y)|0 xp,0yp,x,y)|0 xp,0yp,且且x,yx,y均為均為整數(shù)整

50、數(shù)并上并上O.77橢圓曲線點(diǎn)集產(chǎn)生方法橢圓曲線點(diǎn)集產(chǎn)生方法n對(duì)每一對(duì)每一x(0 xp且且x為整數(shù)，計(jì)算為整數(shù)，計(jì)算x3+ax+b (mod p)n決定求出的值在模決定求出的值在模p下是否有平方根，如下是否有平方根，如果沒(méi)有那么橢圓曲線上沒(méi)有與這一果沒(méi)有那么橢圓曲線上沒(méi)有與這一x對(duì)應(yīng)對(duì)應(yīng)的點(diǎn)；如果有，那么求出兩個(gè)平方根。的點(diǎn)；如果有，那么求出兩個(gè)平方根。78有限域上有限域上EC的加法的加法n如果如果P,QEp(a,b)P,QEp(a,b)nP+O=PP+O=Pn如果如果P P(x,y),(x,y),那么那么(x,y)+(x,(x,y)+(x,y)y)O OnP P(x1,y1),Q=(x2,y2

51、),P-Q, P+Q=(x3,y3)(x1,y1),Q=(x2,y2),P-Q, P+Q=(x3,y3)nx3=l2-x1-x2x3=l2-x1-x2mod pmod pn y3=l(x1-x3)-y1 (mod p) y3=l(x1-x3)-y1 (mod p)QPyaxQPxxyy12112122379有限域上有限域上EC的加法的加法n例如：對(duì)于例如：對(duì)于E23(1,1)，P=(3,10) 和和 Q=(9,7) 是是其上的兩個(gè)點(diǎn)其上的兩個(gè)點(diǎn)n計(jì)算計(jì)算P+Qn計(jì)算計(jì)算2P=P+P80有限域上有限域上EC的加法的加法n例子：例子：y2=x3-2x-3是系數(shù)在是系數(shù)在GF(7)上的橢圓曲上的橢圓

52、曲線，線，P=(3,2)是其上的一點(diǎn)，求是其上的一點(diǎn)，求10P。n解答：解答：n2P=P+P=(3,2)+(3,2)=(2,6)n4P=2P+2P=(2,6)+(2,6)=(0,5)n8P=4P+4P=(0,5)+(0,5)=(2,1)n10P=2P+8P=(2,6)+(2,1)=O81有限域上有限域上EC的點(diǎn)數(shù)的點(diǎn)數(shù)82有限域上有限域上EC的點(diǎn)數(shù)的點(diǎn)數(shù)83橢圓曲線運(yùn)算練習(xí)橢圓曲線運(yùn)算練習(xí)n橢圓曲線橢圓曲線 E11(1,6) 表示曲線表示曲線 y2=x3+x+6 (mod 11)，求其上面的所有點(diǎn)。，求其上面的所有點(diǎn)。n點(diǎn)點(diǎn)G=(2,7)在橢圓曲線上，求在橢圓曲線上，求2G, 3G, , 一一直到直到 nG=O。84明文到橢圓曲線的嵌入明文到橢圓曲線的嵌入85明文到橢圓曲線的嵌入明文到橢圓曲線的嵌入86ElGamal密碼體制密碼體制n由離散對(duì)數(shù)問(wèn)題可以構(gòu)造由離散對(duì)數(shù)問(wèn)題可以構(gòu)造ElGamalElGamal密碼體制密碼體制n有限域上的離散對(duì)數(shù)問(wèn)題有限域上的離散對(duì)數(shù)問(wèn)題n在