Skip to 0 minutes and 3 seconds Computationally secure encryption schemes, such as the RSA algorithm and the Diffie Hellman key exchange, relied on the principle that computers can’t determine the prime factors of large numbers in sufficient time to break the encryption. But as technology improves and computers become more powerful, larger prime numbers are needed to secure our encryption schemes. One encryption scheme that is unbreakable, regardless of the computing power of the eavesdroppers, is the Vernam cipher. The Vernam cipher substitutes each letter in a message with a five digit binary number using Baudot code. For example, the word hello becomes this in binary. Next, a random key stream of ones and zeros is generated that is longer than or equal to the length of the message.
Skip to 0 minutes and 43 seconds The key stream and the Baudot code are then combined using an operation called an XOR. An XOR operation compares the values at each position and returns a zero if they are the same and a one if they are different. So in this example, the key stream and the Baudot code are XORed to create this cipher text. To decrypt the message, the cipher text is XORed with the key stream again. If the key stream used in a Vernam cipher is completely random, then the cipher text it creates also looks completely random. This means that the Vernam cipher is secure as long as the key stream is kept secret and only used once.
Skip to 1 minute and 16 seconds With a powerful enough computer, a hacker could try to generate every possible key stream in an attempt to decipher an intercepted message, but even if they guess a key stream that generates a plain text that looks plausible, they cannot be sure that they’ve found the correct key stream. For example, pairing this cipher text with this key stream generates this plaintext. But the key stream could equally be this or this or this. So from the hacker’s point of view, several key streams would be equally likely to be correct. Can you encrypt your own message using a Vernam cipher?
Skip to 1 minute and 51 seconds Share your encrypted messages and key streams in the comments, and be sure to try decrypting and responding to other people’s messages as well.
In this step you will learn about the strongest encryption scheme, the one-time pad (or OTP, as implemented by the Vernam cipher), and its limitations.
Last week we looked at a variety of encryption schemes that are computationally secure, which means that their security comes from the limitations in modern technology. Encryption schemes like RSA and the Diffie–Hellman key exchange rely on the principle that computers cannot determine the prime factors of very large numbers in a sufficiently short time to break the encryption scheme. This means that, as technology improves and the speed of computers increases, the larger the numbers used in an encryption schemes will need to be.
However, there does exist an encryption scheme that is unbreakable regardless of the computing power of any eavesdroppers. This encryption scheme is called the Vernam cipher, and is an implementation of the one-time pad.
The Vernam cipher
The Vernam cipher is a form of stream cipher that mixes each letter in a message with a letter from a completely randomly chosen string called the key stream.
To do this, the letters of the message are translated into numbers. When the scheme was first proposed by Gilbert Vernam in the early 19th century, the message was translated into Baudot code, and so each letter was represented by a five-digit binary number.
Next, the key stream is generated. To do this, a random string that is longer than or equal in length to the message is created.
Each binary digit can then be combined with a binary digit from the key stream using a logical XOR operation. To carry out this operation, the values of the two bits are compared; if they are the same (i.e. both 0 or 1) then XOR returns 0, and if they are different, XOR returns 1.
You can find out more about XOR and other logic gates in our “How computers work” course.
Let’s take a look at how to encrypt the word ‘hello’ using the Vernam cipher.
First, ‘hello’ is translated into Baudot code:
Then a random key stream is generated (we created our by rolling a die). The XOR operation is applied to each corresponding pair of digits.
To decrypt the message, the ciphertext is XORed with the key stream again.
How secure is the Vernam cipher?
If the key stream used in a Vernam cipher is completely random, and is as long as the plaintext, then the ciphertext is indistinguishable from a text that is completely random. This means that the Vernam cipher is secure as long as the key stream is kept secret and is only used once.
If an attacker had a powerful enough computer, they might try to generate all of the possible key streams used to encrypt the message. However, because more than one randomly generated key stream will produce a five-letter word, they won’t know which is the correct key stream and which is the correct plaintext.
For example, given the ciphertext
10100, 11011, 10110, 11111, 00101
You might guess that the key stream is
00110, 11010, 01010, 00111, 01001
and that the secret word is “lemon”.
But the key stream is equally likely to be
01000, 11010, 00100, 00111, 01001
which would make the secret word “melon. “
In the next step we will discuss in more detail how the security of encryption schemes is measured.
- Why does the key stream have to be completely random for the encryption scheme to be secure?
- What are the disadvantages of the Vernam cipher, and why do you think it is not used more frequently?
- Can you encrypt your own message using the Vernam cipher?
- Try decrypting and responding to other people’s messages too
Share your encrypted messages and key streams in the comments.