I wrote a bit about Sequence Transposition way back in Groundwork 3 – Keys. We’re going to need two pieces beyond our message: a 10-wide key, and a five digit primer. First, write out your message, minus any spaces and punctuation. We need this to get the length.
(Manual encrypter/decrypter screen)
LETSUSEALONGERTESTMESSAGETHISTIMEORMAYBENOT
Length: 43
Next, pick a primer. We could use a keyword, but we want a way to generate any digit between 0 and 9, and a normal keyword approach would just take us from 0 to 4 (if we have 5 letters in the key). We could assign 0-9 to the letters A-J, or just assign 0-25 to A-Z, and then take mod 10 of the letter value. To keep it simple, I’m just going to pick a number.
72926
Write the primer over the message, and extend it by adding the first two digits (7 + 2 = 9), taking the units digit if the sum is greater than 9, and appending the units digit to the right-hand end of the primer sequence. Keep doing this until the sequence is the length of the message.
7292691185029352128733050635569801578162597
LETSUSEALONGERTESTMESSAGETHISTIMEORMAYBENOT
We follow this by picking a ten-letter key, and writing a regular key number under it, starting with 1 for the lowest letter, and incrementing from left to right and in ascending order. This is the normal way of creating a numeric key, except that instead of going 0-9, we’re going 1-10, and dropping the ten’s digit.
0123456789 - Normal ascension
1234567890 - Sequence ascension
TRANSPOSED
0714865932
We now get into the encryption phase. Taking each letter in the message one at a time, from the left, write them under the matching digits in the key.
Example:
729269118
LETSUSEAL
TRANSPOSED
0714865932
.LE.LU.T.E
..A....S.S
(Sequence encryption middle steps)
To create the finished message, write the primer, then take the text off in columns from left to right. Finish by appending the last digit of the sequence as a checksum.
72926 NAEEL EMTEA SOYLM MAUTT BOTGI SRNTS EIORS SHESG ETE 7
Decryption is the reverse process.
(Auto-solver screen, with solution)
To solve Sequence Transposition, we can either use a wordlist attack, or a permutating incrementing counter attack on the key. The wordlist attack is similar to that from Cadenus. Read all 10-letter words in the list, step through them one at a time, and turn each one into a numeric key as described above. Decrypt the message with the key, count the n-grams in the output text, and save the top potential “solutions” to our data record object for display to the user. If the key isn’t in the wordlist, ask the user if they want to run the key attack.
The key attack is standard. Run through the key space from 0-9 to 9-0. Add 1 to all of the digits in the solved keys when displaying them.
Both the wordlist and key attacks will take a minute or more to complete, depending on the length of the message (the longer the message, the slower the program runs), meaning that we need time slicing to avoid “program not responding errors.” We could introduce a hillclimbing attack, but that would take longer than the key attack does, so I won’t bother with it.
A couple weeks before I wrote this, one of the ACA members in the Facebook group mentioned that he’d found a discrepancy between the description of the Sequence Transposition given in the ACA Resources pages, and the way it’s actually implemented by the members creating CONs for the newsletter. I’m not exactly sure if I can duplicate his findings, but I do know that as a result my keyword handling functions are kind of funky. I was documenting my solver GUI as described above, and suddenly discovered that it wouldn’t auto-solve the example crypt.
The manual encryption/decryption section worked fine on the ACA examples, and my own cipher, but the auto-solver failed just on my crypt when I used a keyword. Took me several hours to pinpoint the problem to the “make a key from a keyword” function, and when I tried to simplify the code across the Python file, everything stopped working. For the moment, I’ve fixed the problem as I understand it, but the current state of the code isn’t particularly elegant. We’ll see what happens in the future when/if the ACA corrects their online Sequence Transposition page. On the plus side, the ACA only runs one or two Sequence Transpositions a year (that is, out of 600+ CONs a year).
Functions in this file:
sequence_make_frames(): ... Encrypter/decrypter GUI code
sequence_ed(): ............ Manual E/D handler
tostr(): .................. Convert list to string
make_sequence(): .......... Extend the primer to message length
make_primer(): ............ Convert string to int list
make_template(): .......... Encrypt numeric positions
make_key_from_word(): ..... Used by wordlist_solve()
sequence_showtemplate(): .. Display intermediate encryption step
sequence_solve(): ......... Entry point from main GUI for auto-solvers
sequence_wordlist_solve():. Auto-solver using 10-letter wordlist
sequence_keyattack_solve(): Auto-solver using key incrementer
#######################
# transpo_sequence.py #
#######################
# Imports
import tkinter as tk
from tkinter import Menu, ttk
from tkinter.messagebox import showinfo, askyesno, showerror
from crypt_utils import group_in, count_grams_w_crib, sort_first
from transpo_utils import make_key_from_string, ravel, unravel, \.... key_to_str, transpo_solver_data
from cons_parser_update_wordlists import get_word_from_bywidthlist, \
.... get_lengthof_bywidthlist
from inc_utils import inc_perm
from time import time
from sys import exit
"""
sequence_make_frames()
TKinter code for creating the manual encrypter/decrypter GUI frames. Pretty much identical to the other make_frames() functions, with the addition of the "Primer" entry field. Check out the above screencap for the final results.
"""
def sequence_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), ('Primer:', 0, 1), \.................. ('Key:', 0, 2), ('Input:', 0, 3), \.................. ('Output:', 0, 4)]
... 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), ('primer', 1, 1, 20), \.................. ('key', 1, 2, 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
... in_area = tk.Text(frame, width=80, height=10)
... in_area.grid(column=1, row=3, 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=3, 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=4, 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=4, 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
"""
sequence_ed()
Manual encrypter/decrypter function. Called when the user clicks on the Encrypt or Decrypt buttons.
action: 0 = Encrypt, 1 = Decrypt.
msgstr: Our cipher or plaintext message, precleaned.
keystr: Our key, as an unprocessed string.
primerstr: Our 5-digit sequence primer, as a string.
"""
def sequence_ed(action, msgstr, keystr, primerstr):
# Error checking.
... if len(keystr.strip()) != 10:
....... showinfo('Bad Key Length', '%s needs to be length 10' % \................ (keystr.strip()))
....... return ''
... if len(msgstr) == 0:
....... showinfo('No Message', 'Message not entered.')
....... return ''
# Turn the key from whatever kind of string it is
# into a 10-digit numeric list running from 1 to (1)0.
... key = make_key_from_string(keystr.upper())
... if action == 0:
# For encryption, initialization.
....... msg = msgstr
....... msglen = len(msg)
# Error handling, valid primer not entered.
....... if len(primerstr.strip()) != 5:
........... showinfo('Bad Primer Length', '%s needs to be length 5' \.................... % (primerstr.strip()))
........... return
# Convert the primer from a string to a int list.
# Extend the primer to the length of the message.
# Grab the checksum digit at the end of the sequence.
....... primer = make_primer(primerstr)
....... seq = make_sequence(primer, msglen)
....... check = seq[msglen - 1]
... else:
# For decryption.
# Pull the primer off the front of the message.
# Grab the checksum from the end.
# Clean the message string.
# Get the message length as a variable.
....... primer = make_primer(msgstr[0:5])
....... check = int(msgstr[len(msgstr) - 1])
....... msg = msgstr[5: len(msgstr) - 1]
....... msg = msg.replace(' ', '').replace('\n', '').replace('.', '')
....... msglen = len(msg)
# Extend the primer to the length of the message.
....... seq = make_sequence(primer, msglen)
# Verify the checksum from the message.
....... if seq[msglen - 1] != check:
........... showinfo('Check digit mismatch', '%s does not match %s' \......................% (seq[msglen - 1], check))
........... return ''
# For both encrypting and decrypting, encrypt the
# numeric positions based on the sequence and the key list.
... template = make_template(seq, key)
... if action == 0:
# Encryption: Print the primer, the cipher grouped in 5s,
# and the checksum digit.
....... text_out = '%s %s %s' % (tostr(primer), \.................. group_in(ravel(msg, template)), str(check))
... else:
# Decryption: Print the deciphered plaintext.
....... text_out = unravel(msg, template)
... return text_out
"""
tostr()
Take the Sequence key list and convert it to a string.
"""
def tostr(l):
... ret = []
... for e in l:
....... ret.append(str(e))
... return ''.join(ret)
"""
make_sequence()
Extend the primer to the length of the user's message as given in seqlen. This is done by adding the primer (and then the rest of the sequence) in pairs, and adding the sum mod 10 to the right-hand end of the sequence.
That is, for primer ABCDE,
Sequence = [A,B,C,D,E,A+B,B+C,C+D, etc.]
Remembering to strip off any 10's place carryover.
"""
def make_sequence(primer, seqlen):
# Initialization.
... seq = [0] * seqlen
# Copy in the primer as individual ints.
... for i in range(5):
....... seq[i] = primer[i]
# Extend the sequence by adding digit pairs mod 10.
... for i in range(seqlen - 5):
....... seq[i + 5] = (seq[i] + seq[i + 1]) % 10
... return seq
"""
make_primer()
Convert the primer string into a 5-digit list.
The user can enter the primer either as a numeric string:
'39427'
or as a keyword, where the ASCII value will be converted by mod 10.
"""
def make_primer(p):
... ret = []
... for ch in p:
# Numeric character, just convert to a digit.
....... if ch in '0123456789':
........... ret.append(int(ch))
....... else:
# String character. Get the ASCII value, treat "A" = 0,
# and apply mod 10 to any other letter.
........... val = ord(ch.upper())
........... if val >= 65 and val <= 91:
............... ret.append((val - 65) % 10)
........... else:
# Any ASCII character can be used for the key if desired.
............... ret.append(val % 10)
... return ret
"""
make_template()
Using the sequence and the 10-digit key, encrypt the numeric positions of the message text, return as a list.
"""
def make_template(sequence, key):
# Initialization.
... temp = [[] for i in range(10)]
... ret = []
# Build up the "message" as position numbers from 0 to message length.
... for i in range(len(sequence)):
....... temp[sequence[i]].append(i)
# Go through the sequence and assign each "letter" in
# the message to the appropriate digit in the key list.
... for ptr in key:
....... for e in temp[(ptr + 1) % 10]:
........... ret.append(e)
... return ret
"""
sequence_showtemplate()
Duplicate the first half of sequence_ed(), and build up the sequence as a string for display, for debugging if for nothing else.
"""
def sequence_showtemplate(msg, keystr, primerstr):
# Key processing.
... key = make_key_from_string(keystr.upper())
... for i in range(len(key)):
....... key[i] = (key[i] + 1) % 10
... msglen = len(msg)
# Convert the primer and extend it the length of the message.
... primer = make_primer(primerstr)
... seq = make_sequence(primer, msglen)
# Build the numeric positions list.
... template = [[] for i in range(10)]
... for i in range(msglen):
....... template[seq[i]].append(msg[i])
# Encrypt the positions based on the sequence and key digits.
... maxlen = len(max(template, key=len))
... for i in range(len(template)):
....... for j in range(len(template[i]), maxlen):
........... template[i].append(' ')
# Prep the display header.
... ret = [tostr(seq), msg, '\n', keystr, tostr(key), '-' * 10]
# Display the key and the keyed text under it.
# Check out the above screencap for an example display.
... for row in range(maxlen):
....... strline = []
....... for i in range(10):
........... col = key[i]
........... strline.append(template[col][row])
....... ret.append(''.join(strline))
... return '\n'.join(ret)
"""
sequence_solve()
Common entry point from the main GUI.
Run the wordlist solver if action is 0.
Otherwise, run the bruteforce key incrementer.
"""
def sequence_solve():
... global transpo_solver_data
... if transpo_solver_data.attack_type == 0:
....... sequence_wordlist_solve()
... elif transpo_solver_data.attack_type == 1:
....... sequence_keyattack_solve()
"""
make_key_from_word()
In the sequence_wordlist_solve() function, we need to take the 10-letter words and turn them into their numeric equivalents (such as TRANSPOSED = 0714865932), starting with the lowest letter to the left of the word as 1. For the moment, I'm defaulting the keyword as being in English. I don't think I've ever seen a xeno Sequence CON. This can always be fixed in the future if/when needs be.
"""
def make_key_from_word(word):
# Initialization.
... wordlen = len(word)
... ret = [0] * wordlen
... ptr = 0
# Go through the alphabet. If the current letter is
# in the key, assign ptr to it in the associated place
# in the ret list, and increment ptr. Since we're going
# from 1 to 10, use mod 10 to eliminate the 10's digit
# carryover.
... for ch in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
........ for i in range(wordlen):
............ if ch == word[i]:
................ ret[i] = ptr
................ ptr = (ptr + 1) % 10
... return ret
"""
sequence_wordlist_solve()
Wordlist bruteforce solver. This one's easy. The wordlist (wordlist_bywidth) is preloaded by the GUI, and all we have to do is step through it, try to decrypt the message with each word as the key, and score the results by n-gram count. We do need to use time slicing, so return control back to the GUI after 1 second, as necessary.
"""
def sequence_wordlist_solve():
# Grab our list of 10-letter words.
... global wordlist_bywidth
# Load our most commonly-used values from the data
# record object to variables for speed.
... msg, key, hint, attack_type, option, width, dummy, \
........ cnt_settings = transpo_solver_data.get()
# Initialization.
... cnt_max, cnt_offset = cnt_settings[0], cnt_settings[1]
... ret = []
... timer = time()
... done = False
... listlen = get_lengthof_bywidthlist()
... have_hint = (len(hint.strip()) != 0)
... sequence = transpo_solver_data.sequence
# Run until we hit the end of the wordlist, or we time out.
... while not done:
# Get the next word in our list. Key is a pointer here.
....... word = get_word_from_bywidthlist(key)
# Make the numeric key.
....... key_list = make_key_from_word(word)
# Encrypt the number positions using the sequence and
# the current key.
....... encrypt_order = make_template(sequence, key_list)
....... strout = unravel(msg, encrypt_order)
# Do the n-gram count. Update max count if needed. Mark
# the current solution if the n-gram count is equal to
# or greater than max count - count offset.
....... have_hit, cnt_max, cnt = \
................. count_grams_w_crib(strout, hint, have_hint, \................. cnt_max, cnt_offset)
# We have a potential winner. Add it to the return list object.
....... if have_hit:
........... ret.append([cnt, word, strout])
# Increment our wordlist pointer. If we've hit the
# end of the list, quit out.
....... 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
# We've timed out for this time slice. Update our
# data record object and return control to the main GUI.
....... 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 any potential solutions in descending n-gram
# count order, and save to the data record object.
... ret.sort(key=sort_first, reverse=True)
... transpo_solver_data.solutions = ret
... return
"""
sequence_keyattack_solve()
The main GUI solver handler runs sequence_wordlist_solve() first. If the user doesn't select a "correct" solution, the handler will ask if you want to run the bruteforce attack on the key. If the user selects "Yes," it will call sequence_keyattack_solve() in 1 second time slices, initializing the key to [0,1,2,3,4,5,6,7,8,9]. This function increments the key using the permutating incrementer.
"""
def sequence_keyattack_solve():
# Grab our data record object.
... global transpo_solver_data
# Load our most commonly-used values from the data
# record object to variables for speed.
... msg, key, hint, attack_type, option, width, dummy, \
........ cnt_settings = transpo_solver_data.get()
# Sequence is preloaded by the data record object
# initializer for speed.
... sequence = transpo_solver_data.sequence
# Initialization.
... cnt_max, cnt_offset = cnt_settings[0], cnt_settings[1]
... ret = []
... timer = time()
... done = False
... have_hint = (len(hint.strip()) != 0)
... msglen = len(msg)
... keylen = len(key)
# While we are still in the key space, and haven't timed out yet:
... while not done:
# Encrypt our numeric position data using the sequence and key.
....... encrypt_order = make_template(sequence, key)
# Decrypt the message using our encrypted position data.
....... strout = unravel(msg, encrypt_order)
# Check the n-gram count.
....... have_hit, cnt_max, cnt = \
................. count_grams_w_crib(strout, hint, have_hint, \................. cnt_max, cnt_offset)
# If n-grams greater than or equal to max count - count offset,
# add to the return list.
....... if have_hit:
........... ret.append([cnt, key_to_str(key), strout])
# Increment the key. If we're at the end of the
# key space, quit out.
....... done_inc, key = inc_perm(key, keylen - 1, keylen - 1, keylen)
....... if done_inc:
........... transpo_solver_data.done = True
........... transpo_solver_data.key = key
........... transpo_solver_data.ret_msg = 'Reached end of list'
........... done = True
# If we're timing out, update the data record object.
....... if time() - timer > 1:
........... done = True
........... transpo_solver_data.key = key
........... transpo_solver_data.width_min = width
........... transpo_solver_data.cnt[0] = cnt_max
........... transpo_solver_data.ret_msg = key_to_str(key, 0)
# Sort the potential solutions on descending n-gram count.
# Set the solutions to our data record object.
... ret.sort(key=sort_first, reverse=True)
... transpo_solver_data.solutions = ret
... return
Next up: No idea
The Black Chamber 