Asmuth-Bloom 秘密共享 + RSA 加密 share:CRT 重构 zip 密码
ctf/crypto · verified
一句话结论
题目把每个 message 拆成多个 di : S mod di : bitlen 的简化 Asmuth-Bloom share,再分别用多把 RSA 公钥加密;先利用共享素因子/Wiener/Fermat 恢复部分私钥、解出 share,再对同一 message 的多个同余式做 CRT,即可重构出 S(即 message 明文),从中拿到下一层 zip 密码。
原理
- 简化版 Asmuth-Bloom:选一组递增的素数
d1 < d2 < ... < dn,对秘密整数S计算ki = S mod di,share 表示为di:ki:original_bits(十六进制)。只要收集到足够多的 share,且所有di的乘积大于S,就能用中国剩余定理唯一恢复S。 - 题目把多个 message 的 share 拼进同一份明文:
plaintext-j第一行是message1的内容,后面 9 行是message2..message10的 share。因此每解出一个 ciphertext,就同时获得 9 个 message 各一份 share。 - share 再用 RSA 公钥加密。
encrypt.py有两个分支: n_bits >= 2048:RSA-OAEP 加密 32 字节对称密钥,再 AES-GCM 加密 message;n_bits < 2048:随机 16 字节对称密钥直接裸 RSA(pow(key, e, n)),再 AES-GCM。- 多把公钥中存在可攻击的弱点:两两共享素因子(
gcd(n_i, n_j)直接分解)、Wiener 小私钥、Fermat 近素因子。恢复出足够多的私钥后,按密文长度/密钥长度匹配解密,得到 share。 - 对每个 message 收集到足够多的
(di, ki)后,CRT 恢复S;S转回字节即 message 明文。示例中message7里包含下一层 zip 的密码。
触发条件
- 题目给出多把 RSA 公钥与多段密文,明文由“固定前缀 + 多条
di:ki:bitlenshare”拼接。 - 公钥集合存在共享素因子、小私钥或近素因子等弱点,能恢复部分私钥。
- 同一 message 的 share 数量足够(
∏di > S),且di两两互素。 - 能从密文中解密出 share 文本,或能通过其他方式获得 share。
利用步骤
- 解析所有公钥,提取
n/e;对n两两求gcd,命中共享素因子的直接分解;对剩余公钥尝试 Wiener(大e小d)与 Fermat(p、q接近)。 - 对每个密文,根据长度判断走 OAEP+AES-GCM 还是裸 RSA+AES-GCM;用恢复的私钥解密出对称密钥,再 AES-GCM 解密 message。
- 解析明文中的
di:ki:bitlen行,按 message 分组;每行是一个同余式S ≡ ki (mod di)。 - 对每个 message 取足够多的 share,做 CRT 得到
S;用bitlen或最小字节数把S转回 bytes。 - 从恢复的 message 中提取密码/下一层线索;示例用
message7中的密码解level2.zip,继续下一层 RSA 题。
PoC
from math import prod
def crt_shares(shares):
# shares: [(di, ki), ...],di 两两互素,prod(di) > S
M = prod(d for d, _ in shares)
S = 0
for di, ki in shares:
Mi = M // di
S = (S + ki * Mi * pow(Mi, -1, di)) % M
return S
def int_to_bytes(x):
return x.to_bytes((x.bit_length() + 7) // 8, "big")
# 示例:把同一 message 的 10 条 share 转成 (di, ki) 后 CRT
# shares = [(int(d,16), int(k,16)) for d,k,bits in parsed_lines]
# msg = int_to_bytes(crt_shares(shares))
# RSA 侧:共享素因子
from math import gcd
for i in range(len(keys)):
for j in range(i + 1, len(keys)):
g = gcd(keys[i].n, keys[j].n)
if 1 < g < keys[i].n:
p, q = g, keys[i].n // g
变体与关联
- 变体:完整的 Asmuth-Bloom 会引入随机数
alpha与阈值k,share 为(S + alpha*m) mod di;本题是去掉随机项的简化版,CRT 直接恢复S。 - 变体:share 的编码可能是十进制/十六进制/字节串;
bitlen字段用于确定S的字节长度,缺失时用S.bit_length()向上取整。 - 变体:RSA 侧也可能使用共模、低指数广播、Coppersmith 部分私钥等;先做批量
gcd与常见弱密钥筛查。 - 关联:[[ctf-crypto-rsa-shared-prime-batch-gcd]](共享素因子批量 gcd)、[[crypto-rsa-wiener-small-private-exponent-large-e]](Wiener 小私钥)、[[ctf-crypto-rsa-hastad-broadcast-e3-crt]](CRT 在 RSA 广播中的用法)。
- 边界:share 数量不足或
∏di <= S时 CRT 结果不唯一;di不互素时需先处理公因子;恢复出的S需按bitlen截断。
检测与防御
- CTF 识别:多把公钥/多段密文 + 明文中的
modulus:remainder:bitlen行 + 提到“秘密共享/Asmuth-Bloom”,优先做批量 gcd 与 CRT。 - 防御:不要复用 RSA 素数,使用足够大的私钥指数与标准填充;秘密共享不能替代加密,share 的传输/存储仍需认证加密。
- 取证:保留公钥、密文与 share 原文;记录每个 message 的 share 数量与
di乘积,确认 CRT 唯一性。