It takes two

下标模3余2的矩阵都不能取，这里我们取S0，S1，S4，S3进行联立

S1=S0∗A+BS4=S3∗A+B↓A=(S3−S0)−1(S4−S1)S1=S0∗A+BS4=S3∗A+B↓A=(S3−S0)−1(S4−S1)S_1 = S_0*A + B \\ S_4 = S_3*A+B \\ \downarrow\\ A = (S_3-S_0)^{-1} (S_4-S_1)S_1 = S_0*A + B \\ S_4 = S_3*A+B \\ \downarrow\\ A = (S_3-S_0)^{-1} (S_4-S_1)

求出e，e为奇数，二项式定理展开求出e，e为奇数，二项式定理展开

h1≡pe+qe(modn)h2≡pe−qe(modn)↓p=gcd(h1+h2,n)h_1 \equiv p^e +q^e \pmod n \\\\ h_2 \equiv p^e - q^e \pmod n \\\\ \downarrow \\\\ p = gcd(h_1+h_2,n)

求出e，e为奇数，二项式定理展开

e与phi不互素，有限域开方开一下，由于m有padding，大于512bit，所以这里要用crt扩用一下模数

不得不说这里撸矩阵数据有点sb，没什么意思。

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
f = open('C:\\Users\\86153\\Desktop\\ctf chall\\It Takes Two！_8eaea6849fc0a5fc3c2d7c2fee62bef1\\双人成行.txt', 'r')
S0 = [eval(f.readline().replace('[ ', '[').replace('  ', ' ').replace('  ', ' ').replace('  ', ' ').replace(' ', ', ')[2:])]
for i in range(14):
    s = f.readline().replace('  ', ' ').replace('  ', ' ').replace('  ', ' ').replace('[ ', '[').replace(' ', ', ').strip()
    S0.append(eval(s))
s = f.readline().strip().split(', ')
S0.append(eval(s[0].replace('  ', ' ').replace('  ', ' ').replace('  ', ' ').replace('[ ', '[').replace(' ', ', ').strip()))

S1 = [eval(s[1].replace('  ', ' ').replace('  ', ' ').replace('  ', ' ').replace('[ ', '[').replace(' ', ', ').strip())]
for i in range(14):
    s = f.readline().replace('  ', ' ').replace('  ', ' ').replace('  ', ' ').replace('[ ', '[').replace(' ', ', ').strip()
    S1.append(eval(s))
s = f.readline().strip().split(', ')
S1.append(eval(s[0].replace('  ', ' ').replace('  ', ' ').replace('  ', ' ').replace('[ ', '[').replace(' ', ', ').strip()))
for i in range(14):
    f.readline()
s = f.readline().strip().split(', ')
S3 = [eval(s[1].replace('  ', ' ').replace('  ', ' ').replace('  ', ' ').replace('[ ', '[').replace(' ', ', ').strip())]
for i in range(14):
    s = f.readline().replace('  ', ' ').replace('  ', ' ').replace('  ', ' ').replace('[ ', '[').replace(' ', ', ').strip()
    S3.append(eval(s))
s = f.readline().strip().split(', ')
S3.append(eval(s[0].replace('  ', ' ').replace('  ', ' ').replace('  ', ' ').replace('[ ', '[').replace(' ', ', ').strip()))
S4 = [eval(s[1].replace('  ', ' ').replace('  ', ' ').replace('  ', ' ').replace('[ ', '[').replace(' ', ', ').strip())]
for i in range(14):
    s = f.readline().replace('  ', ' ').replace('  ', ' ').replace('  ', ' ').replace('[ ', '[').replace(' ', ', ').strip()
    S4.append(eval(s))
s = f.readline().strip().split(', ')
S4.append(eval(s[0].replace('  ', ' ').replace('  ', ' ').replace('  ', ' ').replace('[ ', '[').replace(' ', ', ').strip()))
f.close()
print('S0 =',S0)
print('S1 =', S1)
print('S3 = ',S3)
print('S4= ',S4)

from Crypto.Util.number import *
n = 126930298936285661712486297662920895162569606037310367763354747221281175771655642407136326621695910623038808779778530112406355314071209370688157872928010633181351390724545013677593062556323119308457918805555312069055604237211117650220178416298165021603211366843640334616217695418858036626587483782452105122653
c = 113627841667808982839757084973426219545127121566516056267404541633803040730885409234473068650543791446730694746311695177758797711077000091232969424826171863685060090359260225102836081852105845748467870581394884564134418376982186965340367386781824886506478939204791426457255483148486730526127180397268053506840
h1 = 87021607670080656750728189202811647321664825322085967432146885995538140004901574830625347954724344331514731852873721100175299656618161173874818773415684739773055620673258848991693719847569489515642296650035465632567910004553054397894647697286044465567405142149926303968235362573821060105908856127568162452912
h2 = 70528801000055618659638315463133504198238507722722570127215098017082205934290867816695737682738831717228470799826957490782948760796844881508632060312080331264474968266753069687287034453036854258618280625776346633340081217397502423530180647548747144401922660710323623212890923488339464759360304751017490144695

m = 16
S0 = matrix(ZZ,m,m,S0)
S1 = matrix(ZZ,m,m,S1)
S3 = matrix(ZZ,m,m,S3)
S4 = matrix(ZZ,m,m,S4)
A = (S3-S0).inverse()*(S4-S1)
e = A.LLL().determinant()

p = gcd(h1+h2,n)
q = n//p
phi = (p-1)*(q-1)
tmp = gcd(e,phi) #21
d = inverse(e//tmp,phi)
msg = int(pow(c,d,n))

PR.<x> = Zmod(p)[]
f = x^21 - msg
res1 = f.roots()

PR.<x> = Zmod(q)[]
f = x^21 - msg
res2 = f.roots()

m = []
for i in res1:
    for j in res2:
        m.append(crt([int(i[0]), int(j[0])], [int(p), int(q)]))
        # print(m)

for i in m:
    if b'flag' in long_to_bytes(i):
        print(long_to_bytes(i))

师傅们太卷了，随便玩玩，线下就交给卷王了。