公開金鑰密碼系統 (Public-Key Cryptosystems)

Presentation on theme: "公開金鑰密碼系統 (Public-Key Cryptosystems)"— Presentation transcript:

1 公開金鑰密碼系統 (Public-Key Cryptosystems)

2 本章內容 7.1 公開金鑰基本概念 7.2 RSA公開金鑰密碼機制 7.3 ElGamal的公開金鑰密碼系統 7.4 橢圓曲線密碼系統
7.1 公開金鑰基本概念 7.2 RSA公開金鑰密碼機制 7.3 ElGamal的公開金鑰密碼系統 7.4 橢圓曲線密碼系統 7.5 混合式的加密機制 7.6 機密分享 7.7 量子密碼學 7.8 密碼系統的評估

3 電腦作業系統安全架構(以技術觀點) 3

4 7.1 公開金鑰基本概念 對稱式密碼系統有金鑰的管理問題，例如要與 N個人做秘密通訊，那麼就必須握有N把秘密金鑰
為了改善對稱式密碼系統問題，於是便有公開金鑰密碼系統(Public-Key Cryptosystems)的產生

5 秘密金鑰密碼系統 vs.公開金鑰密碼系統 秘密金鑰密碼系統

6 秘密金鑰密碼系統 祕密金鑰密碼系統(Secret-Key Cryptosystems)
又稱單金鑰密碼系統(One-Key Cryptosystems) 也稱對稱密碼系統(Symmetric Cryptosystems) 優點：加解密速度快 缺點：有金鑰管理的問題 每位使用者需儲存n-1把Keys U2 U3 U1 U4 U5

7 公開金鑰密碼系統 公開金鑰密碼系統(Public-Key Cryptosystems)
又稱雙金鑰密碼系統(Two-Key Cryptosystems) 也稱非對稱密碼系統(Asymmetric Cryptosystems) 優點：沒有金鑰管理的問題 高安全性 有數位簽章功能 缺點：加解密速度慢 著名之公開密碼系統：  RSA密碼系統  ElGamal密碼系統

8 公開金鑰加密系統 志明(B){eB,dB} 春嬌(A) {eA,dA} 志明’s 私有金鑰 dB Send 加密 解密
加解密與接收方金鑰有關 => 達到機密性 Encryption : 加密演算法，使用接收方公開金鑰(Public Key)將明文加密。 Decryption : 解密演算法，必須使用接收方自己的私有金鑰(Private Key)才能將密文解出。 志明(B){eB,dB} 春嬌(A) {eA,dA} 志明’s 私有金鑰 dB 志明’s 公開金鑰 eB Send 加密 解密 密文 密文 明文 明文 C= EeB(M) M= DdB(C) =DdB(EeB(M))

9 數位簽章 (Digital Signature)
一般數位簽章具有下列功能： 訊息來源鑑別性(Authentication)：可確認文件來源的合法性，而非經他人偽造。 完整性(Integrity)：可確保文件內容不會被新增或刪除。 不可否認性(Non-repudiation)：簽章者事後無法否認曾簽署過此文件。

10 數位簽章的基本概念 SA=EdA(M) DeA(SA)=DeA (EdA(M)) M=DeA(SA) ?
簽章與發送方金鑰有關 => 達到訊息來源鑑別性、完整性、發送方不可否認性 簽章: 簽章演算法，使用發送方自己的私有金鑰(Private Key)將明文簽章。 簽章驗證: 驗證演算法，必須使用發送方公開金鑰(Public Key)才能解簽章。 SA=EdA(M) E D DeA(SA)=DeA (EdA(M)) M=DeA(SA) ?

11 ? 公開金鑰密碼系統 志明(B){eB,dB} 春嬌(A) {eA,dA} Send 加解密與接收方金鑰有關 => 達到機密性
簽章與發送方金鑰有關 => 達到訊息來源鑑別性、完整性、不可否認性 如何設計同時達到機密性、訊息來源鑑別性、完整性、不可否認性? 春嬌(A) {eA,dA} 志明(B){eB,dB} ? Send 明文 明文

12 7.2 RSA 加密法 非對稱式密碼系統的一種。 1978年美國麻省理工學院三位教授Rivest、Shamir及Adleman (RSA) 所發展出來的。 利用公開金鑰密碼系統作為資料加密的方式，可達到資料加密及數位簽章的功能。 使用指數運算式，將明文加密成二進位值小於整數n的區塊， n的大小通常是1024個位元。

13 數論 質數 (Prime)：只能被 1 或自己整除的數。 1 ~ 100 之間的質數：
2, 3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 任意數 a > 1，可被分解成多個質數的乘積： a = p1αp1× p2αp2 × p3αp3× p4αp4…× piαpi = Πpiαpi 譬如： 3600 = 24 × 32 × 52，則 α2 =4、α3 =2、α5 =2。

14 數論 互質： gcd(a, b) 表示 a 和 b 的最大公因數。 如果 gcd(a, b) =1， 表示 a 與 b 互質。
300 = 22 × 31 × 52； 18 = 21 × 32 × 50，則 gcd(300, 18) = 21 × 31 × 50 = 6

15 模數運算 若a 為整數、n 為正整數 將a mod n 的值定義為 a除n的餘數 整數n稱為模數(Modulo)
若（a mod n ) = ( b mod n ) 整數a、b是n的同餘 寫成a ≡ b(mod n) b 是 a mod n的餘數即 a mod n = b 例如: 40 ≡ 1(mod 13)

16 模數運算 模數加法 (Modular Addition) [(a mod n) + (b mod n) ] mod n
= (a + b) mod n a=16、 b=24 、 n=13 左邊 = [(16 mod 13) + (24 mod 13) ] mod 13 = (3+11) mod 13 = 1 右邊 = ( ) mod 13 = 40 mod 13 = 1

17 模數為8的模數加法運算 + 1 2 3 4 5 6 7 (7+6) mod 8 =13 mod 8 = 5 可寫成
1 2 3 4 5 6 7 (7+6) mod 8 =13 mod 8 = 5 可寫成 13 ≡ 5(mod 8)

18 模數運算 模數乘法 (Modular Multiplication)
[(a mod n) × (b mod n) ] mod n = (a × b) mod n a=16、 b=24 、 n=13 左邊 = [(16 mod 13) × (24 mod 13) ] mod 13 = (3 × 11) mod 13 = 7 右邊 = (16 × 24) mod 13 = 384 mod 13 = 7

19 模數運算 模數指數 (Modular Exponentiation) [(a mod n)b mod n = ab mod n
a=16、 b=4 、 n=13 左邊 = (16 mod 13) 4 mod 13 = (3) 4 mod 13 = 81 mod 13 =3 右邊 = 164 mod 13 = mod 13 = 3

20 RSA 演算法 選 2 個大質數 p 和 q (至少100位數) 計算N = p × q ，再計算Ø(N)=(p-1) × (q-1)，
Ø(N)為Euler‘s Totient函數，其意為與N互質之個數 3. 選 1 個與Ø(N)互質數 e, 即GCD (e, Ø(N)) = 1 (e, N) 即為張三的公開金鑰(Public Key) 加密法為 C = Ee(M)=Me mod N 4. 選 1 個數 d，滿足 e × d mod Ø(N) = 1, 即e, d互為mod Ø(N)的乘法反元素 (d , N)即為張三的私有金鑰(Private Key) 解密法為 M =Dd(C)= Cd mod N RSA之安全性取決於質因數分解之困難度 要將很大的N因數分解成P跟Q之相乘，是很困難的

21 費瑪定理(Fermat Theorem) 費瑪(Fermat)定理: 若n為質數且(m,n)互質，則 mn-1 mod n = 1 例如

22 尤拉定理(Euler’s Theorem)
尤拉定理(課本 page 177 ，由費瑪定理產生) 若m，n互質，則 mØ(n) mod n = 1 尤拉函數: Ø(P) = P-1 ，若P為質數 Ø(N) = Ø(P × Q) = Ø(P) × Ø(Q)= (P-1) ×(Q-1) 例如 m=3; n=5; Ø(5)=4; 因此 3Ø(5) mod 5 = 34 mod 5 = 1 m=2; n=15; Ø(15)= Ø(3) × Ø(5) = 2 × 4 =8 因此 2Ø(15) mod 15 = 28 mod 15 = 1

23 RSA密碼系統的解密證明 加密法： C = Ee (M) = Me mod N 解密法： M = Dd (C) = Cd mod N 證明:
Dd (C)=Dd (Me mod N ) =(Me)d mod N =M e × d mod N , since e × d = 1 mod ø(N) = Ma × ø(N)+1 mod N , a 為整數 =Ma × ø(N) × M mod N =(M(N)) a × M mod N, 根據尤拉定理， Ma(N) mod N =1 =1 × M =M

24 RSA 演算法-課本範例 選定兩個質數 p=3 ， q=11 此時 N = p x q = 3 x 11 = 33
Ø(N)= ( p-1 ) x ( q-1 ) = ( 3-1 ) x( 11-1 )= 2 x 10 =20 3. 選定1 個與Ø(N)互質數 e=3 4. 選定 d，但必須滿足d x e mod Ø(N) =1 (=> 7 x 3  1 (mod 20 )) 選 1 個數 d=7 當作私有金鑰 經過上述推演得到： 公開金鑰：KPU = {e, N} = {3, 33} 私有金鑰：KPR = {d, N} = {7, 33} 令明文 M = 19 加密 : C = Me mod N = 193 mod 33 = 28 解密 : M = Cd mod N = 287 mod 33 = 19 使用擴充歐基里得演算法 179 (176, 183) 0: black 255: white 使用指數運算或平方再乘法

25 RSA 演算法-範例 假設參數： 1. 選定兩個質數，p = 7、q = 17。
2. 計算 N = p × q = 7 × 17 = 119。 計算Ø (N) = (p-1) × (q-1) = 6 × 16 = 96。 3.  選定 e，但必須滿足 gcd(e, Ø(N)) =1，則選擇 e =5，因與 96 互 質。 4. 選定 d，但必須滿足 d × e ≡1 (mod 96)，且 d < 96。 本範例選擇 d = 77，因為 77×5 = 385 ≡1 (mod 96 )。 經過上述推演得到： 公開金鑰：KPU = {e, N} = {5, 119} 私有金鑰：KPR = {d, N} = {77, 119}

26 RSA 演算法-範例 驗證推演結果 假設明文 M = 19
加密編碼：C = Me mod N = 195 mod 119 = 66 ，則密文為 66。 演算過程如下： 寫法1(課本寫法) 寫法2 192 mod 119 = 361 mod 119 = 4 194 mod 119 = (4 × 4) mod 119 = 16 195 mod 119 = (194 × 191 )mod 119 =(16 × 19) mod 119 = 66 192 = 361 ≡ 4 (mod 119 ) 194 ≡ 4 × 4 ≡16 (mod 119 ) 195 = (194 × 191 ) ≡(16 × 19) ≡ 66 (mod 119 )

27 RSA 演算法-範例 驗證推演結果 密文  C = 66  解密編碼：M = Cd mod N = 6677 mod 119 = 19 ，則明文為 19。 演算過程如下： 662 mod 119 = 72 664 = (72 × 72) mod 119 = mod 119 = 67 668 mod 119 = (67 × 67) mod 119 = 4489 mod 119 = 86 6616 mod 119 = (86 × 86) mod 119 = 7396 mod 119 = 18 6632 mod 119 = (18 × 18) mod 119 = 324 mod 119 = 86 6664 mod 119 = (86 × 86) mod 119 = 7396 mod 119 = 18 6677 mod 119 = (6664 × 668 × 664 × 66) mod 119 = mod 119 = 19

28 指數運算 計算 x = AB mod N 計算 x = A17 mod N = A• (((A2)2)2)2
a1:= A; b1:=B; x:=1; while b1  0 do begin while b1 mod 2 = 0 do b1 := b1 div 2; a1 := (a1 × a1) mod N; end b1 := b1 - 1; x := (x × a1) mod N 計算 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

29 平方再乘(Square-and-multiply)演算法 計算 x = AB mod N
假設指數B可用k位元的二進制數字來代表， 即 B = (bk-1 bk-2 … b2 b1 b0) Step 1. x←1 Step 2. for i ← k-1 downto 0 do x ← x × x mod N If bi = 1 then x ← A × x mod N 29

30 範例計算:510 mod 11 510 mod 11 = mod 11 = 1 指數 B =10 = (b3 b2 b1 b0) = (1010) 平方再乘： i 3 2 1 bi x 5 x (12 mod 11) mod 11 =5 52 mod 11 = 3 5 x (32 mod 11) mod 11 = 5 x 9 mod 11 = 1 12 mod 11 = 1 30

31 RSA數位簽章機制 春嬌(A) SA = MdAmod N 傳送 M || SA 志明(B) M =? SAeAmod N
春嬌(A)使用自己的私有金鑰(dA)對文件 M 做數位簽章SA 春嬌(A) 一般使用時會先將文件M 作HASH函數處理，使得 HASH(M)比N小 SA = MdAmod N 傳送 M || SA 志明(B) M =? SAeAmod N 志明使用春嬌的公開金鑰(eA)確認數位簽章SA及文件(M)

32 RSA數位簽章機制 簽章與發送方金鑰有關 => 達到訊息來源鑑別性、完整性、不可否認性
簽章: 簽章演算法，使用發送方自己的私有金鑰(Private Key)將明文簽章。 簽章驗證: 驗證演算法，必須使用發送方公開金鑰(Public Key)才能解簽章。 SA=EdA(M) = MdAmod N E D DeA(SA)=DeA (EdA(M)) = SAeAmod N M=? SAeAmod N

33 RSA 演算法-課本範例(簽章) 選定兩個質數 p=3 ， q=11 此時 N = p x q = 3 x 11 = 33
Ø(N)= ( p-1 ) x ( q-1 ) = ( 3-1 ) x( 11-1 )= 2 x 10 =20 3. 選定1 個與Ø(N)互質數 e=3 4. 選定 d，但必須滿足d x e mod Ø(N) =1 (=> 7 x 3  1 (mod 20 )) 選 1 個數 d=7 當作私有金鑰 經過上述推演得到： 公開金鑰：KPU = {e, N} = {3, 33} 私有金鑰：KPR = {d, N} = {7, 33} 令明文 M = 19 簽 章: S = Md mod N = 197 mod 33 = 13 簽章驗證: M = Se mod N = 133 mod 33 = 19 179 (176, 183) 0: black 255: white

34 RSA 密碼機制的安全性 一般的乘法反元素問題 找到一數 x 使得 (a × x)= 1 x的解為 x =a-1 模數係的乘法反元素問題
找到一數 x 使得 1 = (a × x) mod N x的解為 x =a-1 mod N

35 模數係下的乘法反元素問題 若a 與N互質，則x = a-1 mod N 有唯一解 若a 與N不互質，則x = a-1 mod N 無解
例如： 5模14的乘法反元素為3，但2模14的乘法反元素就不存在。 這也就是為何在RSA密碼系統中，使用者所選擇的公開金鑰e必須與Ø(N)互質的原因。 e × d mod Ø(N) = 1 => d =e-1 mod Ø(N) 一般來說有兩種方法可以用來解乘法反元素的問題 - 利用尤拉定理 - 利用擴展歐幾理德演算法

36 計算最大公因數(GCD): 輾轉相除法 希臘數學家歐基里得演算法(輾轉相除法) GCD (A, B) = GCD (B, A mod B)
Algorithm: Step 1. If B = 0, then return A Step 2. R ← A mod B A ← B B ← R Step 3. Goto Step 1 Example : GCD (552,234) = GCD (234,84) = GCD (84,66) = GCD (66,18) = GCD (18,12) = GCD (12,6) = GCD (6,0) = 6 36

37 擴充歐基里得演算法 已知: a, P 求: x 滿足 x x a mod P = 1
x又稱為a模P的乘法反元素(multiplicative inverse)，x = a-1 mod P Step A ← P B ← a x' ← 0 x ← 1 Step Q =floor(A  B) 註: (A  B)的商 R = A mod B 註: (A  B)的餘數 Step If R ≠ 0, then goto Step 4 return x Step A ← Bold B ← Rold x' ← xold x ← (x‘old － xold x Qold ) mod N Goto Step 2 37

38 擴充歐基里得演算法-範例1 A B x' x Q R 96 5 1 19 RSA 演算法: 選定兩個質數，p = 7、q = 17
選定公鑰 e=5 ,計算私鑰d (滿足e × d mod Ø(N)=1), => 滿足 d × 5 mod 96 = 1 A B x' x Q R 96 5 1 19 (0-1×19) mod 96 = = 77 = d 38

39 擴充歐基里得演算法-範例2 Find the inverse of 15 mod 26 => d ×15 mod 26 =1 A B x' x Q R 26 15 1 11 (0-1×1) mod 26 = -1+26=25 4 25 (1-25×1) mod 26 = =2 2 3 (25-2×2) mod 26 = 21 21 (2-21×1) mod 26 = 7 = d

40 因式分解的問題 Factoring Problem
User知 Ø(N) => e × d mod Ø(N) = 1 =>可得私有金鑰KPR = {d, N} 其他人可知公開金鑰：KPU = {e, N} =>無法得知Ø(N) => 無法得知私有金鑰KPR = {d, N} 但其他人知N= p × q ，可計算Ø(N)=(p-1) ×(q-1) ，可得私有金鑰KPR = {d, N} Factoring a number means finding its prime number Ex: N=10 = 2 × 5; N=60 = 2 × 2 × 3 × 5 但是解一個大數的值因數分解問題是很困難的。 請試著分解: N=3337 RSA 的安全性便是植基於解因式分解的難題上

41 因數分解的問題 三種以數學運算攻擊RSA的方法： 將n分解成兩個質因數，最後算出d ≡ e-1 (mod ø(n))
不需要先算出p和q而直接算出ø(n) 不需要先算出 ø(n)而直接算出d 大部分RSA密碼破解的焦點，是將n分解成兩個質因數 RSA-768（768 bits, 232 digits）2009年12月12日數也被成功分解

42 密碼系統線上工具

43 OpenSSL進行RSA產生私鑰 使用 OpenSSL RSA 演算法產生私鑰 - genrsa > openssl genrsa -out rsa_private.pem -passout pass: des 1024 43

44 OpenSSL進行RSA產生相對應的公鑰
RSA 管理命令 – rsa 使用 RSA 的私鑰產生相對應的公鑰 >openssl rsa -in rsa_private.pem -passin pass: out rsa_public.pem 將私鑰轉換成一般文件格式（rsaprivate.txt），觀察其內容如何。 > openssl rsa -in rsa_private.pem -passin pass:12345 –text > rsa_private.txt 44

45 OpenSSL進行RSA加解密 使用 RSA 的公鑰加解密檔案 使用 RSA 的私鑰解密檔案
使用 "rsautl" 為其參數，隨後附上 "-encrypt" 參數指定加密的運行，"-inkey" 參數指定密鑰檔案，"-pubin" 參數將公鑰產生於加密檔案中，"-in" 參數指定欲加密的檔案，以及 "-out" 參數指定加密後的檔案名稱︰ >openssl rsautl -encrypt -pubin -inkey publickey.pem -in rsa_plain.txt -out rsa_cipher.txt 使用 RSA 的私鑰解密檔案 請使用 "rsautl" 為其參數，隨後附上 "-decrypt" 參數指定解密的運行，"-inkey" 參數指定密鑰檔案，"-in" 參數指定欲解密的檔案，以及 "-out" 參數指定解密後的檔案名稱: >openssl rsautl -decrypt -inkey privatekey.pem -passin pass: in rsa_cipher.txt -out rsa_plain1.txt 45

46 OpenSSL進行RSA數位簽章 使用 RSA 的私鑰簽章 使用 RSA 的公鑰解簽章
請使用 "rsautl" 為其參數，隨後附上 "-decrypt" 參數指定解密的運行，"-inkey" 參數指定密鑰檔案，"-in" 參數指定欲解密的檔案，以及 "-out" 參數指定解密後的檔案名稱: >openssl rsautl -encrypt -inkey privatekey.pem -passin pass: in rsa_plain.txt -out rsa_signature.txt 使用 RSA 的公鑰解簽章 使用 "rsautl" 為其參數，隨後附上 "-encrypt" 參數指定加密的運行，"-inkey" 參數指定密鑰檔案，"-in" 參數指定欲加密的檔案，以及 "-out" 參數指定加密後的檔案名稱︰ >openssl rsautl -decrypt -inkey publickey.pem -in rsa_signature.txt -out rsa_plain2.txt 46

47 OpenSSL測試RSA加解密效率 >openssl speed rsa1024 rsa2048 rsa4096 47

48 7.5 混合式的加密機制 混合式加密機制顧名思義就是同時採用對稱式密碼機制及公開金鑰密碼機制的加密系統，截長補短，使得它可以同時擁有這兩種密碼機制的優點。

49 數位信封(Digital Envelope)
(1)SK Sender : 春嬌 Receiver : 志明 密文 明文 (2)C = ESK(M) (4)密文C及信封V (6)M = DSK(C) 信封 交談金鑰 (3)V = EPU(SK) (5)SK = DPR(V) SK: Session Key(交談金鑰) ESK :秘密金鑰密碼系統(Key: SK) EPU :志明之公開金鑰 (Key: PU) EPR:志明之私有金鑰 (Key: PR) 確定達到機密性 達到訊息來源鑑別(Authentication)? 確定是春嬌寄的密文與V ?

50 數位信封(Digital Envelope)
(2)C=ESK(M) (3)V=EPU(SK) (5)SK=DPR(V) (6)M=DSK(C) (1) Another application in which public-key encryption is used to protect a symmetric key is the digital envelope, which can be used to protect a message without needing to first arrange for sender and receiver to have the same secret key. The technique is referred to as a digital envelope, which is the equivalent of a sealed envelope containing an unsigned letter. The general approach is shown here from Figure 2.9 in the text. Suppose Bob wishes to send a confidential message to Alice, but they do not share a symmetric secret key. Bob does the following: 1. Prepare a message 2. Encrypt that message using conventional encryption with a one-time conventional session key. 3. Encrypt the session key using public-key encryption with Alice's public key. 4. Attach the encrypted session key to the message and send it to Alice. Only Alice is capable of decrypting the session key and therefore of recovering the original message. If Bob obtained Alice's public key by means of Alice's public-key certificate, then Bob is assured that it is a valid key. (4)

51 數位信封(Digital Envelope)
Another application in which public-key encryption is used to protect a symmetric key is the digital envelope, which can be used to protect a message without needing to first arrange for sender and receiver to have the same secret key. The technique is referred to as a digital envelope, which is the equivalent of a sealed envelope containing an unsigned letter.

52 Diffie-Hellman的金鑰協議與交換機制
沒有真正地利用公開金鑰去對訊息做加解密，而是利用公開金鑰的概念來幫助通訊雙方可以安全地協議出一把共同的交談金鑰(Session Key,會議金鑰)。 真正的加解密工作是利用所協議出來的這把交談金鑰，透過DES或AES等對稱式的密碼系統來完成。

53 什麼是原根？ 原根 (primitive root, 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 p). g also called primitive root of mod p 21 mod 11 = 2 22 mod 11 = 4 23 mod 11 = 8 24 mod 11 = 5 25 mod 11 = 10 26 mod 11 = 9 27 mod 11 =7 28 mod 11 = 3 29 mod 11 = 6 210 mod 11 =1 3不是模11下的一個原根，因為3a mod 11 =2中，a為無解 2 is a generator modulo 11

54 Diffie-Hellman 的金鑰協議方法
雙方共用p 與 g 為公開值且為質數，g為與p互質之原根(primitive) 春嬌(a) &志明(b)雙方各自之私鑰與公鑰 (Xa, Ya) (Xb, Yb) 計算出『SK(秘密鑰匙,交談金鑰)』

55 Diffie-Hellman 的金鑰驗證 shared secret key for users春嬌(a) &志明(b) is SK:
SK=SKa = (Yb)xa mod p = (gxb mod p)xa mod p = (g xb)xa mod p = g xb.xa mod p = (g xa)xb mod p = (g xa mod p)xb mod p = (Ya)xb mod p = SKb 春嬌(a)所接收到志明(b)的公鑰

56 Diffie-Hellman 的金鑰交換方法

57 Diffie-Hellman 範例 have prime number p = 353 primitive root g = 3
A and B each compute their public keys A computes Ya = 397 mod 353 = 40 B computes Yb = 3233 mod 353 = 248 then exchange and compute secret key: for A: SK = (Yb)Xa mod 353 = mod 353 = 160 for B: SK = (Ya)Xb mod 353 = mod 353 = 160 attacker must solve: 3Xa mod 353 = 40 which is hard desired answer is 97, then compute key as B does Here is an example. Key exchange is based on the use of the prime number q = 353 and a primitive root of 353, in this case  = 3. A and B select secret keys XA = 97 and XB = 233, respectively. Each computes its public key: A computes YA = 397 mod 353 = 40. B computes YB = 3233 mod 353 = 248. After they exchange public keys, each can compute the common secret key: A computes K = (YB)XA mod 353 = mod 353 = 160. B computes K = (YA)XB mod 353 = mod 353 = 160. We assume an attacker would have available the following information: q = 353;  = 3; YA = 40; YB = 248 In this simple example, it would be possible by brute force to determine the secret key 160. In particular, an attacker E can determine the common key by discovering a solution to the equation 3a mod 353 = 40 or the equation 3b mod 353 = 248. The brute-force approach is to calculate powers of 3 modulo 353, stopping when the result equals either 40 or 248. The desired answer is reached with the exponent value of 97, which provides 397 mod 353 = 40. With larger numbers, the problem becomes impractical.

58 中間人攻擊(Man-in-the-middle Attack)
Trudy 為中間人 (5)C1=Ek2(M) (6) Dk2Ek2(M)=M (7) C2=Ek1(M) or C2=Ek1(M’) (8) Dk1Ek1(M)=M or Dk1Ek1(M’)=M’

59 中間人攻擊(Man-in-the-middle Attack)
All future communication between Bob and Alice is compromised in the following way: 1. Alice sends an encrypted message M: Ek2(M). 2. Trudy intercepts the encrypted message and decrypts it, to recover M. 3. Trudy sends Bob Ek1 (M) or Ek1(M'), where M' is any message. The key exchange protocol is vulnerable to such an attack because it does not authenticate the participants. This vulnerability can be overcome with the use of digital signatures and public-key certificates The protocol depicted in Figure 20.8 is insecure against a man-in-the-middle attack. Suppose Alice and Bob wish to exchange keys, and Darth is attacks as follows: 1. Darth generates two private keys XD1 and XD2, and public keys YD1 & YD2. 2. Alice transmits YA to Bob. 3. Darth intercepts YA and transmits YD1 to Bob. Darth also calculates K2 4. Bob receives YD1 and calculates K1. 5. Bob transmits XA to Alice. 6. Darth intercepts XA and transmits YD2 to Alice. Darth calculates . 7. Alice receives YD2 and calculates . At this point, Bob and Alice think that they share a secret key, but instead Bob and Darth share secret key K1 and Alice and Darth share secret key K2. All future communication between Bob and Alice is compromised in the following way: 1. Alice sends an encrypted message M: E(K2, M). 2. Darth intercepts the encrypted message and decrypts it, to recover M. 3. Darth sends Bob E(K1, M) or E(K1, M'), where M' is any message. In the first case, Darth simply wants to eavesdrop on the communication without altering it. In the second case, Darth wants to modify the message going to Bob. The key exchange protocol is vulnerable to such an attack because it does not authenticate the participants. This vulnerability can be overcome with the use of digital signatures and public-key certificates

60 7.6 機密分享 子機密金鑰Ki產生方法如下： 分派者決定主機密金鑰K 任選K1、K2、…、Kn-1等n-1把子機密金鑰
由下列方程式求出第n把子機密金鑰Kn Kn=K1⊕K2⊕…⊕Kn-1⊕K 當n個成員均拿出其子機密金鑰Ki，即可推導出主機密金鑰K： K=K1⊕K2⊕…⊕Kn

61 (t,n)門檻機密分享技術 Shamir在1979年提出(t,n)門檻機密分享技術(Threshold Secret Sharing)
門檻機密分享技術之兩重要參數： t：門檻值 n：機密分享數目 機密分派者將機密資訊K打造成n份不同的子機密(Shadow)，每位成員都可得到一子機密訊息Ki

62 (t,n)門檻機密分享技術 (t,n)門檻機制的兩個主要法則： 當子機密訊息的數目等於或大於門檻值t時，便可以導出主機密資訊。
(5, 7) 表示 >= 5 人，可以導出主機密資訊

63 (t,n)門檻機密分享技術 分派者任選t-1次多項式 F(X)=K+a1X+a2X2+…+at-1Xt-1 mod P K：主機密資訊
P：為大質數並滿足P≧K 係數 a1,a2,…,at-1：值介於0 ~ P-1間 分派者給每位成員唯一的公開識別碼IDi，及依IDi產生不同的子機密資訊 Ki = F(IDi) ， i=1,2,…,n (IDi,Ki)：可視為多項式F(X)上的一個座標點

64 (t,n)門檻機密分享技術 假設有大於等於t個成員拿出所持有的子機密資訊(IDi,Ki)，可得到下列t條方程式：
Ki=K+a1IDi+a2IDi2+…+at-1IDit-1 mod P, i=1,2,…,t 上式t個未知數(K,a1,a2,…,at-1)可用下列方法解出： 解聯立方程式 利用下列Lagrange(拉格朗日)插值多項式解出機密值K：

65 (t,n)門檻機密分享技術 (t,n)=(3,4)門檻機密分享技術如下 分派者任選2次多項式：F(X)=6+3X+4X2 mod 11
分派者給每位成員識別碼IDi，並計算出各成員的機密資訊Ki => (1, 2), (2, 6), (3, 7), (4, 5) 假設三成員(ID1,ID2,ID3)拿出所持有的子機密資訊(IDi,Ki)，可得到下列三條方程式： 2=K+a1(1)+a2(12) mod 11 6=K+a1(2)+a2(22) mod 11 7=K+a1(3)+a2(32) mod 11

66 (t,n)門檻機密分享技術 可用Lagrange插值多項式解出機密值K： 代入公式得：

67 (t,n)門檻機密分享技術 假設三成員(ID1,ID2,ID4)拿出所持有的子機密資訊(IDi, Ki)，可得到下列三條方程式：
2=K+a1(1)+a2(12) mod 11 6=K+a1(2)+a2(22) mod 11 5=K+a1(4)+a2(42) mod 11 可用Lagrange插值多項式解出機密值K： L1= -2/(1-2)＊(-4)/(1-4) = 8/3 L2= -1/(2-1)＊(-4)/(2-4 )= -2 L4= -1/(4-1)＊(-2)/(4-2 )= 1/3 代入公式得： K=f(0)= 8/3*2+(-2)*6+1/3*5 mod 11 = 16/ /3 mod 11 = -5 mod 11 = 6

68 7.8 密碼系統的評估 C=EK(M) 要判斷一個密碼系統的好壞，可以由下列五項因素來作評估： 保密程度:
密文攻擊、已知明文攻擊、選擇明文攻擊、選擇密文攻擊 金鑰的長度 加密/解密演算法的運算複雜度 錯誤傳播 明文擴充

69 密碼破解(Cryptanalysis) C=EK(M), C隨手可得 , E 大部分為公開 攻擊法 破解者 破解 安全程度 種類 擁有 內容
攻擊法 破解者 破解 種類 擁有 內容 密文攻擊法 密文 明文 (Ciphertext-Only Attack) 已知明文攻擊法 明文-密文 解密 (Known-Plaintext Attack) 配對 金鑰 選擇明文攻擊法 含加密金鑰 秘密 (Chosen-Plaintext Attack) 之密碼系統 金鑰 選擇密文攻擊法 含解密金鑰 秘密 (Chosen-Ciphertext Attack) 之密碼系統 金鑰 安全程度 低 至少 高

70 密碼攻擊者分析訊息的方式 只有密文 (ciphertext-only) 已知明文 (known-plaintext)
通常密碼攻擊者透過監聽等手段只能取得密文。大量的密文也許會透露一些統計學上的蛛絲馬跡，但只靠密文要破解加密算法並不容易。 已知明文 (known-plaintext) 攻擊者如果找到一些明文與密文的對照，破解加密法就容易多了。這個方法幫助破解二次大戰的德國加密機器「謎」。例如大部分電子郵件內容的前四個字母都是 ”dear”。 選擇明文 (chosen-plaintext) 是指攻擊者發出明文，隨即取得密文。例如發一封電子郵件給對方，內容誘使收信人將之加密後轉發出去，如此就可以攔截到整篇的密文。 選擇密文 (chosen ciphertext) 與選擇明文相反的方法。有些人收到加密電子郵件，回覆時將原信做附件，卻未加密。所以有機會從密文取得明文。

71 密碼破解 - 凱撒加密法為例 加密法則： C = EK(M) = (Mi + k) mod 26 密文攻擊法: 破密者僅有一份密文C。
破密者最好的策略就是做一個地毯式的搜索, 因為就只有 26 種可能的鑰匙。 若信息有好幾個字母長, 則不太可能會有超過一個以上 (26 個裡面) 為有意義。 如果你不相信, 可試試看找一個 4 或 5 個字母的英文字, 然後觀察位移轉換後的 26 種 不同的結果。 另一可行的方法是 (若信息夠長的話), 對出現過的字母作頻率分析, 在英文中, 字母 e 最常 出現在單字裡面。 的例子中, 字母 L 在密文中出現最多次 (4 次); 因為 e=4 與 L=11, 所以一個合理的的猜測為 k = 11 − 4 = 7, (可能與實際的 k = 3 不符合, 原因出在信息不夠 長, 頻率分析很難使的上力)。 對位移密碼而言, 此種頻率分析反而會比地毯式搜索更花時間, 加上有時信息長度不夠也會徒勞無功。

72 密碼破解 - 凱撒加密法為例(續) 已知明文攻擊法: 若你只知道明文中的一個字母及其在密文中對應的字母, 則鑰匙馬上可以 得知。 如你已知 T(=19) 加密為 D(=3), 那麼你的鑰匙就是 k ≡ 3 − 19 ≡ −16 ≡ 10 (mod 26)。 選擇明文攻擊法: 選取字母 a 為明文, 則其對應的密文就是鑰匙。 例如, 在密文中對應的字 母為 H(=7), 則其鑰匙就是 k=7。 選擇密文攻擊法: 選取字母 A 為密文, 則其對應的明文之負值就是鑰匙。 例如, 在明文中對 應字母為 h(=7), 則其鑰匙就是 k ≡ −7 ≡ 19 (mod 26)。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 原字母 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z