RSA 陷門置換（RSA trapdoor permutation）是 RSA 加密與簽章背後的核心演算法。

給定模數 n 與一個稱為公開指數（public exponent）的數 e，RSA 陷門置換把集合 Zn* 中的數 x 變換成：

y = x^e mod n

也就是計算 x 與自己相乘 e 次再對 n 取模。

用 RSA 陷門置換加密時，模數 n 與指數 e 構成 RSA 公鑰。

陷門：秘密指數 d#

要從 y 取回 x，我們用另一個數 d：

y^d mod n = (x^e)^d mod n = x^(ed) mod n = x

由於 d 是讓我們能解密的陷門，它是 RSA 金鑰對中私鑰的一部分，而且與公鑰不同，它必須永遠保密。

d 也稱為秘密指數（secret exponent）。

d 是怎麼來的#

d 顯然不是隨便一個數。它必須滿足「e 乘上 d 等價於 1」，從而使 x^(ed) mod n = x 對任何 x 成立。更精確地說：

ed = 1 mod φ(n)

這樣才能得到 x^(ed) = x¹ = x，正確解密訊息。

為什麼這裡是對 φ(n) 而非對 n 取模？

因為指數的行為像 Zn* 中元素的索引，而不像元素本身。既然 Zn* 有 φ(n) 個元素，索引就必須小於 φ(n)。

φ(n) 是安全性的關鍵#

因此 p 與 q 也必須保密，因為知道 p 或 q 就能藉由計算 (p − 1)(q − 1) 得到 φ(n)。