See below for a description of the RSA algorithm.

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

- 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.)

- For maximum security, they should be as large as possible, and they should
have
- 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.

- It’s a good idea not to make
- 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`x``y`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.

- A multiplicative inverse of a number
- 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.

- 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
`m`^{e}(mod`n`). Call this number`M`. Send`M`to the other person.- The number
`m`^{e}(mod`n`) is the remainder that is left when`m`^{e}is divided by`n`.

- The number

- Let
`M`be the message you receive. Your private key is a pair of numbers,`n`and`d`. - Compute
`M`^{d}(mod`n`). Call this number`m`. - Convert the number
`m`back into a message.