鑽石舞台

Bob 和 Alice 通常需要在一個不安全信道交換敏感信息。在第二章中，我們已經了解了 一些基於解決離散對數問題困難度的方法。在本節中，我們將介紹 RSA公鑰密碼系統，它是最早發明的，也是最著名的公鑰密碼系統。RSA 是以其（公開）發明者：Ron Rivest, Adi Shamir, 和 Leonard Adleman 姓氏命名的。

RSA 的安全性取決於以下 dichotomy：

表3.1總結了RSA公鑰密碼系統：Bob 的密鑰是一對大素數。他的公鑰是一對，，其中，和互素。Alice 將其明文轉換為 1 到之間的整數。然後計算加密得到密文。

雖然 Alice 將密文發送給 Bob。而對於 Bob 來說，解同餘式然後恢復 Alice 的消息是簡單的，因為 Bob 知道的因子。而對於敵手 Eve 來說，儘管他可能中途攔截獲取了密文消息，但是由於他不知道的分解，因此他也很難解出同餘式從而破獲 Alice 發給 Bob 的秘密消息。

例 3.9接下來我們用一個小的例子來說明 RSA公鑰密碼系統。當然，這個例子並不安全，因為用的數字很小，所以 Eve 能夠很容易的將的因子計算出來。安全的 RSA 密碼系統需要使用具有數百位比特的模數。

RSA Key Creation

RSA Encryption

RSA Decryption

解得

解得 Alice 得明文消息

注 3.10Bob 的公鑰對，其中被稱為模數，稱為加密指數。而 Bob 用來解密 Alice 消息的整數，且滿足

稱為解密指數。顯然，如果加密指數比較小，那麼加密過程就會比較快。同樣的，如果解密指數比較小，那麼解密過程也會更有效率。當然，Bob 沒法同時使得他們兩個都很小，因為他只能指定其中一個，另外一個是根據同餘式 3.4 計算出來的（當然這也不是嚴格正確的，Bob 可以同時使得，但是這就意味着明文和密文一致了。）

注意到 Bob 也不能選擇，因為需要和互素，所以最小只能選擇，就目前而言，取 3 和比起取其他更大的值還是一樣安全的。對於那些想要快速加密，但是又擔心太小的人，通常採用，因為通過1.3.2一節中描述的平方和乘法算法，計算只需要進行16次平方運算和一個乘法運算。

對於 Bob 來說，另外一個選擇是選擇一個比較小的，然後根據同餘式計算公鑰，那麼應該會很大。然而，事實證明，這可能會導致 RSA 不安全。更準確地說，如果，那麼根據連分數理論 Eve 就能夠破解RSA。

注 3.11Bob 的公鑰對包括模數, 其中是兩個秘密素數。通過命題 3.5 我們知道，如果 Eve 知道的值，那麼它可以輕易的解決，並解密發送給 Bob 的消息。

我們展開得到

Bob 已經公開了 N，因此如果 Eve 能夠知道的和，那麼根據式子 3.5，就可以計算出能夠解密消息的了。

事實上，如果 Eve 知道了和的值，那麼他也能很輕易的計算出來。只需要找到二次多項式

的根就好了。注意到這個多項式可以合併為，所以就是這個多項式的根。因此如果 Bob 公開了的值，對於 Eve 來說，找到的值並不比找到本身來說更容易。

接下來我們通過一個例子來說明，如果 Eve 知道

首先它根據式計算

然後他就可以用二次多項式來進行分解

因此得到

注 3.12最後一個非常重要的點。我們已經證明，Eve 計算出的值並不比分解簡單，但這並不能證明 Eve 為了解密 Bob 的信息必須分解。重點是 Eve 真正需要做的是解決形為同餘方程（即在模求的次根）。可以想象，也許有一種有效的算法可以在不知道的值的情況下求解此類同餘方程，不過暫且還沒有人知道這種方法的存在。儘管求模下的次根可能比分解要容易，詳情請參見 D. Boneh, R. Venkatesan, Breaking RSA may not be equivalent to factoring (extended abstract), in Advances in Cryptology—EUROCRYPT 』98, Espoo. Volume 1403 of Lecture Notes in Computer Science (Springer, Berlin, 1998), pp. 59–71