熊猫杯初赛与决赛 Crypto WriteUp
初赛密码题只有一道，还沾了点猜谜...
绝密文件-代号P
题目代码
import cv2
import numpy as np
from Crypto.Util.number import *
from secret import p, q, c
def arnold(img, shuffle_times, a, b):
r, c, d = img.shape # d: dimension
p = np.zeros(img.shape, np.uint8) # new image
for s in range(shuffle_times): # shuffle times
for i in range(r): # height
for j in range(c): # width
x = (i + b * j) % r # new position
y = ((a * i) + (a * b + 1) * j) % c # new position
p[x, y, :] = img[i, j, :]
img = np.copy(p)
return p
Img_path = "flag_test.png"
Img = cv2.imread(Img_path)
assert isPrime(p) and isPrime(q) and p**2 + \
q**2 == c and c == 179093209181929149953346613617854206675976823277412565868079070299728290913658
Img_arnold = arnold(Img, c, p, q)
cv2.imwrite("flag_enc.png", Img_arnold)
思路
分析得知 arnold()管理图片像素置换，而参数 未知
但在 行有一句断言，给出了关系式
其中， 均为素数
经验使得直接用 SageMath 的二次方根函数，但其返回的解并不为素数，简单尝试 Z3 后也没有得到有效解，偷懒失败，只能另寻方法；于是将 转为高斯整数，寻找分解且进行素性测试，成功分解
分解 | N1gh7ma12e 看了秒了 | Sagemath's Code
from sage.all import *
N = 179093209181929149953346613617854206675976823277412565868079070299728290913658
# 将 N 转换为复数域上的整数
f = ZZ[I](N)
# 获取所有因子
divisors_f = divisors(f)
# 遍历所有因子，寻找满足条件的 p 和 q
for d in divisors_f:
a, b = d.real(), d.imag()
if a**2 + b**2 == N:
p = abs(int(a))
q = abs(int(b))
if is_prime(p) and is_prime(q):
print(f"p = {p}")
print(f"q = {q}")
# break
而复杂度（主要是常数太大）是不能接受的，于是我们寻找周期；懒得推导，使用最朴素的方法：往复加密找重复数据，如果重复即为找到周期
最终找到周期为 ，我们把 拿到 下，这样就能高效找到其原图像
GPT 写的查找周期 | 其中部分常数操作还能优化，但是懒...
# -*- coding: UTF-8 -*-
import cv2
import numpy as np
def arnold_encode(image, a, b):
""" Arnold shuffle for rgb image
Args:
image: input original rgb image
a, b: Arnold parameters
Returns:
Arnold encode image
"""
# 1:创建新图像
arnold_image = np.zeros(shape=image.shape, dtype=image.dtype)
# 2：计算N
h, w = image.shape[0], image.shape[1]
N = h # 或N=w
# 3：遍历像素坐标变换
for ori_x in range(h):
for ori_y in range(w):
# 按照公式坐标变换
new_x = (ori_x + b * ori_y) % N
new_y = (a * ori_x + (a * b + 1) * ori_y) % N
# 像素赋值
arnold_image[new_x, new_y, :] = image[ori_x, ori_y, :]
return arnold_image
def calculate_arnold_period(image, a, b):
""" Calculate the period of Arnold transform
Args:
image: input original rgb image
a, b: Arnold parameters
Returns:
Period of Arnold transform
"""
original_image = image.copy()
transformed_image = arnold_encode(image, a, b)
period = 1
while not np.array_equal(original_image, transformed_image):
transformed_image = arnold_encode(transformed_image, a, b)
period += 1
return period
# 读取图像
img = cv2.imread('flag.png')
# 设置Arnold变换的参数
a, b = 11, 13
# 计算Arnold变换的周期
period = calculate_arnold_period(img, a, b)
print("Arnold变换的周期为:", period)
# 周期和尺寸以及 a, b 参数有关 | 显然, 与次数无关
不过不知哪里的原因（疑似参数错误/代码问题），使得我们在 下的 解密失败
Halois 师傅提示参数不对，于是选择遍历周期。这里有个加速技巧，我们发现每次进行每轮运算都是发生在上轮运算的基础上的（所以不要忘了 .copy()）那我们就可以直接输出图片，使得避免重复计算，最终得到 flag
Exploit
# -*- coding: UTF-8 -*-
import matplotlib.pyplot as plt
import cv2
import numpy as np
from PIL import Image
def arnold_encode(image, shuffle_times, a, b):
""" Arnold shuffle for rgb image
Args:
image: input original rgb image
shuffle_times: how many times to shuffle
Returns:
Arnold encode image
"""
# 1:创建新图像
arnold_image = np.zeros(shape=image.shape)
# 2：计算N
h, w = image.shape[0], image.shape[1]
N = h # 或N=w
# 3：遍历像素坐标变换
for time in range(shuffle_times):
for ori_x in range(h):
for ori_y in range(w):
# 按照公式坐标变换
new_x = (ori_x + b * ori_y) % N
new_y = (a * ori_x + (a * b + 1) * ori_y) % N
# 像素赋值
# print(image[ori_x, ori_y, :])
# print(arnold_image[new_x, new_y, :])
arnold_image[new_x, new_y, :] = image[ori_x, ori_y, :]
image = np.copy(arnold_image)
cv2.imwrite('flag_arnold_encode.png', arnold_image,
[int(cv2.IMWRITE_PNG_COMPRESSION), 0])
return arnold_image
def arnold_decode(image, shuffle_times, a, b):
""" decode for rgb image that encoded by Arnold
Args:
image: rgb image encoded by Arnold
shuffle_times: how many times to shuffle
Returns:
decode image
"""
# 1:创建新图像
decode_image = np.zeros(shape=image.shape)
# 2：计算N
h, w = image.shape[0], image.shape[1]
N = h # 或N=w
# 3：遍历像素坐标变换
for time in range(shuffle_times):
for ori_x in range(h):
for ori_y in range(w):
# 按照公式坐标变换
new_x = ((a * b + 1) * ori_x + (-b) * ori_y) % N
new_y = ((-a) * ori_x + ori_y) % N
decode_image[new_x, new_y, :] = image[ori_x, ori_y, :]
image = np.copy(decode_image)
output_path = f'output/flag_panda_dec_{time + 1}.png'
print(f'writing {time + 1}')
cv2.imwrite(output_path, decode_image, [
int(cv2.IMWRITE_PNG_COMPRESSION), 0])
cv2.imwrite('flag_panda_dec.png', decode_image, [
int(cv2.IMWRITE_PNG_COMPRESSION), 0])
return decode_image
c = 179093209181929149953346613617854206675976823277412565868079070299728290913658
p = 302951519846417861008714825074296492447
q = 295488723650623654106370451762393175957
a, b = p, q
period = 190 # panda
# loop = c % period
# Enc
# img = cv2.imread('flag.png')
# arnold_encode(img, round, 11, 13)
# Dec
img = cv2.imread('flag_panda_enc.png')
arnold_decode(img, period, a, b)
抄了下 1cePeak 之前写过的猫脸变换 代码，稍微改了改
是否能用矩阵快速幂进行加速
决赛
密码题还是只有一道，但质量比初赛好些
OTTO
题目文件
client.py
from Crypto.Util.number import *
from socket import *
from secret import flag
from random import randint
import os
class Oblivious_Transfer():
def __init__(self,host,port):
self.client = socket(AF_INET,SOCK_STREAM)
self.client.connect((host,port))
def recv_para1(self):
self.client.send(b"Give me RSA public key")
self.n1, self.e1 = [int(i) for i in self.client.recv(2048).decode().split('\n')]
print(f"n1 = {self.n1}")
print(f"e1 = {self.e1}")
def recv_para2(self):
self.client.send(b"Give me RSA public key")
self.n2, self.e2 = [int(i) for i in self.client.recv(2048).decode().split('\n')]
print(f"n2 = {self.n2}")
print(f"e2 = {self.e2}")
def transfer1(self):
self.client.send(b"Give me x")
self.x1 = [int(i) for i in self.client.recv(2048).decode().split('\n')]
#self.b = randint(0, 1)
self.k1 = randint(1, self.n1)
#v = (pow(self.k1, self.e1, self.n1) + self.x1[self.b]) % self.n1
#self.client.send(str(v).encode())
self.client.send(str(self.k1).encode())
self.m1 = [int(i) for i in self.client.recv(2048).decode().split('\n')]
print(f"x1 = {self.x1}")
print(f"m1 = {self.m1}")
def transfer2(self):
self.client.send(b"Give me x")
self.x2 = [int(i) for i in self.client.recv(2048).decode().split('\n')]
#self.b = randint(0, 2)
self.k2 = randint(1, self.n2)
#v = (pow(self.k2, self.e2, self.n2) + self.x2[self.b]) % self.n2
#self.client.send(str(v).encode())
self.client.send(str(self.k2).encode())
self.m2 = [int(i) for i in self.client.recv(2048).decode().split('\n')]
print(f"x2 = {self.x2}")
print(f"m2 = {self.m2}")
def close(self):
self.client.close()
OT = Oblivious_Transfer("127.0.0.1", 3333)
try:
OT.recv_para1()
OT.transfer1()
OT.recv_para2()
OT.transfer2()
except:
OT.close()
'''
n1 = 11271769636481167201792947869036553992227573210518633030219178803383349111691460202925344961485630519396298556298353185729133425424986251013234507574460564567554706523170816213012134101324728485027759939177868268886490620475377111559309854971172536072912492915397424686135393068344370029572892256194814415101890916563130328570803042252136741183269883671849873603956230726294410435185435014274882048506167456427852608126478349488290872256072029149848433197043410728314084380999316723835302043375017580973032065204288589969252813061043853493941665391349852606781487173854475699462142399025313772992266906492948457481343
e1 = 3
x1 = [9515572144467353102693379312418710955214891592376652277288115734279056734333735433842688458064791727513305863861235023479729328042101083071837571497065148511710639753106684253478831875505030519724899081680516833763198547371577091213443181418357026416055217075672599840276222008249647801652670192401687584389238718466389175705227396073077728212161850918020236614953688339567726286493333833192267092340593829218909756169268170625006694216875605112065267454732423903631737275763224769800017009573049312062340144144829220945642953262132895898315831950065807615456546917913668105293794016444579372988387899070119905188852, 1892034120103884655057748481218744968570886603116770464293986717297275954889143292301699430583870055377213531296557183365836328935582605537911332825510113738818872104690943672685087209698335996263632901023795785958711815234874952640699783061740546868363055353091127902362863942669248423826595254894726944833887263833323809149528895833061490548685459108186763244472560195193139974039077951072951624681272257192017679341819986081273918682657482308353776379587845617737285532310255049963865808295659252810449272607145518278622472711380742500844288926728181235765064078778435360592122889548497811844849141090787687431691]
m1 = [6016241168918008003676308976207100363787886056310414524692817266526816044605861589333265680725516797725157476881964627121341856194031952078224223712707203444145810288009516867166444302906259425595314875099543375758202468607877956110531218864874778701312073626804583736300557519077867674205675297659120854857631861820501341218694648899186245660067972817620811237063040820817563464199716096063261214384822141532599155146824331413684812783001628935032487957306346174008702256595545954862755182240217576044236510482955069793116079796093428542806091985359518377611477601123779397291583947727903087310885258578166713562127, 5440147501940638137024850606017297210337534677408842136379920848781712980462447118877171733606863014259702536891618925774163741294802932568915293766589177284295703266970860357526016987325665154313719066965567249222221131682926705272951530070261409867083615183965724021333853123572753014882129436586571389423155293377948368049140838120533008304139511510566634163176216591511566937364023875888461854372432939610104040445984493844672803393249479769170488441311099318570005369329133726459281759202562040178972797271360551614266347925035798206639977703364862505440147494902280456168540628714355582075950777307761924432387]
n2 = 13734553138242318628382054742480981343446984988191688662254986243627157625179176065241156011696302206618179554684039418464583144145503176708791330560172722535768542184698066880611009153616062090684034664602606266851696293869899452519578725665110985148196543998607394795861120331954638386927099371326884429866634685812799207305104476545524154915042406729289612658166510017492482175075872284724725422863660604254919264739710275468027278899773185461791413509280443599747367129337405961244474327733607586747648790915994322826728272773783653766560606552040854271186948727715576352830926898026093434984246855183310757045761
e2 = 97
x2 = [13177195145643985162369622498401365177499138154538273683105144116544719466309962486453254331776465984111024384000978936709809981151700299715082451736814113126287335911167543580326081550513657585920705158990979388476560541554360224739435428369017964910714020825020400206978492083575209281469099197416561057829071411270433371623496230236473419547584375357556353533487865301248950946032111351087126169856720042454654832226420081909659506864195491980123873801598391036249027256808516343923925600130215162930220263798094559698140483803320057081107578634042891033997459769087238265628113428210401614417877839230901721993190, 6087668416419425621015217192937881819030086776814461931461321271071632965704332777171900656493718038405650018773284906392054768417180630397123329675678721202895156479498192567976488835849134098984496538043518882047967632186092698690848611693438041802874429890978003588117644629011459601875026269618173841010295947617126507755463408314735056141532883079433786701501106150571651039383128288126543960497006195953471865106598447153220760899089004772873548377773392286170683824466138705674297182685522941020265251198373775479428578340308681511331066572161101438312245374528237712280314548370382811282427949209246902963620]
m2 = [11290088192896104506026832060270527943714366880404242912266063784753126354203886059118599709669598729492075209588587167909865752372998401224088902550832115846922950445881033989219174580290127597931540821558287876108098891608071532321402919702498057050600028620041146727752759548708970938132742356572135342729734097482396575542041618189798845322991442136889598236510334924501541556553680371235401907549785446331539870340463389985682807901483008146184213709636864164058105540385607059315722869586747109233390594619151596441257862747687967610987191500891685999700118692739878206205390683771336361205725982750841624412918, 13297923293604079904865691526854689771243166342933215235463378384491550135554561777664960232137603383114093048818781509117309259419714741409995439792770006827393488190799203124259891829424051546917028377316926517036925667257317044743094940629506839160375855343993956627134396913916798323848609907197075057202723651440732344941034655107043117917579554777531225809712600877171322938484588653102197119270286456014097076345973054360242768465566465700893203405936053400775455573738231554838583225080952941328332237618198730448032110880353626965942852413612822837453591096974975301303294918593974328897924663396162439300901]
'''
server.py
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from socket import *
from secret import flag
from random import randint
from gmpy2 import invert, gcd
import os
length = len(flag)
flag1 = flag[:length//2]
flag2 = flag[length//2:]
class Oblivious_Transfer():
def __init__(self,host,port):
self.server = socket(AF_INET,SOCK_STREAM)
self.server.bind((host,port))
self.server.listen(5)
self.connection, self.addr = self.server.accept()
def keygen1(self):
while True:
p = getPrime(1024)
q = getPrime(1024)
e = 3
n = p * q
phi = (p-1)*(q-1)
if gcd(e, phi) == 1:
d = invert(e, phi)
self.n1 = n
self.e1 = e
self.d1 = d
return
def keygen2(self):
while True:
p = getPrime(1024)
q = getPrime(1024)
e = 97
n = p * q
phi = (p-1)*(q-1)
if gcd(e, phi) == 1:
d = invert(e, phi)
self.n2 = n
self.e2 = e
self.d2 = d
return
def gen_msg1(self):
self.msg1 = [bytes_to_long(flag1), bytes_to_long(os.urandom(length//2))]
def gen_msg2(self):
self.c = [randint(1, self.n2) for i in range(2)]
self.msg2 = [bytes_to_long(pad(flag2, 256)), self.c[0] * bytes_to_long(pad(flag2, 256)) + self.c[1], bytes_to_long(os.urandom(length//2))]
print(f"c = {self.c}")
def send_para1(self):
self.connection.recv(2048)
self.connection.send(str(self.n1).encode() + b'\n' + str(self.e1).encode())
def send_para2(self):
self.connection.recv(2048)
self.connection.send(str(self.n2).encode() + b'\n' + str(self.e2).encode())
def transfer1(self):
self.connection.recv(2048)
self.x1 = [randint(1, self.n1) for i in range(2)]
self.connection.send(str(self.x1[0]).encode() + b'\n' + str(self.x1[1]).encode())
v1 = int(self.connection.recv(2048).decode())
self.m1 = [(pow(v1-self.x1[i], self.d1, self.n1) + self.msg1[i]) % self.n1 for i in range(2)]
self.connection.send(str(self.m1[0]).encode() + b'\n' + str(self.m1[1]).encode())
def transfer2(self):
self.connection.recv(2048)
self.x2 = [randint(1, self.n2) for i in range(2)]
self.connection.send(str(self.x2[0]).encode() + b'\n' + str(self.x2[1]).encode())
v2 = int(self.connection.recv(2048).decode())
print(f"v2 = {v2}")
self.m2 = [(pow(v2-self.x2[i], self.d2, self.n2) + self.msg2[i]) % self.n2 for i in range(2)]
self.connection.send(str(self.m2[0]).encode() + b'\n' + str(self.m2[1]).encode())
def close(self):
self.server.close()
OT = Oblivious_Transfer("127.0.0.1", 3333)
try:
OT.keygen1()
OT.gen_msg1()
OT.send_para1()
OT.transfer1()
OT.keygen2()
OT.gen_msg2()
OT.send_para2()
OT.transfer2()
except:
OT.close()
'''
c = [2022192084163865871637311910190343009806372281260940433264866710576717827000158190013454140869282023553794168299850642713592857046603901804667940047118351375526819434245929363285575321841139031828203969945166801239181091856967945653548638281912992865859782543006093627628764190870048182733564610346559175554351590756572067638680287831888951790549721647896128434643949839982021154615115260457999786151004733151130820602433196485192091297036565179140159868992152310647228915941684271200707824836388347153359567736106504118830380335535571497974547855922884383469780130087191722420344937756494122346487016566419242463836, 12061552506303089886042745624408653176981782225020423963019198845243742139258023869466665561793608045001319021047887667664174994585869340313951796548176269089114160706384746387983277073112591591489643976442622321188641202129622786824693293150098394659731881683945896467114040450861544761586718952331369001004695294268894235852363740831011251046468659589566501557902013744612394168830044111638387497950139803719642714677584615407052702028855832555056064595619857064644590245323361565888668910950428292688990851782269368022834514035734196544300120061524133712573144079293439936276463509498262847888571155492592609260783]
v2 = 9556276713294185634675025767802869929252472183681399946558259127635089951399817649411122499036657904914953334191629273438214371861747375930220930123236040473592720606113932507502872050616210539047321307830911690987874269273684519795136175561107095807358688729096068293698083610276557300656827563421114987688852668095314933405088107467416611145574761738655696672560862813137945205091832198111391817949039251665825121659323773270436391580589841573178391221735428798318886660824941824216932260996644044749424023313841093829840154123672637916095508058599701154434489213872161152359221137791753598589303710126033417598315
'''
Exploit
Part 1
难点在于读懂 hint（题目代码注释掉的部分）
# https://github.com/defund/coppersmith
from sage.all import *
import itertools
def small_roots(f, bounds, m=1, d=None):
if not d:
d = f.degree()
if isinstance(f, Polynomial):
x, = polygens(f.base_ring(), f.variable_name(), 1)
f = f(x)
R = f.base_ring()
N = R.cardinality()
f /= f.coefficients().pop(0)
f = f.change_ring(ZZ)
G = Sequence([], f.parent())
for i in range(m+1):
base = N ^ (m-i) * f ^ i
for shifts in itertools.product(range(d), repeat=f.nvariables()):
g = base * prod(map(power, f.variables(), shifts))
G.append(g)
B, monomials = G.coefficient_matrix()
monomials = vector(monomials)
factors = [monomial(*bounds) for monomial in monomials]
for i, factor in enumerate(factors):
B.rescale_col(i, factor)
B = B.dense_matrix().LLL()
B = B.change_ring(QQ)
for i, factor in enumerate(factors):
B.rescale_col(i, 1/factor)
H = Sequence([], f.parent().change_ring(QQ))
for h in filter(None, B*monomials):
H.append(h)
I = H.ideal()
if I.dimension() == -1:
H.pop()
elif I.dimension() == 0:
roots = []
for root in I.variety(ring=ZZ):
root = tuple(R(root[var]) for var in f.variables())
roots.append(root)
return roots
return []
n1 = 11271769636481167201792947869036553992227573210518633030219178803383349111691460202925344961485630519396298556298353185729133425424986251013234507574460564567554706523170816213012134101324728485027759939177868268886490620475377111559309854971172536072912492915397424686135393068344370029572892256194814415101890916563130328570803042252136741183269883671849873603956230726294410435185435014274882048506167456427852608126478349488290872256072029149848433197043410728314084380999316723835302043375017580973032065204288589969252813061043853493941665391349852606781487173854475699462142399025313772992266906492948457481343
e1 = 3
x1 = [9515572144467353102693379312418710955214891592376652277288115734279056734333735433842688458064791727513305863861235023479729328042101083071837571497065148511710639753106684253478831875505030519724899081680516833763198547371577091213443181418357026416055217075672599840276222008249647801652670192401687584389238718466389175705227396073077728212161850918020236614953688339567726286493333833192267092340593829218909756169268170625006694216875605112065267454732423903631737275763224769800017009573049312062340144144829220945642953262132895898315831950065807615456546917913668105293794016444579372988387899070119905188852,
1892034120103884655057748481218744968570886603116770464293986717297275954889143292301699430583870055377213531296557183365836328935582605537911332825510113738818872104690943672685087209698335996263632901023795785958711815234874952640699783061740546868363055353091127902362863942669248423826595254894726944833887263833323809149528895833061490548685459108186763244472560195193139974039077951072951624681272257192017679341819986081273918682657482308353776379587845617737285532310255049963865808295659252810449272607145518278622472711380742500844288926728181235765064078778435360592122889548497811844849141090787687431691]
m1 = [6016241168918008003676308976207100363787886056310414524692817266526816044605861589333265680725516797725157476881964627121341856194031952078224223712707203444145810288009516867166444302906259425595314875099543375758202468607877956110531218864874778701312073626804583736300557519077867674205675297659120854857631861820501341218694648899186245660067972817620811237063040820817563464199716096063261214384822141532599155146824331413684812783001628935032487957306346174008702256595545954862755182240217576044236510482955069793116079796093428542806091985359518377611477601123779397291583947727903087310885258578166713562127,
5440147501940638137024850606017297210337534677408842136379920848781712980462447118877171733606863014259702536891618925774163741294802932568915293766589177284295703266970860357526016987325665154313719066965567249222221131682926705272951530070261409867083615183965724021333853123572753014882129436586571389423155293377948368049140838120533008304139511510566634163176216591511566937364023875888461854372432939610104040445984493844672803393249479769170488441311099318570005369329133726459281759202562040178972797271360551614266347925035798206639977703364862505440147494902280456168540628714355582075950777307761924432387]
# flag_index = 0
# flag1_c = m1[0]
# flag1_x1 = x1[0]
# k := 1 -- n \
# 发 v(实际是 k) 接收 v
# v = (pow(self.k1, self.e1, self.n1) + self.x1[self.b]) % self.n1
# m_1 = (v1 - x1) ^ d1 % n1 + msg1 % n1
# v = (power_mod(k1, e1, n1) + x1[?]) % n1
# m_1 =
PR = PolynomialRing(Zmod(n1), 2, 'x, y')
x, y = PR.gens() # 不 gens() 会导致可能找不到变量..
msg1 = [x, y]
k1 = m1[1] - msg1[1]
f = (m1[0] - msg1[0]) ** e1 - (k1 ** e1 + x1[1] - x1[0])
bounds = (2**168, 2**168) # 预估的根(msg_1)的范围
root = small_roots(f, bounds, m=6, d=4)
print(f'root = {root}')
for i in root[0]:
try:
flag1 = bytes.fromhex(hex(i)[2:])
print(f'flag1 = {flag1}')
except Exception as e:
print(f'Error: {e}')
print(f'Error root = {i}')
Part 2
找到线性关系，用多项式 GCD 秒了。难点和 Part 1 一样，在于读懂 hint
self.m2 = [(pow(v2-self.x2[i], self.d2, self.n2) +
self.msg2[i]) % self.n2 for i in range(2)]
SageMath's Code
from sage.all import *
from Crypto.Util.number import long_to_bytes
n2 = 13734553138242318628382054742480981343446984988191688662254986243627157625179176065241156011696302206618179554684039418464583144145503176708791330560172722535768542184698066880611009153616062090684034664602606266851696293869899452519578725665110985148196543998607394795861120331954638386927099371326884429866634685812799207305104476545524154915042406729289612658166510017492482175075872284724725422863660604254919264739710275468027278899773185461791413509280443599747367129337405961244474327733607586747648790915994322826728272773783653766560606552040854271186948727715576352830926898026093434984246855183310757045761
e2 = 97
x2 = [13177195145643985162369622498401365177499138154538273683105144116544719466309962486453254331776465984111024384000978936709809981151700299715082451736814113126287335911167543580326081550513657585920705158990979388476560541554360224739435428369017964910714020825020400206978492083575209281469099197416561057829071411270433371623496230236473419547584375357556353533487865301248950946032111351087126169856720042454654832226420081909659506864195491980123873801598391036249027256808516343923925600130215162930220263798094559698140483803320057081107578634042891033997459769087238265628113428210401614417877839230901721993190, 6087668416419425621015217192937881819030086776814461931461321271071632965704332777171900656493718038405650018773284906392054768417180630397123329675678721202895156479498192567976488835849134098984496538043518882047967632186092698690848611693438041802874429890978003588117644629011459601875026269618173841010295947617126507755463408314735056141532883079433786701501106150571651039383128288126543960497006195953471865106598447153220760899089004772873548377773392286170683824466138705674297182685522941020265251198373775479428578340308681511331066572161101438312245374528237712280314548370382811282427949209246902963620]
m2 = [11290088192896104506026832060270527943714366880404242912266063784753126354203886059118599709669598729492075209588587167909865752372998401224088902550832115846922950445881033989219174580290127597931540821558287876108098891608071532321402919702498057050600028620041146727752759548708970938132742356572135342729734097482396575542041618189798845322991442136889598236510334924501541556553680371235401907549785446331539870340463389985682807901483008146184213709636864164058105540385607059315722869586747109233390594619151596441257862747687967610987191500891685999700118692739878206205390683771336361205725982750841624412918, 13297923293604079904865691526854689771243166342933215235463378384491550135554561777664960232137603383114093048818781509117309259419714741409995439792770006827393488190799203124259891829424051546917028377316926517036925667257317044743094940629506839160375855343993956627134396913916798323848609907197075057202723651440732344941034655107043117917579554777531225809712600877171322938484588653102197119270286456014097076345973054360242768465566465700893203405936053400775455573738231554838583225080952941328332237618198730448032110880353626965942852413612822837453591096974975301303294918593974328897924663396162439300901]
c = [2022192084163865871637311910190343009806372281260940433264866710576717827000158190013454140869282023553794168299850642713592857046603901804667940047118351375526819434245929363285575321841139031828203969945166801239181091856967945653548638281912992865859782543006093627628764190870048182733564610346559175554351590756572067638680287831888951790549721647896128434643949839982021154615115260457999786151004733151130820602433196485192091297036565179140159868992152310647228915941684271200707824836388347153359567736106504118830380335535571497974547855922884383469780130087191722420344937756494122346487016566419242463836, 12061552506303089886042745624408653176981782225020423963019198845243742139258023869466665561793608045001319021047887667664174994585869340313951796548176269089114160706384746387983277073112591591489643976442622321188641202129622786824693293150098394659731881683945896467114040450861544761586718952331369001004695294268894235852363740831011251046468659589566501557902013744612394168830044111638387497950139803719642714677584615407052702028855832555056064595619857064644590245323361565888668910950428292688990851782269368022834514035734196544300120061524133712573144079293439936276463509498262847888571155492592609260783]
v2 = 9556276713294185634675025767802869929252472183681399946558259127635089951399817649411122499036657904914953334191629273438214371861747375930220930123236040473592720606113932507502872050616210539047321307830911690987874269273684519795136175561107095807358688729096068293698083610276557300656827563421114987688852668095314933405088107467416611145574761738655696672560862813137945205091832198111391817949039251665825121659323773270436391580589841573178391221735428798318886660824941824216932260996644044749424023313841093829840154123672637916095508058599701154434489213872161152359221137791753598589303710126033417598315
PR = PolynomialRing(Zmod(n2), 'x')
x = PR.gen()
msg2 = [x, c[0] * x + c[1]]
f1 = (m2[0] - msg2[0]) ** e2 - (v2 - x2[0])
f2 = (m2[1] - msg2[1]) ** e2 - (v2 - x2[1])
poly_gcd = lambda g1, g2: g1.monic() if not g2 else poly_gcd(g2, g1%g2)
final = poly_gcd(f1, f2)
# final = fast_polynomial_gcd(f1, f2)
# m = -f.coefficients()[0] % n2
print(f'final: {final}')
flag = -final[0]
print(long_to_bytes(int(flag)))
# final: x + 6614822911828648841029566614609692232717566785431897706995761713358691828281048883885460997534713812928885427376052969053113035408201570098963665047166474161596931074245439587004827659080053168450904636891335870984666098971532036063307641238076861938065930001774323573153456751609422951477990714901749314390735306087634151973365560079869808509156531935955315619080678040305880088357221350311823549249960413722702171840098647622157653435215815139586482418316879783405057079364458768390721542460619040059466985689320265237243120479062052511143507688727497844100712330669491175130677443361943090661187554989173615114774
# b'8f-4145-87d8051cc3c5}\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb\xeb'