2023红明谷WriteUp
It Takes Two!(赛后)
比赛的时候脑瘫矩阵除的方向整错了,卡半天没出...最后没时间了
#task
from sage.all import *
from Crypto.Util.number import *
from os import urandom
from secret import flag
n = 16
bound = 2^15
A = [ZZ.random_element(-bound, bound) for _ in range(n*n)]
A = Matrix(ZZ, n, n, A)
B = [ZZ.random_element(-bound, bound) for _ in range(n*n)]
B = Matrix(ZZ, n, n, B)
res = []
for i in range(5):
bound = 2^15
S = [ZZ.random_element(-bound, bound) for _ in range(n*n)]
S = Matrix(ZZ, n, n, S)
tmp = []
for i in range(0, 60):
S = S* A + B
bound = 2^(int(S[0, 0]).bit_length())
if i % 3 == 2:
tmp.append(Matrix(ZZ,n,n,[ZZ.random_element(-bound, bound) for _ in range(n*n)]))
continue
tmp.append(S)
res.append(tmp)
e = A.LLL().determinant()
p = getPrime(512)
q = getPrime(512)
n = p * q
m = bytes_to_long(urandom(int(n).bit_length() // 8 - len(flag) - 1) + flag)
c = pow(m, e, n)
h1 = pow(p+q, e, n)
h2 = pow(p-q, e, n)
f = open('双人成行.txt', 'w')
f.writelines(str(res)+'\n')
f.writelines(str(n)+'\n')
f.writelines(str(c)+'\n')
f.writelines(str(h1)+'\n')
f.writelines(str(h2)+'\n')
f.close()
读取数据:
替换了一下'双人成行.txt'里的逗号,换成\n
,然后:
f = open('双人成行.txt', 'r')
res = []
for a in range(300):
tmp = []
for aa in range(16):
line = f.readline().replace('[', '').replace(']', '')
line = [int(i) for i in line.split()]
tmp.append(line)
res.append(tmp)
f.close()
读代码发现第三组矩阵被替换成了随机值,所以选取第1,2,4,5组矩阵,运算得到A。
\(S_2=S_1*A+B\)
\(S_5=S_4*A+B\)
\(A = (S_4-S_1)^{-1}*(S_5-S_2)\)
s1 = Matrix(ZZ,res[0])
s2 = Matrix(ZZ,res[1])
s4 = Matrix(ZZ,res[3])
s5 = Matrix(ZZ,res[4])
a = ((s4-s1)^(-1))*(s5-s2)
e = a.LLL().determinant()
再求\(p,q\),对\(h1,h2\)稍作转化得到
\(h1 \equiv p^e \pmod{q}\)
\(h2\equiv p^e\pmod{q}\)
两式相减得到\(h1-h2\equiv 0 \pmod{q}\)
故对\(n\)和\((h1-h2)\)取最大公约数即可得到\(q\)
随后发现\(gcd(e,\phi)=21\),有限域开根求一下,再CRT组合就好。
from gmpy2 import *
from Crypto.Util.number import *
n = 126930298936285661712486297662920895162569606037310367763354747221281175771655642407136326621695910623038808779778530112406355314071209370688157872928010633181351390724545013677593062556323119308457918805555312069055604237211117650220178416298165021603211366843640334616217695418858036626587483782452105122653
c = 113627841667808982839757084973426219545127121566516056267404541633803040730885409234473068650543791446730694746311695177758797711077000091232969424826171863685060090359260225102836081852105845748467870581394884564134418376982186965340367386781824886506478939204791426457255483148486730526127180397268053506840
h1 = 87021607670080656750728189202811647321664825322085967432146885995538140004901574830625347954724344331514731852873721100175299656618161173874818773415684739773055620673258848991693719847569489515642296650035465632567910004553054397894647697286044465567405142149926303968235362573821060105908856127568162452912
h2 = 70528801000055618659638315463133504198238507722722570127215098017082205934290867816695737682738831717228470799826957490782948760796844881508632060312080331264474968266753069687287034453036854258618280625776346633340081217397502423530180647548747144401922660710323623212890923488339464759360304751017490144695
p = gcd(h1+h2, n)
q = n//p
phi = (p-1)*(q-1)
d = inverse(e//21, phi)
c_ = pow(c, d, n)
PR.<x> = PolynomialRing(Zmod(p))
f = x^21-c_
f = f.monic()
root_p = f.roots()
PR.<x> = PolynomialRing(Zmod(q))
f = x^21-c_
f = f.monic()
root_q = f.roots()
for i in root_p:
for j in root_q:
m = CRT([int(i[0]), int(j[0])], [p, q])
flag = long_to_bytes(m)
#print(flag)
if b'flag' in flag:
print(flag)
标签:Matrix,谷杯,WriteUp,红明,h1,bound,h2,ZZ,res
From: https://www.cnblogs.com/sCh3n/p/17498232.html