Teacher resources and professional development across the curriculum

Teacher professional development and classroom resources across the curriculum

Monthly Update sign up
Mailing List signup
Search
MENU

Unit 1

The Primes

1.6 Encryption

HISTORY

• The need to send private messages has ancient roots.
• Most historical encryption schemes used private keys.

When sending sensitive information, such as logging onto a bank account via the World Wide Web, we want the intended receiver to be able to "read" the message, and we also want any unintended recipient (or thief) of the message to be thwarted. To accomplish this, we need a system of encryption, one that will be impervious to even the cleverest of hackers. Online transactions are only the most recent example of situations in which information must be protected while in transit. There have been many different systems of encoding throughout the years, many of them mathematical in nature.

Mathematical encryption relies on concepts such as modular arithmetic and the fundamental properties of prime numbers to make messages incomprehensible to unintended recipients. Obviously, encryption requires operations that are easy to perform one way (i.e., encoding), yet nearly impossible to perform the other way (i.e., decoding) without a key. Prime numbers can help us with this. Recall that multiplying two primes is easy, whereas factoring a product of two unknown primes can be extremely difficult and time-consuming.

The problem of sending a vital message to someone without it being discovered, or deciphered, is an ancient one. This need crops up in a variety of situations, but an all-too-common need for encryption has arisen time after time on the battlefield. When attacking an enemy, it is critical to be able to send coordinating information to your involved units without the enemy discovering your plans. By encrypting messages in some fashion, you hope that, even if a message is intercepted, its meaning will be inaccessible to unintended readers. Encryption schemes have come in many forms throughout the ages. Many early schemes could hardly be called "encryption"—"concealment" would be a more appropriate term. A particularly striking example is the story of Histaiaeus, a 5th-century-BC Greek provincial ruler, or tyrant, who wanted to encourage a fellow tyrant of a neighboring state to revolt against the Persian king, Darius. To convey his instructions securely, Histaiaeus shaved the head of his messenger, wrote the message on his scalp, and then waited for the hair to re-grow. The messenger, apparently carrying nothing of interest, traveled without being harassed. Upon arriving at his destination, the messenger shaved his head and pointed it toward the intended recipient. Although this was perhaps clever for its time, such a system would quickly be compromised as word of its use spread.

back to top

CAESAR CIPHERS

• The simplest encryption scheme is to jumble the letters of the alphabet according to some rule.

Clearly, a system of simply concealing one's message is effective only up to a point—a thorough search is all that is needed to expose the scheme and intercept the message. To ensure message security, one would want an interloper, were he or she to find the communication, to be baffled by what it actually says. A simple scheme, whose first use is attributed to Julius Caesar, is to replace each letter of the alphabet with a different letter according to some rule. For example:

rule of add three

This scheme replaces each letter with the letter that comes three letters later in the sequence of the alphabet. In effect, this encoding scheme just shifts the alphabet three letters to the left, with the substitutions for the last three letters coming from the beginning of the sequence. Our key, let's call it "k," is 3. Let's now shift our thinking from letters to numbers; we can easily assign each letter of the alphabet to a corresponding number as follows:

rule of add three

Applying the same "shift by 3" that was just used in the preceding example to this new system creates the following encryption scheme:

rule of add three

To encrypt a letter, we simply add three to the number with which it was originally paired. For example:

A, originally paired with "1" gets shifted, or encrypted, to "4."
and
M, originally paired with "13" gets shifted to "16."

When we get to X, however, we have a problem. Following the current encryption scheme, X, originally associated with "24," would get shifted to "27." However, 27 isn't anywhere in our list of possible numbers. So, we can wrap around and start over at 1 after hitting 26 instead of using more numbers. To express this adjustment mathematically, we could write:

24 + 3 = 1

This strange sort of arithmetic might seem somewhat familiar because it is related to how we apply arithmetic to cyclical time. For example, if it is four o'clock and we add twelve hours, it is again four o'clock, ignoring the A.M./P.M. difference. This "clock math" is known as "modular arithmetic."

back to top

MODULAR ARITHMETIC

Modular arithmetic is a key to understanding modern forms of encryption, and it also demonstrates interesting properties of prime numbers. It incorporates"wrap around" effects by having some number other than zero play the role of zero in addition. For example, on an analog clock:

Analog Clock

The number 12 behaves like zero, because adding 12 hours to any time (again, ignoring A.M. or P.M. differences) doesn't change anything. A typical addition problem in this scheme would be:

3 + 12 = 3

To write a number in this system, we have to be conscious of how many multiples of 12 it contains. A number such as 5 has no multiples of 12 in it, so we would simply write 5. The number 17, however, is 5 + 1(12), which is also equal to 5 in this system. Similarly, the number 29 is 5 + 2(12), which is also equal to 5, again because the number twelve is acting like zero in this system.

In such a system, 12 is called the "modulus." To describe the number 29, we would say that it is "congruent to 5 modulo 12", or 29 ≡ 5 mod 12.

Note that:
5 ≡ 5 mod 12
17 ≡ 5 mod 12
29 ≡ 5 mod 12
etc.

Any number of the form 5 + n(12) will be congruent to 5 in this system.

With this new foundation in modular arithmetic, let's return to the Caesar cipher from before. Previously, the integrity of the code was dependent on the security of our key (i.e., only we and our intended correspondent can know it). The integrity of our code is vulnerable, however, to anyone who suspects that we are simply shifting letters. If our message is sufficiently long, one could rather easily figure out our key by examining letter frequencies. That is, it is highly likely that the letter that appears most frequently in our code represents the letter "E," which is the most commonly used letter in English. After the code is "cracked" in this way, the whole scheme crumbles because every letter is shifted by the same amount!

Let's shift our thinking back to a number code again. To increase security and make our encryption "uncrackable" by a simple shift, we could multiply numbers instead. In this case, the code key would be the number by which we choose to multiply the original numbers. Multiplying in modular arithmetic is just like multiplying in normal arithmetic, except that whenever we encounter a product that is greater than some multiple of our modulus, we use the wraparound effect. For example, using our clock from before (mod 12), 4 × 2 ≡ 8 mod 12 (no surprise), but 4 × 3 ≡ 0 mod 12, and 4 × 4 ≡ 4 mod 12. A multiplication table for mod 12 looks like this:

Mod 12 Multiplication Chart

Notice first that we are using zero in place of the number twelve. Also, notice that some of the columns do not contain all of the numbers in our system, namely all of the numbers between 0 and 11 inclusive. As you can see, this is true for the rows, as well. If we were to choose these numbers as our key for encrypting a message, we would be setting our recipient up for confusion. For example, let's say that our encryption scheme involves multiplying the numbers that make up our message by 4 in this mod 12 system. For simplicity's sake, let's also say we are using a 12-letter alphabet.

Corresponding 12 Letter Alphabet

This would serve as the top row of our mod 12 table. Because we are using k = 4 as our key, we are going to look to the 4th row of the table.

Table Mod 12 Row 4 Key

The letter D, which is 4, would be encoded as:
4(letter) × 4(key) ≡ 4 (encrypted letter) mod 12

G would be:
7(letter) × 4(key) ≡ 4 (encrypted letter) mod 12

J would be:
10(letter) × 4(key) ≡ 4 (encrypted letter) mod 12

The same goes for the letter A.

So, suppose that the message we want to encrypt is "GD JA." Following this encryption scheme, the message would be encoded as "4444." How would the recipient know which 4's represent D's and which are supposed to be J's, G's, or A's? It would be impossible for our recipient to decode our message. For this reason, choosing 4, or any other key for which the row does not contain every number is a bad idea!

Note, however, that 7 contains all the numbers in its corresponding row and column. This means that using 7 as a key would give each letter a unique number in our encryption scheme.

Seven is not the only number we could choose, of course. A quick check of the table shows that both 5 and 11 would work, as well. Notice also that 5, 7, and 11, the three numbers that have all the potential code numbers present in their rows and columns, share no common factors with the modulus, 12. This is because they are prime but are not factors of 12. The numbers 2 and 3 are also prime, but they are factors of 12, so their rows and columns include repetitions. This suggests that prime numbers have some interesting properties in modular arithmetic, especially as it relates to making sure that every letter has a unique encryption. The power of prime numbers in codes, however, does not stop there.

PRIME MODULI

To maximize the potential number of encoding keys, we would ideally like to have a table that includes every possible value in every column and every row. With such a table, any key we choose will accurately transmit our message— that is, our recipient will be able to decode the message with no ambiguity. We noticed that keys that share factors with the modulus, or "size of our clock," are no good. So, what if we choose a modulus that is unlikely to share factors with other numbers? A prime number has no factors other than 1 and itself, so it seems that any prime would be a good choice of modulus in this situation.

For example, the mod 7 multiplication table looks like this:

Mod 7 Multiplication Table

This modulus would correspond to a seven-letter alphabet:

Mod 7 Alphabet

Would a system such as this be harder to crack? Looking at our mod 7 table, we can see that for a key of 5, which again means that we look at row 5, the letter D gets mapped, or encoded, to 6. If someone were to figure out, perhaps by analyzing letter frequencies, that D is represented by 6, and they knew that our modulus, the size of our alphabet, was 7, then they could set up the following congruence: 4 × k ≡ 6 mod 7. With a little more thought, they could figure out that k must be represented by 5. So, it seems that this encryption system is somewhat more difficult to crack than the additive Caesar cipher, but it is by no means impenetrable!

An advantage of having a prime modulus is that every "fraction," mod p, will exist. Think for a minute back to mod 12.

Mod 12 Multiplication

Can we find a number, that, when multiplied by 5, for example, yields 1? In other words, does 5 have a reciprocal? This number would have to be our equivalent of "one fifth." Looking at our mod 12 table, we can see that this number is 5. So, 5 plays the role of "one fifth" because 5 × 5 ≡ 1 mod 12. Does every number in mod 12 have such a reciprocal fraction? Consider the number 2, and notice that nowhere in the rows or columns marked by 2 does the number 1 appear. This means that in the mod 12 system, there is no number that you can multiply 2 by and get an answer of 1—the 2 has no reciprocal. In other words, in the mod 12 system, not all fractions exist!

Now let's look at our mod 7 table again.

Mod 7 Multiplication

We figured out that because 7 is prime, every number appears in every row of the table. Therefore, the number 1 appears in every row, which implies that every number has an associated reciprocal. In addition to a maximal choice of keys, the existence of every reciprocal is necessary in order to create an encryption scheme that is much harder to break than anything we have seen so far. Reciprocals are critical because instead of adding or multiplying in a given modulus, we will need to use exponents to create a strong encryption scheme. Specifically, we will be raising powers to powers, such as (23)4, which is equivalent to 23 × 4, or 212.

Suppose that our message is some number, M. In this strong encryption scheme, we could raise M to a power, e, to encrypt it. If another number, d, is the reciprocal of e, then it can be used to decrypt Me as follows:

(Me)d = Me × d = M1 = M

In order for this strategy to work in the modulus that we are using, every number, e, must have a reciprocal, d. This will be true only if our modulus is prime. We've now caught a glimpse of the unique properties of primes in modular arithmetic. This understanding is an important base from which we can launch our examination of the modern standard for data encryption, RSA , in the final section.

back to top

Next: 1.7 RSA Encryption


HomeVideo CatalogAbout UsSearchContact Us

© Annenberg Foundation 2013. All rights reserved. Privacy Policy