* an early Greek transposition cipher
* a strip of paper was wound round a staff
* message written along staff in rows, then paper removed
* leaving a strip of seemingly random letters
* not very secure as key was width of paper & staff

transposition or permutation ciphers hide the message contents by rearranging the order of the letters

* use Kasiski method & IC to estimate period d
* then separate ciphertext into d sections, and solve each as a monoalphabetic cipher

* Index of Coincidence (IC) was introduced in 1920s by William Friedman
* measures variation of frequencies of letters in ciphertext
o period = 1 => simple subs => variation is high, IC high
o period > 1 => poly subs => variation is reduced, IC low
o first define a measure of roughness (MR) giving variation of frequencies of individual characters relative to a uniform distribution

* use repetitions in ciphertext to give clues as to period, looking for same plaintext an exact period apart, leading to same ciphertext

Plaintext: TOBEORNOTTOBE
Key: NOWNOWNOWNOWN
Ciphertext: GCXRCNACPGCXR

Since repeats are 9 chars apart, guess period is 3 or 9.

* human languages are highly redundant
o e.g., th lrd s m shphrd shll nt wnt
* Claude Shannon derived several important results about the information content of languages in 1949
* entropy of a message H(X) is related to the number of bits of information needed to encode a message X
o cannot exceed log_(2)n bits for n possible messages
* the rate of langauge for messages of length k denotes the average number of bits in each character

D = F(H(M),k)

* rate of English is about 3.2 bits/letter

* just the inverse of the Vigenère (decrypts it)

given K = k(1) k(2) ... k(d)
then f(i) (a) = a - k(i) (mod n)

* similar to Vigenère but with alphabet written backwards
* can be descibed by

given K = k(1) k(2) ... k(d)
then f(i) (a) = (k(i) - a) (mod n)

and its inverse is

f(i) ^(-1)(a) = (k(i) - c) (mod n)

Key = d
Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher: DCBAZYXWVUTSRQPONMLKJIHGFE

* in general use more than one substitution alphabet
* makes cryptanalysis harder since have more alphabets to guess
* and because flattens frequency distribution (since same plaintext letter gets replaced by several ciphertext letter, depending on which alphabet is used)

Vigenère Cipher

* basically multiple caesar ciphers
* key is multiple letters long K = k_(1) k_(2) ... k_(d)
* ith letter specifies ith alphabet to use
* use each alphabet in turn, repeating from start after d letters in message

Plaintext: THISPROCESSCANALSOBEEXPRESSED

* more generally could use a more complex equation to calculate the ciphertext letter for each plaintext letter

E(a,b) : i ->a.i + b mod 26

a must not divide 26 (i.e., gcd(a,26) = 1)

otherwise cipher is not reversible, e.g.,
a=2 and a=0, b=1, c=2 ... , y=24, z=25
eg E(5 7) : i ->5.i + 7 mod 26
Cryptanalysis

* use letter frequency counts to guess a couple of possible letter mappings (frequency pattern not produced just by a shift)
* use these mappings to solve 2 simultaneous equations to derive above parameters