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

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

7.1 公開金鑰加密系統 CA Send 加密 解密 Send 解密 加密 李四’s公開金鑰 李四’s私有金鑰 金鑰 密文 密文 明文 明文 張三 李四 李四’s公開金鑰 李四’s私有金鑰

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

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

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

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之相乘，是很困難的

RSA 演算法- 例子 1. 張三選 p=3 ， q=11 ; 此時 N = p • q = 3 x 11 = 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,滿足 e • d  1 mod 20當作解密金鑰，( d=7 7 x 3  1 mod 20 ) 令明文 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

RSA 演算法 Cd mod N = Med mod N = MaØ(N)+1 mod N = M 定理: Ø(P) = P-1 若P為質數 Ø(N) = Ø(PQ) = Ø(P)Ø(Q) Ø(A) = i=1..t Piei-1 (Pi-1) 設A=P1e1P2e2…Ptet Pi為所有質因數 Cd mod N = Med mod N = MaØ(N)+1 mod N = M Euler通用定理: 若A，P互質，則 AØ(P) mod P = 1 費瑪(Fermat)定理: 若P為質數且(A,P)互質，則 AP-1 mod P = 1

RSA 演算法（續） 乘法反元素求法： 已知A，P互質，如何計算A-1使得AA-1 mod P=1? 方法一：利用Euler定理 A-1 = AØ(P)-1 mod P 方法二：利用歐氏里德(Euclid)演算法 g0:= P; g1:=A; u0:=1; u1:=0; v0:=0; v1:=1; i:=1; while gi  0 do begin y := gi-1 div gi; gi+1 = gi-1 - y * gi; ui+1 := ui-1 - y * ui; vi+1 := vi-1 - y * vi; i:=i+1; end x:= vi-1; if x  0 then A-1 := x else A-1 := x + P;

RSA 演算法（續） 指數運算：計算 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

RSA數位簽章 張三 一般使用時會先將文件M 作HASH函數處理，使得 HASH(M)比N小 S = Md張mod N張 傳送M及S 李四 M =? Se張mod N張 李四使用張三的公開金鑰確認數位簽章及文件

RSA數位簽章（續） 數位簽章法(Digital Signature) H || M M 比較是否相等 D ESKa[H(M)] 為M之簽章 DPKa[ESKa[H(M)]] =H(M) ESKa[H(M)] 為M之簽章 PKa H E 512 位元 SKa

RSA數位簽章+加密 張三 C = ( Md張mod N張 )e李mod N李 傳送密文 C 李四 M = ( Cd李mod N李)e張mod N張 李四使用私有金鑰解開密文 C 再用張三的公開金鑰確認數位簽章

7.3 ElGamal Cryptosystem  非對稱式密碼系統的一種。  1985年由ElGamal所發展出來的。  安全性導因於離散對數(Discrete Logarithm)之困難度。  相同明文可得到不相同的密文。 RSA密碼系統則是相同明文得到相同密文。 離散對數(Discrete Logarithm)的問題： 若p為很大之質數；g為p之原根 (primitive root) y = gx mod p 雖已知y, g, p ，但要導出x值是很困難的

ElGamal Cryptosystem（續）  若g為p之原根 (primitive root)： gi mod p  gj mod p 其中i  j且i, j介於1至(p-1)之間 例如：2為11之原根，因為 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  若g為p之原根，且a與(p-1)互質，則ga mod p亦為p之原根。例如：2為11之原根，且3與10互質，則23 mod 11=8亦為11之原根。  定理：p之原根個數為Ø(p-1)。

ElGamal 加密法 李四之金鑰產生： 張三將明文m以李四之公開 y = gx mod P 金鑰加密： y為李四之公開金鑰 g為與P互質之原根 張三將明文m以李四之公開 金鑰加密： 1. 張三選一個亂數r 2. 計算 b = gr mod P c = m • yr mod P 張三送(b,c)給李四 4. 李四收到(b,c)後計算 c • (bx)-1 mod P = m

ElGamal 數位簽章法 李四之金鑰產生： 李四將明文m以李四之祕密 y = gx mod P 金鑰製作簽章： y為李四之公開金鑰 g為與P互質之原根 李四將明文m以李四之祕密 金鑰製作簽章： 1.李四選一個亂數k使得gcd(k,p-1)=1 2.計算r = gk mod p 3.李四計算s使得m = (xr+ks) mod (p-1) 4.李四送(m,r,s)給驗證者(張三) 5.張三收到(m,r,s)後驗證 gm = yrrs mod P 上式若相等表示m確定為李四所簽署

7.4 橢圓曲線密碼系統 RSA或ElGamal密碼系統最為人詬病的問題就是在加解密或是簽章的時候需要龐大的運算量，所以需要較長的運算時間。 為了改善其效率（較少之運算量），因此提出橢圓曲線的密碼系統(Elliptic Curve Cryptosystem, ECC)，它的安全性必須相當於RSA或ElGamal的密碼系統。

橢圓曲線上的有限加法群 所使用的橢圓曲線方程式為y2=x3+ax+b 此曲線剛好對稱於y=0這條直線 參數 a 及 b 必須滿足4a3+27b2≠0，才能確保沒有重根，具有唯一解 加法單位元素O為一無窮遠的點，並滿足O= -O 此加法單位元素亦需滿足：橢圓曲線上某三點共線其合為O

橢圓曲線上不同座標點相加

橢圓曲線上相同座標點相加

橢圓曲線上一座標點與一無窮遠點相加 © The McGraw-Hill Companies, Inc., 2005

橢圓曲線上兩對稱點相加 A＋B=A+(-A)=O B

在有限體內的橢圓曲線運算 在此橢圓曲線上可能出現的點有(0,1)、(0,4)、(2,1)、(2,4)、(3,1)、(3,4)、(4,2)、(4,3)、(∞, ∞) 任取橢圓曲線上兩點，無論作加法、減法或乘法，其結果永遠為上述座標點中的一點 橢圓曲線中的離散對數難題：給訂一參數K及一點A，要求得另一點B，使得B=KA是很容易的。 例如：5A=A+A+A+A+A 但若給定A及B要求得K則很困難

橢圓曲線的公開金鑰加密機制 點: G, B, R 數字: M, M1, M2, K, r, C1, C2

橢圓曲線的數位簽章 數字: M, K, S, r, Rx 點: G, B, R, V1, V2 © The McGraw-Hill Companies, Inc., 2005

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

數位信封(Digital Envelope) Sender : Alice Receiver : Bob 密文 明文 C = ESK(M) 密文及信封 M = DSK(C) 信封 交談金鑰 V = EPU(SK) SK = DPR(V) SK: Session Key(交談金鑰) ESK :秘密金鑰密碼系統(Key: SK) PU: Bob之公開金鑰 EPU :公開金鑰密碼系統(Key: PU) PR: Bob之秘密金鑰

Diffie-Hellman 的金鑰交換方法 註: p為很大之質數 g為與p互質之原根(primitive)

Diffie-Hellman 的金鑰協議方法

7.6 量子密碼學 前使用的密碼系統中，如DES、RSA、ElGamal或橢圓曲線密碼系統，其安全程度都僅屬於計算安全 (Computational Secure) 。 量子電腦的出現，使得現存的密碼系統都將不再安全。 有機會利用量子電腦來發展出無條件安全的密碼系統

量子電腦的基本概念 量子電腦 (Quantum Computer)是利用量子物理的法則所設計的一種電腦。 與傳統電腦最大的差別在於量子電腦可以同步地處理同一件工作，因此可大幅縮減在運算上所需花費的時間。 量子電腦的基本元素稱之為量子位元 (Quantum Bits)，簡稱為qubits。

量子電腦的特性 疊加性 (Superposition) 假設每一個量子位元都可能會有兩種狀態，不是順時針旋轉就是逆時針旋轉，若我們把一個粒子放到一個暗箱裡，然後用一個微弱的脈衝打進去，此時箱子內的粒子可能是順時針，也可能是逆時針，若不打開箱子看，我們無法得知這個粒子旋轉的方向。這種所有狀態都可能出現的情況就稱為疊加性。 測量性 (Measurement) 在箱子打開之前，量子是以疊加的狀態存在，也就是順時針旋轉或逆時針旋轉都有可能。一旦箱子被打開後，答案就公佈了，量子的疊加性也隨之消失。

量子電腦的特性（續） 可逆性 (Reversing) 在量子運算中，所有運算在未經測量前都是可逆的。 不可複製性 (No-cloning) 無法對處於疊加狀態中的量子進行複製。 糾纏性 (Entanglement) 無法分解成任意兩個量子態的乘積。

量子電腦對傳統密碼學的威脅 以猜數字遊戲為例，一方從0到9的數字中任選四個不同的數字，由另一方來猜，總共有10 × 9 × 8 × 7 = 5040 種可能的答案。 若把這個猜謎遊戲交給傳統電腦來執行，就算電腦依序測試各種可能的答案，例如，先猜0123，若不對，接著就猜0124，如此不斷地猜下去，徹底嘗試過5040種可能的答案，也只需要幾秒鐘的時間就可以找到正確的答案。

量子電腦對傳統密碼學的威脅（續） 由於量子電腦可以對同一個問題的不同狀態進行同步的處理，所以量子電腦可以更有效率地來執行這個猜謎遊戲。其作法如下： 我們可以用14個位元來表示任何由4個數字所組成的十進位數字，例如「00000001111011」就相當於十進位的「0123」，「00000001111100」相當於十進位的「0124」。 然後將每一個位元用一個量子位元來表示，再將這14個量子位元同時放到一個箱子中。 打入弱脈衝，使之旋轉方線產生變化，此時這14個量子就進入疊加狀態了，它同時代表214種可能發生的狀態，然後把這些處於疊加狀態的粒子放入量子電腦中執行。 由於量子電腦可以同時嘗試所有可能的答案，一個單位時間後，量子電腦就會告訴我們正確的謎底為何，而傳統電腦可能需要5040個單位時間，才能完成所有可能答案的搜查。

量子密碼學 概念是利用光子的偏震方向來代表「0」或「1。 偏震方向的定義有兩種，分別是直線方案 (Rectilinear)與斜線方案(Diagonal)。 直線方案中偏振方向「|」代表「1」，偏振方向「－」代表「0」。 斜線方案中偏振方向「\」代表「1」，偏振方向「/」代表「0」。 而用來測量偏振方向的偵測器也可分為兩種，分別為直線型「＋」，與斜線型「×」，「 ＋ 」型偵測器可用來判定「|」及「－」偏振的光子；同理， 「×」型偵測器可用來判定「\」及「/」偏振的光子。

利用量子密碼進行秘密通訊 春嬌隨意用直線或斜線方案來傳送一連串可代表0或1位元的光子給志明。 由於志明不知道春嬌依序用了哪些方案來傳送這些光子，故志明也隨意選用直線或斜線偵測器來測定光子的偏振方向。若志明所選的偵測器恰好與春嬌發送時所選用的方案一樣時，則志明可正確地測量出該光子是代表0或是1位元；反之，若選用的偵測器與春嬌發送時所選用的不一樣時，則有一半的機率可以正確地猜出所要表示的位元。 因此春嬌與志明要確認哪些位元是判定正確的位元、哪些是誤判的位元。確認方法只針對依序所使用方案做一確認並沒有談及所判定的結果為何。

利用量子密碼進行秘密通訊（續） 春嬌與志明核對完之後，他們捨去掉那些使用錯誤偵測器所得到的位元，而保留用正確的偵測器所判定的位元。因此雙方可共同得到一段由正確判定位元所組成的加密金鑰。 不過春嬌與志明所持有的這個加密金鑰也可能會有錯誤，原因是在傳遞的過程中攻擊者還是有可能會進行竊聽。春嬌與志明可以執行一個簡單的錯誤檢查協定，例如雙方所協議出來的金鑰長度共有1064個位元，春嬌就從中選取64個位元與志明做比對，若比對的結果有誤，就表示在傳送的過程中遭到監聽，金鑰的協議需要重新來過；若無誤，則春嬌與志明大可相信他們手中的金鑰是一致的。 金鑰協議無誤後，就可利用此一協議出來的金鑰來做加解密，由於春嬌選擇要傳送的量子位元是隨機的，志明選擇用來判定偏振方向的偵測器也是隨機的，所協議出來的金鑰也可當做一次性密碼系統(One-Time Pad)的金鑰來使用，因此可以達到無條件的安全。

範例 / | / / | \ / | --\ 010 011 0101 x+x x+x x++x (春) xxx ++x x+x+ (志) / | / / | \ / | --\ 010 011 0101 x+x x+x x++x (春) xxx ++x x+x+ (志) 0?0 ?11 01?? (核對) 001101 01 (比對) /  +  | or ― |  x / or \ 正確 key = 0110 錯誤 竊聽  從新來過

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

密碼破解(Cryptanalysis) 攻擊法 破解者 破解 種類 擁有 內容 密文攻擊法 密文 明文 攻擊法 破解者 破解 種類 擁有 內容 密文攻擊法 密文 明文 (Ciphertext-Only Attack) 已知明文攻擊法 明文-密文 解密 (Known-Plaintext Attack) 配對 金鑰 選擇明文攻擊法 含加密金鑰 秘密 (Chosen-Plaintext Attack) 之密碼系統 金鑰 選擇密文攻擊法 含解密金鑰 秘密 (Chosen-Ciphertext Attack) 之密碼系統 金鑰 低 至少 高