ICTF Collections

Một số bài CTF trên trang imaginaryCTF mà mình sưu tầm rồi giải lại được.

ICTF Round 54

univariate

Source code của bài:

from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag
 
p = getPrime(512)
q = getPrime(512)
n = p*q
 
m = bytes_to_long(flag.encode())
e = 65537
c = pow(m,e,n)
 
P.<x> = PolynomialRing(ZZ)
x = P.gens()[0]
 
terms = [x**i for i in range(137)]
 
T = RealDistribution('gaussian', 2)
coefs = [round(T.get_random_element()) for _ in range(len(terms))]
 
f = sum([term*coef for term,coef in zip(terms,coefs)])
w = pow(2,f(p),n)
 
with open('out.txt', 'w') as file:
    file.write(f'{n = }\\n')
    file.write(f'{e = }\\n')
    file.write(f'{c = }\\n')
    file.write(f'{f = }\\n')
    file.write(f'{w = }\\n')

output.txt

n = 151510886600487624888537926759375027338192556324330182365859112926770109752858284462159488504727238764120612593911292154858008775463001345641311051184326218974685701057787672193003745574697137968457609530135969033403360561333863943223407215732526198691453110628598401583407984162075630768455052482583101773637
e = 65537
c = 74468088842131664480394073891613024559473817230309311952320910922177130990996003196602702376336093457990873018154873841543712071422931358036924937335888815556064840522100618318507080665149514719351519909821468981883880543654015414713368018500970500498936910817336501949914675483148862843329341461828563728789
f = -x^136 + x^135 - 2*x^134 - 4*x^132 + 2*x^130 - x^128 - 3*x^127 + 4*x^126 + 3*x^125 + 3*x^124 + x^123 + x^122 - 5*x^121 - 3*x^120 - x^119 - x^118 + x^117 + x^116 - 4*x^114 - 2*x^112 + 2*x^110 + x^109 + 2*x^108 - 2*x^107 + 3*x^106 - x^104 + 2*x^103 - x^102 + x^101 - 2*x^100 + 3*x^99 - 2*x^98 - x^97 - x^96 - 3*x^95 - x^94 - 2*x^93 - 2*x^91 + 3*x^90 - 2*x^89 - 2*x^88 + x^86 + x^85 - 2*x^84 - 3*x^83 + 2*x^82 + 3*x^79 - x^76 + 2*x^75 - x^74 + x^71 - 5*x^70 - x^67 + x^66 + x^65 + x^63 - x^61 + x^59 - 2*x^58 + 6*x^56 + x^55 + 3*x^54 - x^53 + 2*x^52 + 3*x^51 + x^50 + 2*x^49 + 3*x^47 + 2*x^46 - 4*x^45 + 3*x^44 + 3*x^43 - x^42 - 2*x^40 - 5*x^39 + x^38 + x^37 + 2*x^36 + 2*x^35 + x^34 - x^33 + x^32 - 5*x^31 + x^30 + x^29 + 2*x^28 - 2*x^27 + 3*x^26 - x^25 - x^23 - x^22 - 3*x^21 + 2*x^20 - x^19 - x^17 + 2*x^16 - 2*x^15 - 2*x^14 - 2*x^13 - 2*x^12 + 2*x^11 - 2*x^9 + 3*x^8 - 4*x^7 + 2*x^6 - 2*x^5 - 5*x^4 - 3*x^3 + 5*x^2 - 2
w = 86258923706084556733053644452456806418792871483898871193707132372143291757396867798433017660985422614532352743658877188445517898648519256573663299464811234251773841741466280567326570167017786562044635756348763128567054349991798640926148221279889174229551074668002853442182664523748992260830782387602048836221

Chú ý dòng này

T = RealDistribution('gaussian', 2)
coefs = [round(T.get_random_element()) for _ in range(len(terms))]
 

Nó đang tạo các hệ số cho đa thức theo phân phối chuẩn Gauss, đa thức có bậc là 136 và các hệ số nằm trong khoảng $[-2,2]$. Ta được cho biết giá trị của $w=2^{f(p)}\mathrm{mod}n$.

Ta biết rằng

$$f(p)=f(1)\mathrm{mod}p-1$$

Cho nên nếu bây giờ ta lấy

$$w\times 2^{-f(1)}=2^{f(p)-f(1)}=2^{k(p-1)}=1\mathrm{mod}p$$

Thì bằng cách này ta có thể factor được $n$ bằng cách lấy $gcd$.

from Crypto.Util.number import *
from sage.all import *
P = PolynomialRing(QQ,'x')
x = P.gen()
with open('out.txt','r') as file:
    exec(file.read().replace('^','**'))
f_1 = f(1)
print(f_1)
inv = pow(2, -int(f_1), n) 
A = (w * inv) % n
p = gcd(A - 1, n)
print(p)
q = n//p 
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
m = pow(int(c),int(d),int(n))
print(long_to_bytes(int(m)))
 
# b'ictf{p-1_g0es_aB$olU7eLy_w1lD!!!}'

bivariate

from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag
 
p = getPrime(512)
q = getPrime(512)
n = p*q
 
m = bytes_to_long(flag.encode())
e = 65537
c = pow(m,e,n)
 
P.<x,y> = PolynomialRing(ZZ)
x, y = P.gens()
 
terms = []
for i in range(16):
    terms += [(x**i)*(y**j) for j in range(16-i)]
 
T = RealDistribution('gaussian', 2)
coefs = [round(T.get_random_element()) for _ in range(len(terms))]
 
f = sum([term*coef for term,coef in zip(terms,coefs)])
w = pow(2,f(p,q),n)
 
with open('out.txt', 'w') as file:
    file.write(f'{n = }\\n')
    file.write(f'{e = }\\n')
    file.write(f'{c = }\\n')
    file.write(f'{f = }\\n')
    file.write(f'{w = }\\n')

Lần này khó hơn một chút, thay vì đa thức một biến như lần trước thì lần này bài dùng một đa thức hai biến $f(p,q)$.

Nếu muốn dùng trick như lần trước thì ta cần phải biết được giá trị của $p$ để tính

$$f(p,q)-f(p,1)⋮q-1$$

Nhưng tất nhiên là ta không thể biết được giá trị của $p,q$ rồi

Nếu mình thay $p=n$ thì sao?

Mỗi đa thức hai biến đều có dạng

$$f(x,y)=\sum _{i,j\ge 0}{a}_{ij}{x}^i{y}^j,\forall x,y\in \mathbb{Q}$$

Nếu bây giờ mình tính $f(n,1)$ và trừ cho $f(p,q)$ sẽ được gì?

$$\begin{gathered} f(n,1)-f(p,q)=f(pq,1)-f(p,q) \\ \iff \sum _{i,j\ge 0}{a}_{ij}((pq{)}^i-p^i{q}^j)=\sum _{i,j\ge 0}{a}_{ij}(p^i(q^i-q^j)) \end{gathered}$$

Do số mũ $i,j$ sẽ có sự chênh lệch cho nên ta có tổng trên chia hết cho $q-1$. Nếu hai số mũ bằng nhau thì tích bằng 0 cũng coi như chia hết cho $q-1$. Vậy ta có thể factor được $n$ và làm tương tự bài trên.

from Crypto.Util.number import *
from sage.all import PolynomialRing, QQ, gcd
P = PolynomialRing(QQ,['x','y'])
x,y= P.gens()
with open('out.txt','r') as file:
    exec(file.read().replace('^','**'))
exp = int(f(1,n))
factor = pow(2,exp,n)
p = gcd(factor-w,n)
print(p)
q = n//int(p)
q = int(q)
p = int(p)
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
# b'ictf{symmetry_of_bivariate_polynomials_is_zany}'

Tính chất trên có vẻ chỉ hoạt động với đa thức hai biến hoặc nhiều biến hơn. Đối với trường hợp một biến thì ta không thể lấy $f(kp)-f(1)⋮p-1$ được.

ICTF Round 57

polynomials

#!sage
from Crypto.Util.number import bytes_to_long, getPrime
from secrets import randbits
 
flag = 'ictf{test_flag}'
m = bytes_to_long(flag.encode())
 
p = getPrime(512)
q = getPrime(512)
priv = [randbits(512),randbits(512)]
n = p*q
e = 65537
c = pow(m,e,n)
 
P.<x> = PolynomialRing(ZZ)
x = P.gen()
terms = [x**i for i in range(137)]
T = RealDistribution('gaussian', 2)
 
f = []
f1 = -x**136 + 2*x**135 - 3*x**134 + 3*x**133 + 2*x**132 + x**131 + 3*x**130 - 3*x**129 + 3*x**128 + 2*x**127 + 2*x**126 - 3*x**125 - x**124 - 3*x**123 - 2*x**122 + x**121 - x**120 - x**119 + 4*x**118 + x**117 - x**116 - 2*x**115 - 3*x**114 + x**113 + x**112 - 4*x**111 - x**110 + 2*x**109 + 2*x**108 + 3*x**107 - x**106 + 2*x**105 + 2*x**104 - 2*x**103 + 2*x**102 + 2*x**101 - 4*x**100 - 2*x**99 - 3*x**98 + 4*x**97 - 2*x**96 - 2*x**95 - 4*x**94 + x**93 - x**92 + x**91 - x**90 - 3*x**89 - x**88 - 4*x**87 - 2*x**86 - x**85 - x**84 - 3*x**83 + x**82 + x**81 + 4*x**80 - 5*x**79 - 4*x**78 + 2*x**77 - x**76 - x**75 + x**74 - 2*x**73 - 3*x**72 - 3*x**71 + x**70 + 2*x**69 + x**68 - x**67 - 2*x**66 - x**65 - 2*x**64 + x**63 + x**62 - x**61 - x**60 + x**59 - 5*x**58 + x**57 - 3*x**56 + x**55 + 2*x**54 + 5*x**53 - 2*x**52 - 2*x**51 + x**50 + x**49 + 3*x**48 + 4*x**47 + 2*x**46 - x**45 - x**44 + x**43 - 2*x**42 - x**41 + 2*x**40 + 2*x**39 + x**38 + 2*x**37 - 2*x**36 + 3*x**35 + 2*x**34 - 4*x**33 - 3*x**32 + 2*x**31 - 2*x**30 - 3*x**29 - 4*x**28 - 3*x**27 + x**26 + x**25 + 3*x**24 + x**23 + 4*x**22 + 2*x**21 + 2*x**20 + x**19 + x**18 + 3*x**17 + x**16 - 4*x**15 - x**14 + x**13 + x**12 + 2*x**11 + 2*x**10 + x**9 + x**8 + x**7 + 3*x**6 - 2*x**5 + 3*x**4 + 2*x**3 + 2*x**2 + 2*x - 1
f2 = x**136 - 3*x**135 + x**134 + 3*x**133 + 5*x**132 + x**131 + x**130 - 2*x**129 + 2*x**128 + 3*x**127 + x**126 - x**125 + 4*x**124 - 4*x**123 + 2*x**122 + x**121 - x**120 - x**119 + x**118 + x**117 - x**116 - 3*x**115 + 3*x**114 - x**113 + x**112 - x**111 + x**110 - 4*x**109 + x**108 + x**107 + x**106 + 3*x**105 + 7*x**104 - x**103 + 3*x**102 + 2*x**101 - 4*x**100 + 2*x**99 + x**98 + x**97 - x**96 - x**95 + 2*x**94 + 2*x**93 - 2*x**92 + x**91 + x**90 + 2*x**89 - 2*x**88 - x**87 - 2*x**86 - 3*x**85 - x**84 - x**83 - 2*x**82 - 3*x**81 + 2*x**80 - 2*x**79 - 4*x**78 - 3*x**77 + 2*x**76 + x**75 - 3*x**74 - 2*x**73 + x**72 - x**71 + x**70 - 2*x**69 + x**68 + x**67 + x**66 - x**65 - x**64 - x**63 - 4*x**62 + x**61 - x**60 + 2*x**59 - 6*x**58 - 2*x**57 - x**56 + x**55 - 2*x**54 + x**53 - 4*x**52 - 2*x**51 - 3*x**50 + x**49 + 3*x**48 + 4*x**47 + 3*x**46 - x**45 + x**44 - x**43 + 5*x**42 + 3*x**41 + x**40 + x**39 + 2*x**38 + x**37 + x**36 - x**35 + x**34 - x**33 - 3*x**32 + x**31 + x**30 + x**29 + x**28 + x**27 - x**26 - x**25 - x**24 + 2*x**23 + x**22 + x**21 + x**20 - 5*x**19 + x**18 + 2*x**17 + x**16 - 2*x**15 - x**14 - 3*x**13 - x**12 - 3*x**11 + x**10 - 2*x**9 - x**8 - x**7 - x**6 - 3*x**5 - 2*x**4 + 2*x**3 - x**2 + 5*x + 1
 
pub = []
pub.append([f1,pow(priv[0],priv[1],f1(p))])
pub.append([f1,pow(priv[0],priv[1],f2(p))])
 
with open('out.txt','w') as file:
    file.write(f'{n = }\\n')
    file.write(f'{e = }\\n')
    file.write(f'{c = }\\n')
    file.write(f'{pub = }')

output.txt

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

Phân tích: Ở bài này đầu tiên ta có thuật toán mã hóa RSA. Ngoài ra còn có thêm

terms = [x**i for i in range(137)]

Tạo các đơn thức $x^i$ với $i$ từ $0$ tới $136$. priv là một list gồm hai giá trị $a,b$. Bây giờ, bài cho ta hai đa thức $f_1$ và $f_2$. Tiếp theo nó sẽ lấy

$$\begin{array}{l}{a}^b\mathrm{mod}{f}_1(p)\\ a^b\mathrm{mod}{f}_2(p)\end{array}$$

Và gán vào pub : Đ (mình cx K hiểu tác giả cho thêm f1 vào làm gì :v chắc code nhầm)

pub.append([f1,pow(priv[0],priv[1],f1(p))])
pub.append([[f1,pow(priv[0],priv[1],f2(p))])

Như mọi bài RSA khác thì mục tiêu của ta vẫn là tìm cách factor cái modulo $n$. Giả thiết duy nhất mà ta khai thác được hiện tại là hai giá trị $priv[0]$ và $priv[1]$ . Tạm gọi lần lượt là $u,v$. Ta có

$$\begin{array}{l}u\equiv a^b\mathrm{mod}{f}_1(p)\\ v\equiv a^b\mathrm{mod}{f}_2(p)\end{array}$$

Ta có tính chất sau:

$$\begin{array}{l}{f}_1(p)-f_1(0)⋮p\\ f_2(p)-f_2(0)⋮p\end{array}$$

Đặt $a^b=t$ ta viết lại phương trình đồng dư dưới dạng

$$\begin{array}{l}u-t=k_1{f}_1(p)\\ v-t=k_2{f}_2(p)\end{array}$$

Mà $f_1(p)=f_1(0)+c_{1}p$ nên ta có thể biến đổi thử về như sau

$$\begin{array}{l}u-t=k_1\times (f_1(0)+c_{1}p)\end{array}$$

Tương tự với $v$. Nhưng nếu như thử biến đổi theo cách này thì hmm, ta lại tạo ra các phương trình có quá nhiều ẩn . Nhưng nếu ta đưa về rút gọn theo modulo $p$ thì sao? Ta sẽ được

$$\begin{array}{l}u-t=k_1\times f_1(0)\mathrm{mod}p\\ v-t=k_2\times f_2(0)\mathrm{mod}p\end{array}$$

Các giá trị $f_1(0),f_2(0)$ ta đều tính được. Hơn nữa cả hai phương trình này đều có nghiệm nguyên. Bây giờ nếu ta lấy

$$\begin{array}{l}u-t-v+t=k_1\times f_1(0)-k_2\times f_2(0)=u-v\mathrm{mod}p\end{array}$$

Đưa về phương trình $ax+by=c\mathrm{mod}p$. Trong đó $x,y$ là hai ẩn số cần tìm. Ở đây là $k_1,k_2$. Còn $f_1(0),f_2(0),u-v$ ta đều tính được.

Nhưng có một số vấn đề với hướng đi này. Đầu tiên là phép lấy modulo $p$. Giả sử kể cả khi mình tìm được nghiệm của phương trình trên mà không biết modulo $p$, tức là chỉ cần tìm một ràng buộc thỏa mãn (bằng LLL hoặc gì đó) thì khi thay vào sẽ bị sai lệch. Vì ban đầu cách phép biến đổi đang làm trên các modulo khác hoàn toàn so với $p$ nên cách này phá sản.

Nếu ta viết $u=t+k_1{f}_1(p)$ và $v=t+k_2{f}_2(p)$ thì từ đây nếu ta lấy

$$u-v=k_1{f}_1(p)-k_2{f}_2(p)=\gcd (f_1(p),f_2(p))\times (k_1\frac{f_1(p)}{gcd(f_1(p),f_2(p)}-k_2\frac{f_2(p)}{gcd(f_1(p),f_2(p)})$$

Tương đương với $u-v$ là bội của $\gcd (f_1(p),f_2(p))$. Đầu tiên mình thử lấy gcd xem có gì đặc biệt.

from sage.all import *
from Crypto.Util.number import *
n = 139330151536291968154362056939191793190070421572607425126412864337960428214252710841790520177640304299848055785679956848879739289740736863858805522021402011784816289402906107827951305153323054170827032255783498256586075556326444324525178342434840530590901685035569099701248356757529471617586874231156794230817
e = 65537
c = 15697592827886645187966669864651924219495308876901271939626110164697706354780388148028280108438305865692406640426779894405286509802915488727759853245713073474018996800135683443416843570824582921878289587458989402877628178914425857255506044374087201140996429025129707759174701127979197532188604260843479601147
import sys
sys.set_int_max_str_digits(0)
P = PolynomialRing(QQ,"x")
x = P.gen()
f1 = -x**136 + 2*x**135 - 3*x**134 + 3*x**133 + 2*x**132 + x**131 + 3*x**130 - 3*x**129 + 3*x**128 + 2*x**127 + 2*x**126 - 3*x**125 - x**124 - 3*x**123 - 2*x**122 + x**121 - x**120 - x**119 + 4*x**118 + x**117 - x**116 - 2*x**115 - 3*x**114 + x**113 + x**112 - 4*x**111 - x**110 + 2*x**109 + 2*x**108 + 3*x**107 - x**106 + 2*x**105 + 2*x**104 - 2*x**103 + 2*x**102 + 2*x**101 - 4*x**100 - 2*x**99 - 3*x**98 + 4*x**97 - 2*x**96 - 2*x**95 - 4*x**94 + x**93 - x**92 + x**91 - x**90 - 3*x**89 - x**88 - 4*x**87 - 2*x**86 - x**85 - x**84 - 3*x**83 + x**82 + x**81 + 4*x**80 - 5*x**79 - 4*x**78 + 2*x**77 - x**76 - x**75 + x**74 - 2*x**73 - 3*x**72 - 3*x**71 + x**70 + 2*x**69 + x**68 - x**67 - 2*x**66 - x**65 - 2*x**64 + x**63 + x**62 - x**61 - x**60 + x**59 - 5*x**58 + x**57 - 3*x**56 + x**55 + 2*x**54 + 5*x**53 - 2*x**52 - 2*x**51 + x**50 + x**49 + 3*x**48 + 4*x**47 + 2*x**46 - x**45 - x**44 + x**43 - 2*x**42 - x**41 + 2*x**40 + 2*x**39 + x**38 + 2*x**37 - 2*x**36 + 3*x**35 + 2*x**34 - 4*x**33 - 3*x**32 + 2*x**31 - 2*x**30 - 3*x**29 - 4*x**28 - 3*x**27 + x**26 + x**25 + 3*x**24 + x**23 + 4*x**22 + 2*x**21 + 2*x**20 + x**19 + x**18 + 3*x**17 + x**16 - 4*x**15 - x**14 + x**13 + x**12 + 2*x**11 + 2*x**10 + x**9 + x**8 + x**7 + 3*x**6 - 2*x**5 + 3*x**4 + 2*x**3 + 2*x**2 + 2*x - 1
f2 = x**136 - 3*x**135 + x**134 + 3*x**133 + 5*x**132 + x**131 + x**130 - 2*x**129 + 2*x**128 + 3*x**127 + x**126 - x**125 + 4*x**124 - 4*x**123 + 2*x**122 + x**121 - x**120 - x**119 + x**118 + x**117 - x**116 - 3*x**115 + 3*x**114 - x**113 + x**112 - x**111 + x**110 - 4*x**109 + x**108 + x**107 + x**106 + 3*x**105 + 7*x**104 - x**103 + 3*x**102 + 2*x**101 - 4*x**100 + 2*x**99 + x**98 + x**97 - x**96 - x**95 + 2*x**94 + 2*x**93 - 2*x**92 + x**91 + x**90 + 2*x**89 - 2*x**88 - x**87 - 2*x**86 - 3*x**85 - x**84 - x**83 - 2*x**82 - 3*x**81 + 2*x**80 - 2*x**79 - 4*x**78 - 3*x**77 + 2*x**76 + x**75 - 3*x**74 - 2*x**73 + x**72 - x**71 + x**70 - 2*x**69 + x**68 + x**67 + x**66 - x**65 - x**64 - x**63 - 4*x**62 + x**61 - x**60 + 2*x**59 - 6*x**58 - 2*x**57 - x**56 + x**55 - 2*x**54 + x**53 - 4*x**52 - 2*x**51 - 3*x**50 + x**49 + 3*x**48 + 4*x**47 + 3*x**46 - x**45 + x**44 - x**43 + 5*x**42 + 3*x**41 + x**40 + x**39 + 2*x**38 + x**37 + x**36 - x**35 + x**34 - x**33 - 3*x**32 + x**31 + x**30 + x**29 + x**28 + x**27 - x**26 - x**25 - x**24 + 2*x**23 + x**22 + x**21 + x**20 - 5*x**19 + x**18 + 2*x**17 + x**16 - 2*x**15 - x**14 - 3*x**13 - x**12 - 3*x**11 + x**10 - 2*x**9 - x**8 - x**7 - x**6 - 3*x**5 - 2*x**4 + 2*x**3 - x**2 + 5*x + 1
with open('out.txt','r') as file:
    exec(file.read().replace('^','**'))
def poly_gcd(a,b):
    if b == 0:
        return a.monic()
    return poly_gcd(b, a % b)
print(poly_gcd(f1,f2))
 
# x-1

Vậy $u-v$ là bội của $p-1$. Từ kết quả này ta có thể factor $n$ bằng cách lấy

$$\gcd (2^{u-v}-1,n)$$

Script:

from sage.all import *
from Crypto.Util.number import *
n = 139330151536291968154362056939191793190070421572607425126412864337960428214252710841790520177640304299848055785679956848879739289740736863858805522021402011784816289402906107827951305153323054170827032255783498256586075556326444324525178342434840530590901685035569099701248356757529471617586874231156794230817
e = 65537
c = 15697592827886645187966669864651924219495308876901271939626110164697706354780388148028280108438305865692406640426779894405286509802915488727759853245713073474018996800135683443416843570824582921878289587458989402877628178914425857255506044374087201140996429025129707759174701127979197532188604260843479601147
import sys
sys.set_int_max_str_digits(0)
P = PolynomialRing(QQ,"x")
x = P.gen()
f1 = -x**136 + 2*x**135 - 3*x**134 + 3*x**133 + 2*x**132 + x**131 + 3*x**130 - 3*x**129 + 3*x**128 + 2*x**127 + 2*x**126 - 3*x**125 - x**124 - 3*x**123 - 2*x**122 + x**121 - x**120 - x**119 + 4*x**118 + x**117 - x**116 - 2*x**115 - 3*x**114 + x**113 + x**112 - 4*x**111 - x**110 + 2*x**109 + 2*x**108 + 3*x**107 - x**106 + 2*x**105 + 2*x**104 - 2*x**103 + 2*x**102 + 2*x**101 - 4*x**100 - 2*x**99 - 3*x**98 + 4*x**97 - 2*x**96 - 2*x**95 - 4*x**94 + x**93 - x**92 + x**91 - x**90 - 3*x**89 - x**88 - 4*x**87 - 2*x**86 - x**85 - x**84 - 3*x**83 + x**82 + x**81 + 4*x**80 - 5*x**79 - 4*x**78 + 2*x**77 - x**76 - x**75 + x**74 - 2*x**73 - 3*x**72 - 3*x**71 + x**70 + 2*x**69 + x**68 - x**67 - 2*x**66 - x**65 - 2*x**64 + x**63 + x**62 - x**61 - x**60 + x**59 - 5*x**58 + x**57 - 3*x**56 + x**55 + 2*x**54 + 5*x**53 - 2*x**52 - 2*x**51 + x**50 + x**49 + 3*x**48 + 4*x**47 + 2*x**46 - x**45 - x**44 + x**43 - 2*x**42 - x**41 + 2*x**40 + 2*x**39 + x**38 + 2*x**37 - 2*x**36 + 3*x**35 + 2*x**34 - 4*x**33 - 3*x**32 + 2*x**31 - 2*x**30 - 3*x**29 - 4*x**28 - 3*x**27 + x**26 + x**25 + 3*x**24 + x**23 + 4*x**22 + 2*x**21 + 2*x**20 + x**19 + x**18 + 3*x**17 + x**16 - 4*x**15 - x**14 + x**13 + x**12 + 2*x**11 + 2*x**10 + x**9 + x**8 + x**7 + 3*x**6 - 2*x**5 + 3*x**4 + 2*x**3 + 2*x**2 + 2*x - 1
f2 = x**136 - 3*x**135 + x**134 + 3*x**133 + 5*x**132 + x**131 + x**130 - 2*x**129 + 2*x**128 + 3*x**127 + x**126 - x**125 + 4*x**124 - 4*x**123 + 2*x**122 + x**121 - x**120 - x**119 + x**118 + x**117 - x**116 - 3*x**115 + 3*x**114 - x**113 + x**112 - x**111 + x**110 - 4*x**109 + x**108 + x**107 + x**106 + 3*x**105 + 7*x**104 - x**103 + 3*x**102 + 2*x**101 - 4*x**100 + 2*x**99 + x**98 + x**97 - x**96 - x**95 + 2*x**94 + 2*x**93 - 2*x**92 + x**91 + x**90 + 2*x**89 - 2*x**88 - x**87 - 2*x**86 - 3*x**85 - x**84 - x**83 - 2*x**82 - 3*x**81 + 2*x**80 - 2*x**79 - 4*x**78 - 3*x**77 + 2*x**76 + x**75 - 3*x**74 - 2*x**73 + x**72 - x**71 + x**70 - 2*x**69 + x**68 + x**67 + x**66 - x**65 - x**64 - x**63 - 4*x**62 + x**61 - x**60 + 2*x**59 - 6*x**58 - 2*x**57 - x**56 + x**55 - 2*x**54 + x**53 - 4*x**52 - 2*x**51 - 3*x**50 + x**49 + 3*x**48 + 4*x**47 + 3*x**46 - x**45 + x**44 - x**43 + 5*x**42 + 3*x**41 + x**40 + x**39 + 2*x**38 + x**37 + x**36 - x**35 + x**34 - x**33 - 3*x**32 + x**31 + x**30 + x**29 + x**28 + x**27 - x**26 - x**25 - x**24 + 2*x**23 + x**22 + x**21 + x**20 - 5*x**19 + x**18 + 2*x**17 + x**16 - 2*x**15 - x**14 - 3*x**13 - x**12 - 3*x**11 + x**10 - 2*x**9 - x**8 - x**7 - x**6 - 3*x**5 - 2*x**4 + 2*x**3 - x**2 + 5*x + 1
with open('out.txt','r') as file:
    exec(file.read().replace('^','**'))
def poly_gcd(a,b):
    if b == 0:
        return a.monic()
    return poly_gcd(b, a % b)
print(poly_gcd(f1,f2))
u = pub[0][1]
v = pub[1][1]
mul = ZZ(int(u-v))
p_mul = pow(2,mul,n) - 1 
p_factor = gcd(p_mul,n)
print(p_factor)
q = n//int(p_factor)
print(q)
phi = (p_factor - 1)*(q-1)
d = pow(e,-1,int(phi))
m = long_to_bytes(pow(c,d,n))
print(m)
# b'ictf{l1ne4r_di0phan+1n3_equat1on!}'

recurring

from secret import flag
from Crypto.Util.number import getPrime, bytes_to_long
 
assert len(flag) == 64
m1 = bytes_to_long(flag[:32].encode())
m2 = bytes_to_long(flag[32:].encode())
 
p = getPrime(256)
def release(m):
    print(hex((m * pow(2, m, p)) % p)[2:].rjust(64, '0'))
 
print(hex(p)[2:])
release(m1)
release(m2)
release(m2-m1)
release(m2+m1)

Phân tích: Ta được cho một số nguyên tố $p$ và hàm release(m). Hàm này tính giá trị của

$$m\times 2^m\mathrm{mod}p$$

Flag ban đầu được chia ra làm 2 phần là $m_1,m_2$. Ta biết giá trị của của $r(m_1),r(m_2),r(m_2+m_1),r(m_2-m_1)$.

Ý tưởng đầu tiên mình nghĩ tới đó là sử dụng Groebner Basis để tìm lại $m_1,m_2$ với 4 biến $m_1,m_2,x,y$ trong đó $x=2^{m_1}$ và $y=2^{m_2}$.

Lúc đầu mình thử làm như này:

from Crypto.Util.number import *
from sage.all import *
hex_p = "afe4dfec75d05b8204f949749dce9d69eaee982528f7e2c177862b4f12b635d9"
m1 = "6d04f0ebde78ca72c0a65629cd6f2cc337319c05b266ed789843ea2bdf11551f"
m2 = "61483d050ad72a0e6dda11e3f683fbac20ab17b4a26615ac3eb4fbaecef519bd"
m2_min_m1 = "13c9395628b7f90ff1675d73cc97ae24ea5c9993366364627d20f9f52b19fabb"
m2_plus_m1 = "75e04f3f38420029fa57934de57b6fb59f9615e4be32eaa4460c57a47c2842ae"
 
p = int(hex_p,16)
print(p)
m1 = int(m1,16)
m2 = int(m2,16)
m2_min_m1 = int(m2_min_m1,16)
m2_plus_m1 = int(m2_plus_m1,16)
 
P = PolynomialRing(GF(p),['m1','m2','x','y'])
m1,m2,x,y = P.gens()
# x = 2^m1
# y= 2^m2
a = P(m1)
b = P(m2)
c = P(m2_min_m1)
d = P(m2_plus_m1)
f1 = m1*x - a
f2 = m2*y - b 
f3 = b-m1*y - x*c 
f4 = x*b + a*y - d 
I = Ideal([f1,f2,f3,f4])
G = I.groebner_basis()
for g in G:
    print(g,"\\n")

Nhưng kết quả thu được

m2^2 + 17595843616801879051555279780002794828875249670711601700507661487574799873779*m2 + 3771965002026442863219550337848419707004585911970202387892150640161102036914*x + 49816143496886072884796993788092798854318326877676082385647724612433977429792 
 
m2*x + m2 + 70609658991743217951142622403375534292696456350503096370615694901705180986142*x + 26242211128115887308791769222276249582980156319678114119895297138877084332843 
 
x^2 + 5369462632810651238072812506818695431232155584785637664457123676761516887726*m2 + 79559135097231088745461412741104874367466799372248185651735720737977696400855*x + 15960740682678432328113261042598440926619528927942116414133891437533463103168 
 
m1 - m2 + 8949476105487870794318790337729340074770343021745089281120025836272515414715*x 
 
y + 79559135097231088745461412741104874367466799372248185651735720737977696400856 
 

Đống này thì không có nhiều ý nghĩa lắm :v chưa kể phương trình cuối thu được $y=1$ nữa.

Hmm mình thử làm lại bằng cách tăng số ẩn lên thay vì dùng các hằng số $a,b,c,d$. Cụ thể với

$$f_3=b-m_{1}y-xc=b-m_1{2}^{m_2}-2^{m_1}c$$

Tức là từ

$$\begin{array}{l}(m_2-m_1)2^{m_2-m_1}=c\\ \to (m_2-m_1)2^{m_2}=c{2}^{m_1}\\ \to (m_2-m_1)y=xc\end{array}$$

Tương tự

$$\begin{gathered} (m_2+m_1)2^{m_2+m_1}=d \\ (m_2+m_1)xy=d \end{gathered}$$

Thử lại nó vẫn y như cũ =))) wtf. Sau đó mình nhận ra là do mình gọi a = P(m1). Thay vì vậy cứ giữ nguyên giá trị là được rồi.

p = int(hex_p,16)
print(p)
a = int(m1,16)
b = int(m2,16)
c = int(m2_min_m1,16)
d = int(m2_plus_m1,16)
 
P = PolynomialRing(GF(p),['m1','m2','x','y'])
m1,m2,x,y = P.gens()
# x = 2^m1
# y= 2^m2
f1 = m1*x - a
f2 = m2*y - b 
f3 = (m2-m1)*y - x*c
f4 = (m2+m1)*x*y -d 
I = Ideal([f1,f2,f3,f4])
G = I.groebner_basis()
for g in G:
    print(g,"\\n")
 
'''
y^2 + 53828782916467504542200882955339970557050732143438843219277667246487732628985*y + 76971113624917467874374510763932482481164404723962833259090635956091918182634 
 
m1 + 12805458084869301436741162678603190080483127809176539734135669470059352907708*y + 32528867516883187857487949723059261844327552313104568787225481106651293715561 
 
m2 + 22262697383559545521980507773828346620016319620359642829633483781693773355345*y + 46003003667765517449760938473289467953970160881105788075261093006892844454785 
 
x + 35421002449310154485122596794018045944043224247978045617818267884232943864562*y + 74810796032202649444010834497993886436367750202863879948661676882751099027184 
'''

Đa thức đầu tiên là đa thức đơn biến theo $y$ nên mình sẽ giải đa thức này trước.

Full solve:

from Crypto.Util.number import *
from sage.all import *
hex_p = "afe4dfec75d05b8204f949749dce9d69eaee982528f7e2c177862b4f12b635d9"
m1 = "6d04f0ebde78ca72c0a65629cd6f2cc337319c05b266ed789843ea2bdf11551f"
m2 = "61483d050ad72a0e6dda11e3f683fbac20ab17b4a26615ac3eb4fbaecef519bd"
m2_min_m1 = "13c9395628b7f90ff1675d73cc97ae24ea5c9993366364627d20f9f52b19fabb"
m2_plus_m1 = "75e04f3f38420029fa57934de57b6fb59f9615e4be32eaa4460c57a47c2842ae"
 
p = int(hex_p,16)
print(p)
a = int(m1,16)
b = int(m2,16)
c = int(m2_min_m1,16)
d = int(m2_plus_m1,16)
 
P = PolynomialRing(GF(p),['m1','m2','x','y'])
m1,m2,x,y = P.gens()
# x = 2^m1
# y= 2^m2
f1 = m1*x - a
f2 = m2*y - b 
f3 = (m2-m1)*y - x*c
f4 = (m2+m1)*x*y -d 
I = Ideal([f1,f2,f3,f4])
G = I.groebner_basis()
for g in G:
    print(g,"\\n")
g1 = y**2 + 53828782916467504542200882955339970557050732143438843219277667246487732628985*y + 76971113624917467874374510763932482481164404723962833259090635956091918182634 
roots = g1.univariate_polynomial().roots()[-1][0]
print(roots)
m2 = b*inverse(ZZ(int(roots)),p) % p 
print(long_to_bytes(int(m2)))
 
# tính m1
 
g2 = m1 + 12805458084869301436741162678603190080483127809176539734135669470059352907708*y + 32528867516883187857487949723059261844327552313104568787225481106651293715561 
g2 = g2(y=roots)
next_roots = g2.univariate_polynomial().roots()[-1][0]
print(next_roots)
m1 = ZZ(int(next_roots))
print(long_to_bytes(m1))
print(long_to_bytes(m1)+long_to_bytes(int(m2)))
# b'ictf{wh4t_ev3n_i5_@_r34l_w0r1d_4ppl1c4ti0n_9OoYVHHxYhQG6teVZXHC}'