Cryptography

Encryption has been used for far longer than computers have been around. Today we are going to be doing low-tech cryptography. You will be able to draw on your knowledge from the last two weeks.

There are two tasks. The first task is to be performed in the lab. You can move on to the second task when you are ready, or try it in your own time. The second task is very similar to a question on the assessment. If you're struggling with it, you can ask me for help on this practical question.

Mathematics and Problem Solving

2. Cryptography

David Gundry

Task 1: Cypher challenge

Get into a group of around 3-5.

Your task is to develop a cypher. Your goal is to make a cypher that is easy for someone who knows the cypher to decrypt while someone who does not know the cypher used is unable to decrypt it. However, as an additional constraint, all of the steps must be easy to perform by hand. This might involve pen and paper, a pack of cards, or anything easily to hand in the practical lab. You are also not allowed to copy an existing cypher. However, you might want to look at some for inspiration. Your cypher should make use of one or more keys.

Your task is also to crack the cypher of one or more other groups. Which team can create the strongest cypher, and who can crack another team's cypher?

At the end of the session I want each group to send me the instructions for their cypher. Please send me the same plaintext/encrypted messages as you would another group so I can take a crack at breaking them first.

As with much of this module, the more thought you put into this task, the more you will get out of it.

Instructions

Write a complete description of your cypher (both for encryption and decryption) so that anyone could use it to encode and decode messages. I want you to submit this to me at the end of the practical.

Once you're happy with your cypher, encode two messages, each time using different keys. Generate your messages using this tool, which calls the Metaphorpsum API.

Ask another group to try and crack your cypher. To make it easier for the group doing the decryption, give them the plaintext, cyphertext, and key of the first message, in addition to the cyphertext and key of the second message. (If you did not give them the key for the second message, you could use a one time pad that would be unbreakable.)

If they successfully crack your cypher, you might want to consider how you can make it stronger. If they cannot crack it, feel free to offer them hints so you can see how strong your cypher really is.

The restrictions are as follows:

All information necessary for decoding the cypher must be included in your description (you cannot secretly pass information to your target group)
You must be able to complete all steps to encode and decode messages by hand using easily accessible materials in the lab.

Can you crack the cyphers of the other groups? You should make a serious attempt at cracking at least one other group's cypher.

You will be given a message to try and decode.

While the cypher should be workable by hand, you can use any tools you like to try and break it. You might want to look online for tools for cracking common cyphers. You can write scripts to help you. You can even try to brute force it.

Depending on how difficult the cypher is, you may or may not succeed.

Create a cypher

Create a novel cypher that can be worked by hand
Write a description of how to encrypt and decrypt
Challenge another group to crack it

Crack a cypher

Try and decode a message encrypted by another group
They will give you a plaintext/cyphertext/key pair and a plaintext/key pair
You need to work out the algorithm required to turn the plaintext/key into the cyphertext

Questions

Answer these questions about your groups' cypher.

How hard would it be to brute force your cypher? This is related to the key size, but be aware that just increasing the size of the key may not actually increase the number of values an attacker needs to test. For example, no matter how large the keys of the affine cypher are, with an alphabet of 26 characters, there are only 312 values to test.
If you received a message that used your cypher, how would you go about cracking it? Would you use brute force or is there a better way?
If you have not yet given your cypher a mathematical definition, how would you give it one? Analyse how your cypher algorithm functions. Research whether similar cyphers have already been invented.

Hints and Examples

Imagine you create a simple monoalphabetic shift cypher that operates only on alphabetic characters. The formula of the cypher is

\[ E(X) = X+k \mod 26 \]

\[ D(X) = X-k \mod 26 \]

The algorithm for the cypher is as follows:

Convert the message to lower case
Each alphabet character is converted to a number between 0-25. a=0, b=1, etc. (non alphabet characters are unchanged)
Each value is encrypted using the function $ E(X) $above and the letter is replaced with the letter corresponding to the result of this function

This process is reversed for decryption, and the decryption function $ D(X) $ is used.

This cypher has a single key, $ k $. You could encode the same message with two different values of $ k $. The plaintext is:

the quick brown fox jumps over the lazy dog

The cyphertexts for this message, and the keys are as follows:

wkh txlfn eurzq ira mxpsv ryhu wkh odcb grj (k=3)

    aol xbpjr iyvdu mve qbtwz vcly aol shgf kvn (k=7)

At this point, it might be wise to consider how easily another group might crack this cypher before you decide to use it.

A simple shift cypher is not likely to cause an attacker much difficulty. What else could you try?

Remember you are creating a cypher that can be worked by hand. You could use algebraic functions, but you could come up with a visual method.

Hints and tools

Hints, examples, and tools are available on the practical webpage.

Work in your groups, ask other groups for help.

Ask the lecturer and technicians - we don't have the answers, but we can help with your thinking

Task 2: Codebreaking challenge

If for some reason you cannot participate in task 1 above, or you missed the practical session, you can work on this task instead.

Supplied is a set of plaintext/cyphertext pairs. Provide an encryption function $E(X, i)$ that works for all of these pairs and use it to reconstruct the missing plaintext. $X$ is the index of the letter to encrypt in the alphabet (starting from 0), $i$ is the index of the letter in the string (starting from 0). Non-alphabet letters are left unchanged, but do increment $i$.

Do you best to crack at least one cypher. Use the tools provided at the bottom of this practical to help you and test your answers.

The messages this tool uses are generated by the Metaphorpsum API.

Plaintext	Cyphertext

Guidance

Let's say we wanted to work out an encryption function $E(X, i)$ for the following pairs:

Plaintext	Cyphertext
abba	bigv
book	kvth
anon	bmti

What we need to find is a function that takes as input the $X$ and $i$ values for a letter and returns the encrypted form. If we convert the letters to the corresponding numerical value, we can produce tables to help us see this correspondence more clearly. In each of the following, the top line is the numerical value of the plaintext letter, the bottom line is the numerical value of the cyphertext letter.

i	0	1	2	3
abba	0	1	1	0
bigv	1	8	6	21

i	0	1	2	3
book	1	14	14	10
kvth	10	21	19	7

i	0	1	2	3
anon	0	13	14	13
bmti	1	12	19	8

We know a few things

All of these words are encrypted using the same function. So every time the same letter appears in the same place, we will get the same output.
The function takes $i$ as an input. If the same letter appears in different places in the word, any difference in the value it takes is due to the influence of $i$.
If a different letter appears at the same place in the word, any difference in value is due to the influence of $X$.

We might perhaps assume that the solution is not going to be too obscure because this is an exercise question.

Look at "book", we have two consecutive "o"s, which is the 14th letter, yet the cyphertext takes values 21 and 19. Thus we have $E(14, 1) = 21$ and $E(14, 2) = 19$. We can produce a table of $E(14,i)$. We will do the same for the "n"s in "anon" and the "a"s in "abba".

i	0	1	2	3
E(14,i)		21	19

i	0	1	2	3
E(13,i)		12		8

i	0	1	2	3
E(0,i)	1			21

In each table, the only difference between the values is due to $i$. We cannot compare absolute values between tables, but we can compare differences between tables. Do you notice any patterns?

Next, lets consider the first letters. Here $i$ is kept consistent within the table. Can you spot any patterns? Remember we are working modulo 26, so you need to consider how values will 'wrap around'. Are there any relatively simple functions (multiplication, addition, subtraction) that would work account for all of these cases? If you have a hypothesis for the influence of $i$ from above, you may be able to use that to allow you to compare between tables.

X	E(X, 0)
0	1
1	10

X	E(X, 1)
1	8
14	21
13	12

You should be able to check any answers you think you have found using the tool below.

Cypher builder tool

With this tool, (capital) X is the index of the letter in the alphabet and i is the index of the letter in the input string.

Plaintext	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
$ X $	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

0 errors

Error: Cannot read properties of undefined (reading 'evaluate')
Error: Cannot read properties of undefined (reading 'evaluate')