Re: A86:RSA Encryption

[Prev][Next][Index][Thread]

Re: A86:RSA Encryption


I was wondering if anyone on this list knows how RSA encryption works

Thanx in advance
----- My Reply ---------------------------------------
I got the following directly from a website: 
http://world.std.com/~franl/crypto/rsa-guts.html
---

The RSA algorithm was invented in 1978 by Ron Rivest, Adi Shamir, and 
Leonard Adleman.

Here's the relatively easy to understand math behind RSA public key 
encryption. It is most ironic that it is not illegal to transport this 
mathematical description out of the U.S. and Canada, but it is illegal to 
export an implementation of this cipher from the U.S. or Canada. Any 
competant programmer could use this knowledge to implement a strong crypto 
product beyond the borders of the U.S. and Canada.

Find P and Q, two large (e.g., 1024-bit) prime numbers.

Choose E such that E is less than PQ, and such that E and (P-1)(Q-1) are 
relatively prime, which means they have no prime factors in common. E does 
not have to be prime, but it must be odd. (P-1)(Q-1) can't be prime because 
it's an even number.

Compute D such that (DE - 1) is evenly divisible by (P-1)(Q-1). 
Mathematicians write this as DE = 1 mod (P-1)(Q-1), and they call D the 
multiplicative inverse of E.

The encryption function is encrypt(T) = (T^E) mod PQ, where T is the 
plaintext (a positive integer) and ^ indicates exponentiation.

The decryption function is decrypt(C) = (C^D) mod PQ, where C is the 
ciphertext (a positive integer) and ^ indicates exponentiation.
Your public key is the pair (PQ, E). Your private key is the number D 
(reveal it to no one). The product PQ is the modulus (often called N in the 
literature). E is the public exponent. D is the secret exponent.

You can publish your public key freely, because there are no known easy 
methods of calculating D, P, or Q given only (PQ, E) (your public key). If P 
and Q are each 1024 bits long, the sun will burn out before the most 
powerful computers presently in existence can factor your modulus into P and 
Q.

--- Here is an example of RSA encryption: ---
p  = 61    <= first prime number (destroy this after computing e and d)
q  = 53    <= second prime number (destroy this after computing e and d)
pq = 3233  <= modulus (give this to others)
e  = 17    <= public exponent (give this to others)
d  = 2753  <= private exponent (keep this secret!)

Your public key is (pq,e).
Your private key is d.

C = encrypt(T) = (T^17) mod 3233
T = decrypt(C) = (C^2753) mod 3233

encrypt(123) = (123^17) mod 3233
             = 337587917446653715596592958817679803 mod 3233
             = 855

decrypt(855) = (855^2753) mod 3233
             =
50432888958416068734422899127394466631453878360035509315554967564501
05562861208255997874424542811005438349865428933638493024645144150785

[snip]

54234930424749053693992776114261796407100127643280428706083531594582
305946326827861270203356980346143245697021484375 mod 3233
             = 123








-----     RSA in 2 Lines of Perl     -----

It uses dc, an arbritrary precision arithmetic package that ships with most 
UNIX systems. Here's the Perl code:

print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`


        -Barcode (Andy D.)
        http://nft.cjb.net

______________________________________________________
Get Your Private, Free Email at http://www.hotmail.com