In cryptography we encrypt messages that contains letters, but substitution ciphers are based on arithmetic operations on integers. Therefore, we have to convert the letters into integers before we apply the cryptosystem on the message. Because we use the English alphabet with 26 letters we have the following conversion between letters and integers:
| a | b | c | d | e | f | g | h | i | j | k | l | m |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| n | o | p | q | r | s | t | u | v | w | x | y | z |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
You already use modulo computation when you look at the clock and e.g. needs to figure out what time it's 3 hours after 11 o'clock, which is 2 o'clock. In math we write that as:
\( (11 + 3) \: mod \: 12 = 2 \)
where 12 is the modulus because we want the time as an integer between 0 and 11 (12 o'clock is in this case denoted by 0). In words we say 11 plus 3 modulo 12 is equal 2. The result of a modulo computation is an integer between 0 and the modulus minus 1. E.g. with the modulus 3 we have that:
If we e.g. look at \( 27 \: mod \: 5 \) then modulo computes the number of times 5 divides 27 and then returns the remainder of the result which is 2 in this case, i.e. \( 27 \: mod \: 5 = 2 \). But how did we get this result?
First we compute the number of times it's possible to multiply 5 with the number \( x \) such that we get an integer as close as possible to 27 without exceeding it, i.e. we have to find the maximun value of \( x \) such that \( 5 \cdot x \leq 27 \). In this case we have that \( x = 5 \) because \( 5 \cdot 5 = 25 \leq 27 \). Then by subtracting 27 with 25 we get the answer \( 27 - 25 = 2\).
If the integer is negative e.g. \( -27 \: mod \: 5 \) we have to do it slightly different and the answer is \( -27 \: mod \: 5 = 3 \). In this case the integer \( x \) is negative and should be the closest integer that exceed -27, i.e. we have to find the minimum value of \( -x \) such that \( 5 \cdot -x \geq -27 \). Now we have that \( -x = -6 \) because \( 5 \cdot -6 = -30 \geq -27 \). Then by subtracting -27 with -30 we get the answer \( -27 - (-30) = -27 + 30 = 3\).
It's important that \( x \) or \( -x \) is an integer such as \( -14, 3, 17 \) etc. and NOT a fraction or float such as \( \frac{1}{4}, \frac{-3}{7}, 2.5, 5.1 \) etc.
If two integers \( a \) and \( b \) modulo the same modulus \( c \) returns the same remainder \( r \), then we say that \( a \) and \( b \) are congruent modulo \( c \). I.e. if \( a \: mod \: c = r \) and \( b \: mod \: c = r \) then \( a \equiv b \: (mod \: c) \). Also, notice that if the modulus \( c \) is greater than the integer \( a \), i.e. \( c > a \), the result will always be equal \( a \: mod \: c = a \).
Before we describe what the greatest common divisor of two integers are, we first define what we mean by a divisor. In this context is a divisor of an integer \( x \) some integer that divides \( x \) evenly, i.e. the result must not be a float. E.g. if you try to divide \( x=12 \) with 5 it returns the float \( \frac{12}{5} = 2.4 \) and 5 is therefore not a divisor of \( x=12 \). For \( x=12 \) we have the divisors 1, 2, 3, 4, 6 and 12 because \( \frac{12}{1} = 12 \), \( \frac{12}{2} = 6 \), \( \frac{12}{3} = 4 \), \( \frac{12}{4} = 3 \), \( \frac{12}{6} = 2 \) and \( \frac{12}{12} = 1 \).
Likewise the divisors of 16 is 1, 2, 4, 8 and 16 because \( \frac{16}{1} = 16 \), \( \frac{16}{2} = 8 \), \( \frac{16}{4} = 4 \), \( \frac{16}{8} = 2 \) and \( \frac{16}{16}=1 \).
The greatest common divisor of 12 and 16 is therefore 4, because it is the largest integer of the common divisors. In math we write that as \( \gcd(12, 16) = 4 \).
Two integers with greatest common divisor 1 are called relatively prime numbers or co-primes. E.g. 15 and 28 are relatively prime numbers because \( \gcd(15, 28) = 1 \) (notice that 28 is not a prime number).
If one of the two integers is a prime number the greatest common divisor will always be 1, i.e. \( \gcd(a, p) = 1 \) where \( a \) is an integer (either a prime number or a composite number) and \( p \) is a prime number.
One method to compute the greatest common divisor of two integers is by using the Euclidean algorithm developed by the famous Greek mathematician Euclid. See "The extended Euclidean algorithm" for more information about how to compute the greatest common divisor of two integer.
The extended Euclidean algorithm is an extended version of the Euclidean algorithm, which only returns the greatest common divisor of two integers. Given two integers \( a \) and \( b \) the extended Euclidean algorithm returns the integers \( a \), \( b \), \( \lambda \) and \( \mu \) such that:
\( a \cdot \lambda + b \cdot \mu = \gcd(a, b) \)
where \( \lambda \) and \( \mu \) are called the Bézout coefficients for \( a \) and \( b \). Only if \( a \) and \( b \) are relatively prime numbers, i.e. \( \gcd(a, b) = 1 \), then:
\( a \cdot \lambda + b \cdot \mu = 1 \)
and \( \lambda \; mod \; b \) is the inverse of \( a \), denoted \( a^{-1} = \lambda \; mod \; b \), and \( \mu \: mod \: a \) is the inverse of \( b \), denoted \( b^{-1} = \mu \: mod \: a \) (see "Modulo computation" for more information about the \( mod \) operator). One useful property of an integer and its inverse is that \( a \cdot a^{-1} \; mod \; b = 1 \) and \( b \cdot b^{-1} \; mod \; a = 1 \).
You can easily compute \( \gcd(a, b) \), \( \lambda \) and \( \mu \) for e.g. \( a=5 \) and \( b=39 \) with a simple table. So, let us first create a table with 3 columns (we do not yet know how many rows there will be in the table). Let us denote the entry in the first row and first column for [1,1], the entry in the first row and second column for [1,2], the entry in the second row and first column for [2,1] and so on.
Next we write \( b=39 \) in entry [1,1] and \( a=5 \) in entry [2,1]. Then we try to find the biggest integer \( q_{1} \), such that \( q_{1} \cdot a \leq b \). We have that \( q_{1}=7 \), which we write in entry [2,2], because \( 7 \cdot 5 = 35 \leq 39 \) and a remainder of \( r_{1}=4 \), which we write in entry [3,1].
Again we try to find the biggest integer \( q_{2} \), such that \( q_{2} \cdot r_{1} \leq a \). We have that \( q_{2}=1 \), which we write in entry [3,2], because \( 1 \cdot 4 = 4 \leq 5 \) and a remainder of \( r_{2}=1 \) that we write in entry [4,1]. Notice that we just computed the same as before, just with integers in a lower row.
The next computation returns a remainder of \( r_{3} = 0 \) because \( q_{3} \cdot r_{2} = 4 \cdot 1 = 4 \leq 4 = r_{1} \). We have now computed \( \gcd(5, 39)=r_{2}=1 \) since \( r_{3} = 0 \). And because 5 and 39 are relatively prime numbers, we know that \( \lambda \) and \( \mu \) exists and we can then start using the last column.
First we write \( x_{1}=0 \) in entry [4,3] and \( x_{2}=1 \) in entry [3,3]. Then we write \( x_{3}=q_{2} \cdot x_{2} + x_{1} = 1 \cdot 1 + 0 = 1 \) in entry [2,3]. For entry [1,3] we compute the same as before, just with integers from the row above, i.e. \( x_{4}=q_{1} \cdot x_{3} + x_{2} = 7 \cdot 1 + 1 = 8 \).
Finally we have that \( a \cdot x_{4} \pm b \cdot x_{3} = r_{2} \), where we need to decide whether it should be plus or minus between the two terms. Because \( a \cdot x_{4} = 5 \cdot 8 = 40 \), \( b \cdot x_{3} = 39 \cdot 1\) and \( 40 \geq 39 \) we have that \( 5 \cdot 8 - 39 \cdot 1 = 1 \) (which is the same as \( 5 \cdot 8 + 39 \cdot (-1) = 1 \)) and the Bézout coefficients are \( \lambda=8 \) and \( \mu=-1 \). Notice that \( a^{-1} = \lambda \; mod \; b = 8 \; mod \; 39 = 8\) and \( b^{-1} = \mu \; mod \; a = -1 \: mod \: 5 = 4\) where \( a \cdot a^{-1} \; mod \; b = 5 \cdot 8 \; mod \; 39 = 1 \) and \( b \cdot b^{-1} \; mod \; a = 39 \cdot 4 \; mod \; 5 = 1 \).
The table for computing \( 5 \cdot \lambda + 39 \cdot \mu = \gcd(5, 39) \) is:
| \( b=39 \) | \( x_{4}=8 \) | |
| \( a=5 \) | \( q_{1}=7 \) | \( x_{3}=1 \) |
| \( r_{1}=4 \) | \( q_{2}=1 \) | \( x_{2}=1 \) |
| \( r_{2}=1 \) | \( q_{3}=4 \) | \( x_{1}=0 \) |
| \( r_{3}=0 \) |
The Caesar cipher, also known as the shift cipher, is named after the Roman general Julius Caesar who used it to communicate with his officers during wars about the year of 50 BC. It's a simple substitution cipher where each letter in the alphabet is substituted with another letter by shifting it \( s \) times. It's said that Julius Caesar used the shift value \( s = 3 \).
Assume Alice wants to send a message \( m \) (also called the plaintext) to her friend Bob using the Caesar cipher. First they in advance agree on a shift value \( s \) and then Alice encrypts the message by shifting each letter in the message \( s \) times to the right which produces the ciphertext \( c \). She then sends the ciphertext to Bob who decrypts it by shifting each letters in the ciphertext \( s \) times to the left.
In the case with the shift value \( s = 3 \) the letter "a" in the plaintext becomes "D" in the ciphertext, "b" becomes "E", "c" becomes "F" etc. You may wonder what happens with the last letters in the alphabet because there is no letter appearing three letters after "x", "y" and "z". The answer is simple: we just use the same approach as modulo computation, i.e. "x" becomes "A", "y" becomes "B" and "z" becomes "C". The encryption table for \( s = 3 \) is illustrated in the following table where the plaintext letters are in lowercase and the ciphertext letters are in uppercase:
| Encryption table for \( s = 3 \) | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a | b | c | d | e | f | g | h | i | j | k | l | m |
| D | E | F | G | H | I | J | K | L | M | N | O | P |
| n | o | p | q | r | s | t | u | v | w | x | y | z |
| Q | R | S | T | U | V | W | X | Y | Z | A | B | C |
If we convert the letters into integers such that "a" is converted into "0", "b" is converted into "1", "c" is converted into "2" etc. then the encryption of the letter \( m_{i} \) in the message \( m \) is defined as \( c_{i} = (m_{i} + s) \: mod \: 26 \) and decryption is defined as \( m_{i}' = (c_{i} - s) \: mod \: 26 \). The modulus is 26 because there is 26 letters in the English alphabet. It's easy to verify that \( m_{i}' = m_{i} \) because:
\( \eqalign{ m_{i}' &= (c_{i} - s) \: mod \: 26 &&(c_{i} = (m_{i} + s)) \\ &= ((m_{i} + s)- s) \: mod \: 26 \\ &= m_{i} \: mod \: 26 } \)
| Key exchange | |
| Alice and Bob agree on the shift value \( s \). | |
| Encryption | |
| Alice: Uses the shift value to compute the ciphertexts \( c_{i} = (m_{i} + s) \: mod \: 26 \) for \( i = 1, 2, \dots n \) where \( n = |m| \) (the length of the plaintext \( m \)). | |
| Alice sends the ciphertext \( c = (c_{1}, c_{2}, \dots, c_{n}) \) to Bob. | |
| Decryption | |
| Bob: Uses the shift value to decrypt the ciphertexts \( m_{i} = (c_{i} - s) \: mod \: 26 \) for \( i = 1, 2, \dots n \) where \( n = |c| \) (the length of the ciphertext \( c \)). | |
Try a demo of the cipher here.
Alice wants to send the message \( m = \mbox{"meet me at the secret location"} \) to Bob. First they agree on the shift value \( s = 3 \) and then Alice converts the letters in \( m \) into the integers \( m_{1} = 12, m_{2} = 4, \dots, m_{25} = 13 \), which she encrypts:
\( \eqalign{ c_{1} &= (m_{1} + s) \: mod \: 26 = (12 + 3) \: mod \: 26 = 15 \\ c_{2} &= (m_{2} + s) \: mod \: 26 = (4 + 3) \: mod \: 26 = 7 \\ &\vdots \\ c_{25} &= (m_{25} + s) \: mod \: 26 = (13 + 3) \: mod \: 26 = 16 } \)
She then converts the ciphertexts \( c_{1} = 15, c_{2} = 7, \dots, c_{25} = 16 \) into letters and sends the ciphertext \( c = \mbox{"PHHW PH DW WKH VHFUHW ORFDWLRQ"} \) to Bob.
Bob decrypts the received ciphertext almost just like Alice encrypted the message. First he converts the letters in the ciphertext \( c \) into the integers \( c_{1}, c_{2}, \dots, c_{25} \) and then he decrypts them:
\( \eqalign{ m_{1} &= (c_{1} - s) \: mod \: 26 = (15 - 3) \: mod \: 26 = 12 \\ m_{2} &= (c_{2} - s) \: mod \: 26 = (7 - 3) \: mod \: 26 = 4 \\ &\vdots \\ m_{25} &= (c_{25} - s) \: mod \: 26 = (16 - 3) \: mod \: 26 = 13 } \)
Finally he converts the plaintexts \( m_{1}, m_{2}, \dots, m_{25} \) back into letters which result in the message \( m = \mbox{"meet me at the secret location"} \).
The affine cipher is a combination of the Caesar cipher and a multiplication cipher: First Alice and Bob agrees on the two integers \( a \) and \( b \) between 0 and 25 such that \( \gcd(a, 26) = 1 \) because during decryption her friend Bob needs the inverse \( a^{-1} \) of \( a \) which only exists when \( \gcd(a, 26) = 1 \).
Alice then encrypts the message \( m \) by first converting each letter into integers where the letter "a" is converted into the integer "0", "b" is converted into "1", "c" is converted into "2" etc. Then for each integer \( m_{i} \) she computes \( c_{i} = (a \cdot m_{i} + b) \: mod \: 26 \) (notice that if \( a=1 \) the affine cipher corresponds to the Caesar cipher with the sift value \( b \)), converts each \( c_{i} \) back into letters and sends the ciphertext \( c \) to Bob. The modulus is 26 because there is 26 letters in the English alphabet.
Bob decrypts the ciphertext in a similar way as Alice encrypted the message. First he computes the inverse \( a^{-1} \) of \( a \) with the extended Euclidean algorithm, which gives him the equation \( a \cdot \lambda + 26 \cdot \mu = \gcd(a, 26) \) where \( a^{-1} = \lambda \; mod \; 26 \) and \( a \cdot a^{-1} \: mod \: 26 = 1 \) (remember that \( a^{-1} \) only exists because \( \gcd(a, 26) = 1 \)). Then he converts each letter in \( c \) into integers \( c_{i} \), computes \( m_{i}' = a^{-1} \cdot (c_{i} - b) \: mod \: 26 \) and finally he converts the integers \( m_{i}' \) back into letters, which result in the message \( m \). We see that \( m_{i}' = m_{i} \) because:
\( \eqalign{ m_{i}' &= a^{-1} \cdot (c_{i} - b) \: mod \: 26 &&(c_{i} = (a \cdot m_{i} + b)) \\ &= a^{-1} \cdot ((a \cdot m_{i} + b) - b) \: mod \: 26 \\ &=a^{-1} \cdot (a \cdot m_{i}) \: mod \: 26 &&(a \cdot a^{-1} \: mod \: 26 = 1) \\ &= m_{i} \: mod \: 26 } \)
| Key exchange | |
| Alice and Bob agree on the values \( a \) and \( b \) such that \( \gcd(a, 26) = 1 \). | |
| Encryption | |
| Alice: Uses the values \( a \) and \( b \) to compute the ciphertexts \( c_{i} = (a \cdot m_{i} + b) \: mod \: 26 \) for \( i = 1, 2, \dots n \) where \( n = |m| \) (the length of the plaintext \( m \)). | |
| Alice sends the ciphertext \( c = (c_{1}, c_{2}, \dots, c_{n}) \) to Bob. | |
| Decryption | |
| Bob: Computes the inverse \( a^{-1} \) of \( a \) with the extended Euclidean algorithm. Uses \( b \) and \( a^{-1} \) to decrypt the ciphertexts \( m_{i} = a^{-1} \cdot (c_{i} - b) \: mod \: 26 \) for \( i = 1, 2, \dots n \) where \( n = |c| \) (the length of the ciphertext \( c \)). | |
Try a demo of the cipher here.
Alice wants to send the message \( m = \mbox{"it begins at midnight"} \) to Bob. First they agree on the integers \( a = 15 \) and \( b = 9 \) where \( \gcd(a, 26) = \gcd(15, 26) = 1 \). Then Alice converts the letters in \( m \) into the integers \( m_{1} = 8, m_{2} = 19, \dots, m_{18} = 19 \), which she encrypts:
\( \eqalign{ c_{1} &= (a \cdot m_{1} + b) \: mod \: 26 = (15 \cdot 8 + 9) \: mod \: 26 = 25 \\ c_{2} &= (a \cdot m_{2} + b) \: mod \: 26 = (15 \cdot 18 + 9) \: mod \: 26 = 19 \\ &\vdots \\ c_{18} &= (a \cdot m_{18} + b) \: mod \: 26 = (15 \cdot 19 + 9) \: mod \: 26 = 8 } \)
She then converts \( c_{1} = 15, c_{2} = 7, \dots, c_{18} = 16\) back into letters and sends the ciphertext \( c = \mbox{"ZI YRVZWT JI HZCWZVKI"} \) to Bob.
When Bob receives the ciphertext he first computes the inverse \( a^{-1} \) of \( a = 15 \) with the extended Euclidean algorithm. The extended Euclidean algorithm gives him the equation \( \gcd(a, 26) = a \cdot \lambda + 26 \cdot \mu = 15 \cdot 7 + 26 \cdot (-4) = 1 \) where \( a^{-1} = \lambda \; mod \; 26 = 7 \; mod \; 26 = 7 \). Then he converts the letters in \( c \) into the integers \( c_{1} , c_{2}, \dots, c_{18} \) and decrypts them:
\( \eqalign{ m_{1} &= a^{-1} \cdot (c_{1} - b) \: mod \: 26 = 7 \cdot (15 - 9) \: mod \: 26 = 8 \\ m_{2} &= a^{-1} \cdot (c_{2} - b) \: mod \: 26 = 7 \cdot (7 - 9) \: mod \: 26 = 18 \\ &\vdots \\ m_{18} &= a^{-1} \cdot (c_{18} - b) \: mod \: 26 = 7 \cdot (16 - 9) \: mod \: 26 = 19 } \)
Finally he converts \( m_{1} , m_{2}, \dots, m_{18} \) back into letters which result in the message \( m = \mbox{"it begins at midnight"} \).
The Caesar and affine cipher are both monoalphabetic ciphers because once a key is chosen each letter is mapped uniquely to another letter. As cryptanalytic methods became more sophisticated in the 16th century more sophisticated ciphers were invented and one of them was the Vigenére cipher, which was invented by Blaise de Vigenére in the 16th century. The Vigenére cipher is a polyalphabetic cipher because each letter is encrypted and decrypted with different keys, i.e. the same letter can be mapped to multiple different letters.
In the Vigenére cipher Alice and Bob first agrees on a keyword \( K \) of length \( t \). If the keyword is shorter than the message \( m \) that Alice wants to send to Bob, i.e. \( t < n \) where \( n = |m| \) (the length of the message \( m \)), then they repeat the keyword until \( t=n \). Alice then use the letters in the keyword to determine how much each letter in the message should be shifted: She first converts the letters in the keyword \( K \) and the message \( m \) into the integers \( k_{1}, k_{2}, \dots, k_{n} \) and \( m_{1}, m_{2}, \dots, m_{n} \) respectively (remember that a short keyword is repeated until \( t = n \)). She then encrypts each letter by computing \( c_{i} = (m_{i} + k_{i}) \: mod \: 26 \) (just like encryption in the Caesar cipher) where the modulus is 26 because the English alphabet has 26 letters. Finally she converts the integers \( c_{1}, c_{2}, \dots, c_{n} \) into letters and sends the ciphertext \( c \) to Bob.
Bob decrypts the received ciphertext \( c \) in a similar way: if the keyword (with length \( t \)) is shorter than the ciphertext he repeats it until \( t = n \) where \( n = |c| \) (the length of the ciphertext \( c \)). He then converts the keyword \( K \) and the ciphertext \( c \) into the integers \( k_{1}, k_{2}, \dots, k_{n} \) and \( c_{1}, c_{2}, \dots, c_{n} \) respectively and computes \( m_{i}' = (c_{i} - k_{i}) \: mod \: 26 \). Finally he converts the integers \( m_{1}', m_{2}', \dots, m_{n}' \) into letters, which result in the message \( m \). It's easy to verify that \( m_{i}' = m_{i} \) because:
\( \eqalign{ m_{i}' &= (c_{i} - k_{i}) \: mod \: 26 &&(c_{i} = (m_{i} + k_{i})) \\ &= ((m_{i} + k_{i})- k_{i}) \: mod \: 26 \\ &= m_{i} \: mod \: 26 } \)
| Key exchange | |
| Alice and Bob agree on the keyword \( K = (k_{1}, k_{2}, \dots, k_{t}) \). If \( t < n \) where \( n = |m| \) (the length of the message \( m \)) then they repeat the keyword until \( t = n \). | |
| Encryption | |
| Alice: Uses the key \( k_{i} \) to compute the ciphertext \( c_{i} = (m_{i} + k_{i}) \: mod \: 26 \) for \( i = 1, 2, \dots, n \). | |
| Alice sends the ciphertext \( c = (c_{1}, c_{2}, \dots, c_{n}) \) to Bob. | |
| Decryption | |
| Bob: Uses the key \( k_{i} \) to decrypt the ciphertext \( m_{i} = (c_{i} - k_{i}) \: mod \: 26 \) for \( i = 1, 2, \dots, n \). | |
Try a demo of the cipher here.
Alice wants to send the message \( m = \mbox{"it is hidden at the bridge"} \) to Bob where \( n = |m| = 21\). First they agree on the keyword \( K = \mbox{"THEORY"} \) of length \( t = 6 \). Because \( t < n \) Alice repeats it until \( t = n \), i.e. the keyword become \( K = \mbox{"THEORYTHEORYTHEORYTHE"} \). She then converts the letters in \( K \) and \( m \) into the integers \( k_{1} = 19, k_{2} = 7, \dots, k_{21} = 4 \) and \( m_{1} = 8, m_{2} = 19, \dots, m_{21} = 4 \) respectively and computes:
\( \eqalign{ c_{1} &= (m_{1} + k_{1}) \: mod \: 26 = (8 + 19) \: mod \: 26 = 1 \\ c_{2} &= (m_{2} + k_{2}) \: mod \: 26 = (19 + 7) \: mod \: 26 = 0 \\ &\vdots \\ c_{21} &= (m_{21} + k_{18}) \: mod \: 26 = (4 + 4) \: mod \: 26 = 8 } \)
She then converts \( c_{1} = 1, c_{2} = 0, \dots, c_{21} = 8 \) back into letters and sends the ciphertext \( c = \mbox{"BA MG YGWKIB RR MOI PIGWNI"} \) to Bob.
When Bob receives the ciphertext he first repeats the keyword such that \( K = \mbox{"THEORYTHEORYTHEORYTHE"} \) because \( t < n \) where \( n = 21\) is the length of the ciphertext \( c \). Then he converts the letters in \( K \) and \( c \) into the integers \( k_{1} , k_{2}, \dots, k_{21} \) and \( c_{1} , c_{2}, \dots, c_{21} \) respectively and computes:
\( \eqalign{ m_{1} &= (c_{1} - k_{1}) \: mod \: 26 = (1 - 19) \: mod \: 26 = 8 \\ m_{2} &= (c_{2} - k_{2}) \: mod \: 26 = (0 - 7) \: mod \: 26 = 19 \\ &\vdots \\ m_{21} &= (c_{21} - k_{18}) \: mod \: 26 = (8 - 4) \: mod \: 26 = 4 } \)
Finally he converts \( m_{1} , m_{2}, \dots, m_{21} \) back into letters, which result in the message \( m = \mbox{"it is hidden at the bridge"} \).
The one-time pad described by Gilbert Vernam in 1917 is a perfectly secure cryptosystem when the used key is completely random and only used to encrypt a single message. Perfectly secure means that if Alice and Bob's common adversary Eve with infinity computing power intercept a ciphertext she learns nothing whatsoever about the message or the key.
Encryption and decryption in the one-time pad are almost identical to the one used in the Vigenére cipher which makes it very attractive because they are simple operations, but unfortunately the used key must have the same length as the message. If we could encrypt multiple messages with the same key this would not be a problem, but the key must only be used once to keep the one-time pad perfectly secure.
In the one-time pad Alice and Bob first agrees on a random key \( K \) of length \( n \) where \( n = |m| \) (the length of the message \( m \)). Alice then encrypts the message \( m \) using the key \( K \) just like she did in the Vigenére cipher: She first converts the letters in the key \( K \) and the message \( m \) into the integers \( k_{1}, k_{2}, \dots, k_{n} \) and \( m_{1}, m_{2}, \dots, m_{n} \) respectively. Then she encrypts each letter by computing \( c_{i} = (m_{i} + k_{i}) \: mod \: 26 \) where the modulus is 26 because the English alphabet has 26 letters. Finally she converts the integers \( c_{1}, c_{2}, \dots, c_{n} \) into letters and sends the ciphertext \( c \) to Bob.
Bob decrypts the received ciphertext \( c \) in a similar way: he converts the key \( K \) and the ciphertext \( c \) into the integers \( k_{1}, k_{2}, \dots, k_{n} \) and \( c_{1}, c_{2}, \dots, c_{n} \) respectively and computes \( m_{i}' = (c_{i} - k_{i}) \: mod \: 26 \). Finally he converts the integers \( m_{1}', m_{2}', \dots, m_{n}' \) into letters, which result in the message \( m \). We have that \( m_{i}' = m_{i} \) because:
\( \eqalign{ m_{i}' &= (c_{i} - k_{i}) \: mod \: 26 &&(c_{i} = (m_{i} + k_{i})) \\ &= ((m_{i} + k_{i})- k_{i}) \: mod \: 26 \\ &= m_{i} \: mod \: 26 } \)
| Key exchange | |
| Alice and Bob agree on the key \( K = (k_{1}, k_{2}, \dots, k_{n}) \) where \( n = |m| \) (the length of the message \( m \)). | |
| Encryption | |
| Alice: Uses the key \( k_{i} \) to compute the ciphertext \( c_{i} = (m_{i} + k_{i}) \: mod \: 26 \) for \( i = 1, 2, \dots, n \). | |
| Alice sends the ciphertext \( c = (c_{1}, c_{2}, \dots, c_{n}) \) to Bob. | |
| Decryption | |
| Bob: Uses the key \( k_{i} \) to decrypt the ciphertext \( m_{i} = (c_{i} - k_{i}) \: mod \: 26 \) for \( i = 1, 2, \dots, n \). | |
Try a demo of the cipher here.
Alice wants to send the message \( m = \mbox{"meet me tomorrow morning"} \) to Bob where \( n = |m| = 21 \). First they agree on a random key with the same length as the message: \( K = \mbox{"WVJLQCOEUTYJNNUGDROVS"} \) . She then converts the letters in \( K \) and \( m \) into the integers \( k_{1} = 22, k_{2} = 21, \dots, k_{21} = 18 \) and \( m_{1} = 12, m_{2} = 4, \dots, m_{21} = 6 \) respectively and computes:
\( \eqalign{ c_{1} &= (m_{1} + k_{1}) \: mod \: 26 = (12 + 22) \: mod \: 26 = 8 \\ c_{2} &= (m_{2} + k_{2}) \: mod \: 26 = (4 + 21) \: mod \: 26 = 25 \\ &\vdots \\ c_{21} &= (m_{21} + k_{18}) \: mod \: 26 = (6 + 18) \: mod \: 26 = 24 } \)
She then converts \( c_{1} = 8, c_{2} = 25, \dots, c_{21} = 24 \) back into letters and sends the ciphertext \( c = \mbox{"IZNE CG HSGHPABJ GUUEWIY"} \) to Bob.
When Bob receives the ciphertext he converts the letters in \( K \) and \( c \) into the integers \( k_{1} , k_{2}, \dots, k_{21} \) and \( c_{1} , c_{2}, \dots, c_{21} \) respectively and computes:
\( \eqalign{ m_{1} &= (c_{1} - k_{1}) \: mod \: 26 = (8 - 22) \: mod \: 26 = 12 \\ m_{2} &= (c_{2} - k_{2}) \: mod \: 26 = (25 - 21) \: mod \: 26 = 4 \\ &\vdots \\ m_{21} &= (c_{21} - k_{18}) \: mod \: 26 = (24 - 18) \: mod \: 26 = 6 } \)
Finally he converts \( m_{1} , m_{2}, \dots, m_{21} \) back into letters, which result in the message \( m = \mbox{"meet me tomorrow morning"} \).