|
密碼學 Chapter 4 基於電腦的非對稱性金鑰密碼學演算法
Computer-based Asymmetric Key Cryptographic Algorithms (Part 1)
|
|
|
|
前言
對稱性金鑰密碼學是快速且有效率的
對加密的訊息，發送方和接收方在對稱性金鑰密碼學中使用相同金鑰，要同意這一把金鑰並未讓任何其他人知道是一件非常困難的事
非對稱性金鑰密碼學可以解決這個問題
|
|
|
|
非對稱性金鑰密碼學的簡史
在1970年間，史丹佛大學的學生 Whitfield Diffie 遇見他的教授 Martin Hellman，他們開始思考金鑰交換的問題，經過一些研究與複雜的數學分析，他們開始興起非對稱性金鑰密碼學的想法
許多專家認為這在密碼學史上或許是唯一的真正改個概念，因此，Diffie 和 Hellman 被當成非對稱性金鑰密碼學之父
|
|
|
|
非對稱性金鑰密碼學的簡史
非對稱性金鑰密碼學榮耀的爭論
英國通訊電子安全組織 (Communication Electronic Security Group, CSEG)
秘密的單位
1960, Jame Ellis
1973, Cliffird Cocks
1974, Malcolm
美國國家安全局 (National Security Agency, NSA)
1970, 也在發展非對稱金鑰密碼系統
|
|
|
|
非對稱性金鑰密碼學的簡史
在1977年，Ron Rivest、Adi Shamir 和Len Adleman 在 MIT 時發展出第一個主要的非對稱性金鑰密碼學系統
基於 Diffie 和 Hellman 理論的框架
並在 1978 年發表他們的結果。這個機制被稱為 RSA演算法
|
|
|
|
非對稱性金鑰密碼學的簡史
RSA 是被廣泛接受的公開金鑰機制
解決了金鑰協議和分配的問題
|
|
|
|
非對稱性金鑰密碼學總覽
非對稱性金鑰密碼學 (Asymmetric Key Cryptography)
公開金鑰密碼學 (Public Key Cryptography)
金鑰對 (key pair)
公開金鑰 (public key)
散佈給任何人都可以取得
用於加密
私密金鑰 (private key)
個人保存
用於解密
|
|
|
|
非對稱性金鑰密碼學的運作
當A想要寄出訊息給B，A使用B的公開金鑰加密訊息。(因為A知道B的公開金鑰)
A寄出這個訊息給B。(已經用B的公開金鑰加密的訊息)
B使用B的私密金鑰解密A的訊息。(只有B知道自己的私密金鑰)
只有B才有解開密文訊息的私密金鑰，故傳輸過程中的訊息對任何人是沒有意義的。
|
|
|
|
非對稱性金鑰密碼學的運作
若B要傳送訊息給A
使用相同的步驟，但是B使用A的公開金鑰加密訊息，A收到B傳送過來的密文訊息，A使用A的私密金鑰解開密文。
|
|
|
|
私密與公開金鑰
私密金鑰：用於解密
公開金鑰：用於加密
|
|
|
|
RSA演算法
RSA演算法為目前最受歡迎的非對稱性金鑰密碼學演算法
RSA基於因數分解的問題
RSA使用大質數來產生金鑰
|
|
|
|
質數
所謂質數是指只能被 1 和自己整除的數
例如
3, 5, 7, 11, 13, 17, 19, 23, 29, 31,…
|
|
|
|
RSA演算法原理
基於數學事實
找大質數並相乘是容易，但要從乘積中進行因數分解是非常困難的
RSA的私密與公開金鑰是基於一個非常大的質數(100位數或是更多位數)
RSA的演算法非常簡單，但是真正的挑戰在金鑰的選擇和產生
|
|
|
|
RSA金鑰產生步驟
選擇兩個大質數 P 和 Q
計算 N = P * Q
選擇公開金鑰 E，使它不是一個 (P – 1) 和 (Q – 1) 的因數
選擇私密金鑰 D，使下列的恒等式為真 (D * E) mod (P – 1) * (Q – 1) = 1
|
|
|
|
RSA加解密步驟
在加密中，從明文 PT 計算密文 CT CT = PTE mod N
將密文 CT 寄給接收方
在解密中，從密文 CT 計算明文 PT PT = CTD nod N
|
|
|
|
範例(步驟1, 2)
選擇兩個大質數 P 和 Q P = 47, Q = 71
計算 N = P * Q N = 47 * 71 = 3337
|
|
|
|
範例(步驟3)
選擇公開金鑰 E，使它不是一個 (P – 1) 和 (Q – 1) 的因數 (47 – 1) * (71 – 1) = 46 * 70 = 3220 3220 的因數為 2, 2, 5, 7, 23 3220 = 2 * 2 * 5 * 7 * 23 選擇 E 不包含上述因數 Ex: 4 (含2), 15 (含5), 14 (含2, 7), 69 (含23)不可選 E = 79
|
|
|
|
範例(步驟4)
選擇私密金鑰 D，使下列的恒等式為真 (D * E) mod (P – 1) * (Q – 1) = 1 在恆等式替換 E = 79, P = 47, Q = 71 (D * 79) mod (47 – 1) * (71 – 1) = 1 (D * 79) mod (46 * 70) = 1 (D * 79) mod 3220 = 1 經過計算 D = 1019 (1019 * 79) mod 3220 = 80501 mod 3220 = 1
|
|
|
|
|
|
Comments