Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Playfair Cipher Attack by xffox
import copy
import string
from dataclasses import dataclass, field
from typing import List, Set, Dict
_EXCLUDE_CHAR = 'j'
_ALPHABET = list(v for v in string.ascii_lowercase if v != _EXCLUDE_CHAR)
_ALPHABET_CHARS = set(_ALPHABET)
_SIZE = 5
_CHUNK_SIZE = 2
_TARGET_PLAINTEXT = "topsecretmessage"
@dataclass
class Candidate:
rows: List[Set[str]] = field(default_factory=list)
cols: List[Set[str]] = field(default_factory=list)
right: Dict[str, str] = field(default_factory=dict)
below: Dict[str, str] = field(default_factory=dict)
def _try_extend_groups(groups, values):
cur_row = set(values)
next_groups = []
for row in groups:
if any(val in row for val in cur_row):
cur_row |= row
if len(cur_row) > _SIZE:
return None
else:
next_groups.append(row)
next_groups.append(cur_row)
return next_groups
def _try_extend_followers(followers, plain_bigram, crypt_bigram):
for plain_char, crypt_char in zip(plain_bigram, crypt_bigram):
try:
cur_right = followers[plain_char]
if cur_right != crypt_char:
return None
except KeyError:
cycle_left = _SIZE
cur = crypt_char
while cycle_left > 0:
try:
cur = followers[cur]
except KeyError:
cycle_left = None
break
cycle_left -= 1
if cur == plain_char:
break
if cycle_left is not None and cycle_left != 1:
return None
next_followers = copy.deepcopy(followers)
for plain_char, crypt_char in zip(plain_bigram, crypt_bigram):
next_followers[plain_char] = crypt_char
return next_followers
def _in_same_group(groups, values):
for group in groups:
if len(group & values) > 1:
return True
return False
def _update_followers(candidate, values):
targets = list(values)
targets.extend(k for k, v in candidate.right.items() if v in values)
targets.extend(k for k, v in candidate.below.items() if v in values)
for val in targets:
try:
val_right = candidate.right[val]
val_below = candidate.below[val]
except KeyError:
continue
try:
val_right_below = candidate.below[val_right]
if candidate.right.get(val_below, None) != val_right_below:
candidate = _try_same_row(
candidate, val_below, val_right_below)
if candidate is None:
return None
except KeyError:
pass
try:
val_below_right = candidate.right[val_below]
if candidate.below.get(val_right, None) != val_below_right:
candidate = _try_same_col(
candidate, val_right, val_below_right)
if candidate is None:
return None
except KeyError:
pass
return candidate
def _try_same_row(candidate, plain_bigram, crypt_bigram):
all_chars = set(plain_bigram + crypt_bigram)
if _in_same_group(candidate.cols, all_chars):
return None
next_rows = _try_extend_groups(candidate.rows, all_chars)
if next_rows is None:
return None
next_right = _try_extend_followers(candidate.right,
plain_bigram, crypt_bigram)
if next_right is None:
return None
next_cand = Candidate(rows=next_rows, cols=candidate.cols,
right=next_right, below=candidate.below)
return _update_followers(next_cand, plain_bigram)
def _try_same_col(candidate, plain_bigram, crypt_bigram):
all_chars = set(plain_bigram + crypt_bigram)
if _in_same_group(candidate.rows, all_chars):
return None
next_cols = _try_extend_groups(candidate.cols, all_chars)
if next_cols is None:
return None
next_below = _try_extend_followers(candidate.below,
plain_bigram, crypt_bigram)
if next_below is None:
return None
next_cand = Candidate(rows=candidate.rows, cols=next_cols,
right=candidate.right, below=next_below)
return _update_followers(next_cand, plain_bigram)
def _try_diagonal(candidate, plain_bigram, crypt_bigram):
next_rows = _try_extend_groups(
candidate.rows, set((plain_bigram[0], crypt_bigram[0])))
if next_rows is None:
return None
next_rows = _try_extend_groups(
next_rows, set((plain_bigram[1], crypt_bigram[1])))
if next_rows is None:
return None
next_cols = _try_extend_groups(
candidate.cols, set((plain_bigram[0], crypt_bigram[1])))
if next_cols is None:
return None
next_cols = _try_extend_groups(
next_cols, set((plain_bigram[1], crypt_bigram[0])))
if next_cols is None:
return None
return Candidate(rows=next_rows, cols=next_cols,
right=candidate.right, below=candidate.below)
def _find_solutions(candidate, get_followers, get_groups, try_followers):
followers = get_followers(candidate)
all_left = _ALPHABET_CHARS - followers.keys()
if not all_left:
yield candidate
return
all_vals = _ALPHABET_CHARS - set(followers.values())
cand_left = all_left
cand_vals = all_vals
groups = get_groups(candidate)
for group in groups:
if len(group) == _SIZE:
common_vals = group & all_left
if common_vals and len(common_vals) < len(cand_left):
cand_left = common_vals
cand_vals = group & all_vals
val = next(iter(cand_left), None)
cand_vals -= set((val,))
for next_val in cand_vals:
cur_result = try_followers(candidate, val, next_val)
if cur_result is not None:
yield from _find_solutions(cur_result,
get_followers, get_groups,
try_followers)
def _make_table(candidate):
result = [['']*_SIZE for _ in range(_SIZE)]
row_char = 'a'
for row in range(_SIZE):
col_char = row_char
for col in range(_SIZE):
result[row][col] = col_char
col_char = candidate.right[col_char]
row_char = candidate.below[row_char]
return result
def _next_position(idx):
return (idx+1) % _SIZE
def _encrypt(plaintext, table):
positions = {}
for row_idx, row in enumerate(table):
for col_idx, val in enumerate(row):
positions[val] = (row_idx, col_idx)
result = []
for i in range(0, len(plaintext), _CHUNK_SIZE):
pos1 = positions[plaintext[i]]
pos2 = positions[plaintext[i+1]]
if pos1[0] == pos2[0]:
result.append(table[pos1[0]][_next_position(pos1[1])])
result.append(table[pos2[0]][_next_position(pos2[1])])
elif pos1[1] == pos2[1]:
result.append(table[_next_position(pos1[0])][pos1[1]])
result.append(table[_next_position(pos2[0])][pos2[1]])
else:
result.append(table[pos1[0]][pos2[1]])
result.append(table[pos2[0]][pos1[1]])
return ''.join(result)
def playfair_attack(plaintext: str, cryptogram: str) -> str:
candidates = [Candidate()]
for i in range(0, len(plaintext), _CHUNK_SIZE):
next_candidates = []
for candidate in candidates:
plain_bigram = plaintext[i:(i+_CHUNK_SIZE)]
crypt_bigram = cryptogram[i:(i+_CHUNK_SIZE)]
next_cand = _try_same_row(candidate, plain_bigram, crypt_bigram)
if next_cand is not None:
next_candidates.append(next_cand)
next_cand = _try_same_col(candidate, plain_bigram, crypt_bigram)
if next_cand is not None:
next_candidates.append(next_cand)
next_cand = _try_diagonal(candidate, plain_bigram, crypt_bigram)
if next_cand is not None:
next_candidates.append(next_cand)
candidates = next_candidates
for candidate in candidates:
for right_cand in _find_solutions(
candidate, lambda v: v.right, lambda v: v.rows,
_try_same_row):
for below_cand in _find_solutions(
right_cand, lambda v: v.below, lambda v: v.cols,
_try_same_col):
table = _make_table(below_cand)
if table is not None:
return _encrypt(_TARGET_PLAINTEXT, table)
return ''
if __name__ == "__main__":
print("Example:")
print(
playfair_attack(
'abcdefghiklmnopqrstuvwxyzx', 'scxviuklhzhlorqlngoeyxwvdh'
)
)
# These "asserts" are used for self-checking and not for an auto-testing
assert (
playfair_attack(
"sixcrazykingsvowedtoabolishmyquitepitifulioust",
"zlgrcekqztvoolunhbvkemsvlzadnpzflrqlvlhwtluzkl",
)
== "vklprhcrixbpzebc"
)
assert (
playfair_attack(
"pythonsxstandardlibraryisveryextensiveofferingawiderangeofstuffx",
"aiwblarskwphydowzehmhoieksxlixgwvufxlvzqvizxbehdycxlphyxzqkwcvsi",
)
== "dmhfiulxgbxvqhyx"
)
assert (
playfair_attack(
"zombiesquicklyatetwelveofmyneighboursx",
"uzuywyksmzdcvhfgtnftonbnkfevywlgxzmxzd",
)
== "xnzpchtyrfcwpkth"
)
print("Coding complete? Click 'Check' to earn cool rewards!")
Jan. 23, 2022