RSA

---

RSA is an asymmetric cipher developed by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT.

• Created in 1977
• most widely used public key algorithm in existence today
  • used in SSL
• based on relationships of prime numbers
  • to generate key pairs
  • security derives from the fact that it is difficult to factor a large integer composed of two or more large prime factors
• slow and computationally expensive
  • mostly used to exchange a session key
    • is a symmetric key that is only used for the duration of a single communication session

How It Works

• to create the key
  • two large random prime numbers ( and ) of approximately equal size are generated
  • two numbers are chosen so that when multiplied together the product will be the desired size
    • e.g., 1,024 bits, 2048 bits, etc.
  • and are multiplied to get
  • then multiply by Euler’s Totient for each of these primes
    • is the total number of coprime numbers
    • two numbers are considered coprime if they have no common factors
      • e.g., 7 has a coprime of 5
    • for prime numbers, coprime is always the number minus 1
      • 7 has six coprimes, so
  • then another number is selected, called
    • is coprime to
  • number is calculated that when multiplied by and modulo would yield a 1
    • i.e. find , such that
  • Thus you have public keys and and private keys and
• to encrypt
  • simply take the message raised to the power and module
• to decrypt
  • take the ciphertext raised to the power modulo