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
|
"""CodeShell.kr — Marginalia: refine the 22-column Vigenere key.
Stage 1 (marginalia.py) found key length 22 by column-IC and produced a nearly
readable plaintext, but chi-square mis-picks a few columns because each column
only holds ~12 characters.
Stage 2 (here): local search over the 22 shifts, scoring a candidate plaintext
by how much of it is covered by dictionary words. Starting from the chi-square
key, try every shift for every column, keep improvements, repeat until stable.
"""
import sys
from pathlib import Path
ALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
WORDS = None
def load_words(path):
return {w.strip().upper() for w in Path(path).read_text().split()
if 2 <= len(w.strip()) <= 20 and w.strip().isalpha()}
def coverage(text, words):
"""Greedy longest-match word coverage: fraction of chars inside words."""
i, covered, n = 0, 0, len(text)
while i < n:
best = 0
for L in range(min(20, n - i), 1, -1):
if text[i:i + L] in words:
best = L
break
if best:
covered += best
i += best
else:
i += 1
return covered
def decode(text, key):
"""key: iterable of int shifts (or a letter string)."""
shifts = [ALPHA.index(k) if isinstance(k, str) else k for k in key]
L = len(shifts)
return ''.join(ALPHA[(ALPHA.index(c) - shifts[i % L]) % 26]
for i, c in enumerate(text))
def refine(text, key, words, passes=12):
key = list(key)
best = coverage(decode(text, key), words)
print(f"start coverage {best}/{len(text)}")
for p in range(passes):
changed = 0
for col in range(len(key)):
cur = key[col]
local_best, local_shift = best, cur
for s in range(26):
if s == cur:
continue
key[col] = s
sc = coverage(decode(text, key), words)
if sc > local_best:
local_best, local_shift = sc, s
key[col] = local_shift
if local_shift != cur:
changed += 1
best = local_best
print(f"pass {p}: {changed} columns changed, coverage {best}/{len(text)}")
if changed == 0:
break
return ''.join(ALPHA[s] if isinstance(s, int) else s for s in key)
def main():
global WORDS
text = Path('marg.txt').read_text().strip()
text = ''.join(c for c in text.upper() if c in ALPHA)
WORDS = load_words(sys.argv[1] if len(sys.argv) > 1 else
'~/wordlists/words_alpha.txt')
print(f"words {len(WORDS)} ciphertext {len(text)}")
key = refine(text, 'QMVJHLQXTNPSKOEACZBGFW', WORDS)
print("key:", key)
plain = decode(text, key)
for i in range(0, len(plain), 60):
print('%3d %s' % (i, plain[i:i + 60]))
if __name__ == '__main__':
main()
|