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 系统，可以在不泄露其私有代码的情况下，将发送者的身份识别为真实的。