跳到主要内容

弱 RSA 密钥分解与私钥重建

RSA 的安全性押在 n 的大数分解难度上。模数过短（如 256-bit、512-bit）或 p、q 取值过近时，n 可以被实际分解；拿到 p、q 后即可重建私钥解密密文。这条链路适用于"拿到公钥与密文，但拿不到私钥"的场景。

仅限授权环境

以下分析仅用于授权评估、题目环境与自己生成的弱密钥。

识别弱密钥​

openssl pkey -pubin -in pub.pem -text -noout

看输出里的模数位数：256-bit、512-bit 都属于可分解范围。位数越大分解成本越高，见到几百位的模数就可以直接走分解流程。

分解路线一：FactorDB​

很多弱模数早已被收录，直接查已知分解：

curl "http://factordb.com/api?query=<十进制n>"

返回结果里带 p、q 时无需任何计算。

分解路线二：Fermat 分解​

p、q 相近时，Fermat 法从 a = isqrt(n) 开始递增，检查 a*a - n 是否完全平方数：

import math

def fermat(n):
    a = math.isqrt(n)
    while True:
        b2 = a * a - n
        b = math.isqrt(b2)
        if b * b == b2:
            return a - b, a + b
        a += 1

n = (a-b)(a+b) 成立时立即返回 p、q，p、q 越接近迭代次数越少。

私钥重建与解密​

用 Python cryptography 重建私钥。核心三步：e = 65537、phi = (p-1)(q-1)、d = pow(e, -1, phi)。rsa.RSAPrivateNumbers 需要提供全字段，dmp1/dmq1/iqmp 可由 p、q 计算：

from cryptography.hazmat.primitives.asymmetric import rsa, padding

e = 65537
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

priv = rsa.RSAPrivateNumbers(
    p=p, q=q, d=d,
    dmp1=d % (p - 1),
    dmq1=d % (q - 1),
    iqmp=pow(q, -1, p),
    public_numbers=rsa.RSAPublicNumbers(e=e, n=p * q),
).private_key()

plaintext = priv.decrypt(ciphertext, padding.PKCS1v15())

解密用 PKCS1v15 填充；密文按传统 PKCS#1 v1.5 加密时直接可解。

附带问题：OpenSSH 私钥 magic 修复​

OpenSSH 新格式私钥以 openssh-key-v1\0 magic 开头。头部被覆盖时按格式重写前 15 字节即可恢复解析，正文未损坏时不需要重新生成。

复核要点​

  • 重建私钥后先加密一段已知明文再解密自检，确认 p、q 正确。
  • 解密报填充错误时，先确认密文的填充方式与密钥是否对应。
  • FactorDB 无记录且 p、q 不相近时，本页两条分解路线都不适用，需要另找路线。

防御建议​

  1. RSA 模数不低于 3072 位，禁用短模数与遗留密钥。
  2. 加密场景优先使用 OAEP 填充。
  3. 审计密钥生成流程：确保熵源充足，不在低熵环境（如刚启动的嵌入式设备）生成密钥。
  4. 定期盘点在用密钥的位数与算法，淘汰弱密钥。