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
| """CodeShell.kr — Afterglow: RANSAC with small subsets (run with sage).
Calibration (afterglow_synth.py, using the real h values and moduli):
corrupt=0 -> 80/80 correct
corrupt=1 -> 79/80 correct (one outlier is tolerated)
corrupt=3 -> fails outright
clean subsets of size 50 still solve
and `q/2^153 = 73.31`, so `top7 > 73` is provably corrupt (5 rows: 89, 98, 89,
81, 103). Dropping those leaves 75 rows that still contain a handful of
small-valued corruptions, which is why the all-rows reduction fails.
So: sample small subsets and keep only those that are clean or have a single
outlier. With ~7 remaining bad rows out of 75, a random 50-subset is usable
about 15% of the time, so a few dozen trials suffice.
Every candidate is checked against the public key `y = g^x mod p`.
Usage:
sage -c "exec(open('.../afterglow_ransac.py').read())" [trials]
"""
import hashlib
import json
import random
import sys
from pathlib import Path
from sage.all import Matrix, ZZ
ROOT = Path('codeshell')
TRACE = ROOT / 'extracted' / 'afterglow' / 'trace.json'
SHIFT = 153
def load():
d = json.loads(TRACE.read_text())
p, q, g, y = (int(d[k]) for k in ('p', 'q', 'g', 'y'))
nbytes = (p.bit_length() + 7) // 8
hs, ss, tops = [], [], []
for r in d['records']:
h = int.from_bytes(
hashlib.sha256(r['m'].encode()
+ int(r['R']).to_bytes(nbytes, 'big')).digest(),
'big') % q
hs.append(h)
ss.append(int(r['s']))
tops.append(int(r['top7']))
return p, q, g, y, hs, ss, tops
def score(q, hs, ss, tops, x):
return sum(1 for h, s, t in zip(hs, ss, tops)
if ((s - h * x) % q) >> SHIFT == t)
def candidates(q, hs, ss, tops, idx, B):
n = len(idx)
h0, s0, t0 = hs[idx[0]], ss[idx[0]], tops[idx[0]]
c0 = (s0 - (t0 << SHIFT) - (B >> 1)) % q
inv_h0 = pow(h0, -1, q)
ts = [(hs[j] * inv_h0) % q for j in idx[1:]]
As = [((ss[j] - (tops[j] << SHIFT) - (B >> 1)) - t * c0) % q
for j, t in zip(idx[1:], ts)]
dim = n + 1
m = Matrix(ZZ, dim, dim)
for i in range(n - 1):
m[i, i] = q
for i in range(n - 1):
m[n - 1, i] = ts[i]
m[n, i] = As[i]
m[n - 1, n - 1] = 1
m[n, n] = B
out = []
for row in m.LLL().rows():
if abs(int(row[dim - 1])) != B:
continue
for e0 in (int(row[dim - 2]), -int(row[dim - 2])):
x = (c0 - e0) * inv_h0 % q
if 0 < x < q:
out.append(x)
return out
def main():
trials = int(sys.argv[1]) if len(sys.argv) > 1 else 60
p, q, g, y, hs, ss, tops = load()
B = 1 << SHIFT
mx = (q - 1) >> SHIFT
keep = [i for i, t in enumerate(tops) if t <= mx]
print(f"n={len(hs)}, kept={len(keep)} (dropped {len(hs) - len(keep)} "
f"provably corrupt)", flush=True)
random.seed(2026)
best = (0, None)
for size in (55, 50, 45, 40):
found = 0
for t in range(trials):
idx = random.sample(keep, size)
for x in candidates(q, hs, ss, tops, idx, B):
if pow(g, x, p) == y:
print(f"\n*** SOLVED (size {size}, trial {t}) ***",
flush=True)
ok = score(q, hs, ss, tops, x)
bad = [i for i, (h, s, tp) in
enumerate(zip(hs, ss, tops))
if ((s - h * x) % q) >> SHIFT != tp]
print(f"rows explained: {ok}/{len(hs)}", flush=True)
print(f"corrupt rows : {bad}", flush=True)
dg = hashlib.sha256(x.to_bytes(20, 'big')).hexdigest()[:24]
print(f"answer: CodeShell{{{dg}}}", flush=True)
return
ok = score(q, hs, ss, tops, x)
if ok > best[0]:
best = (ok, x)
print(f" [size {size} t{t}] best rows {ok}/{len(hs)}",
flush=True)
found += 1
print(f"size {size}: {trials} trials, {found} candidates, "
f"best rows {best[0]}/{len(hs)}", flush=True)
print(f"\nnot solved; best rows {best[0]}/{len(hs)}", flush=True)
if __name__ == '__main__':
main()
|