二、現代的加解密法：RSA 非對稱式密碼系統的一種。 1978年美國麻省理工學院三位教授Rivest、Shamir、 Adleman (RSA) 所發展出來的。 利用公開金鑰密碼系統作為資料加密的方式，可達 到資料加密及數位簽署的功能。 Encryption : RSA 加密演算法，明文加密使用區塊為每 次加密的範圍，使用對方公開金鑰(Public Key)將明文加密。 Decryption : RSA 解密演算法，必須使用自己的私有金 鑰(Private Key)才能將密文解出。 1-

二、現代的加解密法：RSA 1. 張三選 2 個大質數 p 和 q (至少100位數)，令 N = p • q 2. 再計算Ø(N)=(p-1)(q-1)，並選 1 個與Ø(N)互質數 e Ø(N)為Euler‘s Totient函數，其意為與N互質之個數 3. (e,N) 即為張三的公開金鑰 加密法為 C = Me mod N 4. 張三選 1 個數 d，滿足 e • d mod Ø(N) = 1 5. d 即為張三的解密金鑰(亦稱私有金鑰或祕密金鑰) 解密法為 M = Cd mod N  RSA之安全性取決於質因數分解之困難度  要將很大的N因數分解成P跟Q之相乘，是很困難的 1-

RSA 演算法- 例子 1. 張三選 p=5 ， q=11 ; 此時 N = p • q = 5 x 11 = 55 2. 張三選出 1 個與 ( p-1 ) x ( q-1 ) = ( 5-1 )( 11-1 ) = 4 x 10 = 40 互質數 e=7 3. ( e, N) = (7,55) 即為張三的公開金鑰 4. 張三選 1 個數 d=7 當作解密金鑰， 滿足 e • d  1 mod 40 ( 7 x 23  1 mod 40 ) 令明文 M = 53 加密 : C = Me mod N = 537 mod 55 = 37 解密 : M = Cd mod N = 3723 mod 55 = 53 179 (176, 183) 0: black 255: white 1-

RSA 演算法數學理論- Fermat’s Little Theorem If p is a prime, and a is not a multiple of p, then Fermat’s little theorem says ap-1 mod p =1 Ex. 26 mod 7 =1 費瑪(Fermat)定理: 若p為質數且(a,p)互質，則 ap-1 mod p = 1 1-

RSA 演算法數學理論- Euler’s Theorem If gcd(a,n)=1, then Euler通用定理: 若a，n互質，則 aØ(n) mod n = 1 where () called Euler phi function. 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 p and q are prime, then (n)=(p-1)(q-1) 定理: Ø(P) = P-1 若P為質數 Ø(N) = Ø(PQ) =Ø(P)Ø(Q) = (P-1)(Q-1) 1-

RSA 演算法數學理論 C = E(M) = Me mod n M = D(C) = Cd mod n Cd=(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 n According to Euler’s Theorem, we get M*1=M 1-

RSA 演算法整理 Key Generation Select p, q p and q both prime Calculate n=pq calculate Φ(n)=(p-1)(q-1) Select integer e gcd(Φ(n), e)=1;1<e< Φ(n) Calculate d d=e-1 mod Φ(n) Public key {e, n} Private key {d} [模乘法反元素] 1-

RSA 演算法整理-例子 Key Generation Select p =5, q =11 Calculate n=pq =55 Select integer e =7 Calculate d =23 7*23=1 mod 40 Public key {e =7, n =55 } Private key {d =23 } 1-

RSA 演算法整理 Encryption Decryption Plaintext: M< n M=53 Ciphertext: C=Me mod n C=537 mod 55 = 37 Decryption Ciphertext: C C=37 Plaintext: M=Cd mod n M=3723 mod 55 =53 1-

模乘法反元素 The problem is finding an x such that 1 = (a * x) mod n This is also written as a-1 mod n =x Note: 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. Ex. The inverse of 5, modulo 14, is 3. 2 has no inverse modulo 14. 1-

如何計算模乘法反元素 x=a(n)-1 mod n Method 1: Using Euler’s 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 缺點: (n) is not always known 1-

如何計算模乘法反元素 Let r0=n, r1=a, we get Method 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 1-

如何計算模乘法反元素 Because rm-1= rm-3 – rm-2gm-2 We can find gcd(a, n) = sa + 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-1 Because rm-1= rm-3 – rm-2gm-2 so 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 1-

數位簽章 (digital signature)原理 A 將文件與簽章同時傳給 B B 利用 A 的公開金匙對 A 的數位簽章進行運算， 將結果與傳送的文件進行比對，如果兩者相同， 就表示該文件確實是由 A 所簽發 1-

RSA數位簽章 S =Md mod n S= 3723 mod 55= 53 M =Se mod n 37= 537 mod 55 簽章 驗證 M =Se mod n 37= 537 mod 55 1-

RSA 同時達到秘密通訊與簽章 1.分開送 UA UB 公開金匙: (eA, NA) (eB, NB) 私密金匙: dA dB 若使用者UA欲送文件M給使用者UB 1-

RSA 同時達到秘密通訊與簽章 加密 C = MeB mod NB 簽章 S = MdA mod NA UB UA 解密 M = CdB mod NB 驗証 M = SeA mod NA 1-

RSA 同時達到秘密通訊與簽章 2.合併送 If NA < NB C UB UA 簽章 S = MdA mod NA 解密 S = CdB mod NB 加密 C = SeB mod NB 驗証 M = SeA mod NA 1-