公開金鑰密碼系統 Public Key Cryptosystem 　　　　 　　 　 Public key ▽ Plaintext 明文 → Encrypt 加密 　　　 ↖ ↘ Decrypt 解密　← 　Ciphertext 密文 △ Private key　　　　　 最廣泛使用的 PKC: RSA (Rivest – Shamir – Adleman 1977) 逐漸受重視的 PKC: ECC (橢圓曲線 Elliptic Curve Cryptosystem) 2018/11/16

私密金鑰 與 公開金鑰 私密金鑰 公開金鑰 Private Key 非常困難 Public Key 容易計算 藉由數學工具達成此目的 私密金鑰　與　公開金鑰 　　　　　　　　　　 　 容易計算 私密金鑰 公開金鑰 Private Key 　非常困難　　　 Public Key 　藉由數學工具達成此目的　　　　　　　 2018/11/16

RSA方法 RSA加密演算法是一種非對稱加密演算法，在1977年由Ron Rivest、Adi Shamir與Leonard Adleman一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。 如果你想和別人祕密通訊，那麼你可以先選定兩個非常巨大的質數p,q作為私鑰（private key，解密用的），然後將p,q的乘積作為加密用的公鑰 (public key)，你可以把公開鑰匙公佈出去。別人要傳一封密函給你，他必需要先得到你的公鑰，按照一個約定的方法將信件加密後送出。你在收到密函後，再用你的私鑰就可以解出密函原文。 RSA演算法的可靠性基於分解極大的整數是很困難的。假如有人找到一種很快的分解因子的演算法的話，那麼用RSA加密的資訊的可靠性就肯定會極度下降。但找到這樣的演算法的可能性是非常小的。 今天只有短的RSA鑰匙才可能被強力方式解破。到2008年為止，世界上還沒有任何可靠的攻擊RSA演算法的方式。只要其鑰匙的長度足夠長，用RSA加密的資訊實際上是不能被解破的。

Definition For n1, (n) --- 小於或等於n且跟互質n的正整數個數. (1)=1, (2)=1, (3)=2, (4)=2, (5)=4, (6)=2, (7)=6, (8)=5 (n)= n -1 if and only if n is prime.

Theorem If the integer n>1 has the prime factorization n=p1k1p2k2…prkr, then

Theorem (Euler) 給定正整數n與整數a且 gcd (a,n)=1, 則 a(n) 1 (mod n). Fermat’s little theorem: 令為p質數且a與p互質,則ap-1  1(mod p).

Example 316  814  (-19)4  3612  612  21 (mod 100) Find the last two digits of 3256 100=2252 (100)=100(1-1/2)(1-1/5)=40 340  1 (mod 100) 3256  (340)6  316  316 (mod 100) 316  814  (-19)4  3612  612  21 (mod 100)

RSA方法 Alice隨意選擇兩個大的相異質數p和q，並計算出n=pq。 任選擇一個小於(p-1)(q-1)且與(p-1)(q-1)互質的整數E，並計算出d使得Ed ≡ 1 (mod (p-1)(q-1)) 。 n和E是公鑰，公開給大眾的。d是私鑰，只有Alice 知道。 假設Bob想給Alice送一個隱密的消息M，他先將M轉換為一個比較小的整數P (必須小於n且與n互質) ，比如他可以將每一個字轉換為這個字的unicode碼，然後將這些數字連在一起組成一個數字。假如他的資訊非常長的話，他可以將這個資訊分為幾段，然後將每一段轉換為P。利用公鑰N和E及PE  C(mod n)這個式子將P加密為C。 Bob算出C後就可以將它傳遞給Alice。 Alice得到Bob的訊息C後就可以利用她的私鑰d及式子Cd  P (mod n)來解碼還原成P。

如何產生公鑰E和私鑰d Alice隨意選擇兩個大的相異質數p和q，並計算出n=pq。 任選擇一個小於(p-1)(q-1)且與(p-1)(q-1)互質的整數E，並計算出d使得Ed ≡ 1 (mod (p-1)(q-1)) 。 n和E是公鑰，公開給大眾的。d是私鑰，只有Alice 知道。 依需求找出兩相異質數 。 假設是p=47,q=59 則 n=pq=47 * 59=2773 且 b=(p-1)(q-1)=2668 從與與b互質的整數中依需求找出E，假設找出的 E = 157 求出Ex 1(mod b)的解。最小正整數解即為私鑰d = 17。

加密 假設Bob想給Alice送一個隱密的消息M，他先將M轉換為一個小於n的整數P。利用公鑰N和E及PE  C(mod n)這個式子將P加密為C。 n=pq=47 * 59=2773 且 E = 157 假設Bob想給Alice送一個隱密的消息M=3。此時P=M=3 PE  3157  (9)78 ·3 (mod 2773)  (81)39 ·3 (mod 2773)  (6561)19 ·81·3 (mod 2773)  (1015)19 ·81·3 (mod 2773)  (1030225)9 ·1015·81·3 (mod 2773)  (1442)9 ·1015·81·3 (mod 2773)  441 (mod 2773)

解密 Bob利用公鑰N和E及PE  C(mod n)這個式子將P加密為C。 Alice如何還原出P。 n為兩個相異質數p和q的乘積，E為小於且互質於b=(p-1)(q-1)的整數。 找出Ex 1(mod b)的解。最小正整數解即為私鑰d，所以Ed = kb+1。 尤拉定理(Euler Theorem)告訴我們對所有與n互質的正整數a皆有ab  1 (mod n). 所以Cd  (PE)d  PEd  Pkb+1  P (mod n)

RSA方法 Alice隨意選擇兩個大的相異質數p和q，並計算出n=pq。 任選擇一個小於(p-1)(q-1)且與(p-1)(q-1)互質的整數E，並計算出d使得Ed ≡ 1 (mod (p-1)(q-1)) 。 n和E是公鑰，Alice將它們公開給大眾。d是私鑰，只有Alice 知道。 Bob將隱密的消息M分為幾段使得每段皆為比較小的整數P (必須小於n且與n互質)。然後他利用PE  C(mod n)這個式子將P加密為C。 Bob算出C後就可以將它傳遞給Alice。 Alice得到Bob的訊息C後就可以利用她的私鑰d及式子Cd  P (mod n)解碼。

Example Alice找出兩相異質數 p=29,q=41 則 n=pq=29 * 41=1189 且 b=(p-1)(q-1)=1120 從與與b互質的整數中依需求找出E = 101 求出Ex 1(mod b)的解。最小正整數解即為私鑰d = 621。 假設Bob想給Alice送一個隱密的消息M=90。此時P=M=90 他利用PE  C(mod n)這個式子將P加密為C。

Example 90101  (902)50 ·90 (mod 1189)  (966)50 ·90 (mod 1189) 他利用PE  C(mod n)這個式子將P加密為C=582。 90101  (902)50 ·90 (mod 1189)  (966)50 ·90 (mod 1189)  (9662)25 ·90 (mod 1189)  (980)25 ·90 (mod 1189)  (9802)12 ·980·90 (mod 1189)   582 (mod 1189)

Example Alice找出兩相異質數 p=29,q=41 則 n=pq=29 * 41=1189 且 b=(p-1)(q-1)=1120 從與與b互質的整數中依需求找出E = 101 求出Ex 1(mod b)的解。最小正整數解即為私鑰d = 621。 假設Bob想給Alice送一個隱密的消息M=90。此時P=M=90 他利用PE  C(mod n)這個式子將P加密為C=582 。 Alice得到Bob的訊息C=582後就可以利用她的私鑰d = 621及式子Cd  P (mod n)解碼。

Example 582621  (5822)310 ·582 (mod 1189)  (1048)310 ·582 (mod 1189) Alice得到Bob的訊息C=582後就可以利用她的私鑰d = 621及式子Cd  P (mod n)解碼。 582621  (5822)310 ·582 (mod 1189)  (1048)310 ·582 (mod 1189)  (10482)155 ·582 (mod 1189)  (857)155 ·582 (mod 1189)  (8572)77 ·857·582 (mod 1189)   90 (mod 1189)

RSA 的安全性 分解 (Factoring): 如果能將 n 分解成兩個質數, 就能計算 (n) 及 d=e-1 mod (n). 因此, 破 RSA 不會比 integer factoring (整數分解) 難. 然而, 要分解一個 160-digit 的數並不容易

Mathematical attacks: 暴力法 試所有的 private keys 需要 O(d) 的時間 因此 d 應該要夠大, 例如 >sqrt(n) Mathematical attacks: 分析 n 的結構找 p 和 q 選擇好的質數(強質數) p-1 和 q-1 要有大的質因數 gcd(p-1, q-1) 要小 …

Example Alice利用RSA依代碼a=00, b=01, …, z=25將明文字母各自轉換成數字後使用公鑰(n=1073, e=605)編碼得 (18,0,316,316) 並傳給Bob。請問 Alice所使用的質數p,q為何? 密鑰d為何? 傳送的訊息為何?

(n=1073, e=605)編碼得 C=(18,0,316,316) n=1073=3729  p=37,q=29 b=(n)=(37-1)(29-1)=1008 1008=605+403 605=403+202 403=202+201 202=201+1 1=202-201=2022-403=6052-4033 =6055-10083 d = 5

(n=1073, e=605)編碼得 C=(18,0,316,316) n=1073=3729  p=37,q=29 d = 5 185  5832182 (mod 1073)  467182 (mod 1073)  15 (mod 1073) 3165  795210 (mod 1073)  18 (mod 1073) (15,0,18,18)  PASS

數位簽章 Digital Signature * 秘密性 (confidentiality) * 身份鑑別性 (Authentication) * 完整性 (Integrity) * 不可否認性 (Non-Repudiation) 2018/11/16

數位簽章 當收到具有數位簽章的訊息時，接收者可以利用簽章來得知傳送者的身分，進而確認訊息的內容是否已遭到竄改。 由於數位簽章具有不可否認的特性，所以若使用者在訊息上使用了數位簽章，便無法逃避曾經撰寫過此訊息的事實。 數位簽章在數位訊息中扮演著鑑別的角色，它可以讓接收者對於訊息的來源及其完整性更有信心。

RSA簽章 選擇兩個大質數 p , q 計算 n = p×q 計算ψ(n)=(p-1)×(q-1) 找出一組數值 e×d≡1 mod ψ(n) 將(e, n)公開、其他數值保持秘密

RSA簽章 選擇兩個大質數 p , q 計算 n = p×q 計算ψ(n)=(p-1)×(q-1) 找出一組數值 e×d≡1 mod ψ(n) 將(e, n)公開、其他數值保持秘密 此時任何人交付明文 m要求簽章

RSA簽章 此時任何人交付明文 m要求簽章 用秘密的 d 值，就可簽署明文為 s = m d mod n

RSA簽章 用秘密的 d 值，就可簽署明文為 s = m d mod n 用公開的 (e, n)，即可驗證簽章 s e mod n = (m d)e mod n = m

RSA簽章 選擇兩個大質數 p , q 計算 n = p×q 計算ψ(n)=(p-1)×(q-1) 找出一組數值 e×d≡1 mod ψ(n) 將(e, n)公開、其他數值保持秘密 此時任何人交付明文 m要求簽章 用秘密的 d 值，就可簽署明文為 s = m d mod n 用公開的 (e, n)，即可驗證簽章 s e mod n = (m d)e mod n = m

RSA簽章 選擇兩個大質數 p , q 所謂簽章就是證明你是你，而如果能做出一件事是只有你做得出來，那就是最好的證明，而這個過程正是如此 計算 n = p×q 選擇兩個大質數 p , q 計算ψ(n)=(p-1)×(q-1) 找出一組數值 e×d≡1 mod ψ(n) 將(e, n)公開、其他數值保持秘密 所謂簽章就是證明你是你，而如果能做出一件事是只有你做得出來，那就是最好的證明，而這個過程正是如此 此時任何人交付明文 m要求簽章 用秘密的 d 值，就可簽署明文為 s = m d mod n 用公開的 (e, n)，即可驗證簽章 s e mod n = (m d)e mod n = m

RSA簽章的實例 選擇 p = 622354832383 q = 38895514943 計算 n =24206811682801236799169 計算ψ(n)=24206811682139986451844 找出一組數值 e×d≡1 mod ψ(n) e=31, d=19521622324306440686971 將(e, n)公開、其他數值保持秘密

RSA簽章的實例 計算 n =24206811682801236799169 選擇 p = 622354832383 q = 38895514943 計算ψ(n)=24206811682139986451844 找出一組數值 e×d≡1 mod ψ(n) e=31, d=19521622324306440686971 將(e, n)公開、其他數值保持秘密 此時任何人交付明文 m要求簽章

RSA簽章的實例 假設要假設要簽署的明文 m為 ‘bob cracked rsa’， 公鑰: e=31, n=24206811682801236799169 密鑰: d=19521622324306440686971 假設要假設要簽署的明文 m為 ‘bob cracked rsa’， 依代碼 □= 0, a= 1, b=2, …, z=26將明文編成27進制的數值，即可得下列明文m值: m = (2, 15 , 2, 0, 3,18, 1, 3, 11, 5, 4, 0, 18, 19, 1)27 = 2×2714+15×2713+2×2712+3×2710+18×279+1×278 +3×277 +11×276 +5×275 +4×274 +18×272+ 19×27+1 = 279927250081200479782 此時任何人交付明文 m要求簽章

RSA簽章的實例 假設要假設要簽署的明文 m為 ‘bob cracked rsa’， 公鑰: e=31, n=24206811682801236799169 密鑰: d=19521622324306440686971 假設要假設要簽署的明文 m為 ‘bob cracked rsa’， 依代碼 □= 0, a= 1, b=2, …, z=26將明文編成27進制的數值，即可得明文 m = 279927250081200479782 有秘密的 d 值，就可以將明文簽署成下列的 s 值: S = md (mod n) = 27992725008120047978219521622324306440686971 = 17083178691394655337512 (mod 24206811682801236799169) 用秘密的 d 值，就可簽署明文為 s = m d mod n

RSA簽章的實例 假設要假設要簽署的明文 m為 ‘bob cracked rsa’， 公鑰: e=31, n=24206811682801236799169 密鑰: d=19521622324306440686971 用公開的 (e, n)，即可驗證簽章 s e mod n = (m d)e mod n = m 假設要假設要簽署的明文 m為 ‘bob cracked rsa’， 依代碼 □= 0, a= 1, b=2, …, z=26將明文編成27進制的數值，即可得明文 m = 279927250081200479782 有秘密的 d 值，就可以將明文簽署成下列的 s 值: 有公開的e,n值，任何人均可驗證簽章是否可經下列計算得出明文: m = se (mod n) =1708317869139465533751231 (mod 24206811682801236799169) =279927250081200479782 = 2×2714+15×2713+2×2712+3×2710+18×279+1×278+3×277+11×276 +5×275 +4×274 +18×272+ 19×27+1 = (2,15, 2, 0, 3, 18, 1, 3, 11, 5, 4, 0, 18, 19, 1)27 即為 ‘bob cracked rsa’

RSA簽章的實例 選擇 p = 622354832383 q = 38895514943 計算 n =24206811682801236799169 計算ψ(n)=24206811682139986451844 找出一組數值 e×d≡1 mod ψ(n) e=31, d=19521622324306440686971 將(e, n)公開、其他數值保持秘密 此時任何人交付明文 m要求簽章 用秘密的 d 值，就可簽署明文為 s = m d mod n 用公開的 (e, n)，即可驗證簽章 s e mod n = (m d)e mod n = m RSA

RSA簽章的可能偽造方法與解決方案 選擇 p = 622354832383 q = 38895514943 計算 n =24206811682801236799169 計算ψ(n)=24206811682139986451844 找出一組數值 e×d≡1 mod ψ(n) e=31, d=19521622324306440686971 將(e, n)公開、其他數值保持秘密 此時任何人交付明文 m要求簽章 用秘密的 d 值，就可簽署明文為 s = m d mod n 用公開的 (e, n)，即可驗證簽章 s e mod n = (m d)e mod n = m

RSA簽章的可能偽造方法與解決方案 選擇 p = 622354832383 q = 38895514943 此時任何人交付明文 m要求簽章 用秘密的 d 值，就可簽署明文為 s = m d mod n 用公開的 (e, n)，即可驗證簽章 s e mod n = (m d)e mod n = m 計算 n =24206811682801236799169 選擇 p = 622354832383 q = 38895514943 計算ψ(n)=24206811682139986451844 找出一組數值 e×d≡1 mod ψ(n) e=31, d=19521622324306440686971 將(e, n)公開、其他數值保持秘密 RSA簽章有"乘法代數性質"，所以是有可能被偽造的唷！ 假設 s1=m1d mod n , s2=m2d mod n 代表對兩份明文 m1 與 m2 所做的簽章 s1 與 s2 可是，把這兩個簽章相乘 s1 ．s2 = (m1d mod n) ． (m2d mod n) = (m1．m2)d mod n 令兩個簽章的相乘值為 s3，而假設有心人花了很大的 功夫找出一個有意義的明文 m3 ， 而且 m3 = m1．m2 ，那麼 s3 即為 m3 的正確簽章， 也就是說，雖然只有簽過兩份明文 m1 與 m2，但卻可 能冒出第三份明文 m3 號稱也被簽署過 而且兜出來的簽章 s3 也是正確的。

RSA簽章的可能偽造方法與解決方案 RSA簽章有"乘法代數性質"，所以是有可能被偽造的唷！ 若要防止這種偽造的發生，最簡單的方法就是用密鑰 對明文做簽章前，先用雜湊函數 (Hash function)對明文做摘錄，而且確定摘錄值相乘不會 有"乘法代數性質" : H(m1．m2 ) ≠ H(m1 )．H(m2 ) 所以，也就是說 : s1 ．s2 ＝ (H(m1 ) d mod n) ． (H(m2 ) d mod n) ≠ (H(m1 ．m2 )) d mod n 如此就不可能冒出第三份明文 m3 號稱也被簽署過， 而且被兜出一個正確的簽章 s3。

RSA簽章的可能偽造方法與解決方案 RSA簽章有"乘法代數性質"，所以是有可能被偽造的唷！ 至於什麼是雜湊函數(Hash function)？就如同 中文譯名的 "雜湊" 二字，可以隨興設計一個 亂湊出來的方式，把不論多長的明文都摘錄成一個不 太大的數值。 譬如，在報章雜誌常見的生命靈數命理方法 : 西元出生年+月份+日期=生命靈數，如果算出來是兩位數，則再將 十位數加個位數，一直簡化到個位數字為止。例如1980年8月23日 的生命靈數是：1＋9＋8＋0＋0＋8＋2＋3＝31，再做3＋1＝4。 可以說就是一種Hash function，你也可以發明一套更 亂的公式，不只是加法，還把各種運算融入，甚至把 身份字號、電話號碼、門牌號碼都一起算進來，反正 最後就是出來一個數值，然後你就可以依據這個數值 幫大家算命，亂掰一下囉！

數位簽章與雜湊函數合併使用 數位簽章通常會和雜湊函數合併使用，以增進簽章的運算效能。 雜湊函數的設計必須具備無法找出相同雜湊值的能力。 假設A要發送一封具有簽章的訊息給B，則A必須先對所發送的整篇訊息執行雜湊函數（Hash Function）運算，產生一個訊息摘要。 這個訊息摘要可以看成是整封訊息的「數位指紋」，若此訊息的任一部份遭到修改，則雜湊函數的運算結果就會不同。

完成訊息摘要後，A就可以用他的私密金鑰對此訊息摘要進行簽署的動作，此簽署過的訊息摘要就是整封訊息的數位簽章，接著A再將訊息以及數位簽章寄送給B。 當B收到A所傳送來的訊息及數位簽章後，為了要查驗此訊息，B必須先將收到的訊息使用與A相同的雜湊函數計算出另一個訊息摘要後，再使用A的公開金鑰來針對訊息摘要做驗證，若兩者驗證結果相符，則代表訊息確實來自A，且證明訊息的內容在A簽章過後就沒有遭到修改。

進一步衍生的電子憑證(Certificate)概念 若交付簽章的明文 m是身份資料 具有公信力的憑證中心以密鑰 d 簽署明文摘錄值 s = H(m) d mod n 用憑證中心公開的 (e, n)，任何人均可驗證某人的身份資料之簽章 s e mod n = (H(m) d)e mod n = H(m)

進一步衍生的電子憑證(Certificate)概念 具有公信力的憑證中心簽署某人 身份資料的明文與簽章組成憑證 就是可證明其身份的電子身份證 Certificate

混合式密碼系統 B Public key A Private key A B Private key A Public key B

同時達到秘密通訊與數位簽署 A 欲傳送資訊給 B 數位簽署 A 以自己的 private key 加密，若 B 能以 A 的 public key 解開，則可驗證為 A 所發。 秘密通訊 A 以 B 的 public key 加密，B 以自己的 private key 解開(同前)。

優缺點比較(非對稱) 優點 資訊機密性高 (加密機制較嚴密) 鑰匙方便管理 (一公一私) 不可否認性 (數位簽署認證) 缺點 運算複雜耗時長，速度慢

網路安全應用實例 : SSL SSL(Secure Socket Layer)是Netscape所提出來的資料保密協定，採用了RC4、MD5，以及RSA等加密演算法。 如果您想登入的網站具有SSL功能那麼您與網站之間所傳的資料都可以使用SSL協定來保密，除非能破解傳輸密碼，否則其他任何人都無法得到這些機密資料。 那SSL的密碼會被破解嗎？答案是『非常非常不容易』，而且保密鑰匙的長度（key-length）越長，安全度越高！

網路安全應用實例 : SSL 使用SSL 安全方法時，使用者產生一把對稱金鑰（session key），將待傳送的資料「加密」成亂碼，網站接收資料後再使用同一把對稱金鑰「解密」出原來的資料。為了將使用者產生的這一把加解密用的對稱金鑰安全地傳給伺服器，SSL 於使用者傳送這一把對稱金鑰前，先使用伺服器的公開金鑰（publickey）將對稱金鑰「加密」成亂碼，網站接收資料後再使用伺服器的私密金鑰（private key）「解密」出原來的對稱金鑰。

Remark 加密過程越複雜，安全性更高，但相對的速度也越慢 (trade off) 安全性 → 即使破祕者知道加密演算法，也無法輕易破解密文 沒有絕對破解不了的演算法 (假如有無限時間)，只要相對安全即可 (10^16 年 ……)