第七章公開金鑰密碼系統(tǒng)(Public-Key Cryptosystems)

1、1第七章第七章公開金鑰密碼系統(tǒng)公開金鑰密碼系統(tǒng)(Public-Key Cryptosystems)2目錄7.1 公開金鑰基本概念7.2 RSA公開金鑰密碼機制7.3 ElGamal的公開金鑰密碼系統(tǒng)7.4 橢圓曲線密碼系統(tǒng)7.5 混合式的加密機制7.6 密碼系統(tǒng)的評估37.1 公開金鑰基本概念對稱式密碼系統(tǒng)有金鑰的管理問題，例如要與N個人做秘密通訊，那麼就必須握有N把秘密金鑰為了改善對稱式密碼系統(tǒng)問題，於是便有公開金鑰密碼系統(tǒng)(Public-Key Cryptosystems)的產(chǎn)生4Secret-Key Cryptosystem祕密金鑰密碼系統(tǒng)(Secret-Key Cryptosystem

2、s) 又稱單金鑰密碼系統(tǒng)(One-Key Cryptosystems)也稱對稱密碼系統(tǒng)(Symmetric Cryptosystems)優(yōu)點：加解密速度快缺點：有金鑰管理的問題 每位使用者需儲存n-1把Keys U1U2U5U3U457.1.1 公開金鑰密碼系統(tǒng)的基本概念CA明文加密解密明文密文密文明文解密加密明文密文密文張三張三s 私有金鑰李四李四s 私有金鑰張三張三李四李四李四李四s 公開金鑰張三張三s 公開金鑰SendSend金鑰6Public-Key Cryptosystem公開金鑰密碼系統(tǒng)(Public-Key Cryptosystems) 又稱雙金鑰密碼系統(tǒng)(Two-Key Cry

3、ptosystems)也稱非對稱密碼系統(tǒng)(Asymmetric Cryptosystems)優(yōu)點：沒有金鑰管理的問題 高安全性 有數(shù)位簽章功能缺點：加解密速度慢 著名之公開密碼系統(tǒng)： RSA密碼系統(tǒng) ElGamal密碼系統(tǒng)7 非對稱式密碼系統(tǒng)的一種。 1978年美國麻省理工學院三位教授Rivest、Shamir、 Adleman (RSA) 所發(fā)展出來的。 利用公開金鑰密碼系統(tǒng)作為資料加密的方式，可達 到資料加密及數(shù)位簽署的功能。 Encryption : RSA 加密演算法，明文加密使用區(qū)塊為每 次加密的範圍，使用對方公開金鑰(Public Key)將明文加密。 Decryption : R

4、SA 解密演算法，必須使用自己的私有金 鑰(Private Key)才能將密文解出。7.2 RSA公開金鑰密碼機制81. 張三選 2 個大質(zhì)數(shù) p 和 q (至少至少100位數(shù)位數(shù))，令 N = p q2. 再計算(N)=(p-1)(q-1)，並選 1 個與(N)互質(zhì)數(shù) e (N)為Eulers Totient函數(shù)，其意為與與N互質(zhì)的數(shù)之個互質(zhì)的數(shù)之個數(shù)數(shù)3. (e,N) 即為張三的公開金鑰 加密法加密法為 C = Me mod N4. 張三選 1 個數(shù) d，滿足 e d mod (N) = 15. d 即為張三的解密金鑰(亦稱私有金鑰或祕密金鑰) 解密法解密法為 M = Cd mod N R

5、SA RSA之安全性取決於質(zhì)因數(shù)分解之困難度之安全性取決於質(zhì)因數(shù)分解之困難度 要將很大的要將很大的N N因數(shù)分解成因數(shù)分解成P P跟跟Q Q之相乘，是很困難的之相乘，是很困難的7.2.1 RSA 的加解密機制9RSA 演算法演算法- 例子例子1. 張三選 p=3 ， q=11 ; 此時 N = p q = 3 x 11 = 332. 張三選出 1 個與 ( p-1 ) x ( q-1 ) = ( 3-1 )( 11-1 ) = 2 x 10 = 20互質(zhì)數(shù) e=33. ( e, N) = (3,33) 即為張三的公開金鑰4. 張三選 1 個數(shù) d=7 當作解密金鑰，滿足 e d 1 mod 2

6、0 ( 7 x 3 1 mod 20 )令明文令明文 M = 19加密加密 : C = Me mod N = 193 mod 33 = 28解密解密 : M = Cd mod N = 287 mod 33 = 1910Fermats Little Theorem If p is a prime, and a is not a multiple of p, then Fermats little theorem says ap-1 mod p =1 Ex. 26 mod 7 =1 費瑪費瑪(Fermat)定理定理:若若p為質(zhì)數(shù)且為質(zhì)數(shù)且(a,p)互質(zhì)互質(zhì)，則 ap-1 mod p = 1 11E

7、ulers Theorem If gcd(a,n)=1, then 1mod)(nanwhere () called Euler phi function. Euler通用定理通用定理:若若a，n互質(zhì)互質(zhì)，則 a(n) mod n = 1 定理定理: (P) = P-1 若若P為質(zhì)數(shù)為質(zhì)數(shù) (N) = (PQ) = (P)(Q) = (P-1)(Q-1) It is the number of positive integers less than n that are relatively prime to n. If n is a prime, (n)=n-1.If n=pq, where

8、 p and q are prime, then (n)=(p-1)(q-1)12Modular Inverse Problem The problem is finding an x such that 1 = (a * x) mod n This is also written as a-1 mod n =xNote: a-1 mod n =x has a unique solution if a and n are relatively prime.If a and n are not relatively prime, then a-1 mod n =x has no solution

9、. Ex. The inverse of 5, modulo 14, is 3. 2 has no inverse modulo 14. 13How to Find Multiplicative InverseMethod 1: Using Eulers Theorem x= a-1 mod n ax mod n =1 x=a(n)-1 mod n If gcd(a,n)=1, then a(n) mod n=1 Ex. What is the inverse of 5, modulo 7 ? 56-1 mod 7 = 55 mod 7 =3 Note: (n) is not always k

10、nown 14How to Find Multiplicative InverseMethod 2: Using Extended Euclidean Algorithm Euclidean Algorithm Find gcd(a,n) Let r0=n, r1=a, we get r0=r1g1+r2 , r1=r2g2+r3 , . . . , rj-2=rj-1gj-1+rj , . . ., rm-4=rm-3gm-3+rm-2, rm-3=rm-2gm-2+rm-1, rm-2=rm-1gm-1+rm, rm-1=rmgm 15We can find gcd(a, n) = sa

11、+ tn, where s and t are integers. If gcd(a,n)=1, we get sa + tn =1.We can find s and t by using rm=gcd(a,n)=rm-2-rm-1gm-1because rm-1= rm-3 rm-2gm-2so gcd(a,n) = rm-2 - (rm-3 rm-2gm-2)gm-1= (1+gm-1gm-2 )rm-2 g m-1rm-3 and so on. sa+tn = 1 sa + tn mod n=1 sa mod n=1 s = a-1 mod n 16Why RSA is Correct

12、 C = E(M) = Me mod n M = D(C) = Cd mod nCd=(Me)d=Med mod n since ed= 1 mod (p-1)(q-1)so Med = Ma(p-1)(q-1)+1 =MMa(p-1)(q-1) =MMa(n) mod nAccording to Eulers Theorem, we get M*1=M 17因式分解的問題因式分解的問題Factoring Problem Factoring a number means finding its prime number Ex: 10 = 2 * 5; 60 = 2 * 2 * 3 * 5How

13、ever, it is difficult to factor a large number.Try to factor the large number: 3337 RSA 的安全性便是植基於解因式分解的難題上的安全性便是植基於解因式分解的難題上18RSA 演算法演算法指數(shù)運算：計算指數(shù)運算：計算 x = AB mod N? a1:= A; b1:=B; x:=1; while b1 0 do begin while b1 mod 2 = 0 do begin b1 := b1 div 2; a1 := (a1 * a1) mod N; end b1 := b1 - 1; x := (x *

14、 a1) mod N end 計算計算 x = A17 mod N = A10001 mod N = A (A2)2)2)2 計算計算 x = A13 mod N = A1101 mod N = A (A2)2) (A2)2)2 計算計算 x = A7 mod N = A111 mod N = A (A2) (A2)2 19Public-Key Cryptosystems之特性1. D(d, E(e, M) = M，可還原性2. d 和 e很容易求得3. 若公開(e, n)，別人很難從(e, n)求得d，即只有自己知道如何解密(以e加密)4. E(e, D(d, M) = MPublic-ke

15、y Cryptosystems一定要能忍受Chosen-Plaintext Attack20Public-Key Cryptosystems之特性之特性( (續(xù)續(xù)) ) 滿足13項稱之為trap-door one-way function “one-way”因易加密而不易解密 “trap-door”若知一些特別資訊即可解密 滿足14項稱之為trap-door one-way permutation 13項為public-key cryptosystems之要求 若同時滿足第4項要求，則該保密法可用來製作數(shù)位簽章。21Digital Signature (數(shù)位簽章數(shù)位簽章)一般數(shù)位簽章具有下列功

16、能：n確認性(Authentication)：可確認文件來源的合法性，而非經(jīng)他人偽造。n完整性(Integrity)：可確保文件內(nèi)容不會被新增或刪除。n不可否認性(Non-repudiation)：簽章者事後無法否認曾簽署過此文件。 22數(shù)位簽章的基本概念237.2.2 RSA數(shù)位簽章S = Md張張mod N張張 M =? Se張張mod N張張張三使用自己的祕密金鑰對文件 M 做數(shù)位簽章S張三張三李四李四李四使用張三的公開金鑰確認數(shù)位簽章及文件傳送M及S一般使用時會先將文件M作HASH函數(shù)處理，使得HASH(M)比N小24數(shù)位簽章法(Digital Signature:)MHE|MHD比較

17、是否相等SKaPKaESKaH(M)為M之簽章DPKaESKaH(M)=H(M)512位元25RSA數(shù)位簽章+加密C = ( Md張張mod N張張 )e李李mod N李李M = ( Cd李李mod N李李)e張張mod N張張 張三對文件 M 做數(shù)位簽章後用李四的公用金鑰將簽章加密張三張三李四李四李四使用私有金鑰解開密文 C 再用張三的公開金鑰確認數(shù)位簽章傳送密文 C26 非對稱式密碼系統(tǒng)的一種。 1985年由ElGamal所發(fā)展出來的。 安全性導因於離散對數(shù)(Discrete Logarithm)之困難度。 相同明文可得到不相同的密文。 RSA密碼系統(tǒng)則是相同明文得到相同密文。 ElGam

18、al有訊息擴充的問題，RSA機制則沒有此問題7.3 ElGamal的公開金鑰密碼系統(tǒng)離散對數(shù)(Discrete Logarithm)的問題：若p為很大之質(zhì)數(shù)；g為p之原根 (primitive root) y = gx mod p雖已知y, g, p ，但要導出x值是很困難的 27 什麼是原根什麼是原根 ？原根 generators: if p is a prime, and g is less than p, then g is a generator mod p if for each b from 1 to p-1, there exists some a where ga b (mod

19、 p). g also called primitive root of mod p 21 mod 11 = 222 mod 11 = 423 mod 11 = 824 mod 11 = 525 mod 11 = 1026 mod 11 = 927 mod 11 =728 mod 11 = 329 mod 11 = 6210 mod 11 =12 is a generator modulo 113 is not a generator modulo 11 because there is no solution on 3a mod 11 =2 28解離散對數(shù)的問題解離散對數(shù)的問題This is

20、 a hard problem:Find x where ax mod n = bEx. If 3x mod 17 = 15, then x=6 Note: Not all discrete logarithms have solution.Ex. 3x mod 13 = 7, no solution ! 29張三將明文M以李四之公開金鑰加密：1. 張三選一個亂數(shù)r2. 計算 b = gr Mod P c = M yr mod P3. 張三送(b,c)給李四7.3.1 ElGamal的加解密機制李四之金鑰產(chǎn)生： y = gx mod Py為李四之公開金鑰x為李四之秘密金鑰P為很大之質(zhì)數(shù)g為與P

21、互質(zhì)之原根4. 李四收到(b,c)後計算 c (bx)-1 mod P = M30李四將明文M以李四之祕密金鑰製作簽章：1.李四選一個亂數(shù)k使得gcd(k,p-1)=12.計算r = gk mod p3.李四計算s使得M = (xr+ks) mod (p-1)4.李四送(M,r,s)給驗證者(張三)7.3.2 ElGamal的數(shù)位簽章機制李四之金鑰產(chǎn)生： y = gx mod Py為李四之公開金鑰x為李四之秘密金鑰P為很大之質(zhì)數(shù)g為與P互質(zhì)之原根5.張三收到(M,r,s)後驗證 gM = yrrs mod P 上式若相等表示M確定為李四所簽署31 7.4 橢圓曲線密碼系統(tǒng)RSA或ElGamal

22、密碼系統(tǒng)最為人詬病的問題就是在加解密或是簽章的時候需要龐大的運算量，所以需要較長的運算時間。為了改善其效率（較少之運算量），因此提出橢圓曲線的密碼系統(tǒng)(Elliptic Curve Cryptosystem, ECC)，它的安全性必須相當於RSA或ElGamal的密碼系統(tǒng)。32 橢圓曲線上的有限加法群所使用的橢圓曲線方程式為y2=x3+ax+b此曲線剛好對稱於y=0這條直線參數(shù)a及b必需滿足4a3+27b20，才能確保沒有重根，具有唯一解加法單位元素O為一無窮遠的點，並滿足O= -O此加法單位元素亦需滿足：橢圓曲線上某三點共線其合為O33 橢圓曲線上不同座標點相加34 橢圓曲線上相同座標點相加

23、35 橢圓曲線上一座標點與一無窮遠點相加36 橢圓曲線上兩對稱點相加AB=A+(-A)=O B37 在有限體內(nèi)的橢圓曲線運算 在此橢圓曲線上可能出現(xiàn)的點有(0,1)、(0, 4)、(2, 1)、(2, 4)、(3, 1)、(3, 4)、(4, 2)、(4, 3)、(, )任取橢圓曲線上兩點，無論作加法、減法或乘法，其結(jié)果永遠為上述座標點中的一點橢圓曲線中的離散對數(shù)難題：給訂一參數(shù)K及一點A，要求得另一點B，使得B=KA是很容易的。例如：5A=A+A+A+A+A但若給定A及B要求得K則很困難38橢圓曲線的公開金鑰加密機制11111)()()()()()()(MGKBBrBrMGrRGrKBrMRKCMxxxxXxxxx39橢圓曲線的數(shù)位簽章40 7.5 混合式的加密機制混合式加密機制顧名思義就是同時採用對稱式密碼機制及公開金鑰密碼機制的加密系統(tǒng)，截長補短，使得它可以同時擁有這兩種密碼機制的優(yōu)點。417.5.1 數(shù)位信封(Digital Envelope)Send