One Time Pad
This week, we will look at the one time pad. In short, this is an encryption technique that cannot be broken. We saw in the tutorial about hard problems, that we often have to prove security relative to a hard problem we assume is not feasible to break; using a one time pad means we do not need to rely on such assumptions.
What is a one time pad?
A one time pad is a shared random secret piece of information. When this one time pad is combined with the plaintext (message), the plaintext will become impossible to decrypt as it too will become completely random.
Example:
It is much easier to see exactly what a one time pad is with an example.
Let us encrypt the plaintext ‘HELLO’ with the one time pad ‘XMCKL’. In this case we are going to combine the one time pad with the plain text as follows. We are going to shift the letter in the plaintext by the number of letters along the alphabet that corresponds to the letter in the one time pad. Let’s see how we encrypt the first letter ‘H’:
‘X’ is the first letter of the one time pad, ‘X’ corresponds to the 23rd letter in the alphabet so we shift ‘H’ 23 letters along to get ‘E’. Note, we have looped round the alphabet again once we get to the end.
Following the same technique for the rest of the plaintext we end up with the ciphertext as follows:
HELLO = EQNVZ
Is this secure?
Assuming the one time pad is completely random the resulting ciphertext will also be completely random and thus there is no way to decrypt it unless you have the one time pad, which should be kept secret.
Why the name?
The name one time pad comes from history. The secret information would be written on the top sheet of a pad of paper, which could then be torn off and destroyed once used.
Question:
What do you think the advantages and disadvantages of the one time pad are?
Hint: for the disadvantages, think about how efficient this process is.
The solution is at the very end of this article.
This article was written by David Butler, one of the course creators and teachers at Oxbridge Inspire. David is studying for a PhD at the Alan Turing Institute in London.
Oxbridge Inspire delivers innovative STEM education and provides guidance and inspiration to young people wishing to pursue STEM subjects at University and beyond. To find out more about Oxbridge Inspire and the courses and activities we offer, visit our website.
Answer:
Advantages: The main advantage of the one time pad is that it provides perfect secrecy. If the encryption is carried out properly, using a completely random one time pad, then no adversary will be able to decrypt it —assuming of course they do not know the one time pad! This provides what is known as ‘perfect secrecy’ or ‘information theoretic security’.
Disadvantages: The hint says to think about how efficient this process is. Let us think about how long the one time pad must be. We have to have a new piece of randomness for every letter of the plaintext, therefore the one time pad must be the same length as the plaintext (in some cases it must be longer). Imagine if our message was a page long, that means we would have to have a one time pad that is also a page long. Remember also, that these one time pads must be kept secret; the longer they are, the more paper one needs to write them down on and the harder they are to keep private.
