糖醋小鸡块的blog
0%

2024-蜀道山高校联合公益赛-wp-crypto

发表于 分类于 Valine：

有师傅赛后给了我这一套题，正好学弟们也参加了这场，所以这几天到处线下比赛（其实是旅游）的中途断断续续做了做，现在写个wp。

xorsa

题目：

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
from Crypto.Util.number import *
from gmpy2 import *
import uuid
flag='LZSDS{'+str(uuid.uuid4())+'}'

while True:
    p=getPrime(512)
    if p.bit_length()==512:
        break
mask=??????
q=p^mask
hint1=p^q
hint2=q
n=p*q
e=2026
m=bytes_to_long(flag.encode())
c=pow(m,e,n)
print("c =",c)
print("n =",n)
print("hint1 =",hint1)
print("hint2 =",hint2)

'''
c = 13760578729891127041098229431259961120216468948795732373975536417751222443069805775693845560005881981622202089883866395577154701229046245882282127054969114210307175116574178428823043817041956207503299220721042136515863979655578210499512044917781566303947681251248645504273995402630701480590505840473412765662
n = 14247038211821385209759067256846232227444163173099199085257790370590450749665206556163364754269182255358084948354345827898987234756662133974633117062902370811855466665351784027125333112663075085395676501121759786699720149098576433141817737564928779420725539793335830274229206316999461309927000523188222801659
hint1 = 8938538619961731399716016665470564084986243880394928918482374295814509353382364651201249532111268951793354572124324033902502588541297713297622432670722730
hint2 = 1493298155243474837320092849325750387759519643879388609208314494000605554020636706320849032906759121914762492378489852575583260177546578935320977613050647
'''

题目的hint2直接给了q，用n做整除就有p，之后就是e与phi有一个公因子2的问题，分别开根之后crt起来就可以得到flag。

exp：

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
from Crypto.Util.number import *

e = 2026
c = 13760578729891127041098229431259961120216468948795732373975536417751222443069805775693845560005881981622202089883866395577154701229046245882282127054969114210307175116574178428823043817041956207503299220721042136515863979655578210499512044917781566303947681251248645504273995402630701480590505840473412765662
n = 14247038211821385209759067256846232227444163173099199085257790370590450749665206556163364754269182255358084948354345827898987234756662133974633117062902370811855466665351784027125333112663075085395676501121759786699720149098576433141817737564928779420725539793335830274229206316999461309927000523188222801659
hint1 = 8938538619961731399716016665470564084986243880394928918482374295814509353382364651201249532111268951793354572124324033902502588541297713297622432670722730
hint2 = 1493298155243474837320092849325750387759519643879388609208314494000605554020636706320849032906759121914762492378489852575583260177546578935320977613050647

q = hint2
p = n // q
phi = (p-1)*(q-1)

m2 = pow(c, inverse(e//2, phi), n)
PR.<x> = Zmod(p)[]
f = x^2 - m2
resp = f.roots()

PR.<x> = Zmod(q)[]
f = x^2 - m2
resq = f.roots()

for i in resp:
    for j in resq:
        try:
            nlist = [p,q]
            clist = [int(i[0]),int(j[0])]
            m = crt(nlist,clist)
            flag = long_to_bytes(int(m)).decode()
            print(flag)
        except:
            pass


#LZSDS{fcfa4147-d982-4cd8-9ab7-50669e559736}



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的随机数x，并计算：

给出y、g、p以及x的低404位，需要求出x来解AES。

检查一下p-1的因子发现是这样：

1
2 · 385057 · 727646221919<12> · 193893885660581<15> · 193166780451443059<18> · 3881671740574461385603964379125531<34> · 77364837756797328321829387679372821139010103152781295726133301368685957<71>

第2-4个因子都比较小，dlp是比较容易求的，而他们的乘积有106bit，所以和x的低404位crt一下的话可以获得510bit左右的信息。

而p是512bit的，所以这个范围已经很接近真实的x，只需要再小爆一下就可以了。

exp：

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib

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'
g = 37
p = 6302810904265501037924401786295397288170843149817176985522767895582968290551414928308932200691953758726228011793524154509586354502691822110981490737900239
r1 = 193166780451443059
r2 = 3881671740574461385603964379125531
r3 = 77364837756797328321829387679372821139010103152781295726133301368685957

r = r1*r2*r3
Fp = GF(p)
xr = discrete_log(Fp(pow(y,r,p)), Fp(pow(g,r,p)), operation="*", ord=(p-1)//r)

x = crt([xl, xr], [2^404, (p-1)//r])

for i in range(2^10):
    temp = x + i*lcm([2^404, (p-1)//r])
    if(temp > p-1):
        break
    key = hashlib.md5(str(temp).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}



签到!?

题目：

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
import hashlib
import gmpy2
from Crypto.Util.number import *

flag = b''
m = bytes_to_long(flag)
a = getPrime(1024);b = getPrime(1024);c = getPrime(1024);d = getPrime(128);n = getPrime(1024)

y = 0
for i in range(n+1):
    x = a*i+b
    y += (x//c)*i

if isPrime(y):
    pass
else:
    y = gmpy2.next_prime(y)

tmp = hashlib.md5(str(y).encode()).hexdigest()
cc = pow(d,int(tmp,16),n)

e = 52595
c3 = pow(m,e,y)
c4 = pow(a*m+b,e,y)

print('a =',a)
print('b =',b)
print('c =',c)
print('d =',d)
print('n =',n)
print('cc =',cc)
print('c3 =',c3)
print('c4 =',c4)

# a = 111406501658261575231314234156049408466629183228824951940397996549233343837444378602865612803520661162092930300450227752136992834681100817745708350750328806415942948297139334928206997684336812509277385194519252428443612078118898709910123899406877252165189871184174372173644257644751683554571917518602985248103
# b = 105754676330138681072874983469472331489357433467464632569519728162042635815478944541148477139634812590504509864018789141646023167940434519693396156652820504954321975234632684842726055170039476517204102162821838097200563406354332901840869790790015364563201564244853988381159598703692897790765599565893345380553
# c = 170600113386807592462858319531540617567133570960670217596634485327958954420566724690918464046407772634147753234450737353193173923873879958589824005123545638184186453602233634037809629812111243183450002707175703333920828461245731172668838771751457387207779427008047454548463398397079552688864699792002976130047
# d = 229823065384822950015724955215847476631
# n = 169428502732446427714165121824913735747920403586738853921495983139840483604966163669399379093896888954652663456556496947292418676356981468237136780175047349167561875551277606897449804926885192045760368051311243166090981061101913245493065268528634952461907634111084108803207099139506693313918834075542826388183
# cc = 105324189115602620621800798531371526317853537119154266873657796691360779628410005302892575043351618666760506544724245300953227618282253336044824499240524905915476071538182232622771476344880513465689824790881603214009332398038930113198889292160815386819010434380814610557831376377280232817587639852364108539892
# c3 = 791801877941025556812260671377895956461402542450910806211264471681160334454968210834058573374802678147030803278793623022600774676606263064237697305258809520983007689647782562591531551137322198839457388757360504835352506363286012791482381915207800512880078672338934869429374580298570299136345411005736381918329554791587303420005844148692211002120828912548145333101329366616120459060822278273689238720580513363138874807500470690610311215233669314430430554144017703130663205211791135140813550629558977548476426876112982216083736966681702987597722820852894624586687261277977164491919429492650781084296080288020330875247574855906390404509845311187888602482142661083771230000178356724801659025002251056321173755782500071361114235931347064100961296562902176010402092225439511324625249209554560052627349307173707304259200397468217911136832133364420684914378754649851955359890480612161233059263522713390654506714661592991514955637304
# c4 = 101923921400007092267790478161024103799892954880859052793422615329222813129835333442478632220182544724530301816393072530672763263645022408189547815923383906565611606888926097135400527299006862907781058931838804887994883095683814203452663467235776407572822082944022133476409878374663555627258035317631489173719410785629090255417861686081571376756906799938593870745471956936393066774907988124411318124604178920755698887086399177650502004883860844187365911953472980921213184639411672503691612418437276530896198002610276732906004741692286470538565288852344158830229580771834123582320782258698392853262935944858898937999647004599668060425461150846652642931397311468425476235056756761805933421643525566845928057238991458469113290576159465234243274971982913939709869951907061169493132309863852016682533998299893705859834844325876890511405664336001308600133946440998690503095156964687645597227368993047211862703399858777949126471093

题目主要分为两个部分，第一个部分要求计算出：

第二部分则要通过如下两个式子计算出m，m就是flag：

第一部分是一种speedup，所以十有八九是算法，搜索一下可以知道这是类欧几里得算法，照着下面文章写个分段函数就可以了：

P5170 【模板】类欧几里得算法 - 洛谷 (luogu.com.cn)

直接分三种函数$f,g,h$跑的会很慢，所以要照上文最后的说法把所有一起计算才好

肯定有师傅会想问这种算法怎么搜，我一般的方法是把公式打出来然后搜公式，比如对于这题就是：

1
\sum_{i=0}^{n}{i \cdot \lfloor \frac{ai+b}{c} \rfloor}

第二部分显然是个HGCD，但是y是个素数，而且52595实际上和y-1是互素的，所以直接求逆就可以拿到flag。

exp：

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
from Crypto.Util.number import *
import hashlib
import gmpy2

def f(a,b,c,N):
    if(a == 0):
        return (N+1)*(b//c)
    elif(a >= c or b >= c):
        return (N*(N+1)//2)*(a//c) + (N+1)*(b//c) + f(a%c, b%c, c, N)
    else:
        M = (a*N+b)//c
        return N*M - f(c, c-b-1, a, M-1)

def g(a,b,c,N):
    if(a == 0):
        return (N+1)*(b//c)^2
    elif(a >= c or b >= c):
        return g(a%c, b%c, c, N) + 2*(a//c)*h(a%c, b%c, c, N) + 2*(b//c)*f(a%c, b%c, c, N) +\
            (N*(N+1)*(2*N+1)//6)*(a//c)^2 + N*(N+1)*(a//c)*(b//c) + (N+1)*(b//c)^2
    else:
        M = (a*N+b)//c
        return N*M*(M+1) - f(a, b, c, N) - 2*h(c, c-b-1, a, M-1) - 2*f(c, c-b-1, a, M-1)

def h(a,b,c,N):
    if(a == 0):
        return (N*(N+1)//2)*(b//c)
    elif(a >= c or b >= c):
        return h(a%c, b%c, c, N) + (N*(N+1)*(2*N+1)//6)*(a//c) + (N*(N+1)//2)*(b//c)
    else:
        M = (a*N+b)//c
        return (M*N*(N+1) - g(c, c-b-1, a, M-1) - f(c, c-b-1, a, M-1))//2

def calc(a, b, c, N):
    F, G, H = 0, 0, 0
    if(a == 0):
        F = (N+1)*(b//c)
        G = (N+1)*(b//c)^2
        H = (N*(N+1)//2)*(b//c)
    elif(a >= c or b >= c):
        ff, gg, hh = calc(a%c, b%c, c, N)
        F = (N*(N+1)//2)*(a//c) + (N+1)*(b//c) + ff
        G = gg + 2*(a//c)*hh + 2*(b//c)*ff +\
            (N*(N+1)*(2*N+1)//6)*(a//c)^2 + N*(N+1)*(a//c)*(b//c) + (N+1)*(b//c)^2
        H = hh + (N*(N+1)*(2*N+1)//6)*(a//c) + (N*(N+1)//2)*(b//c)
    else:
        M = (a*N+b)//c
        ff, gg, hh = calc(c, c-b-1, a, M-1)
        F = N*M - ff
        G = N*M*(M+1) - f(a, b, c, N) - 2*hh - 2*ff
        H = (M*N*(N+1) - gg - ff)//2
    return [F, G, H]

a = 111406501658261575231314234156049408466629183228824951940397996549233343837444378602865612803520661162092930300450227752136992834681100817745708350750328806415942948297139334928206997684336812509277385194519252428443612078118898709910123899406877252165189871184174372173644257644751683554571917518602985248103
b = 105754676330138681072874983469472331489357433467464632569519728162042635815478944541148477139634812590504509864018789141646023167940434519693396156652820504954321975234632684842726055170039476517204102162821838097200563406354332901840869790790015364563201564244853988381159598703692897790765599565893345380553
c = 170600113386807592462858319531540617567133570960670217596634485327958954420566724690918464046407772634147753234450737353193173923873879958589824005123545638184186453602233634037809629812111243183450002707175703333920828461245731172668838771751457387207779427008047454548463398397079552688864699792002976130047
d = 229823065384822950015724955215847476631
n = 169428502732446427714165121824913735747920403586738853921495983139840483604966163669399379093896888954652663456556496947292418676356981468237136780175047349167561875551277606897449804926885192045760368051311243166090981061101913245493065268528634952461907634111084108803207099139506693313918834075542826388183
cc = 105324189115602620621800798531371526317853537119154266873657796691360779628410005302892575043351618666760506544724245300953227618282253336044824499240524905915476071538182232622771476344880513465689824790881603214009332398038930113198889292160815386819010434380814610557831376377280232817587639852364108539892
c3 = 791801877941025556812260671377895956461402542450910806211264471681160334454968210834058573374802678147030803278793623022600774676606263064237697305258809520983007689647782562591531551137322198839457388757360504835352506363286012791482381915207800512880078672338934869429374580298570299136345411005736381918329554791587303420005844148692211002120828912548145333101329366616120459060822278273689238720580513363138874807500470690610311215233669314430430554144017703130663205211791135140813550629558977548476426876112982216083736966681702987597722820852894624586687261277977164491919429492650781084296080288020330875247574855906390404509845311187888602482142661083771230000178356724801659025002251056321173755782500071361114235931347064100961296562902176010402092225439511324625249209554560052627349307173707304259200397468217911136832133364420684914378754649851955359890480612161233059263522713390654506714661592991514955637304
c4 = 101923921400007092267790478161024103799892954880859052793422615329222813129835333442478632220182544724530301816393072530672763263645022408189547815923383906565611606888926097135400527299006862907781058931838804887994883095683814203452663467235776407572822082944022133476409878374663555627258035317631489173719410785629090255417861686081571376756906799938593870745471956936393066774907988124411318124604178920755698887086399177650502004883860844187365911953472980921213184639411672503691612418437276530896198002610276732906004741692286470538565288852344158830229580771834123582320782258698392853262935944858898937999647004599668060425461150846652642931397311468425476235056756761805933421643525566845928057238991458469113290576159465234243274971982913939709869951907061169493132309863852016682533998299893705859834844325876890511405664336001308600133946440998690503095156964687645597227368993047211862703399858777949126471093

y = calc(a,b,c,n)[2]
if isPrime(y):
    pass
else:
    y = gmpy2.next_prime(y)

tmp = hashlib.md5(str(y).encode()).hexdigest()
assert cc == pow(d,int(tmp,16),n)

print(long_to_bytes(pow(c3, inverse(52595,y-1), y)))


#LZSDS{laozishudaosan_814595285}



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'
"""

题目的加密流程是：

  • 先生成一个128bit的种子SEED，并初始化一个LCG类，记为R。LCG的state递推是：

    这很正常，不正常的是他的随机数生成方式：

    也就是生成的随机数是64bit的，其值等于当前state的高64位异或低64位。

  • 用R连续生成八个随机数，分别作为八个LFSR的mask，并给出后四个mask的值

  • 随机生成八个64bit的随机数，分别当作八个LFSR的初始state

  • 计算combine后的16000bit的LFSR输出作为密钥流，给出其与pad后的flag异或的值，combine函数是：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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

    这里题目的调用出问题了，他这个输入参数seed应该是初始128bit那个SEED，但是后面seed被更新成含8个seed的列表了，所以直接跑题目代码是跑不起来的

  • 给出pad后flag的最后100字节

我们要用如上信息还原flag。

首先，既然有combine的LFSR，就肯定要观察combine后的输出与每个LFSR之间输出的相关性，而要做到这样的观测首先需要把初始的SEED求出来。因此第一步是根据mask的后四个输出还原LCG的初始state。

而虽然这个LCG给出了a、b以及模数$2^{128}$，但是他给出的随机数是当前state的高64位与低64位的异或值，所以似乎并不简单。

我处理这一部分的办法比较奇怪，由于我们有高64位与低64位的异或值$x_i$，所以LCG的一个state可以写成：

把他代入到LCG的递推：

由于模数是$2^{128}$，所以可以改到$2^{64}$下得到：

上面的推导表明了两个事情：

  • state的低位可以在模$2^{64}$下递推
  • 如果有state低位的部分比特，可以用$x_i$获得state高位对应的部分比特

打个比方，我们现在有连续四个64bit的随机数$x_1,x_2,x_3,x_4$，他们对应四个128bit的状态$s_1,s_2,s_3,s_4$，如果我们爆破$s_1$的低10位，那么我们可以：

  • 在模$2^{64}$下递推得到$s_2,s_3,s_4$的低10位
  • 利用$x_1,x_2,x_3,x_4$得到$s_1,s_2,s_3,s_4$的对应高位，也就是64-74这一段比特

所以我们爆破t位的话，实际上可以获得8t位的信息，而剩下的比特可以当作HNP问题用LLL做一下。测试发现爆破17bit就可以LLL得到正确结果了，此时也就有了全部八个mask和初始SEED。

然后就是测试一下每个LFSR的输出和combine的输出的相关性，这一部分如下：

1
2
3
4
5
6
7
8
9
10
F = [0 for i in range(8)]
for i in product([0,1],repeat=8):
    x0,x1,x2,x3,x4,x5,x6,x7 = i
    xs = [x0,x1,x2,x3,x4,x5,x6,x7]
    bit = f(i, SEED)
    for j, xj in enumerate(xs):
        if(xj == bit):
            F[j] += 1
F = [float(i/256) for i in F]
print(F)
1
[0.5, 0.96875, 0.46875, 0.53125, 0.53125, 0.5, 0.5, 0.46875]

可以发现combine的输出与第二个LFSR的相关性特别强，达到了0.96875，这表示combine后的输出与LFSR2的输出有96.875%的概率是相等的。

而由于给出了flag的最后100字节，把这些比特与加密结果做异或后，就有最后800bit的combine输出流。我们可以从其中随机抽取一些比特，当抽取的这些比特恰好全部是LFSR2的输出的时候，就可以解线性方程还原LFSR2的初始种子了。

还原LFSR2的初始种子之后，因为他输出有96.875%的概率与combine后的输出相等，所以直接用他生成16000bit的输出流并与加密结果异或，就可以获得一个96.875%的比特均正确的pad后的flag串。而由于flag重复了25次，所以可以做统计确定每一个比特具体值。

exp：

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
from Crypto.Util.number import *
from tqdm import *
from itertools import *


###################################################################################### part1 recover LCG seed
mask = [14220691401612821285, 6144765487634854340, 15963296602901011718, 11570958398098493701]
l = 17
a = 47026247687942121848144207491837523525
b = 117397592171526113268558934119004209487
m = 2**128

for i in trange(2^l):
    x0l = i
    x1l = (a*x0l + b) % 2^l
    x2l = (a*x1l + b) % 2^l
    x3l = (a*x2l + b) % 2^l

    x0h = x0l ^^ mask[0]
    x1h = x1l ^^ mask[1]
    x2h = x2l ^^ mask[2]
    x3h = x3l ^^ mask[3]

    xl = [x0l, x1l, x2l, x3l]
    xh = [x0h, x1h, x2h, x3h]

    L = Matrix(ZZ, 12, 12)
    for j in range(8):
        L[j, j] = 1
    L[8, 8] = 2^(64-l)

    for j in range(3):
        cj = (a*2^64*xh[j] + a*xl[j]) + b - (2^64*xh[j+1] + xl[j+1])
        L[2*j, 9+j] = a*2^(64+l)
        L[2*j+1, 9+j] = a*2^l
        L[2*j+2, 9+j] = -2^(64+l)
        L[2*j+3, 9+j] = -2^l
        L[8, 9+j] = cj
    for j in range(3):
        L[-1-j,-1-j] = m
    
    L[:,-3:] *= m
    
    res = L.LLL()[4]

    XL = []
    for j in range(4):
        XL.append(abs(res[2*j+1])*2^l + xl[j])
    X = []
    for j in range(4):
        X.append((XL[j] ^^ mask[j]) * 2^64 + XL[j])
    
    if((a*X[0]+b) % m == X[1]):
        print(i, X)
        break

#5560 [92831300514842470778050206073212376504, 300627232761252052375847323708839963623, 163242678873498952260658145182439395474, 181626518661366839855132689767079904425]

X = [92831300514842470778050206073212376504, 300627232761252052375847323708839963623, 163242678873498952260658145182439395474, 181626518661366839855132689767079904425]

for i in range(4):
    x0 = (X[0] - b) * inverse(a, m) % m
    X = [x0] + X
SEED = (X[0] - b) * inverse(a, m) % m
print(SEED)

###################################################################################### part2 find correlation
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

F = [0 for i in range(8)]
for i in product([0,1],repeat=8):
    x0,x1,x2,x3,x4,x5,x6,x7 = i
    xs = [x0,x1,x2,x3,x4,x5,x6,x7]
    bit = f(i, SEED)
    for j, xj in enumerate(xs):
        if(xj == bit):
            F[j] += 1
F = [float(i/256) for i in F]
print(F)
print((F[1])^70)

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

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'

mask1 = (X[1] >> 64) ^^ (X[1] % 2**64)
###################################################################################### part3 recover LFSR seed1
stream = XOR(enc[-100:], hint)
stream = bin(bytes_to_long(stream))[2:].zfill(800)

L = Matrix(GF(2), 64, 64)
for i in range(63):
    L[i,i+1] = 1
for i in range(64):
    L[-1,i] = int(bin(mask1)[2:].zfill(64)[i])

FIND_l = 70
for i in trange(800-FIND_l):
    Left = Matrix(GF(2), 0, 64)
    Right = vector(GF(2), FIND_l)
    for j in range(FIND_l):
        Left = Left.stack((L^(8*1900+i+j+1))[-1])
        Right[j] = int(stream[i+j])

    try:
        SEED1 = Left.solve_right(Right)

        SEED1 = int("".join(list(map(str, SEED1))), 2)
        lfsr = LFSR(64, SEED1, mask1)
        output = 0
        for tt in range(2000 * 8):
            output <<= 1
            output += lfsr()
        flag = XOR(enc[:1000], long_to_bytes(output, 2000)[:1000])
        print(flag)
        break
    except:
        pass

###################################################################################### part4 statistics
cut = []
for i in range(25):
    cut.append(bin(bytes_to_long(flag[40*i:40*i+40]))[2:].zfill(320))

FLAG = ""
for i in range(320):
    compare = 0
    for j in range(25):
        if(cut[j][i] == "0"):
            compare += 1
        else:
            compare -= 1
    if(compare > 0):
        FLAG += "0"
    else:
        FLAG += "1"
FLAG = long_to_bytes(int(FLAG, 2))
print(FLAG)

import hashlib
assert hashlib.sha256(FLAG).hexdigest() == "1b6208006b19ceddc493a8fe1342c1c7bba1800b2a66b9da4cd819f8440f331f"


#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)]
"""

题目是个基于如下环的DH：

这样的DH肯定不是自己想的，一眼就是论文，所以主要任务在于搜到这样的DH的论文以及它的attack，最后搜到了这篇：

010.pdf (iacr.org)

这个题目就是这篇论文DH的实现，attack也很简单，照着写一遍就好了。

这个题目难度主要就在于搜论文，如果给出论文链接的话可能半小时都不需要，因为他的attack非常好写

有不少师傅问了我这种怎么搜，我其实也没啥门道，单对这个题来说我的搜索的过程是这样的，也许可以参考：

  • 组合各种词，比如crypto system, DH, key exchange, algebra, max, ring, matrix, entry-wise，在google上搜
  • 发现有个叫极大加代数的东西，max plus algebra，他的加法是max，乘法是加法，感觉很像
  • 顺着这个去加关键词搜，搜到一个基于max plus matrix algebra的key exchange
  • 但是他的元素还是数字，所以就继续搜，然后搜到个attack是关于max-T semirings啥的
  • max-T好像和题目表示对上了，然后发现他好像跟什么tropical algebra有关系，然后eprint上搜这个就找到了元素为pair的，一看就是这个系统以及attack

exp：

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5

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
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 = [(59900590664029081588751597115949479657291730864508459758763562295986654520462, 68320552779283515276240499643319977619901440989200422494626425642962224959344), (89698054093719949422762429034310548012077225043893131168337545047107450749496, 51479199576292239130066082976332639976062899059190752269878695108378488146679), (62218736027330266192570144338062026977337231944985836220559539768109014406831, 61214354159525954062640070826510640683451706120539795727362849462686622564693), (39805827211060089460158250456599968341463470401750393132792110953878249393569, 99103416592859133938491410425030428643259368893929508081326035011417306901272), (20922493031536155240718266043337868355652138270147183521353456319726724009058, 31430964180770964194690164159235543367301572045989047438624310779165592317271), (8959191626315499956806224120588498434035126032025230565571486221513367178374, 20067214390603904748675229391030612573671604470294660618614875919888930884780), (66048220278298402781571427858585494416782927078968140383635650050886579125833, 18175597939833315588572188448012546734970985103503074208793106634216584036818), (14432081053446841732493980558668616443341123394659689880088380115934894274635, 83557493069309650142798328460651561327339732728386566873314215777128303177667), (34511162979554971448736265846077014796752072453004958739933710734947541396694, 77364571020765493103034943723333754233327577188690990300833856668531817680505)]
Y = [(78533528545456238383274783853785358016819467733594018596743219756487720633746, 93976221569207299395273293543645974643384826524816615562497005292252667770601), (103766862112463335445955325531890205089005117500922857426350491681602103969000, 47323529900779960229909476477918095608118443655903527805237066535366116839149), (10190752330406968772077432866677538790850926811710030717810026338836331450472, 86375880251137784911361557173115785351126971447566503084261189167084220453288), (13780196681979042044702022951434986810164135209191561823725939514845972817610, 55170363535880083300862447306063246181282182639154190917220001586753468629546), (436029875577652990270691130860178026240806299188121622633421834221330373636, 110804259765120571425960874898903708961853698355143533817410855395636486531982), (6397911849400997286703265695504239070876241554571709807303889197285939312681, 17360696619752702589750097897661044951586752285334140009669640422948343241568), (58041034583523761593801980039841494595215125402194920275127841961766699686394, 54766044749028865088458074550257196739016298676359665986238379481142351990626), (77530103367856397256662107816221151235947660504364282548276904992741575506849, 63854892725980295947169956482257581700294549443273322483764382131671051522332), (47497441477952935509240863594022229337695084880724507207404445061842628668952, 56713418154978297086219120150091406983389112617302018465360827172758909144570)]
A_p = [(40547797283575399311345964287271714617688023231464400205040285835460999315476731205228816544079212468645004319629302959473711018684702750872290449940972698, 40547797283575399311345964287271714617688023231464400205040285835460999315476698934497596879746169782553959201278357925243089469169482083236651301175074462), (40547797283575399311345964287271714617688023231464400205040285835460999315476786839125045784567337567072597160092083530989427008027602941726099332958875134, 40547797283575399311345964287271714617688023231464400205040285835460999315476750004263963436463523550691311785519855896914393402679802307379634177780083118), (40547797283575399311345964287271714617688023231464400205040285835460999315476706776849302561292697869327278531705692232746803441653969601206061897674894004, 40547797283575399311345964287271714617688023231464400205040285835460999315476682432777130064993198309463393760622192553532626436203592834759900982411655833), (40547797283575399311345964287271714617688023231464400205040285835460999315476733573193663026027748192077028026006061293036706834385224678998540725414561492, 40547797283575399311345964287271714617688023231464400205040285835460999315476709827727502107645065946715613329058910783689656325976029039752886304715182546), (40547797283575399311345964287271714617688023231464400205040285835460999315476789207089892266515873290504620866468841864552422823728124869852349608432463928, 40547797283575399311345964287271714617688023231464400205040285835460999315476765461623731348133191045143206169521691355205372315318929230606695187733084982), (40547797283575399311345964287271714617688023231464400205040285835460999315476709144814149043241233592759302238082450566309799257354491529332312173148482798, 40547797283575399311345964287271714617688023231464400205040285835460999315476685399347988124858551347397887541135300056962748748945295890086657752449103852), (40547797283575399311345964287271714617688023231464400205040285835460999315476692793936572469446889818453385542291673187750773962605187059907381322027502633, 40547797283575399311345964287271714617688023231464400205040285835460999315476725064667792133779932504544430660642618221981395512120407727543020470793400869), (40547797283575399311345964287271714617688023231464400205040285835460999315476746626235376326170902419020010827637210112057551060804659922530107892689013547, 40547797283575399311345964287271714617688023231464400205040285835460999315476780698564021374268057602972023501105398793497111501463307918396829353811303305), (40547797283575399311345964287271714617688023231464400205040285835460999315476676292216105654693918345362820101635507816040310929639297811430631003264084004, 40547797283575399311345964287271714617688023231464400205040285835460999315476700636288278150993417905226704872719007495254487935089674577876791918527322175)]
B_q = [(44956584717324859629636950162153871886560739437959809729281253007078755840271381302732123072890496216398568268656559622476770594999251404506445788064037538, 44956584717324859629636950162153871886560739437959809729281253007078755840271413573463342737223538902489613387007504656707392144514472072142084936829935774), (44956584717324859629636950162153871886560739437959809729281253007078755840271432372498489629607849984535920852898057594148074528509571628649428664669046194, 44956584717324859629636950162153871886560739437959809729281253007078755840271469207359571977711664000917206227470285228223108133857372262995893819847838210), (44956584717324859629636950162153871886560739437959809729281253007078755840271364801011656258137524743308002828000394250766307562033362156029695469300618909, 44956584717324859629636950162153871886560739437959809729281253007078755840271389145083828754437024303171887599083893929980484567483738922475856384563857080), (44956584717324859629636950162153871886560739437959809729281253007078755840271392195962028300789392380560222396437112480923337451805798361022680791604145622, 44956584717324859629636950162153871886560739437959809729281253007078755840271415941428189219172074625921637093384262990270387960214994000268335212303524568), (44956584717324859629636950162153871886560739437959809729281253007078755840271447829858257541277517478987815236899893052439053441148698551876489674622048058, 44956584717324859629636950162153871886560739437959809729281253007078755840271471575324418459660199724349229933847043561786103949557894191122144095321427004), (44956584717324859629636950162153871886560739437959809729281253007078755840271367767582514318002877781242496608513501754196429874775065211356452239338066928, 44956584717324859629636950162153871886560739437959809729281253007078755840271391513048675236385560026603911305460652263543480383184260850602106660037445874), (44956584717324859629636950162153871886560739437959809729281253007078755840271407432902318326924258938389039728020819919215076637950177048812814957682363945, 44956584717324859629636950162153871886560739437959809729281253007078755840271375162171098662591216252297994609669874884984455088434956381177175808916465709), (44956584717324859629636950162153871886560739437959809729281253007078755840271463066798547567412384036816632568483600490730792627293077239666623840700266381, 44956584717324859629636950162153871886560739437959809729281253007078755840271428994469902519315228852864619895015411809291232186634429243799902379577976623), (44956584717324859629636950162153871886560739437959809729281253007078755840271383004522804344137744339071313940097209192488169060919443899146586405416285251, 44956584717324859629636950162153871886560739437959809729281253007078755840271358660450631847838244779207429169013709513273992055469067132700425490153047080)]

#################################################################################### part1 handle data
T = algebraring()
X = Matrix(T, n, n, [T(*i) for i in X])
Y = Matrix(T, n, n, [T(*i) for i in Y])
A_p = Matrix(T, n, n, [T(*i) for i in A_p])
B_q = Matrix(T, n, n, [T(*i) for i in B_q])

#################################################################################### part2 attack
class algebra1(CommutativeRingElement):
    def __init__(self, parent, a):
        CommutativeRingElement.__init__(self, parent)
        self.a = a

    def __add__(self, other):
        return algebra1(
            self.parent(), max(self.a, other.a)
        )
    
    def __sub__(self, other):
        return algebra1(
            self.parent(), self.a - other.a
        )

    def __mul__(self, other):
        return algebra1(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 __repr__(self):
        return f"T1({self.a})"

    def _mul_(self, other):
        return self.__mul__(other)
    
class algebraring1(UniqueRepresentation, Parent):
    def __init__(self):
        Parent.__init__(self, category=CommutativeRings())

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

    def __repr__(self):
        return "algebraring1"

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

def convert(M):
    M_ = Matrix(2*n, 2*n).change_ring(T1)
    for i in range(n):
        for j in range(n):
            M_[2*i,2*j] = T1(ZZ(M[i,j].a1))
            M_[2*i,2*j+1] = T1(ZZ(M[i,j].a2))
            M_[2*i+1,2*j] = T1(ZZ(M[i,j].a2))
            M_[2*i+1,2*j+1] = T1(ZZ(M[i,j].a1))
    return M_

def shift1(matrix, x):
    n = len(matrix[0, :].list())
    ring = matrix.base_ring()
    new_matrix = [
        [ring(T1(matrix[i, j].a) * x) for j in range(n)] for i in range(n)
    ]
    return Matrix(ring, new_matrix)

def convert_inv(M_):
    M = Matrix(T, n, n)
    for i in range(n):
        for j in range(n):
            M[i,j] = T(ZZ(M_[2*i,2*j].a), ZZ(M_[2*i,2*j+1].a))
    return M

def compare_same(M):
    for i in range(10):
        x1,y1,x2,y2 = [randint(0,n) for _ in range(4)]
        if(C[x1,y1] != C[x2,y2]):
            return False
    return True

T1 = algebraring1()
X_ = convert(X)
Y_ = convert(Y)
A_p_ = convert(A_p)
B_q_ = convert(B_q)

for k1 in range(10):
    for l1 in range(10):
        C = A_p_ - X_^k1*Y_^l1
        if(compare_same(C)):
            tau = C[0,0]

            key = convert_inv(shift1(X_^k1*B_q_*Y_^l1, tau))
            key = md5(str(key).encode()).digest()
            aes = AES.new(key=key, mode=AES.MODE_ECB)
            flag = aes.decrypt(enc)
            print(flag)


#LZSDS{dbc6bad4-7e16-4883-b7a1-682333a18c7c}