RSA

From InfoAnarchy
Jump to: navigation, search

See also: Cryptography

http://www.rsa.com

  1. A successful public-key cryptosystem that generates two keys, one public and the other private. The patent for RSA expired recently. Named for its authors Rivest, Shamir, and Adleman.
  2. A company RSA Inc. that specializes in security and cryptography products, including the RSA cryptographic library.

The RSA algorithm is as follows:

  • Alice chooses two large prime numbers, <i>p</i> and <i>q</i>.
  • <i>N</i> is then defined to be <i>p&#8201;q</i>, and <i>m</i> is (<i>p</i>-1)&#8201;(<i>q</i>-1).
  • Alice now selects two numbers <i>e</i> and <i>d</i> such that <i>e</i>&#8201;<i>d</i>&#8201;&#8801;&#8201;1 mod <i>m</i>. (Often, <i>e</i> is simply chosen to be 3 or 65537, and <i>d</i> is computed appropriately.)
  • Alice can now publish her public key (<i>N</i>,<i>e</i>), while keeping her private key (<i>N</i>,<i>d</i>) a secret.
  • Now, if Bob wishes to send Alice an encrypted message <i>M</i>, he computes <i>C</i>=<i>M</i>^<i>e</i> mod <i>N</i>. <i>C</i> is the encrypted text and cannot (as far as we know) easily be decrypted without knowledge of the decryption key.
  • Alice, however, upon receiving <i>C</i>, can easily decrypt it, by computing <i>M</i>=<i>C</i>^<i>d</i> mod <i>N</i>. <i>M</i> will be the same as Bob's <i>M</i> above, the original message.

There are a number of pitfalls to be wary of when implementing the RSA algorithm, so it is unwise to do so exactly as described here. Instead, unless you know what you're doing, use the version in OpenSSL, GNU TLS, or another cryptographic library.

Related Links: