一、RSA 简介
RSA 是一种公钥密码体制，由罗纳德・李维斯特（Ron Rivest）、阿迪・萨莫尔（Adi Shamir）和伦纳德・阿德曼（Leonard Adleman）于 1977 年提出，算法名称由他们三人姓氏的首字母组成。与对称加密算法不同，RSA 使用不同的加密密钥与解密密钥，属于非对称加密方式。
RSA 涉及三个重要参数：n、e、d。其中，(n, e) 作为公钥可对外公开，(n, d) 则作为私钥由用户妥善保存。这里的 n 是两个大素数 p 和 q 的乘积，即 n = p * q；e 是一个满足 1 < e < φ(n) 且与 φ(n) 互素的整数，其中 φ(n) 是 n 的欧拉函数值，在 RSA 算法中，φ(n) = (p - 1) * (q - 1) ；d 是 e 关于模 φ(n) 的乘法逆元，即满足 e * d ≡ 1 (mod φ(n)) 。
二、算法原理
（一）费马小定理
若 p 为素数，对于任意整数 a，满足 a^(p - 1) ≡ 1 (mod p) 。该定理在 RSA 算法原理推导中起到了一定的铺垫作用。例如，当 p = 5，a = 3 时，3^(5 - 1) = 81，81 mod 5 = 1，符合费马小定理。
（二）欧拉定理
- 欧拉函数：对于任意给定的正整数 n，欧拉函数 φ(n) 表示小于等于 n 的正整数中与 n 构成互质关系的数的个数。在 RSA 算法中，若 n = p * q（p、q 为互质的素数），则有 φ(n) = φ(pq) = φ(p) * φ(q) ，且当 p 为质数时，φ(p) = p - 1，所以 φ(n) = (p - 1) * (q - 1) 。
- 欧拉定理与模反元素：若两个正整数 a 和 n 互质，则存在 a^φ(n) ≡ 1 (mod n) 。从这个等式可以推导出模反元素的概念，因为 a^φ(n) = a * a^(φ(n) - 1) ≡ 1 (mod n) ，所以如果两个正整数 a 和 n 互质，那么一定存在整数 b（这里 b = a^(φ(n) - 1) ），使得 a * b - 1 能被 n 整除，即 a * b 被 n 除的余数是 1，b 就是 a 关于模 n 的模反元素。在 RSA 算法中，求私钥 d 的公式为 d * e ≡ 1 (mod (p - 1) * (q - 1)) ，即 d 是 e 关于模 (p - 1) * (q - 1) 的模反元素。
（三）模运算
模运算与基本四则运算类似，但除法运算有所不同。其具有结合律、交换律、分配律等性质。同余的定义为：给定一个正整数 m，如果两个整数 a 和 b 满足 (a - b) 能被 m 整除，即 (a - b) mod m = 0，则称 a 和 b 对模 m 同余。在模 n 意义下，除法规则有所变化，除以一个数等价于乘以它的逆元。
（四）拓展欧几里得原理
对于互素的两个整数 e1、e2，可以通过拓展欧几里得算法求解满足 e1 * x + e2 * y = gcd (e1, e2) 的整数 x 和 y。在 RSA 算法中，计算 e 关于模 φ(n) 的乘法逆元 d 时，可以利用拓展欧几里得算法，此时 e1 = e，e2 = φ(n)，求解出的 x 即为 d（需确保 x 为正数，若为负数则通过模运算转换为正数）。
三、算法流程
图解版：
文解版：
（一）密钥生成
- 选取大素数 p、q：随机选取两个大素数 p 和 q，并严格保密这两个数。例如，假设选取 p = 17，q = 19（实际应用中 p 和 q 通常是非常大的素数）。
- 计算乘积 n、欧拉函数值 φ(n)：
- 计算 n = p * q ，在上述例子中，n = 17 * 19 = 323。
- 计算 φ(n) = (p - 1) * (q - 1) ，即 φ(323) = (17 - 1) * (19 - 1) = 16 * 18 = 288。
- 选取整数 e：选取一个整数 e，满足 1 <e < φ(n) 且 gcd (φ(n), e) = 1（即 e 与 φ(n) 互素）。例如，选取 e = 5（5 与 288 互素）。
- 计算乘法逆元 d：计算 d，使得 d * e ≡ 1 (mod φ(n)) 。这里利用拓展欧几里得算法，对于 e = 5，φ(n) = 288，求解 5 * d ≡ 1 (mod 288) ，通过计算可得 d = 173（因为 5 * 173 = 865，865 mod 288 = 1）。
- 生成密钥：
- 公开钥为 {e, n}，即 {5, 323}。
- 秘密钥为 {d, n}，即 {173, 323}。
（二）加密
加密时需将明文比特串进行分组，分组长度要小于 log₂n 。假设明文 m = 88（满足小于 log₂323 ≈ 8.34，即分组长度合理），对明文分组 m 进行加密运算，公式为 c ≡ m^e (mod n) 。代入 e = 5，n = 323，m = 88，计算可得 c = 88^5 mod 323 = 233，得到的 c = 233 即为密文。
（三）解密
对密文分组 c 进行解密运算，公式为 m ≡ c^d (mod n) 。将 c = 233，d = 173，n = 323 代入，计算可得 m = 233^173 mod 323 = 88，成功还原出明文。
四、安全性分析
RSA 的安全性主要依赖于大数分解的难度，即给定 n = p * q，要从 n 分解出 p 和 q 在计算上是非常困难的。目前尚未从理论上证明破解 RSA 就一定等同于进行大数分解，也没有证明破译 RSA 的难度与大数分解难度完全等价。但无论如何，分解 n 是攻击 RSA 的最直接方法。随着计算机计算能力的不断提升，为了保证 RSA 的安全性，需要选择足够大的 p 和 q，使 n 的长度足够长。例如，早期较短长度的 RSA 密钥已能被破解，如今通常推荐使用 2048 位甚至更长的密钥长度。同时，密钥生成过程中的随机数生成质量、p 和 q 的选取方式等也对 RSA 的安全性有重要影响。若随机数可预测、p 和 q 选择不当（如太靠近或 p - 1、q - 1 的因子太小等），都可能导致 RSA 被破解。
五、应用场景
RSA 广泛应用于现代通信加密、数字签名等领域。在通信加密中，发送方使用接收方的公钥对消息进行加密，接收方使用自己的私钥进行解密，保证了通信内容的保密性。在数字签名场景中，发送方使用自己的私钥对消息进行签名（对消息的哈希值进行加密），接收方使用发送方的公钥验证签名，确保消息的完整性和发送方身份的真实性。例如在网络支付、安全邮件传输等场景中，RSA 算法都发挥着关键作用，保障了信息的安全传输与交互。
六、总结
RSA 作为一种重要的非对称加密算法，其原理基于数论中的多个定理，通过巧妙的密钥生成、加密和解密流程，实现了安全的信息加密与数字签名功能。理解 RSA 算法对于掌握现代密码学知识、保障信息安全具有重要意义。同时，随着技术的发展，需持续关注 RSA 的安全性，不断优化参数选择与应用方式，以应对潜在的安全威胁。
