Right now, I have three working solvers – Route, Cadenus and Railfence. I’ve already covered Route, and Railfence is kind of problematic, so that just leaves Cadenus to write up. The reason Railfence is problematic is that it’s the basis for Redefence (which is just Railfence with a key for transposing the rails). The code for both is in one file, and I’d prefer to wait until the Redefence solver is finished and then write up the entire file as a whole.
So now, Cadenus. Route is the only cipher type that needed to be broken into two files (utils and main). Cadenus is all in just the one main file.
Cadenus is made up of columns that are each 25 rows deep, meaning that the cipher text has to be a factor of 25. The ACA guidelines restrict the message length to a width of 6 (i.e. – 150 letters total), for rectangles of 4 x 25, to 6 x 25. The idea is that a keyword is chosen of the proper width (say “GOLD” for a 4×25 message). There are now two stages. The first is to turn the key into a number (1320) and transpose the columns as you would for Complete Columnar.
The second step is to rotate the columns based on the key letters and where they appear in a column index of “AZYXVUTSRQPONMLKJIHGFEDCB” (W=V) (A=0). That is, the “G” column would be rotated by 19, O by 11, L by 14, and D by 22. This is important because it affects the way the key incrementer works, and it makes it harder for me to write a hillclimber.
The fast method is to go through a wordlist of the correct number of letters (say, 4), and try to decrypt the message with each word, following that with an n-gram count for fitness. The slow method is to set the key to [0,0,0,0], and increment each column to 24, then increment the next column, etc. I’m using my recursive incrementer (you’re going to have to go way back to find my post on that one), which is slightly faster. 4-wide ciphers solve within one to two minutes. 5-wide can take a couple hours, 6-wide may take at least a day. So, you’re faced with two choices – use the wordlist first and risk the key not being in it, or go the bruteforce route and be prepared to wait a long time for a solution. My approach is to do one after the other. I run the wordlist method, and if it doesn’t find the answer, I switch to the bruteforcer.
Otherwise, operationally, the Cadenus solver shares a lot in common with the Route solver.
(Manual encrypter/decrypter GUI)
(Show intermediate steps screen)
(Auto-solver GUI screen)
(Solver results screen.)
(Auto-solver screen with solution.)
Functions in this file:
cadenus_make_frames(): .... TKinter E/D GUI code
cadenus_ed(): ............. Manual encrypter/decrypter
make_template(): .......... Form numeric rectangle
encrypt_positions(): ...... Encrypt the numeric values
cadenus_showtemplate(): ... Format the intermediary steps
order_str(): .............. Sort the key by ascending letter
make_key_for_cadenus(): ... Make the Cadenus format keys
shift_list(): ............. Rotate each column based on the key
cadenus_solve(): .......... The entry point for time-slice solving
cadenus_wordlist_solve(): . Auto-solve using the wordlist as key
cadenus_bruteforce_solve(): Bruteforce against the key
get_order(): .............. Make a list of column rotation values
key_to_str(): ............. Convert Cadenus key list to a string
######################
# transpo_cadenus.py #
######################
# Imports
import tkinter as tk
from tkinter import Menu, ttk
from tkinter.messagebox import showinfo, askyesno, showerror
from crypt_utils import string_cleaner, show_grams, count_grams, \.... sort_first
from transpo_utils import check_len, ravel, unravel, \.... transpo_solver_data
from inc_utils import inc_comb, inc_comb_recurse
from cons_parser_update_wordlists import get_word_from_widthlist, \.... get_lengthof_widthlist
from time import time
from sys import exit
# Initialize the column rotation order constant
ORDER = 'AZYXVUTSRQPONMLKJIHGFEDCB'
"""
cadenus_make_frames()
TKinter GUI code for the manual encryption/decryption screen.
Nothing really out of the ordinary.
Check out the above .jpg for the visual result.
"""
def cadenus_make_frames(root, entries, frames_list, use_font, \... fixed_font, ciphertype):
... frame = ttk.Frame(root)
... frame.columnconfigure(0, weight=1)
... frame.columnconfigure(1, weight=3)
... label_parms = [('Title:', 0, 0), ('Key:', 0, 1), \.................. ('Input:', 0, 4), ('Output:', 0, 5), \
.................. ('Length:', 0, 3)]
... for label_name, label_col, label_row in label_parms:
....... ttk.Label(frame, text= label_name).grid(column=label_col, \................ row=label_row, sticky=tk.W)
... entry_parms = [('title', 1, 0, 80), ('key', 1, 1, 20)]
... for param_name, param_col, param_row, param_width in entry_parms:
....... entry_text = tk.StringVar()
....... entry_widget = ttk.Entry(frame, width=param_width, \................................ textvariable=entry_text, \................................ font=use_font)
....... entry_widget.grid(column = param_col, row = param_row, \......................... sticky=tk.W, padx=5, pady=5)
....... entries[param_name] = entry_text
# The Check button allows the user to determine the length
# of the plaintext to be enciphered.
... button_check = ttk.Button(frame, text='Check', \
.................. command=lambda: check_len(entries)).grid( \
.................. column=1, row=3, sticky=tk.W, padx=5, pady=5)
... in_area = tk.Text(frame, width=80, height=10)
... in_area.grid(column=1, row=4, sticky=tk.EW, padx=5, pady=5)
... in_area.configure(font= fixed_font)
... entries['in_area'] = in_area
... in_bar = ttk.Scrollbar(frame, orient = tk.VERTICAL)
... in_bar.grid(column=2, row=4, sticky=tk.NS)
... in_area['yscrollcommand'] = in_bar.set
... in_bar['command'] = in_area.yview
... out_area = tk.Text(frame, width=80, height=10)
... out_area.grid(column=1, row=5, sticky=tk.EW, padx=5, pady=5)
... out_area.configure(font= fixed_font)
... entries['out_area'] = out_area
... out_bar = ttk.Scrollbar(frame, orient = tk.VERTICAL)
... out_bar.grid(column=2, row=5, sticky=tk.NS)
... out_area['yscrollcommand'] = out_bar.set
... out_bar['command'] = out_area.yview
... frames_list['cipher_frame'] = frame
... entries['type'] = ciphertype
... frames_list['input_frame'] = frame
... return entries, frames_list, frame
"""
cadenus_ed()
This is the part that handles manually encrypting/decrypting the user's text.
"""
def cadenus_ed(action, msg, keystring):
# Make sure the user entered a key.
... if len(keystring.strip()) == 0:
....... showinfo('Blank key', 'Need to select a key.')
....... return ''
# Make the key uppercase, and replace "W" with "V".
... keystr = keystring.upper()
... keystr = keystr.replace('W', 'V')
# We need two keys - one for the columnar transposition, and the
# other for rotating the columns. Using the keyword "GOLD":
# colkey = [1, 3, 2, 0]
# shiftkey = [19, 11, 14, 22]
... colkey, shiftkey = make_key_for_cadenus(keystr.upper())
... keylen = len(colkey)
... msglen = len(msg)
# Error check for message length not a factor of 25.
... if msglen % 25 != 0 or int(msglen / 25) != keylen:
....... showinfo('Key mismatch', 'msg length = %s, key length = %s' /................ % (msglen, keylen))
....... return ''
# Make the numbered rectangle template.
... template = make_template(len(msg), len(colkey))
# Encrypt the template with our keys.
... strout = encrypt_positions(template, colkey, shiftkey)
... if action == 0:
# Encrypt the message using the template.
....... return ravel(msg, strout)
... else:
# Decrypt the message using the template
....... return unravel(msg, strout)
"""
make_template()
Make the numbered rectangle template.
"""
def make_template(msglen, width):
... box = [[] for i in range(width)]
... for ptr in range(msglen):
....... box[ptr % width].append(ptr)
... return box
"""
encrypt_positions()
Perform the encryption steps using the columnar transposition key, and the column rotation key.
"""
def encrypt_positions(box, colkey, shiftkey):
... keylen = len(colkey)
# Do the rotations of each column first.
... ret = []
... for i in range(keylen):
....... pos = colkey.index(i)
....... shifted_col = shift_list(box[pos], shiftkey[pos])
....... ret.append(shifted_col)
# Now do the columnar transposition.
... flattened = []
... for col in range(25):
....... for row in range(keylen):
........... flattened.append(ret[row][col])
... return flattened
"""
cadenus_showtemplate()
Prepare the message for the intermediary steps for encryption to verify that they were encrypted correctly.
This section is very similar to manual encryption above.
"""
def cadenus_showtemplate(msg, keystr):
# Initialization.
... colkey, shiftkey = make_key_for_cadenus(keystr.upper())
... msglen = len(msg)
... keylen = len(colkey)
... box = [[] for i in range(keylen)]
# Fill the rectangle with the message.
... for ptr in range(msglen):
....... box[ptr % keylen].append(msg[ptr])
# Rotate each column.
... ret = []
... for i in range(keylen):
....... pos = colkey.index(i)
....... shifted_col = shift_list(box[pos], shiftkey[pos])
....... ret.append(shifted_col)
# Transpose the columns.
... flattened = []
... for column in range(25):
....... hold = []
....... for row in range(keylen):
........... hold.append(ret[row][column])
....... flattened.append(''.join(hold))
# Create the rectangle headers.
... ordered_key = order_str(keystr)
... ul = '-' * keylen
... result = [keystr + ' Key ' + ordered_key + '\n' + ul + ' --- ' + \............. ul]
# Place the plaintext and intermediate ciphertext
# under the headers.
... for i in range(25):
....... line = msg[i * keylen : (i + 1) * keylen]
....... result.append('%s %s %s' % (line, ORDER[i], flattened[i]))
... return '\n'.join(result)
"""
order_str()
Put the keyword in ascending alphabetical order.
That is, for "GOLD" return "DGLO".
"""
def order_str(s):
... r = []
... for ch in s:
....... r.append(ch)
... r.sort()
... return ''.join(r)
"""
make_key_for_cadenus()
Turn "GOLD" into:
[1, 3, 2, 0] and [19, 11, 14, 22]
Return as colkey and shiftkey.
"""
def make_key_for_cadenus(s):
# Error check that we have a key.
... if len(s.strip()) == 0:
....... return ''
# Initialization
... ret = []
... ret_colkey = [0] * len(s)
... cntr = 0
# Build up the transposition list.
... for a in string_cleaner.letters:
....... if a in s:
........... for ptr in range(len(s)):
............... if a == s[ptr]:
................... ret_colkey[ptr] = cntr
................... cntr += 1
# Build up the shifts list.
... ret_shiftkey = [0] * len(s)
... for i in range(len(s)):
....... ret_shiftkey[i] = ORDER.find(s[i])
... return ret_colkey, ret_shiftkey
"""
shift_list()
Rotate the given column by the desired amount.
"""
def shift_list(listvar, shiftval):
... front = listvar[:shiftval]
... return listvar[shiftval:] + front
"""
cadenus_solve()
This is the entry point for auto-solving Cadenus ciphers, called from the GUI time slicer.
Look at the attack_type member in the transpo_solver_data data record for the type of attack to perform. Either bruteforce, or wordlist.
"""
def cadenus_solve():
... global transpo_solver_data
# Use the wordlist approach.
... if transpo_solver_data.attack_type == 0:
....... cadenus_wordlist_solve()
# Just increment the key from [0,0,0,0] to [24,24,24,24]
... else:
....... cadenus_bruteforce_solve()
"""
cadenus_wordlist_solve()
The wordlist is prepped with words of key width through a call to init_wordlist_width(language, width), located in cons_parser_update_wordlists.py. The list itself is a global variable in that file, called wordlist_bywidth[].
cadenus_wordlist_solve() steps through each word in wordlist_bywidth[] and attempts to translate the message with that word as the key. This is followed by an n-gram count check. Everything else works the same way as for transpo_route.py.
"""
def cadenus_wordlist_solve():
... global wordlist_bywidth
# Load the message data from the global record class object.
# This will either be for initialization, or continuing after
# the previous time slice.
... msg, key, hint, attack_type, option, box_width, dummy, \
........ cnt_settings = transpo_solver_data.get()
# Initializations.
... cnt_max, offset = cnt_settings[0], cnt_settings[1]
... ret = []
... timer = time()
... done = False
... listlen = get_lengthof_widthlist()
... template = make_template(len(msg), box_width)
# Enter loop.
... while not done:
# Get the next word from the list.
....... word = get_word_from_widthlist(key)
# Get the keys, encrypt the number positions, and decrypt the message.
....... colkey, shiftkey = make_key_for_cadenus(word)
....... encrypt_order = encrypt_positions(template, colkey, shiftkey)
....... strout = unravel(msg, encrypt_order)
# Get the n-gram count and increment by 50 if the
# hint is in the decrypted string.
....... cnt = count_grams(strout)
....... if len(hint) > 0 and hint in strout:
........... cnt += 50
# Update max count if necessary.
....... if cnt > cnt_max:
............ cnt_max = cnt
# If n-gram count is greater than count max - count offset,
# add the potential solution to the return string.
....... if cnt > cnt_max - offset:
........... ret.append([cnt, '%s' % (word), strout])
# Increment the pointer into the wordlist, and check if
# we've hit the end of the list. If so, quit testing.
....... key += 1
....... if key >= listlen:
........... transpo_solver_data.done = True
........... transpo_solver_data.key = key
........... transpo_solver_data.ret_msg = 'Reached end of list'
........... done = True
# Otherwise, check the timer. If over 1 second, update the
# global data record and exit the function.
....... if time() - timer > 1:
........... done = True
........... transpo_solver_data.key = key
........... transpo_solver_data.cnt[0] = cnt_max
........... transpo_solver_data.ret_msg = word
# Sort the return string list in descending count order.
... ret.sort(key=sort_first, reverse=True)
... transpo_solver_data.solutions = ret
... print('Key = %s' % (transpo_solver_data.key))
# Return to the main GUI.
... return
"""
cadenus_bruteforce_solve()
If the wordlist approach fails, the main GUI will ask the user if they want to try a bruteforce attack. If so, we'll run through the keyspace from [0,0,0,0] to [24,24,24,24] in 1 second time slices. The only real difference between this attack and the wordlist attack is that first we'll have to convert the numeric key into an alphabetic key string, in order to deal with having the two keys (columnar transposition, and columnar rotation).
"""
def cadenus_bruteforce_solve():
... global transpo_solver_data
# Load the message data from the global record class object.
# This will either be for initialization, or continuing after
# the previous time slice.
... msg, key, hint, attack_type, option, box_width, dummy, \
........ cnt_settings = transpo_solver_data.get()
# Initialization.
... msglen = len(msg)
... keylen = len(key)
... ret = []
... strout = ''
... cnt_max, offset = cnt_settings[0], cnt_settings[1]
... done = False
... timer = time()
... template = make_template(msglen, keylen)
# Enter the loop.
... while not done:
# Get the keys, encrypt the number positions, and decrypt the message.
# This is where we convert the numeric key to a key string.
....... colkey, shiftkey = make_key_for_cadenus(key_to_str(key))
....... encrypt_order = encrypt_positions(template, colkey, shiftkey)
....... strout = unravel(msg, encrypt_order)
# Do the n-gram count.
....... cnt = count_grams(strout)
....... if len(hint) > 0 and hint in strout:
........... cnt += 50
# Update max count if necessary.
....... if cnt > cnt_max:
............ cnt_max = cnt
# If n-gram count is greater than count max - count offset,
# add the potential solution to the return string.
....... if cnt > cnt_max - offset:
........... ret.append([cnt, '%s' % (key_to_str(key)), strout])
# Increment the key using the recursive incrementer.
# Format is: "key list, max key digit value, key length, pointer to# last digit incremented."
....... done_inc, key = inc_comb_recurse(key, 24, keylen - 1, keylen)
# If we've reached the end of the keyspace, quit testing.
....... if done_inc:
........... transpo_solver_data.done = True
........... done = True
# Otherwise, check the timer. If over 1 second, update the
# global data record and exit the function.
....... if time() - timer > 1:
........... done = True
........... transpo_solver_data.key = key
........... transpo_solver_data.cnt[0] = cnt_max
........... transpo_solver_data.ret_msg = key_to_str(key)
# Sort the results by n-gram count, and add them to the data record.
... ret.sort(key=sort_first, reverse=True)
... transpo_solver_data.solutions = ret
# Return to the GUI.
... return
"""
get_order()
Get the key transposition order.
(That is: GOLD will be converted to 1320.)
"""
def get_order(key):
... keylen = len(key)
... ret = [0] * keylen
... cntr = 0
... for i in range(25):
....... for ptr in range(keylen):
........... if key[ptr] == i:
............... ret[ptr] = cntr
............... cntr += 1
... return ret
"""
key_to_str()
Convert the numeric key for bruteforce testing into an alphabetic string in ORDER order.
"""
def key_to_str(key):
... ret = []
... for k in key:
....... ret.append(ORDER[k])
... return ''.join(ret)
Next up: No idea
The Black Chamber 