快速入门crypto-RSA 核心笔记

一、加解密核心公式

1. 密钥生成

1. 选两个大质数 p 和 q
2. 计算模数 n = p * q
3. 计算欧拉函数 φ(n) = (p-1) * (q-1)
4. 选公钥 e，满足 1 < e < φ(n) 且 e 和 φ(n) 互质（最大公约数为 1）
5. 求私钥 d，满足 (e * d) mod φ(n) = 1 → d 是 e 在模 φ(n) 下的逆元

2. 加密

明文 m → 密文 c

c = m^e mod n

3. 解密

密文 c → 明文 m

m = c^d mod n

---

二、常见攻击方式（大白话）

1. 模数可分解攻击（最基础）

• 适用场景：拿到公钥 (e, n) 和密文 c，且能把 n 拆成 p*q

• 攻击原理

  ：

  1. 分解 n = p*q（CTF 里常用工具：yafu、factordb 网站）
  2. 算 φ(n) = (p-1)*(q-1)
  3. 求 e 的逆元 d → 用 d 解密 c 得 m

• 关键条件：n 能被成功分解（如果 p 和 q 太小，分解很容易）

2. 共模攻击（同一 n 漏洞）

• 适用场景：同一明文 m，用同一个 n、不同公钥 e1/e2 加密，得到密文 c1/c2

• 攻击原理

  ：

  1. 只要 e1 和 e2 互质，就存在整数 x 和 y，满足 e1*x + e2*y = 1
  2. 明文 m = (c1^x * c2^y) mod n
  3. 遇到负数次幂 → 转成模逆（比如 c1^-k = (c1^k 的逆元) mod n）

• 关键条件：多个公钥共用同一个 n，且公钥之间互质

补充：CTF 里其他常见攻击（拓展）

1. 低加密指数攻击（e 太小，比如 e=3）
   • 场景：e 很小，密文 c = m^3 mod n
   • 原理：直接对 c 开立方，结果就是 m（不用分解 n）
2. 私钥泄露攻击
   • 场景：不小心泄露了私钥 d
   • 原理：拿到 d 就能直接解密任意用 (e,n) 加密的密文

---

三、核心总结

操作	公式	关键条件
加密	c = m^e mod n	知道公钥 (e,n)
解密	m = c^d mod n	知道私钥 d
模数分解攻击	分解 n=p*q → 求 d	n 可被分解
共模攻击	m=(c1^x*c2^y)mod n	同 n、多 e、e1/e2 互质