RSA 的演算法核心（algorithmic core of RSA）
/ R-S-A /
RSA 是著名的公開金鑰機制，讓任何人都能用你公開發布的金鑰把祕密送給你，而只有你能用自己保留的私鑰讀取它。撇開協定細節，它的核心是一小段模算術的食譜：你選兩個大質數，導出一個公開指數與一個私密指數，於是加密與解密各是一次模冪。它之所以安全，靠的是兩個計算問題之間的落差——把質數相乘很容易，但把它們的乘積分解回去被認為很難。
算術核心如下。(1) 選兩個大質數 p 與 q（用米勒-拉賓找到），令 n = p*q。(2) 算 phi = (p-1)*(q-1)。(3) 選一個與 phi 互質的公開指數 e（常用 65537）。(4) 用擴展歐幾里得演算法把私密指數 d 算成 e 對 phi 的模反元素——故 e*d = 1 mod phi。公鑰是 (n, e)；私鑰是 d。要加密訊息 m（一個小於 n 的數），用快速模冪算 c = m^e mod n。要解密，算 m = c^d mod n。解密能還原訊息，是因為 (m^e)^d = m^(e*d) = m mod n，這由 e*d = 1 mod phi 連同關於模 n 指數的歐拉／費馬定理推出。你需要的每一步——產生質數、求反元素、取冪——都是本欄目中的數論演算法，這正是為何 RSA 是它們完美的收尾之作。
它的安全性建立在一個誠實的不對稱上，而這點必須謹慎陳述。計算公鑰很容易，而一個能把 n = p*q 分解成 p 與 q 的攻擊者，就能重算 phi、進而算出 d 並破解機制——所以 RSA 的安全取決於「以已知演算法分解大數不可行」。那是一個被相信的困難性假設，而非已證明的定理：沒有人發表過快速的古典分解演算法，但也沒有人證明它不可能，而一台跑秀爾演算法（Shor's algorithm）的大型量子電腦能有效分解、破解 RSA。本條只談算術核心；真實的 RSA 還需要填充方案與謹慎的金鑰處理，少了它們，教科書版本並不安全——切勿部署未加處理的教科書 RSA。
玩具 RSA：p=3、q=11、n=33、phi=(2)(10)=20。選 e=3（gcd(3,20)=1）。d = 3 模 20 的反元素 = 7（3*7=21=1 mod 20）。加密 m=4：c = 4^3 mod 33 = 64 mod 33 = 31。解密：31^7 mod 33 = 4，還原 m。每個運算都是一次模冪或一次模反元素。
金鑰來自質數與一次模反元素；加密／解密各是一次模冪。
RSA 的安全是一個困難性假設（分解 n 被相信很難），而非證明；且無填充的教科書 RSA 可被破解——僅有算術核心並不構成安全的密碼系統。