RSA tools

See below for a description of the RSA algorithm.

Primality test: (using the Miller–Rabin primality test)

Find the next prime number after (using the Miller–Rabin primality test)

Multiplication: ×

Greatest common divisor: gcd(, ) (using the Euclidean algorithm)

Multiplicative inverse of (mod ) (using the extended Euclidean algorithm)

Exponentiation: ^ (mod ) (using exponentiation by squaring)

Here is how the RSA encryption algorithm works. You can use the tools above to perform the necessary calculations.

Generating keys

  1. Choose two different prime numbers. Call them p and q.
    • For maximum security, they should be as large as possible, and they should have almost the same number of digits. Also, if you choose larger numbers for p and q, then people can send you longer messages. So, for example, a 10-digit prime and an 11-digit prime might be good choices. (In real life these primes are usually chosen to have 150 digits or more.)
  2. Multiply p and q. Call their product n.
  3. Multiply (p − 1)(q − 1). Call this product φ (this is the Greek letter phi).
  4. Find an integer greater than 1 but less than φ that is relatively prime to φ, and call it e. In other words, find e such that 1 < e < φ and gcd(e, φ) = 1.
    • It’s a good idea not to make e too small. (For example, e = 3 is probably too small.) But e doesn’t have to be really big; a number with three or four digits should be fine.
  5. Compute the multiplicative inverse of e (mod φ), and call it d.
    • A multiplicative inverse of a number x is another number y such that the product xy equals 1. In ordinary arithmetic, this is the reciprocal of x; for example, the multiplicative inverse of 2 is 1/2. In modular arithmetic (mod φ), when we say “1” we really mean a number that leaves a remainder of 1 after it is divided by φ. So, for example, the multiplicative inverse of 5 (mod 7) is 3, because 5 × 3 = 15, and 15 leaves a remainder of 1 when it is divided by 7.
  6. Your public key is the pair of numbers n and e. Give this pair of numbers to anyone who wants to send you a message.
  7. Your private key is the pair of numbers n and d. You will use these numbers to decrypt messages that are sent to you. Keep the number d secret!

Never let anyone else know the numbers p, q, φ, or d. If anyone else learns any of these numbers, they can break the code! But without knowing these numbers, the only way to break the code (as far as anyone knows) is to factor the number n in order to learn the original prime numbers p and q. Factoring n is really hard to do if n is very large, and this is what makes RSA encryption secure.

Encrypting a message

  1. To encrypt a message to someone, first get their public key from them. This will be a pair of numbers, n and e.
  2. Turn your message into a number between 2 and n − 2. Call this number m.
    • You can use any method you want to convert your message into a number, as long as the other person knows how to convert it back. For example, a simple substitution cipher works well, with A = 01, B = 02, …, Z = 26; so HELLO would be 0805121215, which is the same as 805121215 (the zero at the beginning doesn’t matter). You can use 00 for a space.
  3. Compute me (mod n). Call this number M. Send M to the other person.
    • The number me (mod n) is the remainder that is left when me is divided by n.

Decrypting a message

  1. Let M be the message you receive. Your private key is a pair of numbers, n and d.
  2. Compute Md (mod n). Call this number m.
  3. Convert the number m back into a message.

Zif Yoip