The more I work on writing up the Transpo cipher solvers, the more I realize I have to elaborate more on general background subjects, too.
I had to go in for a root canal treatment (one of four visits to the dentist for one tooth), and the anesthetic keeps wearing off before the dentist is done drilling into the tooth. So, this morning, as I wait for the next treatment to start and knowing what I’m in for, I tried distracting myself by thinking of Python code. And I realized that I was doing something a little inefficiently in the n-gram counter section.
Originally, in the auto-solvers, I’d do something like this:
done = False
cnt_max = 50
cnt_offset = 5
while not done:
... order = transpose(msg_template, key)
... strout = unravel(msg, order)
... cnt = count_grams(strout)
... if len(crib) > 0 and crib in strout:
....... cnt += 50
... if cnt >= cnt_max - cnt_offset:
....... if cnt > cnt_max:
........... cnt_max = cnt
....... print('n-gram count: %s, plaintext: %s' % (cnt, strout))
Where count_grams() was defined as:
def count_grams(message):
... global ngrams_holder
... ret = 0
... for gram in ngrams_holder:
....... ret += message.count(gram) * len(gram)
... return ret
Now, I realize that I’m leaving some details unexplained, but these are the important parts. There are two things I didn’t like about this (three, in that one thing was the dentist never hit me with enough anesthetic). First was that I was constantly checking the length of the crib, when the crib never changed. Second was that the n-gram counter section wasn’t efficient enough.
This is what I came up with instead:
def count_grams_w_crib(message, crib, have_crib, cnt_max, cnt_offset):
... global ngrams_holder
... cnt = 0
... for gram in ngrams_holder:
....... cnt += message.count(gram) * len(gram)
... if have_crib and crib in message:
....... cnt += 50
... if cnt >= cnt_max - cnt_offset:
....... if cnt > cnt_max:
........... return True, cnt, cnt
....... else:
........... return True, cnt_max, cnt
... return False, cnt_max, cnt
The calling code in the body of the auto-solver changes to:
have_crib = (len(crib.strip()) > 0)
cnt_max = 50
cnt_offset = 5
done = False
while not done:
... order = transpose(msg_template, key)
... strout = unravel(msg, order)
... have_hit, cnt_max, cnt = \
....... count_grams_w_crib(strout, crib, have_crib, cnt_max, \.......................... cnt_offset)
... if have_hit:
....... print('n-gram count: %s, plaintext: %s' % (cnt, strout))
To me, these changes do two things. First, they simplify the auto-solver body, which makes it easier for me to reuse some of this code in each subsequent solver (that is, copy-pasting the Fixed Distance body to create the starting point for writing the Columnar transposition solver). Second, they move the len(crib) operation out of the test loop, and turn a numeric comparison into a simple boolean if-statement. No idea if this gives me a speed boost, but I’d like to think it does.
Plus, some changes to the GUI:
(Add the n-gram count max and offset settings to the menu)
(n-gram count max and offset settings screen)
Ok, Fixed Distance.
The idea here is that encryption is just a matter of taking a certain number of steps along the plaintext message, and sampling each position along the message once and only once. For this to work, the step size can’t share factors with the message length. That is, the two numbers need to be relatively prime. In other words, if the length is 10, then good step sizes would be 1, 3, 7 and 9. 1 can be ruled out because we’d just get our plaintext back out. And 9 is the same thing as -1. If we use a step size (a key) of 3:
thisistest
We get:
tstti sshie
The above example is a case of “pick then count.” Using count then pick:
isshi etstt
Note that all we’re really doing is shifting the start point of the cipher message. The letter order is still the same.
Now, an interesting side effect is that each step size has an “inverse” step. What this means is that enciphering the message with a “key” of 3, we can get our plaintext back out by enciphering with the inverse value, which is 7 in this example:
tsttisshie
thisistest
Conversely, if we’d encrypted the message with 7, we’d decrypt by encrypting with 3.
The problem is that Fixed Distance (also known as Skip) doesn’t offer any real security, and it almost never appears as a CON in the ACA’s Cryptogram newsletter. It’s more of a novelty, but it does show up in introductions to Public Key Encryption. Regardless, I had a Python Fixed Distance solver already written, and it amused me to include it in Transpo Solver.
Note also that there’s no real intermediate step in the Fixed Distance algorithm, so I don’t have a show_template() function for it.
(Fixed Distance manual encryption/decryption screen)
(Manual encryption/decryption screen with cipher text)
(Auto-solver screen)
(With found solution)
Functions in this file:
fixed_make_frames(): . Create manual GUI screen
fixed_ed(): .......... Perform encryption or decryption step
is_prime(): .......... Test if message length is prime
get_gcds(): .......... Get GCD list for message length
check_len(): ......... Get message length for manual data entry
get_inverse(): ....... Get inverse mod of encryption key
transpose(): ......... Transpose numeric positions list
fixed_solve(): ....... Fixed Distance auto-solver
####################
# transpo_fixed.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_w_crib, sort_first
from math import sqrt, gcd
from transpo_utils import ravel, unravel, transpo_solver_data
"""
fixed_make_frames()
Define the screen layout for the manual encryption/decryption interface. Pretty much like all of the other screen definitions.
Although, we need the Check button to show us all of the legal key values for the current length of the plaintext message.
Invert is used for toggling between "Pick then Count," and "Count then Pick."
"""
def fixed_make_frames(root, entries, frames_list, use_font, \... fixed_font, option, 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),
.................. ('%s:' % option, 0, 2), ('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
... invert_var = tk.BooleanVar()
... invert_check = ttk.Checkbutton(frame, variable=invert_var)
... invert_check.grid(column = 1, row = 2, sticky=tk.W, padx=5, \..................... pady=5)
... entries['invert_var'] = invert_var
... 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
"""
fixed_ed()
This is the manual encrypter/decrypter section.
"""
def fixed_ed(entries, action, msg, key, option):
# Error check if the key is left empty.
... if len(key.strip()) == 0:
....... showinfo('Bad key', 'Empty key')
....... return ''
# Initialization.
... msglen = len(msg)
... keyint = int(key)
# Error check if the key is not in the valid list for the message# length.
... if key not in get_gcds(msglen):
....... showinfo('Bad key', 'Key %s not valid' % (key))
....... return ''
# Initialize the numeric positions template.
... order = []
... template = []
... for i in range(msglen):
....... template.append(i)
# Encrypt the template positions using the given key (step size).
... order = transpose(msglen, option, template, keyint)
# If action is 0, then we're encrypting the plaintext.
# Otherwise, decrypt.
... if action == 0:
....... entries['message'].set('Inverse key: %s' % \............................. (get_inverse(msglen, keyint)))
....... return ravel(msg, order)
... else:
....... return unravel(msg, order)
"""
is_prime()
If the message length is prime, any key other than 0 is valid.
"""
def is_prime(n):
... sr = int(sqrt(n)) + 1
... for i in range(2, sr):
....... if n % i == 0: return False
... return True
"""
get_gcds()
The Greatest Common Denominator is the largest factor two numbers have in common. If the value is 1, then the two numbers are relatively prime, which is what we want for Fixed Distance ciphers. Get all of the GCDs within the range of our message length.
"""
def get_gcds(msglen):
... results = []
... for n in range(2, msglen):
....... if gcd(n, msglen) == 1:
........... results.append(str(n))
... return results
"""
check_len()
This function is called when the user clicks on the Check button in the manual E/D screen.
Get the current message, clean it for the language selected, then check if the number is prime. If not, return all of the relatively prime numbers within the range of the message length.
“””
def check_len(entries):
... msg = string_cleaner.clean(entries['in_area'].get(1.0, 'end'))
... msglen = len(msg)
... if is_prime(msglen):
....... entries['message'].set('Message length: %s is prime.' % /.............................. (msglen))
... else:
....... gcds = get_gcds(msglen)
....... entries['message'].set('Valid values: %s' % (' '.join(gcds)))
"""
get_inverse()
Each relatively prime number referenced to the message length has an "inverse" that will decrypt the message by using the inverse as the encryption step length (key). When the user manually encrypts the message, display the inverse value in the feedback entry widget.
"""
def get_inverse(msglen, key):
... gcds = get_gcds(msglen)
... for g in gcds:
....... if (key * int(g)) % msglen == 1:
........... return g
... return 0
"""
transpose()
Encrypt the position numbers template using the step size (key), the message length, and option (pick then count, or count then pick).
"""
def transpose(msglen, option, template, step):
# Initialization.
... ptr = 0
... order = []
# Step through the msglen range.
... for i in range(msglen):
# For each increment:
....... if option == 0:
# Pick the position value, then count "step" positions.
........... order.append(template[ptr])
........... ptr = (ptr + int(step)) % msglen
....... else:
# Count "step" positions, then pick the position value.
........... ptr = (ptr + int(step)) % msglen
........... order.append(template[ptr])
... return order
"""
fixed_solve()
This is the Fixed Distance auto-solver. Get the list of relatively prime numbers for the message length, then test each one by trying to encrypt the message and then testing the number of valid n-grams in the result.
"""
def fixed_solve():
# Get our message data from the record object.
... global transpo_solver_data
# Read the important values from the record.
... msg, key, hint, attack_type, option, dummy1, dummy2, \....... cnt_settings = transpo_solver_data.get()
# Initialization.
# If we have a hint (i.e. - the crib), set the hint flag.
... msglen = len(msg)
... have_hint = (len(hint.strip()) != 0)
... ret = []
... strout = ''
... cnt_max, cnt_offset = cnt_settings[0], cnt_settings[1]
# Error check for a blank message.
... if msglen == 0:
....... showinfo('Bad message', 'Empty message')
....... return
# Create our positions template.
... template = []
... for i in range(msglen):
....... template.append(i)
# Get the list of relatively prime step values.
... valid_steps = get_gcds(msglen)
# Go through our list.
... for step in valid_steps:
# Encrypt the template using the current step value as the key.
....... order = transpose(msglen, option, template, step)
# Encrypt the message using the encrypted position order.
....... strout = ravel(msg, order)
# Get the n-gram count, while also passing the hint. If the current
# count is greater than the current max, cnt_max will automatically
# be updated. If the cnt is between cnt_max and cnt_max - cnt_offset,
# have_hit will be true.
....... have_hit, cnt_max, cnt = \
................. count_grams_w_crib(strout, hint, have_hint, \.................................... cnt_max, cnt_offset)
# If have_hit is True, add the count, step-as-key, and the
# current message text to the return list.
....... if have_hit:
........... ret.append([cnt, step, strout])
# Sort the return list in descending cnt order,
# and return the sorted list to the calling GUI.
... ret.sort(key=sort_first, reverse=True)
... transpo_solver_data.solutions = ret
... return
Next up: No idea
The Black Chamber 