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
|
"""CodeShell.kr — infinity-palindrome solver.
vault.json: RSA modulus n, exponent e=5, 12 affine pairs (a,b) and ciphertext
entries. Each affine pair identifies two entries: m^5 and (a*m+b)^5 mod n.
Same modulus, same small exponent, known LINEAR relation between the two
plaintexts -> Franklin-Reiter related-message attack: x - m divides both
x^e - c1 and (a*x+b)^e - c2 over Z_n[x], so gcd() of the two polynomials
recovers m.
The recovered m values are concatenated as 30-byte unsigned big-endian
integers; the answer is SHA256 of that concatenation.
Usage: uv run python solvers/palindrome.py
"""
import hashlib
import itertools
import json
from pathlib import Path
VAULT = "extracted/infinity-palindrome/vault.json"
M_BYTES = 30
def trim(p):
while p and p[-1] == 0:
p.pop()
return p
def polymul(a, b, n):
if not a or not b:
return []
out = [0] * (len(a) + len(b) - 1)
for i, ai in enumerate(a):
if not ai:
continue
for j, bj in enumerate(b):
out[i + j] = (out[i + j] + ai * bj) % n
return trim(out)
def polymod(a, b, n):
a = list(a)
db = len(b) - 1
binv = pow(b[db], -1, n)
while len(a) - 1 >= db and trim(a):
da = len(a) - 1
if da < db:
break
factor = a[da] * binv % n
shift = da - db
for i in range(db + 1):
a[shift + i] = (a[shift + i] - factor * b[i]) % n
trim(a)
return a
def polygcd(a, b, n):
a, b = trim(list(a)), trim(list(b))
while b:
a, b = b, polymod(a, b, n)
return a
def poly_pow(base, exp, n):
result = [1]
b = trim(list(base))
while exp:
if exp & 1:
result = polymul(result, b, n)
exp >>= 1
if exp:
b = polymul(b, b, n)
return trim(result)
def power_x(e):
"""Polynomial x**e."""
return [0] * e + [1]
def recover_m(a, b, c1, c2, n, e):
"""gcd(x^e - c1, (a x + b)^e - c2) should be x - m."""
f = power_x(e)[:]
f[0] = (f[0] - c1) % n
lin = [b % n, a % n]
g = poly_pow(lin, e, n)
g[0] = (g[0] - c2) % n
trim(g)
h = polygcd(f, g, n)
if len(h) != 2:
return None
root = (-h[0] * pow(h[1], -1, n)) % n
return root
def main():
v = json.loads(Path(VAULT).read_text())
n, e = int(v["n"]), int(v["e"])
aff = [(int(a), int(b)) for a, b in v["affine"]]
cts = [int(c) for c in v["ciphertexts"]]
print(f"n bits={n.bit_length()} e={e} affine={len(aff)} ciphertexts={len(cts)}")
used = set()
ms = []
for i, (a, b) in enumerate(aff):
hit = None
for x, y in itertools.combinations(range(len(cts)), 2):
if x in used or y in used:
continue
for c1, c2 in ((cts[x], cts[y]), (cts[y], cts[x])):
m = recover_m(a, b, c1, c2, n, e)
if m is None:
continue
if pow(m, e, n) == c1 and pow((a * m + b) % n, e, n) == c2:
hit = (x, y, m)
break
if hit:
break
if not hit:
print(f"pair {i}: no matching ciphertext pair")
return
x, y, m = hit
used |= {x, y}
ms.append(m)
print(f"pair {i:2d}: ciphertexts #{x},#{y} m^e==c1 and (am+b)^e==c2 verified")
assert len(ms) == len(aff) and len(used) == len(cts), "pairing incomplete"
blob = b"".join(m.to_bytes(M_BYTES, "big") for m in ms)
print(f"concatenation bytes={len(blob)} (affine-list order)")
print(f"answer: CodeShell{{{hashlib.sha256(blob).hexdigest()}}}")
if __name__ == "__main__":
main()
|