RSA 公開金鑰密碼機制 非對稱式密碼系統的一種 1978 年美國麻省理工學院三位教授 Rivest Shamir 及 Adleman (RSA) 所發展出來的 利用公開金鑰密碼系統作為資料加密的方式, 可達到資料加密及數位簽署的功能 Encryption : RSA 加密演算法, 明文加密使用區塊為每次加密的範圍, 使用對方公開金鑰 (Public Key) 將明文加密 Decryption : RSA 解密演算法, 必須使用自己的私有金鑰 (Private Key) 才能將密文解出 1
RSA 演算法 1. 選兩個大質數 p 和 q ( 至少 100 位數 ), 令 N = p q 2. 再計算 Ø(N)=(p-1)(q-1), 並選一個與 Ø(N) 互質數 e Ø(N) 為 Euler s Totient 函數, 其意為與 N 互質之個數 3. (e,n) 即為公開金鑰 加密法為 C = M e mod N 4. 選一個數 d, 滿足 e d mod Ø(N) = 1 5. d 即為解密金鑰 ( 亦稱私有金鑰或祕密金鑰 ) 解密法為 M = C d mod N RSA 之安全性取決於質因數分解之困難度 要將很大的 N 因數分解成 P 跟 Q 之相乘, 是很困難的 2
RSA 演算法例子 1. 接收方選 p=3, q=11 ; 此時 N = p q = 33 2. 找出 1 個與 ( p-1 ) x ( q-1 ) = ( 3-1 )( 11-1 ) = 2 x 10 = 20 互質數 e=3 3. ( e, N) = (3,33) 即為接收方的公開金鑰 4. 接收方選一個數 d=7 當作解密金鑰, 滿足 e d 1 mod 20 ( 7 x 3 1 mod 20 ) 令明文 M = 19 加密 : C = M e mod N = 19 3 mod 33 = 28 解密 : M = C d mod N = 28 7 mod 33 = 19 3
相關的數學理論 費瑪 (Fermat) 定理 : 若 p 為質數且 (a,p) 互質, 則 a p-1 mod p = 1 Fermat s Little Theorem If p is a prime, and a is not a multiple of p, then Fermat s little theorem says a p-1 mod p =1 Ex. 2 6 mod 7 =1 4
尤拉定理 Euler 定理 : 若 a,n 互質, 則 a Ø(n) mod n = 1 Euler s Theorem If gcd(a,n)=1, then a φ ( n ) mod n = 1 where φ() called Euler phi function. 尤拉函數 : Ø(P) = P-1 若 P 為質數 Ø(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 p and q are prime, then φ(n)=(p-1)(q-1) 5
模數係下的乘法反元素問題 一般的乘法反元素問題 找到一數 x 使得 (a x)= 1 x 的解為 x =a -1 模數係的乘法反元素問題 找到一數 x 使得 1 = (a x) mod N x 的解為 x =a -1 mod N 6
模數係下的乘法反元素問題 ( 續 ) Modular Inverse Problem 若 a 與 N 互質, 則 x = a -1 mod n 有唯一解 若 a 與 N 不互質, 則 x = a -1 mod n 無解 例如 : 5 模 14 的乘法反元素為 3, 但 2 模 14 的乘法反元素就不存在 這也就是為何在 RSA 密碼系統中, 使用者所選擇的公開金鑰 e 必須與 Ø(N) 互質的原因 一般來說有兩種方法可以用來解乘法反元素的問題 - 利用尤拉定理 - 利用擴展歐幾理德演算法 7
如何找到模數係下的乘法反元素 方法一 : 利用尤拉定理 (Euler s Theorem) x= a -1 mod n a x mod n =1 x=a φ(n)- 1 mod n 理由是依據尤拉定理 :If gcd(a,n)=1, then a φ(n) mod n=1 例如 : 5 模 7 的乘法反元素如何求得? 5 6-1 mod 7 = 5 5 mod 7 =3 where φ(n)=6 Note: 若 n 為質數, 則 φ(n) 可以很輕易求得 ; 但若 n 為一很大的非質數, 則要求的 φ(n) 相當於解質因數分解的困難度 8
如何找到模數係下的乘法反元素 ( 續 ) 方法 2: 擴展歐幾理德演算法 (Extended Euclidean Algorithm) 歐幾理德演算法 (Euclidean Algorithm) 常被用在解最大公因數的問題上 Find gcd(a,n) Let r 0 =n, r 1 =a, we get r 0 =r 1 g 1 +r 2, r 1 =r 2 g 2 +r 3,..., r j-2 =r j-1 g j-1 +r j,..., r m-4 =r m-3 g m-3 +r m-2, r m-3 =r m-2 g m-2 +r m-1, r m-2 =r m-1 g m-1 +r m, r m-1 =r m g m 9
如何找到模數係下的乘法反元素 ( 續 ) 根據擴展歐幾理德演算法, 若 a 與 n 兩數互質, 一定可以找到兩個整數 s 與 t, 使得 gcd(a, n) = sa + tn = 1. 其作法如下 : If gcd(a,n)=1, we get sa + tn =1. We can find s and t by using r m =gcd(a,n)=r m-2 -r m-1 g m-1 because r m-1 = r m-3 r m-2 g m-2 sa+tn = 1 sa + tn mod n=1 sa mod n=1 s = a -1 mod n so gcd(a,n) = r m-2 - (r m-3 r m-2 g m-2 )g m-1 = (1+g m-1 g m-2 )r m-2 g m-1 r m-3 and so on. 10
RSA 密碼系統的正確性 C = E(M) = M e mod n M = D(C) = C d mod n C d =(M e ) d =M ed mod n since ed= 1 mod (p-1)(q-1) so M ed = M a(p-1)(q-1)+1 =MM a(p-1)(q-1) =MM aφ(n) mod n 根據尤拉定理 (Euler s Theorem), 得到 M 1=M 11
因式分解的問題 Factoring Problem Factoring a number means finding its prime number Ex: 10 = 2 5; 60 = 2 2 3 5 但是解一個大數的值因數分解問題是很困難的 請試著分解 : 3337 RSA 的安全性便是植基於解因式分解的難題上 12
RSA 演算法 指數運算 : 計算 x = A B mod N? a 1 := A; b 1 :=B; x:=1; while b 1 0 do begin while b 1 mod 2 = 0 do begin b 1 := b 1 div 2; a 1 := (a 1 a 1 ) mod N; end b 1 := b 1-1; x := (x a 1 ) mod N end 計算 x = A 17 mod N = A 10001 mod N = A (((A 2 ) 2 ) 2 ) 2 計算 x = A 13 mod N = A 1101 mod N = A ((A 2 ) 2 ) ((A 2 ) 2 ) 2 計算 x = A 7 mod N = A 111 mod N = A (A 2 ) (A 2 ) 2 13
Public-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)) = M Public-key Cryptosystems 一定要能忍受 Chosen-Plaintext Attack 14
Public-Key Cryptosystems 之特性 ( 續 ) 滿足 1~3 項稱之為 trap-door one-way function one-way 因易加密而不易解密 trap-door 若知一些特別資訊即可解密 滿足 1~4 項稱之為 trap-door one-way permutation 1~3 項為 public-key cryptosystems 之要求 若同時滿足第 4 項要求, 則該保密法可用來製作數位簽章 15
RSA 數位簽章 張三使用自己的祕密金鑰對文件 M 做數位簽章 S 張三 S = M d 張 mod N 張 一般使用時會先將文件 M 作 HASH 函數處理, 使得 HASH(M) 比 N 小 傳送 M 及 S 李四 M =? S e 張 mod N 張 李四使用張三的公開金鑰確認數位簽章及文件 16
數位簽章法 M H E 512 位元 SKa M E SKa [H(M)] 為 M 之簽章 H D PKa 比較是否相等 D PKa [E SKa [H(M)]] =H(M) 17
RSA 數位簽章 + 加密 張三對文件 M 做數位簽章後用李四的公用金鑰將簽章加密 張三 C = ( M d 張 mod N 張 ) e 李 mod N 李 傳送密文 C 李四 M = ( C d 李 mod N 李 ) e 張 mod N 張 李四使用私有金鑰解開密文 C 再用張三的公開金鑰確認數位簽章 18