RSA加密逐步模拟器

什么是 RSA 加密？

RSA（Rivest-Shamir-Adleman）是最早的公钥加密系统之一，由 Ron Rivest、Adi Shamir 和 Leonard Adleman 于 1977 年发布。与对称加密（使用相同的密钥进行加密和解密）不同，RSA 使用一对密钥对：任何人都可以使用的用于加密数据的公钥，以及只有所有者才能使用的用于解密数据的私钥。

RSA 的数学安全性建立在大整数分解问题的基础上：将两个大质数相乘非常简单，但将它们的乘积分解回质数在计算上对于足够大的数字来说是不可行的。

RSA 密钥生成的工作原理

RSA 密钥生成过程涉及五个基本步骤：

• 步骤 1 – 选择质数： 选择两个不同的、较大的质数 p 和 q。质数越大，密钥越安全。
• 步骤 2 – 计算模数： 计算 n = p × q。n 的位长度决定了密钥大小（例如 2048 位）。
• 步骤 3 – 欧拉函数： 计算 φ(n) = (p−1)(q−1)。此值对于选择 e 和计算 d 至关重要。
• 步骤 4 – 公钥指数： 选择 e，使得 1 < e < φ(n) 且 gcd(e, φ(n)) = 1。标准选择通常为 65537。
• 步骤 5 – 私钥指数： 使用扩展欧几里得算法计算 d，使得 d × e ≡ 1 (mod φ(n))。

扩展欧几里得算法

计算私钥指数 d 需要找到 e 关于模 φ(n) 的模反元素。扩展欧几里得算法通过扩展标准 GCD 算法，不仅能找到最大公约数，还能找到系数 x 和 y，使得 a·x + b·y = gcd(a, b)。

当 gcd(e, φ(n)) = 1 时，该算法会得出 x，使得 e·x ≡ 1 (mod φ(n))，从而得到 d = x mod φ(n)。

RSA 安全性考量

• 密钥大小： 现代 RSA 使用 2048 或 4096 位密钥。此模拟器中的小质数仅用于教学目的，可以被瞬间分解。
• 填充方案： 现实世界中的 RSA 实现使用填充（如 OAEP, PKCS#1）来防止针对原始 RSA 的数学攻击。
• 性能： RSA 比对称加密慢得多。在实践中，通常使用 RSA 加密一个随机的对称密钥，然后由该对称密钥加密实际数据（混合加密）。
• 量子威胁： 在足够强大的量子计算机上运行 Shor 算法可以高效地分解大数，从而威胁 RSA 的安全。后量子加密技术正作为对策在开发中。

RSA 的实际应用

• TLS/SSL (HTTPS)： RSA 用于握手阶段，以安全地交换对称会话密钥。
• 数字签名： RSA 通过使用私钥加密哈希值来签署文档，可使用公钥进行验证。
• 电子邮件加密： PGP 和 S/MIME 使用 RSA 来加密电子邮件通信。
• SSH 认证： RSA 密钥对为远程服务器访问提供无密码身份验证。
• 代码签名： 软件发行商使用 RSA 签署可执行文件，以证明真实性和完整性。

常见问题解答