Visit our newest sister site!
Hundreds of free aircraft flight manuals
Civilian • Historical • Military • Declassified • FREE!

 TUCoPS :: Crypto :: rsa.txt RSA encryption
```
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).

```

TUCoPS is optimized to look best in Firefox® on a widescreen monitor (1440x900 or better).
Site design & layout copyright © 1986-2015 AOH