Lecture Notes on Cryptography

Subsection 2.1 Shift ciphers

In a shift cipher we replace each letter in the message by a letter that is some fixed number of positions further along in the alphabet. Julius Caesar used a special shift cipher to communicate important military information to his military commanders. The length of the shift we are using is called the encryption key. In case of the Caesar cipher it is 3. If we use a 26 letter alphabet, then the encryption can be formulated as follows

where \(p_1,p_2,\ldots\) denotes the sequence of letters in the plaintext and \(c_1,c_2,\ldots\) is the sequence of letters in the ciphertext, the \(k\) stands for the encryption key. Given a ciphertext character \(c_i\) the corresponding plaintext character can be determined by the formula

We will use a quote from Adi Shamir as a plaintext: “Fully secure systems do not exist today and they will not exist in the future.”

There are only 26 possible keys, hence a brute force attack is applicable here.

Subsection 2.2 Affine ciphers

A generalization of the shift cipher is given by the so-called affine cipher. Here we use a function of the form \(ax+b,\) where \(\gcd(a,26)=1.\) A ciphertext character \(c_i\) is computed via the formula

To recover \(p_i\) from \(c_i\) we apply the congruence given by

This is the point where we see why the assumption \(\gcd(a,26)=1\) is important, otherwise the multiplicative inverse of \(a\) does not exist modulo 26. Here we use the same Adi Shamir quote as plaintext as in case of the shift cipher.

A brute force attack can easily break the system, here the possible number of keys is \(26\times 26\) even if we count those violating the \(\gcd\) condition. We only display 40 candidate decipherments.

Subsection 2.3 Hill ciphers

Affine ciphers use functions of the form \(f(x)=ax+b,\) so these are one-dimensional ciphers. Hill ciphers act on blocks of \(k\) characters. Given a \(k\times k\) matrix \(A\) such that modulo 26 it has an inverse and \(b\) is a \(k\)-dimensional vector. A ciphertext block \(C_i\) is computed by using the formula

To recover \(p_i\) from \(c_i\) we apply the congruence given by

Subsection 2.4 Substitution ciphers

We consider an alphabet \(\mathcal{A}\text{,}\) let say all the capital letters from ’A’ to ’Z’. Encryption is based on a substitution that is we take a permutation \(\pi: \mathcal{A}\rightarrow \mathcal{A}\) and in the plaintext we replace each letter \(\alpha\) with \(\pi(\alpha).\) To decrypt a ciphertext we simple replace each letter \(\beta\) in the ciphertext with \(\pi^{-1}(\beta).\) Exhaustive search is now much more difficult than in case of shift ciphers, here the key space has \(26!\) elements.

Subsection 2.5 Vigenère ciphers

An extended version of affine ciphers. Blaise de Vigenère wrote a book in 1586 in which he described the known ciphers of his time. This cipher is named after him. The Vigenère cipher uses a keyword of any length greater than one. In case of a Vigenère cipher we add each of the index of the plaintext character to the index of the keyword character using the so-called Vigenère square.

Let \(M=M_1M_2\ldots M_n\) denote the message represented by numbers between 0 and 25 (\(A=0,B=1,C=2\) etc.), \(K=K_1K_2\ldots K_n\) is the key obtained by repeating the keyword and \(C=C_1C_2\ldots C_n\) is the ciphertext. The encryption and decryption can be described algebraically as follows

If the plaintext is ’CRYPTOGRAPHY’ and the keyword is ’SEVEN’, then we have

and here \(M_1=2\) since the first character in the plaintext is ’C’. In a similar way we get that \(K_1=18,\) since the first letter in the keyword is ’S’. Therefore \(C_1=2+18=20\pmod{26}\) and the first letter in the ciphertext is ’U’. The complete encryption is SageMath can be done as follows.

Decryption is easy by using the Vigenère square, if we consider the row of the letter ’S’ we look for the corresponding ciphertext letter (in our example it is ’U’) and we see that it is in the third column, the column of ’C’. Thus the first letter in the plaintext is ’C’.

To break the Vigenère cipher first we need to figure out the length of the keyword. This is done by applying the so-called Kasiski method. It uses the fact that certain plaintext fragments occur quite frequently, while other plaintext fragments occur infrequently. The list of the distances that separate the repetitions has a key role here. The length of the keyword is likely to divide many of these distances. Let us try to use this idea in case of a quote by Anand.

There are some substrings that occur a few times, for example

Hence we obtain the list of distances \([30,5,5].\) We may guess that the length of the keyword is 5. We partition the encrypted message into 5 parts:

Frequency analysis is useful to break shift ciphers. The characteristic frequency probability distribution table of Beker and Piper can be obtained in SageMath using the code:

There is an other table by Lewand:

Thus characters with a high frequency of occurence are E,A and T. In case of

we obtain the following frequency distribution

{A: 0.0204081632653061, C: 0.102040816326531,
 D: 0.0612244897959184, E: 0.0612244897959184,
 F: 0.0408163265306122, G: 0.102040816326531,
 H: 0.0408163265306122, I: 0.0204081632653061,
 J: 0.0408163265306122, K: 0.0816326530612245,
 N: 0.0204081632653061, P: 0.0408163265306122,
 Q: 0.0816326530612245, R: 0.0204081632653061,
 T: 0.0408163265306122, U: 0.0408163265306122,
 V: 0.122448979591837, W: 0.0408163265306122,
 X: 0.0204081632653061}

It suggests that here V is E,A or T. The second partition given by

has

{A: 0.0816326530612245, B: 0.0204081632653061,
 C: 0.0204081632653061, F: 0.0612244897959184,
 H: 0.0408163265306122, I: 0.0204081632653061,
 J: 0.0408163265306122, K: 0.0204081632653061,
 L: 0.142857142857143, M: 0.0612244897959184,
 O: 0.102040816326531, P: 0.0612244897959184,
 S: 0.0408163265306122, T: 0.0816326530612245,
 U: 0.0408163265306122, V: 0.0408163265306122,
 W: 0.0204081632653061, Y: 0.0204081632653061,
 Z: 0.0816326530612245}

Therefore we may expect that L is one of the letters E,A or T. In this way we only need to check a few possible shifts in a given partition. In this concrete example we obtain that

Subsection 2.6 ADFGX and ADFGVX ciphers

The German Army used the ADFGX cipher during World War I. It is named after the five letters used in the ciphertext: A, D, F, G and X. These letters were chosen in a way to reduce the possibility of operator error, these are very different from each other when transmitted via morse code. To see how the encryption works let us provide the steps involved.

• We need to construct a so-called polybius square, a \(5\times 5\) matrix containing the letters from ’a’ to ’z’ in such a way that ’i’ is considered to be the same as ’j’. For example

  \begin{equation*} \begin{array}{c c} & \begin{array}{c c c c c } A & D &F & G & X\\ \end{array} \\ \begin{array}{c} A \\ D\\ F\\ G\\ X \end{array} & \left(\begin{array}{rrrrr} m & z & t & x & i/j \\ q & u & b & w & c \\ k & g & n & p & d \\ y & e & r & s & o \\ l & h & a & v & f \end{array}\right) \end{array} \end{equation*}

• To encode a plaintext we use the above matrix in the following way: \(m\rightarrow AA, z\rightarrow AD, \ldots, f\rightarrow XX.\) For example the plaintext ’cryptography’ is going to be

  \begin{equation*} DX GF GA FG AF GX FD GF XF FG XD GA. \end{equation*}

• A code word is chosen and we write the enciphered plaintext underneath. Following the above example using the code word CIPHER we obtain

  C	I	P	H	E	R
  D	X	G	F	G	A
  F	G	A	F	G	X
  F	D	G	F	X	F
  F	G	X	D	G	A

• We apply a columnar transposition, that is we sort the code word alphabetically, moving the appropriate columns as well. In the above example we get

  C	E	H	I	P	R
  D	G	F	X	G	A
  F	G	F	G	A	X
  F	X	F	D	G	F
  F	G	D	G	X	A

• We read the final ciphertext off in columns as follows

  \begin{equation*} DFFF GGXG FFFD XGDG GAGX AXFA. \end{equation*}

An extension based on six letters A, D, F, G, V and X was invented by Colonel Fritz Nebel and introduced in March 1918. It uses a 6 by 6 polybius square containing all the letters and the numbers from 0 to 9. Let us describe the steps in case of the plaintext ’cryptography2020’ and with code word ’MOVE’.

• We fix the polybius square as follows

  \begin{equation*} \begin{array}{c c} & \begin{array}{c c c c c c } A & D &F & G &V & X\\ \end{array} \\ \begin{array}{c} A \\ D\\ F\\ G\\ V \\ X \end{array} & \left(\begin{array}{rrrrrr} m & j & t & z & 0 & 1 \\ u & 6 & w & 9 & g & d \\ 4 & e & y & r & l & v \\ h & s & a & 3 & x & i \\ q & b & c & k & 2 & 8 \\ 7 & 5 & n & p & o & f \end{array}\right). \end{array} \end{equation*}

• Encoding the plaintext ’cryptography2020’ using the above polybius square yields

  \begin{equation*} VF FG FF XG AF XV DV FG GF XG GA FF VV AV VV AV. \end{equation*}

• The code word is ’MOVE’ so we have

  M	O	V	E
  V	F	F	G
  F	F	X	G
  A	F	X	V
  D	V	F	G
  G	F	X	G
  G	A	F	F
  V	V	A	V
  V	V	A	V

• We sort the code word alphabetically together with the corresponding columns to obtain the ciphertext

  \begin{equation*} VFADGGVV FFFVFAVV FXXFXFAA GGVGGFVV. \end{equation*}

A possible SageMath implementation with a random polybius square is as follows.

Subsection 2.7 Playfair cipher

The Playfair cipher is named after Lord Lyon Playfair who promoted the use of the cipher. The cipher itself was invented by Charles Wheatstone in 1854. The British Army in World War I used as the standard field system. It is also based on a polybius square like the ABFGX and ABFGVX ciphers, however here one uses a keyword as well to form the appropriate \(5\times 5\) square. The two letters I and J are identified out of the 26 capital letters used in the cryptosystem. For example if we have KEYWORD given as a keyword, then the corresponding polybius square is

We will demonstrate the rules used in the encryption process using the plaintext COMMUNICATION and the polybius square given above.

• We split the plaintext up into digraphs: CO MM UN IC AT IO N.

• If a digraph consists of the same letter twice, then we insert an X between them. If the length of the plaintext is odd, then we add an X at the end. In our example we have MM as a digraph hence we get CO MX MU NI CA TI ON.

• If the two letters in a digraph appear on the same row in the polybius square, then replace each letter by the letter immediately to the right of it in the polybius square (cycling round if necessary). In our example we have CA in a given row, it is encrypted as RB.

• If the two letters in a digraph appear in the same column in the polybius square, then replace each letter by the letter immediately below it in the polybius square (cycling round if necessary). In the example the digraph CO is encrypted as LC.

• If the two letters are not in the same row or column, then form the rectangle for which the two letters are two opposite corners. We replace each letter with the letter that forms the other corner of the rectangle that lies on the same row. Let us see this latter rule in action in our example. We have

  MX	\(\longrightarrow\)	QT
  MU	\(\longrightarrow\)	NT
  NI	\(\longrightarrow\)	QG
  TI	\(\longrightarrow\)	XF
  ON	\(\longrightarrow\)	ES

  .

That is the plaintext COMMUNICATION is encrypted as LCQTNTQGRBXFES.

The following SageMath implementations are due to Alasdair McAndrew (see https://trac.sagemath.org/ticket/8559) and modified by Catalina Camacho-Navarro (see https://wiki.sagemath.org/interact/cryptography#Playfair_Cipher). First we consider the encryption part.