RSA Encryption and Decryption

by Modern UART

Keeping Secrets File #3

RSA Encryption and Decryption

by Modern UART

written for the New Gnostics, NYC

This text file is intended to serve as a tutorial for those who wish to encrypt and decrypt their files using the RSA scheme. While the scheme is explained in detail, I suggest that another scheme be utilized. My reasons for making this recommendation can be found scattered throughout the text.

RSA encryption is a method for securing data. It has unique properties that make it especially attractive for securing data that must be transferred among many parties. Sensitive information that is, for instance, stored on a bulletin board system, can be secured using RSA and posted publicly. It can be downloaded by several people who possess keys for the data, and can only be decrypted with the right key.

Can RSA encryption be broken? Well, yes and no. Data that is encrypted with a sufficiently strong key cannot be broken within the life span of the planet earth. Data encrypted with a weak key can be broken by a ten-year-old with a pocket calculator.

RSA is dependent upon the use, and the unique properties, of prime numbers. A VERY large prime number used as a key is a VERY strong key. The problem is, how do we get those large prime numbers?

First, for you real math virgins, prime numbers are numbers that can only be divided by themselves and 1 with there being no remainder. The early primes are 2,3,5,7,.... 1 is considered neither prime or non-prime. The common way to find prime numbers is to use the sieve of Eratosthenes. This has been the only true way to find all primes in a range since the third century B.C. The sieve works like this: Let's say you want to find all the prime numbers in between 2 and 100. Well, you write each number down and start with 2. 2 is prime, so circle 2 and cross off all the numbers in the list that would go evenly into 2 (4,6,8, etc.). Go on to 3. It hasn't been crossed off, so it's prime. circle it and cross off all the numbers that go evenly into it (9,12, etc.). Go on to 4. It's crossed off so go on to 5. It's not crossed off so it's prime. Circle it and cross off numbers that would go evenly into it. Keep this up until all the numbers in the list are either circled or crossed off, and all the primes are circled.

On a computer, this can easily be done in an array.

Obviously, hunting for primes is a big pain in the ass. This is the first problem with RSA. If we wanted to find all the prime numbers between, let's say, 1 and 8,000, we'd need an array with 8,000 elements to use the sieve. If we were to define each element as a bit, that's 1000 bytes. but the largest prime we could hope to find with such a program would be 8000 (which is obviously not prime). And 8000 isn't a large enough prime to make RSA secure. Try 8000000000000000000000000. This is, it's true, a pain in the ass, but it's also why RSA works. Because it's so hard to find primes, even on computers, the chances of your data being decrypted are really astronomical.

RSA really is based on a simple mathematical principle. It's easier to multiply two prime numbers than it is to figure out what two prime factors a particular huge composite (non-prime) number is the product of.

Okay, let's say I want to receive encrypted messages. I tell you that I want the messages sent as follows: I will supply you with two numbers, a very large number N and an integer r. You must transform your message into an integer of no greater than N, breaking it into blocks if necessary. Now raise this number to the power r, divide this result by N, and send me the remainder.

Now, let's look at how we decide what those numbers should be. We take two prime numbers, let's say 3 and 11. We multiply them to get 33, which will be our value for N. Next, we go through the following procedure to get two more values (one value will be r and one will be s, which will be used for decryption). We subtract 1 from each prime number to get 2 and 10, then we multiply these numbers. r can be any value between 1 and twenty that is not a factor of 20, so 2, 4, 5, and 10 are eliminated. To determine s, we need to find a number that when multiplied by our value r and then divided by 20 will always leave a remainder of 1. So let's say we chose 7 as r, then a suitable value for s might be 3, since r*s(mod 20) = 1 then 7*3(mod 20) = 1, where mod = modulo, a fancy word for divide and throw away everything but the remainder.

I want you to send me an encrypted message, so I give you N and r but keep s to myself.

Let's say the message is "H". In order to keep the example simple, I will take certain liberties. First of all, instead of using ASCII, I will simply number the letters of the alphabet. That is because in order for the scheme to work, the values transmitted must fall between the range of 1 and N. ASCII would automatically violate that constraint using the simple values I've defined.

So, "H" here will equal 8. Since N=33, you are within the constraints of N. You will compute 8^7 = 2097152. Now you compute 2097152/33 and keep the remainder, which is 2. Okay, so you send me the number 2.

To decrypt the message, I would compute 2^3. This is, of course, 8. Usually I would have to divide this by N (33) and the remainder would be my answer. In this simple example, simply multiplying the message has yielded the answer.

That's all there is to it.

But here we've reached the first of the series of problems with RSA. First, any schoolkid could have cracked the above example. For the sake of the example I kept it extremely simple, yet still had the intermediate value 2097152. Much larger values are needed for N, which usually means much larger values for r and s. These yeild absolutely uncrackable results, but you try writing the code for 120 byte unsigned integers and see how far you get. And 120 byte unsigned integers are just the beginning, really. To send the code "Hi!" as a 24-bit integer, you'll get an intermediate value with a minimum of 33 (decimal) digits, whatever values you have picked for N, r, and s. Try sending a whole sentence!

This makes RSA really slow, and absolutely unusable on all but the fastest of micros. Now, there are better algorithms for computing primes, specifically ones that skip a few in between. Actually, these are the only algorithms that are worth using. The great thing is that while you only need to be sure any two large numbers are prime to encrypt a message, a person would have to try every possible prime to crack a message. And with a (very) small stream length, RSA is a possibility. Also, RSA really doesn't explode the length of a file like some encryption methods (like multi-pass DES) do. Because it uses modulo arithmetic, packet sizes are always kept under the length of N. Those are the benefits of RSA. However, several other encryption methods, particularly key-dependant ones like multi-pass DES and toth, are more practical. On the other hand, If you post your keys, anyone in the world can use them to send you messages and only you can decrypt them. That's not bad. Still to come: knapsack (a variation of RSA), and toth (a two-key password system).