题目

一个level1目录，内部是很多公钥文件，一个level2压缩包带密码，密码应该在level1解密拿到

level1

有一个README，看一下内容

我们需要先恢复message内容

有两个python脚本，看名称一个是生成message，另一个是加密

message

先看generate-plaintexts.py，分析一下原始明文的内容

这里我们可以得知share的格式是模数d : 余数k : 原始比特长度

1
2
3
d = 一个素数
k = S mod d
original_bits = 原消息长度

但是仔细看脚本里的Asmuth-Bloom并没有真正做标准的Asmuth-Bloom重构条件，本质上只是把秘密整数 S 拆成了很多个

也就是说后面只要拿到足够多组(di, ki)，就能直接用中国剩余定理把S还原出来

往后看生成的消息和share，先把message1.txt的内容被复制到 10 个plaintext文件的开头

message2到message10每个message都被分成10份share，分别放进对应的plaintext-xxx.txt

加密分析

继续看encrypt.py分析加密方式

当rsa模数位数大于等于2048时，先随机生成AES key，再RSA-OAEP加密这个AES key，然后AES-GCM 加密正文

当 RSA 模数位数小于2048时，直接RSA加密AES key，再AES-GCM加密正文

现在我们的思路就是，先找出多个能被破解的RSA公钥，解开对应的ciphertext，拿到多条share，再对每个message用CRT重建

公钥分析

先看一下所有公钥的特征

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
key-0.pem   4096 bits, e=65537
key-1.pem   2048 bits, e=65537
key-2.pem   2047 bits, e=65537
key-3.pem   2047 bits, e=65537
key-4.pem   2566 bits, e=65537
key-5.pem   198 bits,  e=3
key-6.pem   2047 bits, e=一个超大数
key-7.pem   2047 bits, e=65537
key-8.pem   2048 bits, e=65537
key-9.pem   4095 bits, e=65537
key-10.pem  4095 bits, e=65537
key-11.pem  4096 bits, e=65537
key-12.pem  2047 bits, e=一个超大数
key-13.pem  2048 bits, e=65537
key-14.pem  4095 bits, e=65537
key-15.pem  2565 bits, e=65537
key-16.pem  2048 bits, e=65537
key-17.pem  2047 bits, e=一个超大数
key-18.pem  2048 bits, e=65537
key-19.pem  4096 bits, e=65537

1、key-5.pem很小，可以直接分解

2、有几对大小相同，可能存在共因子或者相近素数

3、key-6、key-12、key-17 的e很大

两两求gcd（key 1、2、4、15）

编写脚本批量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#!/usr/bin/env python3
from math import gcd
from pathlib import Path
import argparse
from Crypto.PublicKey import RSA


def load_keys(key_dir: Path):
    keys = []
    for pem in sorted(key_dir.glob("key-*.pem"), key=lambda p: int(p.stem.split("-")[1])):
        idx = int(pem.stem.split("-")[1])
        key = RSA.import_key(pem.read_bytes())
        keys.append({
            "idx": idx,
            "path": pem,
            "n": key.n,
            "e": key.e,
            "bits": key.n.bit_length(),
        })
    return keys


def main():

    key_dir = Path("level1").resolve()
    keys = load_keys(key_dir)

    if not keys:
        raise SystemExit(f"No key-*.pem found in {key_dir}")

    hits = []
    for i in range(len(keys)):
        for j in range(i + 1, len(keys)):
            k1 = keys[i]
            k2 = keys[j]
            g = gcd(k1["n"], k2["n"])
            if g == 1:
                continue

            q1 = k1["n"] // g
            q2 = k2["n"] // g
            hits.append((k1, k2, g, q1, q2))

            print(f"[!] shared factor found: key-{k1['idx']}.pem <-> key-{k2['idx']}.pem")
            print(f"    gcd bits : {g.bit_length()}")
            print(f"    q1  bits : {q1.bit_length()}")
            print(f"    q2  bits : {q2.bit_length()}")
            print(f"    check #1 : {g * q1 == k1['n']}")
            print(f"    check #2 : {g * q2 == k2['n']}")
            print()

    if not hits:
        print("[-] no non-trivial gcd found")
        return

    print("[+] summary")
    for k1, k2, g, q1, q2 in hits:
        print(
            f"    key-{k1['idx']} / key-{k2['idx']} -> "
            f"shared {g.bit_length()} bits, others {q1.bit_length()} / {q2.bit_length()} bits"
        )


if __name__ == "__main__":
    main()

共有两组存在共因子，接下来通过gcd恢复私钥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#!/usr/bin/env python3
from math import gcd
from pathlib import Path
from Crypto.PublicKey import RSA


def load_public_keys(level1_dir: Path):
    keys = {}
    for pem in sorted(level1_dir.glob("key-*.pem"), key=lambda p: int(p.stem.split("-")[1])):
        idx = int(pem.stem.split("-")[1])
        keys[idx] = RSA.import_key(pem.read_bytes())
    return keys


def main():
    root = Path(__file__).resolve().parent
    level1_dir = root / "level1"
    out_dir = root / "recovered_keys_from_gcd"
    out_dir.mkdir(exist_ok=True)

    keys = load_public_keys(level1_dir)
    indices = sorted(keys)
    recovered = {}

    print(f"[+] scanning {len(indices)} public keys for shared factors")
    print()

    for i in range(len(indices)):
        for j in range(i + 1, len(indices)):
            a = indices[i]
            b = indices[j]
            n1 = keys[a].n
            n2 = keys[b].n
            g = gcd(n1, n2)
            if g == 1:
                continue

            print(f"[!] shared factor found: key-{a}.pem <-> key-{b}.pem")
            print(f"    gcd bits = {g.bit_length()}")

            for idx, other in ((a, b), (b, a)):
                p = int(g)
                q = int(keys[idx].n // g)
                phi = (p - 1) * (q - 1)
                d = pow(keys[idx].e, -1, phi)
                priv = RSA.construct((keys[idx].n, keys[idx].e, d, p, q))
                recovered[idx] = {
                    "p": p,
                    "q": q,
                    "d": d,
                    "other": other,
                    "priv": priv,
                }
                out_path = out_dir / f"key-{idx}-private.pem"
                out_path.write_bytes(priv.export_key())
                print(f"    [OK] recovered key-{idx}.pem using gcd with key-{other}.pem")
                print(f"         wrote {out_path.name}")
            print()

    print("[+] summary")
    if not recovered:
        print("    no gcd-vulnerable keys found")
        return

    for idx in sorted(recovered):
        info = recovered[idx]
        print(
            f"    key-{idx}.pem: p_bits={info['p'].bit_length()} "
            f"q_bits={info['q'].bit_length()} d_bits={info['d'].bit_length()}"
        )


if __name__ == "__main__":
    main()

成功恢复4个私钥，解密得到两份plaintext

小模数直接因式分解（key 5）

直接写脚本分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#!/usr/bin/env python3
from pathlib import Path
from Crypto.PublicKey import RSA
from sympy import factorint


def load_public_keys(level1_dir: Path):
    keys = {}
    for pem in sorted(level1_dir.glob("key-*.pem"), key=lambda p: int(p.stem.split("-")[1])):
        idx = int(pem.stem.split("-")[1])
        keys[idx] = RSA.import_key(pem.read_bytes())
    return keys


def main():
    root = Path(__file__).resolve().parent
    level1_dir = root / "level1"
    out_dir = root / "recovered_keys_small_modulus"
    out_dir.mkdir(exist_ok=True)

    keys = load_public_keys(level1_dir)

    print("[+] scanning for small RSA moduli")
    print()

    recovered = {}
    for idx in sorted(keys):
        key = keys[idx]
        bits = key.n.bit_length()

        # 这里只打非常小的模数，避免误伤大数
        if bits > 256:
            continue

        print(f"[+] trying key-{idx}.pem ({bits} bits)")
        factors_dict = factorint(key.n)

        factors = []
        for prime, exp in factors_dict.items():
            factors.extend([int(prime)] * exp)

        prod = 1
        for f in factors:
            prod *= f

        if prod != key.n:
            print("    [-] factorization check failed")
            print()
            continue

        phi = 1
        for f in factors:
            phi *= (f - 1)

        try:
            d = pow(key.e, -1, phi)
        except ValueError:
            print("    [-] e is not invertible modulo phi")
            print()
            continue

        recovered[idx] = {
            "factors": factors,
            "d": d,
        }

        out_path = out_dir / f"key-{idx}-private-info.txt"
        lines = [
            f"key = key-{idx}.pem",
            f"n_bits = {bits}",
            f"e = {key.e}",
            f"d = {d}",
            f"factor_count = {len(factors)}",
            "factors =",
        ]
        lines.extend(str(f) for f in factors)
        out_path.write_text("\n".join(lines) + "\n")

        print(f"    [OK] factors found: {len(factors)} prime factors")
        print(f"    [OK] wrote {out_path.name}")
        print()

    print("[+] summary")
    if not recovered:
        print("    no small modulus key was factored")
        return

    for idx in sorted(recovered):
        info = recovered[idx]
        bit_list = ", ".join(str(f.bit_length()) for f in info["factors"])
        print(f"    key-{idx}.pem -> factor bits [{bit_list}]")


if __name__ == "__main__":
    main()

1
2
3
4
5
6
7
8
n_bits = 198
e = 3
d = 223190228465821694677907677521533419817411950213806180649643
factor_count = 3
factors =
1528159911436197621287
15950473204537742369
13734854446830088769

但是这一步得到的结果一个都解不出来，应该是误导

Fermat分解（key 3、7、13、18）

我们之前公钥分析的时候看到了有几组2047/2048位模数，很像正常双素数RSA的大小，尝试Fermat分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#!/usr/bin/env python3
from math import isqrt
from pathlib import Path
from Crypto.PublicKey import RSA


def load_public_keys(level1_dir: Path):
    keys = {}
    for pem in sorted(level1_dir.glob("key-*.pem"), key=lambda p: int(p.stem.split("-")[1])):
        idx = int(pem.stem.split("-")[1])
        keys[idx] = RSA.import_key(pem.read_bytes())
    return keys


def fermat_factor(n, max_steps=200000):
    a = isqrt(n)
    if a * a < n:
        a += 1
    for step in range(max_steps + 1):
        b2 = a * a - n
        b = isqrt(b2)
        if b * b == b2:
            p = int(a - b)
            q = int(a + b)
            if p * q == n:
                return p, q, step
        a += 1
    return None


def main():
    root = Path(__file__).resolve().parent
    level1_dir = root / "level1"
    out_dir = root / "recovered_keys_fermat"
    out_dir.mkdir(exist_ok=True)

    keys = load_public_keys(level1_dir)

    print("[+] scanning keys with Fermat factorization")
    print()

    recovered = {}
    for idx in sorted(keys):
        key = keys[idx]
        bits = key.n.bit_length()

        # Fermat 主要给中等/大模数用，小模数前一步已处理
        if bits < 512:
            continue

        print(f"[+] trying key-{idx}.pem ({bits} bits)")
        result = fermat_factor(key.n)
        if not result:
            print("    [-] not factorable within step limit")
            print()
            continue

        p, q, step = result
        phi = (p - 1) * (q - 1)
        try:
            d = pow(key.e, -1, phi)
        except ValueError:
            print("    [-] e is not invertible modulo phi")
            print()
            continue

        priv = RSA.construct((key.n, key.e, d, p, q))
        pem_path = out_dir / f"key-{idx}-private.pem"
        info_path = out_dir / f"key-{idx}-info.txt"
        pem_path.write_bytes(priv.export_key())
        info_path.write_text(
            "\n".join([
                f"key = key-{idx}.pem",
                f"n_bits = {bits}",
                f"method = Fermat",
                f"step = {step}",
                f"p_bits = {p.bit_length()}",
                f"q_bits = {q.bit_length()}",
                f"d_bits = {d.bit_length()}",
                f"p = {p}",
                f"q = {q}",
                f"d = {d}",
            ]) + "\n"
        )
        recovered[idx] = {"step": step, "p": p, "q": q, "d": d}
        print(f"    [OK] factorable by Fermat at step {step}")
        print(f"    [OK] wrote {pem_path.name}")
        print()

    print("[+] summary")
    if not recovered:
        print("    no key was factored by Fermat")
        return
    for idx in sorted(recovered):
        info = recovered[idx]
        print(
            f"    key-{idx}.pem -> step={info['step']} "
            f"p_bits={info['p'].bit_length()} q_bits={info['q'].bit_length()}"
        )


if __name__ == "__main__":
    main()

成功恢复4个私钥，解密得到3份plaintext

中国剩余定理恢复message

到这一步我们已经拿到了5份plaintext

内容和我们之前分析的一致，对应的列数分别如下

先把share按message对齐

对每条message做CRT恢复

level1密码

得到密码：9Zr4M1ThwVCHe4nHnmOcilJ8

level2

用密码解压后得到

level3仍然是个带密码的压缩包，先来看这个脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import gmpy2
import hashlib
from Crypto.Util.number import *

def generate_polynomial_coefficients(degree, bound=100):
    coefficients = []
    for i in range(degree + 1):
        coefficients.append(getRandomRange(-bound, bound))
    while coefficients[-1] == 0:
        coefficients[-1] = getRandomRange(-bound, bound)
    return coefficients

def evaluate_polynomial(coeffs, x, n):
    result = 0
    power = 1
    for i, coeff in enumerate(coeffs):
        result = (result + coeff * power) % n
        power = (power * x) % n
    return result

p = getPrime(512)
q = getPrime(512)
d = getPrime(180)  

lam = (p-1) * (q-1) // gmpy2.gcd(p-1, q-1)

e = gmpy2.invert(d, lam)

n = p * q
m1 = bytes_to_long(b"Secret message: " + b"A" * 16)

poly2_coeffs = generate_polynomial_coefficients(2)
poly3_coeffs = generate_polynomial_coefficients(3)

m2 = evaluate_polynomial(poly2_coeffs, m1, n)
m3 = evaluate_polynomial(poly3_coeffs, m1, n)

c1 = pow(m1, e, n)
c2 = pow(m2, e, n)
c3 = pow(m3, e, n)

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

poly2_coeffs_display = poly2_coeffs.copy()
poly2_coeffs_display[0] = "?"  
poly3_coeffs_display = poly3_coeffs.copy()
poly3_coeffs_display[0] = "?"  

print("n =", n)
print("e =", e)
print("c1 =", c1)
print("c2 =", c2)
print("c3 =", c3)
print("poly2_coeffs =", poly2_coeffs_display)  
print("poly3_coeffs =", poly3_coeffs_display)  

# n = 99573363048275234764231402769464116416087010014992319221201093905687439933632430466067992037046120712199565250482197004301343341960655357944577330885470918466007730570718648025143561656395751518428630742587023267450633824636936953524868735263666089452348466018195099471535823969365007120680546592999022195781
# e = 12076830539295193533033212232487568888200963123024189287629493480058638222146972496110814372883829765692623107191129306190788976704250502316265439996891764101447017190377014980293589797403095249538391534986638973035285900867548420192211241163778919028921502305790979880346050428839102874086046622833211913299
# c1 = 88537483899519116785221065592618063396859368769048931371104532271282451393564912999388648867349770059882231896252136530442609316120059139869000411598215669228402275014417736389191093818032356471508269901358077592526362193180661405990147957408129845474938259771860341576649904811782733150222504695142224907008
# c2 = 94664119872856479106437852390497826718494891787231788048637569911820802241271385500237521849783257742020074596801243551199558780516078698265978603364906102405513805258523893161481880920117078266554039648951735640682344760175446065823258414274759467738667667682764189886842676476993302026419523097311062869020
# c3 = 17452842791128500883484238194649202112170709841838938382334668085116735124742824096780522905501631340623564870573855325492444043679562915249332054460794149403631363005265204604824764244033832504758820981926933304283896441280291037649477532990161765794023799333588888734136298348520144818810380374971149851767
# poly2_coeffs = ['?', -36, -94]
# poly3_coeffs = ['?', -11, -20, 11]

task.py分析

1、生成512-bit的p,q

2、生成一个180-bit的私钥指数d

3、构造公钥：lam = lcm(p-1, q-1)；e = invert(d, lam)

4、计算c1、c2、c3

最终密码是sha256(str(p + q).encode()).hexdigest()，也就是说固定为sha256(str(p + q))，我们只需要分解n得到p、q即可

这道题首先想到从c1、c2、c3和多项式关系入手，但是多项式常数项被隐藏了，e也不是小指数，不一定能够快速分解，继续往下看

d只有180位，而n有1024位，那么n^(1/4) ≈ 2^256，d远远小于这个量级，也就是小私钥RSA，这里我们很容易联想到Wiener攻击

但这里并不是标准的Wiener，正常e为invert(d, phi(n))

标准Wiener推导很多时候默认的是ed - 1 = k * φ(n)

这里变成了ed - 1 = k * λ(n)

也就是说ed - 1是λ(n)的倍数，不一定是φ(n)的倍数

所以普通版Wiener套公式可能不直接命中，但小私钥的问题还是存在

概括一下思路：

1、先把它认成小私钥RSA，也就是Wiener家族问题

2、对e/n做连分数展开，拿到一串收敛分数候选

3、因为这里用的是λ(n)而不是φ(n)，所以不能死套标准Wiener判定，而是做一个小修正：

  • 从收敛分数里拿候选d

  • 允许它和真实d差一个很小的因子修正

  • 然后利用ed - 1是λ(n)的倍数这一点去反向分解n

为什么拿到ed-1的倍数就能分解n呢，因为如果拿到了某个数M是λ(n)的倍数，那么对于任意和n互素的a：a^M≡1modn

这就和RSA/群阶有关，然后可以像Miller-Rabin/平方根分解那样，把M写成：M=2^s*t

不断平方，寻找非平凡平方根，从而求出：gcd(x-1,n)

最后把n拆开，所以只要从小私钥候选里拿到一个正确的ed-1，就能把n因式分解

关键信息有：n、e、d很小、flag为sha256(str(p+q))

修正版Wiener分解p,q

编写脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#!/usr/bin/env python3
from math import gcd
from pathlib import Path
import json
import random

# 来自 level2/task.py 注释区的公开参数
N = 99573363048275234764231402769464116416087010014992319221201093905687439933632430466067992037046120712199565250482197004301343341960655357944577330885470918466007730570718648025143561656395751518428630742587023267450633824636936953524868735263666089452348466018195099471535823969365007120680546592999022195781
E = 12076830539295193533033212232487568888200963123024189287629493480058638222146972496110814372883829765692623107191129306190788976704250502316265439996891764101447017190377014980293589797403095249538391534986638973035285900867548420192211241163778919028921502305790979880346050428839102874086046622833211913299


def rational_to_contfrac(x: int, y: int):
    out = []
    while y:
        a = x // y
        out.append(a)
        x, y = y, x - a * y
    return out


def convergents_from_contfrac(frac):
    n0, d0 = 0, 1
    n1, d1 = 1, 0
    for a in frac:
        n2 = a * n1 + n0
        d2 = a * d1 + d0
        yield n2, d2
        n0, d0, n1, d1 = n1, d1, n2, d2


def factor_from_lambda_multiple(n: int, m: int, trials: int = 80):
    if m <= 0:
        return None

    t = m
    s = 0
    while t % 2 == 0:
        t //= 2
        s += 1

    if s == 0:
        return None

    bases = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    bases += [random.randrange(2, n - 1) for _ in range(trials)]

    for a in bases:
        g = gcd(a, n)
        if 1 < g < n:
            return g, n // g

        x = pow(a, t, n)
        if x == 1 or x == n - 1:
            continue

        for _ in range(s):
            y = pow(x, 2, n)
            if y == 1:
                p = gcd(x - 1, n)
                if 1 < p < n:
                    return p, n // p
                break
            if y == n - 1:
                break
            x = y
    return None


def main():
    root = Path(__file__).resolve().parent
    out_json = root / "step5_level2_factor_result.json"
    out_txt = root / "step5_level2_factor_result.txt"

    frac = rational_to_contfrac(E, N)

    print("[+] running modified Wiener attack on level2")
    print(f"[+] convergents: {len(frac)}")
    print()

    # 这里的关键：候选分母可能是 g * d，所以尝试除以一个小因子 g
    small_divisors = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32]

    checked = 0
    for idx, (k, q_candidate) in enumerate(convergents_from_contfrac(frac), start=1):
        if q_candidate.bit_length() > 220:
            break

        for g in small_divisors:
            if q_candidate % g != 0:
                continue

            d = q_candidate // g
            if d <= 0:
                continue

            m = E * d - 1
            checked += 1

            fac = factor_from_lambda_multiple(N, m)
            if not fac:
                continue

            p, q = fac
            if p * q != N:
                continue
            if p > q:
                p, q = q, p

            result = {
                "method": "modified_wiener_lambda",
                "convergent_index": idx,
                "small_divisor_g": g,
                "d": str(d),
                "d_bits": d.bit_length(),
                "p": str(p),
                "q": str(q),
                "p_bits": p.bit_length(),
                "q_bits": q.bit_length(),
                "n": str(N),
                "e": str(E),
            }
            out_json.write_text(json.dumps(result, ensure_ascii=False, indent=2) + "\n")
            out_txt.write_text(
                "\n".join([
                    "[level2 factor result]",
                    f"method = {result['method']}",
                    f"convergent_index = {idx}",
                    f"small_divisor_g = {g}",
                    f"d_bits = {d.bit_length()}",
                    f"p_bits = {p.bit_length()}",
                    f"q_bits = {q.bit_length()}",
                    f"p = {p}",
                    f"q = {q}",
                ]) + "\n"
            )

            print(f"[OK] found factors at convergent #{idx}, g={g}")
            print(f"     d bits = {d.bit_length()}")
            print(f"     p bits = {p.bit_length()}")
            print(f"     q bits = {q.bit_length()}")
            print(f"[+] wrote {out_json}")
            print(f"[+] wrote {out_txt}")
            return

    print(f"[-] not found after checking {checked} candidates")


if __name__ == "__main__":
    main()

1
2
3
4
5
6
7
8
method = modified_wiener_lambda
convergent_index = 108
small_divisor_g = 4
d_bits = 180
p_bits = 512
q_bits = 512
p = 9107629749578703007521753435128188255997152813554367948373413785978810344628038189563213036161837882971963700600044412434325055960560499599730973768232229
q = 10932961240863053140021227333995503042196506533433133299916502568289020826078008576745192725272664686384293526720057562101790406102729886343233171385110689

成功分解p、q

从p,q计算下一层密码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#!/usr/bin/env python3
from pathlib import Path
import json
import hashlib


def main():
    root = Path(__file__).resolve().parent
    in_json = root / "step5_level2_factor_result.json"
    out_txt = root / "step5_level2_next_pass.txt"

    if not in_json.exists():
        raise SystemExit(f"Missing input file: {in_json}")

    result = json.loads(in_json.read_text())
    p = int(result["p"])
    q = int(result["q"])
    s = p + q
    digest = hashlib.sha256(str(s).encode()).hexdigest()
    password = f"next pass is {digest}"

    out_txt.write_text(
        "\n".join([
            "[level2 next pass]",
            f"p_plus_q = {s}",
            f"sha256(str(p+q)) = {digest}",
            password,
        ]) + "\n"
    )

    print(f"[+] p + q = {s}")
    print(f"[+] sha256(str(p+q)) = {digest}")
    print(password)
    print(f"[+] wrote {out_txt}")


if __name__ == "__main__":
    main()

level2密码

1
2
3
[+] p + q = 20040590990441756147542980769123691298193659346987501248289916354267831170706046766308405761434502569356257227320101974536115462063290385942964145153342918
[+] sha256(str(p+q)) = 2aa9c360df99cbb4209e4dbab5a9f9ffd86d34906e3206fecfdabf0bb7aeb5ac
next pass is 2aa9c360df99cbb4209e4dbab5a9f9ffd86d34906e3206fecfdabf0bb7aeb5ac

得到密码：2aa9c360df99cbb4209e4dbab5a9f9ffd86d34906e3206fecfdabf0bb7aeb5ac

level3

解压得到level3脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from Crypto.Util.number import getPrime, bytes_to_long

p = getPrime(1536)
q = getPrime(1536)
n = p * q
e = 65537

flag = b"dart{**************}"
c = pow(bytes_to_long(flag), e, n)

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

leak = ( (p * CONST1) ^ (q * CONST2) ^ ((p & q) << 64) ^ ((p | q) << 48) ^ ((p ^ q) * CONST3) ) + ((p + q) % MOD128) ^ ((p * q) & MASK64)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"leak = {leak}")

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

task.py分析

这一层题目给了个leak：

1
leak = ( (p * CONST1) ^ (q * CONST2) ^ ((p & q) << 64) ^ ((p | q) << 48) ^ ((p ^ q) * CONST3) ) + ((p + q) % MOD128) ^ ((p * q) & MASK64)

而且我们已知：n=p*q

这意味着n给了p*q的所有低位约束，leak又给了你p,q混合后的额外低位约束

这类题很适合做从低位开始，一位一位枚举p,q的bit，逐步筛掉错误分支，也就是bitlifting/low-bitreconstruction

假设已经猜出了p,q的低k位，那么可以检查p*q mod 2^k是否等于n mod 2^k

也可以检查leak的低k位是否匹配，如果都匹配就保留这个候选，如果不匹配就裁掉，由于这题约束很强，实际会很快收敛到唯一一组p,q

我们的思路就很清晰了，从低位恢复 p,q，计算d = e^{-1} mod (p-1)(q-1)、m = c^d mod n

得到最终 flag

bit-lifting分解p、q

编写bit-lifting脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#!/usr/bin/env python3
from pathlib import Path
import json


MASK64 = (1 << 64) - 1


def main():
    root = Path(__file__).resolve().parent
    in_json = root / "step6_level3_params.json"
    out_json = root / "step6_level3_factor_result.json"
    out_txt = root / "step6_level3_factor_result.txt"

    params = json.loads(in_json.read_text())
    n = int(params["n"])
    leak = int(params["leak"])
    A = int(params["const1"])
    B = int(params["const2"])
    C = int(params["const3"])

    target = leak ^ (n & MASK64)

    def t_low(p: int, q: int, k: int):
        mask = (1 << k) - 1
        x = ((p * A) ^ (q * B) ^ ((p & q) << 64) ^ ((p | q) << 48) ^ ((p ^ q) * C))
        s = (p + q) & ((1 << 128) - 1)
        return (x + s) & mask

    cands = {(1, 1)}
    print("[+] starting low-bit lifting")

    for k in range(1, 1536):
        mask = (1 << (k + 1)) - 1
        target_n = n & mask
        target_t = target & mask
        nxt = set()

        for p, q in cands:
            for bp in (0, 1):
                for bq in (0, 1):
                    pp = p | (bp << k)
                    qq = q | (bq << k)
                    if (pp * qq) & mask != target_n:
                        continue
                    if t_low(pp, qq, k + 1) != target_t:
                        continue
                    nxt.add((pp, qq))

        cands = nxt
        if not cands:
            raise SystemExit(f"No candidates left at bit {k + 1}")
        if len(cands) > 10000:
            raise SystemExit(f"Too many candidates at bit {k + 1}: {len(cands)}")
        if (k + 1) % 128 == 0 or k < 20:
            print(f"    bits {k + 1}: {len(cands)} candidate(s)")

    if len(cands) != 1:
        raise SystemExit(f"Expected exactly 1 final candidate, got {len(cands)}")

    p, q = next(iter(cands))
    if p > q:
        p, q = q, p

    if p * q != n:
        raise SystemExit("Recovered factors do not multiply back to n")

    result = {
        "method": "bit_lifting_from_n_and_leak",
        "p": str(p),
        "q": str(q),
        "p_bits": p.bit_length(),
        "q_bits": q.bit_length(),
    }
    out_json.write_text(json.dumps(result, ensure_ascii=False, indent=2) + "\n")
    out_txt.write_text(
        "\n".join([
            "[level3 factor result]",
            f"method = {result['method']}",
            f"p_bits = {p.bit_length()}",
            f"q_bits = {q.bit_length()}",
            f"p = {p}",
            f"q = {q}",
        ]) + "\n"
    )

    print(f"[OK] recovered p and q")
    print(f"[+] wrote {out_json}")
    print(f"[+] wrote {out_txt}")


if __name__ == "__main__":
    main()

1
2
3
4
5
method = bit_lifting_from_n_and_leak
p_bits = 1536
q_bits = 1536
p = 1707409731376314795999673399644896831773113631916193464259935767498639233398656041693151647684636824933980722820855222725690297941643517419906221825861730073489224554305559179283922396783611098752937409830400941648419260598819028494552512482509512236956144966960506482426135682006340832164470103583395459735070745893411476234089404558564875229768662461905874150673437533528191205114624917667791799816966017830043080586780620851038224028348188524334138215456616749
q = 2141573345627585371553787251648053741410445905256360451856340437573603641142767425814601119975790360922588103737873793493614076837288293103777795188569218362732735616305950754442774259470221411601014586798147206055920156749954034989669601788173864983031343224818275175942690789067112461738865540083192521838275489406927966810543155749231403489582462847315255827362973792259727757243033997062234932720733059810639405260209480382634232650958389211775287627610180991

成功分解

RSA解密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#!/usr/bin/env python3
from pathlib import Path
import json
from Crypto.Util.number import long_to_bytes


def main():
    root = Path(__file__).resolve().parent
    params_json = root / "step6_level3_params.json"
    factors_json = root / "step6_level3_factor_result.json"
    out_txt = root / "step6_level3_flag.txt"

    params = json.loads(params_json.read_text())
    factors = json.loads(factors_json.read_text())

    n = int(params["n"])
    e = int(params["e"])
    c = int(params["c"])
    p = int(factors["p"])
    q = int(factors["q"])

    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)
    m = pow(c, d, n)
    flag = long_to_bytes(m).decode("utf-8")

    out_txt.write_text(
        "\n".join([
            "[level3 flag]",
            f"phi_bits = {phi.bit_length()}",
            f"d_bits = {d.bit_length()}",
            f"flag = {flag}",
        ]) + "\n"
    )

    print(flag)
    print(f"[+] wrote {out_txt}")


if __name__ == "__main__":
    main()

FLAG

得到flag：dart{379c9308-e9a8-45a1-bd55-45bbd822e86d}