DesCTF 2026 WriteUp - Q1uJu's House

Crypto#

签到#

天命战队通过专业技术发现线索：2月28日凌晨，伊朗革命卫队某电报群紧急发送一条消息后立即撤回。有群成员截图了撤回通知，但只看到“这条消息已被撤回”。实际上，撤回的消息仍会短暂留在本地缓存中。

天命战队专家提取到了撤回消息的文本并翻译：“坐标25.1°N, 51.3°E，目标确认，行动代号：0100---ZRPEA===ZWHCQ===Y2K7A===ZJNCA===”

flag为行动代号

= =，根本评价不了的题目，太抽象了。有没有密码的解法，好奇这是个啥加密，像 base32 又不像的。

https://www.news.cn/20260228/57c604c5c8514ca581938ccb601a0cec/c.html

flag{真实承诺4}

尽人事，听天命#

题目：

1
import random
2
from secret import seed,yin,yang
3

4
signs = ['大吉', '中吉', '小吉', '吉', '末吉', '凶', '大凶']
5
colors = ['赤', '橙', '黄', '青', '蓝', '紫', '黑', '白']
6
pool = []
7
count = 2495
8
bits = 32
9
kbits = 6
10

11
def next_omen():
12
    global pool
13
    if not pool:
14
        x = random.getrandbits(32)
15
        pool = [x & 0xff, (x >> 8) & 0xff, (x >> 16) & 0xff, (x >> 24) & 0xff]
16
    return pool.pop(0)
17

18
def make_book(name):
19
    t = next_omen()
20
    a = t % 101
21
    b = (t * 3 + 7) % 101
22
    c = (t * 5 + 11) % 101
23
    d = (t * 7 + 13) % 101
24
    color = colors[t & 7]
25
    sign = signs[(t >> 1) % len(signs)]
26
    return '\n'.join([
27
        '【天命阁命书】',
28
        f'有缘人：{name}',
29
        f'命途：{a}',
30
        f'福缘：{b}',
31
        f'财势：{c}',
32
        f'劫数：{d}',
33
        f'吉色：{color}',
34
        f'签文：{sign}',
35
        f'天命：{t}'
36
    ])
37

38
def pull(k):
39
    x = 0
40
    off = 0
41
    while off < k:
42
        x |= random.getrandbits(32) << off
43
        off += 32
44
    return x & ((1 << k) - 1)
45

46
def main():
47
    random.seed(seed)
48
    names = [f'有缘人{i:04d}' for i in range(count)]
49
    with open('命书.txt', 'w', encoding='utf-8') as f:
50
        f.write('天命阁旧录\n')
51
        f.write('知天命，可窥未来。\n')
52
        f.write('见未来，方知真形。\n\n')
53
        for name in names:
54
            f.write(make_book(name))
55
            f.write('\n\n')
56
        bound = yin * yang
57
        trace = yin ^ (yang >> kbits)
58
        seal_a = bound ^ pull(bits * 2)
59
        seal_b = trace ^ pull(bits)
60
        f.write('【未来残页】\n')
61
        f.write(f'阴阳交积封印：{seal_a}\n')
62
        f.write(f'阴阳离合封印：{seal_b}\n')
63
        f.write('\n')
64
        f.write('flag = DesCTF{md5(str(min(yin,yang)) + "|" + str(max(yin,yang)))}\n')
65

66
if __name__ == '__main__':
67
    main()

本题看似花里胡哨，实际上就是一个 MT19937 预测，就是提取数据有点麻烦。

加密流程可以拆解成两部分：

生成 2495 本命书
生成未来残页

我们需要做的是从 2495 本命书中恢复state序列，然后通过生成未来残页的信息解出未知的yin和yang，获得flag。

仔细看看生成命书的两个关键函数：

next_omen()通过random库的getrandbits函数生成一个 32 位的随机数x，再按小端序拆成 4 个字节：[x & 0xff, (x >> 8) & 0xff, (x >> 16) & 0xff, (x >> 24) & 0xff]。

make_book(name)函数主要实现了命书的参数生成，其中我们可以发现天命t = next_omen()，也就是说每一本命书的天命: t就是实际生成的随机数里的一个字节，那我们可以根据 2495 本命书里的天命t得到random库连续2495 * 8 = 19960 bit的输出。虽然最后一个输出缺失 8-bit 导致state不唯一，但该不确定性仅存在于state的尾部，而后续我们所需的 3 个输出只依赖于state的前部，因此不会受到影响，我们只需找到任意一个满足的解即可正确预测出后续用于pull(64)和pull(32)的随机数，从而成功恢复yin和yang并最终得到flag。

exp.py：

1
import re
2
import hashlib
3
from sympy import factorint
4
from gf2bv import LinearSystem
5
from gf2bv.crypto.mt import MT19937
6

7
def recover_mt_from_omens(omens):
8
    lin = LinearSystem([32] * 624)
9
    mt = lin.gens()
10
    rng = MT19937(mt)
11
    eqs = []
12
    # 前 623 个完整 32-bit 输出
13
    for i in range(623):
14
        x = (
15
            omens[4 * i]
16
            | (omens[4 * i + 1] << 8)
17
            | (omens[4 * i + 2] << 16)
18
            | (omens[4 * i + 3] << 24)
19
        )
20
        eqs.append(rng.getrandbits(32) ^ x)
21
    # 第 624 个输出只知道低 24 bit
22
    last24 = omens[2492] | (omens[2493] << 8) | (omens[2494] << 16)
23
    y = rng.getrandbits(32)
24
    eqs.append((y & 0xFFFFFF) ^ last24)
25
    print("solving...")
26
    sol = lin.solve_one(eqs)
27
    return sol
28

29
with open("命书.txt", "r", encoding="utf-8") as f:
30
    text = f.read()
31
omens = list(map(int, re.findall(r"天命：(\d+)", text)))
32
seal_a = int(re.search(r"阴阳交积封印：(\d+)", text).group(1))
33
seal_b = int(re.search(r"阴阳离合封印：(\d+)", text).group(1))
34
sol = recover_mt_from_omens(omens)
35
rng = MT19937(sol)
36
pyrand = rng.to_python_random()
37
# 跳过已经消费掉的 624 个 32-bit 输出
38
for _ in range(624):
39
    pyrand.getrandbits(32)
40
r1 = pyrand.getrandbits(32)
41
r2 = pyrand.getrandbits(32)
42
r3 = pyrand.getrandbits(32)
43
# 重构 pull(64), pull(32)
44
rand64 = r1 | (r2 << 32)
45
rand32 = r3
46
bound = seal_a ^ rand64
47
trace = seal_b ^ rand32
48
fac = factorint(bound)
49
factors = list(fac.keys())
50
assert len(factors) == 2
51
a, b = factors
52
if (a ^ (b >> 6)) == trace:
53
    yin, yang = a, b
54
elif (b ^ (a >> 6)) == trace:
55
    yin, yang = b, a
56
else:
57
    raise ValueError("No valid (yin, yang) found")
58
msg = f"{min(yin, yang)}|{max(yin, yang)}"
59
flag = hashlib.md5(msg.encode()).hexdigest()
60
print("DesCTF{" + flag + "}")
61
# solving...
62
# DesCTF{28dc9b687456ef5897c4477a98a8bdbf}

Check in#

题目：

1
from sage.all import *
2
from Crypto.Util.number import getStrongPrime, inverse
3
from hashlib import *
4
while True:
5
    p = getStrongPrime(512)
6
    q = getStrongPrime(512)
7
    if p%4==3 and q%4==3:
8
        print(p,q)
9
        break
10
N = p * q
11
phi_N = (p**2 + p + 1) * (q**2 + q + 1)
12
d = Integer(N)**RR(0.47)
13
e = inverse(Integer(d), phi_N)
14
flag='flag{'+md5(str(p+q).encode()).hexdigest()+'}'
15
print(f"e = {e}")
16
print(f"N = {N}")
17
print(flag)
18
"""
19
e = 20285928988408708385825788658664300305494782819689883492429762785687493161646901961627732482030570554944571523044008931416609595056746847083499405860944240804200816473153171825246196297214879750749954991916614158499347588230595409852985660426387332691700171974951765953937059128044510635005259571262430221092123685629379451869171518153057333553882827808279895371867053070597655168641441209936240962391624079704514097507822408340977683148014817264999772615710237278286803551400605422497036878844692741788304043681532328471441465596285604159664321904195632202009921776619257725630740166796422445907541165144233376010917
20
N = 162318864198120848289602513685294100213662002310524040016141267082602211702801751627271587107738223466644399363879018058536864307889254050305605097781721847474240769410050480646447538698253600786017599233831714710010395996308361674973789283465587010960323042209564459904257042660293061844258544118566558516881
21
"""

左看看右看看，这d好像是定值啊，可以直接按d = Integer(N) ** R(0.47)算出。然后我们由

ed-k\varphi(N)=1

得：

k=\frac{ed-1}{\varphi(N)}

根据源代码中phi_N = (p**2 + p + 1) * (q**2 + q + 1)，也就是:

\varphi(N)=N^2+(s-1)N+s^2+s+1

其中

s=p+q

因为p和q都是 512-bit 的数量级，所以

\varphi(N)\approx N^2

于是可以近似认为

k\approx \frac{ed}{N^2}

并且这里误差十分小，直接取整就能得到正确的k。

然后有了d和k后，我们可以直接计算得到

\varphi(N)=\frac{ed-1}{k}

然后将phi_N的表达式整理成关于s的二次方程：

s^2+(N+1)s+(N^2-N+1-\varphi(N))=0

求解出s = p + q，即可得到flag='flag{'+md5(str(p+q).encode()).hexdigest()+'}'。

exp.py：

1
# SageMath 10.7
2
from hashlib import md5
3

4
e = 20285928988408708385825788658664300305494782819689883492429762785687493161646901961627732482030570554944571523044008931416609595056746847083499405860944240804200816473153171825246196297214879750749954991916614158499347588230595409852985660426387332691700171974951765953937059128044510635005259571262430221092123685629379451869171518153057333553882827808279895371867053070597655168641441209936240962391624079704514097507822408340977683148014817264999772615710237278286803551400605422497036878844692741788304043681532328471441465596285604159664321904195632202009921776619257725630740166796422445907541165144233376010917
5
N = 162318864198120848289602513685294100213662002310524040016141267082602211702801751627271587107738223466644399363879018058536864307889254050305605097781721847474240769410050480646447538698253600786017599233831714710010395996308361674973789283465587010960323042209564459904257042660293061844258544118566558516881
6
d = Integer(N ** RR(0.47))
7
k = Integer(round((e * d) / (N ** 2)))
8
phi_N = (e * d - 1) // k
9
PR.<x> = PolynomialRing(ZZ)
10
f = x ** 2 + (N + 1) * x + (N ** 2 - N + 1 - phi_N)
11
res = f.roots()
12
s = None
13
for r, _ in res:
14
    if r > 0:
15
        s = Integer(r)
16
        break
17
flag = "flag{" + md5(str(s).encode()).hexdigest() + "}"
18
print(flag)
19
# flag{563ca40e34c288a7fa6a0384b69ccac4}

Low Bits, High Risk#

题目：

1
from hashlib import *
2
from secrets import randbelow
3
from ecdsa import SigningKey, SECP160r1, util
4

5
leak = 3
6
total = 61
7
mask = (1 << leak) - 1
8

9
def main():
10
    sk = SigningKey.generate(curve=SECP160r1)
11
    vk = sk.verifying_key
12
    q = SECP160r1.order
13
    print(hex(vk.pubkey.point.x()))
14
    print(hex(vk.pubkey.point.y()))
15
    d = sk.privkey.secret_multiplier
16
    flag = "DesCTF{" + md5(str(d).encode()).hexdigest() + "}"
17
    for i in range(total):
18
        msg = f"msg-{i}".encode()
19
        digest = sha1(msg).digest()
20
        h = int.from_bytes(digest, "big") % q
21
        k = randbelow(q - 1) + 1
22
        sig = sk.sign_digest(digest, sigencode=util.sigencode_string, k=k)
23
        r, s = util.sigdecode_string(sig, q)
24
        print(f"({hex(h)}, {hex(int(r))}, {hex(int(s))}, {hex(k & mask)}),")
25

26

27
if __name__ == "__main__":
28
    main()
29
"""
30
0x8e0a0071e8cf437efec4233ff8444a4ff8adba2f
31
0xa869fce702b70799c443b450a4d41cc4f65b3eee
32
(0x525931a9ff8ef95025939a57275ecedc2730421f, 0x5288ed7146c188ebda9b6c8909726c3d6f957891, 0x334c301c2d861fa8cceecabc542a5cb7dd7df7d9, 0x6),
33
(0x4b21047e1112dbfee487b4f23471f2fb438e268, 0x82878368ef18996109bf10adae81e1acaeb9fa25, 0xd4d9ec1faa9534a3fa4ff0fe78488ebf175cdfec, 0x4),
34
(0xdd2e98102508e178fdf1e289ac8342250da6408f, 0x38069b3213a57a077a38938d082a7590d0a21b95, 0xcff1f76af8f15422bb288c8af372332cc6ace970, 0x1),
35
(0xecb8547ea2a68788665e01a7025093c47f2b45de, 0x6f7155ce9da5434227e48554a0bef7d7492cadb, 0x53f6e1a52554436620b392dea75738b5f670d2b2, 0x2),
36
(0xefb887600edf8d279f3cca868ef641e9284ae769, 0x9caea57dd4681d1ab53029cf631a47277386bc72, 0xce7743df557c732daff4595d8430ea8485ab3aca, 0x3),
37
(0x957ec8b7a53dea95d53a5c94d595b834c2be61ca, 0x1b24031194de7dac370a2f7c9be316dc14cbe3f2, 0xc40b5c4c674d1f4cb99891bf342f8acebca9258b, 0x5),
38
(0x8ba1946c16b7c8d98c6e01836ae0d791ecae07d9, 0x6daec7923c03c56a18d764d9497c39871912fb1a, 0x717b2cf60cc5416eb3f1666e79f30d538f5c9038, 0x5),
39
(0x72337b25f3486e8518d8f3a4da21724cf3977246, 0xff88c0ddcdcdfb98ca50b68c035434ee2e81cd1d, 0x748e1c374d1efdcb3b9bd7b3c812213ddc1ab940, 0x4),
40
(0xa71275186b7bbc9747c5831b1e4c75f1bd3eae7a, 0x43b995ded8fddfa6365a51d547456376c8f79b88, 0x6c9a0e390dc7d40900f412313dfe0deb8a5cbb45, 0x6),
41
(0x926bff0ea87d5c1e8c9da39ceb01a10d1b3c0709, 0xaeb5012cbaf479dd3c2d297ba3a80d344ab22f57, 0xa3eff29dffaed0371d860e291c8f65eb287918ce, 0x3),
42
(0xdc9e51d365f8a827988cf70c4913d987343dc74a, 0xa6940f2d3f38d0d4b20c36b24f4f91b5bdee59c1, 0xb3a7373eeaf10e449aca7e3cc00f6f554ff0473f, 0x4),
43
(0x2bcbef8732ab1e591dff595cb1c979f90ebadf0c, 0x3b629a50ab44f67f762dff710653c1fa995863c1, 0x7425a16af106e5eba3a0f751baba95708ead3c0, 0x1),
44
(0x6a0eadeed0b9e7e900df27d5e253968c30f0f6bd, 0x47e22a97f4dfee66b8b04983bbfbfe0374fa917d, 0xfadb3f2a5b347b9fa8cfdaeddecb1215f19ec707, 0x7),
45
(0x884675226091712e22a0fbf1fa3c0de95fa09dae, 0x6549eabd7fd5bc6832e2ab061fb02d0f1df6b19a, 0xb660a3baf9d96985c3b8d420259003b8fc0a4410, 0x2),
46
(0x2a81e382054ed9523f5e4d2a966252b51046325d, 0x81f663abbd508d6df460a1d5a857829834a969ac, 0xe51bcf400dd3fddb5b9f13fd0403b3af011f9fc6, 0x4),
47
(0x25f6147e13fc52aaf92b1622134c52dff9ec282d, 0x76e457adf428f8a1a82711584e336c0b3b70e94e, 0x6af1ced8354c4bdf84fc55fef847848d4dad83e6, 0x3),
48
(0xfe0eba650a95051d8fa04f43824d465fdad34493, 0xadd5339288e5527a394a602a2f4e891dbdf8d7aa, 0x169a5d1b893fa66e35ec2620bc96f73d067c9460, 0x3),
49
(0xb8914a5d41cdd7ff1f0eed7e6eab2e79fabfde5b, 0xf6673ed83fe9731508921bfc12773a19980e5345, 0x83710a069298113cfc91d716a38e1584b2606033, 0x5),
50
(0xae25b8812cc4f7fec5a14f4174328be0a254cc26, 0x16381c71aa45674488d8b1a10ff0a16d4fd6c997, 0xa947337c2f9d0efe9e69f3a5332c7d0887937643, 0x0),
51
(0xd8bc55b669d86fe42448a83063aea36251b5fe75, 0x8050afa80843f0162c7fa5323cf19f4f194f90ec, 0x9207917cde2804eb97708cb3392610f716e8c5c, 0x4),
52
(0xabf778fe7279f34fe6f883d56b938ec46bafb21, 0xf1e96791da0ebc0981eb60fae9509f3c973d5df7, 0xf3f07a604cde6a2164601357cfde0c4b2200fb44, 0x5),
53
(0x8bbc50d04d2841668fc639c0a0f5ae2cd9f13e03, 0xfa4107e471bd396a25b3853ec09a56c49343cfa3, 0xaf2d6a8142fcf028ce8aabc31377c6d7c63bc9c3, 0x7),
54
(0xd3db7034072a88a03f7a632fdc3f5a07846c79c3, 0x463871a92ceba68a12ab4d02759ff1aec24c9355, 0xc61b3931ecf8330d4b26b9175efa8690161d25b4, 0x4),
55
(0x5d5672957260b5794e305ee24bccc07f8dd34d94, 0x7c27bdada7014240c904d42c5a1a1e5f38ea9826, 0x779a7fcc0582e3d901494a98b8d9aa1b8d5f5840, 0x7),
56
(0x1d197eefd0a6c59ea8f3cfc69c066ce92d7f6e96, 0x665a2ba8a286880c09e2c9ea9adb7479d5bc123d, 0x6377c18c0cf75070627ef9613af864be815eeed6, 0x4),
57
(0x9c7975f4b345048f7e2d3614d5fdcf162be0d920, 0xf2142d01b4b7c2a5585c8458366c716729ee3329, 0x1dd8903dafda53bfe000f606bceee5b31816f683, 0x7),
58
(0x5062cb7d6e3b50df1820f5996962b5b8b1fc4617, 0xaa47856eecf23e8ef0f212ed3a978f4d5564d650, 0xa02ffbb157a74b3f105895cbe487c6e1da411070, 0x0),
59
(0xcdfcb6ff93ca01a2755c0c8f0ad8ee04118e1b9e, 0x1fdc78b5968fbd65351406a0e7cb6f45d9f26a01, 0xcec3c44ec773a31fd3785a998e3526624a504705, 0x3),
60
(0x65fc356da2a36d35d88c5c5792661d8fe152821c, 0x20a49731ddf37504876ed4303cf8ee52426abbbe, 0xf974613f265ced476f0ad2548eecffcf4b648a9e, 0x7),
61
(0x59544b829fa1f696558ea62792b85e114e397433, 0x23645dd35469fd873a73db34f1018f08ae7f2c24, 0xe5a23255d9760df1f8d6c8ce1652e0480beb0b7d, 0x2),
62
(0x8ef11fdbed1a2f64faca70aea2cac44dadd8c14c, 0x640d24c485e9e04b9af2355c07cf7ad430c7ca58, 0x20f0e050124bd754c13b8c2e86dbebaee2132bec, 0x1),
63
(0x1b5ac91240f6450de7fc5208f0762501790e28b7, 0x7991d2db2512b6463c201f0523ed863ce2a670e8, 0xebf64515f997f18b726cd11a24276ef26505a409, 0x6),
64
(0xba35a8c66a894fae013ac56c9d6ba538d8cbcf0b, 0xcea24619e5bdd3418da925e3aebd5a3c6f64ef03, 0xb9216f67fe0aa26e374b92ecf4b0c8545522785e, 0x0),
65
(0xe4e86fdd765bc4d98bc807e3f56ad2f2ef8dbd15, 0x67a9d34b95c25764e1026fd64a0cdadc4f894ef, 0x57f0a006eb1ddbae5b7aaaa3e5a2740c1401c9e2, 0x6),
66
(0xe582d66c85dda020da90ce0248057e9dff2a0120, 0x8f261523dad715ddc7c992972d8cdab39a0e8920, 0x2bcd65226ab00e4e1117a90b735ea287a921641a, 0x2),
67
(0x62ac7d9437e54969456ae056289adeaefaccd6bb, 0xe7a23830bdccf8e24a6aa1d84d94cff498f3958a, 0x13d192adc3f46a9a2b624a3a93e6faf243e2120f, 0x7),
68
(0xd24bfd231c4e6b4b3fe46ec642392e59bf1b7358, 0x51b756a681426525f7194a66375a35185d529813, 0x57a86c9d1fe7fe8ad9b05ea21239cd42bce93ca6, 0x2),
69
(0xeb0501d2e40edeb6ecad416cfb5d12459de1f32a, 0xc5a4cacf614bc7519130e6727126823d77b51c85, 0xd86708d496f4e4265526247c79931bbc0351237c, 0x0),
70
(0xb41393d8fe5adbe01ec1ae88aacf8030f990c260, 0xb6997c03f903bc1add14cb98e8741647a60c62ad, 0x2fa481db8208ccfa161e791631d91cc012bff387, 0x5),
71
(0x851a5f6a1ff9ad28e22858aded0abe1d927f8f47, 0xa35a9a8b26bcbf0a639efd5583c9830aa2834a61, 0x71ed5887fc9b53af96793aa25285227e679923d0, 0x6),
72
(0x36d5d74fdbb34184f56989136c19526a1e66f284, 0xe2636b99dd8277a5bdf411a2ab44688704682b8b, 0x8fa686e14e0c8c40f507b8e4cc8abf2d8391e13e, 0x3),
73
(0x136e1685ce0dd8fa72c17db7f71ad3ec08201b0f, 0xf8715b24f37af56cd40108e12d4cd65dfe47b18a, 0x447eb0b48cd17036c130d2c9814df4452645562e, 0x3),
74
(0x442cd9850919eef698ad67aad25dac1e609042cc, 0x8879c395e3021c4c8e1d4cf3ed7556ddcfe88c98, 0xaf3310936f1bf6f93698081b581b362aa4432c2f, 0x0),
75
(0xe788598a42acba0d0b7b1f6ec9b230b44a477aad, 0xad119581e7a04cf0b3b1f5197bc27d9684813b36, 0x774ad198691047f7a63714bc633ebf66aa7d2e9d, 0x0),
76
(0x96db72fa75d1f4ef567ae6b0a6a9b67b6eb925, 0xb2a2d5c2c26fdf25b4ccc5981beff2fbce544bf1, 0x259ef89bfdf867a25f2a45ba31e3b8f01d15ac98, 0x6),
77
(0xfe84f3657569c6b2f6a820fe72ae29980bb3d3b6, 0x81f40f3434d8a526ae3bdd9229e3b91436c195f2, 0xd9ad8ce4bae25a93282b2d585a3ccc9f76c3cfd2, 0x0),
78
(0xbd38a3ba51b95b74301f1a375039aadf45cf9500, 0x981371c31ca751800cd9554d120390faa176f90, 0xc687f4008be79d2f747d0d3d373d2908dc99f863, 0x0),
79
(0x5cf2a3d05d937cb49929f7a5420c77a510f9b9db, 0x43b40c9c33d53a2c03193c499ef7f99c19d36ed2, 0x6efe5e9f33a99b6d6e2b072c52923bbbc6050ee0, 0x4),
80
(0xb3096421f5e4056f23b5bab000b764a049bff24d, 0x8f826e2bce70b6aa6ec454bc8e9e8cd851ebb165, 0xbb9e3082a3a1bd77fd66bb03772219a944f03e29, 0x7),
81
(0x3dd4cead2e79dcf86cc7917a579a2dba900bb099, 0x7f75439b0103ed40729a24e7f9846b7c2ca3558, 0x2ebb76dc34c83a60571f14cdf6f8261988a902bd, 0x7),
82
(0x3180aeb53046ca485f501895ed61e57e8ed27b7, 0x7efbf45c158b115885fb00e2ac5b5df85eef468a, 0x7c97ef4e278686bce1a424a92471b21fcf3658b6, 0x3),
83
(0x559fa993834a40f6fd31f8a3a2f83da980b2ef84, 0x8785d04f6d97d688f90af33140889e4c7201382a, 0x779f8d284898ca25426208f3a6c3b9455c70eb0d, 0x7),
84
(0x49a0f529e86a638d1cb71dbd948357d390646128, 0xc5c72505c3807890a11502cfc0286fdf40c924bd, 0xdc242283b58e5d98803c067a4633590e5d1e5d9e, 0x1),
85
(0xef75ace89af3a7791034ae6161e608384984eb34, 0x61a4d32ca6bdf4f8559cf15bc9be41721575650, 0x8fd9e8a6cdd86a2d960409b124453245b1c92f09, 0x5),
86
(0xcf0cf859a451378f576de4e10b918fa70b0d0e02, 0x66a7f51a86fe0cd0db57d2025464c1d95384c6c0, 0xcc4673380c3a3cc4545e5644ebaad0ee2205af36, 0x5),
87
(0xa973fdecf97847abfadc76a530cfaa51a544992f, 0x64ebd081e1e5be70904723e1a786d9581ad4e5a5, 0x58c16e616268863fce12b920e281ad4b1d9d2881, 0x1),
88
(0x9bbcfa5f87bea52e4df986ecdb89dadf9fe7242b, 0x520b4e89d3e3cd032e5c8c9cfab3f706fe49ca8c, 0x198aa5c2cab8d22845c4f3ea8f710becaba98d13, 0x3),
89
(0x42abe9b2d14ec440b51362694f93116cf4a8980d, 0x38c3965c6f9c9699476239ea669acc598bf748b6, 0xb47208202e92dbc5ed3d4319dd9e4ceeb21e9ec8, 0x5),
90
(0x334732df257a5c08e42c56dcd31f3be5cfaa196e, 0xe6387cab10b4e3bff5c72b7a8c47bf3f73812e0c, 0x315e28210455bc5535e6f2a6dcf5a76732ad8c88, 0x3),
91
(0x825347e82b6ecb7c40353d9282daf9804088f22b, 0xced5ac7b578c4a95a177a283f60437a70232ff0, 0xb647c743e3b4ce3ca95c586bdd14afc41d91ad09, 0x4),
92
(0xf862df8e80ded401998ce913668155e078f5863f, 0xa73fe4db4136c28cbfc6ee73c800548a0bd463e2, 0xff0395bc6b17d90c38ba263488be5987e3b44890, 0x7),
93
"""

题目使用了 ECDSA over SECP160r1 进行签名，并对每条消息msg-i：

计算哈希
$h_i=SHA1(msg_i)~mod~q$
生成随机 nonce
$k_i\in[1,q-1]$
计算签名
$r_i=(k_iG)_x~mod~q$ $s_i\equiv k^{-1}_i(h_i+r_id)\pmod{q}$

最后对每轮签名输出h_i，r_i，s_i，k_i & 7，由于leak = 3，也就是每个 nonce 的低 3-bit 位泄露了。

而ECDSA满足：

s_ik_i\equiv h_i+r_id\pmod{q}

题目泄露了

k_i\equiv kp_i\pmod{2^3}

令B = 2 ** 3 = 8，可记成：

k_i=kp_i+Bt_i

代回签名方程中有：

s_i(kp_i+Bt_i)\equiv h_i+r_id\pmod{q}

整理一下变成：

(B^{-1}r_is_i^{-1})d-t_i\equiv B^{-1}(kp_i-h_is_i^{-1})\pmod{q}

典型的 ECDSA partial nonce leakage / Hidden Number Problem。

而本题中曲线阶约为 160-bit，每条签名泄露 3-bit，样本数为 61，61 * 3 = 183 > 160，理论上泄露足够。令：

\alpha_i=(B^{-1}\cdot r_i\cdot s_i^{-1}~mod~q)

\beta_i=(B^{-1}\cdot(kp_i-h_is_i^{-1})~mod~q)

则签名方程中为：

\alpha_id-t_i\equiv \beta_i\pmod{q}

也就是说存在整数 $u_i\in\mathbb{Z}$ ，使得

\alpha_id-t_i-\beta_i=qu_i

即

\alpha_id-\beta_i=qu_i+t_i

我们再令

a_i=2B\alpha_i

b_i=2B\beta_i+q

ps: 这里目的是为了去掉 $\alpha$ 和 $\beta$ 前面的分母 $B^{-1}$ ，让系数变为标准整数结构，同时统一尺度，将所有项都对齐到q的量级，同时b_i中的+ q将误差中心化，也就是让最后我们找到的目标向量更短：

2Bt_i-q\in[-q,q]

则有

a_id-(b_i-q)=2Bt_i+2Bqu_i

整理移项可得等式：

(-u_i)\cdot 2Bq+a_id-b_i=2Bt_i-q

由等式构如下格：

L=\begin{bmatrix} 2Bq & 0 & 0 & \cdots & 0 & 0 & 0\\ 0 & 2Bq & 0 & \cdots & 0 & 0 & 0\\ 0 & 0 & 2Bq & \cdots & 0 & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ 0 & 0 & 0 & \cdots & 2Bq & 0 & 0\\ a_1 & a_2 & a_3 & \cdots & a_m & 1 & 0\\ b_1 & b_2 & b_3 & \cdots & b_m & 0 & q \end{bmatrix}

有

(-u_1,-u_2,\cdots,-u_m,d,-q)L=(2Bt_1-q,2Bt_2-q,\cdots,2Bt_m-q,d,-q)

最后check_d扫一遍格基出来的d找到成功验证的即可。

exp.py：

1
# SageMath 10.7
2
from hashlib import md5
3

4
def check_d(d):
5
    for h, r, s, kp in sigs:
6
        k = ((h + r * d) * inverse_mod(s, q)) % q
7
        if Integer(k) % kbits != kp:
8
            return False
9
    return True
10

11
q = 0x100000000000000000001F4C8F927AED3CA752257
12
kbits = 2 ^ 3
13
sigs = [
14
(0x525931a9ff8ef95025939a57275ecedc2730421f, 0x5288ed7146c188ebda9b6c8909726c3d6f957891, 0x334c301c2d861fa8cceecabc542a5cb7dd7df7d9, 0x6),
15
(0x4b21047e1112dbfee487b4f23471f2fb438e268, 0x82878368ef18996109bf10adae81e1acaeb9fa25, 0xd4d9ec1faa9534a3fa4ff0fe78488ebf175cdfec, 0x4),
16
(0xdd2e98102508e178fdf1e289ac8342250da6408f, 0x38069b3213a57a077a38938d082a7590d0a21b95, 0xcff1f76af8f15422bb288c8af372332cc6ace970, 0x1),
17
(0xecb8547ea2a68788665e01a7025093c47f2b45de, 0x6f7155ce9da5434227e48554a0bef7d7492cadb, 0x53f6e1a52554436620b392dea75738b5f670d2b2, 0x2),
18
(0xefb887600edf8d279f3cca868ef641e9284ae769, 0x9caea57dd4681d1ab53029cf631a47277386bc72, 0xce7743df557c732daff4595d8430ea8485ab3aca, 0x3),
19
(0x957ec8b7a53dea95d53a5c94d595b834c2be61ca, 0x1b24031194de7dac370a2f7c9be316dc14cbe3f2, 0xc40b5c4c674d1f4cb99891bf342f8acebca9258b, 0x5),
20
(0x8ba1946c16b7c8d98c6e01836ae0d791ecae07d9, 0x6daec7923c03c56a18d764d9497c39871912fb1a, 0x717b2cf60cc5416eb3f1666e79f30d538f5c9038, 0x5),
21
(0x72337b25f3486e8518d8f3a4da21724cf3977246, 0xff88c0ddcdcdfb98ca50b68c035434ee2e81cd1d, 0x748e1c374d1efdcb3b9bd7b3c812213ddc1ab940, 0x4),
22
(0xa71275186b7bbc9747c5831b1e4c75f1bd3eae7a, 0x43b995ded8fddfa6365a51d547456376c8f79b88, 0x6c9a0e390dc7d40900f412313dfe0deb8a5cbb45, 0x6),
23
(0x926bff0ea87d5c1e8c9da39ceb01a10d1b3c0709, 0xaeb5012cbaf479dd3c2d297ba3a80d344ab22f57, 0xa3eff29dffaed0371d860e291c8f65eb287918ce, 0x3),
24
(0xdc9e51d365f8a827988cf70c4913d987343dc74a, 0xa6940f2d3f38d0d4b20c36b24f4f91b5bdee59c1, 0xb3a7373eeaf10e449aca7e3cc00f6f554ff0473f, 0x4),
25
(0x2bcbef8732ab1e591dff595cb1c979f90ebadf0c, 0x3b629a50ab44f67f762dff710653c1fa995863c1, 0x7425a16af106e5eba3a0f751baba95708ead3c0, 0x1),
26
(0x6a0eadeed0b9e7e900df27d5e253968c30f0f6bd, 0x47e22a97f4dfee66b8b04983bbfbfe0374fa917d, 0xfadb3f2a5b347b9fa8cfdaeddecb1215f19ec707, 0x7),
27
(0x884675226091712e22a0fbf1fa3c0de95fa09dae, 0x6549eabd7fd5bc6832e2ab061fb02d0f1df6b19a, 0xb660a3baf9d96985c3b8d420259003b8fc0a4410, 0x2),
28
(0x2a81e382054ed9523f5e4d2a966252b51046325d, 0x81f663abbd508d6df460a1d5a857829834a969ac, 0xe51bcf400dd3fddb5b9f13fd0403b3af011f9fc6, 0x4),
29
(0x25f6147e13fc52aaf92b1622134c52dff9ec282d, 0x76e457adf428f8a1a82711584e336c0b3b70e94e, 0x6af1ced8354c4bdf84fc55fef847848d4dad83e6, 0x3),
30
(0xfe0eba650a95051d8fa04f43824d465fdad34493, 0xadd5339288e5527a394a602a2f4e891dbdf8d7aa, 0x169a5d1b893fa66e35ec2620bc96f73d067c9460, 0x3),
31
(0xb8914a5d41cdd7ff1f0eed7e6eab2e79fabfde5b, 0xf6673ed83fe9731508921bfc12773a19980e5345, 0x83710a069298113cfc91d716a38e1584b2606033, 0x5),
32
(0xae25b8812cc4f7fec5a14f4174328be0a254cc26, 0x16381c71aa45674488d8b1a10ff0a16d4fd6c997, 0xa947337c2f9d0efe9e69f3a5332c7d0887937643, 0x0),
33
(0xd8bc55b669d86fe42448a83063aea36251b5fe75, 0x8050afa80843f0162c7fa5323cf19f4f194f90ec, 0x9207917cde2804eb97708cb3392610f716e8c5c, 0x4),
34
(0xabf778fe7279f34fe6f883d56b938ec46bafb21, 0xf1e96791da0ebc0981eb60fae9509f3c973d5df7, 0xf3f07a604cde6a2164601357cfde0c4b2200fb44, 0x5),
35
(0x8bbc50d04d2841668fc639c0a0f5ae2cd9f13e03, 0xfa4107e471bd396a25b3853ec09a56c49343cfa3, 0xaf2d6a8142fcf028ce8aabc31377c6d7c63bc9c3, 0x7),
36
(0xd3db7034072a88a03f7a632fdc3f5a07846c79c3, 0x463871a92ceba68a12ab4d02759ff1aec24c9355, 0xc61b3931ecf8330d4b26b9175efa8690161d25b4, 0x4),
37
(0x5d5672957260b5794e305ee24bccc07f8dd34d94, 0x7c27bdada7014240c904d42c5a1a1e5f38ea9826, 0x779a7fcc0582e3d901494a98b8d9aa1b8d5f5840, 0x7),
38
(0x1d197eefd0a6c59ea8f3cfc69c066ce92d7f6e96, 0x665a2ba8a286880c09e2c9ea9adb7479d5bc123d, 0x6377c18c0cf75070627ef9613af864be815eeed6, 0x4),
39
(0x9c7975f4b345048f7e2d3614d5fdcf162be0d920, 0xf2142d01b4b7c2a5585c8458366c716729ee3329, 0x1dd8903dafda53bfe000f606bceee5b31816f683, 0x7),
40
(0x5062cb7d6e3b50df1820f5996962b5b8b1fc4617, 0xaa47856eecf23e8ef0f212ed3a978f4d5564d650, 0xa02ffbb157a74b3f105895cbe487c6e1da411070, 0x0),
41
(0xcdfcb6ff93ca01a2755c0c8f0ad8ee04118e1b9e, 0x1fdc78b5968fbd65351406a0e7cb6f45d9f26a01, 0xcec3c44ec773a31fd3785a998e3526624a504705, 0x3),
42
(0x65fc356da2a36d35d88c5c5792661d8fe152821c, 0x20a49731ddf37504876ed4303cf8ee52426abbbe, 0xf974613f265ced476f0ad2548eecffcf4b648a9e, 0x7),
43
(0x59544b829fa1f696558ea62792b85e114e397433, 0x23645dd35469fd873a73db34f1018f08ae7f2c24, 0xe5a23255d9760df1f8d6c8ce1652e0480beb0b7d, 0x2),
44
(0x8ef11fdbed1a2f64faca70aea2cac44dadd8c14c, 0x640d24c485e9e04b9af2355c07cf7ad430c7ca58, 0x20f0e050124bd754c13b8c2e86dbebaee2132bec, 0x1),
45
(0x1b5ac91240f6450de7fc5208f0762501790e28b7, 0x7991d2db2512b6463c201f0523ed863ce2a670e8, 0xebf64515f997f18b726cd11a24276ef26505a409, 0x6),
46
(0xba35a8c66a894fae013ac56c9d6ba538d8cbcf0b, 0xcea24619e5bdd3418da925e3aebd5a3c6f64ef03, 0xb9216f67fe0aa26e374b92ecf4b0c8545522785e, 0x0),
47
(0xe4e86fdd765bc4d98bc807e3f56ad2f2ef8dbd15, 0x67a9d34b95c25764e1026fd64a0cdadc4f894ef, 0x57f0a006eb1ddbae5b7aaaa3e5a2740c1401c9e2, 0x6),
48
(0xe582d66c85dda020da90ce0248057e9dff2a0120, 0x8f261523dad715ddc7c992972d8cdab39a0e8920, 0x2bcd65226ab00e4e1117a90b735ea287a921641a, 0x2),
49
(0x62ac7d9437e54969456ae056289adeaefaccd6bb, 0xe7a23830bdccf8e24a6aa1d84d94cff498f3958a, 0x13d192adc3f46a9a2b624a3a93e6faf243e2120f, 0x7),
50
(0xd24bfd231c4e6b4b3fe46ec642392e59bf1b7358, 0x51b756a681426525f7194a66375a35185d529813, 0x57a86c9d1fe7fe8ad9b05ea21239cd42bce93ca6, 0x2),
51
(0xeb0501d2e40edeb6ecad416cfb5d12459de1f32a, 0xc5a4cacf614bc7519130e6727126823d77b51c85, 0xd86708d496f4e4265526247c79931bbc0351237c, 0x0),
52
(0xb41393d8fe5adbe01ec1ae88aacf8030f990c260, 0xb6997c03f903bc1add14cb98e8741647a60c62ad, 0x2fa481db8208ccfa161e791631d91cc012bff387, 0x5),
53
(0x851a5f6a1ff9ad28e22858aded0abe1d927f8f47, 0xa35a9a8b26bcbf0a639efd5583c9830aa2834a61, 0x71ed5887fc9b53af96793aa25285227e679923d0, 0x6),
54
(0x36d5d74fdbb34184f56989136c19526a1e66f284, 0xe2636b99dd8277a5bdf411a2ab44688704682b8b, 0x8fa686e14e0c8c40f507b8e4cc8abf2d8391e13e, 0x3),
55
(0x136e1685ce0dd8fa72c17db7f71ad3ec08201b0f, 0xf8715b24f37af56cd40108e12d4cd65dfe47b18a, 0x447eb0b48cd17036c130d2c9814df4452645562e, 0x3),
56
(0x442cd9850919eef698ad67aad25dac1e609042cc, 0x8879c395e3021c4c8e1d4cf3ed7556ddcfe88c98, 0xaf3310936f1bf6f93698081b581b362aa4432c2f, 0x0),
57
(0xe788598a42acba0d0b7b1f6ec9b230b44a477aad, 0xad119581e7a04cf0b3b1f5197bc27d9684813b36, 0x774ad198691047f7a63714bc633ebf66aa7d2e9d, 0x0),
58
(0x96db72fa75d1f4ef567ae6b0a6a9b67b6eb925, 0xb2a2d5c2c26fdf25b4ccc5981beff2fbce544bf1, 0x259ef89bfdf867a25f2a45ba31e3b8f01d15ac98, 0x6),
59
(0xfe84f3657569c6b2f6a820fe72ae29980bb3d3b6, 0x81f40f3434d8a526ae3bdd9229e3b91436c195f2, 0xd9ad8ce4bae25a93282b2d585a3ccc9f76c3cfd2, 0x0),
60
(0xbd38a3ba51b95b74301f1a375039aadf45cf9500, 0x981371c31ca751800cd9554d120390faa176f90, 0xc687f4008be79d2f747d0d3d373d2908dc99f863, 0x0),
61
(0x5cf2a3d05d937cb49929f7a5420c77a510f9b9db, 0x43b40c9c33d53a2c03193c499ef7f99c19d36ed2, 0x6efe5e9f33a99b6d6e2b072c52923bbbc6050ee0, 0x4),
62
(0xb3096421f5e4056f23b5bab000b764a049bff24d, 0x8f826e2bce70b6aa6ec454bc8e9e8cd851ebb165, 0xbb9e3082a3a1bd77fd66bb03772219a944f03e29, 0x7),
63
(0x3dd4cead2e79dcf86cc7917a579a2dba900bb099, 0x7f75439b0103ed40729a24e7f9846b7c2ca3558, 0x2ebb76dc34c83a60571f14cdf6f8261988a902bd, 0x7),
64
(0x3180aeb53046ca485f501895ed61e57e8ed27b7, 0x7efbf45c158b115885fb00e2ac5b5df85eef468a, 0x7c97ef4e278686bce1a424a92471b21fcf3658b6, 0x3),
65
(0x559fa993834a40f6fd31f8a3a2f83da980b2ef84, 0x8785d04f6d97d688f90af33140889e4c7201382a, 0x779f8d284898ca25426208f3a6c3b9455c70eb0d, 0x7),
66
(0x49a0f529e86a638d1cb71dbd948357d390646128, 0xc5c72505c3807890a11502cfc0286fdf40c924bd, 0xdc242283b58e5d98803c067a4633590e5d1e5d9e, 0x1),
67
(0xef75ace89af3a7791034ae6161e608384984eb34, 0x61a4d32ca6bdf4f8559cf15bc9be41721575650, 0x8fd9e8a6cdd86a2d960409b124453245b1c92f09, 0x5),
68
(0xcf0cf859a451378f576de4e10b918fa70b0d0e02, 0x66a7f51a86fe0cd0db57d2025464c1d95384c6c0, 0xcc4673380c3a3cc4545e5644ebaad0ee2205af36, 0x5),
69
(0xa973fdecf97847abfadc76a530cfaa51a544992f, 0x64ebd081e1e5be70904723e1a786d9581ad4e5a5, 0x58c16e616268863fce12b920e281ad4b1d9d2881, 0x1),
70
(0x9bbcfa5f87bea52e4df986ecdb89dadf9fe7242b, 0x520b4e89d3e3cd032e5c8c9cfab3f706fe49ca8c, 0x198aa5c2cab8d22845c4f3ea8f710becaba98d13, 0x3),
71
(0x42abe9b2d14ec440b51362694f93116cf4a8980d, 0x38c3965c6f9c9699476239ea669acc598bf748b6, 0xb47208202e92dbc5ed3d4319dd9e4ceeb21e9ec8, 0x5),
72
(0x334732df257a5c08e42c56dcd31f3be5cfaa196e, 0xe6387cab10b4e3bff5c72b7a8c47bf3f73812e0c, 0x315e28210455bc5535e6f2a6dcf5a76732ad8c88, 0x3),
73
(0x825347e82b6ecb7c40353d9282daf9804088f22b, 0xced5ac7b578c4a95a177a283f60437a70232ff0, 0xb647c743e3b4ce3ca95c586bdd14afc41d91ad09, 0x4),
74
(0xf862df8e80ded401998ce913668155e078f5863f, 0xa73fe4db4136c28cbfc6ee73c800548a0bd463e2, 0xff0395bc6b17d90c38ba263488be5987e3b44890, 0x7),
75
]
76
n = len(sigs)
77
L = Matrix(ZZ, n + 2, n + 2)
78
invk = inverse_mod(kbits, q)
79
for i in range(n):
80
    h, r, s, kp = sigs[i]
81
    sinv = inverse_mod(s, q)
82
    L[i, i] = 2 * kbits * q
83
    L[n, i] = 2 * kbits * ((invk * r * sinv) % q)
84
    L[n + 1, i] = 2 * kbits * ((invk * (kp - h * sinv)) % q) + q
85
L[n, n] = 1
86
L[n + 1, n + 1] = q
87
B = L.BKZ(block_size=30)
88
for row in B.rows():
89
    cand = Integer(row[n]) % q
90
    for d in [cand, (-cand) % q]:
91
        if check_d(d):
92
            print("d =", hex(d))
93
            print("flag =", "DesCTF{" + md5(str(int(d)).encode()).hexdigest() + "}")
94
            raise SystemExit
95
# d = 0x1357ef5f048c1bf1c3a138631e70b76ba8d921f9
96
# flag = DesCTF{9669bfa7126ffabbc99cd92f1165938a}

持续更新中~

Crypto#

签到#

尽人事，听天命#

Check in#

Low Bits, High Risk#