Penguin
Recent Changes

RSA is a cryptographic algorithm, named after its authors, Rivest, Shamir, and Adleman. (Also an acronym for the Returned Serviceman's Association. Ask your grandfather, if he's sober.)

This is commonly the algorithm used in PublicKeyEncryption.

Loosely described, this is how it works.

  1. Find P and Q, two large (e.g., 1024-bit) prime numbers.
  2. 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.
  3. . 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.
  4. 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.
  5. 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. 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 have to do with the RSA algorithm; I assume they either hired the inventors and/or bought the name.

CategoryAlgorithm