Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
List key possibilities for each clue and cautiously merge them into one full key solution in Clear category for Playfair Cipher Attack by Phil15
# 0.65 seconds to pass all tests on my computer and python 3.10.
import string
from bisect import bisect
from collections.abc import Iterable, Iterator
from itertools import product
Char = str # of length 1
Pair = tuple[Char, Char]
Position = tuple[int, int]
CHAR_REPLACEMENTS = {'j': 'i'}
FILL_CHAR = 'x'
UNKNOWN = '.'
ALPHABET = frozenset(string.ascii_lowercase) - set(CHAR_REPLACEMENTS)
SIZE = 5
assert SIZE ** 2 == len(ALPHABET)
class PlayfairPartialKey:
__slots__ = 'chars', '_ch2pos', '_grid', '_top_left_char'
def __init__(self) -> None:
# _ch2pos, _grid, _top_left_char are private to this class but I had to
# use "chars" in another class, so just to clear it would not be okay
# for it to change it, I chose to make it frozen, the overhead is small.
self.chars: frozenset[Char] = frozenset()
self._ch2pos: dict[Char, Position] = {}
# NOTE: `chars` and `_ch2pos.keys()` are equivalent,
# but the big use of the keys method was a bit slow.
self._grid = [[UNKNOWN] * SIZE for _ in range(SIZE)]
self._top_left_char = UNKNOWN
# `_top_left_char == _grid[0][0]` but use a property was a bit slow.
@property
def solved(self) -> bool:
return self.chars == ALPHABET
def __str__(self) -> str:
return '[%s]' % ', '.join(map(repr, map(''.join, self._grid)))
__repr__ = __str__
def copy(self) -> 'PlayfairPartialKey':
new = self.__class__()
new.chars = self.chars
new._ch2pos = self._ch2pos.copy()
new._grid = [line[:] for line in self._grid]
new._top_left_char = self._top_left_char
return new
def __setitem__(self, position: Position, char: Char) -> None:
r, c = position
assert char not in self.chars and self._grid[r][c] == UNKNOWN
if char in self.chars:
raise ValueError('Already placed in the grid.')
self.chars |= {char}
self._ch2pos[char] = position
self._grid[r][c] = char
if r == c == 0:
self._top_left_char = char
def rotate(self, top_left_char: Char) -> None:
"""Change the top left letter."""
if self._top_left_char == top_left_char:
return # Nothing to do!
ch2pos = self._ch2pos
r0, c0 = ch2pos[top_left_char] # may raise KeyError if not cautious
self._grid = [[UNKNOWN] * SIZE for _ in range(SIZE)]
for ch, (r, c) in ch2pos.items():
r, c = ch2pos[ch] = (r - r0) % SIZE, (c - c0) % SIZE
self._grid[r][c] = ch
self._top_left_char = top_left_char
# The most time consuming function (half the entire time to pass tests).
def can_merge(self, other: 'PlayfairPartialKey') -> bool:
common_chars = self.chars & other.chars
if not common_chars:
return False # No common char to merge on.
# Have the same "top left letter" if possible, rotate if necessary.
if self._top_left_char != other._top_left_char:
if self._top_left_char in common_chars:
other.rotate(self._top_left_char)
elif other._top_left_char in common_chars:
self.rotate(other._top_left_char)
else:
top_left_char = next(iter(common_chars))
self.rotate(top_left_char)
other.rotate(top_left_char)
# Check if the chars placed in the grids are compatibles.
for ch in common_chars:
if self._ch2pos[ch] != other._ch2pos[ch]:
return False # Incompatible positions.
for ch in self.chars - common_chars:
r, c = self._ch2pos[ch]
if ch != other._grid[r][c] != UNKNOWN:
return False # Incompatible chars.
for ch in other.chars - common_chars:
r, c = other._ch2pos[ch]
if ch != self._grid[r][c] != UNKNOWN:
return False # Incompatible chars.
return True
def merge(self, other: 'PlayfairPartialKey') -> 'PlayfairPartialKey':
new = self.copy()
# Merge into new.
for ch, (r, c) in other._ch2pos.items():
assert ch not in new._ch2pos or new._ch2pos[ch] == (r, c)
assert new._grid[r][c] in (UNKNOWN, ch)
new._ch2pos[ch] = r, c
new._grid[r][c] = ch
new.chars |= other.chars
if len(new.chars) == SIZE ** 2 - 1:
# Only one letter missing in the grid, easy to deduce.
(ch,) = ALPHABET - new.chars
for r, c in product(range(SIZE), repeat=2):
if new._grid[r][c] == UNKNOWN:
new.chars = ALPHABET
new._ch2pos[ch] = r, c
new._grid[r][c] = ch
break
new._top_left_char = new._grid[0][0]
return new
def encrypt(self, pair: Pair) -> Pair:
a, b = pair
assert a != b
if self.chars.issuperset(pair):
(r0, c0), (r1, c1) = self._ch2pos[a], self._ch2pos[b]
if c0 == c1: # Same column: next rows.
r0, r1 = (r0 + 1) % SIZE, (r1 + 1) % SIZE
elif r0 == r1: # Same row: next columns.
c0, c1 = (c0 + 1) % SIZE, (c1 + 1) % SIZE
else: # Different rows and columns: swap columns.
c0, c1 = c1, c0
c, d = self._grid[r0][c0], self._grid[r1][c1]
if c != UNKNOWN != d:
return c, d
raise ValueError(f'We can not encrypt {pair!r} yet.')
def decrypt(self, pair: Pair) -> Pair:
c, d = pair
assert c != d
if self.chars.issuperset(pair):
(r0, c0), (r1, c1) = self._ch2pos[c], self._ch2pos[d]
if c0 == c1: # Same column: prev rows.
r0, r1 = (r0 - 1) % SIZE, (r1 - 1) % SIZE
elif r0 == r1: # Same row: prev columns.
c0, c1 = (c0 - 1) % SIZE, (c1 - 1) % SIZE
else: # Different rows and columns: swap columns.
c0, c1 = c1, c0
a, b = self._grid[r0][c0], self._grid[r1][c1]
if a != UNKNOWN != b:
return a, b
raise ValueError(f'We can not encrypt {pair!r} yet.')
class PlayfairMapping:
def __init__(self, elems: Iterable[PlayfairPartialKey] = ()) -> None:
self._pkeys: list[PlayfairPartialKey] = list(elems)
@classmethod
def from_clue(cls, plain: Pair, encrypted: Pair) -> 'PlayfairMapping':
"""
List all possible partial grids that would okay with the clue.
Up to 2 elements if there is a letter in common
or `SIZE ** 2 - 5` (so 20 here) elements otherwise.
"""
# AB --> CD so A --> C and B --> D
(A, B), (C, D) = plain, encrypted
if A == C or B == D:
raise ValueError('An encrypted char must be different from the non-encrypted.')
self = cls()
if C == B or D == A:
# A --> C == B --> D OR B --> D == A --> C
line = (A, B, D) if C == B else (B, A, C)
prow0, pcol0 = PlayfairPartialKey(), PlayfairPartialKey()
for i, ch in enumerate(line):
prow0[0, i] = pcol0[i, 0] = ch
self._pkeys += [prow0, pcol0]
# 2 new elements only
else:
# Row 0 AND column 0: A --> C ; B --> D in disjoint groups.
for i in range(2, SIZE - 1):
prow0, pcol0 = PlayfairPartialKey(), PlayfairPartialKey()
prow0[0, 0] = pcol0[0, 0] = A
prow0[0, 1] = pcol0[1, 0] = C
prow0[0, i] = pcol0[i, 0] = B
prow0[0, i + 1] = pcol0[i + 1, 0] = D
self._pkeys += [prow0, pcol0]
# Square
# A --> C
# D <-- B
for r, c in product(range(1, SIZE), repeat=2):
pkey = PlayfairPartialKey()
pkey[0, 0] = A
pkey[0, c] = C
pkey[r, c] = B
pkey[r, 0] = D
self._pkeys.append(pkey)
# 2 * (SIZE - 3) + (SIZE - 1) ** 2 == SIZE ** 2 - 5 new elements
return self
def chars(self) -> frozenset[Char]:
union: frozenset[Char] = frozenset()
for pkey in self._pkeys:
union |= pkey.chars
return union
# Please collapse mappings with the fewest partial key grids first
# to avoid the collapsed list to be large...
def collapse(self, other: 'PlayfairMapping') -> 'PlayfairMapping':
return self.__class__(
k0.merge(k1) for k0 in self._pkeys for k1 in other._pkeys if k0.can_merge(k1)
)
def __lt__(self, other: 'PlayfairMapping') -> bool:
return len(self._pkeys) < len(other._pkeys)
@property
def full_key(self) -> PlayfairPartialKey | None:
if len(self._pkeys) == 1:
pkey = self._pkeys[0]
if pkey.solved:
return pkey
return None
class PlayfairAttack:
def __init__(self) -> None:
self._mappings: list[PlayfairMapping] = []
# To avoid to make mapping duplicates.
self._clues: set[tuple[Pair, Pair]] = set()
@staticmethod
def _pairs(text: str) -> Iterator[Pair]:
# yield from zip(text[::2], text[1::2]) # Enough if the text is prepared.
for repl in CHAR_REPLACEMENTS.items():
text = text.replace(*repl)
a = ''
for b in text:
if not a:
a = b
elif b == a:
yield a, FILL_CHAR
elif a:
yield a, b
a = ''
if a:
if a == FILL_CHAR: # We must not return a pair with the same char.
# That's why "x" is choosen: it is uncommon, but possible.
raise ValueError(f"Don't end this with {FILL_CHAR!r} please.")
yield a, FILL_CHAR
def feed(self, plaintext: str, cryptogram: str) -> None:
for clue in zip(self._pairs(plaintext), self._pairs(cryptogram), strict=True):
if clue not in self._clues:
self._mappings.append(PlayfairMapping.from_clue(*clue))
self._clues.add(clue)
def attack(self) -> None:
maps = self._mappings
# mappings are compared at multiple places here, only with the
# implementation of the `__lt__` method in the PlayfairMapping class:
# * `maps.sort()`
# * `m2 < m0` ; `m1 < m2` when computing `low` and `high`.
# * `bisect` compares `m2` with elements of `maps`.
# I though using a key to sort, but bisect don't allow to use a key.
# And bisect being the right way to do this, I chose to use `__lt__`.
maps.sort()
for length in range(len(maps), 1, -1):
for i0, i1 in [(i, j) for j in range(1, length) for i in range(j)]:
m0 = maps[i0]
m1 = maps[i1]
if m0.chars() & m1.chars(): # Otherwise it can not merge.
m2 = m0.collapse(m1)
if m2:
break
else:
print("We can't deduce anything anymore, we need more clues.")
break
full_key = m2.full_key
if full_key is not None:
# Solved! We avoid checking if it is compatible with the other
# mappings. But you can commenting this out if you want.
maps.clear()
maps.append(m2)
break
del maps[i0]
i1 -= 1 # remove i0 first move the index i1 down because i0 < i1.
del maps[i1]
# We can do it without given low/high, but it is faster with.
low, high = (
(0, 0)
if not maps
else (0, i0)
if m2 < m0
else (i1, len(maps))
if m1 < m2
else (i0, i1)
)
i2 = bisect(maps, m2, low, high) # To keep maps sorted.
maps.insert(i2, m2)
@property
def full_key(self) -> PlayfairPartialKey | None:
maps = self._mappings
return maps[0].full_key if len(maps) == 1 else None
def encrypt(self, plaintext: str) -> str:
key = self.full_key
if key is None:
raise ValueError('No full key yet!')
return ''.join(map(''.join, map(key.encrypt, self._pairs(plaintext))))
# TODO: Partial decryption when we do not have the full key.
def decrypt(self, cryptogram: str) -> str:
key = self.full_key
if key is None:
raise ValueError('No full key yet!')
return ''.join(map(''.join, map(key.decrypt, self._pairs(cryptogram))))
def playfair_attack(
plaintext: str,
cryptogram: str,
decrypt_text: bool = False,
text: str = 'topsecretmessage',
) -> str:
playfair = PlayfairAttack()
playfair.feed(plaintext, cryptogram)
playfair.attack()
# playfair.full_key.rotate('a') # Only to have an unique display.
# print(playfair.full_key)
return playfair.decrypt(text) if decrypt_text else playfair.encrypt(text)
if __name__ == '__main__':
TESTS = [
(
'pythonsxstandardlibraryisveryextensiveofferingawiderangeofstuffx',
'aiwblarskwphydowzehmhoieksxlixgwvufxlvzqvizxbehdycxlphyxzqkwcvsi',
'dmhfiulxgbxvqhyx',
),
(
'sixcrazykingsvowedtoabolishmyquitepitifulioust',
'zlgrcekqztvoolunhbvkemsvlzadnpzflrqlvlhwtluzkl',
'vklprhcrixbpzebc',
),
(
'zombiesquicklyatetwelveofmyneighboursx',
'uzuywyksmzdcvhfgtnftonbnkfevywlgxzmxzd',
'xnzpchtyrfcwpkth',
),
(
'youshouldreadeliezeryudkowskysrationalityfromaitozombies',
'kcohsuwcxabmvawqmpbefcxflooxkgemztcxeutzfikrrmtzwswrmyrp',
'xwgpblebzirphrpb',
),
(
'thexexampleaboveisaverysimplequantummechanicsequationx',
'bghyhyganmgvrhefzivsoklvaxnmofgspwglygxospzxvunogmzhdl',
'rgnaoykomauviveu',
),
(
'echoofaclockrhythmicallypulsatedinmyveinsx',
'xepkvuuyctxopnlmrkgybyycocxdbmlwdrirwzdrqh',
'mvhgxezymoxwiqwc',
),
(
'wearealxlfromxanthcubesaidquicklyiustvisitingphaze',
'baixamwkblsfasihxatgcbxmmungeuqgnmdrgamrauficqawpb',
'dwyzbzzidamzxmcv',
),
(
'youshouldreadeliezeryudkowskysrationalityfromaitozombies',
'kcohsuwcxabmvawqmpbefcxflooxkgemztcxeutzfikrrmtzwswrmyrp',
'xwgpblebzirphrpb',
),
(
'aquickbrownfoxiumpsoverthelazydogx',
'quqdyngvshtchpdqxoofryfqcwbtbwmspq',
'xfzowyeixnwrvuri',
),
(
'doesthetreemakeasoundifitfallsintheforestwherenobody',
'lccwbsawmzvwgtozhcnysduxhnokdhgubsopzlcwbhwomzfahzru',
'hauwoamzwkcwtcva',
),
(
'discoelysiumanisometricdetectiverpgwhatkindofcopareyou',
'lzhxcdasilfnpulimwaqtzoeaqcfqzhppkmsyerbrgomhfkdptahbm',
'zblvcfqpzulhylfl',
),
(
'ideaofcognitivebiasinpsychologyworksinanalogousway',
'eobdkqiwbtrxpxbaelxcvecwpyxomqwsmiwvexdeuymqmlcsuh',
'xmcvrpirrtcnnybr',
),
(
'abacadaebcbdbecdcedeafbfcfdfefagbg',
'wgqlpuslimtzomryemkrwhfmmvzxmnghti',
'gbawmelmbrkowqol',
),
(
'thefiveboxingwizardsiumpquicklyx',
'irfbnhfgisotcpnxkaolxizaudxudruz',
'enwzigbtmrofmwqf',
),
(
'abcdefghiklmnopqrstuvwxyzx',
'scxviuklhzhlorqlngoeyxwvdh',
'ouygqboqotbttstq',
),
(
'iackdawslovesmybigblacksphinxofquartzx',
'rckuxihpmkdxohgrbnctcbzoswsdepuxfcbmpv',
'mzkoqromhwdopiyv',
),
(
'fiftysixbigredietplaneszoxomedbythetower',
'krnmpkufruioznuzneatpczhbwraznoqvccnayic',
'acskctcivlzpyvez',
),
(
'letusconfirmaphonydoubtx',
'ufetqvlkpxywgeydkrlqoeiz',
'zuvgvtwfcwvaagap',
),
(
'mzpyfihnfzvmpokuomptmb',
'hqthbemywrxaldcnaztsqx',
'gptygklfvhtfxpig',
),
(
'nxnymfyubalsbvbwckbhoqwbgx',
'mtlxshpdmsrapbzpoumccfpzti',
'khibvoevhxrzzskr',
),
(
'discoelysiumanisometricdetectiverpgwhatkindofcopareyou',
'yuiqrfxluspueqsuuhabospyablnxsebunfdtfhqrcwulkukeslvir',
'hsqulnnbmbarqtef',
),
(
'echoofaclockrhythmicallypulsatedinmyveinsx',
'gbtssogqdmbxirmrtkgpgeamfgeolrlbwckxsawcpk',
'lmfvgbhaltbkveua',
),
(
'ohfukrwsvsbepegqansgzpdmtbdrcv',
'colwsgftzviaiuygevkrpuflbpfymk',
'hwtzodywbfwnvwyo',
),
(
'innitrkmqcmocvvbydmsux',
'hoohwpsralxngeuzhrnelo',
'uimfcmmwepcefccv',
),
(
'rehoomhoonaelkqlndplqedahccggf',
'edsvlqsvbqudzlmocrovmuauvhityx',
'wvoxdmedzcukxuza',
),
(
'thisexamplecontainsunxnesesxsarilylongplaintextandciphertextyoupr'
'obablydontnexedasamplethisbigtobreaktheplayfairencryptionsoadxdso'
'mekindofcontrolwhenthekeytableisfoundyoushouldstopadxdingnewdigra'
'phsanywaytomakesurethatwehavexenoughletxtersabcdefghiklmnopqrstuv'
'wxyz',
'wgbpomebicytaqueblbsqbdagafbbnxrclqydsicybduomuedlpyhfvmgdmzvacsx'
'vaninelaqudomdtnbebicdgprbampzemxyedwgvicevsorxadwilicmaqfaenmqfa'
'edlrdlqxzyduxvkcgvdugvdvecnadybpxqsuleazgfazklguyfenmqblsdvtlmhmy'
'sfgnuvcevzebedvbsmvwgeutvsvoymoqatspkdgmzvmbniutdspprqkbdyfkxguwa'
'zroc',
'zehgytmvgeagbnmd',
),
]
def main(nb: int) -> None:
import cProfile
import statistics as stats
from time import perf_counter
global TESTS
if nb == 0:
for plaintext, cryptogram, answer in TESTS:
result = playfair_attack(plaintext, cryptogram)
assert result == answer, (result, answer)
top = playfair_attack(plaintext, cryptogram, decrypt_text=True, text=answer)
assert top == 'topsecretmessage', (top, 'topsecretmessage')
print('Well done! xoxo')
elif nb > 0:
ts = []
for _ in range(nb):
t = -perf_counter()
for plaintext, cryptogram, _ in TESTS:
playfair_attack(plaintext, cryptogram)
t += perf_counter()
ts.append(t)
for func in sum, min, max, stats.mean, stats.median:
secs = func(ts) # type: ignore
print(f'{func.__name__: <6} {secs:.6f} seconds')
else:
TESTS *= -nb
cProfile.run('for *a, _ in TESTS: playfair_attack(*a)', sort='tottime')
main(10)
Jan. 4, 2022
Comments:
