1
import math
2

3
def continued_fractions(n, d):
4
    while d:
5
        q = n // d
6
        yield q
7
        n, d = d, n % d
8

9
def convergents(cf):
10
    n0, n1 = 0, 1
11
    d0, d1 = 1, 0
12
    for q in cf:
13
        n_next = q * n1 + n0
14
        d_next = q * d1 + d0
15
        yield n_next, d_next
16
        n0, n1 = n1, n_next
17
        d0, d1 = d1, d_next
18

19
def solve_quadratic_int(a, b, c):
20
    # Roots of ax^2 + bx + c = 0
21
    # Delta = b^2 - 4ac
22
    delta = b*b - 4*a*c
23
    if delta < 0: return None
24

25
    # Integer square root
26
    isqrt_delta = math.isqrt(delta)
27

28
    if isqrt_delta * isqrt_delta != delta:
29
        return None
30

31
    # Roots
32
    x1 = (-b + isqrt_delta) // (2*a)
33
    x2 = (-b - isqrt_delta) // (2*a)
34
    return x1, x2
35

36
n = 53935752499632394237566118604359892718551599347103770165725315381682199061231305149871806005165260280090479975164442744084144966392328763556404239396226819470535452063874887678501380410846947366731878954649755863213861355954458952288934844717604661623462592208245116654049598341395547558917480988549480710053
37
e = 24089812727939473377106986839231213000027354412422404767919546765423920656889461253619150192713429210805965327870135779746565500272194239190912741430085434073206746835643285459484069375458331543164741898206782337319633955007342267096062328568437378488906707151581554299081980005056634810284685406654001592981
38
c = 11841667115298930394046403591110886728843116188296120349135149714823163139880036389113944364018136771206785113712667463402504792394799117772574425782666242546383751254294439949528419287518978093348377437226381021286296812291097137179772817826065372736601838186625888784853135191493875564754914102135431686285
39

40
cf = continued_fractions(e, n)
41
conv = convergents(cf)
42

43
found_d = None
44
for k, d in conv:
45
    if k == 0: continue
46

47
    if (e * d - 1) % k == 0:
48
        phi = (e * d - 1) // k
49

50
        # Check roots
51
        # equation: x^2 - (n - phi + 1)x + n = 0
52
        b_val = -(n - phi + 1)
53
        roots = solve_quadratic_int(1, b_val, n)
54
        if roots:
55
            found_d = d
56
            break
57

58
if found_d:
59
    m = pow(c, found_d, n)
60
    try:
61
        print(m.to_bytes((m.bit_length() + 7) // 8, 'big'))
62
    except:
63
        print(m)
64
else:
65
    print("Failed")

1
from hashlib import md5
2
from itertools import product
3

4
SBOX = [
5
    [0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76],
6
    [0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0],
7
    [0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15],
8
    [0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75],
9
    [0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84],
10
    [0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF],
11
    [0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8],
12
    [0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2],
13
    [0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73],
14
    [0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB],
15
    [0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79],
16
    [0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08],
17
    [0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A],
18
    [0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E],
19
    [0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF],
20
    [0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16]
21
    ]
22

23
SBOX_inv = [
24
    [0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB],
25
    [0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB],
26
    [0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E],
27
    [0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25],
28
    [0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92],
29
    [0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84],
30
    [0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06],
31
    [0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B],
32
    [0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73],
33
    [0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E],
34
    [0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B],
35
    [0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4],
36
    [0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F],
37
    [0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF],
38
    [0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61],
39
    [0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D]
40
    ]
41

42
Rcon = [0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000, 0x1B000000, 0x36000000]
43

44
def SubBytes(State):
45
    for i in range(len(State)):
46
        row = State[i] >> 4
47
        col = State[i] & 0xF
48
        State[i] = SBOX[row][col]
49
    return State
50

51
def SubByte_inverse(State):
52
    for i in range(len(State)):
53
        row = State[i] >> 4
54
        col = State[i] & 0xF
55
        State[i] = SBOX_inv[row][col]
56
    return State
57

58
def ShiftRow(S):
59
    return [S[0],S[5],S[10],S[15],
60
            S[4],S[9],S[14],S[3],
61
            S[8],S[13],S[2],S[7],
62
            S[12],S[1],S[6],S[11]]
63

64
def ShiftRow_inverse(S):
65
    return [S[0],S[13],S[10],S[7],
66
            S[4],S[1],S[14],S[11],
67
            S[8],S[5],S[2],S[15],
68
            S[12],S[9],S[6],S[3]]
69

70
def GFmul(poly1,poly2):
71
    result = 0
72
    for index in range(poly2.bit_length()):
73
        if poly2 & 1 << index:
74
            result ^= (poly1 << index)
75
    return result
76

77
def mod(poly):
78
    MOD = 0b100011011
79
    while poly.bit_length() > 8:
80
        poly ^= MOD << (poly.bit_length() - 9)
81
    return poly
82

83
def MixColumns(State):
84
    T = [[0x2, 0x3, 0x1, 0x1],
85
        [0x1, 0x2, 0x3, 0x1],
86
        [0x1, 0x1, 0x2, 0x3],
87
        [0x3, 0x1, 0x1, 0x2]]
88

89
    M = [0 for _ in range(16)]
90
    for row in range(4):
91
        for col in range(4):
92
            for Round in range(4):
93
                M[row + col*4] ^= GFmul(T[row][Round],State[Round + col*4])
94
            M[row + col*4] = mod(M[row + col*4])
95
    return M
96

97
def MixColumns_inverse(State):
98
    T = [[0xe, 0xb, 0xd, 0x9],
99
        [0x9, 0xe, 0xb, 0xd],
100
        [0xd, 0x9, 0xe, 0xb],
101
        [0xb, 0xd, 0x9, 0xe]]
102

103
    M = [0 for _ in range(16)]
104
    for row in range(4):
105
        for col in range(4):
106
            for Round in range(4):
107
                M[row + col*4] ^= GFmul(T[row][Round],State[Round + col*4])
108
            M[row + col*4] = mod(M[row + col*4])
109
    return M
110

111
def RotWord(_4byte_block):
112
    res = ((_4byte_block & 0xFFFFFF) << 8) + (_4byte_block >> 24)
113
    return res
114

115
def SubWord(_4byte_block):
116
    res = 0
117
    for position in range(4):
118
        i = _4byte_block >> position * 8 + 4 & 0xF
119
        j = _4byte_block >> position * 8 & 0xF
120
        res ^= SBOX[i][j] << position * 8
121
    return res
122

123
def generateKey(key:bytes):
124
    key = int.from_bytes(key)
125
    w = [key >> 96,
126
        key >> 64 & 0xFFFFFFFF,
127
        key >> 32 & 0xFFFFFFFF,
128
        key & 0xFFFFFFFF]
129
    w = w + [0] * 40
130
    for i in range(4,44):
131
        tmp = w[i-1]
132
        if i % 4 == 0:
133
            tmp = SubWord(RotWord(tmp)) ^ Rcon[i // 4 - 1]
134
        w[i] = w[i-4] ^ tmp
135
    newkey = [sum([w[4*i]<<96,w[4*i+1]<<64,w[4*i+2]<<32,w[4*i+3]]).to_bytes(16,byteorder = 'big') for i in range(11)]
136
    return newkey
137

138
def _16bytes_xor(_16bytes_1,_16bytes_2):
139
    len1 = len(_16bytes_1)
140
    if len1 != 16:
141
        _16bytes_1 = b"\x00"*(16 - len1) + _16bytes_1
142
    len2 = len(_16bytes_2)
143
    if len2 != 16:
144
        _16bytes_2 = b"\x00"*(16 - len2) + _16bytes_2
145
    return [_16bytes_1[i] ^ _16bytes_2[i] for i in range(16)]
146

147
def AddRoundKey(State,Roundkeys,index):
148
    return _16bytes_xor(State,Roundkeys[index])
149

150
def EncryptBlock(block: bytes, key: bytes):
151
    State = list(block)
152
    Roundkeys = generateKey(key)
153
    State = AddRoundKey(State,Roundkeys,0)
154
    for round in range(1,10):
155
        State = SubBytes(State)
156
        State = ShiftRow(State)
157
        State = MixColumns(State)
158
        State = AddRoundKey(State,Roundkeys,round)
159
    State = SubBytes(State)
160
    State = ShiftRow(State)
161
    State = AddRoundKey(State,Roundkeys,10)
162
    return bytes(State)
163

164
def DecryptBlock(block: bytes, key: bytes):
165
    State = list(block)
166
    Roundkeys = generateKey(key)
167
    State = AddRoundKey(State,Roundkeys,10)
168
    for round in range(1,10):
169
        State = ShiftRow_inverse(State)
170
        State = SubByte_inverse(State)
171
        State = AddRoundKey(State,Roundkeys,10-round)
172
        State = MixColumns_inverse(State)
173
    State = ShiftRow_inverse(State)
174
    State = SubByte_inverse(State)
175
    State = AddRoundKey(State,Roundkeys,0)
176
    return bytes(State)
177

178
def unpad(message:bytes):
179
    pad_len = message[-1]
180
    if pad_len < 1 or pad_len > 16:
181
        raise ValueError("Invalid padding")
182
    if message[-pad_len:] != bytes([pad_len] * pad_len):
183
        raise ValueError("Invalid padding")
184
    return message[:-pad_len]
185

186
def FullDecrypt(ciphertext, key):
187
    blocks = [ciphertext[i*16:(i+1)*16] for i in range(len(ciphertext) // 16)]
188
    plaintext = b""
189
    for block in blocks:
190
        plaintext += DecryptBlock(block, key)
191
    return unpad(plaintext)
192

193
unique_ints = sorted(list(set(b"Block_Encrypt")))
194
plaintext = b"Block_Encryption"
195
ciphertext = b'\xbd\xbe\xbe\xa6\xd2\x97\xd8\x95P\x08\x9a\xcac\xc0U\x13'
196
enc_flag = b'H,\xac\xa0\xf2Y2\xb6\xe1d#\x99o`\xfcO@\x06\xf4jm\x15\x84\x0b\xd5s1\xdf\xc1$\x04U<h\xe78\xd5u\x96\xc1\xf4\xe9"X\xd0@\x01\x92'
197

198
# 1. Build table: E(P, k1) -> a
199
forward_map = {}
200
for p in product(unique_ints, repeat=4):
201
    a = bytes(p)
202
    k1 = md5(a).digest()
203
    mid = EncryptBlock(plaintext, k1)
204
    forward_map[mid] = a
205

206
# 2. Check
207
found_a = None
208
found_b = None
209

210
for p in product(unique_ints, repeat=4):
211
    b_cand = bytes(p)
212
    k2 = md5(b_cand).digest()
213
    dec_mid = DecryptBlock(ciphertext, k2)
214
    if dec_mid in forward_map:
215
        found_a = forward_map[dec_mid]
216
        found_b = b_cand
217
        print(f"Found! a={found_a}, b={found_b}")
218
        break
219

220
if found_a and found_b:
221
    final_key = md5(found_a + found_b).digest()
222
    try:
223
        flag = FullDecrypt(enc_flag, final_key)
224
        print(f"Flag: {flag}")
225
    except Exception as e:
226
        print(f"Decryption failed: {e}")
227
else:
228
    print("Not found.")