a ctfer on the load

1
from flask import Flask, request, make_response, render_template, redirect, url_for, abort
2
from Crypto.Cipher import AES
3
from Crypto.Util.Padding import pad, unpad
4
import os
5

6
app = Flask(__name__)
7
KEY = os.getenv("SECRET_KEY", os.urandom(16))
8
ADMIN_PASS = os.getenv("ADMIN_PASS", "admin123")
9
FLAG = os.getenv("FLAG", "XMCTF{xxxxxx}")
10

11
# 初始数据，禁止注册 admin
12
USERS = {"admin": ADMIN_PASS}
13

14
def get_session_data(token_hex):
15
    if not token_hex: return None
16
    data = bytes.fromhex(token_hex)
17
    iv, ct = data[:16], data[16:]
18
    cipher = AES.new(KEY, AES.MODE_CBC, iv)
19
    decrypted = cipher.decrypt(ct)
20
    print(decrypted)
21
    return unpad(decrypted, 16).decode(errors='ignore')
22

23
def create_session(username):
24
    iv = os.urandom(16)
25
    cipher = AES.new(KEY, AES.MODE_CBC, iv)
26
    msg = f"user={username}".encode()
27
    ct = cipher.encrypt(pad(msg, 16))
28
    return (iv + ct).hex()
29

30
@app.route('/')
31
def index():
32
    token = request.cookies.get('session')
33
    if not token:
34
        return redirect(url_for('login_page'))
35

36
    try:
37
        msg = get_session_data(token)
38
        if not msg or not msg.startswith("user="):
39
            return redirect(url_for('login_page'))
40

41
        username = msg[5:]
42
    except:
43
        abort(500, description="Invalid Session")
44

45
    return render_template('index.html', username=username, flag=FLAG if username == "admin" else None)
46

47
@app.route('/login', methods=['GET', 'POST'])
48
def login_page():
49
    if request.method == 'GET':
50
        return render_template('login.html')
51

52
    user = request.form.get('username')
53
    pw = request.form.get('password')
54

55
    if USERS.get(user) == pw:
56
        resp = make_response(redirect(url_for('index')))
57
        resp.set_cookie('session', create_session(user))
58
        return resp
59
    return "Invalid username or password", 403
60

61
if __name__ == '__main__':
62
    app.run(host='0.0.0.0', port=5000)

1
import sys
2

3
import requests
4

5
URL = "http://nc1.ctfplus.cn:36477"
6

7

8
def check_padding(iv, ct):
9
    cookie = (iv + ct).hex()
10
    try:
11
        r = requests.get(URL + "/", cookies={"session": cookie}, allow_redirects=False)
12
        return r.status_code != 500
13
    except requests.exceptions.RequestException:
14
        return False
15

16

17
ct = bytearray([0] * 16)
18
I = bytearray([0] * 16)
19

20

21
for pad_val in range(1, 17):
22
    idx = 16 - pad_val
23
    iv = bytearray([0] * 16)
24

25
    for i in range(idx + 1, 16):
26
        iv[i] = I[i] ^ pad_val
27

28
    found = False
29
    for guess in range(256):
30
        iv[idx] = guess
31
        if check_padding(iv, ct):
32
            if pad_val == 1:
33
                iv[idx - 1] ^= 0xFF
34
                if not check_padding(iv, ct):
35
                    iv[idx - 1] ^= 0xFF  # 还原
36
                    continue
37
                iv[idx - 1] ^= 0xFF  # 还原
38

39
            I[idx] = guess ^ pad_val
40
            print(f"[+] 发现第 {idx} 字节: {hex(I[idx])}")
41
            found = True
42
            break
43

44
    if not found:
45
        print("[-] 爆破失败，请检查网络或 URL。")
46
        sys.exit(1)
47

48
print("[*] 中间状态 (I0) 爆破完成:", I.hex())
49

50
target_pt = b"user=admin" + bytes([6] * 6)
51

52
# 逆向计算出我们需要发送的伪造 IV
53
final_iv = bytearray(16)
54
for i in range(16):
55
    final_iv[i] = I[i] ^ target_pt[i]
56

57
final_cookie = (final_iv + ct).hex()
58
print("[+] 成功伪造 Admin Session Token:", final_cookie)
59

60
# 用伪造的 Cookie 获取 Flag
61
print("[*] 正在请求获取 Flag...")
62
r = requests.get(URL + "/", cookies={"session": final_cookie})
63

64
if "XMCTF{" in r.text or "flag{" in r.text:
65
    print("\n[🎉] 获取成功！页面内容：")
66
    print("-" * 50)
67
    # 提取并打印包含 flag 的那几行HTML
68
    for line in r.text.split("\n"):
69
        if "flag" in line.lower() or "xmctf" in line.lower():
70
            print(line.strip())
71
    print("-" * 50)
72
else:
73
    print("[-] 未找到 Flag，请检查返回的页面内容：")
74
    print(r.text)

1
from Crypto.Util.number import *
2
from secrets import flag
3

4
p =
5
a = 0
6
b =
7
c =
8
d =
9
e =
10

11

12
def add(P1, P2):
13
    if P1 is None:
14
        return P2
15

16
    x1, y1 = P1
17
    x2, y2 = P2
18

19
    l = (y2 - y1) * pow(x2 - x1, -1, p) % p
20
    x3 = (l**2 + a * l - b - x1 - x2) % p
21
    y3 = (l * (x1 - x3) - y1 - a * x3 - c) % p
22
    return (x3, y3)
23

24

25
def double(P):
26
    if P is None:
27
        return None
28

29
    x, y = P
30

31
    denom = (2 * y + a * x + c) % p
32
    num = (3 * x**2 + 2 * b * x + d - a * y) % p
33
    l = (num * pow(denom, -1, p)) % p
34
    x3 = (l**2 + a * l - b - 2 * x) % p
35
    y3 = (l * (x - x3) - y - a * x3 - c) % p
36
    return (x3, y3)
37

38

39
def mul(k, P):
40
    Q = None
41
    while k:
42
        if k & 1:
43
            Q = add(Q, P)
44
        P = double(P)
45
        k >>= 1
46
    return Q
47

48

49
m = bytes_to_long(flag)
50
G = (, )
51
P = mul(m, G)
52
print(P)

1
from Crypto.Util.number import *
2

3
p =
4
a = 0
5
b =
6
c =
7

8
G = (
9
    ,
10
    ,
11
)
12
P = (
13
    ,
14
    ,
15
)
16

17
yc = (-c * pow(2, -1, p)) % p
18
xc = (-b * pow(3, -1, p)) % p
19

20

21
def phi(Pt):
22
    x, y = Pt
23
    return (x - xc) * pow(y - yc, -1, p) % p
24

25

26
u = phi(P)
27
v = phi(G)
28

29
m = (u * pow(v, -1, p)) % p
30
print(long_to_bytes(m))

1
from hashlib import md5
2
from secret import flag
3

4
_H = lambda m: md5(m).digest()
5

6
S = set()
7

8
for _ in range(10):
9
    A, B, C = bytes.fromhex(input('A > ')), bytes.fromhex(input('B > ')), bytes.fromhex(input('C > '))
10
    ha, hb, hc = _H(A), _H(B), _H(C)
11
    assert ha == hb == hc
12

13
    D, E, F = bytes.fromhex(input('D > ')), bytes.fromhex(input('E > ')), bytes.fromhex(input('F > '))
14
    hd, he, hf = _H(ha + D), _H(hb + E), _H(hc + F)
15
    assert hd == he == hf
16

17
    G, H, I = bytes.fromhex(input('G > ')), bytes.fromhex(input('H > ')), bytes.fromhex(input('I > '))
18
    assert _H(hd + G) == _H(he + H) == _H(hf + I)
19

20
    cur = (A, B, C, D, E, F, G, H, I)
21
    assert len(set(cur)) == 9
22
    assert not any(x in S for x in cur)
23
    S.update(cur)
24

25
print(f'good: {flag}')

1
import hashlib
2
import os
3
import subprocess
4

5
from pwn import *
6

7
FASTCOLL = "/Users/zsm/CTF/tool/hashclash/bin/md5_fastcoll"
8

9

10
def get_fastcoll(prefix: bytes) -> tuple[bytes, bytes]:
11
    with open("prefix.bin", "wb") as f:
12
        f.write(prefix)
13

14
    subprocess.run(
15
        [FASTCOLL, "-p", "prefix.bin", "-o", "out1.bin", "out2.bin"],
16
        stdout=subprocess.DEVNULL,
17
        stderr=subprocess.DEVNULL,
18
    )
19

20
    with open("out1.bin", "rb") as f:
21
        out1 = f.read()
22
    with open("out2.bin", "rb") as f:
23
        out2 = f.read()
24

25
    m1 = out1[len(prefix) :]
26
    m2 = out2[len(prefix) :]
27
    return m1, m2
28

29

30
def generate_round():
31

32
    prefix_A = os.urandom(64)
33
    m1, m2 = get_fastcoll(prefix_A)
34
    m3, m4 = get_fastcoll(prefix_A + m1)
35

36
    A = prefix_A + m1 + m3
37
    B = prefix_A + m1 + m4
38
    C = prefix_A + m2 + m3
39
    ha = hashlib.md5(A).digest()
40

41
    pad_D = os.urandom(48)
42
    prefix_D = ha + pad_D
43
    m5, m6 = get_fastcoll(prefix_D)
44
    m7, m8 = get_fastcoll(prefix_D + m5)
45

46
    D = pad_D + m5 + m7
47
    E = pad_D + m5 + m8
48
    F = pad_D + m6 + m7
49
    hd = hashlib.md5(ha + D).digest()
50
    pad_G = os.urandom(48)
51
    prefix_G = hd + pad_G
52
    m9, m10 = get_fastcoll(prefix_G)
53
    m11, m12 = get_fastcoll(prefix_G + m9)
54

55
    G = pad_G + m9 + m11
56
    H = pad_G + m9 + m12
57
    I = pad_G + m10 + m11
58

59
    return (A, B, C, D, E, F, G, H, I)
60

61

62
def main():
63
    rounds_data = []
64
    for i in range(10):
65
        print(f"[*] 正在计算第 {i + 1}/10 轮...")
66
        rounds_data.append(generate_round())
67

68
    for f in ["prefix.bin", "out1.bin", "out2.bin"]:
69
        if os.path.exists(f):
70
            os.remove(f)
71

72
    p = remote("nc1.ctfplus.cn", 36943)
73

74
    for i, r_data in enumerate(rounds_data):
75
        A, B, C, D, E, F, G, H, I = r_data
76
        p.sendlineafter(b"A > ", A.hex().encode())
77
        p.sendlineafter(b"B > ", B.hex().encode())
78
        p.sendlineafter(b"C > ", C.hex().encode())
79
        p.sendlineafter(b"D > ", D.hex().encode())
80
        p.sendlineafter(b"E > ", E.hex().encode())
81
        p.sendlineafter(b"F > ", F.hex().encode())
82
        p.sendlineafter(b"G > ", G.hex().encode())
83
        p.sendlineafter(b"H > ", H.hex().encode())
84
        p.sendlineafter(b"I > ", I.hex().encode())
85

86
    p.interactive()
87

88

89
if __name__ == "__main__":
90
    main()

1
import random
2

3
import sympy
4
from Crypto.Util.number import *
5
from secret import c, flag
6

7

8
def get_poly(k):
9
    x, a, b = sympy.symbols("x a b")
10

11
    poly = x**3 - a * x**2 + b * x - c - k * n
12
    deriv1 = sympy.diff(poly, x)
13

14
    a1 = random.randint(2**119, 2**120)
15
    b1 = random.randint(2**119, 2**120)
16
    x1 = random.randint(2**510, 2**511)
17

18
    deriv1_num = deriv1.subs({x: x1, a: a1, b: b1})
19
    return x1, deriv1_num
20

21

22
def RSA():
23
    p = getPrime(512)
24
    q = getPrime(512)
25
    n = p * q
26
    k = getPrime(8)
27
    m = bytes_to_long(flag)
28
    e = inverse(c, (p - 1) * (q - 1))
29
    cipher = pow(m, e, n)
30
    return n, k, cipher
31

32

33
if __name__ == "__main__":
34
    n, k, cipher = RSA()
35
    x1, deriv1_num = get_poly(k)
36
    print("n =", n)
37
    print("x1 =", x1)
38
    print("cipher =", cipher)
39
    print("deriv1_num =", deriv1_num)

1
import sympy
2
from Crypto.Util.number import *
3

4
n = 63407394080105297388278430339692150920405158535377818019441803333853224630295862056336407010055412087494487003367799443217769754070745006473326062662322624498633283896600769211094059989665020951007831936771352988585565884180663310304029530702695576386164726400928158921458173971287469220518032325956366276127
5
x1 = 3481408902400626584294863390184557833125008467348169645656825368985677578418186933223051810792813745190000132321911937970968840332589150965113386330575858
6
deriv1_num = 36360623837143006554133449776905822223850034204333042340303731846698251185379183585401025894584873826284649058526470710038176516677326058549625930550928515944115160614909195746688504416967586844354012895944251800672195553936202084073217078119494546421088598245791873936703883718926122761577400400368341859847
7
cipher = 17359360992646515022812225990358117265652240629363564764503325024700251560440679272576574598620940996876220276588413345495658258508097150181947839726337961689195064024953824539654084620226127592330054674517861032601638881355220119605821814412919221685287567648072575917662044603845424779210032794782725398473
8

9

10
a1 = (3 * x1 * x1 - deriv1_num) // (2 * x1) + 1
11
b1 = deriv1_num - 3 * x1 * x1 + 2 * a1 * x1
12

13

14
kk = list(sympy.primerange(2**7, 2**8))
15

16

17
for k in kk:
18
    c = x1**3 - a1 * x1 * x1 + b1 * x1 - k * n
19

20
    m = pow(cipher, c, n)
21
    ff = long_to_bytes(m)
22
    if b"xmctf" in ff:
23
        print(ff)
24
        break

1
from Crypto.Util.number import getPrime, bytes_to_long
2
import random
3
import os
4
import signal
5

6
FLAG = os.environ.get("FLAG", "XMCTF{fake_flag}")
7
secret = os.urandom(64)
8

9
e = 263
10
bit_length = 1024
11

12

13
def get_rsa_params():
14
    p = getPrime(bit_length)
15
    q = getPrime(bit_length)
16
    N = p * q
17
    return N
18

19

20
class RSA_LCG:
21
    def __init__(self, seed, a, b, N):
22
        self.seed = seed
23
        self.a = a
24
        self.b = b
25
        self.N = N
26
        self.e = e
27

28
    def leak_params(self):
29

30
        diff = (self.b - self.a) % self.N
31
        leak_diff_e = pow(diff, self.e, self.N)
32

33
        return  self.a, leak_diff_e
34

35

36
    def next(self):
37

38
        self.seed = (self.a * self.seed + self.b) % self.N
39

40
        return pow(self.seed, self.e, self.N)
41

42

43
def challenge():
44

45
    N = get_rsa_params()
46

47
    seed = bytes_to_long(secret)
48
    assert seed < N
49

50
    a = random.getrandbits(bit_length)
51
    b = random.getrandbits(bit_length)
52

53
    rsa_lcg = RSA_LCG(seed, a, b, N)
54

55
    print(f"N = {N}")
56
    print(f"e = {e}")
57
    print("-" * 30)
58

59

60
    leak = rsa_lcg.leak_params()
61
    print(f"[+] leak: {leak}")
62

63

64
    out1 = rsa_lcg.next()
65
    print(f"[+] Output 1: {out1}")
66

67
    out2 = rsa_lcg.next()
68
    print(f"[+] Output 2: {out2}")
69

70

71
if __name__ == "__main__":
72
    challenge()
73
    signal.alarm(4)
74
    guess_hex = input("secret (hex): ").strip()
75
    guess = bytes.fromhex(guess_hex)
76
    if guess == secret:
77
        print(f"Good! Here is your flag: {FLAG}")

1
d = b - a mod N
2
b = d + a
3
x1 = a * secret + b = d + a * (secret + 1)
4
x2 = a * x1 + b = a * x1 + d + a
5

6
有三个关系
7
d^e mod N = leak
8
x1^e mod N = out1
9
(a*x1 + d + a)^e mod N = out2
10

11
多项式启动
12
f1(x) = x^e - out1
13
f2(x,d) = (a*x + d + a)^e - out2
14
f3(d) = d^e - leak
15

16
为了消去d，我们要对 f2(x,d) 和 f3(d) 关于变量 d 做 resultant
17

18
再和 x1^e = out1 联立
19
f1(x1) = x1^e - out1 = 0 mod N
20

21
那么gcd可以恢复了x1

1
import ast
2
import os
3
import pickle
4
import socket
5
from math import ceil
6

7
import gmpy2
8

9
try:
10
    import flint
11
except ImportError:
12
    flint = None
13

14

15
HOST = "nc1.ctfplus.cn"
16
PORT = 41668
17
E = 263
18
CACHE_FILE = os.path.join(os.path.dirname(__file__), "step_cache_263.pkl")
19

20

21
def batch_invert(values, modulus):
22
    prefix = [gmpy2.mpz(1)] * len(values)
23
    acc = gmpy2.mpz(1)
24
    for i, value in enumerate(values):
25
        prefix[i] = acc
26
        acc = gmpy2.f_mod(acc * value, modulus)
27
    inv_acc = gmpy2.invert(acc, modulus)
28
    out = [0] * len(values)
29
    for i in range(len(values) - 1, -1, -1):
30
        out[i] = gmpy2.f_mod(inv_acc * prefix[i], modulus)
31
        inv_acc = gmpy2.f_mod(inv_acc * values[i], modulus)
32
    return out
33

34

35
def build_step_products():
36
    steps = []
37
    offsets = [0]
38
    for n in range(1, E + 1):
39
        for k in range(n):
40
            base1 = E * (n - k)
41
            base2 = E * k
42
            num = 1
43
            den = 1
44
            for t in range(1, E + 1):
45
                num *= base1 - t + 1
46
                den *= base2 + t
47
            steps.append((num, den))
48
        offsets.append(len(steps))
49
    return {"steps": steps, "offsets": offsets}
50

51

52
def load_cache():
53
    if os.path.exists(CACHE_FILE):
54
        with open(CACHE_FILE, "rb") as fh:
55
            return pickle.load(fh)
56
    cache = build_step_products()
57
    with open(CACHE_FILE, "wb") as fh:
58
        pickle.dump(cache, fh, protocol=pickle.HIGHEST_PROTOCOL)
59
    return cache
60

61

62
STEP_CACHE = load_cache()
63

64

65
def build_step_multipliers(modulus):
66
    modulus = gmpy2.mpz(modulus)
67
    denoms = [gmpy2.mpz(den) % modulus for _, den in STEP_CACHE["steps"]]
68
    den_inv = batch_invert(denoms, modulus)
69
    return [
70
        gmpy2.f_mod(gmpy2.mpz(num) * inv, modulus)
71
        for (num, _), inv in zip(STEP_CACHE["steps"], den_inv)
72
    ]
73

74

75
def build_power_sums(c2, leak, modulus, step_mult):
76
    modulus = gmpy2.mpz(modulus)
77
    c2 = gmpy2.mpz(c2)
78
    leak = gmpy2.mpz(leak)
79
    offsets = STEP_CACHE["offsets"]
80
    neg_leak = gmpy2.f_mod(-leak, modulus)
81
    inv_neg_leak = gmpy2.invert(neg_leak, modulus)
82
    sums = [0] * (E + 1)
83
    for n in range(1, E + 1):
84
        choose = gmpy2.mpz(1)
85
        c_pow = gmpy2.mpz(1)
86
        l_pow = gmpy2.powmod(neg_leak, n, modulus)
87
        total = gmpy2.mpz(0)
88
        base = offsets[n - 1]
89
        for k in range(n + 1):
90
            total = gmpy2.f_mod(total + choose * c_pow * l_pow, modulus)
91
            if k == n:
92
                break
93
            choose = gmpy2.f_mod(choose * step_mult[base + k], modulus)
94
            c_pow = gmpy2.f_mod(c_pow * c2, modulus)
95
            l_pow = gmpy2.f_mod(l_pow * inv_neg_leak, modulus)
96
        sums[n] = gmpy2.f_mod(E * total, modulus)
97
    return sums
98

99

100
def build_resultant_coeffs(c2, leak, modulus):
101
    modulus = gmpy2.mpz(modulus)
102
    step_mult = build_step_multipliers(modulus)
103
    sums = build_power_sums(c2, leak, modulus, step_mult)
104

105
    elem = [0] * (E + 1)
106
    elem[0] = gmpy2.mpz(1)
107
    for k in range(1, E + 1):
108
        acc = gmpy2.mpz(0)
109
        sign = 1
110
        for i in range(1, k + 1):
111
            acc += sign * elem[k - i] * sums[i]
112
            sign = -sign
113
        elem[k] = gmpy2.f_mod(acc * gmpy2.invert(k, modulus), modulus)
114

115
    coeffs = [0] * (E + 1)
116
    for r in range(E + 1):
117
        coeffs[E - r] = int(gmpy2.f_mod(((-1) ** r) * elem[r], modulus))
118
    return coeffs
119

120

121
def mul_mod_xe_minus_c(poly_a, poly_b, c, modulus):
122
    size = len(poly_a)
123
    out = [0] * size
124
    for i, ai in enumerate(poly_a):
125
        if not ai:
126
            continue
127
        for j, bj in enumerate(poly_b):
128
            if not bj:
129
                continue
130
            k = i + j
131
            term = ai * bj % modulus
132
            if k < size:
133
                out[k] = (out[k] + term) % modulus
134
            else:
135
                out[k - size] = (out[k - size] + term * c) % modulus
136
    return out
137

138

139
def eval_poly_paterson_stockmeyer(coeffs, value, c1, modulus):
140
    degree = len(coeffs) - 1
141
    block = ceil((degree + 1) ** 0.5)
142
    size = len(value)
143

144
    value_pows = [[0] * size for _ in range(block)]
145
    value_pows[0][0] = 1
146
    for i in range(1, block):
147
        value_pows[i] = mul_mod_xe_minus_c(value_pows[i - 1], value, c1, modulus)
148

149
    giant = mul_mod_xe_minus_c(value_pows[block - 1], value, c1, modulus)
150

151
    grouped = []
152
    for start in range(0, degree + 1, block):
153
        acc = [0] * size
154
        for j, coeff in enumerate(coeffs[start : start + block]):
155
            if not coeff:
156
                continue
157
            power = value_pows[j]
158
            for idx, pv in enumerate(power):
159
                if pv:
160
                    acc[idx] = (acc[idx] + coeff * pv) % modulus
161
        grouped.append(acc)
162

163
    out = [0] * size
164
    for chunk in reversed(grouped):
165
        out = mul_mod_xe_minus_c(out, giant, c1, modulus)
166
        for i, val in enumerate(chunk):
167
            if val:
168
                out[i] = (out[i] + val) % modulus
169
    return out
170

171

172
def trim(poly):
173
    poly = poly[:]
174
    while poly and poly[-1] == 0:
175
        poly.pop()
176
    return poly
177

178

179
def poly_mod(f, g, modulus):
180
    f = trim(f)
181
    g = trim(g)
182
    while f and len(f) >= len(g):
183
        scale = f[-1] * pow(g[-1], -1, modulus) % modulus
184
        delta = len(f) - len(g)
185
        for i, coeff in enumerate(g):
186
            f[delta + i] = (f[delta + i] - scale * coeff) % modulus
187
        f = trim(f)
188
    return f
189

190

191
def poly_gcd(f, g, modulus):
192
    f = trim(f)
193
    g = trim(g)
194
    while g:
195
        f, g = g, poly_mod(f, g, modulus)
196
    inv = pow(f[-1], -1, modulus)
197
    return [coeff * inv % modulus for coeff in f]
198

199

200
def flint_poly_gcd(poly_f, poly_g, modulus):
201
    while poly_g != 0:
202
        _, rem = divmod(poly_f, poly_g)
203
        poly_f, poly_g = poly_g, rem
204
    lead = int(poly_f[poly_f.degree()])
205
    return poly_f * pow(lead, -1, modulus)
206

207

208
def flint_eval_paterson_stockmeyer(ctx, coeffs, value, modulus_poly):
209
    degree = len(coeffs) - 1
210
    block = ceil((degree + 1) ** 0.5)
211

212
    powers = [ctx([1])]
213
    for _ in range(1, block):
214
        powers.append(powers[-1].mul_mod(value, modulus_poly))
215
    giant = powers[-1].mul_mod(value, modulus_poly)
216

217
    chunks = []
218
    zero = ctx([0])
219
    for start in range(0, degree + 1, block):
220
        acc = zero
221
        for j, coeff in enumerate(coeffs[start : start + block]):
222
            if coeff:
223
                acc += ctx([coeff]) * powers[j]
224
        chunks.append(acc % modulus_poly)
225

226
    out = zero
227
    for chunk in reversed(chunks):
228
        out = out.mul_mod(giant, modulus_poly)
229
        out += chunk
230
        out %= modulus_poly
231
    return out
232

233

234
def recover_secret(n, a, leak, out1, out2):
235
    coeffs_u = build_resultant_coeffs(out2, leak, n)
236

237
    a_e = pow(a, E, n)
238
    u_of_x = [0] * E
239
    u_of_x[0] = a_e * (1 + out1) % n
240
    choose = 1
241
    for k in range(1, E):
242
        choose = choose * (E - k + 1) // k
243
        u_of_x[k] = a_e * choose % n
244

245
    if flint is not None:
246
        ctx = flint.fmpz_mod_poly_ctx(n)
247
        base_poly = ctx([(-out1) % n] + [0] * (E - 1) + [1])
248
        eliminated_poly = flint_eval_paterson_stockmeyer(ctx, coeffs_u, ctx(u_of_x), base_poly)
249
        factor = flint_poly_gcd(base_poly, eliminated_poly, n)
250
        if factor.degree() != 1:
251
            raise ValueError(f"unexpected gcd degree: {factor.degree()}")
252
        x1 = (-int(factor[0])) % n
253
    else:
254
        eliminated = eval_poly_paterson_stockmeyer(coeffs_u, u_of_x, out1, n)
255
        base = [(-out1) % n] + [0] * (E - 1) + [1]
256
        factor = poly_gcd(base, eliminated, n)
257
        if len(factor) != 2:
258
            raise ValueError(f"unexpected gcd degree: {len(factor) - 1}")
259
        x1 = (-factor[0]) % n
260

261
    bound = 1 << 1024
262
    d = None
263

264
    residue_small = x1 % a
265
    small_count = max(1, (bound - 1 - residue_small) // a + 1) if residue_small < bound else 0
266
    for k in range(small_count):
267
        candidate = residue_small + k * a
268
        if candidate < bound and pow(candidate, E, n) == leak:
269
            d = candidate
270
            break
271

272
    if d is None:
273
        residue = (-x1) % a
274
        near_count = max(1, (bound - 1 - residue) // a + 1) if residue < bound else 0
275
        for k in range(near_count):
276
            small = residue + k * a
277
            if small < bound:
278
                candidate = n - small
279
                if pow(candidate, E, n) == leak:
280
                    d = candidate
281
                    break
282

283
    if d is None:
284
        raise ValueError("failed to recover d from x1")
285

286
    return ((x1 - d) * pow(a, -1, n) - 1) % n
287

288

289
def parse_challenge():
290
    sock = socket.create_connection((HOST, PORT), timeout=10)
291
    file = sock.makefile("rwb", buffering=0)
292

293
    n = int(file.readline().decode().split("=", 1)[1].strip())
294
    _ = int(file.readline().decode().split("=", 1)[1].strip())
295
    file.readline()
296

297
    leak_line = file.readline().decode().split(":", 1)[1].strip()
298
    a, leak = ast.literal_eval(leak_line)
299
    out1 = int(file.readline().decode().split(":", 1)[1].strip())
300
    out2 = int(file.readline().decode().split(":", 1)[1].strip())
301
    return sock, file, n, a, leak, out1, out2
302

303

304
def main():
305
    sock, file, n, a, leak, out1, out2 = parse_challenge()
306
    secret = recover_secret(n, a, leak, out1, out2)
307
    guess = secret.to_bytes(64, "big").hex().encode()
308
    file.write(guess + b"\n")
309
    print(file.readline().decode(errors="ignore").strip())
310
    sock.close()
311

312

313
if __name__ == "__main__":
314
    main()

1
from Crypto.Util.number import getRandomNBitInteger
2
from Crypto.Cipher import AES
3
from Crypto.Util.Padding import pad
4
from hashlib import md5
5
import signal
6
import os
7

8
FLAG = os.getenv("FLAG", "xmctf{fake_flag}")
9
class MLFSR:
10
    def __init__(self, n, seed, mask, lfsr=None):
11
        self.state = [int(b) for b in f"{seed:0{n}b}"]
12
        self.mask_bits = [int(b) for b in f"{mask:0{n}b}"]
13
        self.n = n
14
        self.lfsr = lfsr
15

16
    def update(self):
17
        s = sum([self.state[i] * self.mask_bits[i] for i in range(self.n)]) & 1
18
        self.state = self.state[1:] + [s]
19

20
    def __call__(self):
21
        if self.lfsr:
22
            if self.lfsr():
23
                self.update()
24
            return self.state[-1]
25
        else:
26
            self.update()
27
            return self.state[-1]
28

29

30
class LFSR(MLFSR):
31
    def __init__(self, n, seed, mask):
32
        super().__init__(n, seed, mask, lfsr=None)
33

34

35
signal.alarm(60)
36

37
secret = f'fakeflag{{{os.urandom(16).hex()}}}'
38

39
n = 64
40
seed = getRandomNBitInteger(n)
41
mask1, mask2 = getRandomNBitInteger(n), getRandomNBitInteger(n)
42
lfsr1 = LFSR(n, seed, mask1)
43
lfsr2 = MLFSR(n, seed, mask2, lfsr1)
44
print(f"mask1 = {mask1}")
45
print(f"mask2 = {mask2}")
46
print(f"output = {sum(lfsr2() << (n - 1 - i) for i in range(n))}")
47
print(f"enc = {AES.new(key=md5(str(seed).encode()).digest(), mode=AES.MODE_ECB).encrypt(pad(secret.encode(), 16)).hex()}")
48

49
if input('> ') == secret:
50
    print('🤭:', FLAG)