公鑰密碼學(xué)Read課件

1、第九章 公鑰密碼學(xué) 第1頁(yè)，共41頁(yè)。對(duì)稱密碼體制的缺陷： 第2頁(yè)，共41頁(yè)。 9.1公鑰密碼學(xué)思想 定義9.1.1一個(gè)公鑰密碼體制是這樣的一個(gè)5元組M,C,K，EK，DK，且滿足如下的條件：1.M是可能消息的集合；2.C是可能的密文的集合；3. 密鑰空間K是一個(gè)可能密鑰的有限集； 4對(duì)每一個(gè)K=K1，K2 K，都對(duì)應(yīng)一個(gè)加密算法EK1 E, EK1:MC和解密算法DK2 D,DK2:C M,滿足對(duì)于任意的m M,都有c= EK1（m）,m= DK2(c)=DK2(EK1（m）)=m；5對(duì)于所有的KK，在已知E的情況下推出D是計(jì)算上不可能的； 對(duì)每一個(gè)K K，函數(shù)EK1和DK2都是多項(xiàng)式時(shí)間可

2、計(jì)算的函數(shù)。EK1是一個(gè)公開(kāi)函數(shù),K1 稱作公鑰；而DK2是一個(gè)秘密函數(shù)，K2稱作私鑰，由用戶秘密地保存。 第3頁(yè)，共41頁(yè)。public-key/two-key/asymmetric 包括兩個(gè)密鑰:公開(kāi)密鑰(a public-key), 可以被任何人知道, 用于加密或驗(yàn)證簽名私鑰( private-key), 只能被消息的接收者或簽名者知道,用于解密或簽名加密或驗(yàn)證簽名者不能解密或多或生成簽名.是密碼學(xué)幾千年歷史中最有意義的結(jié)果第4頁(yè)，共41頁(yè)。3.公鑰加密方案第5頁(yè)，共41頁(yè)。4.公鑰密碼理論由私鑰及其他密碼信息容易計(jì)算出公開(kāi)密鑰 (a polynomial time (P-time) p

3、roblem) 由公鑰及算法描述,計(jì)算私鑰是難的 (an NP-time problem) 因此,公鑰可以發(fā)布給其他人(wishing to communicate securely with its owner )密鑰分配問(wèn)題不是一個(gè)容易的問(wèn)題(the key distribution problem )第6頁(yè)，共41頁(yè)。5.公鑰算法分類Public-Key Distribution Schemes (PKDS) 用于交換秘密信息(依賴于雙方主體) 常用于對(duì)稱加密算法的密鑰Public Key Encryption (PKE) 用于加密任何消息 任何人可以用公鑰加密消息 私鑰的擁有者可以解密

4、消息 任何公鑰加密方案能夠用于密鑰分配方案PKDS 許多公鑰加密方案也是數(shù)字簽名方案Signature Schemes 用于生成對(duì)某消息的數(shù)字簽名私鑰的擁有者生成數(shù)字簽名任何人可以用公鑰驗(yàn)證簽名 第7頁(yè)，共41頁(yè)。6.公鑰的安全性依賴于足夠大大的困難性差別類似與對(duì)稱算法,窮搜索在理論上是能夠破解公鑰密碼 exhaustive search 但實(shí)際上,密鑰足夠長(zhǎng) (512bits) 一般情況下,有一些已知的困難問(wèn)題(hard problem” 要求足夠大的密鑰長(zhǎng)度 (512 bits) 導(dǎo)致加密速度比對(duì)稱算法慢第8頁(yè)，共41頁(yè)。 2. RSA (Rivest, Shamir, Adleman)

5、使用最廣泛的公鑰加密算法Rivest, Shamir & Adleman (RSA) in 1977 R L Rivest, A Shamir, L Adleman, On Digital Signatures and Public Key Cryptosystems, Communications of the ACM, vol 21 no 2, pp120-126, Feb 1978 第9頁(yè)，共41頁(yè)。3. RSA Setup每個(gè)用戶生成自己的公鑰私鑰對(duì):選擇兩個(gè)隨機(jī)大素?cái)?shù) (100 digit), p, q 計(jì)算模數(shù) N=p.q 選擇一個(gè)隨機(jī)加密密鑰匙 e : eN, gcd(e,(N)

6、=1 解下列同余方程,求解密密鑰 d: e.d=1 mod (N) and 0=d=N 公開(kāi)加密密鑰: Kr=er,Nr 保存其解密似鑰: K-1r=d,p,q 第10頁(yè)，共41頁(yè)。4。RSA 參數(shù)選擇需要選擇足夠大的素?cái)?shù) p, q 通常選擇小的加密指數(shù)e,且與(N) 互素e 對(duì)所有用戶可以是相同的 最初建議使用e=3現(xiàn)在3太小常使用 e=216-1 = 65535 解密指數(shù)比較大第11頁(yè)，共41頁(yè)。5. RSA Usage 要加密消息 M， 發(fā)送者要得到接收者的公鑰Kr=er,Nr 計(jì)算: C=Mer mod Nr, where 0=MN 為解密 C， 接收者使用私鑰 K-1r=d,p,q

7、計(jì)算: M=Cd mod Nr 第12頁(yè)，共41頁(yè)。6. RSA理論RSA 基于Fermats Theorem: if N = pq where p, q are primes, then:X(N) = 1 mod N for all x not divisible by p or q, ie gcd(x,(N)=1 where (N)=(p-1)(q-1) 但在 RSA 中，e & d 是特殊選擇的ie e.d=1 mod (N) 或e.d=1+R(N) hence have:M = Cd = Me.d = M1+R(N) = M1.(M(N)R = M1.(1)R = M1 mod N 第

8、13頁(yè)，共41頁(yè)。8。RSA舉例例子：1. 選素?cái)?shù)p=47和q71，得n=3337, (n)=46703220；2. 選擇e=79，求得私鑰d=e -1 1019(mod 3220）。3. 公開(kāi)n=3337和e=79.4. 現(xiàn)要發(fā)送明文688，計(jì)算：68879(mod 3337)=15705.收到密文1570后，用私鑰d1019進(jìn)行解密： 15701019（mod 3337)=688第14頁(yè)，共41頁(yè)。9。RSA 安全性 RSA 安全性基于計(jì)算 (N)的困難性 要求分解模N 第15頁(yè)，共41頁(yè)。10. RSA的實(shí)現(xiàn)問(wèn)題需要計(jì)算模 300 digits (or 1024+ bits) 的乘法計(jì)算

9、機(jī)不能直接處理這么大的數(shù)（計(jì)算速度很慢）需要考慮其它技術(shù)，加速RSA的實(shí)現(xiàn)第16頁(yè)，共41頁(yè)。11. RSA 的快速實(shí)現(xiàn)加密很快，指數(shù)小解密比較慢，指數(shù)較大利用中國(guó)剩余定理CRT，CRT 對(duì)RSA解密算法生成兩個(gè)解密方程 （利用M = Cd mod R ）即: M1 = M mod p = (C mod p)d mod (p-1) M2 = M mod q = (C mod q)d mod (q-1) 解方程 M = M1 mod p M = M2 mod q 具有唯一解（利用CRT ）：:M = (M2 +q - M1)u mod q p + M1 其中 p.u mod q = 1 第17頁(yè)

10、，共41頁(yè)。9.2.3概率素性檢測(cè) 定義9.2.3：如果P是素?cái)?shù)，且a小于p,如果至少存在一個(gè)x 1，p-1滿足x2a(modp)，則我們稱a是模p的二次剩余（quadratic residue）。定義9.2.4：設(shè)p是一奇素?cái)?shù)，對(duì)任何a0,我們定義勒讓德符號(hào)（Legendre symbol）L(a,p)為 0 如果a 0(modp) L(a,p)= 1 如果a是模p的二次剩余 -1 如果a是p的非二次剩余定理9.2.1（歐拉準(zhǔn)則）：設(shè)p是素?cái)?shù)，那么x是模p的二次剩余當(dāng)且僅當(dāng) x(P-1)/2 1(modp) 第18頁(yè)，共41頁(yè)。推論9.2.1：假設(shè)p是素?cái)?shù)，那么L(a,p) a(P-1)/2

11、(modp) 定義9.2.5：雅可比符號(hào)（Jacobi symbol）,記作J(a,n),是勒讓德符號(hào)的一般化表示，它定義在任意正整數(shù)a和奇整數(shù)n上。設(shè)n的素?cái)?shù)因子分解式為pe1pek,則J(a，n)=L(a，p1)e1 L(a，p)ek 第19頁(yè)，共41頁(yè)。 對(duì)一個(gè)奇整數(shù)n的Solovay-strassen素性測(cè)試 1. 選擇一隨機(jī)整數(shù)a，滿足a 1,n-12.如果J(a,n)=a(n-1)/2modn 則回答“n是素?cái)?shù)”否則 回答“n是合數(shù)”第20頁(yè)，共41頁(yè)。7.Diffie-Hellman 密鑰分配方案公鑰密碼問(wèn)世 Diffie & Hellman in 1976: 密鑰交換的實(shí)際方法

12、 公鑰方案概念的提出W Diffie, M E Hellman, New directions in Cryptography, IEEE Trans. Information Theory, IT-22, pp644-654, Nov 1976 James Ellis (UK CESG) 在案970年曾提出此概念第21頁(yè)，共41頁(yè)。12。El Gamal 公鑰加密方案Diffie-Hellman key distribution scheme 的變形能夠用于安全交換密鑰published in 1985 by ElGamal: T. ElGamal, A Public Key Cryptos

13、ystem and a Signature Scheme Based on Discrete Logarithms, IEEE Trans. Information Theory, vol IT-31(4), pp469-472, July 1985. 安全性是基于離散對(duì)數(shù) 缺點(diǎn)：增加了消息長(zhǎng)度（2倍） 第22頁(yè)，共41頁(yè)。13 密鑰建立密鑰生成：選取一個(gè)大素?cái)?shù)p及本原元a mod p接收者 Bob有一個(gè)密秘鑰 xB 計(jì)算 yB = axB mod p 第23頁(yè)，共41頁(yè)。14. El Gamal 加密為加密 M 發(fā)送者選擇隨機(jī)數(shù)k, 0=k=p-1 計(jì)算消息密鑰 K : K = yBk mo

14、d p 計(jì)算密文對(duì): C = C1,C2 C1 = ak mod p C2 = K.M mod p 發(fā)送到接收者k 需要永久保密 第24頁(yè)，共41頁(yè)。15. El Gamal 解密首先計(jì)算 message key K K = C1xB mod p = ak.xB mod p 計(jì)算明文: M = C2.K-1 mod p 第25頁(yè)，共41頁(yè)。16. El Gamal Example選擇 p=97 及本原根 a=5 recipient Bob 選擇 秘密鑰xB=58 & 計(jì)算并發(fā)布公鑰yB=558=44 mod 97 Alice 要加密 M=3 to Bob 首先得到 Bob的公開(kāi)密鑰 yB=44

15、 選擇隨機(jī) k=36 計(jì)算:K=4436=75 mod 97 計(jì)算密文對(duì): C1 = 536 = 50 mod 97 C2 = 75.3 mod 97 = 31 mod 97 發(fā)送 50,31 to Bob Bob 恢復(fù) message key K=5058=75 mod 97 Bob 計(jì)算 K-1 = 22 mod 97 Bob 恢復(fù)明文 M = 31.22 = 3 mod 97 第26頁(yè)，共41頁(yè)。9.3.1離散對(duì)數(shù)問(wèn)題算法 第27頁(yè)，共41頁(yè)。第28頁(yè)，共41頁(yè)。9.4 基于糾錯(cuò)碼的公鑰密碼體制糾錯(cuò)碼理論中的NPC問(wèn)題。 問(wèn)題1 陪集重量問(wèn)題 問(wèn)題2 重量分布問(wèn)題 問(wèn)題3 最小距離問(wèn)題

16、當(dāng)前關(guān)于建立基于糾錯(cuò)碼的密碼體制很多是基于傳統(tǒng)的Hamming距離的。 第29頁(yè)，共41頁(yè)。第30頁(yè)，共41頁(yè)。9.5橢圓曲線公鑰體制 1橢圓曲線 定義9.5.1：設(shè)p是一個(gè)大于3的素?cái)?shù)，在Zp上的橢圓曲線y2=x3+ax+b 由一個(gè)基于同余式y(tǒng)2=x3+ax+b modp的解集（x，y）Zp*Zp和一個(gè)稱為無(wú)窮遠(yuǎn)點(diǎn)的特定點(diǎn)O組成，這里的a,b Zp是二個(gè)滿足4a+27b0 modp 的常數(shù)。 第31頁(yè)，共41頁(yè)。橢圓曲線上的運(yùn)算設(shè)P=(x1,y1) E, Q=(x2,y2) E, 若 x1=x2且y1=-y2 ,那么 P+Q=O;否則P+Q=(x3,y3) ,這里的x3=2-x1-x2,y3

17、= (x1-x3)-y1. x3=第32頁(yè)，共41頁(yè)。2橢圓曲線密碼體制 定理9.5.1（Hasse定理）：如果E是定義在域GF(q)上的橢圓曲線，N是E上的點(diǎn)(x,y) GF(q)的數(shù)目，則第33頁(yè)，共41頁(yè)。第34頁(yè)，共41頁(yè)。橢圓曲線密碼體制有如下的一些特點(diǎn) ：1.在安全性相當(dāng)?shù)那疤嵯? 可使用較短的密鑰. 2.橢圓曲線密碼體制是建立在一個(gè)不同于大整數(shù)分解及素域乘法群離散對(duì)數(shù)問(wèn)題的數(shù)學(xué)難題之上. 3 橢圓曲線資源豐富, 同一個(gè)有限域上存在著大量不同的橢圓曲線, 這為安全性增加了額外的保證。 4. 在執(zhí)行速度方面,橢圓曲線密碼體制較對(duì)應(yīng)的離散對(duì)數(shù)體制要快, 且在簽名和解密方面較RSA 快,

18、 但在簽名驗(yàn)證和加密方面較RSA 慢. 5橢圓曲線密碼體制的安全性分析成果并不豐碩. 也許這可視為橢圓曲線密碼體制具有高強(qiáng)度的一種證據(jù),因此, 大多數(shù)密碼學(xué)家對(duì)這種密碼體制的前景持樂(lè)觀態(tài)度. 第35頁(yè)，共41頁(yè)。9.6其他公開(kāi)密鑰密碼體制 9.6.1Goldwasser-Micali概率公開(kāi)密鑰密碼系統(tǒng) 第36頁(yè)，共41頁(yè)。第37頁(yè)，共41頁(yè)。Goldwasser-Micali概率公開(kāi)密鑰密碼系統(tǒng)的安全性分析與討論 對(duì)于攻擊者來(lái)說(shuō)，當(dāng)他截獲到密文(C1,C2,Ck)時(shí)，他能求出J(Ci,n) ，但當(dāng)mi=0，J(Ci,n)= J(xi2,n)=1，當(dāng)mi=1, J(yxi2,n)= J(y,n)J(xi2,n)=1,攻擊者無(wú)法獲得其它的任何信息，而對(duì)A來(lái)說(shuō)，因?yàn)樗麚碛兴接忻荑€p和q ，可求出J(Ci,p)，J(Ci,q) , 從而