RSA 所使用的數學
此文節錄《碼書：編碼與解碼的戰爭》的附錄
此書提供了許多簡單易懂的技術描繪（可惜台灣沒有再版了）
如下是 RSA 加密與解密過程的數學描述：
一、愛麗絲挑選兩個巨大的質數 p 和 q。這兩個質數應該要非常龐大，不過，為了簡化說明，我們假設愛麗絲所挑選的是 p=17，q=11。這兩個數字必須保存好，不讓任何人知道。
二、愛麗絲把這兩個質數相乘，得到另一個數字 N。在此例，N=187。她又再挑一個數字 e，假設 e=7，數字 e 和數字 (p-1)×(q-1)必須互質，也就是說，它們不可以有共同的因數
三、愛麗絲公佈 e 和 N，這兩個數字一起，被稱為公開鑰匙（所選取的 e 值可以跟其他人的一樣，但 N 值必須是獨一無二的）
四、加密訊息時，必須先把訊息轉換成一個數字 M。例如，文字被轉換成 ASCII 二進位數字時，我們可以把這些二進位想成一個十進位數字。接著根據如下的公式，就可以把 M 加密成密碼文 C
|
1 2 |
C = M ^ e (mod N) |
五、假設巴伯想送愛麗絲一個吻，就單單一個字母 X。X 的 ASCII 碼是 1011000，換算成十進位數字是 88，因此 M=88
六、巴伯查詢愛麗絲的公開鑰匙，發現 N=187, e=7。這兩個數字等於提供了他加密訊息給愛麗絲所需的公式。套入公式：
|
1 2 |
C = 88 ^ 7 (mod 187) |
用電子計算機運算這個式子反而費事，因為它的顯示版容不下這麼大的數字。事實上，模算術的指數函數有一個計算訣竅：
|
1 2 3 4 5 |
88^1 = 88 = 88 (mod 187) 88^2 = 7,744 = 77 (mod 187) 88^4 = 59,969,536 = 132 (mod 187) 88^7 = 88 × 77 × 132 = 894,432 = 11 (mod 187) |
巴伯把密碼文 C=11 寄送給愛麗絲
七、我們知道模算術裡的指數函數是單向函數，要從 C=11 逆向求出原始訊息 M 是非常困難的事。所以，依芙沒有辦法解譯這則訊息。
八、愛麗絲可以解譯這則訊息，因為她有特別的資訊：她知道 p 和 q 的值。她會利用下面的公式計算出一個 d 值，即她的私人鑰匙：
|
1 2 3 4 5 |
e×d = 1 (mod (p-1 ×(q-1))) 7×d = 1 (mod 16×10) 7×d = 1 (mod 160) d = 23 |
d 值的演算並非輕而易舉的工作，不過一種稱為歐基里德演算法的技巧可以幫愛麗絲又快又簡單地求出 d 值
九、愛麗絲利用下面的公式解譯訊息：
|
1 2 |
M = C ^ d (mod N) |
|
1 2 3 4 |
M = 11 ^ 23 (mod 187) M = 11 × 121 × 55 × 154 (mod 187) M = 88 = X in ASCII |
瑞維斯特、薛米爾和艾多曼創造了一個特殊的單向函數，只有持有特別資訊（p 和 q）的人才能求回原值。每個人都挑選不一樣的 p 和 q，等於把這個函數個人化，任何人都可以用 N 值加密訊息，但只有知道 d 值的人可以解密訊息