# Trendy windy trigonity

**Source**

from Crypto.Util.number import bytes_to_long
flag = b'CSCTF{fake_flag}'
print(len(flag)) 
R = RealField(1000)
a,b = bytes_to_long(flag[:len(flag)//2]),bytes_to_long(flag[len(flag)//2:])
x   = R(0.75872961153339387563860550178464795474547887323678173252494265684893323654606628651427151866818730100357590296863274236719073684620030717141521941211167282170567424114270941542016135979438271439047194028943997508126389603529160316379547558098144713802870753946485296790294770557302303874143106908193100)

enc = a*cos(x)+b*sin(x) 
print(enc)

#38
#enc = 2.78332652222000091147933689155414792020338527644698903976732528036823470890155538913578083110732846416012108159157421703264608723649277363079905992717518852564589901390988865009495918051490722972227485851595410047572144567706501150041757189923387228097603575500648300998275877439215112961273516978501e45

## Phân tích

Ta có phương trình : $flag_1*a + flag_2*b = enc$ , trong đó : $a = cos(x) , b = sin(x)$
Thì đây đơn giản là knapsnack problem đơn giản , nhưng do $a,b,enc$ không phải số thực nên ta chưa áp dụng LLL được . Ta đơn giản chỉ cần nhân bội số đủ để nó thành số nguyên thôi . Chuỗi thập phân đằng sau có độ dài là 300 nên ta nhân `10^300` vào

## Code

from Crypto.Util.number import *
def Low_density_Subset_Sum_Problems(multi,result) :
    n = len(multi)
    N = int(sqrt((n+1)//4)) + 1
    M = Matrix(QQ , n + 1 , n + 1)
    
    
    for i in range(n) :
        M[i,i] = 1
        M[i,-1] = N*multi[i]
        M[-1,i] = 1/2
    M[-1,-1] = -N*result 
    
    
    M = M.LLL()[0]
    M = [int(i-1/2) for i in M]
    return M[:-1]
R = RealField(1000)

x   = R(0.75872961153339387563860550178464795474547887323678173252494265684893323654606628651427151866818730100357590296863274236719073684620030717141521941211167282170567424114270941542016135979438271439047194028943997508126389603529160316379547558098144713802870753946485296790294770557302303874143106908193100)
enc = 2.78332652222000091147933689155414792020338527644698903976732528036823470890155538913578083110732846416012108159157421703264608723649277363079905992717518852564589901390988865009495918051490722972227485851595410047572144567706501150041757189923387228097603575500648300998275877439215112961273516978501e45

a = cos(x)
b = sin(x)

s = Low_density_Subset_Sum_Problems([int(a*10^300),int(b*10^300)],int(enc*10^300))
print(long_to_bytes(s[0]) + long_to_bytes(s[1]))
 

Flag : ```CSCTF{Trigo_453_Tr3ndy_FuN_Th35e_D4Y5}```
# Super-fnv

**Source**

from pwn import xor
from random import randint
from hashlib import sha256
from FLAG import flag

cc = [randint(-2**67, 2**67) for _ in range(9)]
key = sha256("".join(str(i) for i in cc).encode()).digest()
enc = xor(key, flag)

def superfnv():
    x = 2093485720398457109348571098457098347250982735
    k = 1023847102938470123847102938470198347092184702
    for c in cc:
        x = k * (x + c)
    return x % 2**600

print(f"{enc.hex() = }")
print(f"{superfnv() = }")

# enc.hex() = '4ba8d3d47b0d72c05004ffd937e85408149e13d13629cd00d5bf6f4cb62cf4ca399ea9e20e4227935c08f3d567bc00091f9b15d53e7bca549a'
# superfnv() = 2957389613700331996448340985096297715468636843830320883588385773066604991028024933733915453111620652760300119808279193798449958850518105887385562556980710950886428083819728334367280

## Phân tích

Ta có hàm `super-fnv` sẽ thực hiện phép tính : $x = k*(x+c) \ mod \ 2^{600}$ lặp 9 lần , sau 9 lần lặp thì `x` sẽ có dạng :
$x \equiv k^9*x_0 + k^9*c_1 + k^8*c_2 + ... + k^0*c9 \mod \ 2^{600}$
Với $x_0$ là $x$ ban đầu của mình `2093485720398457109348571098457098347250982735`

Thì giờ ta sẽ viết lại :
$x - k^9*x_0 \equiv k^9*c_1 + k^8*c_2 + ... + k^0*c9 \mod \ 2^{600}$

Giờ nó nhìn giống `Modular Subset Sum Problem` nhỉ , ừ thì nó đúng là thế nhưng vấn đề của ta ở đây là nó quá nhiều nghiệm nên không tìm chính xác được nghiệm mà ta cần .

Mình cũng dùng 1 số tool khác để có thể tìm nhiều nghiệm solve linear như `https://github.com/protozeit/toolbase/blob/master/crypto/solvelinmod.py` mà không được :<<

Rồi sau khi anh @Kindoo solve thì mình mới dùng tool `Wolfram` , lúc trước đọc 7749 cái hướng dẫn mà không hiểu cách code của nó =((

Cách giải thì vẫn tương tự solve linear mod như link ở trên thôi , nhập phương trình và bounds của của ẩn , và nó sẽ tìm hết tất cả các nghiệm cho mình :smiley_cat:

## Code

xx = {k^(n - i) for i = 0 to (n - 1)};
target = 2957389613700331996448340985096297715468636843830320883588385773066604991028024933733915453111620652760300119808279193798449958850518105887385562556980710950886428083819728334367280;
LB = -2^67;
UB = 2^67;
M = 2^600;
x = 2093485720398457109348571098457098347250982735;
k = 1023847102938470123847102938470198347092184702;

eq = xx.x + k*M == target;

sol = FindInstance[
  eq && And @@ (Thread[x[
  Append[x, k],
  Integers,
  1000
];


cc = x /. sol[[1]];
key = Hash[cc, "SHA256"];


ct = FromHex["4ba8d3d47b0d72c05004ffd937e85408149e13d13629cd00d5bf6f4cb62cf4ca399ea9e20e4227935c08f3d567bc00091f9b15d53e7bca549a"];


flag = BitXor[key, ct];


If[StringContainsQ[flag, "CSCTF"], Print[flag]]

Flag : ```CSCTF{478845edc037270f072a5e829b1e9b34ad448950718243847c}```

# Connorsmith
**Source**

m = int.from_bytes(b'CSCTF{redacted}')
p = random_prime(2**1024)
q = random_prime(2**1024)
N = p*q
d = randint(0, int(N**0.35))
e = pow(d, -1, (p-1)*(q-1))

print(f'{N = }')
print(f'{e = }')
print(f'c = {pow(m, e, N)}')
print(f'hint = {(p+q) >> 795}')

"""
N = 7552253013225223212686972759229408890943243937848116869511428282592494711559240135372705736006054353083281103140787662239958191241833157109597880624454796412006762881501916845155158694626704629051045217266597685547634722763704638532067409306181328833329683262904207364205190648604464680961179156366009048508124744257064547090561236984730817200175311749708243086463240602718911105727107075971987228340827791295829216059926076767577606528647738447725195880791137450082195604212374273765390335921438605358227547423468794396280894150559661664635540689602987474623120205743645087417873312711804245504568677508120251077973
e = 3972273176912267799970180147678020025192175195982968793722693097132970664724388722714705209022371322943558028173459714967997171817396680330435643595109433373306392229639747130134793710239081601404067602930871254806754684103349829634489509031907387929080189489106215966862642406152181674399593026117258657690036458955106821789654735855538375273851668820461621159458690509295524433242439365251850800232909323376356116251835554606066609685882803255427299046970093232995420925951786433206910901590576814359503385919307570360242528454529766855342865079257244016304989185569117193284115242278439808082079787893597831292429
c = 6722063431743120124281037577917473736384734002344400102535470664988199976365033546621632487383386053044468700113542626459908567596300577088705896140930724832695917664482501591801075560437336915520962349830960551339852803481367045861684404716913927870231244602348980596739084252620702852351036834534769613031735817640709051052713694452907186969900542466747407949270228341375666775282809021111998328175103742416108902755346724742467339317044645243210574003890806923017769148711785248795287760426567277473640239499920974270994457112678786022613046685998793486144172215215581287541508145268729387185453679039441575292812
hint = 891237814844096809623936988168241703768093224718029580247856301709140
"""

## Phân tích
Đập vào mắt ta trong bài này thì là nó xác định $d$ trước với `d = randint(0, int(N**0.35))` , với mấy số d được xác định bởi n kiểu này thì ta thường nghĩ đến các cách tấn công như : `Wiener Attack` hay `Boneh-durfee`.

Nhưng cả 2 cách này đều không khả quan lắm do để thực hiện nó thì giới hạn của d để thực hiện 2 cách trên là $d < N^{0.292}$ , ở đây là `0.35`.

Lúc này thì ta sẽ phải khai thác đến dữ kiện hint kia .

Thì ta có :
$e*d = 1 + k*phi = 1 + k*(N+1- (p+q))$

$1 + k*(N+1 - (p+q)) \equiv 0 \ mod \ e$
$1 + k*(N+1 - (hint << 795 + x)) \equiv 0 \mod \ e$

Thì giờ đây ta chỉ cần giải phương trình này bằng coppersmith với 2 ẩn là $k$ và $x$ trong modulo $e$.

import sys
from coppersmith_multivariate_heuristic import coppersmith_multivariate_heuristic
from Crypto.Util.number import long_to_bytes
from sage.all import *

N = 7552253013225223212686972759229408890943243937848116869511428282592494711559240135372705736006054353083281103140787662239958191241833157109597880624454796412006762881501916845155158694626704629051045217266597685547634722763704638532067409306181328833329683262904207364205190648604464680961179156366009048508124744257064547090561236984730817200175311749708243086463240602718911105727107075971987228340827791295829216059926076767577606528647738447725195880791137450082195604212374273765390335921438605358227547423468794396280894150559661664635540689602987474623120205743645087417873312711804245504568677508120251077973
e = 3972273176912267799970180147678020025192175195982968793722693097132970664724388722714705209022371322943558028173459714967997171817396680330435643595109433373306392229639747130134793710239081601404067602930871254806754684103349829634489509031907387929080189489106215966862642406152181674399593026117258657690036458955106821789654735855538375273851668820461621159458690509295524433242439365251850800232909323376356116251835554606066609685882803255427299046970093232995420925951786433206910901590576814359503385919307570360242528454529766855342865079257244016304989185569117193284115242278439808082079787893597831292429
c = 6722063431743120124281037577917473736384734002344400102535470664988199976365033546621632487383386053044468700113542626459908567596300577088705896140930724832695917664482501591801075560437336915520962349830960551339852803481367045861684404716913927870231244602348980596739084252620702852351036834534769613031735817640709051052713694452907186969900542466747407949270228341375666775282809021111998328175103742416108902755346724742467339317044645243210574003890806923017769148711785248795287760426567277473640239499920974270994457112678786022613046685998793486144172215215581287541508145268729387185453679039441575292812
hint = 891237814844096809623936988168241703768093224718029580247856301709140
hint = hint << 795

PR.<x,y> = PolynomialRing(Zmod(e))
f = y*((N+1) - (x + hint)) + 1

tmp = coppersmith_multivariate_heuristic(f, [2**795, 2**711], beta = 1)[0]
print(tmp)

Chaỵ 3p là ra , nhưng nhanh hơn rất nhiều so với hàm mình dùng trước r , treo máy có khi phải cả đêm :sleeping: . Kiona vô địch :yum:

[177751836399556739219298619379109781012477889949806793333033426536103775450599682453136337130332392835049844717992739559363652650443931602863383863338842680216961343326620972648633880853391604562066337471832137216804201275790942633787153974, 896422735159838833493902020285108669832628148233746995493909503761254449745112601249854782322065199197766396901471392300202416434320465826293530430588281205658179368020642743951305235075064393760621843207154080912]

Sau khi có `tmp` thì ta thấy $tmp[0] + (hint << 795) = p + q$ -> $phi = N + 1 - (p+q)$ . Còn lại thì decrypt rsa thôi .

a = tmp[0]
phi = N + 1 - (hint+a)
d = pow(e,-1,phi)
print(long_to_bytes(pow(c,d,N)))

Flag : ```CSCTF{37c37f30fc67f98f376a1c30b25b3969}```

# Two Many Hints

Bài này chắc là bài mình tiếc nhất vì không giải được trong giải vì 1 lỗi rất ngớ ngẩn :disappointed:

**Source**

from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad,unpad

from secret import flag

# PARAMETERS
q       = 3329
k       = 2 
sigma   = 2.5
n       = 256
K = CyclotomicField(n,'z') 
OK      = K.OK()
OKq= OK.quotient(q,'y')

A = matrix(K, k,k, [K(random_vector(ZZ,n//2,x=-q//2,y=q//2).list()) for _ in k*k*"_"]).lift_centered()
s = matrix(K, [K(random_vector(ZZ,n//2,sigma,distribution="gaussian").list()) for __ in k*"_"] )
e = matrix(K, [K(random_vector(ZZ,n//2,sigma,distribution="gaussian").list()) for __ in k*"_"] )
b = (s*A +e ).change_ring(OKq)  



H = matrix(k,k,[ OK(list(random_vector(ZZ,n))) for _ in k*k*"_"] )
l = s*H                                                # I won't give you this 3:)
h = floor(.25*n/2)                                                 
l2 = matrix([l[0,0] , OK(l[0,1].list()[:-h]) ]) 

key = sha256(str(s).encode()).digest()[:16]
iv  = sha256(str(e).encode()).digest()[:16]

cipher= AES.new(key,AES.MODE_CBC,iv=iv)

enc = cipher.encrypt(pad(flag,16))

#Printing 
print(f"A  = {A.coefficients()}")
print(f"b  = {b.coefficients()}")
print(f"H  = {H.coefficients()}")
print(f"l2 = {l2.coefficients()}")
print("enc = ", enc.hex())

**Output**

A  = [-1052*z^127 + 566*z^126 + 1032*z^125 + 1260*z^124 + 1379*z^123 + 395*z^122 - 929*z^121 - 1350*z^120 + 1535*z^119 + 72*z^118 + 262*z^117 - 669*z^116 + 1141*z^115 + 1076*z^114 - 200*z^113 + 1453*z^112 - 1492*z^111 - 1165*z^110 - 599*z^109 + 990*z^108 - 207*z^107 + 1014*z^106 + 1230*z^105 + 125*z^104 + 369*z^103 - 1073*z^102 - 741*z^101 + 1349*z^100 + 459*z^99 + 51*z^98 - 616*z^97 - 1491*z^96 - 310*z^95 - 975*z^94 + 580*z^93 - 1371*z^92 + 291*z^91 - 904*z^90 - 989*z^89 - 1007*z^88 - 1525*z^87 + 1548*z^86 + 885*z^85 - 671*z^84 - 406*z^83 - 1164*z^82 + 1600*z^81 + 438*z^80 + 1079*z^79 - 15*z^78 + 1027*z^77 + 1263*z^76 + 1307*z^75 + 1250*z^74 - 1347*z^73 - 1003*z^72 - 1444*z^71 - 1174*z^70 + 1117*z^69 + 159*z^68 - 1555*z^67 + 1035*z^66 - 1167*z^65 + 326*z^64 - 362*z^63 - 1377*z^62 + 152*z^61 + 934*z^60 + 1120*z^59 - 155*z^58 - 797*z^57 - 379*z^56 + 501*z^55 - 958*z^54 - 577*z^53 - 836*z^52 + 663*z^51 - 550*z^50 - 442*z^49 + 1271*z^48 + 1200*z^47 - 454*z^46 + 1164*z^45 - 505*z^44 - 1571*z^43 + 1480*z^42 + 113*z^41 - 36*z^40 + 821*z^39 - 1456*z^38 + 1475*z^37 + 325*z^36 + 525*z^35 - 481*z^34 + 1586*z^33 - 139*z^32 - 950*z^31 - 277*z^30 - 389*z^29 + 653*z^28 - 1526*z^27 - 645*z^26 + 438*z^25 - 904*z^24 - 1272*z^23 - 28*z^22 + 848*z^21 - 206*z^20 - 918*z^19 + 1311*z^18 - 1544*z^17 - 760*z^16 - 755*z^15 + 837*z^14 + 1258*z^13 + 659*z^12 + 405*z^11 + 1208*z^10 - 1168*z^9 - 422*z^8 + 356*z^7 - 1398*z^6 - 1632*z^5 + 862*z^4 - 166*z^3 + 391*z^2 + 1229*z - 369, -374*z^127 - 587*z^126 - 509*z^125 + 570*z^124 - 728*z^123 + 999*z^122 + 1375*z^121 - 103*z^120 + 1335*z^119 - 600*z^118 - 91*z^117 + 292*z^116 - 51*z^115 + 140*z^114 - 30*z^113 - 1085*z^112 + 1125*z^111 - 780*z^110 - 1305*z^109 - 715*z^108 - 1403*z^107 - 518*z^106 + 11*z^105 - 936*z^104 + 544*z^103 - 1190*z^102 + 1407*z^101 + 1079*z^100 + 325*z^99 + 278*z^98 + 788*z^97 - 236*z^96 - 1304*z^95 - 1385*z^94 + 1484*z^93 - 771*z^92 - 15*z^91 - 195*z^90 - 799*z^89 - 772*z^88 - 1269*z^87 - 716*z^86 + 1201*z^85 - 199*z^84 + 900*z^83 - 593*z^82 - 1512*z^81 - 1019*z^80 + 1379*z^79 - 753*z^78 + 892*z^77 + 1000*z^76 - 848*z^75 + 41*z^74 + 611*z^73 + 456*z^72 + 1624*z^71 + 262*z^70 + 1112*z^69 - 1527*z^68 - 438*z^67 + 902*z^66 - 1338*z^65 - 1350*z^64 - 1014*z^63 + 1085*z^62 + 511*z^61 - 1236*z^60 + 887*z^59 + 784*z^58 - 966*z^57 - 1174*z^56 - 1236*z^55 + 1206*z^54 - 597*z^53 - 1004*z^52 - 941*z^51 - 1251*z^50 - 543*z^49 - 529*z^48 - 443*z^47 + 796*z^46 - 814*z^45 - 1347*z^44 + 1469*z^43 + 406*z^42 - 551*z^41 + 1408*z^40 + 1605*z^39 + 1481*z^38 + 829*z^37 - 917*z^36 - 1527*z^35 - 1469*z^34 - 1533*z^33 + 143*z^32 - 1221*z^31 - 887*z^30 - 1653*z^29 + 315*z^28 - 125*z^27 - 1373*z^26 + 1026*z^25 - 234*z^24 + 1380*z^23 - 1019*z^22 + 817*z^21 + 716*z^20 - 53*z^19 - 215*z^18 + 1355*z^17 - 184*z^16 - 1364*z^15 + 1269*z^14 - 1402*z^13 - 771*z^12 + 672*z^11 + 66*z^10 - 846*z^9 - 1208*z^8 + 563*z^7 - 1457*z^6 + 259*z^5 + 1486*z^4 - 556*z^3 + 622*z^2 - 164*z + 550, 59*z^127 - 782*z^126 - 80*z^125 - 426*z^124 - 1524*z^123 + 138*z^122 - 646*z^121 + 192*z^120 + 1125*z^119 + 845*z^118 + 948*z^117 - 503*z^116 + 721*z^115 + 158*z^114 + 1543*z^113 - 1638*z^112 - 197*z^111 + 1577*z^110 + 1585*z^109 + 1389*z^108 - 106*z^107 + 1612*z^106 - 289*z^105 - 365*z^104 + 101*z^103 + 354*z^102 - 1037*z^101 + 1388*z^100 - 592*z^99 + 181*z^98 + 454*z^97 - 702*z^96 + 501*z^95 + 904*z^94 - 133*z^93 - 1644*z^92 + 1446*z^91 + 917*z^90 + 1520*z^89 + 1620*z^88 + 971*z^87 + 1398*z^86 - 1386*z^85 + 1130*z^84 + 862*z^83 + 88*z^82 - 1083*z^81 + 782*z^80 - 1138*z^79 + 845*z^78 - 1318*z^77 - 769*z^76 - 226*z^75 + 311*z^74 - 536*z^73 + 287*z^72 + 47*z^71 + 547*z^70 + 249*z^69 - 1470*z^68 + 683*z^67 - 152*z^66 - 1430*z^65 - 147*z^64 + 388*z^63 + 1145*z^62 + 99*z^61 - 646*z^60 - 942*z^59 + 1472*z^58 + 225*z^57 - 412*z^56 - 243*z^55 + 1642*z^54 - 51*z^53 + 1028*z^52 - 1476*z^51 + 1375*z^50 + 938*z^49 - 1304*z^48 - 120*z^47 - 123*z^46 - 1479*z^45 - 1338*z^44 + 257*z^43 + 1562*z^42 - 1413*z^41 - 730*z^40 - 1024*z^39 - 1134*z^38 + 963*z^37 + 142*z^36 - 147*z^35 - 1292*z^34 - 1295*z^33 - 387*z^32 + 1447*z^31 + 1182*z^30 + 10*z^29 - 1656*z^28 - 110*z^27 - 592*z^26 - 1454*z^25 - 328*z^24 - 1001*z^23 - 751*z^22 - 127*z^21 - 467*z^20 - 583*z^19 - 909*z^18 - 122*z^17 - 177*z^16 - 1503*z^15 + 1409*z^14 - 1343*z^13 - 715*z^12 + 1261*z^11 + 1100*z^10 - 929*z^9 - 1314*z^8 + 1207*z^7 + 1474*z^6 + 590*z^5 - 1302*z^4 - 1233*z^3 + 862*z^2 + 354*z - 1358, 511*z^127 + 892*z^126 + 786*z^125 + 1358*z^124 + 301*z^123 + 620*z^122 - 481*z^121 + 1353*z^120 + 408*z^119 - 732*z^118 + 879*z^117 - 779*z^116 + 974*z^115 - 1417*z^114 - 255*z^113 - 1183*z^112 - 593*z^111 - 271*z^110 - 1592*z^109 + 1552*z^108 + 1482*z^107 - 1574*z^106 + 77*z^105 + 219*z^104 + 1193*z^103 + 1598*z^102 + 40*z^101 - 677*z^100 + 978*z^99 - 900*z^98 + 1323*z^97 - 176*z^96 - 1091*z^95 - 299*z^94 + 616*z^93 - 1060*z^92 + 671*z^91 + 786*z^90 + 1123*z^89 + 1547*z^88 + 1214*z^87 - 1076*z^86 - 1463*z^85 - 1201*z^84 - 488*z^83 - 584*z^82 - 530*z^81 + 145*z^80 + 327*z^79 - 964*z^78 + 868*z^77 - 1112*z^76 - 939*z^75 - 955*z^74 + 851*z^73 - 1030*z^72 - 992*z^71 - 1560*z^70 + 488*z^69 - 372*z^68 - 157*z^67 + 382*z^66 - 364*z^65 + 1348*z^64 - 417*z^63 + 262*z^62 + 991*z^61 - 1471*z^60 + 803*z^59 - 1000*z^58 + 1616*z^57 + 1485*z^56 - 963*z^55 - 1020*z^54 + 1381*z^53 - 1048*z^52 + 130*z^51 + 1528*z^50 + 986*z^49 + 1239*z^48 - 1454*z^47 + 1095*z^46 - 639*z^45 - 190*z^44 - 689*z^43 - 1351*z^42 - 1242*z^41 - 550*z^40 - 1180*z^39 - 761*z^38 - 1067*z^37 - 1565*z^36 + 404*z^35 - 821*z^34 + 1449*z^33 - 1377*z^32 + 507*z^31 - 691*z^30 + 604*z^29 - 1649*z^28 + 350*z^27 - 1568*z^26 - 872*z^25 - 944*z^24 - 242*z^23 + 84*z^22 + 240*z^21 + 646*z^20 - 1513*z^19 + 40*z^18 + 266*z^17 - 1232*z^16 - 56*z^15 + 800*z^14 + 1335*z^13 + 1472*z^12 - 1042*z^11 + 636*z^10 - 1620*z^9 + 780*z^8 - 158*z^7 + 818*z^6 - 911*z^5 - 498*z^4 - 1380*z^3 - 1287*z^2 + 820*z - 335]
b  = [-395*z^127 - 347*z^126 + 654*z^125 - 1469*z^124 + 318*z^123 + 325*z^122 - 20*z^121 - 516*z^120 + 159*z^119 + 102*z^118 + 825*z^117 - 943*z^116 - 767*z^115 - 1662*z^114 - 1556*z^113 + 1638*z^112 - 103*z^111 + 1408*z^110 + 1047*z^109 + 169*z^108 - 1205*z^107 - 1025*z^106 - 128*z^105 - 391*z^104 + 1653*z^103 + 441*z^102 - 1430*z^101 + 187*z^100 - 417*z^99 + 468*z^98 + 635*z^97 + 816*z^96 - 1590*z^95 - 822*z^94 - 626*z^93 + 73*z^92 - 206*z^91 + 573*z^90 + 81*z^89 - 620*z^88 - 764*z^87 - 831*z^86 + 1356*z^85 - 106*z^84 - 950*z^83 + 664*z^82 + 453*z^81 - 1663*z^80 - 1410*z^79 + 1243*z^78 + 213*z^77 - 55*z^76 + 814*z^75 - 81*z^74 - 1272*z^73 + 1513*z^72 + 687*z^71 + 519*z^70 + 55*z^69 + 1540*z^68 - 1234*z^67 - 1046*z^66 - 1049*z^65 - 1479*z^64 - 302*z^63 - 496*z^62 + 1586*z^61 - 825*z^60 - 123*z^59 - 1020*z^58 - 1416*z^57 + 623*z^56 - 615*z^55 + 760*z^54 + 1155*z^53 - 1143*z^52 + 1037*z^51 - 478*z^50 - 531*z^49 + 1380*z^48 + 1111*z^47 - 258*z^46 + 884*z^45 - 1491*z^44 + 1132*z^43 - 1184*z^42 - 1397*z^41 + 238*z^40 - 128*z^39 + 642*z^38 + 763*z^37 + 927*z^36 + 1121*z^35 - 441*z^34 + 22*z^33 + 1167*z^32 + 1512*z^31 - 402*z^30 + 1261*z^29 + 750*z^28 - 1469*z^27 - 931*z^26 + 616*z^25 + 229*z^24 + 517*z^23 + 145*z^22 - 112*z^21 + 493*z^20 - 981*z^19 + 796*z^18 - 1196*z^17 + 702*z^16 + 1423*z^15 + 978*z^14 + 1312*z^13 - 183*z^12 - 386*z^11 + 585*z^10 + 1473*z^9 - 1137*z^8 + 918*z^7 + 1539*z^6 - 193*z^5 + 861*z^4 - 315*z^3 - 529*z^2 + 866*z + 1234, -1263*z^127 + 785*z^126 - 515*z^125 - 1149*z^124 - 1165*z^123 - 1111*z^122 - 628*z^121 + 962*z^120 - 1277*z^119 + 1546*z^118 - 13*z^117 + 1237*z^116 + 1397*z^115 - 1056*z^114 - 172*z^113 - 1048*z^112 - 782*z^111 + 430*z^110 - 881*z^109 + 566*z^108 + 67*z^107 - 29*z^106 - 889*z^105 + 1233*z^104 - 1208*z^103 + 497*z^102 - 416*z^101 + 653*z^100 + 1639*z^99 + 516*z^98 - 65*z^97 - 1068*z^96 - 799*z^95 + 324*z^94 + 302*z^93 + 382*z^92 - 123*z^91 - 158*z^90 + 279*z^89 - 896*z^88 + 329*z^87 - 696*z^86 + 1240*z^85 + 315*z^84 + 1113*z^83 - 741*z^82 + 178*z^81 + 186*z^80 - 1171*z^79 + 1126*z^78 - 908*z^77 - 1643*z^76 + 193*z^75 + 1372*z^74 - 793*z^73 + 1544*z^72 - 1330*z^71 + 295*z^70 + 1172*z^69 - 1159*z^68 + 696*z^67 - 718*z^66 - 1587*z^65 + 1007*z^64 - 323*z^63 - 258*z^62 - 125*z^61 - 704*z^60 - 375*z^59 + 1362*z^58 + 97*z^57 - 512*z^56 + 785*z^55 + 1398*z^54 + 1048*z^53 - 926*z^52 + 121*z^51 + 1559*z^50 + 308*z^49 - 72*z^48 - 1050*z^47 + 190*z^46 + 868*z^45 - 1248*z^44 - 1498*z^43 - 658*z^42 + 228*z^41 + 661*z^40 - 670*z^39 - 500*z^38 - 594*z^37 + 1495*z^36 - 194*z^35 - 1119*z^34 + 1139*z^33 + 1268*z^32 - 1589*z^31 + 1133*z^30 - 123*z^29 + 93*z^28 - 859*z^27 - 1547*z^26 + 1274*z^25 - 695*z^24 - 1250*z^23 + 1406*z^22 - 1548*z^21 - 949*z^20 - 566*z^19 + 1542*z^18 + 96*z^17 + 195*z^16 + 149*z^15 - 1152*z^14 + 204*z^13 + 1202*z^12 + 505*z^11 - 1213*z^10 - 575*z^9 - 942*z^8 - 923*z^7 - 503*z^6 + 801*z^5 + 637*z^4 - 1143*z^3 - 506*z^2 + 138*z + 900]
H  = [z^127 - z^126 - z^125 + z^124 + 9*z^123 - z^122 - z^121 + 2*z^120 - 98*z^118 + 8*z^117 + 5*z^115 + 11*z^114 - 2*z^113 - z^111 + 10*z^110 - z^108 + z^106 - z^105 - 4*z^104 - z^103 - z^102 - 3*z^101 + 7*z^100 + z^99 + 50*z^98 + 17*z^97 - 3261*z^96 + z^94 + 2*z^93 + z^92 - z^91 + 14*z^90 + z^89 - z^88 + 4*z^87 - 51*z^86 + 7*z^85 - z^84 + z^83 - z^82 + 2*z^81 - 8*z^80 - z^79 + z^78 + 2*z^76 - 6*z^75 - z^74 - 2*z^73 - z^72 - 2*z^71 - z^69 - z^68 - 2*z^67 - 5*z^66 - 3*z^65 - 30*z^64 + 5*z^63 + z^62 - 4*z^61 - 2*z^60 - 9*z^59 + z^58 - 5*z^57 + 3*z^56 + 6*z^55 - 4*z^54 - z^53 - 3*z^52 - z^51 + 2*z^50 - 13*z^49 + 2*z^47 + z^46 - z^45 - 2*z^44 + 5*z^43 - z^42 + 5*z^41 - z^39 + z^37 - z^35 + z^34 - 3*z^33 + 6*z^32 - 2*z^31 - z^30 - 6*z^28 - z^26 + z^25 - z^24 + 3*z^23 - 8*z^21 - 10*z^20 - 17*z^19 + z^18 - z^16 - 2*z^15 + z^14 + z^13 + z^12 + z^11 + 10*z^10 - z^9 - z^8 - z^7 - 2*z^6 + z^5 - z^3 - z^2 + 12*z, z^126 + z^125 - 4*z^124 + z^123 + z^122 + z^121 - 4*z^119 + z^118 + z^117 - 19*z^116 - z^115 + 3*z^114 - 2*z^113 + z^112 + 5*z^111 + 3*z^110 + z^107 - z^106 - z^105 - 5*z^104 + 2*z^103 - z^102 - 3*z^100 - 8*z^99 + 4*z^98 + 2*z^95 + 13*z^94 - 2*z^93 + z^92 - z^90 - 3*z^88 + z^87 - z^86 + z^85 + z^84 - 2*z^83 - 6*z^81 - 5*z^78 - z^77 + z^76 + z^75 - z^74 - 2*z^73 + z^72 + 8*z^71 + z^70 + 3*z^69 - z^68 - 5*z^66 - z^64 - z^63 - 2*z^62 - 2*z^61 - 16*z^60 + z^59 + 8*z^58 - z^57 - z^56 - z^55 + z^54 + 3*z^53 + z^52 + 5*z^51 - z^50 - 3*z^49 - 4*z^47 + z^46 - z^45 + 5*z^43 + z^40 + z^39 + 2*z^38 - z^37 - z^36 + z^35 - z^34 - 2*z^33 + z^32 + z^31 - z^30 - z^29 + z^27 - 4*z^26 + 2*z^24 + z^23 + 2*z^22 + z^21 + 22*z^19 - z^18 + 2*z^16 + z^15 - z^14 + z^12 - 10*z^11 + z^10 - z^9 + z^8 - z^7 - z^6 - z^3 + z^2, -3*z^124 + 2*z^123 + 2*z^122 + z^121 - 67*z^120 + 2*z^119 + 2*z^118 + z^117 + 55*z^116 - 4*z^115 + z^114 - z^113 - 2*z^112 + 17*z^111 + 4*z^110 - z^109 + z^108 + z^107 + z^106 + z^104 + z^103 + 2*z^102 - z^101 - z^100 - z^99 + z^98 - 6*z^97 - z^96 - z^95 + z^92 - z^91 - z^90 + z^89 - 54*z^88 - z^86 - z^85 - z^84 - z^83 + z^82 + 3*z^81 + z^79 + z^77 - z^76 - 2*z^75 + 2*z^74 - z^73 - 2*z^72 + 2*z^71 - z^70 - z^69 - z^68 + z^67 - z^66 - 3*z^65 + z^64 - z^63 + z^62 + 48*z^60 - z^58 - 3*z^57 - 2*z^56 - z^54 - 4*z^53 + 8*z^52 - 3*z^51 - 56*z^50 + 3*z^49 - z^48 + z^45 + 24*z^44 - z^43 - 3*z^42 + z^40 + z^39 - z^38 + 2*z^37 - z^35 - z^34 - 3*z^33 + 2*z^31 - 42*z^29 - z^28 - 10*z^26 + z^25 + z^24 + 8*z^23 - z^22 + z^21 + 3*z^19 - 6*z^18 + 2*z^16 - z^15 - z^14 - z^13 + z^12 + 6*z^11 - 3*z^10 + z^8 + z^7 + 2*z^6 + 2*z^5 + z^4 + z^3 - 3*z^2 - 1, -z^127 + 2*z^126 - 16*z^125 - z^123 + z^122 + z^121 - 23*z^120 + z^119 + z^118 + 2*z^117 + z^116 + 5*z^115 + 8*z^114 - 5*z^113 + z^112 - z^111 + 5*z^110 + 2*z^108 + z^107 + 24*z^105 + 3*z^104 + z^103 - z^102 + 26*z^101 - 3*z^100 + 3*z^99 - z^98 + 3*z^97 + z^96 - z^94 - z^93 + z^92 - 4*z^90 - 3*z^88 - z^87 + 2*z^86 - 3*z^85 - 2*z^84 + z^83 - 2*z^82 + 6*z^80 + z^79 - z^78 + 8*z^77 - 2*z^76 - 3*z^75 - 2*z^74 - 2*z^73 + 3*z^71 + z^70 + z^69 - 2*z^67 - z^66 - 72*z^64 + 5*z^62 + 5*z^61 - 9*z^60 - z^59 + z^55 + z^54 - z^53 + z^52 + 3*z^51 + 15*z^50 + 3*z^49 - 3*z^48 - z^47 - z^45 - 7*z^44 - z^43 - 3*z^42 + 17*z^41 - z^37 - 3*z^36 + z^35 - 3*z^34 + z^32 - z^31 - z^30 + z^29 + 2*z^28 - z^26 + 2*z^25 + z^24 - 3*z^23 - 2*z^22 + 4*z^20 - 2*z^19 - z^18 + 2*z^17 + 6*z^15 - z^14 - z^13 - 2*z^12 - 2*z^11 + 2*z^9 + z^8 - 3*z^6 - 3*z^5 - z^4 - 4*z^3 + 2*z^2 - z]
l2 = [-6125*z^127 - 2822*z^126 - 92*z^125 - 9474*z^124 - 2842*z^123 + 6910*z^122 - 4249*z^121 + 4443*z^120 - 6752*z^119 - 3199*z^118 - 6560*z^117 + 3735*z^116 + 10442*z^115 - 6547*z^114 - 3302*z^113 - 9315*z^112 + 6096*z^111 + 2825*z^110 + 8951*z^109 - 307*z^108 + 9340*z^107 - 2962*z^106 + 13486*z^105 + 3908*z^104 + 10228*z^103 - 6813*z^102 + 5772*z^101 + 12398*z^100 + 3491*z^99 + 13448*z^98 + 3687*z^97 - 748*z^96 - 361*z^95 + 7100*z^94 - 3617*z^93 + 6460*z^92 + 3983*z^91 + 7359*z^90 - 12602*z^89 - 3562*z^88 - 26786*z^87 - 280*z^86 - 3294*z^85 - 6302*z^84 - 6502*z^83 + 9983*z^82 + 6643*z^81 + 6723*z^80 - 10252*z^79 - 3047*z^78 - 665*z^77 + 10404*z^76 + 6441*z^75 - 6583*z^74 - 5947*z^73 + 9607*z^72 - 12514*z^71 + 131*z^70 - 3517*z^69 - 3115*z^68 + 13435*z^67 - 12509*z^66 - 6094*z^65 - 12622*z^64 + 2840*z^63 + 3166*z^62 + 2622*z^61 + 3362*z^60 - 3041*z^59 + 7126*z^58 - 3046*z^57 - 3350*z^56 - 432*z^55 + 6468*z^54 - 2885*z^53 + 470*z^52 - 3109*z^51 - 6331*z^50 - 3812*z^49 + 6021*z^48 - 3058*z^47 - 4180*z^46 + 3159*z^45 + 19359*z^44 - 6450*z^43 - 6568*z^42 - 13101*z^41 + 6179*z^40 - 13210*z^39 - 2478*z^38 - 3550*z^37 + 6556*z^36 + 3405*z^35 + 309*z^34 + 3076*z^33 + 9636*z^32 - 467*z^31 + 2596*z^30 + 13554*z^29 - 6653*z^28 - 16341*z^27 - 12422*z^26 + 10044*z^25 - 19304*z^24 - 6484*z^23 - 5988*z^22 - 3026*z^21 - 2853*z^20 - 3058*z^19 - 12863*z^18 - 537*z^17 + 2784*z^16 + 804*z^15 - 271*z^14 - 9575*z^13 + 13044*z^12 - 6387*z^11 - 464*z^10 - 10906*z^9 - 6056*z^8 + 137*z^7 - 12311*z^6 - 6797*z^5 + 111*z^4 + 9323*z^3 - 16100*z^2 - 3241*z + 216, 169*z^95 - 237*z^94 - 287*z^93 + 535*z^92 - 142*z^91 - 257*z^90 + 132*z^89 + 61*z^88 + 214*z^87 - 69*z^86 + 154*z^85 - 102*z^84 + 413*z^83 + 166*z^82 + 547*z^81 + 2*z^80 - 88*z^79 - 215*z^78 - 467*z^77 - 167*z^76 - 467*z^75 + 164*z^74 - 120*z^73 - 304*z^72 + 144*z^71 + 282*z^70 - 277*z^69 - 27*z^68 + 41*z^67 + 111*z^66 - 549*z^65 + 636*z^64 - 46*z^63 + 328*z^62 - 65*z^61 + 149*z^60 - 137*z^59 - 130*z^58 - 116*z^57 + 113*z^56 - 150*z^55 - 187*z^54 - 29*z^53 + 422*z^52 - 421*z^51 + 149*z^50 + 236*z^49 + 149*z^48 - 232*z^47 - 336*z^46 - 278*z^45 - 155*z^44 + 135*z^43 - 393*z^42 - 31*z^41 + 358*z^40 + 51*z^39 - 6*z^38 - 47*z^37 + 345*z^36 + 66*z^35 + 243*z^34 - 263*z^33 + 76*z^32 - 120*z^31 - 85*z^30 + 120*z^29 + 99*z^28 - 288*z^27 + 209*z^26 + 178*z^25 + 32*z^24 - 368*z^23 + 148*z^22 - 262*z^21 + 141*z^20 - 357*z^19 + 94*z^18 - 207*z^17 + 205*z^16 + 27*z^15 + 25*z^14 + 62*z^13 - 250*z^12 - 234*z^11 - 36*z^10 + 101*z^9 + 520*z^8 + 200*z^7 - 279*z^6 - 60*z^5 + 369*z^4 - 81*z^3 + 133*z^2 - 330*z + 227]
enc =  0c8850f11526011aad008ba5fdb4335ea1985d2212bd017fd00dce2eae58b1fb46a65644768718d34bd67c921eb278e419c025b7f0ffbb6b24123946908dd4cb

## Phân tích

Đây cũng là lần đầu tiên mình gặp bài về ` CyclotomicField` , nó cũng khiến mình mất một thời gian ngồi research . Xong mình đơn giản hiểu nó là 1 trường số phức mà thôi , trong đó thì $z^n = 1$ và $z^{n/2} = -1$ .
Các phép nhân còn lại thực hiện như bình thường . Ví dụ 1 phép nhân trong trường này nhé

$(z^{30} + z^{125})*(z^{12}*z^{90}) = z^{42} + z^{120} + z^{137} + z^{215}$
$= z^{42} + z^{120} + z^{128}*z{9} + z^{128}*z{87}$
$= z^{42} + z^{120} - z^{9} - z^{27}$

Như ta thấy thì cứ thằng nào mà số mũ vượt qua 128 là tự động trừ đi rồi nhân thêm $-1$ vào hệ số của nó .

q       = 3329
k       = 2 
sigma   = 2.5
n       = 256
K = CyclotomicField(n,'z') 
OK      = K.OK()
OKq= OK.quotient(q,'y')
a = K.gens()[0]
print((a^30+a^125)*(a^12+a^90))

Các bạn chạy thử để kiểm nghiệm nhé :smiley_cat:

Vậy sau khi ta hiểu phép nhân rồi thì ta có thể làm gì với bài này .

Bản thân mình lúc đầu nhìn vào thì thấy `A*s + e = b` thì nhìn thấy nó là `LWE` rồi nhưng để exploit từ dữ kiện `A,b` nhận được thì mình thấy no hope vl nên mình đá qua output còn lại là `H và l2`

H = matrix(k,k,[ OK(list(random_vector(ZZ,n))) for _ in k*k*"_"] )
l = s*H                                                # I won't give you this 3:)
h = floor(.25*n/2)                                                 
l2 = matrix([l[0,0] , OK(l[0,1].list()[:-h]) ]) 

Thì như ta thấy nó sẽ thực hiện 1 phép nhân $l=s*H$ và cho ta biết phần tử đầu tiên của $l$ và 96 phần tử đầu tiên của $l$ .

> Chú ý : Ở đây s là nhân bên trái , tức solve_left nhé , chứ không phải solve_right , chỉ vì cái này mà mình không giải được :crying_cat_face:

Ta có : `s = matrix(K, [K(random_vector(ZZ,n//2,sigma,distribution="gaussian").list()) for __ in k*"_"] )`
Tức `s` là 1 matrix $2x1$ và sẽ có dạng kiểu :

$[x_1*z^{127} + x_2*z^{126} + ... + x_{128}*z^0]$ - $s1$
$[y_1*z^{127} + y_2*z^{126} + ... + y_{128}*z^0]$ - $s2$

Và nó sẽ nhân với`H` , thì mình sẽ đặt các $s$ như trên rồi nhân với $H$ luôn , và sẽ nhóm các phần tử chung $z^{127},z^{126} , ..,z^{0}$ với nhau rồi so sánh với giá trị trong $l$ , ứng với từng $z$ mình sẽ có 1 phương trình
Ở đây $l2[0]$ cho ta $128$ giá trị và $l2[1]$ cho ta $96$ giá trị là 224 giá trị , tức 224 phương trình , tuy chưa để solve_left nhưng đủ để ta giải bằng LLL hoặc tools của Blupper rồi .

Link : https://raw.githubusercontent.com/TheBlupper/linineq/main/linineq.py

Cho bạn nào chưa rõ về phương trình tạo như nào mình sẽ có 1 ví dụ nhỏ ở dưới đây nhé :

$s = (x_1*z^2 + x_2*z)*(3*z^2 + 2) = 3*x_1*z^4 + 2*x_1*z^2 + 3*x_2*z^2 + 2*x_2*z$
$s = 3*x_1*z^4 + (2*x_1+3*x_2)*z^2 + 2*x_2*z$
Thì giá sử mình biết nó có các phần tử của $z,z^2$ là $4,10$ thì mình có thể tìm được $x1,x2$ . Ở đây thì nó là :

$H[0]*s_1 + H[1]*s_2 = l2[0]$
$H[2]*s_1 + H[1]*s_2 = l2[1]$

Mình cũng thực hiện phép nhân rồi lấy các hệ số tương ứng với $z^{127} , .. z^0$ và kết quả của hệ số đó thì ta sẽ lấy ở $l2$

Giờ thì mình sẽ nhờ thực hiện phép nhân để lấy hệ số của từng thằng $z^{127}, z^{126} , .. , z^0$ ra thôi. Cái này thực hiện như phép nhân bình thường chỉ khác chỗ $z^{128}$ mình nói ở trên , khi vượt quá thì số mũ tự động trừ đi $128$ và hệ số nhân thêm $-1$

import sympy as sp
import re

z = sp.symbols('z')
x = sp.symbols('x_0:128')
y = sp.symbols('y_0:128')


poly1 = sum(x[i] * z**(127 - i) for i in range(128))

poly2 = (z**127 - z**126 - z**125 + z**124 + 9*z**123 - z**122 - z**121 + 2*z**120 - 98*z**118 + 8*z**117 + 
         5*z**115 + 11*z**114 - 2*z**113 - z**111 + 10*z**110 - z**108 + z**106 - z**105 - 4*z**104 - 
         z**103 - z**102 - 3*z**101 + 7*z**100 + z**99 + 50*z**98 + 17*z**97 - 3261*z**96 + z**94 + 
         2*z**93 + z**92 - z**91 + 14*z**90 + z**89 - z**88 + 4*z**87 - 51*z**86 + 7*z**85 - z**84 + 
         z**83 - z**82 + 2*z**81 - 8*z**80 - z**79 + z**78 + 2*z**76 - 6*z**75 - z**74 - 2*z**73 - z**72 - 
         2*z**71 - z**69 - z**68 - 2*z**67 - 5*z**66 - 3*z**65 - 30*z**64 + 5*z**63 + z**62 - 4*z**61 - 
         2*z**60 - 9*z**59 + z**58 - 5*z**57 + 3*z**56 + 6*z**55 - 4*z**54 - z**53 - 3*z**52 - z**51 + 
         2*z**50 - 13*z**49 + 2*z**47 + z**46 - z**45 - 2*z**44 + 5*z**43 - z**42 + 5*z**41 - z**39 + 
         z**37 - z**35 + z**34 - 3*z**33 + 6*z**32 - 2*z**31 - z**30 - 6*z**28 - z**26 + z**25 - z**24 + 
         3*z**23 - 8*z**21 - 10*z**20 - 17*z**19 + z**18 - z**16 - 2*z**15 + z**14 + z**13 + z**12 + 
         z**11 + 10*z**10 - z**9 - z**8 - z**7 - 2*z**6 + z**5 - z**3 - z**2 + 12*z)


product_poly1 = poly1 * poly2


poly3 = sum(y[i] * z**(127 - i) for i in range(128))


poly4 = (z**126 + z**125 - 4*z**124 + z**123 + z**122 + z**121 - 4*z**119 + z**118 + z**117 - 19*z**116 - 
         z**115 + 3*z**114 - 2*z**113 + z**112 + 5*z**111 + 3*z**110 + z**107 - z**106 - z**105 - 
         5*z**104 + 2*z**103 - z**102 - 3*z**100 - 8*z**99 + 4*z**98 + 2*z**95 + 13*z**94 - 2*z**93 + 
         z**92 - z**90 - 3*z**88 + z**87 - z**86 + z**85 + z**84 - 2*z**83 - 6*z**81 - 5*z**78 - z**77 + 
         z**76 + z**75 - z**74 - 2*z**73 + z**72 + 8*z**71 + z**70 + 3*z**69 - z**68 - 5*z**66 - z**64 - 
         z**63 - 2*z**62 - 2*z**61 - 16*z**60 + z**59 + 8*z**58 - z**57 - z**56 - z**55 + z**54 + 3*z**53 + 
         z**52 + 5*z**51 - z**50 - 3*z**49 - 4*z**47 + z**46 - z**45 + 5*z**43 + z**40 + z**39 + 2*z**38 - 
         z**37 - z**36 + z**35 - z**34 - 2*z**33 + z**32 + z**31 - z**30 - z**29 + z**27 - 4*z**26 + 2*z**24 + 
         z**23 + 2*z**22 + z**21 + 22*z**19 - z**18 + 2*z**16 + z**15 - z**14 + z**12 - 10*z**11 + z**10 - 
         z**9 + z**8 - z**7 - z**6 - z**3 + z**2)





result_poly =  poly1*poly2 + poly3*poly4


result_poly_simplified = sp.expand(result_poly)


adjusted_terms = {}
for term in result_poly_simplified.as_ordered_terms():
    coeff, z_exp = term.as_coeff_exponent(z)
    if z_exp > 127:
        new_exp = z_exp - 128
        coeff *= -1
    else:
        new_exp = z_exp
    if new_exp in adjusted_terms:
        adjusted_terms[new_exp] += coeff
    else:
        adjusted_terms[new_exp] = coeff
adjusted_poly = sum(coeff * z**exp for exp, coeff in adjusted_terms.items())

coefficients = [adjusted_terms.get(i, 0) for i in range(128)]



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

result_poly = poly1*poly5 + poly3*poly6
result_poly_simplified = sp.expand(result_poly)

adjusted_terms = {}
for term in result_poly_simplified.as_ordered_terms():
    coeff, z_exp = term.as_coeff_exponent(z)
    if z_exp > 127:
        new_exp = z_exp - 128
        coeff *= -1
    else:
        new_exp = z_exp
    if new_exp in adjusted_terms:
        adjusted_terms[new_exp] += coeff
    else:
        adjusted_terms[new_exp] = coeff

adjusted_poly = sum(coeff * z**exp for exp, coeff in adjusted_terms.items())
coefficients_2 = [adjusted_terms.get(i, 0) for i in range(128)]

multi = []
coeffis = coefficients + coefficients_2
with open('test.txt' , 'w') as f :
    for i in coeffis :
        f.write(str(i) + '\n')
        
        

Nó chạy khá lâu đấy nên mình sẽ để luôn file test.txt ở đây , ờ ừm nope bị giới hạn từ r , các bạn tự chạy hen =))

Mình không nhân trực tiếp được bằng sage , do khi nó nhân thì nó không giữ nguyên $z$ nữa mà bị biến về dạng số phức rồi.

Sau khi có hệ số thì ta chú ý 1 chút về phép nhân ma trận ta thực hiện , ở đây là $s*H$ nên $s$ sẽ nhân các phần tử theo hàng dọc chứ không phải hàng ngang :crying_cat_face:

Nên sau khi ta lấy hệ số nhân ta phải chuyển vị nó lại và lấy 224 hàng đầu tiên là sẽ có được hệ số nhân đúng cho việc solve_right :crying_cat_face:

import re 
import sympy as sp 

multi = []
f = open('test.txt' , 'r')
for _ in range(256) : 
    
    expression = str(f.readline())
    
    x_coeffs = [0] * 128  
    y_coeffs = [0] * 128  
    expression = expression.replace(' ', '')
  
    matches = re.findall(r'([+-]?\d*)\*?(x|y)_(\d+)', expression)
    for match in matches:
        coeff_str, var, index_str = match
        index = int(index_str)  
        
      
        if coeff_str == '' or coeff_str == '+':
            coeff = 1
        elif coeff_str == '-':
            coeff = -1
        else:
            coeff = int(coeff_str)
        
      
        if var == 'x':
            if 0 <= index < 128:
                x_coeffs[index] = coeff 
        elif var == 'y':
            if 0 <= index < 128:
                y_coeffs[index] = coeff 

   
    coefficients = x_coeffs + y_coeffs
    
    multi.append(coefficients)


from linineq import * 

coefficients = [
    216, -3241, -16100, 9323, 111, -6797, -12311, 137, -6056, -10906, 
    -464, -6387, 13044, -9575, -271, 804, 2784, -537, -12863, -3058, 
    -2853, -3026, -5988, -6484, -19304, 10044, -12422, -16341, -6653, 
    13554, 2596, -467, 9636, 3076, 309, 3405, 6556, -3550, -2478, 
    -13210, 6179, -13101, -6568, -6450, 19359, 3159, -4180, -3058, 
    6021, -3812, -6331, -3109, 470, -2885, 6468, -432, -3350, -3046, 
    7126, -3041, 3362, 2622, 3166, 2840, -12622, -6094, -12509, 13435, 
    -3115, -3517, 131, -12514, 9607, -5947, -6583, 6441, 10404, -665, 
    -3047, -10252, 6723, 6643, 9983, -6502, -6302, -3294, -280, -26786, 
    -3562, -12602, 7359, 3983, 6460, -3617, 7100, -361, -748, 3687, 
    13448, 3491, 12398, 5772, -6813, 10228, 3908, 13486, -2962, 9340, 
    -307, 8951, 2825, 6096, -9315, -3302, -6547, 10442, 3735, -6560, 
    -3199, -6752, 4443, -4249, 6910, -2842, -9474, -92, -2822, -6125
]
coefficients2 = [
    227, -330, 133, -81, 369, -60, -279, 200, 520, 101, 
    -36, -234, -250, 62, 25, 27, 205, -207, 94, -357, 
    141, -262, 148, -368, 32, 178, 209, -288, 99, 120, 
    -85, -120, 76, -263, 243, 66, 345, -47, -6, 51, 
    358, -31, -393, 135, -155, -278, -336, -232, 149, 236, 
    149, -421, 422, -29, -187, -150, 113, -116, -130, -137, 
    149, -65, 328, -46, 636, -549, 111, 41, -27, -277, 
    282, 144, -304, -120, 164, -467, -167, -467, -215, -88, 
    2, 547, 166, 413, -102, 154, -69, 214, 61, 132, 
    -257, -142, 535, -287, -237, 169
]
print(len(coefficients) , len(coefficients2))
coe = coefficients + coefficients2


M = Matrix(multi).T 
M2 = []
for i in range(224) :
    M2.append(M[i])
    
    
M2 = Matrix(M2)
b = vector(coe)
s = solve_bounded(M2,b,[-10]*256,[10]*256)

q       = 3329
k       = 2 
sigma   = 2.5
n       = 256
K = CyclotomicField(n,'z') 
OK      = K.OK()
OKq= OK.quotient(q,'y')
a = K.gens()[0]
s1 , s2  = s[:128] , s[128:]

poly1 = sum(s1[i] * a**(127 - i) for i in range(128))
print(poly1)
poly2 = sum(s2[i] * a**(127 - i) for i in range(128))
print(poly2)

Sau khi có $s$ thì mọi chuyển trở nên đơn giản rồi , ta chỉ cần lấy $b - A*s$ là ra e , rồi decrypt flag thôi .

s = vector([poly1,poly2])
e = (b-s*A).change_ring(OKq)
key = sha256(str(matrix(s)).encode()).digest()[:16]
iv  = sha256(str(matrix(e)).encode()).digest()[:16]

cipher= AES.new(key,AES.MODE_CBC,iv=iv)
print(cipher.decrypt(enc)) 

Flag : ```CSCTF{wh4t_1f_my_h1nt_i5_4lgbr4!c????0x54763498142}```