CTFshow 七夕杯

ctfshow 2022 七夕杯 Luck7

f(x) = x**3 - 2*x**2*y + 4*x*y - y**2 - 2
g(y) = 2*x*y**2 + x*y - y**3 - 2

exp

#sage
from sage.matrix.matrix2 import Matrix

P.<x,y> = PolynomialRing(ZZ)
f = x**3 - 2*x**2*y + 4*x*y - y**2 - 2
g = 2*x*y**2 + x*y - y**3 - 2
syl_x = f.sylvester_matrix(g,x)
syl_y = f.sylvester_matrix(g,y)
print(syl_x)
print(syl_y)
det = Matrix.determinant(syl_x)
r = det.univariate_polynomial()
rr = r.roots()
print(rr)
#
[        1      -2*y       4*y  -y^2 - 2]
[2*y^2 + y  -y^3 - 2         0         0]
[        0 2*y^2 + y  -y^3 - 2         0]
[        0         0 2*y^2 + y  -y^3 - 2]
[          -1 -2*x^2 + 4*x      x^3 - 2            0            0]
[           0           -1 -2*x^2 + 4*x      x^3 - 2            0]
[           0            0           -1 -2*x^2 + 4*x      x^3 - 2]
[          -1          2*x            x           -2            0]
[           0           -1          2*x            x           -2]
[(1, 1)]

from Crypto.Util.number import bytes_to_long, getPrime
from secret import flag

l = len(flag)
assert l == 56
x = bytes_to_long(flag[:l//2])
y = bytes_to_long(flag[l//2:])

p = getPrime(1024)
e = 0x10001

x = pow(x, e, p)
y = pow(y, e, p)

a = (7 * x + x * y + 77 * y ** 7) % p
b = (x ** 7 + 777 * y) % p

print(f'p = {p}')
print(f'a = {a}')
print(f'b = {b}') 

# p = 160676801612994301361202519503059426958636739446670462398261976532859847492256822690640058297338763725128097587993428329580105931247817467950370089691908132361316857330836120708767594061772979871315614755470773991633234068651435625372887767258609941208307491359777513843529144444836847722372845148836203335627
# a = 30318995909014771647618268716833486449002423009996671727903532973647046764624121316716790986592523978549131384964872198795285872746623966910764159262479160147876027157581577141632378119375701270068263640642243000011932466519579133761464923463402462812787531220639360431295348786697861069940729757964584951972
# b = 51036630170491152581994259808984114372634216659979376101433163181132141957563047348137651942358538069256102718534893846618166559129391336639526588292370462975735415885732360576961407017238385374280336346614960555565504032093702784952402038043052556719843691506943605133036720410419999467125928578673380637828

exp

from sage.matrix.matrix2 import Matrix
p = 160676801612994301361202519503059426958636739446670462398261976532859847492256822690640058297338763725128097587993428329580105931247817467950370089691908132361316857330836120708767594061772979871315614755470773991633234068651435625372887767258609941208307491359777513843529144444836847722372845148836203335627
a = 30318995909014771647618268716833486449002423009996671727903532973647046764624121316716790986592523978549131384964872198795285872746623966910764159262479160147876027157581577141632378119375701270068263640642243000011932466519579133761464923463402462812787531220639360431295348786697861069940729757964584951972
b = 51036630170491152581994259808984114372634216659979376101433163181132141957563047348137651942358538069256102718534893846618166559129391336639526588292370462975735415885732360576961407017238385374280336346614960555565504032093702784952402038043052556719843691506943605133036720410419999467125928578673380637828

P.<x,y> = PolynomialRing(Zmod(p))
f = 7 * x + x * y + 77 * y ** 7
g = x ** 7 + 777 * y
syl_x = f.sylvester_matrix(g,x)
syl_y = f.sylvester_matrix(g,y)
print(syl_x)
print(syl_y)
det = Matrix.determinant(syl_y)
r = det.univariate_polynomial()
rr = r.roots()
print(rr)
#[(124677607092699803557245096919169398136580412155378593939051149355949509639134172159374552671328477192344918077474528677254293365365056476381340047245166533034614547983910284650487898068076271628784742627193559227237521199903328795912044690896480268380435664902608764379396376511419616765760368085289853921946, 1), (101197808656260953767935150929587022842527379136028020550077900827970982860361893217477657450620199373260292804196998852119741853953064360608206142874222917565476755760479763120058651175413539739510401608563715176772205861690365915918645182169533799211493313257092937896040771679648446929396445817904328114154, 1), (82982156164889265547114487000414450511619571181382717620369100250166868953604720806049031711409782996767220234103576215405094816243896996877989617172487417746586106859764617150590513989026059108165373088563612854774167077702575816200543039956224155092922423771253682291949643149787308740168764992420196392137, 1), (74241344290627119024345152054975965488805953398113351801413147987083499826635415394563128639239984073380745450306356089509314982021764857351604479344139511952856961090121077508346844301237256442188282621763603850090015846665801510279074142017141443712145897922169511153895396409335459042954293454522763316940, 1), (25557687121306522994745703930012851402037132517158036418494527364948244097623864611327847656965293371153147932839950372173050082034699668147654540828773542254076093680525862804415287622552715758629050501128020978362090344991945300772363640503601322787556617555549161445446003116123935272807916741925993063990, 1)]

x,_ = zip(*rr)
y = [((b - i**7)*inverse_mod(777,p))%p for i in x]
print(y)
#[30602266914964209224638817218762050988947232921227623176684620247431173494712312284186908124534521688334805308860486647001553783515417133911989769473040987337400163922906963242723841271688854264099754304325369414185733824210330000328051172423305974130068487952657718522585142033422945968983719066363146640016, 77213293767491230492860115777251177313392946798921770484126738681801029335139715365372291981480195053456501831028224413865286897611037169682397380381929062917672505578574952404526751805370691255131187067280119827131064074686524786101284346472030379058450580974269726158568516055363637040666472777588946575018, 62271581697487304005531089929367480957324711152230085432379204102763672941723460816985224422705850564580722496375394200363563224416152187387007099617206594848750405894692511846007876648799784545662207361978711150529867739038396344755201446896298306534649109714533518618696222324251704881278950228598159045825, 150922743998103953055350313504987422655606827385642281931652890016472474620040801549783712805987591069097288176204082082105906534894014711164122461779643282427221706756887221089818316644298511221593284404724618746764829152373997559838769047063911176932744097918416123041936362094672205463135712919705863561828, 69464814887159232676614236201633352678213755273455618830085792854565099627331794170875052412372208057230131744850310870640910845756550741925500748865058192147351078471077095468538955670357124767826190339710021993394191397041781945555294385090507101867745587003795447760094601944847883122438067538626075652503]
x,_= zip(*x)
d = gmpy2.invert(e,p-1)
for i in range(len(x)):
    m1 = pow(x[i],d,p)
    m2 = pow(y[i],d,p)
    try:
        print(long_to_bytes(m1),long_to_bytes(m2))
    except:
        pass
#b'ctfshow{1t_Is_S0o0o0o0o_3A5Y' b'_70_50Lv3_m0duLaR_EqUAt10nS}'