概念

RSA

基于大整数分解的困难性：公钥含模数 n=pq，解密需要知道 p 与 q，是使用最广泛的公钥加密算法。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

RSA密码学

01定义

RSA 的安全性建立在大整数分解的困难上：公钥含模数

n=pq

，加密

c=m^e\bmod n

，解密需要私钥

d

——而由

n,e

恢复

d

等价于分解

n

。公钥加密、数字签名、密钥封装三种用途一网打尽，是应用最广的公钥算法。

RSA：乘法容易，分解难

$m^{ed}=m^{1+k\varphi(n)}\equiv m\pmod n$ ：解密正确性完全依赖欧拉定理； $e$ 常取 65537（费马素数，快速幂高效）， $d$ 由扩展欧几里得求逆元。

裸 RSA 不安全：必须加填充（OAEP 加密、PSS 签名）防代数攻击；中国剩余定理加速解密四倍；密钥长度 2048 位起步，3072 位面向长期安全。

数域筛法（GNFS）是经典最强算法，复杂度亚指数 $e^{O(n^{1/3})}$ ；RSA-250（829 位）2020 年被分解；Shor 量子算法使 RSA 面临后量子迁移压力。

c\equiv m^e\ (\bmod\ n),\quad m\equiv c^d\ (\bmod\ n),\ \ ed\equiv 1\ (\bmod\varphi(n))

Rivest、Shamir、Adleman 1977 年发表 RSA（英国 GCHQ 的 Cocks 1973 年已内部提出）；三人获 2002 年图灵奖；RSA 实验室的分解挑战赛推动了十余年的算法进步。

HTTPS 证书签名、代码签名、SSH 密钥认证、文档数字签名与时间戳。

RSA：m⁷ mod 33 加密 · c³ mod 33 解密拖动明文 m（n=33, e=7, d=3）：密文看似乱跳，解密后必然还原

m 明文5