|
What is RSA Encryption?
RSA Encryption is a method of manipulating data so that it can be sent to another person
without being intercepted and understood by someone other than the intended receiver. It is commonly used for secure
communications on the internet when sending payment or other personal information across an open line.
How does RSA Encryption work?
RSA Encryption uses a two key system to encrypt data. Information is encrypted with the
public key of the intended receiver, and can be decrypted only with the intended receiver's private key. This means
that regardless of who intercepts the message in-transit, only the intended receiver can read it.
The elements used in RSA Encryption are:
 | P & Q: prime numbers used to generate the keys
| N: the modulus or public key, used when encrypting or decrypting
| PHI: used to find E
| E: an exponent used when encrypting
| D: the private key, used when decrypting
| | | | |
Here is an example showing how to generate your keys and walking through an encryption
example:
Let's assume that I want to send you an encrypted message. The first thing I need is your
public key. In order to get your keys, you first need to decide how large you want the key to be. Larger keys are
more secure, but take longer to process messages. For this example you select a 16 bit key (which makes the math
easier, but can be cracked in under 10 seconds).
Since you want your final key to be 16 bits, you generate two prime numbers with half
the number of bits: 8. Your first prime number P = 163, your second Q = 193. Your public key N = P * Q or 31459.
To encrypt a message, we also need E (the exponent). E is the lowest number that is relatively prime with PHI (the
greatest common denominator of E and PHI is 1). PHI = (P-1) * (Q-1) or 31104. Finding E now is a little less straight
forward. Starting at 2, fing the greatest common denominator of E and PHI; if it is 1, you've found E; otherwise,
increment and try againg. In this example, E works out to 5... it is almost always a low number and so requires
little cpu time to find. The final element is D. D = E inversemod PHI. Finding this programatically can be a pain,
but classes have been built with inverse mod functions that greatly simplify the programmer's job. D in our example
is 6221.
Now that we have our values, let's say the message I want to send you is the number 25.
The encrypted value is 25^E mod N or 13335. To get this information, I needed only E and N. To decrypt it, you
will need D (your private key) and N. The decrypted value is 13335^D mod N or 25!
Weakness of RSA Encryption
Every encryption algorhythm has a weakness, and RSA is no different. Since the public
key N is generated using prime numbers, the public key itself can be used to find P and Q. The security varies
based on the number of bits used for the key. In the example above, the 16 bit key can be cracked on a 233 P1 in
under 10 seconds, while a larger key of 128 bits is estimated at 9 * 10^8 years to crack (without optimizations...
my time estimate is off since it assumes going from the current attempt to 0, but we're still looking at a couple
of decades). The security of this system is provided by the sheer number of iterations a computer must go through
to find the correct primes needed to generate the keys. The number of attempts needed increases exponentially in
relation to the number of bits in the key. Optimizations can make significant improvements on this, but I'll leave
it up to you to figure out how to speed things up ;-) .
Java Toys
Attached are the classes of a Java application that generates P, Q, and N; and then uses
N to attempt to crack P and Q. Once P and Q are found through the crack, PHI, E, and D are generated. Every 100000
iterations, the program will show the current key and the estimated number of seconds remaining (ESR). The current
attempt appears to be 200000 less than the last because our attempts start at the
square root of N and decrement
by 2 (only one even prime, so why try them all). The program can also generate prime numbers with the specified
number of bits. This is a true Java app and has only been tested using Sun's JDK 1.1. It may not work with Microsoft
'Java.' Get Sun Java -- its free.
You will need both classes to run: Zipped Classes
Syntax:
java RSATester #bits
Generates P and Q with the #bits specified (your key will have twice this number) and
proceeds with the crack.
java RSATester Primes #bits
Generates a random prime with the #bits specified, and continues to find the next higher
prime untill stopped.
Remember that java IS case sensitive, and the commands shown above must be entered with
the proper case. Extract the classes to the directory of your choice and run the commands from there.
|
