-
Cracking the Viginére
The mathematical techniques for attacking the Vignére are quite sophisticated. The principle part of the attack involves determining the length of the key, n say. Once this is done the problem resolves itself into breaking n separate Caesar ciphers.
The main defence against this attack is to use very long keys resulting in insufficient data for an effective attack. The idea of extending the key will be returned to later!
Variants
There is no reason for the Viginere square to be constructed in a regular manner –as long as sender and receiver work from the same table. A particularly important variant is the Beaufort Table. This table is essentially the same as the viginere except the rows are reversed. A small section of the table follows.
a b c d e f g h i j k l m n o p q r s t u v w x y z a Z Y X W V U T S R Q P O N M L K J I H G F E D C B A b A Z Y X W V U T S R Q P O N M L K J I H G F E D C B c B A Z Y X W V U T S R Q P O N M L K J I H G F E D C $\ldots$ The advantage of the Beaufort table is that encipherment and decipherment are identical processes. This property, while not particularly useful with hand worked algorithms, is very useful when ciphers are implemented on physical devices: the same program does both jobs! To see this property use the key abc and encipher ‘the’. The ciphertext becomes GTX. Repeat the encipherment process with GTX and ‘the’ is returned.
Note that the Beaufort table is in no way more secure than the Vignére table – the advantage is purely from the calculation perspective. [Calculation efficiency plays an important role in modern ciphers because of the sheer quantity of data that has to encrypted.]
The basic idea of using polyalphabetic substitutions can be extended to incorporate monoalphabetic components other than the Caeser shift (the one used by the Vignere cipher); though these require more work to encrypt and decrypt (this is not too much of a problem for an automated system).
Polygraphic Ciphers
Another attempt at creating ciphers that are not susceptible to attacks based on frequency analysis is to substitute pairs (or priles etc) of letters. The most famous example of this is the Playfair cipher.
Polygraphic ciphers should not be confused with polyalphabetic ciphers, which replace individual symbols with differing arrangements of an alphabet; whereas the polygraphic replaces groups of symbols.
The Playfair Cipher
First create a $5 \times 5$ square – this will contain all the letters of the alphabet (i and j are both treated as i). The key is an agreed word or phrase – for example Wheatstone (the true inventor of this cipher). Repeated letters are deleted from the key and the remaining letters are entered into the top of the $5 \times 5$ square.
w h e a t s o n b c d f g i/j k l m p q r u v x y z The plaintext is divided into pairs. If the pair of letter are in a different row and column then we encipher using the generated rectangle; eg ‘hi’ is enciphered ‘af’ but note that ‘ih’ is enciphered as ‘fa’ – the order is important.
If the letters are in the same row then they are enciphered by choosing the adjacent letters on the right; with wrap around for letters in the last column; eg ‘ob’ goes to ‘nc’ and ‘bc’ goes to ‘cs’.
If the plaintext letter pair are in the same column then we chose the letters below each; e.g. ‘aq’ goes to ‘by’. If the letter is in the last row we return at the top, so ‘tz’ goes to ‘ct’
The only problems that can arise are double letters and an unpaired last letter. These are both handled using x (or q say): we add x to the end of text – if needed -to ensure we have a letter pair for encryption, and we insert an x between double letters.
To decipher we reverse the process. Note that if ciphertext digraph are letters in the same row or column then we look to left or above.
EXAMPLE
Use the Playfair code in the above to encipher: ‘this day is soon over’
PLAINTEXT : th is da yi sx so xo no ve rx
CIPHERTEXT : WE DB IW AQ NU DN VN BN XH PZ
Deciphering example:
CIPHERTEXT : AK PH QE NU NW NU
PLAINTEXT : ti me pa sx se sx = time passes
Attacking the Playfair
Characteristics. If we have ciphertext examples we note that they always have an even number of symbols and no letter appears repeated!
This is susceptible to a frequency analysis attack: the frequency of letter pairs are non-uniform; for example ‘th’ and ‘et’ occurs often, but ‘tz’ occurs seldomly (note the bigram might end one word and start another).
There is quite a lot of structure in the code; in particular it is possible to quickly deduce which letters are in the same row and column of a given letter. This can be utilised to speed up an attack.
-
Transposition Ciphers
A transposition cipher is a rearrangement of the symbols in the plaintext. The rearrangement has to be carried out in a manner that can undone by the receiver – it cannot be haphazard. (On the other hand the rearrangement must not be too obvious or this will undermine concealment.)
We consider a simple example.
Example
Who is the winner; what was the score?
Rewrite in $5$ columns as shown below (drop spaces and punctuation) and pad (with $x$) to make a multiple of $5$.
$\matrix{w & h & o & i & s \\ t & h & e & w & i \\n & n & e & r & w \\ h & a & t & w & a \\ s & t & h & e & s \\ c & o & r & e & x}$
Read the text downward to get
WTNHSCHHNATOOEETHRIWRWEESIWASX
To decrypt :divide into 5 blocks of text write vertical and read across.
This can be further complicated by reordering the columns according to a predefined key. If the key is $13254$ for example
Example
Using the same plaintext as the last example; write as 5 columns in the last example then interchange the columns 2 and 3, and columns 4 and 5.
$\matrix{w & o & h & s & i \\ t & e & h & i & w \\n & e & n & w & r \\ h & t & a & a & w \\ s & h & t & s & e \\ c & r & o & x & e}$
Read the text downwards to get:
WTNNSCOEETHRHHHATOSIWASXIWRWEE
To decrypt reverse the process: divide into 5 blocks; write each block vertically; reorder the columns by reversing the permutation given by the key; and read horizontally.
Cracking the above code;
An analysis of the frequency returns the conventional frequency correspondences : E matches to e; T with t etc. This suggests that the conventional English has undergone transposition.
Determine the total number of letters and its divisors and try each of the following in turn: divide text up into chunks of appropriate size and write as columns; look to find anagrams in the rows as a means of determining the reorder sequence.
Transposition Matrices
We introduced this topic in the lecture on matrices.
DEFINITION
A permutation matrix is a square matrix in which a 1 appears precisely once in each row and column; the remaining elements are all zero. The matrix can be any size.
Example
$\pmatrix{0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0}, \pmatrix{0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0}$
Transposition matrices can be used to encipher text replaced by numbers (e.g. $a=1; b=2; \ldots; z=26, \text{Space}=0$). Divide text into fixed size chunks, which are used to form column vectors. If the text length not a multiple of the chunk size then pad with spaces.
For example (using chunks of size three): ‘To busy’. $20, 15, 0, 2, 21,19, 25,0,0$ becomes $(20,15,0)^T, (2,21,19)^T,(25,0,0)^T$ (note the $T$ for transpose which means that these are in fact column vectors!
We now create a new message (cryptogram) by multiplying the vectors by a permutation matrix. For example:
$\pmatrix{0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0}\pmatrix{20\\15\\\;\,0} = \pmatrix{15 \\\;\, 0 \\ 20}, \pmatrix{0 & 1 & 0 \\ 0 & 0 & 1 \\1 & 0 & 0} \pmatrix{\;2 \\ 21 \\ 19} = \pmatrix{21 \\ 19 \\ \;\, 2}$ and $\pmatrix{0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0}\pmatrix{25 \\ \;\,0 \\ \;\, 0} = \pmatrix{\; 0 \\ \; 0 \\ 25}$
Which on putting back into a message gives $15, 0, 20, 21, 19, 2, 0, 0, 25$.
Which can be deciphered back into in letters: ‘o_tusb__ y’
The last example is fairly trivial but for large matrices transposition combined with substitution can generate non-trivial ciphers.
To decipher the original ciphergram; requires the inverse of the original permutation matrix. The inverse is another permutation matrix (unsurprisingly!)
$\pmatrix{0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0}^{-1} = \pmatrix{0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0}$
(You can check this by multiplying the two matrices to get the identity).
$\pmatrix{0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0}\pmatrix{15 \\ \;\,0 \\ 20} = \pmatrix{20 \\ 15 \\ \;\,0}, \pmatrix{0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0}\pmatrix{21 \\ 19 \\ \;\,2} = \pmatrix{\;2 \\ 21 \\ 19}, \pmatrix{0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0} \pmatrix{\;\, 0 \\ \;\, 0 \\25} = \pmatrix{25 \\ \;\,0 \\ \;\, 0}$
Which returns the original message.
These ciphers are very easy to crack.
NOTE: The inverse of a permutation matrix is the transpose of the matrix
Example
$\pmatrix{0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0}^{-1} = \pmatrix{0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0}^{T} = \pmatrix{0 & 0 & 1 \\ 1 & 0 & 0 \\0 & 1 & 0}$
(Note this only applies to the permutation matrix – but still a useful result)
Example
Find the inverse of the permutation matrix
$\pmatrix{0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0}$
and comment.
Solution
$\pmatrix{0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0}^{-1} = \pmatrix{0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0}$
Comment: the same matrix, which is not surprising since the original permutation interchanges the first and the third elements, the inverse operation will do the same thing to change them back.
-
Historical Cryptosytems
An obvious variant on simple substitution and transposition is to use a mixture of both in the encipherment process. Even these blended ciphers are prone to attack and modern cipher systems are based on new approaches, which we will describe later.
We briefly indicate a few systems of purely historical interest.
The Polybius Checkerboard
This system is older than the Caeser System and is a variant on the mono-alphabetic substitution cipher. Pairs of numbers are used to substitute for letters.
1 2 3 4 5 1 A B C D E 2 F G H IJ K 3 L M N O P 4 Q R S T U 5 V W X Y Z Plaintext: plato
Ciphertext: 35 31 11 44 34.
This system can be used with torches for shore to ship communication (a type of semaphore). It was famously used by Russian political prisoners using paired groups of taps (eg M -> tap-tap-tap, tap-tap (32) ).
What is particularly interesting about this system it that it is designed to match the technology of the communication channel In a similar approach, modern ciphers are designed around computer systems and modern communications.
The Polybius Checkerboard could be viewed as more of a code than a cipher); though introducing a Key word, such as in the Playfair example demonstrated previously, could make this a cipher to compare with general mono-alphabetic ciphers.
ADFGVX
This cipher from World War I operates as a Polybius checkerboard combined with a transposition. It is a good example of how complex crytptographic systems can be built up out of primitives. [But note that it is not always necessarily a good idea to simply put cipher techniques on top of each other - for example enciphering twice with a mono-alpahbetic system does not add security; it could even be dangerous!]
The checkerboard used is:
A D F G V X A F L 1 A 0 2 D J D W 3 G U F C I Y B 4 P G R 5 Q 8 V E V 6 K 7 Z M X X S N H 0 T 9 Plaintext letters are replaced by the pair of letters in the row and column: for example L is enciphered as AD.
The plaintext ‘CRYTOGRAM’ becomes FA GA FF FX XV AV DV GA AG VV
This encoding is then enhanced using columnar transposition based on a keyword. Suppose the keyword is SCOT. Write down message below SCOT and then generate a transposition based on the alphabetic order of the keyword.
$\matrix{S & C & O & T \\ 3 & 1 & 2 & 4 \\ \\F & A & G & A \\F & F & F & X \\ X & V & A & V \\ D & V & G & A \\A & G & V & V}$
Read off the columns in the order indicated : AFVVG GFAGV FFXDA AXVAV [Note how this procedure splits the pairings!]
This is another system designed to match the technology it was being run over. The choice of letters ADFGVX was because of their ease in Morse code transmission.
-
Summary
In this lecture we have introduced some ciphers of historical significance. None of these ciphers are in use today, but the lessons learned from them are still relevant.
Identifying attacks on ciphers guides us in the development of new ciphers. For example no new cipher should be susceptible to a frequency attack or any other types of attack that can be identified from the historical precedent.
Additionally, we have seen that it is useful to marry the cipher system to the technology that will be used to carry the ciphertext. For example the ADFGVX code was based on the distinctiveness of the letters when transmitted using Morse code - helping to reduce the possibility of operator error. The Polybius checkerboard was designed to be used with torch signalling.
The importance of historical ciphers in understanding the design principles for new ciphers should be clear.