蜀道山高校公益联赛

发表于 更新于

闲着无聊随便出了几道题玩玩()

CRYPTO

Something like coppersmith

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import hashlib
from secret import flag

p = 6302810904265501037924401786295397288170843149817176985522767895582968290551414928308932200691953758726228011793524154509586354502691822110981490737900239
g = 37
x = getRandomRange(1, p)
key = hashlib.md5(str(x).encode()).digest()
aes = AES.new(key=key, mode=AES.MODE_ECB)
print(f"y = {pow(g, x, p)}")
print(f"xl = {x & (2**404 - 1)}")
print(f"enc = {aes.encrypt(pad(flag, 16))}")
"""
y = 1293150376161556844462084321627758417728307246932113125521569554783424543983527961886280946944216834324374477189528743754550041489359187752209421536046860
xl = 17986330879434951085449288256517884655391850545705434564933459034981508996937405053663301303792832616366656593647019909376   
enc = b'\x08[\x94\xc1\xc2\xc3\xb9"C^\xd6P\xf9\x0c\xbb\r\r\xaf&\x94\x8cm\x02s\x87\x8b\x1c\xb3\x92\x81H\xe7\xc6\x190a\xca\x91j\xc0@(\xc5Fw\x95\r\xee'
"""

比赛前看的时候p的阶的分解在http://factordb.com/ 都是不完全的，结果后面一看全给分解完了(不知道是不是谁花钱去分解了)

预期是pohlig_hellman+bsgs，但是都有分解了就可以pohlig_hellman之后爆破就好了难度也大大降低了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
from Crypto.Util.number import *
import gmpy2
import functools
from Crypto.Cipher import AES
from tqdm import trange
import hashlib

def CRT(mi, ai):
    assert functools.reduce(gmpy2.gcd, mi) == 1
    assert isinstance(mi, list) and isinstance(ai, list)
    M = functools.reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M // m) * gmpy2.invert(M // m, m) for (m, a) in zip(mi, ai)]
    return functools.reduce(lambda x, y: x + y, ai_ti_Mi) % M


def babystep_giantstep(g, y, p, q=None):
    if q is None:
        q = p - 1
    m = int(q**0.5 + 0.5)
    table = {}
    gr = 1
    for r in range(m):
        table[gr] = r
        gr = (gr * g) % p
    try:
        gm = pow(g, -m, p)
    except:
        return None
    ygqm = y
    for q in range(m):
        if ygqm in table:
            return q * m + table[ygqm]
        ygqm = (ygqm * gm) % p
    return None


def pohlig_hellman_DLP(g, y, p, fac):
    crt_moduli = []
    crt_remain = []
    for q in fac:
        x = babystep_giantstep(pow(g, (p - 1) // q, p), pow(y, (p - 1) // q, p), p, q)
        if (x is None) or (x <= 1):
            continue
        crt_moduli.append(q)
        crt_remain.append(x)
    x = CRT(crt_moduli, crt_remain)
    return x


p = 6302810904265501037924401786295397288170843149817176985522767895582968290551414928308932200691953758726228011793524154509586354502691822110981490737900239
fac = [2, 385057, 727646221919]
f = 385057 * 727646221919
g = 37
y = 1293150376161556844462084321627758417728307246932113125521569554783424543983527961886280946944216834324374477189528743754550041489359187752209421536046860
xl = 17986330879434951085449288256517884655391850545705434564933459034981508996937405053663301303792832616366656593647019909376
enc = b'\x08[\x94\xc1\xc2\xc3\xb9"C^\xd6P\xf9\x0c\xbb\r\r\xaf&\x94\x8cm\x02s\x87\x8b\x1c\xb3\x92\x81H\xe7\xc6\x190a\xca\x91j\xc0@(\xc5Fw\x95\r\xee'
t = y * inverse(pow(g, xl, p), p) % p
d = inverse(2**404, (p - 1) // 2)
td = pow(t, d, p)
xs = pohlig_hellman_DLP(g, td, p, fac)
tdx = td * inverse(pow(g, xs, p), p) % p
dic = {}
for k1 in trange(3, 2**24):
    if gmpy2.gcd(k1, p-1) == 1:
        dic[int(gmpy2.powmod(tdx, gmpy2.invert(k1, p - 1), p))] = k1
    else:
        dic[int(gmpy2.powmod(tdx, gmpy2.invert(k1, (p - 1) // gmpy2.gcd(k1, p-1)), p))] = k1
for k2 in trange(2**25):
    aa = int(gmpy2.powmod(g, k2 * f, p))
    if aa in dic:
        k1 = dic[aa]
        print(k1, k2)
        break
xh = xs + k1 * k2 * f
x = xh * 2**404 + xl
key = hashlib.md5(str(x).encode()).digest()
aes = AES.new(key=key, mode=AES.MODE_ECB)
print(aes.decrypt(enc))
# LZSDS{m@N_Wh@t_c@n_I_5@y_____dfa015cdc546}

prng_lfsr

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import os
from Crypto.Util.number import *
import hashlib
from secret import flag

assert hashlib.sha256(flag).hexdigest() == "1b6208006b19ceddc493a8fe1342c1c7bba1800b2a66b9da4cd819f8440f331f"
assert len(flag) == 40


class LFSR:
    def __init__(self, n, key, mask):
        self.state = key
        self.mask = mask
        self.n = n
        self.state = [int(b) for b in bin(self.state)[2:].zfill(n)]
        self.mask_bits = [int(b) for b in bin(self.mask)[2:].zfill(n)]

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

    def __call__(self):
        self.update()
        b = self.state[-1]
        return b


class LCG:
    def __init__(self, seed):
        self.seed = seed
        self.a = 47026247687942121848144207491837523525
        self.b = 117397592171526113268558934119004209487
        self.m = 2**128

    def next(self):
        self.seed = (self.seed * self.a + self.b) % self.m
        return (self.seed >> 64) ^ (self.seed % 2**64)


def f(alist, seed):
    R = LCG(seed)
    l = len(alist)
    res = 0
    for _ in range(30):
        index = R.next() % l
        res ^= alist[index]
        res &= alist[(index + 1) % l]
        res |= alist[(index - 1) % l]
    return res


def pad(m):
    return m * 25 + os.urandom(2000 - len(m) * 25)


XOR = lambda s1, s2: bytes([x1 ^ x2 for x1, x2 in zip(s1, s2)])


seed = getRandomRange(1, 2**128)
R = LCG(seed)
bit = 64
t = 8
mask = [R.next() for _ in range(t)]
seed = [getRandomNBitInteger(bit) for _ in range(t)]
lfsr = [LFSR(bit, seed[i], mask[i]) for i in range(t)]
output = 0
for i in range(2000 * 8):
    output <<= 1
    output += f([lfsr[i]() for i in range(t)], seed)
flag = pad(flag)
print(f"mask = {mask[-4:]}")
print(f"enc = {XOR(flag, long_to_bytes(output))}")
print(f"hint = {flag[-100:]}")
"""
mask = [14220691401612821285, 6144765487634854340, 15963296602901011718, 11570958398098493701]
enc = b'\xfa\xb2G\xb0\xccYU\x16\t\xbe)\xdc\x19\x1f\x16x\x98D\xdf+\x95\x0b\xeeL\xca\x07[\x1fM\x04T\xd3V\x11\x19\xe3\x8a\x8f\\\xfflda\x7f/B\xae\x85E!\xc4\x17M\xd7\xd3\x9e\xbc\xb2\xfc\x97\xe1W\x83\xdd\xdcR\xcfh\xd0\xd4D\xc5\x949M\xa1\xff\xe1\x9fd\x89\xa85\xff\x85{;:\x9e\x91G\x11o\xc4%\xe9\xb2\x1e\x8e\x9as\xbb<\xbb8z\xae\x15\xac\xea"x:\x81\xe7\xda\xd1\x8fv\xd7\x92\x85\x953AH\xd7CAkBU-\x97\xce\xe0\x11\xbe\xa7\xc6\x7f\x1d\xedgL\xc7B\xfa\x82P\xf1\xeb\xd6#B\xdd\xce=\xae\xaf\x92}A\xed\x99\xec\xa3k\xff|r\xec9d\xa3\x17\x92\xd2\r[o*\x8e\x95\x1b\xecj\xf8\xb2WF\x01\x05ia^\x7f\xa1n\xab\x12\x84\xddo\xd5\x82\xdeJ\xde\xaeX\x83\xd4\xaa\xc3\xbb:\x92\xce\x15\x85f\x06F\xc5\x04\x0c>\xa7\xca^\xf0\x01\x1dG\x12\xbc|\xa5_\x8c\xa3\xb6\x8dj$\xd1\xbet\x8c\x05\x0f\xcc\x01\xf4\n\xeb\xcdb(+\xcf\xc8\x99\x9b\xd0\x0c1\x9c\xa0s\xf3\x93/\xabU{;jbC\xd4\xfa\x92\x83\xcd\x8cb8\xb4\x80\xed\x0600~\x1f\xa8\x1a8\xc42\xd4\xdb\x07+\xa1M\xf6 E\xb1+\xa2R\x81\x91\xd8\xb4\x15&\xbc\xa0\xbd\x87<\xb5\x8d\x9f\x9e\xb1\xb6\xea\xf2\x99w|C^\xa3\xc36BZ\xe1\xe6R|\x18\x9f\xcd\xc3`\x86\n\x13^\x95\x82\xc0P\x11l\x0fY\xd3\x9a\xcc\xef\xd9\x8d]\xa1"}\x89\xd1\x98\t\xc8\xa9/\x1f\xcb\xae\xe9\x936\xd8\x9d\x8d\xed\xb6\xe7d\xe4\xd2\x12\x84\x0cx\x15\xa0K\xc6\t\x1a\x10\xcc\x92\xf3\x95r\xe1\x89\xec\x0eE\x8f\xf9i\x1b\x0b\xa3\xc0I\x99\x81\x05[\x86\xba\xbd\xd9\x16^\x86\xd9\xbc\x86\xe1{\xcd6j\x93\x9d\xe2\xf2\x121<7x\xb1\xb6j\x8cG+\xf2\x0e6\x02Y\xe1\xc8\xa1\x14=Y\xaaUMJ\xec$\xda\xe4N\xd5\xe1i\x03\xe5\xd0w\xb9\xdf|A\xb0\xe4\xa9\xcao\x06[\xc1\x1e~\x1c\x9dx\x97\xbcVoD\xfd\x80\x1b\x96\x1e=\xb7\xf8)\xbe\xbaQ\xbb]\x17\x86\xd18\x18?\x0e\x03\x1f-\xf5\xe0\xe0\xa1\xfbBB$\x0f\xa6\x84O5\x962\xb0\xf1\xb8K\x0c\x83\x15p_\xde\xe6\x05\xb0\xff\x8f\xd2\x7f\xba\xea\x80V\xda\r2j\xd0G\x95?\x18G\xf6\xb5\xc05\xa6\xed\xcd%)\x0f!\xf2\x95\xd7L\x17PX\x07:\x8c\xbb_4\xc9\xef\rw\xda\xdf1\xa5\x805{\x0c\xe0s\x15\xc0/\x83?\xb48\xc1\x0c\xdaW\xddJ\x8d\x8e\x9f\xacx\x11\xf5H\x91\x8b\xec\xcc\xa7\xee\x81\xdf\xdfuBV\x98\xcd}\xcf\xa2\xe5\xf8\xac\xa3\xff\x1d\x90;\xe3\x1dQ\xe4\xaaI\xb0\x9f\xc4\x1d^\xca\x91\xdb\xaf\xfc\xa0\xaa\xc7\x8d\xaa\xe0\xd3\x98\x9c\xba\x9a\xc2\xfb\x96}\xf5\xf3F\xc1\x0e\x9d\xe9i@L\x82\x9c\x9a{\xf0\xe7\xc0yb\x1f,\x92\x81\xa0\x96\xe7\x16o`\x1fQ\xf5\x7f[\x18n\x83]\xdd\xb1Zl\t\xf3\x8f\xd3)J\xaaW\x87\xbf~\x0c\xddX\xad\x10\xfe}DW[\x15\x9a\x81Z\xf0\x9b#\xcd\xc5\xbb\x9c\xad\x86\xc5\xa9,\'-\x0c\xf5w\xd1\x93\xdc\xacKT\xa1\x85\xf6lF\x92l2PI\xdb\xcd\x16\x9a\x1f\xd4\x1d0\n\xb7\x14 \x95\xc7{\'B\xa0\xb8:\xb6\xbe\xc0\xf8\x8a\xe8<O\xaf\xc9FI\xfb\xfd\xf6\xf3v\xac\xea\xd6\xb4spk\xe1\xaa\xe3(\xaa\xd3q\xe5\xca\x9c\xc0R\xb8\xddk6P\xe71\xc2\x8dH\x9b\x0c\x85\xf6z\x1c\x88V\x88\xd2N}\x8a:\x1d/%j\x10\x82j\x141\x01\x9a\xbbr\xa1\x9c8\xb0\xea\xd5\xb67\xef\xc2\x171\xe8!p\x93\x05\x18\x9e\xb3\x07@\x1cY\x9f\xb9\x13\xf3~5\x9d\x10\xa2q\xf9\xf0)%\xbcZ8*\x86\xe4\x12D<\xd3c\x94s\xe4\xc1yr\x02\xc06a\xea\xc7\xc0\xc0\xa1\x8d\x05"] \x127X\xf5\x9bn~\xf6\x85\x93\xf1W\xbc\x94%\xc0\rt\xee6C\xa2\xd6\xf3\xcc\t\xc5\xe8\x8cV,\xb2A;\x9e\xd3\x9c\x1c\xc4\xffE\xec\x15\xb0E\xfb\x18\xab8;\xfa\x00\x84\xf5=\xf6\xd2\tu/\xc1\x8aW\xbb{\xdc\x98\x9e\xecS\xdcOPKq/\x9c\x86\x15h\x0b\x00\xea\x94\xe5\xb4\xe5ip4\x8e8{`\x81\xd9\xee\x19`9\xbf47\x1f\xb5\x05\xe6\xc7\xb9I\x1bM^\xd9\x83\x00\xb4\x0b3\\~\x04;\x1d\xf8\xe0}q\xf4\x94\xad/@b\xde@\xd0\xb7bR\xb84\x9a3\x0f\xba\x90\xd0\x8e\xa0\x022 \xca\xe2\x89\x07qE+#~\xfb<\x90O\x04\xbc\xdb\x7f\t<$\x87\xcf\xc8\xe5\xb7\\\x81\x07\xae\xc7\x84\xbb\xdbV\x17\xc5\xfb\x1a\xe0L\xe9A\xbcy\xc8\xc5\xf7\r>a\x9c\xbc\xad\x18,\xf8\x8ch\xf7\xd6\xb0\xc0\x1e\xbb}\xffr\xae\xcf\xae!\xc7\\\xc6\xd8\xbf\x81\xef\x04\xd9awf\xda\'vh\xeb\xd5\xac\x1c\xe5)PJ\x9f\x02\x1f\xba\x03\xc0\x073\xb8K\xe6A\xc8t\xabjA\xbd\xff\x9e\x81\xfa@\x86H\xa8\xb8\xf5\xbb\xc4\xb9\xe8\x9f \x14\xbcL\x08r\xca\xc8\xfe\xf6k\x18;\xdf\xd6)#\x02X&\x0e|\x03\x85H\xc4\x0c\x81G\x04P\x05h\xaeI*\xd0\x88&|\xf8\x02>\xe1I\x80cF z\xf0yL\x10%\xd1\xa7Wb\x064\xf8\x05[eBwp\x15\xa4c`\x8aL\xba\xb4\xd1\x9c\xce\xd4\xb8\xd0\x18\xf3?b^,\xed\xb8_\x8fp\xa07\xbb\xba \x08\x9c\xf1\xac\x03\xe8\xd5\x05\x83\xf1\xbb\x1c\xcd\x9aF\xc7\x10\xa8\xd9\xdf\x05\xee\xca<\xf4)\x82\xa7\xe8C9\x0c~6\x8e{\xf3\x80\x0c\xbe\x13 \xf6\xfa\x7f\xec\x08\x929\x92\xcd\xd4GT\xbde\xda\x9fSk\xf6\r\x00W\r}\x99(IG\xd5\x0c\xd0\xdcj{r|\x81\t\x9f\x8f\x1f\x0ee^\xcb*<\xbb\x993\x8f\x07\xc2\xa1`\xe2W>\x84c\x00\xa7a\xe2\xdb\xbd\xe2\xb7\x87/2ugj:[\xdd\xa8\x8c\xcc\xe5\xde\xbd\xe39UW\xcc\x9b\xc7\xbb\x88H\xdb N\xeb\xa8xo\x84)\xc2\xa0$\xfe\x90T\xb9rxNDT\x13\xb7\x97\x81^g\xbdU\x89\xfd\x89r\x03U\xf7\x07\xe2gd\x0e\xe5O\xb6,\xcf\xb5+\x00\xca\x93@\rK\xfe=\xca\xbb\x12\x83\x9a)\xfd\xda\xd1\xa95\x9eyw\xaa\xb8^`2wWF\xf3\x7f\xb0b\x83\xa4\'@%f\x8f\xa5J\x1frA\xfb\xb6p\xaf\xe1\x8d\xba\xb2\xff\x9a\xeb\x14%\x10\x89,\xc6\xa2>\xf9m\xb2T\xee\xb4\x98\x04\xde\xf3%o\xd7\x80P\x08\xc2\x00^a\xa3\xe4\xadZ\x90\xad\xc6\xb2\xbd\x04^\x13^\x82\x12\x14\x96\xce+0/\x92U\xfc\xf6A[\xdd\xc3\x8cr\xa8l\x1a\x95\x03Wm\xdeD!\\\xc9\x98\xd3\xea\x90\x8bR\xfe\xf2\x10+\xe1\x8f\xde\x18\xe1\xbb\x0bh\x1c\x0e\xdb\x1ea\xc6\\?\xd2\x8b\xc4c\x84\x7f\x9a_\xe2\xd2\xc84\xaej\x85\x10\x10\xc7d,8\x0b\x89^\x18\x8f\xd6G\xa1p\x83n\xb7^\x14\xcd\x18\x8b\xe6\x9d\x00s\xcb\x02\xc1\xee<\xa2F\xb4\xa99]+\x0b\x1a\xed\xdae\xe3\xd3\x82\x19\x02\x80k-\xc8\xa7\x9c\x9d\x92\xc8\xefr\'\xfds\x9a\xa5\xe8\xd4\tS\xb0\xa0\xbd*\xfc=\xf6\xd4e\xb3\x80\x8c\x0e\xb9_]\xd6\xc2d\xa6\x19\xd5\x90\x0b\x9e3\xb3\xf1\xee\xb0w\xce\xa3&\xd0\xae\xaa+C\x05\xb2 \xf5\xccf\x90\x1d\xb3$\xe5\xbc\x07\xe0\xb4\xc8\xb6~\x00\x9e\x84Z\xf9\xb7\xe1\xdaB=i\x9d\x19\xa4oJ,\xe7\xe4 \'#f\x91vB\xf8\xe2\x0e9\x84\xe7\xf1\xde\xd0+\xa2\x11\x96.\xfd\x8c\xba[jEAM<\x03\x12U\x84\xab{2\x81H\x066\x01\\\x96\x99\xfa\x19\xd0\xb2\xe5\xf9\xb6,+\x97)\xb7h\xd2@\xda\x89_\xd6S\x8f@%q\xb5$\xc7\x89\xb7\xe2\xf8\xb1\xa5\xc8|\x83\xce\xe7\x88\xb8\xb1\xdd\xa5J\xcar\xcd\x8f\xfe\t\x85\xd0\xb4FC#(\x85-\xf6fm5\xecUWE \xd4\x0b}\xc0\x9d\x1c\x14\x83\xfc^5\ng\x7f\x13\xfe{[\x8b\xbc?\xc2+\xfb\xa8O\x8b\xf6e\x91vG\xffd\xdf\x0c\x84Ig&\x1b\xbb\xcb\x84;\x94\x13\\\xcc\x178\xa1\xbd\x08.'
hint = b'\x93+\xc6\\$s\x16Sp\xf24\x91wPg<BS=\x9e\xe4\xce\xdb\xa3N\xe6\xe1/\x17\xfa`9\x8f\xe33\x92\x80\xa6@\xd6P\xb0\xdb\x8eJmD\xf1\x10Y^c4\xd0\x86N\x8an0\xf4\xe3\x8b\xbd\xdff\xb6%H\xd3\x85\xf3`\xbc\n\x02\xa21_\x82U\xa7\t,\xaf\x9e\x9cn\x88\x92\xadi\xab\x19@Wa\xe6\x1e\xf9\x9e'
"""

思路很简单，先通过恢复LCG的seed来得到nfsr的所有mask，然后通过攻击nfsr来恢复flag

这个LCG和普通的不一样的地方在于它是把高位和低位异或了之后才进行输出

但是如果我们爆破它的输出的低位的话，可以拿到它的中位，然后可以看成一个hnp问题来打

恢复出mask后我们考察nfsr的相关性其实发现和lfsr2相关性很高

那很简单了，我们只要恢复出lfsr2的seed(我是通过代数免疫度来攻击的，其实也可以别的)，然后其输出大概率和nfsr的相同，那我们直接用它的输出和密文异或，然后统计一下即可得到flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
from Crypto.Util.number import *
import hashlib
from tqdm import trange

masks = [14220691401612821285, 6144765487634854340, 15963296602901011718, 11570958398098493701]
enc = b'\xfa\xb2G\xb0\xccYU\x16\t\xbe)\xdc\x19\x1f\x16x\x98D\xdf+\x95\x0b\xeeL\xca\x07[\x1fM\x04T\xd3V\x11\x19\xe3\x8a\x8f\\\xfflda\x7f/B\xae\x85E!\xc4\x17M\xd7\xd3\x9e\xbc\xb2\xfc\x97\xe1W\x83\xdd\xdcR\xcfh\xd0\xd4D\xc5\x949M\xa1\xff\xe1\x9fd\x89\xa85\xff\x85{;:\x9e\x91G\x11o\xc4%\xe9\xb2\x1e\x8e\x9as\xbb<\xbb8z\xae\x15\xac\xea"x:\x81\xe7\xda\xd1\x8fv\xd7\x92\x85\x953AH\xd7CAkBU-\x97\xce\xe0\x11\xbe\xa7\xc6\x7f\x1d\xedgL\xc7B\xfa\x82P\xf1\xeb\xd6#B\xdd\xce=\xae\xaf\x92}A\xed\x99\xec\xa3k\xff|r\xec9d\xa3\x17\x92\xd2\r[o*\x8e\x95\x1b\xecj\xf8\xb2WF\x01\x05ia^\x7f\xa1n\xab\x12\x84\xddo\xd5\x82\xdeJ\xde\xaeX\x83\xd4\xaa\xc3\xbb:\x92\xce\x15\x85f\x06F\xc5\x04\x0c>\xa7\xca^\xf0\x01\x1dG\x12\xbc|\xa5_\x8c\xa3\xb6\x8dj$\xd1\xbet\x8c\x05\x0f\xcc\x01\xf4\n\xeb\xcdb(+\xcf\xc8\x99\x9b\xd0\x0c1\x9c\xa0s\xf3\x93/\xabU{;jbC\xd4\xfa\x92\x83\xcd\x8cb8\xb4\x80\xed\x0600~\x1f\xa8\x1a8\xc42\xd4\xdb\x07+\xa1M\xf6 E\xb1+\xa2R\x81\x91\xd8\xb4\x15&\xbc\xa0\xbd\x87<\xb5\x8d\x9f\x9e\xb1\xb6\xea\xf2\x99w|C^\xa3\xc36BZ\xe1\xe6R|\x18\x9f\xcd\xc3`\x86\n\x13^\x95\x82\xc0P\x11l\x0fY\xd3\x9a\xcc\xef\xd9\x8d]\xa1"}\x89\xd1\x98\t\xc8\xa9/\x1f\xcb\xae\xe9\x936\xd8\x9d\x8d\xed\xb6\xe7d\xe4\xd2\x12\x84\x0cx\x15\xa0K\xc6\t\x1a\x10\xcc\x92\xf3\x95r\xe1\x89\xec\x0eE\x8f\xf9i\x1b\x0b\xa3\xc0I\x99\x81\x05[\x86\xba\xbd\xd9\x16^\x86\xd9\xbc\x86\xe1{\xcd6j\x93\x9d\xe2\xf2\x121<7x\xb1\xb6j\x8cG+\xf2\x0e6\x02Y\xe1\xc8\xa1\x14=Y\xaaUMJ\xec$\xda\xe4N\xd5\xe1i\x03\xe5\xd0w\xb9\xdf|A\xb0\xe4\xa9\xcao\x06[\xc1\x1e~\x1c\x9dx\x97\xbcVoD\xfd\x80\x1b\x96\x1e=\xb7\xf8)\xbe\xbaQ\xbb]\x17\x86\xd18\x18?\x0e\x03\x1f-\xf5\xe0\xe0\xa1\xfbBB$\x0f\xa6\x84O5\x962\xb0\xf1\xb8K\x0c\x83\x15p_\xde\xe6\x05\xb0\xff\x8f\xd2\x7f\xba\xea\x80V\xda\r2j\xd0G\x95?\x18G\xf6\xb5\xc05\xa6\xed\xcd%)\x0f!\xf2\x95\xd7L\x17PX\x07:\x8c\xbb_4\xc9\xef\rw\xda\xdf1\xa5\x805{\x0c\xe0s\x15\xc0/\x83?\xb48\xc1\x0c\xdaW\xddJ\x8d\x8e\x9f\xacx\x11\xf5H\x91\x8b\xec\xcc\xa7\xee\x81\xdf\xdfuBV\x98\xcd}\xcf\xa2\xe5\xf8\xac\xa3\xff\x1d\x90;\xe3\x1dQ\xe4\xaaI\xb0\x9f\xc4\x1d^\xca\x91\xdb\xaf\xfc\xa0\xaa\xc7\x8d\xaa\xe0\xd3\x98\x9c\xba\x9a\xc2\xfb\x96}\xf5\xf3F\xc1\x0e\x9d\xe9i@L\x82\x9c\x9a{\xf0\xe7\xc0yb\x1f,\x92\x81\xa0\x96\xe7\x16o`\x1fQ\xf5\x7f[\x18n\x83]\xdd\xb1Zl\t\xf3\x8f\xd3)J\xaaW\x87\xbf~\x0c\xddX\xad\x10\xfe}DW[\x15\x9a\x81Z\xf0\x9b#\xcd\xc5\xbb\x9c\xad\x86\xc5\xa9,\'-\x0c\xf5w\xd1\x93\xdc\xacKT\xa1\x85\xf6lF\x92l2PI\xdb\xcd\x16\x9a\x1f\xd4\x1d0\n\xb7\x14 \x95\xc7{\'B\xa0\xb8:\xb6\xbe\xc0\xf8\x8a\xe8<O\xaf\xc9FI\xfb\xfd\xf6\xf3v\xac\xea\xd6\xb4spk\xe1\xaa\xe3(\xaa\xd3q\xe5\xca\x9c\xc0R\xb8\xddk6P\xe71\xc2\x8dH\x9b\x0c\x85\xf6z\x1c\x88V\x88\xd2N}\x8a:\x1d/%j\x10\x82j\x141\x01\x9a\xbbr\xa1\x9c8\xb0\xea\xd5\xb67\xef\xc2\x171\xe8!p\x93\x05\x18\x9e\xb3\x07@\x1cY\x9f\xb9\x13\xf3~5\x9d\x10\xa2q\xf9\xf0)%\xbcZ8*\x86\xe4\x12D<\xd3c\x94s\xe4\xc1yr\x02\xc06a\xea\xc7\xc0\xc0\xa1\x8d\x05"] \x127X\xf5\x9bn~\xf6\x85\x93\xf1W\xbc\x94%\xc0\rt\xee6C\xa2\xd6\xf3\xcc\t\xc5\xe8\x8cV,\xb2A;\x9e\xd3\x9c\x1c\xc4\xffE\xec\x15\xb0E\xfb\x18\xab8;\xfa\x00\x84\xf5=\xf6\xd2\tu/\xc1\x8aW\xbb{\xdc\x98\x9e\xecS\xdcOPKq/\x9c\x86\x15h\x0b\x00\xea\x94\xe5\xb4\xe5ip4\x8e8{`\x81\xd9\xee\x19`9\xbf47\x1f\xb5\x05\xe6\xc7\xb9I\x1bM^\xd9\x83\x00\xb4\x0b3\\~\x04;\x1d\xf8\xe0}q\xf4\x94\xad/@b\xde@\xd0\xb7bR\xb84\x9a3\x0f\xba\x90\xd0\x8e\xa0\x022 \xca\xe2\x89\x07qE+#~\xfb<\x90O\x04\xbc\xdb\x7f\t<$\x87\xcf\xc8\xe5\xb7\\\x81\x07\xae\xc7\x84\xbb\xdbV\x17\xc5\xfb\x1a\xe0L\xe9A\xbcy\xc8\xc5\xf7\r>a\x9c\xbc\xad\x18,\xf8\x8ch\xf7\xd6\xb0\xc0\x1e\xbb}\xffr\xae\xcf\xae!\xc7\\\xc6\xd8\xbf\x81\xef\x04\xd9awf\xda\'vh\xeb\xd5\xac\x1c\xe5)PJ\x9f\x02\x1f\xba\x03\xc0\x073\xb8K\xe6A\xc8t\xabjA\xbd\xff\x9e\x81\xfa@\x86H\xa8\xb8\xf5\xbb\xc4\xb9\xe8\x9f \x14\xbcL\x08r\xca\xc8\xfe\xf6k\x18;\xdf\xd6)#\x02X&\x0e|\x03\x85H\xc4\x0c\x81G\x04P\x05h\xaeI*\xd0\x88&|\xf8\x02>\xe1I\x80cF z\xf0yL\x10%\xd1\xa7Wb\x064\xf8\x05[eBwp\x15\xa4c`\x8aL\xba\xb4\xd1\x9c\xce\xd4\xb8\xd0\x18\xf3?b^,\xed\xb8_\x8fp\xa07\xbb\xba \x08\x9c\xf1\xac\x03\xe8\xd5\x05\x83\xf1\xbb\x1c\xcd\x9aF\xc7\x10\xa8\xd9\xdf\x05\xee\xca<\xf4)\x82\xa7\xe8C9\x0c~6\x8e{\xf3\x80\x0c\xbe\x13 \xf6\xfa\x7f\xec\x08\x929\x92\xcd\xd4GT\xbde\xda\x9fSk\xf6\r\x00W\r}\x99(IG\xd5\x0c\xd0\xdcj{r|\x81\t\x9f\x8f\x1f\x0ee^\xcb*<\xbb\x993\x8f\x07\xc2\xa1`\xe2W>\x84c\x00\xa7a\xe2\xdb\xbd\xe2\xb7\x87/2ugj:[\xdd\xa8\x8c\xcc\xe5\xde\xbd\xe39UW\xcc\x9b\xc7\xbb\x88H\xdb N\xeb\xa8xo\x84)\xc2\xa0$\xfe\x90T\xb9rxNDT\x13\xb7\x97\x81^g\xbdU\x89\xfd\x89r\x03U\xf7\x07\xe2gd\x0e\xe5O\xb6,\xcf\xb5+\x00\xca\x93@\rK\xfe=\xca\xbb\x12\x83\x9a)\xfd\xda\xd1\xa95\x9eyw\xaa\xb8^`2wWF\xf3\x7f\xb0b\x83\xa4\'@%f\x8f\xa5J\x1frA\xfb\xb6p\xaf\xe1\x8d\xba\xb2\xff\x9a\xeb\x14%\x10\x89,\xc6\xa2>\xf9m\xb2T\xee\xb4\x98\x04\xde\xf3%o\xd7\x80P\x08\xc2\x00^a\xa3\xe4\xadZ\x90\xad\xc6\xb2\xbd\x04^\x13^\x82\x12\x14\x96\xce+0/\x92U\xfc\xf6A[\xdd\xc3\x8cr\xa8l\x1a\x95\x03Wm\xdeD!\\\xc9\x98\xd3\xea\x90\x8bR\xfe\xf2\x10+\xe1\x8f\xde\x18\xe1\xbb\x0bh\x1c\x0e\xdb\x1ea\xc6\\?\xd2\x8b\xc4c\x84\x7f\x9a_\xe2\xd2\xc84\xaej\x85\x10\x10\xc7d,8\x0b\x89^\x18\x8f\xd6G\xa1p\x83n\xb7^\x14\xcd\x18\x8b\xe6\x9d\x00s\xcb\x02\xc1\xee<\xa2F\xb4\xa99]+\x0b\x1a\xed\xdae\xe3\xd3\x82\x19\x02\x80k-\xc8\xa7\x9c\x9d\x92\xc8\xefr\'\xfds\x9a\xa5\xe8\xd4\tS\xb0\xa0\xbd*\xfc=\xf6\xd4e\xb3\x80\x8c\x0e\xb9_]\xd6\xc2d\xa6\x19\xd5\x90\x0b\x9e3\xb3\xf1\xee\xb0w\xce\xa3&\xd0\xae\xaa+C\x05\xb2 \xf5\xccf\x90\x1d\xb3$\xe5\xbc\x07\xe0\xb4\xc8\xb6~\x00\x9e\x84Z\xf9\xb7\xe1\xdaB=i\x9d\x19\xa4oJ,\xe7\xe4 \'#f\x91vB\xf8\xe2\x0e9\x84\xe7\xf1\xde\xd0+\xa2\x11\x96.\xfd\x8c\xba[jEAM<\x03\x12U\x84\xab{2\x81H\x066\x01\\\x96\x99\xfa\x19\xd0\xb2\xe5\xf9\xb6,+\x97)\xb7h\xd2@\xda\x89_\xd6S\x8f@%q\xb5$\xc7\x89\xb7\xe2\xf8\xb1\xa5\xc8|\x83\xce\xe7\x88\xb8\xb1\xdd\xa5J\xcar\xcd\x8f\xfe\t\x85\xd0\xb4FC#(\x85-\xf6fm5\xecUWE \xd4\x0b}\xc0\x9d\x1c\x14\x83\xfc^5\ng\x7f\x13\xfe{[\x8b\xbc?\xc2+\xfb\xa8O\x8b\xf6e\x91vG\xffd\xdf\x0c\x84Ig&\x1b\xbb\xcb\x84;\x94\x13\\\xcc\x178\xa1\xbd\x08.'
hint = b'\x93+\xc6\\$s\x16Sp\xf24\x91wPg<BS=\x9e\xe4\xce\xdb\xa3N\xe6\xe1/\x17\xfa`9\x8f\xe33\x92\x80\xa6@\xd6P\xb0\xdb\x8eJmD\xf1\x10Y^c4\xd0\x86N\x8an0\xf4\xe3\x8b\xbd\xdff\xb6%H\xd3\x85\xf3`\xbc\n\x02\xa21_\x82U\xa7\t,\xaf\x9e\x9cn\x88\x92\xadi\xab\x19@Wa\xe6\x1e\xf9\x9e'

X = masks
a = 47026247687942121848144207491837523525
b = 117397592171526113268558934119004209487
mod = 2 ** 128
l = 17

n = len(X)
AA = [a]
BB = [b]
for i in range(n):
    AA.append(a * AA[-1])
for i in range(n):
    BB.append(a * BB[-1] + b)


for w in trange(2**l):
    R.<Th0,Th1,Th2,Th3,Tl0,Tl1,Tl2,Tl3>=Zmod(mod)[]

    Tl = [w]
    Tm = [w ^^ X[0] & (2**l - 1)]
    for i in range(len(X) - 1):
        k = (a ** (i + 1) * w + b * (a ** (i + 1) - 1) // (a - 1)) & (2**l - 1)
        Tl.append(k)
        Tm.append(k ^^ X[i + 1] & (2**l - 1))
    n = len(Tm)
    A = [a]
    B = [b]
    for i in range(n):
        A.append(a * A[-1])
    for i in range(n):
        B.append(a * B[-1] + b)

    ff = []
    for i in range(n-1):
        ff.append((2**(64+l)*Th0+2**64*Tm[0]+2**l*Tl0+Tl[0])*A[i+1]-B[0]*A[i+1]-(2**(64+l)*eval(f'Th{i+1}')+2**64*Tm[i+1]+2**l*eval(f'Tl{i+1}')+Tl[i+1])*A[0]+B[i+1]*A[0])

    T = 2**(64-l)

    deg_h = sum(ff).degree()
    polys = ff

    M, v = Sequence(polys).coefficient_matrix()
    M = M.T.dense_matrix()
    R, C = M.dimensions()
    B = block_matrix(
        ZZ, [[matrix.identity(C)*mod, matrix.zero(C, R)], [M, matrix.identity(R)]]
    )
    vT = (v.T).list()

    B[:,:C] *= mod
    for jj in range(len(vT)):
        B[:,C+jj:C+jj+1] *= T^(deg_h-vT[jj].degree())

    res = B.BKZ()
    for tt in res:
        trunc = []
        if(abs(tt[-1]) == T^deg_h):
            f=[abs(tt[-i-2])//T^(deg_h-1) for i in range(n)][::-1]
            ml = [2**l*f[i]+Tl[i] for i in range(len(f))]
            break
    mh = [ml[i]^^X[i] for i in range(len(ml))]

    m = [ml[i]+2**64*mh[i] for i in range(len(ml))]
    seed=m[0]
    if (a*seed+b)%mod ==m[1]:
        print(seed)
        # 92831300514842470778050206073212376504
        break

for i in range(5):
    seed = (seed - b)*inverse(a,mod)%mod

print(seed)
# 262310659054038114087383397436792734657
class LCG:
    def __init__(self, seed):
        self.seed = seed
        self.a = 47026247687942121848144207491837523525
        self.b = 117397592171526113268558934119004209487
        self.m = 2**128

    def next(self):
        self.seed = (self.seed * self.a + self.b) % self.m
        return (self.seed >> 64) ^^ (self.seed % 2**64)

R = LCG(seed)
masks = [R.next() for _ in range(8)]

XOR = lambda s1, s2: bytes([x1 ^^ x2 for x1, x2 in zip(s1, s2)])

class LFSRSymbolic:
    def __init__(self, n, key, mask):
        self.state = key
        self.mask = mask
        self.n = n
        self.mask_bits = [int(b) for b in bin(self.mask)[2:].zfill(n)]

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

    def __call__(self):
        self.update()
        b = self.state[-1]
        return b

def ff(alist):
    R = LCG(seed)
    l = len(alist)
    res = 0
    for _ in range(30):
        index = R.next() % l
        res ^^= alist[index]
        res &= alist[(index + 1) % l]
        res |= alist[(index - 1) % l]
    return res

out = XOR(enc[-100:], hint)
out = bytes_to_long(out)
from itertools import product
from sage.crypto.boolean_function import *

table = []
for x7, x6, x5, x4, x3, x2, x1, x0 in product([0, 1], repeat=8):
    x = [x0, x1, x2, x3, x4, x5, x6, x7]
    table.append(ff(x))
f = BooleanFunction(table)
fp = f.algebraic_normal_form()
_, g = f.algebraic_immunity(annihilator=True)
print(g)
bin_out = bin(out)[2:]
mask=masks[1]
br64 = BooleanPolynomialRing(64, [f"x{i}" for i in range(64)])
key_sym = list(br64.gens())
lfsr3 = LFSRSymbolic(64, key_sym, mask)
from tqdm import trange
x3=[]
for i in trange(2000*8):
    x3.append(lfsr3())
x3=x3[-800:]

eqs=[]
for i, bit in enumerate(bin_out):
    if bit=='0':
        eqs.append(x3[i])
m = []
B = []
for i in eqs:
    s = []
    for x in range(len(key_sym)):
        if key_sym[x] in i:
            s.append(1)
        else:
            s.append(0)
    if "+ 1" in str(i):
        B.append(1)
    else:
        B.append(0)
    m.append(s)
m = matrix(GF(2), m)
B = vector(GF(2), B)
seed3=m.right_kernel()[2]
seed3=int(''.join(map(str, seed3)),2)

class LFSR:
    def __init__(self, n, key, mask):
        self.state = [int(b) for b in bin(key)[2:].zfill(n)]
        self.mask = mask
        self.n = n
        self.mask_bits = [int(b) for b in bin(self.mask)[2:].zfill(n)]

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

    def __call__(self):
        self.update()
        b = self.state[-1]
        return b
    
lfsr = LFSR(64,seed3,mask)
output=0

for i in range(2000*8):
    output<<=1
    output +=lfsr()
enc_=bytes_to_long(enc)
mm=long_to_bytes(enc_^^output)
mmm=mm[:1000]
ou=[0 for _ in range(320)]
ji=[0 for _ in range(320)]
c=bin(bytes_to_long(mmm))[2:].zfill(8000)
for i in range(25):
    t=c[i*320:i*320+320]
    for j in range(320):
        if(t[j]=='1'):
            ji[j]+=1
        else:
            ou[j]+=1
flag=''
for i in range(320):
    if(ji[i]>ou[i]):
        flag+='1'
    elif(ji[i]==ou[i]):
        print(i)
    else:
        flag+='0'
flag=long_to_bytes(int(flag,2))
for i in range(256):
    f=flag[:-6]+long_to_bytes(i)+flag[-5:]
    if(hashlib.sha256(f).hexdigest()=='1b6208006b19ceddc493a8fe1342c1c7bba1800b2a66b9da4cd819f8440f331f'):
        print(f)
# LZSDS{d41d8c2d98f00b204e9800998ecf8427e}

algebra

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
from sage.all import *
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5
from secret import flag


class algebra(CommutativeRingElement):
    def __init__(self, parent, a1, a2, c=None):
        CommutativeRingElement.__init__(self, parent)
        self.a1 = a1
        self.a2 = a2
        self.c = c

    def __add__(self, other):
        return algebra(
            self.parent(), max(self.a1, other.a1), max(self.a2, other.a2), c=self.c
        )

    def __mul__(self, other):
        p = 0
        if self.c is not None:
            p += self.c
        first = max(p + self.a1 + other.a1, p + self.a2 + other.a2)
        second = max(p + self.a1 + other.a2, p + self.a2 + other.a1)
        return algebra(self.parent(), first, second, c=self.c)

    def __eq__(self, other):
        return (self.a1 == other.a1) and (self.a2 == other.a2)

    def __ne__(self, other):
        return not self.__eq__(other)

    def __repr__(self):
        return f"T({self.a1}, {self.a2})"

    def _mul_(self, other):
        return self.__mul__(other)


class algebraring(UniqueRepresentation, Parent):
    def __init__(self, c=None):
        Parent.__init__(self, category=CommutativeRings())
        self.c = c

    def _element_constructor_(self, a1, a2):
        return algebra(self, a1, a2, self.c)

    def __repr__(self):
        return "algebraring"

    def zero(self):
        return self(float("-inf"), float("-inf"))

    def random_element(self, lower_bound=-10, upper_bound=10):
        from random import randint

        a1 = randint(lower_bound, upper_bound)
        a2 = randint(lower_bound, upper_bound)
        return self._element_constructor_(a1, a2)


def change_ring(matrix, ring):
    n = len(matrix[0, :].list())
    new_matrix = [
        [ring(matrix[i, j].a1, matrix[i, j].a2) for j in range(n)] for i in range(n)
    ]
    return Matrix(ring, new_matrix)


def shift(matrix, x):
    n = len(matrix[0, :].list())
    ring = matrix.base_ring()
    new_matrix = [
        [ring(matrix[i, j].a1 + x, matrix[i, j].a2 + x) for j in range(n)] for i in range(n)
    ]
    return Matrix(ring, new_matrix)


n = 3

c = getRandomNBitInteger(256)
k = getRandomNBitInteger(256)
l = getRandomNBitInteger(256)
p = getRandomNBitInteger(256)

d = getRandomNBitInteger(256)
r = getRandomNBitInteger(256)
s = getRandomNBitInteger(256)
q = getRandomNBitInteger(256)

T = algebraring()
TA = algebraring(c)
TB = algebraring(d)

X = random_matrix(T, n, lower_bound=0, upper_bound=2**256)
Y = random_matrix(T, n, lower_bound=0, upper_bound=2**256)

XA = change_ring(change_ring(X, TA) ** k, T)
YA = change_ring(change_ring(Y, TA) ** l, T)
A = XA * YA
A_p = shift(A, p)

XB = change_ring(change_ring(X, TB) ** r, T)
YB = change_ring(change_ring(Y, TB) ** s, T)
B = XB * YB
B_q = shift(B, q)

KA = shift(XA, p) * B_q * YA
KB = shift(XB, q) * A_p * YB
assert KA == KB

key = md5(str(KA).encode()).digest()
aes = AES.new(key=key, mode=AES.MODE_ECB)
print(f"enc = {aes.encrypt(pad(flag, 16))}")
print(f"X = {X.list()}")
print(f"Y = {Y.list()}")
print(f"A_p = {A_p.list()}")
print(f"B_q = {B_q.list()}")
"""
enc = b'\x88I\xa6\xa5\x83\x8a\xd3$dk/\xf9\xdb\xc7\xec\xe8\xf6\x8c\x9d\xad\xe7\x8d\xb8\xe73~&\xb6O\xe5\x0f\x12\xf3?@\xd4\xc6I\xeel\x9d\xdd8\x92*gY`'
X = [T(59900590664029081588751597115949479657291730864508459758763562295986654520462, 68320552779283515276240499643319977619901440989200422494626425642962224959344), T(89698054093719949422762429034310548012077225043893131168337545047107450749496, 51479199576292239130066082976332639976062899059190752269878695108378488146679), T(62218736027330266192570144338062026977337231944985836220559539768109014406831, 61214354159525954062640070826510640683451706120539795727362849462686622564693), T(39805827211060089460158250456599968341463470401750393132792110953878249393569, 99103416592859133938491410425030428643259368893929508081326035011417306901272), T(20922493031536155240718266043337868355652138270147183521353456319726724009058, 31430964180770964194690164159235543367301572045989047438624310779165592317271), T(8959191626315499956806224120588498434035126032025230565571486221513367178374, 20067214390603904748675229391030612573671604470294660618614875919888930884780), T(66048220278298402781571427858585494416782927078968140383635650050886579125833, 18175597939833315588572188448012546734970985103503074208793106634216584036818), T(14432081053446841732493980558668616443341123394659689880088380115934894274635, 83557493069309650142798328460651561327339732728386566873314215777128303177667), T(34511162979554971448736265846077014796752072453004958739933710734947541396694, 77364571020765493103034943723333754233327577188690990300833856668531817680505)]
Y = [T(78533528545456238383274783853785358016819467733594018596743219756487720633746, 93976221569207299395273293543645974643384826524816615562497005292252667770601), T(103766862112463335445955325531890205089005117500922857426350491681602103969000, 47323529900779960229909476477918095608118443655903527805237066535366116839149), T(10190752330406968772077432866677538790850926811710030717810026338836331450472, 86375880251137784911361557173115785351126971447566503084261189167084220453288), T(13780196681979042044702022951434986810164135209191561823725939514845972817610, 55170363535880083300862447306063246181282182639154190917220001586753468629546), T(436029875577652990270691130860178026240806299188121622633421834221330373636, 110804259765120571425960874898903708961853698355143533817410855395636486531982), T(6397911849400997286703265695504239070876241554571709807303889197285939312681, 17360696619752702589750097897661044951586752285334140009669640422948343241568), T(58041034583523761593801980039841494595215125402194920275127841961766699686394, 54766044749028865088458074550257196739016298676359665986238379481142351990626), T(77530103367856397256662107816221151235947660504364282548276904992741575506849, 63854892725980295947169956482257581700294549443273322483764382131671051522332), T(47497441477952935509240863594022229337695084880724507207404445061842628668952, 56713418154978297086219120150091406983389112617302018465360827172758909144570)]
A_p = [T(40547797283575399311345964287271714617688023231464400205040285835460999315476731205228816544079212468645004319629302959473711018684702750872290449940972698, 40547797283575399311345964287271714617688023231464400205040285835460999315476698934497596879746169782553959201278357925243089469169482083236651301175074462), T(40547797283575399311345964287271714617688023231464400205040285835460999315476786839125045784567337567072597160092083530989427008027602941726099332958875134, 40547797283575399311345964287271714617688023231464400205040285835460999315476750004263963436463523550691311785519855896914393402679802307379634177780083118), T(40547797283575399311345964287271714617688023231464400205040285835460999315476706776849302561292697869327278531705692232746803441653969601206061897674894004, 40547797283575399311345964287271714617688023231464400205040285835460999315476682432777130064993198309463393760622192553532626436203592834759900982411655833), T(40547797283575399311345964287271714617688023231464400205040285835460999315476733573193663026027748192077028026006061293036706834385224678998540725414561492, 40547797283575399311345964287271714617688023231464400205040285835460999315476709827727502107645065946715613329058910783689656325976029039752886304715182546), T(40547797283575399311345964287271714617688023231464400205040285835460999315476789207089892266515873290504620866468841864552422823728124869852349608432463928, 40547797283575399311345964287271714617688023231464400205040285835460999315476765461623731348133191045143206169521691355205372315318929230606695187733084982), T(40547797283575399311345964287271714617688023231464400205040285835460999315476709144814149043241233592759302238082450566309799257354491529332312173148482798, 40547797283575399311345964287271714617688023231464400205040285835460999315476685399347988124858551347397887541135300056962748748945295890086657752449103852), T(40547797283575399311345964287271714617688023231464400205040285835460999315476692793936572469446889818453385542291673187750773962605187059907381322027502633, 40547797283575399311345964287271714617688023231464400205040285835460999315476725064667792133779932504544430660642618221981395512120407727543020470793400869), T(40547797283575399311345964287271714617688023231464400205040285835460999315476746626235376326170902419020010827637210112057551060804659922530107892689013547, 40547797283575399311345964287271714617688023231464400205040285835460999315476780698564021374268057602972023501105398793497111501463307918396829353811303305), T(40547797283575399311345964287271714617688023231464400205040285835460999315476676292216105654693918345362820101635507816040310929639297811430631003264084004, 40547797283575399311345964287271714617688023231464400205040285835460999315476700636288278150993417905226704872719007495254487935089674577876791918527322175)]
B_q = [T(44956584717324859629636950162153871886560739437959809729281253007078755840271381302732123072890496216398568268656559622476770594999251404506445788064037538, 44956584717324859629636950162153871886560739437959809729281253007078755840271413573463342737223538902489613387007504656707392144514472072142084936829935774), T(44956584717324859629636950162153871886560739437959809729281253007078755840271432372498489629607849984535920852898057594148074528509571628649428664669046194, 44956584717324859629636950162153871886560739437959809729281253007078755840271469207359571977711664000917206227470285228223108133857372262995893819847838210), T(44956584717324859629636950162153871886560739437959809729281253007078755840271364801011656258137524743308002828000394250766307562033362156029695469300618909, 44956584717324859629636950162153871886560739437959809729281253007078755840271389145083828754437024303171887599083893929980484567483738922475856384563857080), T(44956584717324859629636950162153871886560739437959809729281253007078755840271392195962028300789392380560222396437112480923337451805798361022680791604145622, 44956584717324859629636950162153871886560739437959809729281253007078755840271415941428189219172074625921637093384262990270387960214994000268335212303524568), T(44956584717324859629636950162153871886560739437959809729281253007078755840271447829858257541277517478987815236899893052439053441148698551876489674622048058, 44956584717324859629636950162153871886560739437959809729281253007078755840271471575324418459660199724349229933847043561786103949557894191122144095321427004), T(44956584717324859629636950162153871886560739437959809729281253007078755840271367767582514318002877781242496608513501754196429874775065211356452239338066928, 44956584717324859629636950162153871886560739437959809729281253007078755840271391513048675236385560026603911305460652263543480383184260850602106660037445874), T(44956584717324859629636950162153871886560739437959809729281253007078755840271407432902318326924258938389039728020819919215076637950177048812814957682363945, 44956584717324859629636950162153871886560739437959809729281253007078755840271375162171098662591216252297994609669874884984455088434956381177175808916465709), T(44956584717324859629636950162153871886560739437959809729281253007078755840271463066798547567412384036816632568483600490730792627293077239666623840700266381, 44956584717324859629636950162153871886560739437959809729281253007078755840271428994469902519315228852864619895015411809291232186634429243799902379577976623), T(44956584717324859629636950162153871886560739437959809729281253007078755840271383004522804344137744339071313940097209192488169060919443899146586405416285251, 44956584717324859629636950162153871886560739437959809729281253007078755840271358660450631847838244779207429169013709513273992055469067132700425490153047080)]
"""

参考https://eprint.iacr.org/2024/010.pdf 来攻击即可，难度不大，似乎都卡在找这篇论文了 XD

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
from tqdm import trange
from Crypto.Cipher import AES
from hashlib import md5

class TropicalPairElement(CommutativeRingElement):
    def __init__(self, parent, a1, a2, c=None):
        CommutativeRingElement.__init__(self, parent)
        self.a1 = a1
        self.a2 = a2
        self.c = c

    def __add__(self, other):
        return TropicalPairElement(
            self.parent(), max(self.a1, other.a1), max(self.a2, other.a2), c=self.c
        )

    def __mul__(self, other):
        p = 0
        if self.c is not None:
            p += self.c
        first = max(p + self.a1 + other.a1, p + self.a2 + other.a2)
        second = max(p + self.a1 + other.a2, p + self.a2 + other.a1)
        return TropicalPairElement(self.parent(), first, second, c=self.c)

    def __eq__(self, other):
        return (self.a1 == other.a1) and (self.a2 == other.a2)

    def __ne__(self, other):
        return not self.__eq__(other)

    def is_zero(self):
        return self.a1 == float("-inf") and self.a2 == float("-inf")

    def __repr__(self):
        return f"T({self.a1}, {self.a2})"

    def _mul_(self, other):
        return self.__mul__(other)


class TropicalPairSemiring(UniqueRepresentation, Parent):
    def __init__(self, c=None):
        Parent.__init__(self, category=CommutativeRings())
        self.c = c

    def _element_constructor_(self, a1, a2):
        return TropicalPairElement(self, a1, a2, self.c)

    def __repr__(self):
        return "Tropical Semiring of Pairs"

    def zero(self):
        return self(float("-inf"), float("-inf"))

    def one(self):
        return self(0, float("-inf"))

    def random_element(self, lower_bound=-10, upper_bound=10):
        from random import randint

        a1 = randint(lower_bound, upper_bound)
        a2 = randint(lower_bound, upper_bound)
        return self._element_constructor_(a1, a2)


def change_ring(matrix, ring):
    n = len(matrix[0, :].list())
    new_matrix = [
        [ring(matrix[i, j].a1, matrix[i, j].a2) for j in range(n)] for i in range(n)
    ]
    return Matrix(ring, new_matrix)


class TropicalElement(CommutativeRingElement):
    def __init__(self, parent, a):
        CommutativeRingElement.__init__(self, parent)
        self.a = a

    def __add__(self, other):
        return TropicalElement(self.parent(), max(self.a, other.a))

    def __sub__(self, other):
        return TropicalElement(self.parent(), self.a - other.a)

    def __mul__(self, other):
        return TropicalElement(self.parent(), self.a + other.a)

    def __eq__(self, other):
        return self.a == other.a

    def __ne__(self, other):
        return not self.__eq__(other)

    def is_zero(self):
        return self.a == float("-inf")

    def __repr__(self):
        return f"T({self.a})"

    def _mul_(self, other):
        return self.__mul__(other)


class TropicalSemiring(UniqueRepresentation, Parent):
    def __init__(self):
        Parent.__init__(self, category=CommutativeRings())

    def _element_constructor_(self, a):
        return TropicalElement(self, a)

    def __repr__(self):
        return "Tropical Semiring of Pairs"

    def zero(self):
        return self(float("-inf"))

    def one(self):
        return self(0)

    def random_element(self, lower_bound=-10, upper_bound=10):
        from random import randint

        a = randint(lower_bound, upper_bound)
        return self._element_constructor_(a)

    def get_identity_matrix(self, n):
        return Matrix(self,[[self.one() if i == j else self.zero() for j in range(n)] for i in range(n)])


def shift(matrix, x):
    n = len(matrix[0, :].list())
    ring = matrix.base_ring()
    new_matrix = [[ring(matrix[i, j].a1 + x, matrix[i, j].a2 + x) if isinstance(matrix[i, j], TropicalPairElement) else ring(matrix[i, j].a + x) for j in range(n)] for i in range(n)]
    return Matrix(ring, new_matrix)


def pair_to_Semiring(matrix):
    Q = TropicalSemiring()
    Y = []
    n = len(matrix[0, :].list())
    for i in range(n):
        Y_row = []
        for j in range(n):
            Y_row.append(Q(matrix[i, j].a1))
            Y_row.append(Q(matrix[i, j].a2))
        Y.append(Y_row)
        Y_row = []
        for j in range(n):
            Y_row.append(Q(matrix[i, j].a2))
            Y_row.append(Q(matrix[i, j].a1))
        Y.append(Y_row)
    return Matrix(Q, Y)
    

def Semiring_to_pair(matrix):
    Q = TropicalPairSemiring()
    Y = []
    n = len(matrix[0, :].list()) // 2
    for i in range(0, 2 * n, 2):
        YY = []
        for j in range(0, n):
            YY.append(Q(matrix[i,2*j].a,matrix[i,2*j+1].a))
        Y.append(YY)
    return Matrix(Q, Y)


def check(X):
    a = X[0, 0]
    for element in X.list():
        if element != a:
            return False
    return True


def attack(U, D1, M, D2, maxt=None):
    if maxt == None:
        maxt = len(U[0, :].list()) ** 3
    D1_ = [D1**i for i in range(maxt)]
    D2_ = [D2**i for i in range(maxt)]
    for t1 in trange(maxt):
        for t2 in range(maxt):
            T = U - D1_[t1] * M * D2_[t2]
            if check(T):
                yield (int(T[0, 0].a), t1, t2)

n = 3
T = TropicalPairSemiring()

enc = b'\x88I\xa6\xa5\x83\x8a\xd3$dk/\xf9\xdb\xc7\xec\xe8\xf6\x8c\x9d\xad\xe7\x8d\xb8\xe73~&\xb6O\xe5\x0f\x12\xf3?@\xd4\xc6I\xeel\x9d\xdd8\x92*gY`'
X = [T(59900590664029081588751597115949479657291730864508459758763562295986654520462, 68320552779283515276240499643319977619901440989200422494626425642962224959344), T(89698054093719949422762429034310548012077225043893131168337545047107450749496, 51479199576292239130066082976332639976062899059190752269878695108378488146679), T(62218736027330266192570144338062026977337231944985836220559539768109014406831, 61214354159525954062640070826510640683451706120539795727362849462686622564693), T(39805827211060089460158250456599968341463470401750393132792110953878249393569, 99103416592859133938491410425030428643259368893929508081326035011417306901272), T(20922493031536155240718266043337868355652138270147183521353456319726724009058, 31430964180770964194690164159235543367301572045989047438624310779165592317271), T(8959191626315499956806224120588498434035126032025230565571486221513367178374, 20067214390603904748675229391030612573671604470294660618614875919888930884780), T(66048220278298402781571427858585494416782927078968140383635650050886579125833, 18175597939833315588572188448012546734970985103503074208793106634216584036818), T(14432081053446841732493980558668616443341123394659689880088380115934894274635, 83557493069309650142798328460651561327339732728386566873314215777128303177667), T(34511162979554971448736265846077014796752072453004958739933710734947541396694, 77364571020765493103034943723333754233327577188690990300833856668531817680505)]
Y = [T(78533528545456238383274783853785358016819467733594018596743219756487720633746, 93976221569207299395273293543645974643384826524816615562497005292252667770601), T(103766862112463335445955325531890205089005117500922857426350491681602103969000, 47323529900779960229909476477918095608118443655903527805237066535366116839149), T(10190752330406968772077432866677538790850926811710030717810026338836331450472, 86375880251137784911361557173115785351126971447566503084261189167084220453288), T(13780196681979042044702022951434986810164135209191561823725939514845972817610, 55170363535880083300862447306063246181282182639154190917220001586753468629546), T(436029875577652990270691130860178026240806299188121622633421834221330373636, 110804259765120571425960874898903708961853698355143533817410855395636486531982), T(6397911849400997286703265695504239070876241554571709807303889197285939312681, 17360696619752702589750097897661044951586752285334140009669640422948343241568), T(58041034583523761593801980039841494595215125402194920275127841961766699686394, 54766044749028865088458074550257196739016298676359665986238379481142351990626), T(77530103367856397256662107816221151235947660504364282548276904992741575506849, 63854892725980295947169956482257581700294549443273322483764382131671051522332), T(47497441477952935509240863594022229337695084880724507207404445061842628668952, 56713418154978297086219120150091406983389112617302018465360827172758909144570)]
A_p = [T(40547797283575399311345964287271714617688023231464400205040285835460999315476731205228816544079212468645004319629302959473711018684702750872290449940972698, 40547797283575399311345964287271714617688023231464400205040285835460999315476698934497596879746169782553959201278357925243089469169482083236651301175074462), T(40547797283575399311345964287271714617688023231464400205040285835460999315476786839125045784567337567072597160092083530989427008027602941726099332958875134, 40547797283575399311345964287271714617688023231464400205040285835460999315476750004263963436463523550691311785519855896914393402679802307379634177780083118), T(40547797283575399311345964287271714617688023231464400205040285835460999315476706776849302561292697869327278531705692232746803441653969601206061897674894004, 40547797283575399311345964287271714617688023231464400205040285835460999315476682432777130064993198309463393760622192553532626436203592834759900982411655833), T(40547797283575399311345964287271714617688023231464400205040285835460999315476733573193663026027748192077028026006061293036706834385224678998540725414561492, 40547797283575399311345964287271714617688023231464400205040285835460999315476709827727502107645065946715613329058910783689656325976029039752886304715182546), T(40547797283575399311345964287271714617688023231464400205040285835460999315476789207089892266515873290504620866468841864552422823728124869852349608432463928, 40547797283575399311345964287271714617688023231464400205040285835460999315476765461623731348133191045143206169521691355205372315318929230606695187733084982), T(40547797283575399311345964287271714617688023231464400205040285835460999315476709144814149043241233592759302238082450566309799257354491529332312173148482798, 40547797283575399311345964287271714617688023231464400205040285835460999315476685399347988124858551347397887541135300056962748748945295890086657752449103852), T(40547797283575399311345964287271714617688023231464400205040285835460999315476692793936572469446889818453385542291673187750773962605187059907381322027502633, 40547797283575399311345964287271714617688023231464400205040285835460999315476725064667792133779932504544430660642618221981395512120407727543020470793400869), T(40547797283575399311345964287271714617688023231464400205040285835460999315476746626235376326170902419020010827637210112057551060804659922530107892689013547, 40547797283575399311345964287271714617688023231464400205040285835460999315476780698564021374268057602972023501105398793497111501463307918396829353811303305), T(40547797283575399311345964287271714617688023231464400205040285835460999315476676292216105654693918345362820101635507816040310929639297811430631003264084004, 40547797283575399311345964287271714617688023231464400205040285835460999315476700636288278150993417905226704872719007495254487935089674577876791918527322175)]
B_q = [T(44956584717324859629636950162153871886560739437959809729281253007078755840271381302732123072890496216398568268656559622476770594999251404506445788064037538, 44956584717324859629636950162153871886560739437959809729281253007078755840271413573463342737223538902489613387007504656707392144514472072142084936829935774), T(44956584717324859629636950162153871886560739437959809729281253007078755840271432372498489629607849984535920852898057594148074528509571628649428664669046194, 44956584717324859629636950162153871886560739437959809729281253007078755840271469207359571977711664000917206227470285228223108133857372262995893819847838210), T(44956584717324859629636950162153871886560739437959809729281253007078755840271364801011656258137524743308002828000394250766307562033362156029695469300618909, 44956584717324859629636950162153871886560739437959809729281253007078755840271389145083828754437024303171887599083893929980484567483738922475856384563857080), T(44956584717324859629636950162153871886560739437959809729281253007078755840271392195962028300789392380560222396437112480923337451805798361022680791604145622, 44956584717324859629636950162153871886560739437959809729281253007078755840271415941428189219172074625921637093384262990270387960214994000268335212303524568), T(44956584717324859629636950162153871886560739437959809729281253007078755840271447829858257541277517478987815236899893052439053441148698551876489674622048058, 44956584717324859629636950162153871886560739437959809729281253007078755840271471575324418459660199724349229933847043561786103949557894191122144095321427004), T(44956584717324859629636950162153871886560739437959809729281253007078755840271367767582514318002877781242496608513501754196429874775065211356452239338066928, 44956584717324859629636950162153871886560739437959809729281253007078755840271391513048675236385560026603911305460652263543480383184260850602106660037445874), T(44956584717324859629636950162153871886560739437959809729281253007078755840271407432902318326924258938389039728020819919215076637950177048812814957682363945, 44956584717324859629636950162153871886560739437959809729281253007078755840271375162171098662591216252297994609669874884984455088434956381177175808916465709), T(44956584717324859629636950162153871886560739437959809729281253007078755840271463066798547567412384036816632568483600490730792627293077239666623840700266381, 44956584717324859629636950162153871886560739437959809729281253007078755840271428994469902519315228852864619895015411809291232186634429243799902379577976623), T(44956584717324859629636950162153871886560739437959809729281253007078755840271383004522804344137744339071313940097209192488169060919443899146586405416285251, 44956584717324859629636950162153871886560739437959809729281253007078755840271358660450631847838244779207429169013709513273992055469067132700425490153047080)]
X = Matrix(T, [X[3*i:3*(i+1)] for i in range(3)])
Y = Matrix(T, [Y[3*i:3*(i+1)] for i in range(3)])
A_p = Matrix(T, [A_p[3*i:3*(i+1)] for i in range(3)])
B_q = Matrix(T, [B_q[3*i:3*(i+1)] for i in range(3)])
M = TropicalSemiring().get_identity_matrix(2*n)
X_ = pair_to_Semiring(X)
Y_ = pair_to_Semiring(Y)
A_p_ = pair_to_Semiring(A_p)
B_q_ = pair_to_Semiring(B_q)
for t, k_, l_ in attack(A_p_, X_, M, Y_):
    K = shift((X_**k_ * B_q_ * Y_**l_), t)
    key = md5(str(Semiring_to_pair(K)).encode()).digest()
    aes = AES.new(key=key, mode=AES.MODE_ECB)
    flag = aes.decrypt(enc)
    if b'LZSDS' in flag:
        print(flag)
        break
# LZSDS{dbc6bad4-7e16-4883-b7a1-682333a18c7c}

MISC

golf

题目

1
2
3
4
5
6
7
8
9
10
11
12
import base64

flag = open('flag', 'r').read()
BOX = ['63', '7c', '77', '7b', 'f2', '6b', '6f', 'c5', '30', '01', '67', '2b', 'fe', 'd7', 'ab', '76', 'ca', '82', 'c9', '7d', 'fa', '59', '47', 'f0', 'ad', 'd4', 'a2', 'af', '9c', 'a4', '72', 'c0', 'b7', 'fd', '93', '26', '36', '3f', 'f7', 'cc', '34', 'a5', 'e5', 'f1', '71', 'd8', '31', '15', '04', 'c7', '23', 'c3', '18', '96', '05', '9a', '07', '12', '80', 'e2', 'eb', '27', 'b2', '75', '09', '83', '2c', '1a', '1b', '6e', '5a', 'a0', '52', '3b', 'd6', 'b3', '29', 'e3', '2f', '84', '53', 'd1', '00', 'ed', '20', 'fc', 'b1', '5b', '6a', 'cb', 'be', '39', '4a', '4c', '58', 'cf', 'd0', 'ef', 'aa', 'fb', '43', '4d', '33', '85', '45', 'f9', '02', '7f', '50', '3c', '9f', 'a8', '51', 'a3', '40', '8f', '92', '9d', '38', 'f5', 'bc', 'b6', 'da', '21', '10', 'ff', 'f3', 'd2', 'cd', '0c', '13', 'ec', '5f', '97', '44', '17', 'c4', 'a7', '7e', '3d', '64', '5d', '19', '73', '60', '81', '4f', 'dc', '22', '2a', '90', '88', '46', 'ee', 'b8', '14', 'de', '5e', '0b', 'db', 'e0', '32', '3a', '0a', '49', '06', '24', '5c', 'c2', 'd3', 'ac', '62', '91', '95', 'e4', '79', 'e7', 'c8', '37', '6d', '8d', 'd5', '4e', 'a9', '6c', '56', 'f4', 'ea', '65', '7a', 'ae', '08', 'ba', '78', '25', '2e', '1c', 'a6', 'b4', 'c6', 'e8', 'dd', '74', '1f', '4b', 'bd', '8b', '8a', '70', '3e', 'b5', '66', '48', '03', 'f6', '0e', '61', '35', '57', 'b9', '86', 'c1', '1d', '9e', 'e1', 'f8', '98', '11', '69', 'd9', '8e', '94', '9b', '1e', '87', 'e9', 'ce', '55', '28', 'df', '8c', 'a1', '89', '0d', 'bf', 'e6', '42', '68', '41', '99', '2d', '0f', 'b0', '54', 'bb', '16']
s = None
print('give me your solve:')
inp = base64.b64decode(input().encode()).decode()
blacklist = ['BOX', 'flag', 'import', 'os', 'sys', 'subprocess', 'eval', 'exec', '_', 'open', 'compile', 'globals', 'locals', 'vars', 'setattr', 'getattr', 'dir', 'read', 'chr', 'help', 'breakpoint']
assert all(i not in inp for i in blacklist) and len(inp) <= 187
exec(inp)
if BOX == s:
    print(flag)

给非烂了/(ㄒoㄒ)/~~

预期是在187个字符之内实现AES的BOX

做法不是很好说明，具体还是看exp吧

1
2
3
4
5
6
import base64

i = "r=lambda x,s:(x<<s|x>>8-s)&255\ns=['63']*256;p=q=1\nfor o in[0]*255:p=(p^(p*2)^[27,0][p<128])&255;q^=q*2;q^=q*4;q^=q*16;q&=255;q^=[9,0][q<128];s[p]=f'{q^r(q,1)^r(q,2)^r(q,3)^r(q,4)^99:02x}'"
print(base64.b64encode(i.encode()).decode())
print(len(i))
# cj1sYW1iZGEgeCxzOih4PDxzfHg+PjgtcykmMjU1CnM9Wyc2MyddKjI1NjtwPXE9MQpmb3IgbyBpblswXSoyNTU6cD0ocF4ocCoyKV5bMjcsMF1bcDwxMjhdKSYyNTU7cV49cSoyO3FePXEqNDtxXj1xKjE2O3EmPTI1NTtxXj1bOSwwXVtxPDEyOF07c1twXT1mJ3txXnIocSwxKV5yKHEsMilecihxLDMpXnIocSw0KV45OTowMnh9Jw==