RSA的例子（一）

有讀者對我的一系列有關《非對稱密鑰》的文章作出了提問，他覺得很神奇，但又很難明白，希望可以有些具體例子．

這是非常真確的，數學和電腦科學家，看到公式便會明白．正如我說過，看懂RSA並不難，難就難在如何想出來．最近我有興趣聽一個有關‘神秘學’的網台節目，這個節目的水平已算不錯，可是，一說到密碼學，也真是‘神秘化’了．這也說明了我們今天的教育，對抽像思維的訓練實在十分有限，數學教育也要講應用，講具體，但真正的嚴格‘理性’訓練便欠奉了．既然，有讀者這麼有興趣提問，我也嘗試舉一個實例以說明之．但由於真實的操作要處理非常大的數字，完全超越一般計算程式的範圍，例如，不要想以Excel計算，這是不可能的，我就以RSA可以使用的最小數字舉例，但這樣小的數字根本毫不保密，實際的數字是最少都有300位以上的！

第一步，選兩個質數（prime），實際運作，這兩個數要在300位以上，想像一下，一百萬就是最小的7位數，300位數有多大！？

把這兩個質數命名為p及q，我們就選11和3
p=11, q=3

然後，計算n=pq
n = pq = 11.3（註） = 33

然後，計算phi = (p-1)(q-1)
phi = (p-1)(q-1) = 10.2 = 20

在這裏，先停一停，大家請再想像一下，兩個300位的數相乘，又會是多少位呢？n和phi又會是多大呢？

現在，我們要選一個數e，而gcd(e, phi) = 1．
gcd就是最大公因數（greatest common divisor），我們選e=3．
gcd(3, 20) = 1

在繼續前，我要介紹一個一般人比較少用的算術操作，這就是mod，例如5 mod 3的意思就是把5除3的餘數，這即是2．又例如，6 mod 7 = 6，又例如13 mod 7也是6，明白了嗎？

好！現在我們要找出一個d，而令 ed mod phi = 1

我們有方法去找出這個d，但現在先不說如何找，我們找到d=7

你可驗證一下，3.7 = 21
21 mod 20 = 1

所謂密鑰和公開鑰就是(n,e)和(n,d)
即是(33,3)和(33,7)，再一次，那個是‘公開’，那個是‘密’並不重要，總之，就是公開一個，留著一個！

假設你留下(33,3)為密鑰，而把(33,7)公告天下，當你要加密訊息時，你就使用這公式

m’ = m^e mod n

再繼續前，我又要先作點解釋，不論你要加密的訊息是語言文字又或資料檔案甚至是多媒體訊息，這都與加密的算法無關，對加密的算法而言，一切都祗是數字，不論你的訊息內容是甚麼，都是要先要經編碼步驟，編成數字，而加密就是把這些數字改換成另一個數字，而解密，就是把這個數字還原．

好，我們就拿一個數字來舉例罷，例如你要加密8
m’ = m^e mod n
=8³ mod 33
= 512 mod 33
= 17

這就是8經加密後便會變成17

那麼，又如何解密呢？其實，解密的公式和加密的公式完全一致，祗是換了‘公開鑰’而已．這就是
m’ = m^d mod n
即是把e換了d而已，我們若要把17解密，就如下
m’ = m^d mod n
=17⁷ mod 33
= 410338673 mod 33
= 8

等等，17⁷這不是很大嗎？是的，但這個範圍，一般的計算程式如Excel還總算可處理，但實際的d和e最少也有幾百位，真是自乘這麼多次嗎？不可能！？不論電腦有多快，這都不可能，下文再介紹我們是如何計算這個數的！除這以外，還有很多其他細節需要說明．

在告一個段落前，你可以看到，RSA就是巧妙地找出一對d和e，以d加密的，便要用e解密，反之亦然！而找出d和e的關鍵就是要知道p和q，而n就是pq，就以本例而言，33就祗可以是11.3，一眼便可看出，這便是factorization，所以，本例毫無保密性可言．RSA的保密性所在，就是n少說也有600位，我們就是還未有已知的方法可以有效factorize這樣大的數，若有，互聯網上便全無秘密可言了．

下文再續！

註：11.3並不是小數，而是11乘3，這是代數慣用的寫法．