RSA Encryption

This page was prepared by Nathan Carter for MA 267 at Bentley College in the Fall of 2006. It is based upon a section in Goodaire and Parmenter's text. Page numbers will differ from the original textbook because our class is using a custom textbook which only contains part of the original.

This page provides tools for use with the RSA Cryptography content on page 100 of your textbook. It also explains that content a bit more than the book does. Note that Wikipedia has an excellent entry on RSA encryption that explains things in even more detail than this page. Heck, Wikipedia has excellent entries on tons of stuff, and several key phrases below are links to Wikipedia articles.

Introduction

RSA Cryptography allows an individual who wants to receive encoded messages to give other people a "public key" that encrypts the messages in such a way that the person who gave the key is the only one who knows how to decrypt them. The public key is a pair of numbers. Another pair of numbers makes up a corresponding "private key," which only the creator of the keys knows, and keeps secret. It is this private key that helps you decrypt numbers.

Today all of this is handled by computers, and you can get software that will encrypt, decrypt, and securely sign messages for you. (See the Wikipedia article referenced above for more information.) But this page helps you work out an example yourself of how all this works, and explains the mathematics used as you go along. A running example is used at each step of the way.

To create a public key

1. First choose two prime numbers p and q. (A list of the first 10,000 primes is handy. Pick small ones or the webpage calculator may overflow...let's say stay under 1000.)

2. Choose another number s that is relatively prime to both p-1 and q-1. Heck, just pick another prime off the list just mentioned. Again, keep it fairly small. (That Wikipedia article actually suggests it should be less than (p-1)(q-1), but that's not strictly necessary.) With a more sophisticated computing environment, you would choose p, q, and s quite large in order to make it harder for anyone to break your code.

3. Now that you've picked your p, q, and s and written them down somewhere, you need to do one more simple computation: Let r = pq and write r down also.

Your public key (the numbers you'll give to other people) are your r and s. Your "private key," which you must keep secret and is necessary to decode messages, is the pair of numbers p and q.

EXAMPLE: To keep things simple, I will choose three small primes. Let p = 101, q = 103, and s = 97. This makes r = 10403. Such small numbers make for insecure encryption, but this is only an example. Thus if someone wanted to send me a message, they would need my public key, which is r = 10403, s = 97. I could even post this on my website, or include it at the bottom of every one of my emails. In fact, you will sometimes see people post their public key, but it is usually written in hexadecimal form (for computer consumption) with both numbers smashed together, so it is not easily human-readable. But I keep secret my private key, the values p = 101, q = 103, which are necessary for decrypting any message sent to me.

Encrypting a message

We will only be allowed to encrypt numerical messages of length less than r. That's the first place where this page begins to help you. The input boxes and button below allows you to type in any text message and your public key, and it will encrypt the message for you. It just turns every character into a separate number and smooshes them together into a row.

It also splits the number every so often (into what are called "blocks" of the message) to be sure each block is a number smaller than r and then follows the encryption scheme, that a block b of your message is encrypted to the remainder of b^s divided by r.

Given a text message M =
and integers r =
and s =	,
click	to split M into blocks and encode it.
Answer:

The legal characters to use in your message M are letters, numbers, spaces, and any of the following.

.

Note that your r and s values must have been created as described above. But the button above does not check to be sure the r and s you provide make sense; it just trusts you.

EXAMPLE: I used the message M = Testing! and the r and s values mentioned above which are the public key of this example. Entering those in the blanks above and clicking the button gives this output. With r = 10403, blocks up to length 2 are possible. Text portion --> as number ~~> encrypted Block 1: "Te" --> 4504 ~~> 9538 Block 2: "st" --> 1819 ~~> 2223 Block 3: "in" --> 813 ~~> 9574 Block 4: "g!" --> 665 ~~> 8596 This means that the r value I've chosen restricts me to sending messages of up to two characters at most. Thus my eight-character message needs to be split up into four little messages (no big deal). Each message gets written as numbers using the simple table at the end of this page, producing the four numbers 4504 1819 813 665. But that's just for convenience of writing letters as numbers; it's not the encryption. Anyone even moderately skilled at codebreaking would easily decipher that message. Thus each of those numbers gets encrypted using the algorithm described above, producing the four numbers in the rightmost column of the output. Thus if someone used my public key to encrypt the message Testing! then I would receive from them the encoded message 9538 2223 9574 8596.

Decrypting a message

When decrypting, you not only have the public key r, s, but you also have your private key p, q. Recall (from pages 66-7 of your textbook) that whenever you have two relatively prime numbers, there is some linear combination of them that equals 1. We need to use this fact twice in preparing to decode an encrypted message E.

Preparation (can be done in advance)

First I'll need a pair of numbers a and b such that sa+(p-1)b=1. Your book shows you the extended Euclidean algorithm that will help you find a and b, but the input boxes and button below should make it go much faster. Once you've found a and b, you'll need to do the same thing again, finding c and d such that sc+(q-1)d=1.

You can find a and b once up front, which is more efficient, back when you choose your p, q, and s, rather than once every time you decrypt. I just kept the material on this page in the same order it is in your textbook.

Given positive integers x =
and y =	that are relatively prime,
click	to produce a, b such that xa + yb = 1.
Answer:

EXAMPLE: To prepare to decode, I need to find a, b, c, and d satisfying the equations mentioned above. Plugging my values of s and p-1 into the equations makes them 97a + 100b = 1 and 97c + 102d = 1. So I fill in x = 97 and y = 100 in the blanks above, and click the button to find a = 33 and b = -32. Filling in x = 97 and y = 102 gives c = -41 and d = 39. The only values I need to keep are a = 33 and c = -41. As mentioned, all this work could be done back when I pick the values of p, q, s, and r, but I am following the order of the textbook, which follows the mathematics more closely.

Why this matters

This section does not involve any description of any work that needs to be done when decrypting, but it is important for me to take a moment to explain the purpose of the computations you just completed, and why they will be useful. Having the numbers a, b, c, and d, we are able to write the following two equations. They probably don't seem useful at first, but they will soon.

M = M¹ = M^sa+(p-1)b = (M^s)^a (M^p-1)^b

M = M¹ = M^sc+(q-1)d = (M^s)^c (M^q-1)^d

Now whatever the original message M was that was encrypted, we know that M^s = E (mod r), and thus both M^s = E (mod p), and M^s = E (mod q), because both p and q divide r. This lets us simplify the above equations a little, mod p and q respectively.

M = E^a (M^p-1)^b (mod p)

M = E^c (M^q-1)^d (mod q)

And in fact, we can simplify further. Fermat's Little Theorem (from page 91 of your textbook) says any number to the p-1 is congruent to 1 mod p for a prime p. So finally we have this.

M = E^a (mod p)

M = E^c (mod q)

EXAMPLE: In my example, I was to receive the message 9538 2223 9574 8596. We consider it one block at a time. If I want to decrypt 9538, then that means E = 9538 and I want to find what the corresponding original message M is. So I need a way to solve these two equations simultaneously. M = 953833 (mod 101) M = 9538-41 (mod 103) And a similar pair of equations for each of the other three blocks of the message. Block 2: M = 222333 (mod 101) M = 2223-41 (mod 103) Block 3: M = 957433 (mod 101) M = 9574-41 (mod 103) Block 4: M = 859633 (mod 101) M = 8596-41 (mod 103)

The decryption itself

The above two equations are just the type of problem the Chinese Remainder Theorem was built for. If we can provide values for E^a and E^c, the theorem shows us how to figure out the message M. The numbers E^a and E^c may be very large, and thus it is possible that whatever calculator you have at your disposal will not handle them. The following input boxes and button will compute smaller numbers that are congruent to the actual answers mod p and q, as needed.

Given integers x =	,
y =	,
and m =	> 0,
click	to produce the smallest z > 0 such that xy = z (mod m).
Answer:

Even if x and y are fairly large, the computations will be done in such a way that no calculator overflow occurs.

It's interesting that y may sometimes be negative, which is okay because p is prime, and thus everything has a multiplicative inverse mod p. In fact, that inverse is the number F the extended Euclidean algorithm would give if we asked for values F and t such that FE + tp = 1.

EXAMPLE: Recall from above that to decode the first block of my message I need to solve the equations. M = 953833 (mod 101) M = 9538-41 (mod 103) First I need to know what 953833 is modulo 101. Plugging in 9538, 33, and 101 in the above blanks and clicking the button tells me that 953833 = 60 (mod 101). Thus the first equation can really be rewritten more conveniently as M = 60 (mod 101). Repeating with -41 and 103 allows me to rewrite the other equation also. M = 75 (mod 103). Recall that this must be done for each block of the message. Block 2: M = 1 (mod 101). M = 68 (mod 103). Block 3: M = 5 (mod 101). M = 92 (mod 103). Block 4: M = 59 (mod 101). M = 47 (mod 103).

Page 98 of your textbook gives an algorithm for applying the Chinese Remainder Theorem to situations just like the pair of equations above (once you've filled in E^a and E^c) to find a solution M < r as the example has done. The following input boxes and button will do it for you, if you enter the values correctly.

Given integers b =	,
c =	,
m =	,
and n =	, with m and n relatively prime,
click	to produce the unique a such that 0 < a < mn
	such that a = b (mod m) and a = c (mod n).
Answer:

EXAMPLE: The input boxes and button above purport to solve equations like the pair shown on the left below. On the right next to them I have written the first pair of equations I need solved (for the first block of my encrypted message). a = b (mod m)                                 M = 60 (mod 101) a = c (mod n)                                 M = 75 (mod 103) So into the four blanks above, I type in the numbers 60, 75, 101, 103, in that order, and click the button. It tells me my decrypted message block is 4504. I repeat for each of the other blocks of the message. Block 2: M = 1 (mod 101) and M = 68 (mod 103)       -->       M = 1819 Block 3: M = 5 (mod 101) and M = 92 (mod 103)       -->       M = 813 Block 4: M = 59 (mod 101) and M = 47 (mod 103)       -->       M = 665

Note that the output in the blank above is a number, which will need to be converted back into text. The following table should help.

Table for encoding/decoding single characters

EXAMPLE: It is easy to decode each block by hand using the table. 4504     -->     45   04     -->     T   e 1819     -->     18   19     -->     s   t 813     -->     08   13     -->     i   n 665     -->     06   65     -->     g   ! Stringing it all together gives the original message Testing!