Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Playfair Cipher Attack by liuq901
import copy
TEXT = 'topsecretmessage'
class State(object):
def __init__(self):
self.valid = True
self.row_cnt = {}
self.col_cnt = {}
self.row = {}
self.col = {}
self.row_next = {}
self.col_next = {}
for i in range(26):
ch = chr(ord('a') + i)
if ch == 'j':
continue
self.row[ch] = None
self.col[ch] = None
self.row_next[ch] = None
self.col_next[ch] = None
def not_same(self, x1, x2, is_row):
if x1 == x2:
return True
a = self.row if is_row else self.col
if a[x1] is not None and a[x2] is not None:
return a[x1] != a[x2]
return True
def merge(self, x1, x2, is_row):
if x1 == x2:
return
a = self.row if is_row else self.col
cnt = self.row_cnt if is_row else self.col_cnt
if a[x1] is None and a[x2] is None:
a[x1] = a[x2] = len(cnt)
cnt[a[x1]] = 2
elif a[x1] is not None and a[x2] is not None:
if a[x1] != a[x2]:
tmp = a[x2]
for x in a:
if a[x] == tmp:
a[x] = a[x1]
cnt[a[x1]] += cnt[tmp]
cnt[tmp] = 0
else:
if a[x1] is None:
x1, x2 = x2, x1
a[x2] = a[x1]
cnt[a[x1]] += 1
if cnt[a[x1]] > 5:
self.valid = False
def next(self, x1, y1, is_row):
a = self.row_next if is_row else self.col_next
for x in a:
if a[x] == y1 and x != x1:
self.valid = False
if a[x1] is not None and a[x1] != y1:
self.valid = False
a[x1] = y1
def check(self):
for x in self.pos:
if self.pos[x] is None:
continue
x0, y0 = self.pos[x]
y = self.row_next[x]
if y is not None:
x1, y1 = x0, (y0 + 1) % 5
if self.grille[x1][y1] != None and self.grille[x1][y1] != y:
return False
if self.pos[y] is not None and self.pos[y] != (x1, y1):
return False
if self.col[y] is not None:
for z in self.col:
if self.col[z] == self.col[y] and self.pos[z] is not None and self.pos[z][1] != y1:
return False
y = self.col_next[x]
if y is not None:
x1, y1 = (x0 + 1) % 5, y0
if self.grille[x1][y1] != None and self.grille[x1][y1] != y:
return False
if self.pos[y] is not None and self.pos[y] != (x1, y1):
return False
if self.row[y] is not None:
for z in self.row:
if self.row[z] == self.row[y] and self.pos[z] is not None and self.pos[z][0] != x1:
return False
if self.row[x] is not None:
for y in self.row:
if self.row[y] == self.row[x] and self.pos[y] is not None and self.pos[y][0] != x0:
return False
if self.col[x] is not None:
for y in self.col:
if self.col[y] == self.col[x] and self.pos[y] is not None and self.pos[y][1] != y0:
return False
row_set = [set() for _ in range(5)]
col_set = [set() for _ in range(5)]
for i in range(5):
for j in range(5):
if self.grille[i][j] is not None:
row_set[i].add(self.row[self.grille[i][j]])
col_set[j].add(self.col[self.grille[i][j]])
for i in range(5):
if sum(1 if x is None else self.row_cnt[x] for x in row_set[i]) > 5:
return False
if sum(1 if x is None else self.col_cnt[x] for x in col_set[i]) > 5:
return False
return True
def dfs(self, x, y):
if not self.check():
return False
if x == 5:
return True
if y == 5:
return self.dfs(x + 1, 0)
for ch in self.pos.keys():
if self.pos[ch] is None:
self.pos[ch] = (x, y)
self.grille[x][y] = ch
if self.dfs(x, y + 1):
return True
self.pos[ch] = None
self.grille[x][y] = None
return False
def gen_grille(self):
self.pos = {x: None for x in self.row}
self.pos['a'] = (0, 0)
self.grille = [[None] * 5 for _ in range(5)]
self.grille[0][0] = 'a'
return self.dfs(0, 1)
def encode(self, s):
res = []
for i in range(0, len(s), 2):
x1, y1 = self.pos[s[i]]
x2, y2 = self.pos[s[i + 1]]
if x1 == x2:
y1 = (y1 + 1) % 5
y2 = (y2 + 1) % 5
res.extend([self.grille[x1][y1], self.grille[x2][y2]])
elif y1 == y2:
x1 = (x1 + 1) % 5
x2 = (x2 + 1) % 5
res.extend([self.grille[x1][y1], self.grille[x2][y2]])
else:
res.extend([self.grille[x1][y2], self.grille[x2][y1]])
return ''.join(res)
def playfair_attack(plaintext: str, cryptogram: str) -> str:
# your code here
def dfs(dep, state):
if not state.valid:
return None
if dep == len(plaintext):
if state.gen_grille():
return state
else:
return None
x1, x2 = plaintext[dep:dep + 2]
y1, y2 = cryptogram[dep:dep + 2]
if state.not_same(x1, x2, True) and state.not_same(x1, y2, True):
if state.not_same(y1, x2, True) and state.not_same(y1, y2, True):
if state.not_same(x1, x2, False) and state.not_same(x1, y1, False):
if state.not_same(y2, x2, False) and state.not_same(y2, y1, False):
new_state = copy.deepcopy(state)
new_state.merge(x1, y1, True)
new_state.merge(x2, y2, True)
new_state.merge(x1, y2, False)
new_state.merge(x2, y1, False)
res = dfs(dep + 2, new_state)
if res is not None:
return res
if state.not_same(x1, x2, False) and state.not_same(x1, y1, False):
if state.not_same(x1, y2, False) and state.not_same(x2, y1, False):
if state.not_same(x2, y2, False) and state.not_same(y1, y2, False):
new_state = copy.deepcopy(state)
new_state.merge(x1, x2, True)
new_state.merge(x1, y1, True)
new_state.merge(x1, y2, True)
new_state.next(x1, y1, True)
new_state.next(x2, y2, True)
res = dfs(dep + 2, new_state)
if res is not None:
return res
if state.not_same(x1, x2, True) and state.not_same(x1, y1, True):
if state.not_same(x1, y2, True) and state.not_same(x2, y1, True):
if state.not_same(x2, y2, True) and state.not_same(y1, y2, True):
new_state = copy.deepcopy(state)
new_state.merge(x1, x2, False)
new_state.merge(x1, y1, False)
new_state.merge(x1, y2, False)
new_state.next(x1, y1, False)
new_state.next(x2, y2, False)
res = dfs(dep + 2, new_state)
if res is not None:
return res
return None
state = dfs(0, State())
return state.encode(TEXT)
if __name__ == "__main__":
print("Example:")
print(
playfair_attack(
"sixcrazykingsvowedtoabolishmyquitepitifulioust",
"zlgrcekqztvoolunhbvkemsvlzadnpzflrqlvlhwtluzkl",
)
)
# 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. 12, 2022
