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 
yeilded 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).