a ctfer on the load

1
import random
2
print('----Welcome to my division calc----')
3
print('''
4
menu:
5
      [1]  Division calc
6
      [2]  Get flag
7
''')
8
while True:
9
    choose = input(': >>> ')
10
    if choose == '1':
11
        try:
12
            denominator = int(input('input the denominator: >>> '))
13
        except:
14
            print('INPUT NUMBERS')
15
            continue
16
        nominator = random.getrandbits(32)
17
        if denominator == '0':
18
            print('NO YOU DONT')
19
            continue
20
        else:
21
            print(f'{nominator}//{denominator} = {nominator//denominator}')
22
    elif choose == '2':
23
        try:
24
            ans = input('input the answer: >>> ')
25
            rand1 = random.getrandbits(11000)
26
            rand2 = random.getrandbits(10000)
27
            correct_ans = rand1 // rand2
28
            if correct_ans == int(ans):
29
                print('WOW')
30
                with open('flag', 'r') as f:
31
                    print(f'Here is your flag: {f.read()}')
32
            else:
33
                print(f'NOPE, the correct answer is {correct_ans}')
34
        except:
35
            print('INPUT NUMBERS')
36
    else:
37
        print('Invalid choice')

1
from pwn import remote
2
import random
3
from randcrack import RandCrack
4
rc = RandCrack()
5
conn = remote('8.147.132.32', 22975)
6
outputs = []
7

8
for _ in range(624):
9
    conn.recvuntil(b': >>> ')
10
    conn.sendline(b'1')
11
    conn.recvuntil(b'input the denominator: >>> ')
12
    conn.sendline(b'1')
13
    line = conn.recvline().decode().strip()
14
    nominator = int(line.split('=')[1].strip())
15
    outputs.append(nominator)
16
    rc.submit(nominator)
17

18

19
rand1 =rc.predict_getrandbits(11000)
20
rand2 = rc.predict_getrandbits(10000)
21
correct_ans = rand1 // rand2
22
print(correct_ans)
23
conn.recvuntil(b': >>> ')
24
conn.sendline(b'2')
25
conn.recvuntil(b'input the answer: >>>')
26
conn.sendline(correct_ans)
27
conn.interactive()

1
from Crypto.Util.number import *
2
from Crypto.Cipher import ChaCha20
3
import hashlib
4
from secret import flag
5

6

7
class Complex:
8
    def __init__(self, re, im):
9
        self.re = re
10
        self.im = im
11

12
    def __mul__(self, c):
13
        re_ = self.re * c.re - self.im * c.im
14
        im_ = self.re * c.im + self.im * c.re
15
        return Complex(re_, im_)
16

17
    def __eq__(self, c):
18
        return self.re == c.re and self.im == c.im
19

20
    def __rshift__(self, m):
21
        return Complex(self.re >> m, self.im >> m)
22

23
    def __lshift__(self, m):
24
        return Complex(self.re << m, self.im << m)
25

26
    def __str__(self):
27
        if self.im == 0:
28
            return str(self.re)
29
        elif self.re == 0:
30
            if abs(self.im) == 1:
31
                return f"{'-' if self.im < 0 else ''}i"
32
            else:
33
                return f"{self.im}i"
34
        else:
35
            return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"
36

37
    def tolist(self):
38
        return [self.re, self.im]
39

40

41
def complex_pow(c, exp, n):
42
    result = Complex(1, 0)
43
    while exp > 0:
44
        if exp & 1:
45
            result = result * c
46
            result.re = result.re % n
47
            result.im = result.im % n
48
        c = c * c
49
        c.re = c.re % n
50
        c.im = c.im % n
51
        exp >>= 1
52
    return result
53

54
bits = 128
55
p = getPrime(1024)
56
q = getPrime(1024)
57
n = p * q
58
m = Complex(getRandomRange(1, n), getRandomRange(1, n))
59
e = 3
60
c = complex_pow(m, e, n)
61
print(f"n = {n}")
62
print(f"mh = {(m >> bits << bits).tolist()}")
63
print(f"C = {c.tolist()}")
64
print(f"enc = {ChaCha20.new(key=hashlib.sha256(str(m.re + m.im).encode()).digest(), nonce=b'Pr3d1ctmyxjj').encrypt(flag)}")

1
import itertools
2
from Crypto.Util.number import *
3
from tqdm import *
4
def small_roots(f, bounds, m=1, d=None):
5
    if not d:
6
        d = f.degree()
7
    R = f.base_ring()
8
    N = R.cardinality()
9
    f /= f.coefficients().pop(0)
10
    f = f.change_ring(ZZ)
11
    G = Sequence([], f.parent())
12
    for i in range(m + 1):
13
        base = N ^ (m - i) * f ^ i
14
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
15
            g = base * prod(map(power, f.variables(), shifts))
16
            G.append(g)
17
    B, monomials = G.coefficient_matrix()
18
    monomials = vector(monomials)
19
    factors = [monomial(*bounds) for monomial in monomials]
20
    for i, factor in enumerate(factors):
21
        B.rescale_col(i, factor)
22
    B = B.dense_matrix().LLL()
23
    B = B.change_ring(QQ)
24
    for i, factor in enumerate(factors):
25
        B.rescale_col(i, 1 / factor)
26
    H = Sequence([], f.parent().change_ring(QQ))
27
    for h in filter(None, B * monomials):
28
        H.append(h)
29
        I = H.ideal()
30
        if I.dimension() == -1:
31
            H.pop()
32
        elif I.dimension() == 0:
33
            roots = []
34
            for root in I.variety(ring=ZZ):
35
                root = tuple(R(root[var]) for var in f.variables())
36
                roots.append(root)
37
            return roots
38
    return []
39

40
k =  128
41
n =
42
mh =
43
C =
44

45
# 定义多项式环
46
PR.<x, y> = PolynomialRing(Zmod(n))
47

48
a = mh[0]  + x  # x 是 al
49
b = mh[1]  + y  # y 是 bl
50
f1 = (a^3 - 3*a*b^2) - C[0]  # 实部方程
51
f2 = (3*a^2*b - b^3) - C[1]  # 虚部方程
52
res = small_roots(f1,bounds=(2^128,2^128),m=1,d=3)
53
if res != []:
54
     print(res)
55

56
x=
57
y=
58

59
from Crypto.Cipher import ChaCha20
60
import hashlib
61

62
n =
63
mh =
64
enc =
65
x=
66
y=
67
s = (mh[0]) + (mh[1])+x+y
68
key = hashlib.sha256(str(s).encode()).digest()
69
cipher = ChaCha20.new(key=key, nonce=b'Pr3d1ctmyxjj')
70
flag = cipher.decrypt(enc)
71
print(flag)

1
# Visit https://www.lddgo.net/string/pyc-compile-decompile for more information
2
# Version : Python 3.8
3

4
'''
5
Created on Sun Mar 30 18:25:08 2025
6

7
@author: Crypto0
8

9
import re
10
import base64
11
import os
12
import sys
13
from gmssl import sm4
14
from Crypto.Util.Padding import pad
15
import binascii
16
from random import shuffle, randrange
17

18
N = 49
19
p = 3
20
q = 128
21
d = 3
22
assert q > (6 * d + 1) * p
23
R.<x> = ZZ[]
24
def generate_T(d1, d2):
25
    assert N >= d1 + d2
26
    s = [1] * d1 + [-1] * d2 + [0] * (N - d1 - d2)
27
    shuffle(s)
28
    return R(s)
29

30
def invert_mod_prime(f, p):
31
    Rp = R.change_ring(Integers(p)).quotient(x^N - 1)
32
    return R(lift(1 / Rp(f)))
33

34
def convolution(f, g):
35
    return (f * g) % (x^N - 1)
36

37
def lift_mod(f, q):
38
    return R([((f[i] + q // 2) % q) - q // 2 for i in range(N)])
39

40
def poly_mod(f, q):
41
    return R([f[i] % q for i in range(N)])
42

43
def invert_mod_pow2(f, q):
44
    assert q.is_power_of(2)
45
    g = invert_mod_prime(f, 2)
46
    while True:
47
        r = lift_mod(convolution(g, f), q)
48
        if r == 1:
49
            return g
50
        g = lift_mod(convolution(g, 2 - r), q)
51

52
def generate_message():
53
    return R([randrange(p) - 1 for _ in range(N)])
54

55
def generate_key():
56
    while True:
57
        try:
58
            f = generate_T(d + 1, d)
59
            g = generate_T(d, d)
60
            Fp = poly_mod(invert_mod_prime(f, p), p)
61
            Fq = poly_mod(invert_mod_pow2(f, q), q)
62
            break
63
        except:
64
            continue
65
    h = poly_mod(convolution(Fq, g), q)
66
    return h, (f, g)
67

68
def encrypt_message(m, h):
69
    e = lift_mod(p * convolution(h, generate_T(d, d)) + m, q)
70
    return e
71

72
def save_ntru_keys():
73
    h, secret = generate_key()
74
    with open("pub_key.txt", "w") as f:
75
        f.write(str(h))
76
    m = generate_message()
77
    with open("priv_key.txt", "w") as f:
78
        f.write(str(m))
79
    e = encrypt_message(m, h)
80
    with open("enc.txt", "w") as f:
81
        f.write(str(e))
82

83
def terms(poly_str):
84
    terms = []
85
    pattern = r\'([+-]?\\s*x\\^?\\d*|[-+]?\\s*\\d+)\'
86
    matches = re.finditer(pattern, poly_str.replace(\' \', \'\'))
87

88
    for match in matches:
89
        term = match.group()
90
        if term == \'+x\' or term == \'x\':
91
            terms.append(1)
92
        elif term == \'-x\':
93
            terms.append(-1)
94
        elif \'x^\' in term:
95
            coeff_part = term.split(\'x^\')[0]
96
            exponent = int(term.split(\'x^\')[1])
97
            if not coeff_part or coeff_part == \'+\':
98
                coeff = 1
99
            elif coeff_part == \'-\':
100
                coeff = -1
101
            else:
102
                coeff = int(coeff_part)
103
            terms.append(coeff * exponent)
104
        elif \'x\' in term:
105
            coeff_part = term.split(\'x\')[0]
106
            if not coeff_part or coeff_part == \'+\':
107
                terms.append(1)
108
            elif coeff_part == \'-\':
109
                terms.append(-1)
110
            else:
111
                terms.append(int(coeff_part))
112
        else:
113
            if term == \'+1\' or term == \'1\':
114
                terms.append(0)
115
                terms.append(-0)
116
    return terms
117

118
def gen_key(poly_terms):
119
    binary = [0] * 128
120
    for term in poly_terms:
121
        exponent = abs(term)
122
        if term > 0 and exponent <= 127:
123
            binary[127 - exponent] = 1
124
    binary_str = \'\'.join(map(str, binary))
125
    hex_key = hex(int(binary_str, 2))[2:].upper().zfill(32)
126
    return hex_key
127

128
def read_polynomial_from_file(filename):
129
    with open(filename, \'r\') as file:
130
        return file.read().strip()
131

132

133
def sm4_encrypt(key, plaintext):
134
    assert len(key) == 16, "SM4 key must be 16 bytes"
135
    cipher = sm4.CryptSM4()
136
    cipher.set_key(key, sm4.SM4_ENCRYPT)
137
    padded_plaintext = pad(plaintext, 16)
138
    return cipher.crypt_ecb(padded_plaintext)
139

140
def sm4_encrypt_file(input_path, output_path, key):
141
    with open(input_path, \'rb\') as f:
142
        plaintext = f.read()
143

144
    ciphertext = sm4_encrypt(key, plaintext)
145

146
    with open(output_path, \'wb\') as f:
147
        f.write(ciphertext)
148

149
def resource_path(relative_path):
150
    if getattr(sys, \'frozen\', False):
151
        base_path = sys._MEIPASS
152
    else:
153
        base_path = os.path.abspath(".")
154
    return os.path.join(base_path, relative_path)
155

156
def encrypt_directory(directory, sm4_key, extensions=[".txt"]):
157
    if not os.path.exists(directory):
158
        print(f"Directory does not exist: {directory}")
159
        return
160

161
    for root, _, files in os.walk(directory):
162
        for file in files:
163
            if any(file.endswith(ext) for ext in extensions):
164
                input_path = os.path.join(root, file)
165
                output_path = input_path + ".enc"
166

167
                try:
168
                    sm4_encrypt_file(input_path, output_path, sm4_key)
169
                    os.remove(input_path)
170
                    print(f"Encrypted: {input_path} -> {output_path}")
171
                except Exception as e:
172
                    print(f"Error encrypting {input_path}: {str(e)}")
173

174
def main():
175
    try:
176
        save_ntru_keys()
177
        poly_str = read_polynomial_from_file("priv_key.txt")
178
        poly_terms = terms(poly_str)
179
        sm4_key = binascii.unhexlify(poly_terms)
180
        user_name = os.getlogin()
181
        target_dir = os.path.join("C:\\Users", user_name, "Desktop", "test_files")
182

183
        if not os.path.exists(target_dir):
184
            os.makedirs(target_dir, exist_ok=True)
185
            print(f"Created directory: {target_dir}")
186
            return
187

188
        txt_files = [f for f in os.listdir(target_dir)
189
                    if f.endswith(\'.txt\') and os.path.isfile(os.path.join(target_dir, f))]
190

191
        if not txt_files:
192
            print("No .txt files found in directory")
193
            return
194

195
        for txt_file in txt_files:
196
            file_path = os.path.join(target_dir, txt_file)
197
            try:
198
                with open(file_path, \'rb\') as f:
199
                    test_data = f.read()
200

201
                ciphertext = sm4_encrypt(sm4_key, test_data)
202
                encrypted_path = file_path + \'.enc\'
203

204
                with open(encrypted_path, \'wb\') as f:
205
                f.write(ciphertext)
206
            except Exception as e:
207
                print(f"Error processing {txt_file}: {str(e)}")
208

209
    except Exception as e:
210
        print(f"Fatal error: {str(e)}")
211

212
if __name__ == "__main__":
213
    main()
214
'''

1
e =
2
-x^48 - x^46 + x^45 + x^43 - x^42 + x^41 + x^40 + x^36 - x^35 + x^34 - x^33 + x^32 - x^30 + x^29 - x^28 - x^27 - x^26 - x^25 - x^23 - x^22 + x^21 + x^20 + x^19 + x^18 - x^17 - x^16 - x^15 - x^14 - x^12 + x^9 - x^7 - x^6 - x^5 - x^4 + x^3 - x + 1

1
h =

1
import binascii
2
import re
3
from Crypto.Util.number import *
4
from gmssl import sm4
5

6
# 解析多项式字符串，提取每一项的次数 * 系数
7
def terms(poly_str):
8
    terms = []
9
    # 匹配 x^n、x、常数项等
10
    pattern = r'([+-]?x\^?\d*|[-+]?\d+)'
11
    matches = re.finditer(pattern, poly_str.replace(' ', ''))
12

13
    for match in matches:
14
        term = match.group()
15
        if term in ('+x', 'x'):
16
            terms.append(1)
17
        elif term == '-x':
18
            terms.append(-1)
19
        elif 'x^' in term:
20
            coeff_part, exponent = term.split('x^')
21
            exponent = int(exponent)
22
            if not coeff_part or coeff_part == '+':
23
                coeff = 1
24
            elif coeff_part == '-':
25
                coeff = -1
26
            else:
27
                coeff = int(coeff_part)
28
            terms.append(coeff * exponent)
29
        elif 'x' in term:
30
            coeff_part = term.split('x')[0]
31
            if not coeff_part or coeff_part == '+':
32
                terms.append(1)
33
            elif coeff_part == '-':
34
                terms.append(-1)
35
            else:
36
                terms.append(int(coeff_part))
37
        else:
38
            # 常数项 x^0，不影响密钥，但加入 0 是为了保留结构
39
            if term == '+1' or term == '1':
40
                terms.append(0)
41
            elif term == '-1':
42
                terms.append(-0)
43
    return terms
44

45
# 根据解析到的多项式项生成128位密钥（用于 SM4）
46
def gen_key(poly_terms):
47
    binary = [0] * 128
48
    for term in poly_terms:
49
        exponent = abs(term)
50
        if term > 0 and exponent <= 127:
51
            binary[127 - exponent] = 1  # 最高位是 x^127
52
    binary_str = ''.join(map(str, binary))
53
    hex_key = hex(int(binary_str, 2))[2:].upper().zfill(32)
54
    return binascii.unhexlify(hex_key)
55

56
# SM4 解密函数（ECB 模式）
57
def sm4_decrypt(key, ciphertext):
58
    assert len(key) == 16, "SM4 key must be 16 bytes"
59
    cipher = sm4.CryptSM4()
60
    cipher.set_key(key, sm4.SM4_DECRYPT)
61
    return cipher.crypt_ecb(ciphertext)
62

63
# 多项式字符串
64
poly_str = "-x^48-x^46+x^45+x^43-x^42+x^41+x^40+x^36-x^35+x^34-x^33+x^32-" \
65
           "x^30+x^29-x^28-x^27-x^26-x^25-x^23-x^22+x^21+x^20+x^19+x^18-" \
66
           "x^17-x^16-x^15-x^14-x^12+x^9-x^7-x^6-x^5-x^4+x^3-x+1"
67

68
# 提取多项式项
69
poly_terms = terms(poly_str)
70
print("多项式项：", poly_terms)
71

72
# 生成 SM4 密钥（16 字节）
73
sm4_key = gen_key(poly_terms)
74
print("SM4 密钥（hex）：", sm4_key.hex())
75

76
# 密文（注意这里原代码是 hex 字符串，需要转换成字节）
77
ciphertext_hex = (
78
    "bf0cb5cc6bea6146e9c1f109df953a57"
79
    "daa416d38a8ffba6438e7e599613e01f"
80
    "3b9a53dace4ccd55cd3e55ef88e0b835"
81
)
82
ciphertext = binascii.unhexlify(ciphertext_hex)
83

84
# 解密
85
plaintext = sm4_decrypt(sm4_key, ciphertext)
86
print("解密结果：", plaintext)

1
import string
2
import random
3
from secret import flag
4

5
assert flag.startswith('XYCTF{') and flag.endswith('}')
6
flag = flag.rstrip('}').lstrip('XYCTF{')
7

8
table = string.ascii_letters + string.digits
9
assert all(i in table for i in flag)
10
r = random.Random()
11

12
class PRNG:
13
    def __init__(self, seed):
14
        self.a = 1145140
15
        self.b = 19198100
16
        random.seed(seed)
17

18
    def next(self):
19
        x = random.randint(self.a, self.b)
20
        random.seed(x ** 2 + 1)
21
        return x
22

23
    def round(self, k):
24
        for _ in range(k):
25
            x = self.next()
26
        return x
27

28
def encrypt(msg, a, b):
29
    c = [(a * table.index(m) + b) % 19198111 for m in msg]
30
    return c
31

32
seed = int(input('give me seed: '))
33
prng = PRNG(seed)
34
a = prng.round(r.randrange(2**16))
35
b = prng.round(r.randrange(2**16))
36
enc = encrypt(flag, a, b)
37
print(enc)

1
from string import ascii_letters, digits
2
import re
3
from typing import List, Tuple, Optional, Set
4

5
CHAR_TABLE = ascii_letters + digits
6
MOD = 19198111
7
ENC = []
8
def extended_gcd(a: int, b: int) -> Tuple[int, int, int]:
9
    if a == 0:
10
        return b, 0, 1
11
    g, y, x = extended_gcd(b % a, a)
12
    return g, x - (b // a) * y, y
13

14
def modinv(a: int, m: int) -> Optional[int]:
15
    g, x, _ = extended_gcd(a, m)
16
    return x % m if g == 1 else None
17

18
def is_readable(s: str) -> bool:
19
    return bool(re.search(r'[A-Za-z]{2,}', s)) and len(re.findall(r'\d', s)) < 5
20

21
def solve() -> List[str]:
22
    candidates: Set[str] = set()
23
    processed: Set[Tuple[int, int]] = set()
24
    table_len = len(CHAR_TABLE)
25

26
    cipher_pairs = [(i, j) for i in range(len(ENC))
27
                   for j in range(i + 1, len(ENC)) if ENC[i] != ENC[j]]
28

29
    for idx1, idx2 in cipher_pairs:
30
        c1, c2 = ENC[idx1], ENC[idx2]
31
        delta_c = (c1 - c2) % MOD
32

33
        for i1 in range(table_len):
34
            p1 = ord(CHAR_TABLE[i1])
35
            for i2 in range(table_len):
36
                if i1 == i2:
37
                    continue
38
                p2 = ord(CHAR_TABLE[i2])
39

40
                delta_i = (p1 - p2) % MOD
41
                inv = modinv(delta_i, MOD)
42
                if inv is None:
43
                    continue
44

45
                a = (delta_c * inv) % MOD
46
                b = (c1 - a * p1) % MOD
47

48
                if (a, b) in processed:
49
                    continue
50
                processed.add((a, b))
51

52
                a_inv = modinv(a, MOD)
53
                if a_inv is None:
54
                    continue
55

56
                flag = []
57
                for c in ENC:
58
                    i = ((c - b) * a_inv) % MOD
59
                    if not (0 <= i < table_len):
60
                        break
61
                    flag.append(CHAR_TABLE[i])
62
                else:
63
                    candidate = ''.join(flag)
64
                    if len(candidate) == len(ENC):
65
                        candidates.add(candidate)
66

67
    readable = [f for f in candidates if is_readable(f)]
68
    return readable if readable else list(candidates)
69

70
def main():
71
    results = solve()
72
    print(f"Found {len(results)} possible candidates:")
73
    for idx, flag in enumerate(results, 1):
74
        print(f"#{idx}: XYCTF{{{flag}}}")
75

76
if __name__ == "__main__":
77
    main()

1
class ComComplex:
2
    def __init__(self, value=[0,0,0,0]):
3
        self.value = value
4
    def __str__(self):
5
        s = str(self.value[0])
6
        for k,i in enumerate(self.value[1:]):
7
            if i >= 0:
8
                s += '+'
9
            s += str(i) +'ijk'[k]
10
        return s
11
    def __add__(self,x):
12
        return ComComplex([i+j for i,j in zip(self.value,x.value)])
13
    def __mul__(self,x):
14
        a = self.value[0]*x.value[0]-self.value[1]*x.value[1]-self.value[2]*x.value[2]-self.value[3]*x.value[3]
15
        b = self.value[0]*x.value[1]+self.value[1]*x.value[0]+self.value[2]*x.value[3]-self.value[3]*x.value[2]
16
        c = self.value[0]*x.value[2]-self.value[1]*x.value[3]+self.value[2]*x.value[0]+self.value[3]*x.value[1]
17
        d = self.value[0]*x.value[3]+self.value[1]*x.value[2]-self.value[2]*x.value[1]+self.value[3]*x.value[0]
18
        return ComComplex([a,b,c,d])
19
    def __mod__(self,x):
20
        return ComComplex([i % x for i in self.value])
21
    def __pow__(self, x, n=None):
22
        tmp = ComComplex(self.value)
23
        a = ComComplex([1,0,0,0])
24
        while x:
25
            if x & 1:
26
                a *= tmp
27
            tmp *= tmp
28
            if n:
29
                a %= n
30
                tmp %= n
31
            x >>= 1
32
        return a
33

34
from Crypto.Util.number import *
35
from secret import flag, hint
36

37
p = getPrime(256)
38
q = getPrime(256)
39
r = getPrime(256)
40
n = p * q * r
41

42
P = getPrime(512)
43
assert len(hint) == 20
44
hints = ComComplex([bytes_to_long(hint[i:i+5]) for i in range(0,20,5)])
45
keys = ComComplex([0, p, q, r])
46
print('hint =',hints)
47
print('gift =',hints*keys%P)
48
print('P =',P)
49

50
e = 65547
51
m = ComComplex([bytes_to_long(flag[i:i+len(flag)//4+1]) for i in range(0,len(flag),len(flag)//4+1)])
52
c = pow(m, e, n)
53
print('n =', n)
54
print('c =', c)

1
from Crypto.Util.number import long_to_bytes, inverse, bytes_to_long, getPrime
2
from sympy import Matrix
3
import sys
4

5
class ComComplex:
6
    def __init__(self, value=[0,0,0,0]):
7
        self.value = value
8
    def __str__(self):
9
        s = str(self.value[0])
10
        for k,i in enumerate(self.value[1:]):
11
            if i >= 0:
12
                s += '+'
13
            s += str(i) +'ijk'[k]
14
        return s
15
    def __add__(self,x):
16
        return ComComplex([i+j for i,j in zip(self.value,x.value)])
17
    def __mul__(self,x):
18
        a = self.value[0]*x.value[0]-self.value[1]*x.value[1]-self.value[2]*x.value[2]-self.value[3]*x.value[3]
19
        b = self.value[0]*x.value[1]+self.value[1]*x.value[0]+self.value[2]*x.value[3]-self.value[3]*x.value[2]
20
        c = self.value[0]*x.value[2]-self.value[1]*x.value[3]+self.value[2]*x.value[0]+self.value[3]*x.value[1]
21
        d = self.value[0]*x.value[3]+self.value[1]*x.value[2]-self.value[2]*x.value[1]+self.value[3]*x.value[0]
22
        return ComComplex([a,b,c,d])
23
    def __mod__(self,x):
24
        return ComComplex([i % x for i in self.value])
25
    def __pow__(self, x, n=None):
26
        tmp = ComComplex(self.value)
27
        a = ComComplex([1,0,0,0])
28
        while x:
29
            if x & 1:
30
                a *= tmp
31
            tmp *= tmp
32
            if n:
33
                a %= n
34
                tmp %= n
35
            x >>= 1
36
        return a
37

38
A = 375413371936
39
B = 452903063925
40
C = 418564633198
41
D = 452841062207
42

43
G0 =
44
G1 =
45
G2 =
46
G3 =
47

48
P =
49

50
M = Matrix([
51
    [-B,      -C,      -D],
52
    [ A,      -D,       C],
53
    [ D,       A,      -B]
54
])
55
v = Matrix([G0 % P, G1 % P, G2 % P])
56

57
M_inv = M.inv_mod(P)
58
solution = M_inv * v
59
p1 = int(solution[0] % P)
60
q1 = int(solution[1] % P)
61
r1 = int(solution[2] % P)
62
print(p1,q1,r1)

1
from Crypto.Util.number import *
2
from Crypto.Util.number import GCD as gcd
3
class ComComplex:
4
    def __init__(self, value=[0,0,0,0]):
5
        self.value = value
6
    def __str__(self):
7
        s = str(self.value[0])
8
        for k,i in enumerate(self.value[1:]):
9
            if i >= 0:
10
                s += '+'
11
            s += str(i) +'ijk'[k]
12
        return s
13
    def __add__(self,x):
14
        return ComComplex([i+j for i,j in zip(self.value,x.value)])
15
    def __mul__(self,x):
16
        a = self.value[0]*x.value[0]-self.value[1]*x.value[1]-self.value[2]*x.value[2]-self.value[3]*x.value[3]
17
        b = self.value[0]*x.value[1]+self.value[1]*x.value[0]+self.value[2]*x.value[3]-self.value[3]*x.value[2]
18
        c = self.value[0]*x.value[2]-self.value[1]*x.value[3]+self.value[2]*x.value[0]+self.value[3]*x.value[1]
19
        d = self.value[0]*x.value[3]+self.value[1]*x.value[2]-self.value[2]*x.value[1]+self.value[3]*x.value[0]
20
        return ComComplex([a,b,c,d])
21
    def __mod__(self,x):
22
        return ComComplex([i % x for i in self.value])
23
    def __pow__(self, x, n=None):
24
        tmp = ComComplex(self.value)
25
        a = ComComplex([1,0,0,0])
26
        while x:
27
            if x & 1:
28
                a *= tmp
29
            tmp *= tmp
30
            if n:
31
                a %= n
32
                tmp %= n
33
            x >>= 1
34
        return a
35
p,q,r=
36
e=65547
37
c = ComComplex([])
38
pqr=[p,q,r]
39
def inver_d(s):
40
   phi_s = s *(s-1)*(s**2-1)
41
   g_s = gcd(e, phi_s)
42
   phi_prime = phi_s // g_s
43
   d = inverse(e, phi_prime)
44
   return d
45

46
dp=inver_d(p)
47
dq=inver_d(q)
48
dr=inver_d(r)
49

50
cp=c%p
51
cq=c%q
52
cr=c%r
53

54
mp=pow(cp,dp,p)
55
mq=pow(cq,dq,q)
56
mr=pow(cr,dr,r)
57
def crt(shares):
58
    """中国剩余定理合并多个四元复数的每一分量"""
59
    res = []
60
    for i in range(4):
61
        # 提取每个四元数第 i 位的值 和对应模数
62
        a = [s.value[i] for s, _ in shares]
63
        m = [mod for _, mod in shares]
64
        # 使用单分量CRT合并结果
65
        res.append(int(crt_r(a, m)))
66
    return ComComplex(res)
67

68
def crt_r(a, m):
69
    """中国剩余定理求解单个整数分量"""
70
    M = 1
71
    for mi in m:
72
        M *= mi  # 总模数 M 是所有模数的乘积
73

74
    res = 0
75
    for ai, mi in zip(a, m):
76
        Mi = M // mi
77
        inv = inverse(Mi, mi)
78
        res = (res + ai * Mi * inv) % M
79

80
    return res
81

82

83
m=crt([(mp,p),(mq,q),(mr,r)])
84

85
mm = []
86
for ms in m.value:
87
    mm.append(long_to_bytes(ms))
88

89
flag = b''.join(mm)
90
print(flag.decode())

1
from Crypto.Util.number import bytes_to_long
2
from random import Random
3
from secret import flag
4

5
assert flag.startswith(b'XYCTF{') and flag.endswith(b'}')
6
flag = flag[6:-1]
7

8
msg = bytes_to_long(flag)
9
rand = Random()
10
test = bytes([i for i in range(255, -1, -1)])
11
open('output.py', 'w').write(f'enc = {msg ^ rand.getrandbits(msg.bit_length())}\nr = {[rand.choice(test) for _ in range(2496)]}')