rsa

第一层

第一层给了这些东西：

generate-plaintexts.py
encrypt.py
key-*.pem
ciphertext-*.bin

这一层表面上是在考秘密共享 + RSA + AES，实际上核心是：

识破假的门限共享
找弱 RSA 公钥并恢复私钥
解出若干份明文 share
用 CRT 直接恢复原始消息

第一步

generate-plaintexts.py 说它用了 Asmuth-Bloom 秘密共享，但实际上并不是正规的门限共享。

它真正干的事是：

1 2	ki = S % di share_str = f"{di:x}:{ki:x}:{original_bits:x}"

也就是说，每一条 share 本质上只是：

1	(d_i, S mod d_i, 原始信息位数)

所以第一层要做的只是：

把 RSA/AES 拆掉
拿到几个明文 share
对同一个消息做 CRT

换句话说，它并没有真正实现“满足门限才可恢复”的分享机制，而只是把同一个整数 S 对不同模数做了取模而已。

只要我们拿到足够多组：

1
2
3

S ≡ k_1 (mod d_1)
S ≡ k_2 (mod d_2)
...

就可以用中国剩余定理把 S 还原出来。

第二步

encrypt.py 里面分了两种情况：

1. 当 `n.bit_length() >= 2048` 时：

随机生成 32 字节 AES key
用 RSA-OAEP 加密 AES key
再用 AES-GCM 加密明文

2. 当 `n.bit_length() < 2048` 时：

随机生成 16 字节 AES key
直接做 pow(key, e, n) 的“裸 RSA”
再用 AES-GCM 加密明文

所以我们只要能把 RSA 私钥还原出来，就能解出 AES key，再解出 plaintext。

这一层的技术路线非常明确：

先破 RSA
再破 AES-GCM
最后还原 share

第三步：找弱公钥

这一层给了 20 个 key-*.pem，但是只有 10 个 ciphertext-*.bin。

先把所有公钥读出来，提取其中的：

然后检查是否有明显弱点。

弱点 1：共享素因子

把所有 n 两两做 gcd：

from math import gcd

for i in range(len(idxs)):
    for j in range(i + 1, len(idxs)):
        a, b = idxs[i], idxs[j]
        g = gcd(keys[a][0], keys[b][0])
        if 1 < g < keys[a][0]:
            print(a, b, g)

如果两个模数共用了同一个素数 p，那么：

1 2	n1 = p * q1 n2 = p * q2

此时直接：

1
2
3

p = gcd(n1, n2)
q1 = n1 // p
q2 = n2 // p

就能把两个公钥一起分解。

这一题里可以打出来的有：

key-1.pem 和 key-2.pem
key-4.pem 和 key-15.pem

弱点 2：Fermat 分解

对于某些 n = p*q，如果 p 和 q 非常接近，那么可以用 Fermat 分解：

from math import isqrt

def factor_fermat(n: int, limit: int = 2000):
    a = isqrt(n)
    if a * a < n:
        a += 1
    for _ in range(limit):
        b2 = a * a - n
        b = isqrt(b2)
        if b * b == b2:
            p, q = a - b, a + b
            if p > 1 and q > 1 and p * q == n:
                return p, q
        a += 1
    return None

原理是：

1	n = pq = a^2 - b^2 = (a-b)(a+b)

如果 p 和 q 接近，那么 a = (p+q)/2 离 sqrt(n) 很近，搜索很快就能命中。

这题里我实际打出来的弱 key 包括：

key-3.pem
key-7.pem
key-18.pem

因此，第一层并不是“硬啃全部 20 把 RSA”，而是只要筛出那些被故意做弱的公钥即可。

第四步：用弱 key 去试所有 ciphertext

这里有一个容易踩的坑：

不能假设 ciphertext-i.bin 一定对应 key-i.pem。

因为出题人没有承诺它们一一对应，所以正确做法是：

把所有已经分解出的弱 key 都准备好
用每把弱 key 去尝试解每一个 ciphertext-*.bin
如果最后 AES-GCM 验证通过，就说明匹配成功

因为 AES-GCM 自带 tag 校验，所以只要密钥不对，就会直接解密失败。

对于 n.bit_length() >= 2048 的 key，先做 RSA-OAEP 解出 AES key：

priv = rsa.RSAPrivateNumbers(
    p, q, d, d % (p - 1), d % (q - 1), inv(q, p), rsa.RSAPublicNumbers(e, n)
).private_key()

aes_key = priv.decrypt(
    header,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA1()),
        algorithm=hashes.SHA1(),
        label=None,
    ),
)

对于 n.bit_length() < 2048 的 key，则是裸 RSA：

1 2	m = pow(bytes_to_long(header), d, n) aes_key = long_to_bytes(m, 16)

然后用 AESGCM(aes_key).decrypt(...) 解正文。

我实际跑出来的匹配关系是：

ciphertext-1.bin  <-> key-3.pem
ciphertext-3.bin  <-> key-4.pem
ciphertext-4.bin  <-> key-7.pem
[[团队笔记/xinlv/未命名]]ciphertext-8.bin  <-> key-1.pem
ciphertext-9.bin  <-> key-18.pem

也就是说，我们一共拿到了 5 份明文 share。

每一份解出来的明文格式大致是：

第一行：固定提示语
后面 9 行：分别对应 message2 ~ message10

每一行格式是：

1	<di_hex>:<ki_hex>:<bits_hex>

也就是：

1	(d_i, S mod d_i, 原始消息 bit 长度)

所以对于同一个消息，比如 message7，我们只要从 5 份 plaintext 里都取出第 7 对应的那一行，就能得到 5 个同余方程：

S ≡ k_1 (mod d_1)
S ≡ k_2 (mod d_2)
...
S ≡ k_5 (mod d_5)

这时直接 CRT：

def crt(remainders, moduli):
    M = 1
    for m in moduli:
        M *= m
    x = 0
    for r, m in zip(remainders, moduli):
        Mi = M // m
        x = (x + r * Mi * pow(Mi, -1, m)) % M
    return x, M

恢复条件是：

1	模数乘积 M 的 bit 长度 > 原始消息 bit 长度

一旦满足这个条件，CRT 得到的 x 就是那个消息的真实整数表示。

恢复后把 x 转成字节串再解码即可。

第六步：拿到第一层密码

跑完之后会恢复出多条 message，其中关键的一条是：

1	Congratulations! next pass is 9Zr4M1ThwVCHe4nHnmOcilJ8。

这里注意最后有一个中文句号 。，它不是密码的一部分。

所以：

1	level2.zip 密码 = 9Zr4M1ThwVCHe4nHnmOcilJ8

第一层完整解题脚本

from pathlib import Path
from math import gcd, isqrt
from cryptography.hazmat.primitives import serialization, hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives.ciphers.aead import AESGCM

BASE = Path('level1')
if not BASE.exists():
    BASE = Path('.')


def egcd(a, b):
    if b == 0:
        return 1, 0, a
    x, y, g = egcd(b, a % b)
    return y, x - (a // b) * y, g


def inv(a, m):
    x, _, g = egcd(a, m)
    if g != 1:
        raise ValueError('inverse does not exist')
    return x % m


def bytes_to_long(b: bytes) -> int:
    return int.from_bytes(b, 'big')


def long_to_bytes(x: int, size: int | None = None) -> bytes:
    if size is None:
        size = max(1, (x.bit_length() + 7) // 8)
    return x.to_bytes(size, 'big')


def factor_fermat(n: int, limit: int = 2000):
    a = isqrt(n)
    if a * a < n:
        a += 1
    for step in range(limit):
        b2 = a * a - n
        b = isqrt(b2)
        if b * b == b2:
            p, q = a - b, a + b
            if p > 1 and q > 1 and p * q == n:
                return p, q, step
        a += 1
    return None


def crt(remainders, moduli):
    M = 1
    for m in moduli:
        M *= m
    x = 0
    for r, m in zip(remainders, moduli):
        Mi = M // m
        x = (x + r * Mi * pow(Mi, -1, m)) % M
    return x, M


keys = {}
for pem in BASE.glob('key-*.pem'):
    idx = int(pem.stem.split('-')[1])
    pub = serialization.load_pem_public_key(pem.read_bytes())
    nums = pub.public_numbers()
    keys[idx] = (nums.n, nums.e)

factors = {}
idxs = sorted(keys)
for i in range(len(idxs)):
    for j in range(i + 1, len(idxs)):
        a, b = idxs[i], idxs[j]
        g = gcd(keys[a][0], keys[b][0])
        if 1 < g < keys[a][0]:
            factors[a] = (g, keys[a][0] // g, f'gcd with key-{b}')
            factors[b] = (g, keys[b][0] // g, f'gcd with key-{a}')

for idx in idxs:
    if idx in factors:
        continue
    ret = factor_fermat(keys[idx][0], limit=2000)
    if ret:
        p, q, step = ret
        factors[idx] = (p, q, f'fermat step={step}')

print('[+] weak keys found:')
for k in sorted(factors):
    print(f'    key-{k}: {factors[k][2]}')

solved_plaintexts = []
for ct_file in sorted(BASE.glob('ciphertext-*.bin')):
    ct_idx = int(ct_file.stem.split('-')[1])
    ct = ct_file.read_bytes()

    for key_idx, (p, q, how) in sorted(factors.items()):
        if p > q:
            p, q = q, p
        n, e = keys[key_idx]
        key_len = (n.bit_length() + 7) // 8

        if len(ct) <= key_len + 12 + 16:
            continue

        header = ct[:key_len]
        nonce = ct[key_len:key_len + 12]
        body = ct[key_len + 12:-16]
        tag = ct[-16:]
        phi = (p - 1) * (q - 1)
        d = inv(e, phi)

        try:
            if n.bit_length() >= 2048:
                dmp1 = d % (p - 1)
                dmq1 = d % (q - 1)
                iqmp = inv(q, p)
                priv = rsa.RSAPrivateNumbers(
                    p, q, d, dmp1, dmq1, iqmp, rsa.RSAPublicNumbers(e, n)
                ).private_key()
                aes_key = priv.decrypt(
                    header,
                    padding.OAEP(
                        mgf=padding.MGF1(algorithm=hashes.SHA1()),
                        algorithm=hashes.SHA1(),
                        label=None,
                    ),
                )
            else:
                m = pow(bytes_to_long(header), d, n)
                if m >= (1 << 128):
                    continue
                aes_key = long_to_bytes(m, 16)

            pt = AESGCM(aes_key).decrypt(nonce, body + tag, None)
            text = pt.decode()
            if text.startswith("Great job! You've successfully decoded a ciphertext!"):
                print(f'[+] ciphertext-{ct_idx}.bin <-> key-{key_idx}.pem  ({how})')
                solved_plaintexts.append(text)
                break
        except Exception:
            pass

print(f'[+] decrypted plaintext count = {len(solved_plaintexts)}')

lines_list = [pt.splitlines()[1:] for pt in solved_plaintexts]
recovered = {}
for msg_idx in range(2, 11):
    moduli = []
    remainders = []
    original_bits = None
    for lines in lines_list:
        di_hex, ki_hex, bits_hex = lines[msg_idx - 2].split(':')
        di = int(di_hex, 16)
        ki = int(ki_hex, 16)
        original_bits = int(bits_hex, 16)
        moduli.append(di)
        remainders.append(ki)

    x, M = crt(remainders, moduli)
    if M.bit_length() > original_bits:
        msg = x.to_bytes((original_bits + 7) // 8, 'big').decode('utf-8', errors='replace')
        recovered[msg_idx] = msg
        print(f'[+] message{msg_idx} = {msg}')
    else:
        print(f'[-] message{msg_idx} not enough CRT modulus')

print('\n[+] level2.zip password =', recovered[7].replace('Congratulations! next pass is ', '').rstrip('。'))

第二层

解开 level2.zip 后可以得到：

task.py
level3.zip

这一层的关键在于它不是普通 RSA，而是：

1
2
3

d = getPrime(180)
lam = lcm(p - 1, q - 1)
e = inverse(d, lam)

也就是说：

私钥 d 很小，只有 180 bit
但满足的同余关系是：

1	e*d ≡ 1 (mod λ(n))

而不是更常见的：

1	e*d ≡ 1 (mod φ(n))

所以不能直接照抄最普通版本的 Wiener 攻击，而要做一点变形。

第一步：把关系改写成类似 Wiener 的形式

设：

1	λ(n) = lcm(p-1, q-1) = φ(n) / g

其中：

1	g = gcd(p-1, q-1)

因为：

1	ed - kλ(n) = 1

两边同时乘上 g：

1	e(dg) - k*φ(n) = g

令：

D = d*g

就得到：

1	eD - kφ(n) = g

这就很接近 Wiener 的经典形式了。

因此做法是：

对 e/n 做连分数展开
枚举收敛分数 (k, D)
再枚举一个较小的 g
计算
1
φ = (eD - g) / k
由 φ 推 p + q = n - φ + 1
检查判别式是否是完全平方

如果成立，就成功分解 n。

第二步：连分数枚举

核心代码如下：

def continued_fraction(a, b):
    out = []
    while b:
        out.append(a // b)
        a, b = b, a % b
    return out


def convergents(cf):
    p0, q0 = cf[0], 1
    yield p0, q0
    if len(cf) == 1:
        return
    p1, q1 = cf[0] * cf[1] + 1, cf[1]
    yield p1, q1
    for x in cf[2:]:
        p2 = x * p1 + p0
        q2 = x * q1 + q0
        yield p2, q2
        p0, q0, p1, q1 = p1, q1, p2, q2

然后枚举：

cf = continued_fraction(e, n)
for idx, (k, D) in enumerate(convergents(cf)):
    if k == 0:
        continue
    for g in range(1, 500):
        if (e * D - g) % k != 0:
            continue
        phi = (e * D - g) // k
        s = n - phi + 1
        delta = s * s - 4 * n
        ...

如果：

1	Δ = s^2 - 4n

是完全平方，那么：

1 2	p = (s + sqrt(Δ)) / 2 q = (s - sqrt(Δ)) / 2

就能直接恢复出来。

第三步：拿到第二层密码

这题实际会命中一个很小的 g，脚本跑出来是：

g = 4

然后恢复出 p + q。

题目里最后写的是：

1 2	flag_hash = sha256(str(p + q).encode()).hexdigest() flag = f"next pass is {flag_hash}"

所以第二层密码就是：

1	2aa9c360df99cbb4209e4dbab5a9f9ffd86d34906e3206fecfdabf0bb7aeb5ac

即：

1	level3.zip 密码 = 2aa9c360df99cbb4209e4dbab5a9f9ffd86d34906e3206fecfdabf0bb7aeb5ac

第二层完整解题脚本

import hashlib
from math import isqrt

n = 99573363048275234764231402769464116416087010014992319221201093905687439933632430466067992037046120712199565250482197004301343341960655357944577330885470918466007730570718648025143561656395751518428630742587023267450633824636936953524868735263666089452348466018195099471535823969365007120680546592999022195781
e = 12076830539295193533033212232487568888200963123024189287629493480058638222146972496110814372883829765692623107191129306190788976704250502316265439996891764101447017190377014980293589797403095249538391534986638973035285900867548420192211241163778919028921502305790979880346050428839102874086046622833211913299


def continued_fraction(a, b):
    out = []
    while b:
        out.append(a // b)
        a, b = b, a % b
    return out


def convergents(cf):
    p0, q0 = cf[0], 1
    yield p0, q0
    if len(cf) == 1:
        return
    p1, q1 = cf[0] * cf[1] + 1, cf[1]
    yield p1, q1
    for x in cf[2:]:
        p2 = x * p1 + p0
        q2 = x * q1 + q0
        yield p2, q2
        p0, q0, p1, q1 = p1, q1, p2, q2


cf = continued_fraction(e, n)
found = False
for idx, (k, D) in enumerate(convergents(cf)):
    if k == 0:
        continue
    for g in range(1, 500):
        if (e * D - g) % k != 0:
            continue

        phi = (e * D - g) // k
        s = n - phi + 1
        delta = s * s - 4 * n
        if delta < 0:
            continue

        t = isqrt(delta)
        if t * t != delta:
            continue
        if (s + t) % 2 != 0:
            continue

        p = (s + t) // 2
        q = (s - t) // 2
        if p * q == n:
            d = D // g
            print(f'[+] hit convergent #{idx}, g = {g}')
            print('[+] d =', d)
            print('[+] p + q =', p + q)
            pwd = hashlib.sha256(str(p + q).encode()).hexdigest()
            print('[+] level3.zip password =', pwd)
            found = True
            break
    if found:
        break

if not found:
    print('[-] not found')

第三层

解开 level3.zip 后，可以拿到：

n
e = 65537
c
leak

这一层看起来像是一个很复杂的泄露表达式，里面混合了：

乘法
异或
与或操作
位移
截断

表面上很难直接反推，但关键观察点是：

当我们只看模 2^k 的低位时，这个 leak 的低位只依赖于 p 和 q 的低位。

这就意味着可以做 按位提升。

第一步：确定最低位

因为 p 和 q 都是奇素数，所以：

1 2	p ≡ 1 (mod 2) q ≡ 1 (mod 2)

所以一开始可以把候选初始化为：

1	cands = [(1, 1)]

第二步：逐位扩展

假设当前我们已经知道：

1 2	p mod 2^k q mod 2^k

那么第 k 位只可能是 0 或 1，因此枚举：

1	a, b ∈ {0,1}

构造：

1 2	pp = p0 \| (a << k) qq = q0 \| (b << k)

然后检查两个条件：

它们乘起来的低 k+1 位必须和 n 一致
代入泄露函数后的低 k+1 位必须和 leak 一致

对应代码是：

if (pp * qq) % mod != need_n:
    continue
if leak_func(pp, qq) % mod != need_leak:
    continue

只要同时满足，就说明这一位的猜测是对的，把候选留下来。

然后进入下一位继续扩展。

第三步：为什么这样能行

因为：

模 2^(k+1) 只关心低 k+1 位
所有这些按位运算、截断、异或，在低位模数下都是局部可验证的
所以每往上猜一位，都可以立即用 n 和 leak 的低位把错误分支剪掉

这种方法本质上就是一个低位逐步恢复的搜索过程。

在这题里，剪枝效果非常好，候选几乎不会爆炸，最后能稳定恢复出完整的 p 和 q。

第四步：恢复 RSA 私钥并解密

得到 p 和 q 后，就是普通 RSA 收尾：

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
flag = long_to_bytes(m)

最后得到：

1	dart{379c9308-e9a8-45a1-bd55-45bbd822e86d}

第三层完整解题脚本

from math import isqrt

n = 3656543170780671302102369785821318948521533232259598029746397061108006818468053676291634112787611176554924353628972482471754519193717232313848847744522215592281921147297898892307445674335249953174498025904493855530892785669281622228067328855550222457290704991186404511294392428626901071668540517391132556632888864694653334853557764027749481199416901881332307660966462957016488884047047046202519520508102461663246328437930895234074776654459967857843207320530170144023056782205928948050519919825477562514594449069964098794322005156920839848615481717184615581471471105167310877784107653826948801838083937060929103306952084786982834242119877046219260840966142997264676014575104231122349770882974818427591538551719990220347345614399639643257685591321500648437402084919467346049683842042993975696447711080289559063959271045082506968532103445241637971734173037224394103944153692310048043693502870706225319787902231218954548412018259
e = 65537
c = 1757914668604154089701710446907445787512346500378259224658947923217272944211214757488735053484213917067698715050010452193463598710989123020815295814709518742755820383364097695929549366414223421242599840755441311771835982431439073932340356341636346882464058493459455091691653077847776771631560498930589569988646613218910231153610031749287171649152922929066828605655570431656426074237261255561129432889318700234884857353891402733791836155496084825067878059001723617690872912359471109888664801793079193144489323455596341708697911158942505611709946252101670450796550313079139560281843612045681545992626944803230832776794454353639122595107671267859292222861367326121435154862607517890329925621367992667728899878422037182817860641530146234730196633237339901726508906733897556146751503097127672718192958642776389691940671356367304182825433592577899881444815062581163386947075887218537802483045756886019426749855723715192981635971943
leak = 153338022210585970687495444409227961261783749570114993931231317427634321118309600575903662678286698071962304436931371977179197266063447616304477462206528342008151264611040982873859583628234755013757003082382562012219175070957822154944231126228403341047477686652371523951028071221719503095646413530842908952071610518530005967880068526701564472237686095043481296201543161701644160151712649014052002012116829110394811586873559266763339069172495704922906651491247001057095314718709634937187619890550086009706737712515532076

CONST1 = 0xDEADBEEFCAFEBABE123456789ABCDEFFEDCBA9876543210
CONST2 = 0xCAFEBABEDEADBEEF123456789ABCDEF0123456789ABCDEF
CONST3 = 0x123456789ABCDEFFEDCBA9876543210FEDCBA987654321
MASK64 = (1 << 64) - 1
MOD128 = 1 << 128


def leak_func(p, q):
    return (
        ((p * CONST1) ^ (q * CONST2) ^ ((p & q) << 64) ^ ((p | q) << 48) ^ ((p ^ q) * CONST3))
        + ((p + q) % MOD128)
    ) ^ ((p * q) & MASK64)


cands = [(1, 1)]
for k in range(1, 1536):
    mod = 1 << (k + 1)
    need_n = n % mod
    need_leak = leak % mod
    new_cands = []
    seen = set()

    for p0, q0 in cands:
        for a in (0, 1):
            for b in (0, 1):
                pp = p0 | (a << k)
                qq = q0 | (b << k)
                if (pp * qq) % mod != need_n:
                    continue
                if leak_func(pp, qq) % mod != need_leak:
                    continue
                if (pp, qq) not in seen:
                    seen.add((pp, qq))
                    new_cands.append((pp, qq))

    cands = new_cands
    if not cands:
        raise SystemExit(f'[-] dead at bit {k}')

p, q = cands[0]
assert p * q == n
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
flag = m.to_bytes((m.bit_length() + 7) // 8, 'big')
print('[+] flag =', flag.decode())