View Source: RSA - Waikato Linux Users Group

Edit PageHistory Diff Info LikePages
RSA is a cryptographic algorithm, named after its authors, [Rivest, Shamir, and Adleman|Acronym].  (Also an acronym for the [Returned Serviceman's Association|http://www.rsa.org.nz/].  Ask your grandfather, if he's sober.)

This is commonly the algorithm used in PublicKeyEncryption.

Loosely described, this is how it works.

# Find P and Q, two large (e.g., 1024-bit) prime numbers.
# Choose E such that E is greater than 1, E is less than PQ, and 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. This is easy to do -- simply find an integer X which causes D = (X(P-1)(Q-1) + 1)/E to be an integer, then use that value of D.
# The encryption function is C = (T^E) mod PQ, where C is the ciphertext (a positive integer), T is the plaintext (a positive integer), and ^ indicates exponentiation. The message being encrypted, T, must be less than the modulus, PQ.
# The decryption function is T = (C^D) mod PQ, where C is the ciphertext (a positive integer), T is the plaintext (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.

[An example of RSA encryption|http://world.std.com/~franl/crypto/rsa-example.html].  Go read t - it makes all the above stuff make sense.  Note, it's only reversable because the numbers are tiny.

I'm not sure how much [RSA Secyurity|http://www.rsasecurity.com] have to do with the RSA algorithm; I assume they either hired the inventors and/or bought the name.


----
CategoryAlgorithm
4 pages link to RSA:
Last edited on Wednesday, November 5, 2003 9:19:30 pm by CraigBox
Edit PageHistory Diff Info LikePages