Birkhoff's Blog

Thoughts and technonogies.

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

Birkhoff Lee's Avatar May 27th 2016

今天抽空看了一下放在 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

下面我要開始講故事囉!

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

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

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

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

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

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 今天是一個極大質數,那麼這個過程就很難逆運算回去!