返回项目列表

RSA 原理学习

非对称加密数学原理

一、RSA 原理

密钥生成步骤

  1. 1、选择两个大素数 p 和 q
    素数：除了 1 和它本身外，不能被其他自然数整除的数
  2. 2、计算 N = pq
  3. 3、计算欧拉函数 φ(N) = (p-1)(q-1)
    φ(n) 指在 1 到 n 之间，与 n 互质的整数个数；若 n 为素数，则 φ(n) = n-1
  4. 4、选择与 φ(N) 互质的整数 e（加密密钥）
    e即encryption key
  5. 5、计算私钥 d = e-1 (mod φ(N))
    d即decryption key
最终公钥：(N, e)
最终私钥：d

说明：p、q、φ(N) 用于中间计算，保密且最终可丢弃
用公钥加密后只能用私钥解密（用于加密通信），用私钥加密后只能用公钥解密（用于签名）

加密与解密

加密： c ≡ me (mod N)

解密： m ≡ cd (mod N)

其中 m 为明文（message），c 为密文（ciphertext）
解密正确性：cd ≡ (me)d ≡ med ≡ m (mod N)，因为 ed ≡ 1 (mod φ(N))

二、简单实例

Alice 给 Bob 发送秘密消息"love you"

第 1 步：Bob 生成密钥对

选择两个素数：

  • p = 101
  • q = 127

计算：

  • N = 101 × 127 = 12,827
  • φ(N) = (101-1) × (127-1) = 100 × 126 = 12,600
  • e = 11（与 12,600 互质）
  • d = 2,291（满足 11 × 2,291 ≡ 1 (mod 12,600)）
最终公钥：(N=12,827, e=11) ← 公开给 Alice
最终私钥：d=2,291 ← Bob 保密

第 2 步：Alice 将消息转为数字

采用 a=01, b=02, ..., z=26，空格=00 的编码方案：

消息："love you"

完整编码：
l=12, o=15, v=22, e=05, (space)=00, y=25, o=15, u=21

拼接得：12 15 22 05 00 25 15 21

问题：这个数（1215220500251521）超过 N=12,827 的限制

解决方案：分段处理。先取前两位"LO"：
l=12, o=15 → 连接：m = 1,215

第 3 步：Alice 使用公钥加密

c ≡ me (mod N)
c ≡ 1,21511 (mod 12,827)
c ≡ 4,892 (mod 12,827)

密文：4,892 ← Alice 发送给 Bob

第 4 步：Bob 使用私钥解密

m ≡ cd (mod N)
m ≡ 4,8922,291 (mod 12,827)
m ≡ 1,215 (mod 12,827)

恢复明文：1,215 → 12 15 → "LO"
Alice 将整个消息分成多块，每块单独加密发送；Bob 接收后逐块解密重组

三、安全性分析

RSA 的安全性取决于分解两个大质数乘积的难度，即因式分解问题

攻击者知道公钥 (N, e) 和密文 c，要恢复明文需要：

  1. 分解 N 得到 p 和 q（最困难的一步）
  2. 计算 φ(N) = (p-1)(q-1)
  3. 计算私钥 d = e-1 (mod φ(N))
  4. 解密 m = cd (mod N)

密钥强度对比

密钥位数 破解难度 状态
512 位 几小时 ❌ 已破解（1999年）
1024 位 数十年 ⚠️ 开始不安全
2048 位 数百年 ✅ 目前安全
4096 位 极其困难 ✅ 长期安全