Here is how the
RSA encryption
algorithm works. You can use the tools above to perform the necessary
calculations.
Generating keys
- 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.)
- Multiply p and q. Call their
product n.
- Multiply
(p − 1)(q − 1). Call this
product φ (this is the Greek letter phi).
- 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.
- 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.
- 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.
- 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
- To encrypt a message to someone, first get their public key from them. This
will be a pair of numbers, n and e.
- 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.
- 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
- Let M be the message you receive. Your private key is a pair of
numbers, n and d.
- Compute Md (mod n).
Call this number m.
- Convert the number m back into a message.