RSA Encryption

In one sentence: RSA lets anyone lock a message with a public key while only the owner can unlock it with a private key, because undoing a product of two secret primes is very hard.

$c = m^{e} \bmod n, \qquad m = c^{d} \bmod n$

Read it out loud: “c equals m to the power e, mod n. To decrypt, m equals c to the power d, mod n. Here c is the ciphertext, the locked number, and m is the message. The letter n is the product of two secret primes, p and q. The exponents e and d satisfy the rule that e times d is one more than a multiple of phi of n, where phi of n is the totient.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Powers of ten, like $10^{30}$: A power of ten is 10 multiplied by itself a set number of times. $10^{30}$ means 1 followed by 30 zeros. A number such as $6.6 \times 10^{30}$ means 6.6 with the decimal point moved 30 places to the right, which gives a number with 31 digits. A minus sign in the exponent means divide, so $10^{-3} = 0.001$ .
Powers, like $65^{17}$: A small raised number is an exponent, and it says how many times to multiply a number by itself. So $65^{17}$ means 65 multiplied by itself 17 times. The answer is a very large number, so computers reduce it along the way, as the example shows. The raised number $e$ in the formula works the same way.
Prime numbers: A prime number is a whole number greater than 1 that can be divided evenly only by 1 and by itself. The first few are 2, 3, 5, 7, 11 and 13. The numbers 61 and 53 are both prime. Multiplying two primes is easy, but splitting a large product back into its two primes is very hard for ordinary computers.
Remainder and $a \bmod n$: The notation $a \bmod n$ means the remainder after dividing $a$ by $n$ . For example, $17 \bmod 5 = 2$ , because 17 is 3 groups of 5 with 2 left over. RSA does all of its arithmetic this way, and after each reduction the numbers stay smaller than $n$ .
Public key and private key: A public key is a pair of numbers that anyone can use to lock, or encrypt, a message. A private key is a related secret that only its owner has, and it is the only thing that unlocks the message. Both keys are made together, and in practice the public key does not reveal the private key.
Euler’s totient $\varphi(n)$: The totient $\varphi(n)$ counts the whole numbers from 1 to $n$ that share no factor with $n$ . For $n = pq$ , where $p$ and $q$ are different primes, the count is $(p-1)(q-1)$ . Every multiple of $p$ and every multiple of $q$ is excluded, and the rest are counted. The private exponent is calculated from this number.

What each symbol means

Symbol	Meaning
$c$	The ciphertext, the scrambled whole number that is sent instead of the message. It is a whole number between 0 and $n - 1$ . It has no unit, because it is a code number and not a measured amount.
$m$	The message, written as a whole number between 0 and $n - 1$ . Text must first be turned into numbers, for example by giving each letter a number, before it can be encrypted. The message has no unit.
$e$	The public exponent, a whole number shared with everyone. It is the power the message is raised to when someone locks it. Real systems often use 65537, and the example uses 17. It has no unit, because it is a power and not a measured amount.
$d$	The private exponent, a whole number that only the owner knows. It is the power used to unlock the message. It is chosen so that raising to $e$ and then to $d$ returns the original message, which is why the two exponents are linked.
$n$	The modulus, the product of two secret primes, $n = pq$ . It is public, and it is part of both keys. Its size sets how hard the lock is to break, because a bigger $n$ is much harder to split back into its two primes.
$\bmod n$	The remainder after dividing by $n$ . Every power in RSA is reduced in this way, so the numbers stay between 0 and $n - 1$ . It has no unit, because it is a leftover count.
$p, q$	Two different secret prime numbers, $p = 61$ and $q = 53$ in the example. Their product is $n$ . Anyone who learns $p$ and $q$ can compute the private key, so these two primes must stay secret.
$\varphi(n)$	Euler’s totient of $n$ , the count of whole numbers from 1 to $n$ that share no factor with $n$ . For $n = pq$ it equals $(p-1)(q-1)$ . The private exponent $d$ is chosen so that $ed$ leaves a remainder of 1 when divided by it.

The formula piece by piece

$m^{e}$: The message raised to the power $e$ , which means multiplying $m$ by itself $e$ times. With $m = 65$ and $e = 17$ , this is $65^{17}$ , a number with 31 digits. That is far too large to work out by hand, so the next piece keeps it small.
$m^{e} \bmod n$: The same power, with the remainder after dividing by $n$ taken. Every multiplication is reduced mod $n$ , so the numbers stay small. With $n = 3233$ , the result is always a whole number from 0 to 3232.
$c = m^{e} \bmod n$: Encryption in one step: lock the message by raising it to the public exponent and taking the remainder mod $n$ . The result $c$ is the ciphertext that is sent. Anyone with the public key can do this step.
$c^{d} \bmod n$: Decryption: raise the ciphertext to the private exponent and take the remainder mod $n$ . Only the owner, who knows $d$ , can do this step, and it gives back the original message.
$c = m^{e} \bmod n, \qquad m = c^{d} \bmod n$: The whole formula in one sentence: encrypt by raising the message to the public power $e$ and taking the remainder mod $n$ , and decrypt by raising the ciphertext to the private power $d$ and taking the remainder mod $n$ .
$ed \equiv 1 \pmod{\varphi(n)}$: The rule that links the two exponents, a standard way textbooks state it. It says that $ed$ leaves a remainder of 1 when divided by $\varphi(n)$ , so $ed$ is one more than a multiple of $\varphi(n)$ . This rule is what makes decryption return the message.

What the formula is doing, and why

RSA is a public-key method. Each person has a public key, which anyone may use to encrypt a message, and a private key, which only the owner keeps. The public key is the pair $(n, e)$ , and the private key is the pair $(n, d)$ . A message is a whole number $m$ smaller than $n$ . Encryption turns it into $c = m^{e} \bmod n$ , and the result $c$ is what gets sent.

Why does decryption give the message back? Decryption computes $m = c^{d} \bmod n$ . The exponents were chosen so that $ed$ is one more than a multiple of $\varphi(n)$ , which means $ed = 1 + k\varphi(n)$ for some whole number $k$ . Raising $m$ to the power $ed$ is therefore the same as raising it to the power 1, times a power of $m^{\varphi(n)}$ . Euler’s theorem says $m^{\varphi(n)}$ leaves a remainder of 1 when divided by $n$ , for messages that share no factor with $n$ , and a short extra argument covers the rest. So the leftover is $m$ again.

Why is it secure? If someone can split $n$ back into $p$ and $q$ , they can compute $\varphi(n)$ and then $d$ , and the lock opens. Multiplying two primes is easy, but splitting a large product into its prime factors is very hard for ordinary computers. Real keys use primes of hundreds of digits, and the toy numbers in the example are far too small to protect anything. Real systems also add random padding to each message before encryption, which this page leaves out.

Why reduce at every step? A power like $65^{17}$ is much too large to compute in full. Software reduces mod $n$ after each multiplication, so the numbers stay below $n$ at every step. This method is called modular exponentiation, and it is what makes RSA practical even with very large keys.

An everyday picture

Think of a padlock that anyone can snap shut, but only the owner can open. Anyone can close the lock, which is the public part, because the public key is shared freely. The owner alone knows the secret combination, which is the private key. The math behind the lock is multiplying two secret primes, which is easy to do but very hard to undo.

Worked example: Toy RSA with p = 61 and q = 53

Imagine a friend wants to send you the secret number $m = 65$ . For this example we use two small primes, $p = 61$ and $q = 53$ . Your public key is $(n, e) = (3233, 17)$ , and your private exponent is $d = 2753$ . Your friend encrypts 65 with the public key, and you decrypt the result with your private exponent. These numbers are far too small for real security, but they show every step.

Multiply the two secret primes to get the public modulus. Both $p = 61$ and $q = 53$ are prime, because nothing else divides them evenly. Their product is $n = pq = 61 \cdot 53 = 3050 + 183 = 3233$ . This number is public, so anyone can see it.
Compute the totient, which the private key depends on. $\varphi(n) = (p-1)(q-1) = 60 \cdot 52 = 3120$ . Subtracting 1 from each prime and multiplying the results counts the numbers from 1 to $n$ that share no factor with $n$ . Only the owner knows $p$ and $q$ , so only the owner can compute this number.
Check the exponents. Multiply $e \cdot d = 17 \cdot 2753 = 46801$ . Then $15 \cdot 3120 = 46800$ , so $46801 = 15 \cdot 3120 + 1$ . This means $ed$ leaves a remainder of 1 when divided by 3120, which is the rule that makes decryption work.
Encrypt the message. Your friend computes $c = 65^{17} \bmod 3233$ . The power $65^{17}$ has 31 digits, about $6.6 \times 10^{30}$ , which means 6.6 with the decimal point moved 30 places to the right. That is too large to handle directly, so the computer reduces mod 3233 along the way, and the result is $c = 2790$ .
Reduce as you go, starting with the first square. Squaring 65 gives $65^{2} = 4225$ . Dividing by 3233 leaves $4225 - 3233 = 992$ , so $65^{2} \bmod 3233 = 992$ . Each later multiplication starts from a leftover below 3233, so the numbers stay at six digits or fewer at every step.
Decrypt the message. You compute $m = 2790^{2753} \bmod 3233$ , using your private exponent $d = 2753$ , reducing at every step in the same way. The result is $m = 65$ , the original message.
Explain why the answer comes back. Decrypting undoes the encryption, so the exponent becomes $ed = 46801 = 15 \cdot 3120 + 1$ . Euler’s theorem says that $65^{3120}$ leaves a remainder of 1 when divided by 3233, because 65 shares no factor with 3233. So $65^{46801} = 65 \cdot (65^{3120})^{15}$ leaves the remainder 65.

Answer: The ciphertext is 2790. Decrypting it with $d = 2753$ returns the original message 65. These numbers are tiny, so anyone who can factor 3233 can break this key, which is why real keys are far larger.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Using the same exponent for both directions. Encryption uses $e$ and decryption uses $d$ . Swapping them returns a different number, not the message.
Using toy primes in real life. With $n = 3233$ , trial division finds the factors 61 and 53 in moments, so the key gives no secrecy. Real keys need far larger primes.
Computing $65^{17}$ in full before reducing mod $n$ . That number has 31 digits. Reduce mod $n$ at each step instead.
Using $n - 1$ for $\varphi(n)$ . For $n = pq$ , $\varphi(n) = (p-1)(q-1)$ , which is 3120 here, not 3232.

Where you will meet it

Digital certificates and signatures, which prove that a website or file came from who it claims to come from.
Secure email and file-signing tools, which often use RSA keys.
Older secure connection setups, where RSA protects a shared session key while it is sent.
Teaching public-key cryptography, since RSA is the classic first example and its steps are ordinary arithmetic.

Questions people ask

Why is it called public-key encryption?

The encryption key $(n, e)$ can be shared openly. Anyone can encrypt with it, but only the holder of the secret exponent $d$ can decrypt.

Why does RSA need two primes?

Its security rests on $n = pq$ being hard to factor. If you know $p$ and $q$ , you can compute $\varphi(n)$ and $d$ . Two large random primes keep that secret out of reach.

How big are real RSA keys?

A common size is 2048 bits. That makes $n$ about 617 decimal digits long, and each of its two primes about 309 digits long. The number of digits is found from the power of 2, because $2^{2048}$ has about $10^{616.5}$ times the size of 1, which means 617 digits.

Modulo Operation: The modulo operation gives the leftover amount after you split one whole number into as many equal full groups of another number as you can.
Euclidean Algorithm: The Euclidean algorithm finds the largest number that divides two numbers evenly, by replacing the pair with a smaller pair again and again until the remainder is zero.
Password Entropy: Password entropy is a score in bits that counts how many passwords a random generator could have made, so a higher score means guessing one is harder.