Cryptography

For information on our Discover Cryptography program and how to book, click here.

The Discover Cryptography workshop provides an insight into modular arithmetic as a gateway to various methods of public key cryptography, and touches on the workings of state-of-the-art private key cryptography methods such as RSA.

Here is an insight to some of the content covered in the workshop…

Encoding and Decoding

In order to use any of the encryption techniques in the workshop, we first need to encode our plaintext message from letters into numbers. This is the basic encoding from the workshop:

Example: If we wanted to encode the word “hello”, for example, we would do so by replacing the letters by their corresponding numbers in the table above:

So the plaintext “hello” is encoded to 7 4 11 11 14.

Encrypting and Decrypting

In the workshop, we look at a few different methods of encryption and their respective methods of decryption. Here’s a summary of the ones we cover and their methods:

Caesar Shift Ciphers

Caesar Shift Ciphers are named after Julius Caesar, the Roman emperor, who encrypted secret messages to his army generals in this way. This is how it’s done:

1. Convert your message into numbers (encode).
2. Choose a key number.
3. Add the key number to each number (shift).
4. Reduce the numbers mod 26.
5. Convert your message back to letters (decode).

Example: If we choose the key number to be 15 and want to encrypt the plaintext “hello” using a Caesar Shift Cipher, it would work like this:

So the plaintext “hello” is encrypted to the ciphertext “wtaad”.

If you know what they encryption key was, you just work backwards to decrypt (encode the ciphertext, subtract the key, reduce mod 26, and then decode). If you don’t know the shift key, you might need to use a bit of frequency analysis or knowledge of common word endings, letter combinations or short words within the language you’re working in to figure out the key.

Affine Ciphers

An affine cipher is like a Caesar shift cipher, but with an added layer of complexity. Instead of shifting everything by a constant value, we shift by an affine function in the form $ax+b$.

Example: If we encrypt the plaintext “hello” using the affine function $3x+2$, it would work like this:

So the plaintext “hello” is encrypted to the ciphertext “xojjs”.

Decrypting affine ciphers is more complex. We’re used to being able to find inverses of functions quite easily by working backwards and applying the inverses of each individual operation in the function in reverse BIDMAS order. Using our prior knowledge of functions, we could find the inverse of the function $3x+2$ to be $\frac{1}{3}(x-2)$.

Unfortunately when working mod 26 (or mod anything for that matter), fractions don’t exist – we only have the integers from 0 to 25 (or 0 to $n-1$ for mod $n$). With this, we need to find the multiplicative inverse of 3 mod 26 in order to find the decrypying function; that is, the number we can multiply by 3 to get 1 mod 26. This can be found quite easily, as $3\times9=27\equiv1\text{ mod }26$. This means that the inverse function would actually be $9(x-2)$ or $9x-18$ if we expand it.

Example: We can work backwards from the ciphertext we found above to check this is correct.

So the decryption key which corresponds to the encryption $3x+2$ is $9x-18$.

Not all affine ciphers are valid for encryption, as not all numbers are invertible (or reducible) mod 26. Only numbers which have no common factors with 26 have inverses and so whilst the $b$ in $ax+b$ can be anything, the $a$ must only be invertible / reducible mod 26 when working with a basic 26-letter alphabet (i.e. working mod 26).

The following SageMath code computes the inverses of each of the invertible / reducible numbers mod 26.

The reason we can’t use a non-invertible / irreducible number for $a$ in an affine cipher can be seen when we try the affine cipher $2x$. If we encrypt the encoded alphabet (numbers 0-25), we get the ciphertext alphabet which is shown by the following SageMath code:

You’ll notice that the ciphertext alphabet begins to repeat itself halfway through, which means that if the plaintext letters a (0) and n (13) both encrypt to the ciphertext letter a (0), so it would be impossible to decrypt a message encoded by this affine cipher or any affine cipher which uses a non-invertible.

Have a play around with the code above and change the value of $a$ to any other non-invertible number mod 26 (2, 4, 6, 8, 10, 12, 13, 14, 16, 18, 20, 22, 24, or 26) and you’ll see a similar outcome of a repeated alphabet.

Vigenère Cipher

For a long time, the Vigenère Cipher was regarded to be unbreakable. It’s very simple to encrypt something using this cipher, but unless you know the key, it’s very difficult to decrypt. The Vigenère Cipher works as follows:

1. Choose a password and encode it.
2. Convert your message into numbers (encode).
3. Shift the $n^{th}$ letter of your encoded plaintext by the value of the $n^{th}$ letter in the password (shift).
4. Continue on until you reach the end of your password.
5. Move back to the start of your password and shift the next letter of your encoded plaintext by the value of the first letter in the password (shift).
6. Repeat steps 4 and 5 until your message has been encrypted.
7. Reduce the numbers mod 26.
8. Convert your message back to letters (decode).

Example: If we choose the password to be “code” and want to encrypt the plaintext “Message” using a Caesar Shift Cipher, we would first encode our password:

This tells us how much to shift each letter of our message by when encrypting. The encryption works like this:

So the plaintext “message” is encrypted to the ciphertext “osvwcuh”.

Public Key Cryptography: RSA

For information on our Discover Cryptography program and how to book, click here.