Diffie Hellman 密鑰交換
目錄
1. 前情提要
2. Diffie Hellman
2-1 mod
2-2 密鑰交換
3. 美中不足
⦿ 前情提要
⦿ Diffie Hellman
⦿ mod
⦿ 密鑰交換
⦿ 美中不足前情提要
在網路溝通中，有兩件重要的事，一個是 Authentication，一個是 Authority，前者為身份驗證，後者為授權，前者例如登入的帳戶是不是在該網站註冊的，當帳號密碼輸入正確的話就可以登入，或者是後者由主流網站授權，藉第三方（主流網站）登入，一般登入僅需身份驗證，第三方登入則是身份驗證與授權都有。
當你連上一個新的網站，想藉由第三方登入時，通常都會跳出通知，來詢問是否願意將個人註冊資料給這個新的網站使用，或是切換某個已知第三方的帳戶來登入。
一般用戶登入時可以在別人的留言板留言，高級用戶登入時可以發文，這是授權；一般用戶可享商品 95 折的優惠，高級用戶可享商品 88 折的優惠，這也是授權，在現代網路架構下，有一個很重要的管理權限的方式叫做 RBAC，Role-based access control，以角色為基礎的存取控制，在公司帳戶下，開出許多使用者，有的使用者有某些權限，有的使用者有其他的權限，像是管理者、開發者、發佈者、測試用戶⋯⋯等，權限的管控其實相當不容易，如果開發者要具有發佈功能，卻又不讓他有發佈者的所有權限，例如下架，我們就會在開發者底下使用角色去管理，以角色限定權限（管理授權），想加入多種權限就加入多種角色，這邊就不細講。
回到網路溝通上，傳輸資料時必須要有身份驗證與加密，無論加密或身份驗證都需要所謂鑰匙（密鑰或公私鑰），鑰匙不只能用來做資料的加密，也可用來驗證身份，驗證身份中，以憑證（包含公鑰、CA 的簽名）來說，最終是希望獲取對方的公鑰，如何確定公鑰是對方的就要用到 hashing 了，而 hashing 後以私鑰加密就形成了簽名。
憑證與密鑰交換可以分別參考前面兩篇文章：
在第二篇有提到 RSA 與 AES 這兩個演算法，前者是非對稱加密，後者是對稱加密，在密碼學的應用中，不同的演算法有不同的用途，有的演算法只適合做密鑰交換，有的演算法只適合做身份驗證，RSA 都可以做，不過這篇文章再來講一個密鑰交換的演算法 —— Diffie Hellman。
繼續閱讀｜回目錄Diffie Hellman
密鑰是用來做資料加密的，但如何讓雙方使用同一組密鑰就得靠點技術，因為密鑰也可看作資料，它在傳遞時也可能被攔截，在安全的密鑰交換文章中，我們使用 RSA 來加密 AES 密鑰，解密後就可以拿來使用，但這個前提是密鑰對的公鑰是任何人都可以獲取，即便獲取也不會造成風險，因為用來加密的公鑰，僅有有私鑰的人可以解密，只是仍必須確認公鑰的所有者，但身份驗證可以幫我們解決這件事，即是證明公鑰來源是正確、未經竄改的。
Client 到 Server 的溝通過程是 TCP 交握 => Client 拿到憑證、驗證公鑰 => Client 產生密鑰以公鑰加密、Server 以私鑰解密得到密鑰 => 雙方以密鑰加密資料並傳輸。
Diffie Hellman 也是一種密鑰交換方式，不過在講 Diffie Hellman 之前，要先引入數學運算 —— mod（模數、同餘）。
mod
在算式五除以二餘一的表示為 5 ÷ 2 … 1，我們寫成 5 mod 2 為 1，5 是被除數，2 是除數，1 是餘數，而除以 2 同樣餘 1 的情況，我們稱之為同餘，7 mod 2 為 1，而 5 mod 2 跟 7 mod 2 相等，最後寫成 5 ≡ 7 (mod 2)，表示 5 跟 7 分別除以 2 得到同樣的餘數（同餘）。
然而，1 除以 2 的餘數也為 1，我們也可寫成 5 ≡ 1 (mod 2)、7 ≡ 1 (mod 2)、9 ≡ 1 (mod 2)、11 ≡ 1 (mod 2)⋯⋯，若仔細觀察在 ≡ 兩邊的數字相減後會被 2 整除，5 ≡ 7 (mod 2)、9 ≡ 7 (mod 2) 也是如此，這是模數運算的特性。
因為 a ≡ b (mod q) 時，令 a = mq + r；b = nq + r，a - b 就等於 (m-n)q，會被 q 整除，寫成 q | a - b，由此再往下推，已知 a ≡ b (mod q) ；c ≡ d (mod q) ，可得到q | a-b+c-d、q | ac - bd、q | a^n — b^n、q | ma - mb 等特性。
最後甚至可以導出 (a⋅b) mod n = ( (a mod n)⋅(b mod n) ) mod n，即 a 與 b 相乘取模，等於 a 取模、b 取模相乘再取模。
密鑰交換
同樣是 Alice 跟 Bob 的情形，Alice、Bob 分別產生不交換的 private key，假定 Alice 的 private key 是 4；Bob 的 private key 是 5，如下：
除了各自產生的 private key，Alice 跟 Bob 還協議了兩個公開的數，一個是質數 13，一個是隨機數 6，以此來分別計算兩人的公鑰，也就是 13 跟 6 是用來做 Public Key 的算式：
Public Key = 6^private key (mod 13)
由此，Alice 算出 Public Key 為 9；Bob 算出 Public Key 為 2，公開流傳的有質數 13，與隨機數 6，但 Alice 跟 Bob 也要交換彼此的公鑰，所以 Bob 拿到 9，Alice 拿到 2，如下：
至此，再做一次次方及模數的運算：
(shared Public Key)^private key (mod 13)
shared 表示這是對方的 Public Key，於是 Alice 得到 3，Bob 也得到 3，這成了兩者的密鑰（Secret Key；Session Key），但從頭到尾，Alice 跟 Bob 只透露了一個質數、一個隨機數，以及透過質數、隨機數與私鑰做運算而得到的公鑰，這四個數，我們只要檢驗有了 13、6、2、9 的人，有沒有辦法在短時間內得出 3，如果不能，這個密鑰交換就足夠安全（比方說經過三萬年才算出來）。
我們再看一次 3 的算法，在 (shared Public Key)^private key (mod 13) 算式中，公開的數有 Public Key 跟 質數 13，Public Key 的算法是由 13 跟 6 以及 private key 而來，這也就是說我們必須要先推知 private key，才能有效地再推知 Session Key，若寫成未知數如下：
Session Key = ( g^b (mod p) )^a (mod p) = ( g^a (mod p) )^b (mod p) = g^ab (mod p)
這意味著 ( g^b (mod p) )^a、( g^a (mod p) )^b、g^ab 其實沒兩樣，即是 ( g^b )^a 跟 ( g^a )^b 等同於 ( g^b (mod p) )^a、( g^a (mod p) )^b，這是因為前段說的特性得出的結果。
實際上中間攔截的人會得到的是 p、g，以及 g^a (mod p)、g^b (mod p) ，以及 ( g^a (mod p) )^b (mod p)、( g^b (mod p) )^a (mod p)，但是由這些訊息並不能有效地獲取 a 跟 b（private key）以及最終的 Session Key。
而 Alice 跟 Bob 產生的 private key 4 跟 5，協議的質數 13，隨機數 6 都有了，最終要算的就是 6^4*5 (mod 13)，但 private key 並不會傳遞，所以 4*5 不會知道，算法用的是離散對數，即 Diffie Hellman 交換密鑰的精髓所在。
然而，中間人有了 13、6、2、9 真的沒辦法推出 4、5，最後是 3 嗎？ 6^a (mod 13) = 9，我們可以檢查 6¹、6²、6³、6⁴，檢查到 a = 4 時就得到 9 了，也就是 Alice 的 private key 被獲取，而且我們還知道 Bob 的 Public Key 為 2，所以 2^4 (mod 13) 為 3，也得到了 Session Key。
所以，Diffie Hellman 有一些限制，比方這個質數若是 300 位，Alice 跟 Bob 的 private key 各是 100 位，那麼以目前電腦便難以暴力法（Brute Force）算出 private key 跟 Session Key 了。
繼續閱讀｜回目錄美中不足
雖然 Alice 跟 Bob 在交換密鑰過程被攔截了部份資訊，但由這些資訊並不能有效得出 Alice 跟 Bob 的 private key，以及傳訊時加密用的 Session Key，看起來似乎很安全，不過，這並不能保證 Alice、Bob 一開始就有拿到對方的 Public Key，所以 Public Key 仍是中間人攻擊的對象。
若有 PKI（公鑰基礎設施）就可以確認公鑰來源，即是驗證簽名後，再行交換密鑰，最後才是加密資料並傳輸。
在實際密鑰交換的方法中，還有 ECDH（Elliptic Curve Diffie Hellman）這個方法，若進到量子電腦時代，我們已知離散對數的公式，仍可以有效破解 private key 以及 Session Key，因為量子電腦的閘與傳統電腦的邏輯閘是不同概念，因而衍生出不同的演算法，例如秀爾演算法。所謂的有效即解決了時間複雜度的問題，用更好更快的方式得出我們想要的結果。
在 Diffie Hellman 之後，RSA 就被發明出來，用作更安全的加密方法，將來若有機會再繼續研究 RSA 等加密方法，這次就分享到這，感謝您的閱讀。
繼續閱讀｜回目錄Reference：