快速入门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

1
c = m^e mod n

3. 解密

密文 c → 明文 m

1
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 互质