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.7 RSA Encryption

PUBLIC KEY ENCRYPTION

• RSA encryption is the modern standard for sending secure information.
• RSA is based on the modular arithmetic of primes.

In the mid 1970s, three MIT researchers, Ron Rivest, Adi Shamir, and Leonard Adleman, discovered a new method of encryption that relies on the properties of primes and modular arithmetic. This system, RSA (initials of the discoverers), has remained secure for over 20 years, although countless people have attempted to breach it. In 1982, Rivest, Shamir, and Adleman founded RSA Security, a company that would go on to provide the standard in data encryption used worldwide on the Internet.

RSA encryption relies not on one key, as in our previous Caesar cipher examples, but on two. One of these keys is made public, and the other is kept private. If you wish someone to send you an encrypted message, you simply tell them your public key, and they can then encrypt their message so that only you can read it. They do not need to know your private key for this system to work. Here is a brief, and somewhat simplified, description of the process.

As we have seen throughout this unit, multiplying two primes together is easy to do, but factoring a large number into primes is a nightmarish trial-and-error scenario if the number has only two large primes as factors. This property of primes provides the basis of the RSA encryption scheme.

In general, to encrypt a message using the RSA method, we choose two large primes, p and q, and multiply them to produce a number N. The number N will be the modulus of our system and will be made public. This is fine; because p and q are both large and prime, their product, N, will be practically impossible to factor and can be confidently made public knowledge. We will now use p and q to make our public and private keys.

To make our keys, we first subtract 1 from both p and q and then multiply the results: (p-1)(q-1) = T. At this point, we will choose our public key, which can be any number less than T that shares no factors with it. This public key is what we referred to in the previous section as e. To construct our private key, we need to identify a number, d, such that when it is multiplied by e, the public key, it is congruent to 1 mod T. In other words, the following congruence must hold:

d × e ≡ 1 mod T

Now, if we want someone to send us a message that only we can read, we tell them the modulus, N, and the encryption key, e. They then convert their message from letters to a series of number strings, or "words," just as we have been doing in previous sections of this text. We must be careful that none of the words are larger than the modulus, which would result in some words being indecipherable. Let's say this word is the number M. The encrypter raises each word to the "eth" power, mod N. This new word, let's call it C, is now encrypted and can be sent to us. In mathematical terms, we have:

C ≡ Me mod N

We receive the coded number C. To decrypt it, all we have to do is raise it to the "dth" power, mod N. This works because Cd ≡ (Me)d mod N, and Rivest, Shamir, and Adleman were able to show that Med ≡ M mod N. Recall that we chose e and d such that, d times e triple equal 1 mod T (d × e = 1 mod T), so there is some mathematics hidden in this statement! Thus, our private key, known
only to us, undoes the encryption of the public key. Anyone who knows e and N can send us a message that only we, because we know d, can decrypt. To get a better idea, let's look at an example.

A WORKED EXAMPLE OF RSA ENCRYPTION

Real RSA encryption uses very large numbers, which would be very difficult— not to mention less than illuminating—to use here. In this example, we'll use smaller numbers that are not at all realistic but that illustrate how the method works.

First, let's choose the primes that form the foundation of our scheme, p and q:
p = 17 and q = 19

By multiplying p and q, we get our modulus, N:
N = 17 × 19 = 323

Now, we find T by subtracting 1 from both p and q and multiplying:

T = (p-1) × (q-1) = (16) × (18) = 288
Next, we can select the encryption key, the public key, e, so that it has no common factors with 288. Let's let e = 11.

To find the decryption key, d, we need a number that, multiplied by e, gives a product that is congruent to 1 mod 288. Expressed mathematically, we need to find a number d such that:
11 × d = 1 + n(288)

Using trial and error, we find that 131 works because 11 × 131 = 1 + 5(288).

So, our public key is N = 323 and e = 11.

The private key is d = 131.

If someone wants to send us the message "ABC" securely, using this scheme, we tell them N and e. They first convert "ABC" to "123" and then do the following arithmetic:

123e = (123)11 mod 323 = 81

The sender could then send the message, "81," over a public line of communication with confidence.

To decrypt the code, "81," we can use N and d as follows:

81d = (81)131 mod 323 = 123

The message "81" becomes "123" after decryption, which we can then easily convert to "ABC," which was the intended message.

Notice that in order to break this scheme, a hacker would have to find the two numbers that when multiplied together yield 323. The square root of 323 is a little less than 18, so they would have to try a maximum of 7 divisors before they would be guaranteed to break the modulus into the original primes that were used to find the public and private keys. Using a computer, this would not be difficult, so real RSA encryption uses numbers that are sufficiently large so that even the fastest computers would take longer than a human lifespan to factor them. It is upon this foundation, the difficulty of factoring products of two large prime numbers, that modern data encryption rests.

back to top

Next: Bibliography


HomeVideo CatalogAbout UsSearchContact Us

© Annenberg Foundation 2013. All rights reserved. Privacy Policy