RSA算法
定义
RSA算法属于公开密钥密码体制，也称非对称密码算法：加密时使用一个密钥，解密时使用另一个与之配对的密钥，并且从公开的加密密钥出发推算解密密钥在计算上不可行[1][2]。其中对外公布的一把称为公钥，由持有者自己保存的一把称为私钥，通信时由发送方取用接收方的公钥处理信息，接收方再用自己的私钥还原[3]。
RSA算法在公开密钥加密与电子商业活动中被大量采用，也是第一个既能做数据加密又能做数字签名的公钥算法[1]。
原理
算法的数学基础来自数论：找出两个大素数并相乘容易完成，而把一个由两个大素数乘出的合数分解回原来的因子则极为困难，因此可以把乘积部分作为公开参数，把两个素数留作秘密[2][3]。密钥生成通常先随机选取两个互不相同的大素数 $p$ 与 $q$，计算模数 $n=pq$ 以及欧拉函数 $\varphi(n)=(p-1)(q-1)$，再挑出与 $\varphi(n)$ 互素的整数 $e$ 作为公开指数[4]。随后求 $e$ 关于 $\varphi(n)$ 的模逆元 $d$，使 $ed\equiv 1 \pmod{\varphi(n)}$，得到公钥 $(n,e)$ 与私钥 $(n,d)$[4]。
加解密都以模幂运算完成：明文 $m$ 按 $c=m^{e} \bmod n$ 变换为密文，密文按 $m=c^{d} \bmod n$ 还原[4]。其可行性依据欧拉定理，当 $m$ 与 $n$ 互素时 $m^{\varphi(n)}\equiv 1 \pmod n$，由此可推出 $(m^{e})^{d}\equiv m \pmod n$[4]。公开指数常取 65537，私钥指数则借助扩展欧几里得算法求出。
flowchart LR
A[选取大素数 p、q] --> B[计算 n=pq 与 φ(n)]
B --> C[选取公钥指数 e]
C --> D[求私钥指数 d]
D --> E[公钥 n,e 公开]
A --> F[私钥 d 保密]
E --> G[加密 c=m^e mod n]
F --> H[解密 m=c^d mod n]
G --> H
数字签名把这一对运算反过来使用：签名方用自己的私钥对消息摘要运算，验证方用对方公钥检验结果是否与摘要一致，从而判断消息来源与完整性[3]。实际部署中，解密运算还可借助中国剩余定理拆成模 $p$ 与模 $q$ 两步以缩短耗时，同时明文需要按 PKCS#1 等标准填充，不宜直接对原始数据做模幂[5]。
发展历程
1977年，在麻省理工学院工作的李维斯特、萨莫尔与阿德曼共同提出这一方案，算法名称取自三人姓氏的首字母[1]。相关成果于次年公开发表，此后逐渐成为公钥密码领域的常用方案[6]。
更早的相同思路出现在英国：1973年，供职于英国政府通讯总部的数学家克利福德·柯克斯(Clifford Cocks)已在内部文件中描述过类似算法，但文件被列为机密，直到1997年才公开[1]。1983年麻省理工学院在美国为RSA算法取得专利，该专利于2000年9月21日失效；由于申请专利之前算法已经发表，这一专利权在多数其他国家和地区未获承认[1]。
随着计算能力提升与安全标准调整，RSA的推荐密钥长度不断提高。2016年12月5日，上海市密码管理局发布公告，自2017年1月1日起停止提供RSA算法1024位密钥对服务，以应对该长度密钥面临的安全风险[2]。美国国家标准与技术研究院在后量子密码迁移草案中提出，112位安全强度的RSA配置在2030年之后不再用于保护新信息，并在2035年之后全面停用；相关日期属于草案内容，尚未最终确定[7][8]。
应用
RSA最常见的用途是加密通信中的会话密钥分发。由于公开密钥体制运算量大，实践中往往把对称加密与公钥加密配合使用：正文数据交由DES或IDEA一类对称算法处理，RSA只负责加密对话密钥与信息摘要，接收方分别解密并核对摘要[1]。数字证书、安全电子邮件以及TLS等协议也以这类公钥机制为基础[3]。
在电子商业与软件产品中，RSA被嵌入到多种系统里，包括Windows、网景Navigator、Quicken与Lotus Notes等[2]。SET协议要求认证机构使用2048位密钥，其他参与实体使用1024位密钥[1]。
局限
速度是RSA的明显短板。它涉及大数运算，加密解密比同安全级别的对称密码算法慢很多，有资料估计差距在1000倍左右，因此通常只用于少量数据[2]。密钥越长，运算耗时越久，选择长度时需要在保护强度与系统响应时间之间权衡[2]。
安全性的理论依据并不完全严密。RSA的破解难度是否等价于大数分解，一直没有得到证明，只是尚未找到不依赖分解的有效攻击途径[1]。早期使用的小模数已被实际分解，512位密钥被视为不安全，模数必须随攻击能力提升而加长[2]。此外，选择密文攻击对RSA构成威胁，攻击者可诱使私钥持有者对伪装信息签名，再从结果推算所需数据，这类风险需要在实现层面加以处理[2]。
量子计算带来另一重不确定性。运行肖尔算法的量子计算机可在多项式时间内完成大整数分解，届时RSA的安全性将不再成立；由于算法本身依赖分解问题，单纯加长密钥并不能抵消这一威胁[7]。目前尚无具备相关能力的量子计算机，业界讨论的应对方向是改用基于格的密钥封装与签名方案等抗量子算法[7][8]。
参见
参考资料
- [科普中国]-RSA算法 [引用日期2026-10-29]
- RSA算法（非对称加密算法） [引用日期2026-10-29]
- RSA算法仿真模拟 [引用日期2026-10-29]
- RSA算法详解：原理、应用与安全性证明 [引用日期2026-10-29]
- 19-rsa [引用日期2026-10-29]
- US11579239 [引用日期2026-10-29]
- RSA: Secure Today, Scheduled for Retirement [引用日期2026-10-29]
- bootlin.com 上的网页 [引用日期2026-10-29]