Science Focus ( Issue 21)

而RSA 則是非對稱式加密（asymmetric cryptography） 或公鑰加密（public key cryptography）的一員。在對稱 式加密（symmetric cryptography）中，為訊息加密和解 密用的金鑰是一樣的；但是 RSA 用上公鑰（public key） 和私鑰（private key）兩把不同的金鑰 — 即是鎖上箱子 用的鑰匙並不是解鎖的那把！加密和解密用上兩把不同鑰 匙似乎難以用直覺理解，但RSA其實只依靠兩個基本概念： 質數和模算數（modular arithmetic）。 質數是大於一而除了一和自己外，無法被其他自然數整 除的數。它們本身就非常有趣，亦是我們曾經在第二十期討 論過的課題之一。質數可以是任意大的：我們已知能寫出來 的質數之中，最大的一個有多達 24,862,048 個數位。RSA 加密演算法就是利用因數分解通常是極費時這一點，即使 擁有強大電腦力量的人亦然，因此要把加密內容破解往往 需要花上不合理的電腦力量，令人敬而遠之（註二）。 另一個重要的概念是模算數。那基本上和從時鐘看時 間差不多，在 24 小時制裡，我們會以「時間模 24（time modulo 24）」來描述小時 — 23:00 後的三個小時是 02:00，而不是 26:00（註三）。模算數的原理基本上就是 除數：要得出 n mod a ，基本上就要把 n 除以 a 約干次， 直至商數比 a 小，得出的餘數就是我們要找的值。 理解了這兩個概念後，要明白 RSA 加密演算法其實不 太難，在此我們會逐步解釋 [1]。 我們首先選兩個質數作示範，例如 p = 11、 q = 13。把 它們相乘，得出公鑰 n = 143。（在現實世界中這些質數都 極為龐大，現在建議的是 2048 位元（註四）。可是為了編 輯的身心健康著想，我們這次選了比較小的數值！）我們也 要選一個與 10（即 p – 1）和 12（即 q – 1）沒有共同因數 （互質）的數字 e ，這次我們選 e = 7。每個人選的 n 都不同， 而 e 和 n 就是剛才提到的公鑰，它們被發表在一個公開的 目錄中，當傳送訊息給別人的時候，電腦可以使用目錄中的 公鑰。 假設 Cliff 想給我傳一個非常簡單的訊息，越簡單越 好 — 「Hi」。一如所料，如果你要電腦工作，就要先把英 文字母轉成數字。很感恩，我們已經有一套這樣的系統 — 美國資訊交換標準代碼（American standard code for information interchange/ASCII），它可以將英文字母 變成 7 位元的數字。在 ASCII 中「H」的代碼是 72，而「i」 的代碼是 105。 要把字母「H」加密，Cliff 要找出我的公鑰。他從目錄 得知 n = 143、 e = 7。加密後的文字由公式 c = T ^ e (mod n ) 得出，我們的第一個字母是 T 1 = 72，經加密後會變成 c 1 = 72 ^ 7 (mod 143) — 這看起來很棘手，絕不是人手可 以計算的，但我們可以借助電腦的力量 — Google 一下便 可以得出 c 1 = 19 (mod 143)，所以我們第一個要傳送的 是 19。我們重複上述的步驟一次來加密「i」： c 2 = 105 ^ 7 (mod 143)，因此第二個數字是 c 2 = 118 (mod 143)。訊 息「Hi」也就變成了「19 118」。 對外人來說，解開加密訊息是不可能的，因為你不能從 已取模的數字還原本來的數字；可是，我們比外人知道多兩 項資訊，就是 p 和 q 的數值。沒有了它們，你就要對 n 進 行因數分解，而現實上 n 的數值很大，分解往往極之費時。 解密的關鍵如下，我們先取 p - 1 和 q – 1 的最小公倍數 lcm (10, 12) = 60，解密的金鑰 d 能從方程式 1 = ( e x d ) mod (lcm ( p - 1, q - 1)) 得出。對我們而言，1 = (7 x d ) mod 60，所以 d = 43 — 這就是我們還原訊息的神奇密 碼了。最後經過解密的訊息 m 可以由方程式 m = c ^ d (mod n ) 得出。我們收到了兩個字母，所以要把它們分開解密：第 一個字母是 19 ^ 43 (mod 143)，等於 72 (mod 143)，亦 即是字母「H」；同樣地，字母「i」來自 118 ^ 43 (mod 143) = 105 (mod 143)。這些計算看似涉及天文數字，但對電 腦來說其實輕而易舉。此外，有了 d ，你以後可以還原 Cliff 給你的每一條訊息（註五）。 RSA加密法之所以會成功，是因為數論中的費馬小定理 （Fermat’s Little Theorem）— 就是那個費馬，可是這 並不是把數學家弄得焦頭爛額的費馬最後定理（Fermat’s Last Theorem）。費馬小定理乍看起來非常簡單：若 p 是 質數， a ^ p ≡ a (mod p ) （註六）。這可是 RSA 加密法的 關鍵，因為 RSA 常常需要取 p 次方的計算。費馬小定理的 證明需要花點筆墨才能解釋，但在維基百科也能輕易找到， 這裡我們就不介紹了。 現在 RSA 加密系統是用於加密少量訊息的預設選擇， 譬如用於加密對稱金鑰加密中的金鑰（註七）。現時已知最 大被成功因數分解的 n 有 250 個數位（829 位元），電腦