RSA

RSA
Rivest-Shamir-Adleman

设计者

Ron Rivest, Adi Shamir, Leonard Adleman

首次发布

1977年

类别

非对称公钥密码

数学基础

大整数分解难题

推荐密钥

≥ 2048 bit (3072+ 更安全)

标准

PKCS#1, RFC 8017

安全状态

安全（≥2048位）

RSA是 1977 年由 Ron Rivest、Adi Shamir 和 Leonard Adleman 提出的公钥密码系统，是历史上第一个实用的公钥加密方案。RSA 的安全性基于大整数分解的计算困难性：给定两个大素数 p 和 q，计算 n = p × q 很容易；但给定 n，分解出 p 和 q 极其困难。

算法原理

密钥生成:
    1. 选择两个大素数 p, q (通常各 ~1024 位)
    2. 计算 n = p × q
    3. 计算 φ(n) = (p-1)(q-1)
    4. 选择 e，满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1
       （通常 e = 65537 = 0x10001）
    5. 计算 d，满足 e × d ≡ 1 (mod φ(n))

公钥:  (n, e)
私钥:  (n, d)  或 (p, q, d)

加密:  c = m^e mod n
解密:  m = c^d mod n

签名:  s = m^d mod n
验证:  m = s^e mod n

填充方案

原始 RSA（"教科书 RSA"）是不安全的，必须使用填充方案：

方案	用途	安全状态
PKCS#1 v1.5	加密/签名	存在攻击（Bleichenbacher），不推荐新系统
OAEP	加密	推荐（RFC 8017）
PKCS#1 v1.5 签名	签名	仍广泛使用但建议迁移
PSS	签名	推荐（RFC 8017）

密钥长度建议

RSA 密钥	等效对称密钥	推荐
1024 bit	80 bit	已不安全
2048 bit	112 bit	最低要求
3072 bit	128 bit	推荐
4096 bit	150 bit	高安全需求
15360 bit	256 bit	理论最高（不实用）

与 ECC 对比

特性	RSA-2048	ECC P-256
安全强度	112 bit	128 bit
私钥大小	2048 bit	256 bit
公钥大小	2048 bit	256 bit + 参数
签名速度	慢（大数运算）	快
验证速度	快（e=65537）	快
量子威胁	Shor 算法可破解	Shor 算法可破解

参考文献

Rivest, R., Shamir, A., Adleman, L. (1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems". Commun. ACM 21(2): 120-126.
Moriarty, K., et al. (2016). "PKCS #1: RSA Cryptography Specifications Version 2.2". RFC 8017.

加密算法导航

AES · DES/3DES · Blowfish · SM4 · ChaCha20 · RC4 · RSA · ECC · DH · SM2 · ML-KEM · ML-DSA · SLH-DSA

分类：密码学 · 公钥密码 · 数字签名

Open Clock

RSA