# Transposition ciphers attack the fort at dawn a t t a c k t h e f o r t a t d a w n akod ttra aean cft --- layout: true .indexlink[[Index](index.html)] --- # Transposition ciphers Rather than changing symbols (substitution ciphers), Rearrange them. Still disguises the message. (Good ciphers do both, and more.) --- # Scytale Even older than Caesar cipher. * Wrap a strip round a pole * Write the message along it * Unwind the strip * "Unreadable" unless reader has pole of same diameter ``` attack the fort at dawn a t t a c k t h e f o r t a t d a w n akod ttra aean cft ``` --- # Generalising: column transposition ciphers Scytale essentially fills a grid by rows, then reads it by columns * (Deciphering is the reverse) Column transposition ciphers: * Fill a grid * Reorder columns based on keyword * Read the grid (perhaps different direction) (Keyword = secret → cerst) ``` attack the fort at dawn s e c r t c e r s t --------- --------- a t t a c t t a a c k t h e f h t e k f o r t a t t r a o t d a w n w a n d ttaac htekf traot wand thtw tra aean akod cft ``` Scytale is just a special case of column transposition. --- # Grids and data structures What operations do we need to do on a grid? How to represent a grid? --- # Grids and data structures What operations do we need to do on a grid? * Fill, by rows or columns * Empty, by rows or columns * Rearrange columns * Calculate the size of the grid * Pad message to fit a rectangle of the required size How to represent a grid? * List of strings * Each row is a string * Rows in order in the list --- # Finding sizes Know number of columns Number of rows = `\(\left \lceil \frac{\mathrm{message\ length}}{\mathrm{columns}} \right \rceil\)` Paddding is (rows ⨉ columns) - message length * What to use as default padding? * Keyword parameter! ## Fit 'thequickbrownfox' (16 letters) into grid of * 4 columns * 5 columns --- # Fill and empty grid by rows Split message into row-sized chunks * slices and ranges Append all the rows together * `<string>.join()` Keep thinking about test cases! --- # Fill and empty grid by columns Idea: fill and empty by rows, with a transposition. `zip(*rows)` and `itertools.zip_longest(*rows)` --- # Swapping columns How to represent a transposition (_permutation_, to mathematicians)? How to create it from a keyword? --- # Idea of a transposition Says, for each element, where it should go ``` 0 1 2 3 4 5 6 t r e a s o n a e n o r s t 3 2 6 5 1 4 0 ``` The transposition `(3, 2, 6, 5, 1, 4, 0)` says that what was in position 3 moves to position 0, what was in position 2 moves to position 1, what was in position 6 moves to position 2, ... `enumerate(_iterable_)` yields an iterator that walks over the iterable, including the element indexes. ```python >>> [i for i in enumerate('treason')] [(0, 't'), (1, 'r'), (2, 'e'), (3, 'a'), (4, 's'), (5, 'o'), (6, 'n')] >>> [i for i in enumerate((3, 2, 6, 5, 1, 4, 0))] [(0, 3), (1, 2), (2, 6), (3, 5), (4, 1), (5, 4), (6, 0)] ``` Write the `transpose` and `untranspose` functions. --- # Transposition from a keyword Deduplicate the keyword Sort it Use `<iterable>.index()` to find the positions of the letters in the sorted keyword --- # Transposition ciphers Put it all together --- # Back to the scytale Key is number of rows. No transposition of columns. * What does a null transposition look like? How to fill and empty? (Transposing the grid is easier) --- # Masking the fill characters Padding characters can be distinctive. Make a function that generates a random letter, based on the `normalised_english_counts` Use `callable()` to check if the `fillvalue` should be called or just inserted