Update on 24 Mar 2021: 這篇文是小時候寫的，最近開始讀離散數學之後發現很多地方似乎有寫錯。這篇文涵蓋的其實只有模算術與 Diffie-Hellman key exchange。看看就好！建議一定還是要找專門的離散數學的教科書讀過一遍。
今天抽空看了一下放在 browser bookmark 裡面很久了的一個 youtube 影片，裡面用很易懂的方式解釋了 public key cryptography 的工作原理。不過最終還是有提到 modular arithmetic（模算術），於是去 Wikipedia 了解了一下並與朋友交流了一下，以下是整理出來的筆記
要理解 public key cryptography，有個前置技能要先點好，叫做 Modular Arithmetic
Modular Arithmetic #
Modular Arithmetic 就是俗稱的「模算術」、「模運算」。
設正整數 a, b, n 且滿足 (a - b) / n 為正整數，
則有：a ≡ b (mod n)，即 a % n = b
簡言之，正整數 a, b 之差的絕對值為正整數 n 的倍數。
如果 n 為一極大質數（如上百萬位），則這個過程是幾乎無法逆運算回去的（即通過 b 與 n 逆算出 a）。
Public Key Cryptography #
終於到正題了！如果你沒有理解上個小節的內容，你可以參閱 https://en.wikipedia.org/wiki/Modular_arithmetic
下面我要開始講故事囉！
從前從前，在忠孝國中的三年四班，有個小男孩叫做小明，有個正妹叫做小美，還有個八卦男叫做小強。
小明的位置在小強前面，小美坐在小強後面，簡單來說，他們在班上的座位是這樣的：
小明 ─── 小強 ─── 小美
今天上課時，小明要傳一封充滿甜言蜜語的小紙條給小美，要讓小強傳給小美，但是不想讓小強看到內容，該怎麼辦呢？
這時，小明先傳一張紙條給小美，內容是這樣的：
g = 3
p = 17
數學不好的小強打開來看，不知所云，還是傳給了小美。
接著，小明偷偷地記下了一個他自己隨機想好的數字，他選擇了 15。
於是，結合第一張紙條的內容，他算出了 (3 ^ 15) % 17 的結果──6，他把 6 寫在了小紙條上，然後讓小強傳給小美。
數學不好的小強打開來看，還是不知所云，仍然傳給了小美。
接著，小美記下了小明給他的 6 這個數字，然後也做了跟小明一樣的事情，這裡她選擇了 13。
接著，她用第一張紙條預先約定好的 g ── 這裡是 3，與預先約定好的 p ── 這裡是 17，計算出 (3 ^ 13) % 17 的結果──這裡的結果是 12，她把 12 寫在小紙條上，透過小強傳給了小明。
於是，除了第一張紙條外，三個人目前分別有這些數字（假設小強有記下這些數字）：
- 小明：
- 15：自己放在心裡，沒有別人知道的隨機數字
- 12：剛剛小美傳給他的數字
- 小強：
- 6：小明計算後傳給小美的數字
- 12：剛剛小美計算後傳給小明的數字
- 小美：
- 13：自己放在心裡，沒有別人知道的隨機數字
- 6：小明傳給她的數字
接著，精髓部分來了！
小明這時將剛剛小美傳給他的數字 12 與自己的秘密數字 15 進行指數運算，即 12 ^ 15，再進行 % 17 的運算，也就是他計算出了這個式子：(12 ^ 15) % 17，這裡的結果是 10。
小美這時也將剛剛小明傳給他的數字 6 與自己的秘密數字 15 進行指數運算，即 6 ^ 13，再進行 % 17 的運算，也就是他計算出了這個式子：(6 ^ 13) % 17，==這裡的結果也是 10！！==
我們把運算過程整個列出來：
(12 ^ 15) mod 17 = (6 ^ 13) mod 17
(3 ^ 13 ^ 15) % 17 = (3 ^ 15 ^ 13) % 17若要將其轉化為公式：
設小明的秘密數字為 x，小美的秘密數字為 y，可以得到：(g ^ x mod p) ^ y mod P = g ^ x ^ y mod p = (g ^ y mod p) ^ x mod p = key
但是，因為雙方在通訊過程中根本沒有提到他們的秘密數字，因此小強根本就不知道 10 這個數字！不過，如果小強得到了兩個秘密數字中的其中任意一個，那小強就可以破譯他們往後的加密通訊內容了！
也就是說，現在兩人都有一個共享的金鑰，也就是我們今天的主題：public key cryptography 中的 public key！
因此，兩人之間的訊息可以透過現在小強不知道的 public key 10 進行一系列的加密演算進行加密！
你可能會想問：上面的運算都很簡單阿，那如果小強的數學好一點，這些計算豈不都白費了嗎？
沒錯。在上一小節我有提到──
「如果
n為一極大質數（如上百萬位），則這個過程是幾乎無法逆運算回去的（即通過b與n逆算出a）。」
也就是說，當這裡的 p 今天是一個極大質數，那麼這個過程就很難逆運算回去！