2023红明谷WriteUp

发表于 更新于 分类于 ，

比赛的时候脑瘫矩阵除的方向整错了，卡半天没出...最后没时间了

2023红明谷WriteUp

It Takes Two！(赛后)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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，然后：

1
2
3
4
5
6
7
8
9
10
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)\)

1
2
3
4
5
6
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组合就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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)