RSA 加密

一種 公鑰密碼學 演算法，它使用 素因數分解 作為 陷門單向函式。定義

(1)

對於 和 素數。 還要定義一個私鑰 和一個公鑰 使得

(2)

(3)

其中 是 尤拉函式, 表示 最大公約數 (所以 意味著 和 是 互質), 並且 是一個 同餘。 令訊息被轉換為數字 。 然後傳送者公開 和 併發送

(4)

為了解碼，接收者（知道 ）計算

(5)

因為 是一個 整數。 為了破解程式碼，必須找到 。 但這需要因式分解 因為

(6)

應該選擇 和 ，使得 和 可以被大的 素數 整除，否則 Pollard p-1 因式分解方法 或 Williams p+1 因式分解方法 可能會很容易地分解 。 最好 也很大並且可以被大的 素數 整除。

如果 的單元具有小的 域階 (Simmons 和 Norris 1977, Meijer 1996)，則有可能透過重複加密來破解密碼系統，其中 是 0 到 之間的 整數環 在加法和乘法下 (模 )。Meijer (1996) 表明，對於以下 形式 的因子，幾乎每個加密指數 都是安全的，不會透過重複加密被破解

			(7)
			(8)

其中

			(9)
			(10)

並且 , , , , , 和 都是 素數。 在這種情況下，

			(11)
			(12)

Meijer (1996) 還建議 和 應該具有 階數。

使用 RSA 系統，可以在不洩露其私有程式碼的情況下，將傳送者的身份識別為真實的。