Secret Codes: Secret Key Cryptography & The Caesar Cipher
Secret Codes: Secret Key Cryptography & The Caesar Cipher
Secret Codes: Secret Key Cryptography & The Caesar Cipher
Last time we talked about error-detecting codes. These were codes that added some additional information
to a “message” (like the UPC information) in such a way that certain types of copying errors would be
detected.
Today we want to look at a different kind of code called a secret code. Now we want to encode messages
in such a way that only the intended recipients can figure out the message. The study of secret codes
is called cryptography. Obviously this is tremendously important for electronic financial transactions (we
don’t want anyone else to have access to our money at the ATM) and for national security (we can’t have
enemies eavesdropping on our war plans). In fact, the National Security Agency of the United States is
the single largest employer of mathematicians in the country, and one of the main things they study is
code-making and code-breaking.
Many of the coding schemes use modular arithmetic. Let’s look at two of them.
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
1. Convert the message “I LOVE MATH!” into its 9-number code. Notice that the blanks and punctu-
ation are ignored.
Next, some number (Caesar reportedly used 3) was added to each number in the code. (Of course, we
should work mod 26 – why?) This number (3 for Caesar) is called the encoding key.
2. Convert the 9-number code into a new 9-number code by adding 3 (mod 26) to each of the 9 numbers.
Finally, the numeric encoding was converted back to a letter encoding (using the table again).
3. Convert the 9-number code into a new 9-number code by adding 3 (mod 26) to each of the 9 numbers.
4. It is possible to describe this process without using any numbers. Explain how to encode “I LOVE
MATH!” without using any numbers.
5. More messages. Encode each of these messages using a Caesar cipher with encoding key 3.
a) “HELLO”
b) “GO KNIGHTS!”
c) “TO INFINITY AND BEYOND!”
Now redo them with an encoding key of 9.
OK, we’re half done. We can encode messages. But how does the recipient decode them? You can probably
figure this one out.
8. If your method for decoding involved subtraction (or going backwards), try to find another (equivalent
method) that uses addition (or going forwards).
So decoding and encoding are the same thing (but with different keys)! The problem is that once someone
knows the encoding key (e), they can easily figure out the decoding key (d). This has some big disad-
vantages. In particular, how does the sender tell the recipient what key to use? (If you send it with the
messenger, you might as well let the messenger know the message.)
Now we want to find a system such that knowing e is not enough to figure out d. That way, we can receive
messages by posting our encoding key (e) in a directory. Anyone who wants to send a message can simply
encode it with our public key. Of course, we keep the decoding key a secret and use it to decode the
message. We call this the private key.
Let’s suppose we want to send numbers as messages (that saves us the conversion back and forth to letters,
but we could do that if we needed to.) Our directory would look like this:
To send Jane a message, we work mod 65 and encode with e = 5. Of course, we can’t use the Caesar
cipher, because then everyone would know how to decode, and we only want Jane to be able to decode.
So what can we do?
RSA is one particular system that is amazingly like the Caesar cipher. The biggest difference is that we
will use multiplication (actually exponentiation) instead of addition. So here is the scheme.
To send a message to Jane we take our number (let’s call it M for message) and raise it to the power 5
(mod 65). So to send Jane the number 10, we code it as
Decoding uses the same process, but we need to know the secret key. Jane’s secret key is 29 (don’t tell).
So she can decode her secret message from us (30) as follows:
3029 (mod 65) ≡ 6863037736488300000000000000000000000000000 (mod 65) ≡ 10 (mod 65)
It worked! Provided you believe my modular arithmetic. Notice how large 30 29 is. Imagine using large
numbers with 200-400 digits! (That’s the size number used by RSA in practice.) The exponentiation would
get so large, even a computer could not store all the digits.
The situation is very similar to trying to do this computation on a calculator that can only display 10-digit
numbers. Given such a calculator, how do we compute 30 29 (mod 65)? The trick is to do the modular
arithmetic as we go along rather than at the end.
Here’s how it works in our example. First notice that 100 5 = 10000000000 is the smallest 11-digit number,
so we can raise 2-digit numbers to about the fifth power on our calculator (with smaller numbers we can
go a bit higher).
304 = 810000 ≡ 35 (mod 65)
305 = 24300000 ≡ 10 (mod 65)
3025 = (305 )5 ≡ 105 ≡ 100000 ≡ 30 (mod 65)
3029 = 3025 × 304 ≡ 30 × 35 ≡ 1050 ≡ 10 (mod 65)
By taking somewhat smaller steps, we do this using numbers with at most 4-digits (twice the number of
digits in 65).
The numbers n = 65, e = 5, and d = 29 form the three ingredients for an RSA public key cryptography
system. Not just any numbers will work, but there are many that do, and they can be found using a
computer and some facts about prime numbers. Notice that what we need is
(M e )d = M ed ≡ M (mod n)
Or in our case,
(M 5 )29 = M 145 ≡ M (mod 65)
This says that if we take a message and code it, then decode it, we get the original message back, which
is just what we want.
If n is a product of two prime numbers (like 65 = 5 × 13), then we can find numbers e and d that work.
Thus for RSA to work, Jane must also keep secret how to factor n. Fortunately (for cryptography) it is
much easier to multiply than to factor, so Jane can find two large primes (about 200-digits) multiply them
together (to get a number with about 400 digits), but no one knows how to factor such a large number,
even with the fastest computers available today running non-stop for weeks and months.
We won’t go into the theory of all this (but you can read some of it in the text book, if you are interested).
Suffice it to say, it makes use of some special properties of prime numbers and modular arithmetic, the two
things we have been studying.
Solutions
4 I LOVE MATH = L ORYH PDWK
5 Here are the solutions using keys of 3, 6, and 9 to encode: