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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
"""errata solver: Berlekamp-Welch over GF(257), deg<=15, exactly 32 errors/lane."""
import csv, hashlib, sys
P = 257
def inv(a):
return pow(a % P, P - 2, P)
def gauss(A, b):
"""Solve A x = b over GF(P). A: list of rows (len m), b: len n. Returns x or None."""
n = len(A); m = len(A[0])
M = [row[:] + [b[i]] for i, row in enumerate(A)]
piv_cols = []
r = 0
for c in range(m):
piv = None
for i in range(r, n):
if M[i][c] % P:
piv = i; break
if piv is None:
continue
M[r], M[piv] = M[piv], M[r]
iv = inv(M[r][c])
M[r] = [(v * iv) % P for v in M[r]]
for i in range(n):
if i != r and M[i][c] % P:
f = M[i][c]
M[i] = [(M[i][j] - f * M[r][j]) % P for j in range(m + 1)]
piv_cols.append(c)
r += 1
if r == n:
break
for i in range(r, n):
if all(M[i][j] % P == 0 for j in range(m)) and M[i][m] % P != 0:
return None
if len(piv_cols) < m:
pass
x = [0] * m
for i, c in enumerate(piv_cols):
x[c] = M[i][m] % P
return x
def polymul(a, b):
res = [0] * (len(a) + len(b) - 1)
for i, ai in enumerate(a):
if ai:
for j, bj in enumerate(b):
res[i + j] = (res[i + j] + ai * bj) % P
return res
def polydivmod(a, b):
a = a[:]
db = len(b) - 1
ib = inv(b[-1])
q = [0] * (len(a) - db)
for i in range(len(a) - 1, db - 1, -1):
coef = (a[i] * ib) % P
q[i - db] = coef
if coef:
for j in range(db + 1):
a[i - db + j] = (a[i - db + j] - coef * b[j]) % P
rem = a[:db]
while q and q[-1] == 0:
q.pop()
return q, rem
def polyeval(f, x):
v = 0
for c in reversed(f):
v = (v * x + c) % P
return v
def berlekamp_welch(pts, k, e):
"""pts: list of (x,y). k = number of coeffs (deg+1). e = num errors."""
n = len(pts)
degQ = k - 1 + e
nQ = degQ + 1
nE = e
m = nQ + nE
A = []; b = []
for (x, y) in pts:
row = [0] * m
xp = 1
for j in range(nQ):
row[j] = xp
xp = (xp * x) % P
xp = 1
for j in range(nE):
row[nQ + j] = (-y * xp) % P
xp = (xp * x) % P
A.append(row)
b.append((y * xp) % P)
sol = gauss(A, b)
if sol is None:
return None
Q = sol[:nQ]
Ecol = sol[nQ:] + [1]
f, rem = polydivmod(Q, Ecol)
if any(r % P for r in rem):
return None
return f
def main():
path = sys.argv[1] if len(sys.argv) > 1 else "samples.csv"
lanes = {0: [], 1: [], 2: []}
with open(path, newline="") as fh:
rd = csv.reader(fh)
header = next(rd)
for row in rd:
if not row or not row[0].strip():
continue
l, x, y = int(row[0]), int(row[1]), int(row[2])
lanes[l].append((x, y))
for l in lanes:
print(f"lane {l}: {len(lanes[l])} points", file=sys.stderr)
T = b""
for l in (0, 1, 2):
pts = lanes[l]
found = None
for e in (32, 31, 33, 30, 34, 28, 36, 24, 40, 20, 48):
f = berlekamp_welch(pts, 16, e)
if f is None:
continue
good = sum(1 for (x, y) in pts if polyeval(f, x) == y)
print(f"lane {l}: e={e} deg={len(f)-1} matches={good}/{len(pts)}", file=sys.stderr)
if good >= len(pts) - e and len(f) - 1 <= 15:
found = f
break
if found is None:
print(f"lane {l}: FAILED", file=sys.stderr)
return
f = found[:]
while len(f) < 16:
f.append(0)
print(f"lane {l} coeffs: {f}", file=sys.stderr)
for c in f:
T += c.to_bytes(2, "big")
print("T =", T.hex(), file=sys.stderr)
K = hashlib.sha256(b"ERRATA/DEVIL/V1" + T).digest()
print("K =", K.hex(), file=sys.stderr)
S = b"".join(hashlib.sha256(K + i.to_bytes(4, "big")).digest() for i in range(8))
with open("cipher.bin", "rb") as fh:
ct = fh.read()
flag = bytes(a ^ b for a, b in zip(ct, S))
print("FLAG:", flag)
print("FLAG hex:", flag.hex())
if __name__ == "__main__":
main()
|