RSA 非对称加密：公钥加密、私钥解密
什么是RSA非对称加密
RSA是目前应用最广泛的非对称加密算法，由Ron Rivest、Adi Shamir和Leonard Adleman于1977年提出，其名称取自三位发明者姓氏的首字母。它的核心思想是“加密与解密使用不同密钥”，一把是可以公开的公钥，用于加密；另一把是必须严格保密的私钥，用于解密。这种机制天然解决了对称加密中密钥分发难的问题，成为数字签名、安全通信和身份认证的基石。
RSA算法背后的数学基石
RSA的安全性建立在大整数因数分解的困难性之上。理解RSA需要先掌握几个基础数学概念。
互质关系
如果两个正整数的最大公约数为1，它们就称为互质。例如15和32互质，而15和21不互质（公约数3）。欧拉函数φ(n)正是用来统计不超过n且与n互质的正整数个数。
欧拉函数φ(n)
- 若n为质数p，那么φ(p) = p-1，因为1到p-1的所有数都与p互质。
- 若n为两个不同质数p和q的乘积，则φ(n) = φ(pq) = (p-1)(q-1)。这是RSA密钥生成的核心。
模反元素（乘法逆元）
如果两个正整数a与n互质，一定存在整数b，使得：
ab ≡ 1 (mod n)
即ab除以n的余数为1。此时b称为a关于模n的模反元素。欧几里得扩展算法可用于高效求解b。
RSA密钥对的生成过程
密钥生成是RSA的第一步，也是整个算法严谨性的体现。
步骤一：选取两大质数p和q
为保证安全，实践中p和q建议为至少1024位长的随机大质数，且彼此不能太接近。这里我们记为p和q。
步骤二：计算n和φ(n)
n = p × q，n的二进制位数即为密钥长度。n将作为模数同时出现在公钥和私钥中。φ(n) = (p-1)(q-1)，φ(n)需要保密，它连接了公钥指数与私钥指数。
步骤三：选择公钥指数e
选择一个整数e，满足：1 < e < φ(n)，且e与φ(n)互质。常用的e值为65537（即2^16+1），它二进制表示中只有两个1，计算速度快，且通常与φ(n)互质。
步骤四：计算私钥指数d
d是e关于模φ(n)的模反元素，即满足：
e × d ≡ 1 (mod φ(n))
d可通过扩展欧几里得算法高效求得。d必须严格保密。
密钥对公布
- 公钥：(n, e)，可向任何人公开。
- 私钥：(n, d)，只有解密方持有。p、q、φ(n)在生成完密钥后应彻底销毁或严密保管。
RSA加密与解密操作
加密与解密本质上是模幂运算，过程简洁对称。
公钥加密
发送方使用接收方的公钥(n, e)对明文m（需满足m < n）进行加密：
密文 c ≡ m^e (mod n)
注意：明文m通常需要经过填充（例如PKCS#1标准）再转化为整数，不能直接对原始消息进行运算，以防止同态攻击。
私钥解密
接收方收到密文c后，使用自己独有的私钥(n, d)还原明文：
m ≡ c^d (mod n)
解密正确性的数学保证来自欧拉定理：若m与n互质，则有m^φ(n) ≡ 1 (mod n)。由于e·d = 1 + k·φ(n)，代入可得：
c^d ≡ (m^e)^d ≡ m^(e·d) ≡ m^(1 + k·φ(n)) ≡ m·(m^φ(n))^k ≡ m (mod n)
即使m与n不互质，这一结论仍然成立（可通过中国剩余定理证明）。
动手实践：一个小数值示例
为直观展示流程，我们用极小的素数模拟（实际应用绝不能使用此规格）。
生成密钥
- 选择质数 p = 61, q = 53
- n = 61 × 53 = 3233
- φ(n) = (61-1)×(53-1) = 60×52 = 3120
- 选取 e = 17（与3120互质）
- 计算 d：满足 17×d ≡ 1 mod 3120，得 d = 2753
（验证：17×2753 = 46801，46801 ÷ 3120 = 15 余 1）
公钥：(n=3233, e=17)
私钥：(n=3233, d=2753)
加密过程
假设明文为 m = 65（实际应用中m会经过填充并远小于n）
c = 65^17 mod 3233
逐步计算：65^2=4225，4225 mod 3233 = 992，继续幂次组合可得：
65^17 mod 3233 = 2790
密文 c = 2790。
解密过程
使用私钥对密文2790解密：
m = 2790^2753 mod 3233
经过复杂的模幂运算（或用快速幂取模算法），最终结果：
m = 65
为什么RSA难以被破解
RSA的安全性根基在于：从已知的n推算出p和q极其困难。虽然n是公开的，但对于一个足够大的合数（如2048位），目前没有经典计算机能在有效时间内完成因数分解。一旦p和q泄露，攻击者就能算出φ(n)，并迅速求出私钥d。因此，保护私钥本质上就是保护大数分解的秘密。
其他攻击面与防范
- 质数选择不当：若p和q太接近或来自弱随机数发生器，可通过费马分解法等攻击。生成质数应使用可信的密码学安全伪随机数生成器（CSPRNG）。
- 小e攻击：e过小且明文也不大时，c = m^e可能直接小于n，无需模运算就能开e次方根得到m。采用标准e=65537并结合填充即可避免。
- 侧信道攻击：通过计时、功耗分析等物理手段获取私钥信息。需要库实现侧信道防护。
- 量子威胁：Shor算法理论上可在多项式时间内分解大整数，但实用量子计算机尚未成真。后量子密码正在成为研究方向。
RSA的实际应用场景
RSA并非用于直接加密大量数据，因其速度慢且密文长度等于模数n。实际中它主要扮演“安全握手”角色。
数字信封（混合加密）
在HTTPS等协议中，客户端用服务器公钥加密一个临时的对称密钥，服务器用私钥解密得到该密钥，后续通信使用对称加密（如AES）保护。这样既发挥了RSA的密钥分发优势，又避开了性能短板。
数字签名
发送者用自己的私钥对消息摘要进行“加密”，产生签名；接收者用发送者公钥“解密”验证完整性。实际上是签名 s ≡ m^d mod n，验证 m ≡ s^e mod n。RSA签名广泛用于软件分发、文档认证。
密钥交换
部分协议直接借助RSA传输共享秘密，但为了前向安全性，现代TLS更倾向使用ECDHE等临时密钥协商，RSA多用于身份认证。
常见误区与要点回顾
- 公私钥都能加解密，但方向不同：公钥加密、私钥解密用于机密性；私钥“加密”（签名）、公钥“解密”用于认证性。
- RSA不能处理任意长度消息：每次可加密的明文长度取决于模数n和填充方案，如RSA-2048配合OAEP填充，实际可加密长度约为214字节。
- 不要自己实现RSA原语：推荐使用经过验证的密码库（如OpenSSL、Bouncy Castle），因为它们处理了填充、随机数、侧信道防护等复杂细节。直接使用裸RSA（即教科书式RSA）是危险的。
通过本教程，你已掌握RSA从数学原理到密钥生成、加解密操作及安全实践的完整知识体系。下一步可结合OpenSSL生成真实密钥对，并尝试用编程语言调用成熟接口完成一次混合加密通信练习。