RSA

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

RSA is a name of a well-known cryptographic algorithm used to encrypt and decrypt digital messages. RSA stands for the last names of its inventors: Ron Rivest, Adi Shamir, Len Adleman. It is one of the most popular asymmetric algorithms, which was patented in the United States until September 2000. It relies on the difficulty of factoring very large numbers.

How it works:

  1. Choose two large prime numbers p and q and compute m = p * q (Keep in mind that m's with fewer than 256 bits can be factored at home in a few hours with free software from the Internet, and an m with 512 bits has been factored by several hundred computers in 1999, so use at least 1024 bits for m.)
  2. Compute phi = lcm((p-1)(q-1))
  3. Choose a small public exponent e so that it is greater than 1 and has no factor in common with phi
  4. Compute d so that: de = 1 mod phi
  5. Destroy p,q,phi.

m and e are the public key and d is the private key.

To encrypt Take your plaintext, turn it into a number n, and send n to the eth power mod m.

To decrypt Take the number you received, raise it to the dth power mod m, convert the result back to text.


see also cryptography, public key cryptosystem, digital signature