Let's start by considering a simple cypher. Indeed, one of the simplest.

Atbash is a simple cypher dating from biblical times. It was originally used to encrypt the Hebrew alphabet. Its function is simple. Each letter is replaced the letter found by reversing the alphabet. a is replaced by z, b is replaced by y, and so on, as shown in the table below:

Atbash is one of a class of cyphers called monoalphabetic substitution cyphers, because each letter is always substituted for the same letter, wherever it occurs in the plaintext.

Atbash, as you can work out for yourself, is reversible. By applying the same process to an encrypted word, the plaintext is recovered. Thus if I was to give you the word:

Plaintext = Cyphertext = shibboleth
Show Colours

To study such cyphers mathematically, it can be helpful to express them as a mathematical function. To do so, we represent each letter of the alphabet is a number. a is 0, b is 1, c is 3, etc. For the present cypher, we will call the value of a given letter $X$. We will express the encrypted form as the result of the function $E(X)$.

Thus the encrypted form of a, which is represented by the value 0, is $E(0) = 25 - 0$. 25 is the value that represents z, the last letter in the alphabet.

We could write any number of functions to encrypt text. Once we have decide on a way to convert plaintext symbols into numbers (e.g. by representing a with 0, etc.) we can then perform any computations on these numbers that we like. However, not all computations are going to be equally useful as cyphers. For instance, while the cypher $E(X) = 0$ (replace all letters with 0 or a) is unbreakable, the plaintext is completely unrecoverable!

One problem that we quickly encounter when playing with cyphers is that we only have 26 letters in the alphabet (and any alternative alphabet we might choose is finite). The cypher text must fit within the range of values that can be represented with our alphabet.

The Caesar cypher is a simple shift cypher used by Julius Caesar in his private correspondence. To use it, find the value for each letter in the plain text and add a number, such as 3. This is the cypher's key. In order to prevent the letters at the end of the alphabet falling off the end, we will make the alphabet 'wrap around' through the use of the modulus operation $mod$. Thus the Caesar cypher can be written as the function:

With a key of $k=3$, the letter z becomes c. The 'wrapping' is achieved by the modulus operation.

Play with the tool below to see how changing the value of $k$ affects the cyphertext. Observe how the values 'wrap around' at the end of the alphabet due to the mod operation.

k = Show Colours

To understand the mathematics behind these sorts of cyphers we need to understand the mod operation and modular arithmetic.

We saw that to understand cryptography we need to understand modular arithmetic.

You will be familiar with performing arithmetic on a number line. The numbers run from negative infinity, past 0, to positive infinity. Now imagine we cut the number line so it only runs between 0 and a finite number, say 11. Now bend the number line into a circle. Now what happens if you start with the last number (here, 11), and add 1 more? You wrap around back to 0!

If this is hard to imagine, realise that the same idea applies when performing arithmetic on a 12-hour clock. For example, ten o'clock plus three hours is one o'clock, not thirteen o'clock.

When working under modulus, we only work with integer values from 0 (inclusive) to our modulus (exclusive). That is, we are performing arithmetic on a finite set of integers. For example, when we add numbers together, we do not always get a larger value because the values 'wrap around', as illustrated in the figure below:

If we are performing modular arithmetic, we write the modulus we are using at the end in brackets. For example, a simple addition under modulus $5$ might be written:

The symbol $\equiv$ will be explained below.

You might have noticed there is a relationship between modular arithmetic and the remainder of a division. For example, if I were to perform the integer division of 12 and 4, I would find that the remainder is the same as the value of 12 under the modulus 4:

As I have done here, we can apply modulus as an operation when working in otherwise normal arithmetic. We do this using the $\\mod$ operation.

The modulus operation, written mod (and written in most programming languages as %) takes two arguments $a$ and $b$, and returns the remainder from dividing $a$ by $b$. Note that mathematically, mod returns a positive integer, however most programming languages treat % as the remainder, which can be negative and in some situations a decimal.

To find $x \mod m$ of any x, you can follow the following process:

1. If \( x < 0 \), repeatedly add $m$ until \( 0 \leq x < m \)
2. If \( x \geq m \), repeatedly subtract $m$ until \( 0 \leq x < m \)

Remember, your result will always be in the range \( 0 \leq x < m \)

A key property of modular arithmetic is the equivalence of different (non-equal) numbers. You might have noticed the following when performing addition under modulus (if you didn't take a look at the questions above again):

• Under modulus $m$, the result of adding $x$ to a number is the same as adding $(x+m)$

In other words, if we start at a number, and count on the value of our modulus, we get back to the place we started! We can count on as many multiples of our modulus as we like, but every whole multiple of our modulus will get us back to the same place. This indicates a fundamental equivalence between different numbers in modular arithmetic.

Two numbers in our modular arithmetic $a$ and $b$ are equivalent (called congruent) if they differ by a multiple of the modulus (i.e. if $a-b = kx$). Congruence is written using the symbol $\\equiv$. We can express this 'getting back where you started' property with the formula:

It may be helpful to visualise this using the circle below. The modulus 12 is the set of natural numbers smaller than 12, including 0: \( \{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 \} \). The central circle below contains all these numbers. Outside are shown the first three different numbers that are congruent to each middle number under this modulus (though in principle this could be continued indefinitely). For example, 12, 24, and 36 are all congruent to 0 modulo 12.

This gives us sets of numbers called congruence classes. In the above there are $12 congruence classes, which we might label \( {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} \).

The congruence class $0$ is the set of numbers \( \{ 0, 12, 24, 36, 48, 60, 72, \dots \} \)

The congruence class $1$ is the set of number \( \{ 1, 13, 25, 37, 49, 61, 73, \dots \} \)

The congruence class $2$ is the set of number \( \{ 2, 14, 26, 38, 50, 62, 74, \dots \} \)

The congruence class $3$ is the set of number \( \{ 3, 15, 27, 39, 51, 63, 75, \dots \} \)

...and so on.

When we are working under modulus, the different elements of a congruence class are completely equivalent.

You could also think about modular arithmetic being as arithmetic on these classes, For example, under a modulus of 12, if you take something in the class \( 11 \) (\( \{11, 23, 35, \dots \} \)) and add something from the class $1$ (\( \{1, 13, 25, \dots \} \)) and you will get something from the class $0$ (\( \{0, 12, 24, \dots \} \)).

We have already seen modular addition. Modular subtraction is similar.

To calculate \( a - b \pmod{m} \) we can first calculate $a-b$ and then use the mod operation. Remember the result will be non-negative.

(Note: The arrow below is drawn backwards. SVGs are hard to work with.)

Subtraction can also be seen as the addition of the additive inverse of a number.

The additive inverse of a number is the number you need to add to $a$ to get 0. Usually this is straightforward. The additive inverse of 5 is -5 in normal arithmetic because 5 + (-5) = 0.

However when working under modulus, we do not have negative numbers! Still, because of the 'wrapping' effect, there exists an additive inverse for every number under modulus.

For all \( w \in \mathbb{Z}_n \) there exists a $z$ such that \( w + z \equiv 0 \pmod{n} \).

For example, the additive inverse of \( 5 \pmod{7} \) is \( 2 \) because \( 5 + 2 \equiv 0 \pmod 7 \).

Let us see a cypher that is a little more interesting than the Caesar cypher. The table below illustrates the Affine Cypher. This is another monoalphabetic substitution cypher, which is defined by the encryption function:

This cypher has two keys, $a$ and $b$.

To encode this cypher we need to perform multiplication, which is straightforward, as you will see. However, decoding the cypher is a little more challenging. The inverse of multiplication is division, and modular division is rather counter-intuitive. First we will understand multiplication and then we will consider the inverse of multiplication, division.

Multiplication is repeated addition, so other than the wrapping property we have already described, multiplication under modulus works as normal.

We can calculate \( a \times b \pmod{m} \) by first calculating $a \times b$, and then using the modulus operation.

To decode the Affine cypher we will need to perform the inverse of multiplication, which is division.

The multiplicative inverse of a number $a$ is the number you need to multiply by $a$ to get 1. This can be notated $a^-1$.

Like additive inverse, this is straightforward for arithmetic on the real numbers (i.e. where we can have fractional answers). For instance, the multiplicative inverse of $ 5 $ is \( \frac{1}{5} \), because \( 5 \times \frac{1}{5} = 1 \).

However, when we are working under modulus $m$, we can only use those whole numbers that are permitted under our modulus (i.e. between 0 and $m-1$). This should be clear if you think about the Affine cypher. If we tried to decrypt text encoded with the affine cypher, and the inverse of multiplication gave us a decimal value, it would not correspond to a letter in our alphabet!

Recall that the multiplicative inverse is the number that you need to multiply by to get to 1. Under modulus, this number must be a whole number. It happens that this may in fact be larger than dividend because the wrapping effect can still lead to a result of 1.

For example, the multiplicative inverse of \( 5 \pmod7 \) is $3$, because $5 \times 3 \equiv 1 \pmod{7}$. This is defined because 5 and 7 are co-prime. Their greatest common denominator is 1.

Note that, under a modulus of $n$, the multiplicative inverse of a number $w$ is only defined if $n$ and $w$ are co-prime (i.e. the greatest common divisor of $w$ and $n$ is $1$). Otherwise it is undefined. We will come back to primeness and co-primeness of numbers later in the lecture.

In summary, for all \( w \in \mathbb{Z}_n \), where $w$ and $n$ are co-prime, the multiplicative inverse $a$ is the value such that:

Now we have worked out the modular multiplicative inverse, we can perform modular division, which will let us decrypt the affine cypher.

Observe that division by a number $w$ is the same as multiplication by the multiplicative inverse of $w$. For instance:

Thus to divide by a number $w$ under modulus $n$, we multiply by the multiplicative inverse of $w$, if it is defined. If the multiplicative inverse of $w$ is not defined (because $w$ and $n$ are not co-prime) then the division is not possible (its result is undefined).

When we want to perform the inverse of multiplication, which is division, we can instead multiply by the multiplicative inverse. We can apply this to decrypting the Affine cypher.

As we have seen in calculating the multiplicative inverse, primeness and co-primeness are particularly important in modular arithmetic. Prime numbers are incredibly important for cryptography, so it is worth taking some time to understand them.

Number theory is a branch of mathematics that is interested in the patterns that we can observe in the numbers. Number theory most often deal with just the natural numbers. Considering the natural numbers, we might ask: are all numbers essentially the same, or do they have some interesting structure?

One way in which the natural numbers have structure is in their divisibility. Some numbers can be divided by other numbers and give a result that is itself a natural number. For instance, $6 \div 3 = 2$. Thus we might say that $2$ divides $6$ (written $2 \mid 6$). Note that not all numbers fit this relationship. For instance, $4$ does not divide $6$ and give a result in the natural numbers. On the other hand, $1$ divides every number. When considering divisibility, certain patterns start to emerge.

A prime number, or a prime, is a number that is only divisible by itself and $1$. For instance, $2$, $3$, $5$, and $7$ are prime numbers. There is no natural number $x$ such that $x \mid 7$, or any other prime for that matter. A prime number has no factors (other than 1 and itself), thus it is not possible to divide a prime number by a whole number to get a whole-numbered result. It's important to note that 1 is not considered to be a prime number.

All other numbers are composite numbers, because they can be expressed as the product of some set of other numbers. Composite numbers can be visualised as a prime factor tree.

To draw a prime factor tree, check whether the value can be divided by any prime numbers, starting with 2 and working upwards. If you find that it can be divided by a prime, make this the first branch of your factor tree. One branch is the prime factor, the other is the result of dividing by this prime factor. Repeat the process until your final result is prime.

When using the Affine cypher, it is necessary to know whether two integers are co-prime. If you pick a key for the Affine cypher that is not co-prime with the modulus, the decryption function will not work. Two numbers are co-prime when their greatest common divisor is $1$.

The greatest common divisor (GCD) of two integers is the largest integer that divides both numbers.

The Euclidean Algorithm is a way of finding the GCD of two numbers $a$ and $b$. This algorithm is given as pseudocode below.

The concept behind one-time pads dates back to the early 20th century. The one-time pad is a form of encryption that provides theoretically perfect security when a perfectly random key is used. However, its strength and its weakness is the size of its key, which must be at least the same length as the message.

Say we had a message such as

To avoid revealing the lengths of words, it is common practice to write the message in 5-character blocks. Of course, we can also encode spaces as just another character. For how, however, we will continue to only think about encrypting letters of the alphabet

Now let us use a key that is the same length as the cypher. Here I have picked the first line of the William Gibson novel Neuromancer.

The process of using a one-time pad is simple. As before, we replace each letter with a number, which we do to the plaintext and the key. $a=0$, $b=1$, etc. We then apply a simple function. To encrypt the $i$th letter of the plaintext, $P_i$, we simply add the $i$th letter of the key, $K_i$, and take the modulus.

To perform this on bits instead of letters, the XOR operation can be used. Any operation could be used so long as you can perform the inverse to recover the plaintext if you know the key. As we saw with the Caesar cypher, the inverse of addition is subtraction.

Note that for a one-time pad to be secure it is essential that the key is random (unlike here, where an English sentence was used). Also, the key must not used more than once. If either of these requirements are broken, an attacker could potentially break the encryption.

Now that you understand modular arithmetic, the mathematics behind Diffie Hellman key exchange are relatively simple.

Alice and Bob publicly agree on two numbers, $p$ (which must be a large prime number to be secure, usually at least 2048 bits) and $g$. They each secretly choose a number, which is called their private key. Alice picks a number $a$ and Bob picks a number $b$.

Prime modulus
Base
Alice's private key
Bob's private key

From this, Alice and Bob each generate a new number called a public key. They do this by finding the modular exponent of the agreed base $b$ with their own private key. The modulus used is $p$, a large prime number they have publicly agreed upon. They share their public keys with each other, making them public and visible to potential eavesdroppers.

Alice calculates the shared secret using her private key.

Bob calculates the shared secret using his private key.

Now Alice and Bob have agreed on the same number $s$ without this number ever being made public. This can be used as the key for another encryption algorithm, such as a stream cypher.