RSA公鑰密碼淺介

美國電腦學者艾得曼 (Leonard Max Adleman, 1945- )

(照片取自「Wikipedia」 http://en.wikipedia.org/wiki/Len_Adleman)

美國密碼學家李維斯特 (Ronald Linn Rivest, 1947- )

(照片取自「Wikipedia」 http://en.wikipedia.org/wiki/Ron_Rivest )

 

傳統的加密方法,發訊息者 (Sender) 會把明文 (Message) m (在計算機環境下通常為 0 或 1 的序列) 通過一加密 (Code) 運算

c = Ek(m)

變成密文 c,之後發給收訊息者 (Receiver),收訊息者接到密文 (Code) c 之後,利用解密 (Decode) 運算

m = Dk(c)

得到明文 m。這裡的 k 我們稱是一個鑰 (Key),即雙方協同的加密運算參數。

但現在網絡用戶繁多,相互之間的業務關係也不固定,要不斷協定不同的密鑰,大不方便。再加上加密和解密同用一條密鑰,也易被別人洞破。

在 1975年,美國密碼學家迪菲 (Bailey Whitfied 'Whit' Diffie 1944 - ) 和電子工程師赫爾曼 (Martin E. Hellman 1945 - ) 提出了一個新的密碼學概念:即公鑰 (Public Key) 的概念。所謂公鑰概念,即每個用戶有兩條鑰匙,一為公開 (稱公開鑰),一為私有 (稱秘密鑰),而且其他用戶很難從其公鑰去推算其私鑰。看來很不錯的理論,可惜當時只不過是一空談而已,如何把它落實呢?

美國麻省理工 (Massachusetts Institute of Technology) 的美國密碼學家 (Cryptographer) 李維斯特 (Ronald Linn Rivest, 1947- )、以色列密碼學家夏米爾 (Adi Shamir, 1952- ) 及美國理論電腦科學家 (Theoretical Computer Scientist) 艾得曼 (Leonard Max Adleman, 1945- ) 在 1978年發表了《數字簽名和公鑰密碼的一個方法》一文中,提出了一個公鑰密碼的方法,我們把他們的姓氏的首個英文字母密碼的名稱,即現稱的 「RSA公鑰密碼」(RSA Encryption Public-key Cryptograpy)。

到底什麼是「RSA公鑰密碼」呢?看看吧!

成立一密鑰分發中心,一個用戶如要使用密碼,就到該中心領取密鑰。密鑰分發中心選用一個正整數 N= pq,這裡的 p 和 q 分別是兩個很大的素數。 N 是公開的,而其素因子分解式 (Prime Factorization, 即 p*q ) 則保密。 我們知道

j(N) = (p-1) (q-1)

人們若不知 p 和 q ,則無法計算 j(N) 了。

當一個用戶來中心領取密鑰時,中心給他選一個正整數 e,e 小於 j(N) 且與它互素 (Coprime)。我們利用輾轉相除法 (Method of Successive Division) ,可以找到正整數 d 和 x ,使

  ed + xj(N) = 1

ed = 1 (mod j(N))

e 作為該用戶的公開鑰, d 則是該用戶的秘密鑰。

只要知道了該用戶 (收方) 的公開鑰 e 和 N ,任何人 (發方) 都可化向他發加密 (Coding) 明文。設明文 m < n,且 m 與 N 互素 (m 與 N 不互素的情況,出現可能性極小)。發方利用 e 和 N 將明文加密成 c:

c = me (mod N)

發方再把密文 c 經一公開通道傳給收方,收方接到密文 c 後,便可利用其秘密鑰 d 進行解密 (Decoding):

cd = med = m1-xj(N) = m*(mj(N))-x (mod N)

根據歐拉定理 (Euler Theorem),若 (k,m) = 1 則有 kj(m) = 1 (mod m)。

故得 cd = m (mod N) ,得回明文。

由於其他人 (包括發方) 也不知道 d 的數值,故無法自行解密。

要破解 RSA公鑰密碼的方法,在於得悉當中的 j(N) ,故「大數分解」亦成為破解此密碼的關鍵;另一方面尋找得到更大的素數便是保密成功與否的要素。(詳見另文《RSA數》) 因此各大國在尋找新且更有效的分解方法和更大的素數上投放更多資源,更有不少私人機構以獎金鼓勵大眾進行「大數分解」或打破素數的最大紀錄。這無疑是加速了素數或數論研究的發展。雖然偷看別人私密是要不得的事情,但誰也估不上這和數學連上關係。

 

參考文獻及網址:

Wikipdeia. "Adi Shamir." http://en.wikipedia.org/wiki/Adi_Shamir.

Wikipedia. "Leonard Aldeman." http://en.wikipedia.org/wiki/Len_Adleman.

Wikipedia. "Ron Rivest." http://en.wikipedia.org/wiki/Ron_Rivest.

Wikipedia. "RSA." http://en.wikipedia.org/wiki/RSA.