In cryptography, we often encrypt messages that contain letters, but substitution ciphers are based on arithmetic operations with integers. Therefore, we must convert the letters into integers before applying the cryptosystem to the message. Since we use the English alphabet, which has 26 letters, we use 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 a clock and, for example, need to figure out what time it will be 3 hours after 11 o'clock, which is 2 o'clock. In mathematics, we write this as:
\( (11 + 3) \: mod \: 12 = 2 \)
Here, 12 is the modulus because we want the time as an integer between 0 and 11 (in this case, 12 o'clock is denoted by 0). In words, we say "11 plus 3 modulo 12 equals 2." The result of a modulo computation is an integer between 0 and the modulus minus 1. For example, with modulus 3, we have:
For example, if we look at \( 27 \: mod \: 5 \), modulo computes how many times 5 divides into 27 and then returns the remainder, which is 2 in this case. That is, \( 27 \: mod \: 5 = 2 \). But how do we get this result?
First, we compute how many times we can multiply 5 by an integer \( x \) so that the result is as close as possible to 27 without exceeding it. In other words, we find the maximum value of \( x \) such that \( 5 \cdot x \leq 27 \). In this case, \( x = 5 \) because \( 5 \cdot 5 = 25 \leq 27 \). Then, by subtracting 25 from 27, we get the answer: \( 27 - 25 = 2 \).
If the integer is negative, for example \( -27 \: mod \: 5 \), we have to do it slightly differently, and the answer is \( -27 \: mod \: 5 = 3 \). In this case, the integer \( x \) is negative and should be the closest integer such that \( 5 \cdot x \) does not exceed -27. That is, we find the minimum value of \( -x \) such that \( 5 \cdot -x \geq -27 \). Here, \( -x = -6 \) because \( 5 \cdot -6 = -30 \geq -27 \). Then, by subtracting -30 from -27, we get the answer: \( -27 - (-30) = -27 + 30 = 3 \).
It is important that \( x \) or \( -x \) is an integer such as \( -14, 3, 17 \), etc., and NOT a fraction or decimal such as \( \frac{1}{4}, \frac{-3}{7}, 2.5, 5.1 \), etc.
If two integers \( a \) and \( b \) modulo the same modulus \( c \) return the same remainder \( r \), then we say that \( a \) and \( b \) are congruent modulo \( c \). That is, 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 \( a \: mod \: c = a \).
Before we describe what the greatest common divisor of two integers is, we first define what we mean by a divisor. In this context, a divisor of an integer \( x \) is any integer that divides \( x \) evenly, meaning the result is not a fraction. For example, if you divide \( x=12 \) by 5, you get the fraction \( \frac{12}{5} = 2.4 \), so 5 is not a divisor of \( x=12 \). For \( x=12 \), the divisors are 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 \).
Similarly, the divisors of 16 are 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 among their common divisors. In mathematics, we write this as \( \gcd(12, 16) = 4 \).
Two integers whose greatest common divisor is 1 are called relatively prime numbers or co-primes. For example, 15 and 28 are relatively prime because \( \gcd(15, 28) = 1 \) (note 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 any integer (either prime or composite) 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 integers.
The extended Euclidean algorithm is an extension 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) \)
Here, \( \lambda \) and \( \mu \) are called the Bézout coefficients for \( a \) and \( b \). Only if \( a \) and \( b \) are relatively prime, i.e., \( \gcd(a, b) = 1 \), then:
\( a \cdot \lambda + b \cdot \mu = 1 \)
In this case, \( \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 example with \( a=5 \) and \( b=39 \) using a simple table. First, let us create a table with three columns (we do not yet know how many rows there will be). Let us denote the entry in the first row and first column as [1,1], the entry in the first row and second column as [1,2], the entry in the second row and first column as [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 largest integer \( q_{1} \) such that \( q_{1} \cdot a \leq b \). We have \( 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 largest integer \( q_{2} \) such that \( q_{2} \cdot r_{1} \leq a \). We have \( q_{2}=1 \), which we write in entry [3,2], because \( 1 \cdot 4 = 4 \leq 5 \), and a remainder of \( r_{2}=1 \), which we write in entry [4,1]. Notice that we are repeating the same process as before, just with the numbers in the next 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 \). Because 5 and 39 are relatively prime, we know that \( \lambda \) and \( \mu \) exist, and we can 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 as before, just with numbers 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 \( 5 \cdot 8 - 39 \cdot 1 = 1 \) (which is the same as \( 5 \cdot 8 + 39 \cdot (-1) = 1 \)), so 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 around the year 50 BC. It is a simple substitution cipher in which each letter in the alphabet is replaced by another letter, shifted \( s \) positions. It is said that Julius Caesar used a shift value of \( s = 3 \).
Suppose Alice wants to send a message \( m \) (also called the plaintext) to her friend Bob using the Caesar cipher. First, they agree in advance on a shift value \( s \). Then, Alice encrypts the message by shifting each letter in the message \( s \) positions to the right, producing the ciphertext \( c \). She then sends the ciphertext to Bob, who decrypts it by shifting each letter in the ciphertext \( s \) positions to the left.
In the case where the shift value is \( s = 3 \), the letter "a" in the plaintext becomes "D" in the ciphertext, "b" becomes "E", "c" becomes "F", and so on. You may wonder what happens with the last letters in the alphabet, since there is no letter three positions after "x", "y", or "z". The answer is simple: we use the same approach as in modulo computation; that is, "x" becomes "A", "y" becomes "B", and "z" becomes "C". The encryption table for \( s = 3 \) is shown 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" becomes "0", "b" becomes "1", "c" becomes "2", and so on, 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 are 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 \( s \) to compute the ciphertexts \( c_{i} = (m_{i} + s) \: mod \: 26 \) for \( i = 1, 2, \dots, n \), where \( n = |m| \) is 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 \( s \) to decrypt the ciphertexts \( m_{i} = (c_{i} - s) \: mod \: 26 \) for \( i = 1, 2, \dots, n \), where \( n = |c| \) is 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 \). Alice then converts the letters in \( m \) into the integers \( m_{1} = 12, m_{2} = 4, \dots, m_{25} = 13 \), which she encrypts as follows:
\( \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 in almost the same way as 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 as follows:
\( \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 plaintext values \( m_{1}, m_{2}, \dots, m_{25} \) back into letters, which results 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 agree on two integers \( a \) and \( b \) between 0 and 25 such that \( \gcd(a, 26) = 1 \), because during decryption, 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 an integer, where the letter "a" becomes 0, "b" becomes 1, "c" becomes 2, and so on. 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 reduces to the Caesar cipher with the shift value \( b \). She then converts each \( c_{i} \) back into a letter and sends the ciphertext \( c \) to Bob. The modulus is 26 because there are 26 letters in the English alphabet.
Bob decrypts the ciphertext in a similar way to how Alice encrypted the message. First, he computes the inverse \( a^{-1} \) of \( a \) using 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 an integer \( c_{i} \), computes \( m_{i}' = a^{-1} \cdot (c_{i} - b) \: mod \: 26 \), and finally converts the integers \( m_{i}' \) back into letters, which results 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| \) is 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 \) using 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| \) is 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 as follows:
\( \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 \) using 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 as follows:
\( \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 results in the message \( m = \mbox{"it begins at midnight"} \).
The Caesar and affine ciphers 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 advanced ciphers were invented. One of these was the Vigenére cipher, 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; that is, the same letter can be mapped to multiple different letters.
In the Vigenére cipher, Alice and Bob first agree 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 uses 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 results 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 a keyword \( K = (k_{1}, k_{2}, \dots, k_{t}) \). If \( t < n \), where \( n = |m| \) (the length of the message \( m \)), 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 the keyword until \( t = n \); that is, the keyword becomes \( 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 so 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 results 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 key used is completely random and only used to encrypt a single message. Perfectly secure means that if Alice and Bob's common adversary, Eve, with infinite computing power, intercepts a ciphertext, she learns nothing whatsoever about the message or the key.
Encryption and decryption in the one-time pad are almost identical to those used in the Vigenére cipher, which makes it very attractive because the operations are simple. Unfortunately, the key must be as long as the message. If it were possible to encrypt multiple messages with the same key, this would not be a problem, but to keep the one-time pad perfectly secure, the key must only be used once.
In the one-time pad, Alice and Bob first agree 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 as she does 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 results 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 a key \( K = (k_{1}, k_{2}, \dots, k_{n}) \), where \( n = |m| \) is 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 results in the message \( m = \mbox{"meet me tomorrow morning"} \).