Crypto 方向

题目1：签到

不知道那串疑似base32的密文什么意思，在Google地图输入坐标发现是卡塔尔的一个空军基地，然后结合2-28的日期，搜索新闻能找到真实承诺4
ps：这题出得何意味？？？

题目2：check in

在源代码中，d的生成是在RR上的，也就是RealField(53),是53-bit的双精度浮点数，那么之后用Integar转回整数的时候就只保留了高53位bit的数据
这一点在python中也可以直接实现，进而恢复d，然后利用ed和phi的关系可以得出phi，再结合N=p*q解二元方程得到p和q，之后md5得到flag
exp：

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
import math
from hashlib import md5

# 题目提供的已知信息
e = 20285928988408708385825788658664300305494782819689883492429762785687493161646901961627732482030570554944571523044008931416609595056746847083499405860944240804200816473153171825246196297214879750749954991916614158499347588230595409852985660426387332691700171974951765953937059128044510635005259571262430221092123685629379451869171518153057333553882827808279895371867053070597655168641441209936240962391624079704514097507822408340977683148014817264999772615710237278286803551400605422497036878844692741788304043681532328471441465596285604159664321904195632202009921776619257725630740166796422445907541165144233376010917
N = 162318864198120848289602513685294100213662002310524040016141267082602211702801751627271587107738223466644399363879018058536864307889254050305605097781721847474240769410050480646447538698253600786017599233831714710010395996308361674973789283465587010960323042209564459904257042660293061844258544118566558516881

# 1. 利用相同的浮点数精度恢复 d
d_float = float(N) ** 0.47
m, exp = math.frexp(d_float)
M = int(m * (2**53))
E = exp - 53

# 预估 phi_N 近似值 (N^2 + 2*N^1.5)，用于后续精准计算 k 
phi_approx = N**2 + 2 * math.isqrt(N**3)

print("正在搜索并重构密钥，请稍候...")
found = False
for i in range(-5000, 5000):  # 覆盖不同数学库微小的 ULP 偏差
    M_test = M + i
    d_test = M_test * (2**E)
    
    # 估算 k 
    k_est = (e * d_test) // phi_approx
    
    for k in range(k_est - 2, k_est + 3):
        if k > 0 and (e * d_test - 1) % k == 0:
            phi_N = (e * d_test - 1) // k
            
            # 2. 求解 S = p + q
            A = 1
            B = N + 1
            C = N**2 - N + 1 - phi_N
            
            delta = B**2 - 4*A*C
            if delta >= 0:
                sqrt_delta = math.isqrt(delta)
                if sqrt_delta**2 == delta:
                    S = (-B + sqrt_delta) // 2
                    
                    if S > 0:
                        # 3. 求解 p, q
                        delta2 = S**2 - 4*N
                        if delta2 >= 0:
                            sqrt_delta2 = math.isqrt(delta2)
                            if sqrt_delta2**2 == delta2:
                                p = (S + sqrt_delta2) // 2
                                q = (S - sqrt_delta2) // 2
                                
                                flag_content = str(p + q).encode()
                                flag = 'flag{' + md5(flag_content).hexdigest() + '}'
                                print(f"\n[+] 成功解密！")
                                print(f"p = {p}")
                                print(f"q = {q}")
                                print(f"Flag: {flag}")
                                found = True
                                break
        if found: break
    if found: break

if not found:
    print("[-] 尚未找到，请尝试扩大搜索范围。")

flag：flag{563ca40e34c288a7fa6a0384b69ccac4}

题目3：尽人事，听天命

看起来花里花哨的，实质就是MT19937状态泄露问题，有2495本命书，说明624个32位基本全泄露了，除了第624块的最后8位，需要爆破一下，至此恢复random的状态
然后可以得到pull(64)是第625块和626块拼起来，pull(32)是第627块，再一步一步逆推得到yin和yang
exp：

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import re
import random
import hashlib
import math
from collections import Counter

BOOK_PATH = "命书.txt"


def unshift_right_xor(y: int, shift: int) -> int:
    x = 0
    for i in range(31, -1, -1):
        bit = (y >> i) & 1
        if i + shift <= 31:
            bit ^= (x >> (i + shift)) & 1
        x |= bit << i
    return x & 0xffffffff


def unshift_left_xor_mask(y: int, shift: int, mask: int) -> int:
    x = 0
    for i in range(32):
        bit = (y >> i) & 1
        if i - shift >= 0 and ((mask >> i) & 1):
            bit ^= (x >> (i - shift)) & 1
        x |= bit << i
    return x & 0xffffffff


def untemper(y: int) -> int:
    y = unshift_right_xor(y, 18)
    y = unshift_left_xor_mask(y, 15, 0xEFC60000)
    y = unshift_left_xor_mask(y, 7, 0x9D2C5680)
    y = unshift_right_xor(y, 11)
    return y & 0xffffffff


def parse_book(path: str):
    text = open(path, "r", encoding="utf-8").read()
    omens = list(map(int, re.findall(r"天命：(\d+)", text)))
    seal_a = int(re.search(r"阴阳交积封印：(\d+)", text).group(1))
    seal_b = int(re.search(r"阴阳离合封印：(\d+)", text).group(1))
    return omens, seal_a, seal_b


def build_outputs(omens):
    full_count = len(omens) // 4
    outputs = []
    for i in range(full_count):
        a, b, c, d = omens[i * 4:(i + 1) * 4]
        x = a | (b << 8) | (c << 16) | (d << 24)
        outputs.append(x)
    remain = omens[full_count * 4:]
    return outputs, remain


# ---------------- Miller-Rabin + Pollard Rho ----------------

def is_probable_prime(n: int) -> bool:
    if n < 2:
        return False
    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    for p in small_primes:
        if n % p == 0:
            return n == p

    d = n - 1
    s = 0
    while d % 2 == 0:
        s += 1
        d //= 2

    # 64-bit deterministic bases
    for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
        if a % n == 0:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        ok = False
        for _ in range(s - 1):
            x = (x * x) % n
            if x == n - 1:
                ok = True
                break
        if not ok:
            return False
    return True


def pollard_rho(n: int) -> int:
    if n % 2 == 0:
        return 2
    if n % 3 == 0:
        return 3

    while True:
        c = random.randrange(1, n)
        f = lambda x: (pow(x, 2, n) + c) % n
        x = random.randrange(0, n)
        y = x
        d = 1
        while d == 1:
            x = f(x)
            y = f(f(y))
            d = math.gcd(abs(x - y), n)
        if d != n:
            return d


def factor_rec(n: int, out: list):
    if n == 1:
        return
    if is_probable_prime(n):
        out.append(n)
        return
    d = pollard_rho(n)
    factor_rec(d, out)
    factor_rec(n // d, out)


def factorize(n: int):
    facs = []
    factor_rec(n, facs)
    return Counter(facs)


def enum_divisors(factors):
    divs = [1]
    for p, e in factors.items():
        cur = []
        mul = 1
        for _ in range(e + 1):
            for d in divs:
                cur.append(d * mul)
            mul *= p
        divs = cur
    return divs


def recover_yin_yang(bound: int, trace: int):
    factors = factorize(bound)
    divs = enum_divisors(factors)

    for yin in divs:
        yang = bound // yin
        if (yin ^ (yang >> 6)) == trace:
            return yin, yang
        if (yang ^ (yin >> 6)) == trace:
            return yang, yin

    raise ValueError("No valid yin/yang found")


def main():
    omens, seal_a, seal_b = parse_book(BOOK_PATH)
    outputs, remain = build_outputs(omens)

    if len(outputs) != 623 or len(remain) != 3:
        raise ValueError(
            f"unexpected data length: outputs={len(outputs)}, remain={len(remain)}"
        )

    low24 = remain[0] | (remain[1] << 8) | (remain[2] << 16)

    for hi in range(256):
        out624 = low24 | (hi << 24)
        state_words = [untemper(x) for x in outputs + [out624]]

        r = random.Random()
        r.setstate((3, tuple(state_words + [624]), None))

        rand64 = r.getrandbits(64)
        rand32 = r.getrandbits(32)

        bound = seal_a ^ rand64
        trace = seal_b ^ rand32

        try:
            yin, yang = recover_yin_yang(bound, trace)
        except Exception:
            continue

        lo, hi2 = sorted((yin, yang))
        flag = "DesCTF{" + hashlib.md5(f"{lo}|{hi2}".encode()).hexdigest() + "}"

        print("[+] recovered high byte of 624th output:", hex(hi))
        print("[+] pull(64) =", hex(rand64))
        print("[+] pull(32) =", hex(rand32))
        print("[+] bound =", bound)
        print("[+] trace =", trace)
        print("[+] yin =", yin)
        print("[+] yang =", yang)
        print("[+] flag =", flag)
        return

    print("[-] failed")


if __name__ == "__main__":
    main()

运行结果：[+] recovered high byte of 624th output: 0x0
[+] pull(64) = 0x5fe866bfbbacd228
[+] pull(32) = 0xf0c53d1b
[+] bound = 10628364105245574731
[+] trace = 2540299101
[+] yin = 2492562577
[+] yang = 4264031003
[+] flag = DesCTF{28dc9b687456ef5897c4477a98a8bdbf}

题目4：Low Bits，High Risk

ECDSA的数字签名泄露nonce问题，每条消息只泄露3bit，把模运算表示成线性方程的样子
然后构造一个嵌入格
![](/img/2026-DesCTF-crypto-writeup/Low Bits，High Risk/格.png)
系数是(z1,z2,...,z3,−d,1)(z1,z2,...,z3,-d,1)
最后的结果短向量是：(q−2Kt1,q−2Kt2,...,q−2Ktm,−d,q)(q-2Kt1,q-2Kt2,...,q-2Ktm,-d,q)
对正确私钥，整体比较规整，而错误私钥会使向量很长很乱，接下来LLL和BKZ都行
exp：

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import ast
import hashlib
from fpylll import IntegerMatrix, LLL, BKZ
from ecdsa import curves, ellipticcurve

RAW = r"""
0x8e0a0071e8cf437efec4233ff8444a4ff8adba2f
0xa869fce702b70799c443b450a4d41cc4f65b3eee
(0x525931a9ff8ef95025939a57275ecedc2730421f, 0x5288ed7146c188ebda9b6c8909726c3d6f957891, 0x334c301c2d861fa8cceecabc542a5cb7dd7df7d9, 0x6),
(0x4b21047e1112dbfee487b4f23471f2fb438e268, 0x82878368ef18996109bf10adae81e1acaeb9fa25, 0xd4d9ec1faa9534a3fa4ff0fe78488ebf175cdfec, 0x4),
(0xdd2e98102508e178fdf1e289ac8342250da6408f, 0x38069b3213a57a077a38938d082a7590d0a21b95, 0xcff1f76af8f15422bb288c8af372332cc6ace970, 0x1),
(0xecb8547ea2a68788665e01a7025093c47f2b45de, 0x6f7155ce9da5434227e48554a0bef7d7492cadb, 0x53f6e1a52554436620b392dea75738b5f670d2b2, 0x2),
(0xefb887600edf8d279f3cca868ef641e9284ae769, 0x9caea57dd4681d1ab53029cf631a47277386bc72, 0xce7743df557c732daff4595d8430ea8485ab3aca, 0x3),
(0x957ec8b7a53dea95d53a5c94d595b834c2be61ca, 0x1b24031194de7dac370a2f7c9be316dc14cbe3f2, 0xc40b5c4c674d1f4cb99891bf342f8acebca9258b, 0x5),
(0x8ba1946c16b7c8d98c6e01836ae0d791ecae07d9, 0x6daec7923c03c56a18d764d9497c39871912fb1a, 0x717b2cf60cc5416eb3f1666e79f30d538f5c9038, 0x5),
(0x72337b25f3486e8518d8f3a4da21724cf3977246, 0xff88c0ddcdcdfb98ca50b68c035434ee2e81cd1d, 0x748e1c374d1efdcb3b9bd7b3c812213ddc1ab940, 0x4),
(0xa71275186b7bbc9747c5831b1e4c75f1bd3eae7a, 0x43b995ded8fddfa6365a51d547456376c8f79b88, 0x6c9a0e390dc7d40900f412313dfe0deb8a5cbb45, 0x6),
(0x926bff0ea87d5c1e8c9da39ceb01a10d1b3c0709, 0xaeb5012cbaf479dd3c2d297ba3a80d344ab22f57, 0xa3eff29dffaed0371d860e291c8f65eb287918ce, 0x3),
(0xdc9e51d365f8a827988cf70c4913d987343dc74a, 0xa6940f2d3f38d0d4b20c36b24f4f91b5bdee59c1, 0xb3a7373eeaf10e449aca7e3cc00f6f554ff0473f, 0x4),
(0x2bcbef8732ab1e591dff595cb1c979f90ebadf0c, 0x3b629a50ab44f67f762dff710653c1fa995863c1, 0x7425a16af106e5eba3a0f751baba95708ead3c0, 0x1),
(0x6a0eadeed0b9e7e900df27d5e253968c30f0f6bd, 0x47e22a97f4dfee66b8b04983bbfbfe0374fa917d, 0xfadb3f2a5b347b9fa8cfdaeddecb1215f19ec707, 0x7),
(0x884675226091712e22a0fbf1fa3c0de95fa09dae, 0x6549eabd7fd5bc6832e2ab061fb02d0f1df6b19a, 0xb660a3baf9d96985c3b8d420259003b8fc0a4410, 0x2),
(0x2a81e382054ed9523f5e4d2a966252b51046325d, 0x81f663abbd508d6df460a1d5a857829834a969ac, 0xe51bcf400dd3fddb5b9f13fd0403b3af011f9fc6, 0x4),
(0x25f6147e13fc52aaf92b1622134c52dff9ec282d, 0x76e457adf428f8a1a82711584e336c0b3b70e94e, 0x6af1ced8354c4bdf84fc55fef847848d4dad83e6, 0x3),
(0xfe0eba650a95051d8fa04f43824d465fdad34493, 0xadd5339288e5527a394a602a2f4e891dbdf8d7aa, 0x169a5d1b893fa66e35ec2620bc96f73d067c9460, 0x3),
(0xb8914a5d41cdd7ff1f0eed7e6eab2e79fabfde5b, 0xf6673ed83fe9731508921bfc12773a19980e5345, 0x83710a069298113cfc91d716a38e1584b2606033, 0x5),
(0xae25b8812cc4f7fec5a14f4174328be0a254cc26, 0x16381c71aa45674488d8b1a10ff0a16d4fd6c997, 0xa947337c2f9d0efe9e69f3a5332c7d0887937643, 0x0),
(0xd8bc55b669d86fe42448a83063aea36251b5fe75, 0x8050afa80843f0162c7fa5323cf19f4f194f90ec, 0x9207917cde2804eb97708cb3392610f716e8c5c, 0x4),
(0xabf778fe7279f34fe6f883d56b938ec46bafb21, 0xf1e96791da0ebc0981eb60fae9509f3c973d5df7, 0xf3f07a604cde6a2164601357cfde0c4b2200fb44, 0x5),
(0x8bbc50d04d2841668fc639c0a0f5ae2cd9f13e03, 0xfa4107e471bd396a25b3853ec09a56c49343cfa3, 0xaf2d6a8142fcf028ce8aabc31377c6d7c63bc9c3, 0x7),
(0xd3db7034072a88a03f7a632fdc3f5a07846c79c3, 0x463871a92ceba68a12ab4d02759ff1aec24c9355, 0xc61b3931ecf8330d4b26b9175efa8690161d25b4, 0x4),
(0x5d5672957260b5794e305ee24bccc07f8dd34d94, 0x7c27bdada7014240c904d42c5a1a1e5f38ea9826, 0x779a7fcc0582e3d901494a98b8d9aa1b8d5f5840, 0x7),
(0x1d197eefd0a6c59ea8f3cfc69c066ce92d7f6e96, 0x665a2ba8a286880c09e2c9ea9adb7479d5bc123d, 0x6377c18c0cf75070627ef9613af864be815eeed6, 0x4),
(0x9c7975f4b345048f7e2d3614d5fdcf162be0d920, 0xf2142d01b4b7c2a5585c8458366c716729ee3329, 0x1dd8903dafda53bfe000f606bceee5b31816f683, 0x7),
(0x5062cb7d6e3b50df1820f5996962b5b8b1fc4617, 0xaa47856eecf23e8ef0f212ed3a978f4d5564d650, 0xa02ffbb157a74b3f105895cbe487c6e1da411070, 0x0),
(0xcdfcb6ff93ca01a2755c0c8f0ad8ee04118e1b9e, 0x1fdc78b5968fbd65351406a0e7cb6f45d9f26a01, 0xcec3c44ec773a31fd3785a998e3526624a504705, 0x3),
(0x65fc356da2a36d35d88c5c5792661d8fe152821c, 0x20a49731ddf37504876ed4303cf8ee52426abbbe, 0xf974613f265ced476f0ad2548eecffcf4b648a9e, 0x7),
(0x59544b829fa1f696558ea62792b85e114e397433, 0x23645dd35469fd873a73db34f1018f08ae7f2c24, 0xe5a23255d9760df1f8d6c8ce1652e0480beb0b7d, 0x2),
(0x8ef11fdbed1a2f64faca70aea2cac44dadd8c14c, 0x640d24c485e9e04b9af2355c07cf7ad430c7ca58, 0x20f0e050124bd754c13b8c2e86dbebaee2132bec, 0x1),
(0x1b5ac91240f6450de7fc5208f0762501790e28b7, 0x7991d2db2512b6463c201f0523ed863ce2a670e8, 0xebf64515f997f18b726cd11a24276ef26505a409, 0x6),
(0xba35a8c66a894fae013ac56c9d6ba538d8cbcf0b, 0xcea24619e5bdd3418da925e3aebd5a3c6f64ef03, 0xb9216f67fe0aa26e374b92ecf4b0c8545522785e, 0x0),
(0xe4e86fdd765bc4d98bc807e3f56ad2f2ef8dbd15, 0x67a9d34b95c25764e1026fd64a0cdadc4f894ef, 0x57f0a006eb1ddbae5b7aaaa3e5a2740c1401c9e2, 0x6),
(0xe582d66c85dda020da90ce0248057e9dff2a0120, 0x8f261523dad715ddc7c992972d8cdab39a0e8920, 0x2bcd65226ab00e4e1117a90b735ea287a921641a, 0x2),
(0x62ac7d9437e54969456ae056289adeaefaccd6bb, 0xe7a23830bdccf8e24a6aa1d84d94cff498f3958a, 0x13d192adc3f46a9a2b624a3a93e6faf243e2120f, 0x7),
(0xd24bfd231c4e6b4b3fe46ec642392e59bf1b7358, 0x51b756a681426525f7194a66375a35185d529813, 0x57a86c9d1fe7fe8ad9b05ea21239cd42bce93ca6, 0x2),
(0xeb0501d2e40edeb6ecad416cfb5d12459de1f32a, 0xc5a4cacf614bc7519130e6727126823d77b51c85, 0xd86708d496f4e4265526247c79931bbc0351237c, 0x0),
(0xb41393d8fe5adbe01ec1ae88aacf8030f990c260, 0xb6997c03f903bc1add14cb98e8741647a60c62ad, 0x2fa481db8208ccfa161e791631d91cc012bff387, 0x5),
(0x851a5f6a1ff9ad28e22858aded0abe1d927f8f47, 0xa35a9a8b26bcbf0a639efd5583c9830aa2834a61, 0x71ed5887fc9b53af96793aa25285227e679923d0, 0x6),
(0x36d5d74fdbb34184f56989136c19526a1e66f284, 0xe2636b99dd8277a5bdf411a2ab44688704682b8b, 0x8fa686e14e0c8c40f507b8e4cc8abf2d8391e13e, 0x3),
(0x136e1685ce0dd8fa72c17db7f71ad3ec08201b0f, 0xf8715b24f37af56cd40108e12d4cd65dfe47b18a, 0x447eb0b48cd17036c130d2c9814df4452645562e, 0x3),
(0x442cd9850919eef698ad67aad25dac1e609042cc, 0x8879c395e3021c4c8e1d4cf3ed7556ddcfe88c98, 0xaf3310936f1bf6f93698081b581b362aa4432c2f, 0x0),
(0xe788598a42acba0d0b7b1f6ec9b230b44a477aad, 0xad119581e7a04cf0b3b1f5197bc27d9684813b36, 0x774ad198691047f7a63714bc633ebf66aa7d2e9d, 0x0),
(0x96db72fa75d1f4ef567ae6b0a6a9b67b6eb925, 0xb2a2d5c2c26fdf25b4ccc5981beff2fbce544bf1, 0x259ef89bfdf867a25f2a45ba31e3b8f01d15ac98, 0x6),
(0xfe84f3657569c6b2f6a820fe72ae29980bb3d3b6, 0x81f40f3434d8a526ae3bdd9229e3b91436c195f2, 0xd9ad8ce4bae25a93282b2d585a3ccc9f76c3cfd2, 0x0),
(0xbd38a3ba51b95b74301f1a375039aadf45cf9500, 0x981371c31ca751800cd9554d120390faa176f90, 0xc687f4008be79d2f747d0d3d373d2908dc99f863, 0x0),
(0x5cf2a3d05d937cb49929f7a5420c77a510f9b9db, 0x43b40c9c33d53a2c03193c499ef7f99c19d36ed2, 0x6efe5e9f33a99b6d6e2b072c52923bbbc6050ee0, 0x4),
(0xb3096421f5e4056f23b5bab000b764a049bff24d, 0x8f826e2bce70b6aa6ec454bc8e9e8cd851ebb165, 0xbb9e3082a3a1bd77fd66bb03772219a944f03e29, 0x7),
(0x3dd4cead2e79dcf86cc7917a579a2dba900bb099, 0x7f75439b0103ed40729a24e7f9846b7c2ca3558, 0x2ebb76dc34c83a60571f14cdf6f8261988a902bd, 0x7),
(0x3180aeb53046ca485f501895ed61e57e8ed27b7, 0x7efbf45c158b115885fb00e2ac5b5df85eef468a, 0x7c97ef4e278686bce1a424a92471b21fcf3658b6, 0x3),
(0x559fa993834a40f6fd31f8a3a2f83da980b2ef84, 0x8785d04f6d97d688f90af33140889e4c7201382a, 0x779f8d284898ca25426208f3a6c3b9455c70eb0d, 0x7),
(0x49a0f529e86a638d1cb71dbd948357d390646128, 0xc5c72505c3807890a11502cfc0286fdf40c924bd, 0xdc242283b58e5d98803c067a4633590e5d1e5d9e, 0x1),
(0xef75ace89af3a7791034ae6161e608384984eb34, 0x61a4d32ca6bdf4f8559cf15bc9be41721575650, 0x8fd9e8a6cdd86a2d960409b124453245b1c92f09, 0x5),
(0xcf0cf859a451378f576de4e10b918fa70b0d0e02, 0x66a7f51a86fe0cd0db57d2025464c1d95384c6c0, 0xcc4673380c3a3cc4545e5644ebaad0ee2205af36, 0x5),
(0xa973fdecf97847abfadc76a530cfaa51a544992f, 0x64ebd081e1e5be70904723e1a786d9581ad4e5a5, 0x58c16e616268863fce12b920e281ad4b1d9d2881, 0x1),
(0x9bbcfa5f87bea52e4df986ecdb89dadf9fe7242b, 0x520b4e89d3e3cd032e5c8c9cfab3f706fe49ca8c, 0x198aa5c2cab8d22845c4f3ea8f710becaba98d13, 0x3),
(0x42abe9b2d14ec440b51362694f93116cf4a8980d, 0x38c3965c6f9c9699476239ea669acc598bf748b6, 0xb47208202e92dbc5ed3d4319dd9e4ceeb21e9ec8, 0x5),
(0x334732df257a5c08e42c56dcd31f3be5cfaa196e, 0xe6387cab10b4e3bff5c72b7a8c47bf3f73812e0c, 0x315e28210455bc5535e6f2a6dcf5a76732ad8c88, 0x3),
(0x825347e82b6ecb7c40353d9282daf9804088f22b, 0xced5ac7b578c4a95a177a283f60437a70232ff0, 0xb647c743e3b4ce3ca95c586bdd14afc41d91ad09, 0x4),
(0xf862df8e80ded401998ce913668155e078f5863f, 0xa73fe4db4136c28cbfc6ee73c800548a0bd463e2, 0xff0395bc6b17d90c38ba263488be5987e3b44890, 0x7),
"""

def parse_raw(raw: str):
    lines = [x.strip() for x in raw.strip().splitlines() if x.strip()]
    pubx = int(lines[0], 16)
    puby = int(lines[1], 16)
    sigs = []
    for line in lines[2:]:
        line = line.rstrip(",")
        h, r, s, kp = ast.literal_eval(line)
        sigs.append({
            "hash": int(h),
            "r": int(r),
            "s": int(s),
            "kp": int(kp),
        })
    return pubx, puby, sigs

def inv(x: int, n: int) -> int:
    return int(pow(int(x), -1, int(n)))

def build_lattice_lsb(sigs, n_order: int, known_bits: int):
    known_bits = int(known_bits)
    n_order = int(n_order)
    m = len(sigs)
    kbi = int(1 << known_bits)

    lat = IntegerMatrix(m + 2, m + 2)

    for i in range(m):
        lat[i, i] = int(2 * kbi * n_order)

        h = int(sigs[i]["hash"])
        r = int(sigs[i]["r"])
        s = int(sigs[i]["s"])
        kp = int(sigs[i]["kp"])

        a = (inv(kbi, n_order) * (r * inv(s, n_order))) % n_order
        b = (inv(kbi, n_order) * (kp - h * inv(s, n_order))) % n_order

        lat[m, i] = int(2 * kbi * a)
        lat[m + 1, i] = int(2 * kbi * b + n_order)

    lat[m, m] = 1
    lat[m + 1, m + 1] = int(n_order)
    return lat

def test_candidate_from_matrix(lat, G, Q, n_order):
    n_order = int(n_order)
    for i in range(lat.nrows):
        cand = int(lat[i, lat.ncols - 2]) % n_order
        if cand <= 0:
            continue
        if cand * G == Q:
            return cand
        cand2 = n_order - cand
        if cand2 * G == Q:
            return cand2
    return None

def recover_key(pubx, puby, sigs, known_bits=3):
    curve = curves.SECP160r1
    G = curve.generator
    n_order = int(curve.order)
    Q = ellipticcurve.Point(curve.curve, int(pubx), int(puby), n_order)

    lat = build_lattice_lsb(sigs, n_order, int(known_bits))

    LLL.reduction(lat)
    d = test_candidate_from_matrix(lat, G, Q, n_order)
    if d is not None:
        return d

    for bs in (15, 25, 35, 45, 55):
        BKZ.reduction(lat, BKZ.Param(block_size=min(bs, lat.nrows), auto_abort=True))
        d = test_candidate_from_matrix(lat, G, Q, n_order)
        if d is not None:
            return d

    return None

def main():
    pubx, puby, sigs = parse_raw(RAW)
    d = recover_key(pubx, puby, sigs, known_bits=3)
    if d is None:
        print("[-] recover failed")
        return

    flag = "DesCTF{" + hashlib.md5(str(d).encode()).hexdigest() + "}"
    print("[+] d =", hex(d))
    print("[+] flag =", flag)

if __name__ == "__main__":
    main()

结果：[+] d = 0x1357ef5f048c1bf1c3a138631e70b76ba8d921f9
[+] flag = DesCTF{9669bfa7126ffabbc99cd92f1165938a}