輕鬆理解 public key cryptography ─ 公開金鑰加密演算法

今天抽空看了一下放在 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 為一極大質數(如上百萬位),則這個過程是幾乎無法逆運算回去的(即通過 bn 逆算出 a)。

Public Key Cryptography

終於到正題了!如果你沒有理解上個小節的內容,你可以參閱 https://en.wikipedia.org/wiki/Modular_arithmetic 或來 #YSITD 問大家。

下面我要開始講故事囉!

從前從前,在忠孝國中的三年四班,有個小男孩叫做小明,有個正妹叫做小美,還有個八卦男叫做小強

小明的位置在小強前面,小美坐在小強後面,簡單來說,他們在班上的座位是這樣的:

小明 ─── 小強 ─── 小美

今天上課時,小明要傳一封充滿甜言蜜語的小紙條給小美,要讓小強傳給小美,但是不想讓小強看到內容,該怎麼辦呢?

這時,小明先傳一張紙條給小美,內容是這樣的:

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 為一極大質數(如上百萬位),則這個過程是幾乎無法逆運算回去的(即通過 bn 逆算出 a)。」

也就是說,當這裡的 p 今天是一個極大質數,那麼這個過程就是很難逆運算回去的喔!

總結

以上就是 public key cryptography 的運作原理,如有解釋不周或是有別的問題的,都歡迎在下方留言區詢問!