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
| from Crypto.Util.number import long_to_bytes
p = 219054411990148289470292997530776820099
xs = [8491960647856250964788524618271700685, 71795891239628473345986467501840944053, 156002976606013829072222795906955056490, 53087364639737298031576707773864444526, 168655802716010735307052122673425704476]
cs = [8121914627778545197804323606326110761, 35945001560092599768837547895125753710, 145323007892377441978764394884664054314, 151317673926254356634302814424738532048, 66863154042339327032435896661285289022]
def mod_inv(a, p):
return pow(a, p-2, p)
def gauss_elim(A, b, p):
n = len(A)
M = [A[i] + [b[i]] for i in range(n)]
for k in range(n):
pivot = k
for i in range(k, n):
if M[i][k] != 0:
pivot = i
break
else:
return None
M[k], M[pivot] = M[pivot], M[k]
inv_pivot = mod_inv(M[k][k], p)
for j in range(k, n+1):
M[k][j] = (M[k][j] * inv_pivot) % p
for i in range(n):
if i == k:
continue
factor = M[i][k]
for j in range(k, n+1):
M[i][j] = (M[i][j] - factor * M[k][j]) % p
return [M[i][n] for i in range(n)]
n = 5
A = []
for i in range(n):
row = []
for j in range(n):
row.append(pow(xs[i], j, p))
A.append(row)
coeff = gauss_elim(A, cs, p)
flag = b''
for c in coeff:
flag += long_to_bytes(c)
print(flag.decode())
|
