RSA算法简介

RSA（Rivest-Shamir-Adleman）是1977年由罗纳德·李维斯特、阿迪·萨莫尔和伦纳德·阿德曼提出的第一个实用的非对称加密算法。它基于大整数分解的困难性，是目前应用最广泛的公钥密码体制之一。

数学基础

RSA的安全性依赖于以下数论概念：

• 质数：只能被1和自身整除的大整数。
• 欧拉函数 φ(n)：对于n=pq（p、q为质数），φ(n)=(p-1)(q-1)。
• 模反元素：若ed ≡ 1 (mod φ(n))，则d是e关于模φ(n)的模反元素。
• 大整数分解：给定n，分解出p和q在计算上极其困难（当p、q足够大时）。

密钥生成步骤

1. 随机选择两个不相等的大质数p和q。
2. 计算n = p × q。n的长度即为密钥长度（如2048位）。
3. 计算欧拉函数φ(n) = (p-1)(q-1)。
4. 选择一个整数e，满足1 < e < φ(n)且gcd(e, φ(n))=1。通常e取65537（0x10001）。
5. 计算d，使得d × e ≡ 1 (mod φ(n))。d是e的模反元素。
6. 公钥为(n, e)，私钥为(n, d)。

加密与解密

假设发送方要用接收方公钥(n, e)加密消息m（m < n）：

加密：c ≡ m^e (mod n)

解密：m ≡ c^d (mod n)

由于模幂运算的复杂性，实际实现中会使用中国剩余定理加速解密。

安全性分析

RSA的安全性基于：

• 从n分解出p和q的困难性（若n被分解，则φ(n)可算，d可求）。
• 目前已知的最佳分解算法（如数域筛法）对于2048位以上的整数在可预见时间内无法完成。
• 需防范侧信道攻击、填充攻击（如PKCS#1 v1.5）等，实际使用中应配合OAEP填充。

实际应用

• SSL/TLS协议中的密钥交换（如RSA密钥传输）。
• 数字证书（X.509）签名。
• SSH、PGP等安全通信。
• 软件授权、代码签名。

理解RSA的数学原理，有助于正确使用和管理密钥，避免安全陷阱。