# How can a message encrypted with the public key be decrypted with the private key?

I've been reading about encryption and have a basic understanding of the concept. What I don't understand, however, is how a calculation with one key can result in a number that, through calculation with a different key, leads back to the same number you started with. Are they doing the same calculation (what I mean by this is for example: first multiplying the number with the first key, then dividing it with the second one)? If anyone could in a simple way describe how this works to me; and add some examples with actual numbers in them as well perhaps; that'd be be wonderful.

Perhaps a simplified example or two might help you intuitively understand the concept.

Let's say you want to let your little brother and sister encrypt messages so that either of them can encrypt any message, but only you can decrypt them. To keep things simple, let's say that the messages are simply numbers from $1$ to $10$.

Your siblings have been recently learning about addition in school, so you come up with a simple encryption scheme based on that. Specifically, you tell your brother and sister to encrypt their messages like this:

1. add $7$ to the number to be encrypted, and
2. take only the last digit of the result.

Your brother and sister do know about subtraction, and they're smart enough to realize that they could try to decrypt a message by just subtracting $7$ from it. But when they try it, they realize that it only works when the encrypted message is $8$ or $9$ — otherwise, they're not quite sure what to do, since they haven't had negative numbers at school yet (and zero as a number is still kind of an advanced concept for them, too).

You, of course, know how to decrypt the messages, even without using any negative numbers at all! You just add $3$ to the encrypted message, and again take only the last digit (or $10$, if the last digit is $0$!). This works because $3+7 = 10$, and adding $10$ to a number leaves its last digit unchanged.

Eventually, your brother and sister work this out on their own, so you have to come up with a better encryption scheme. Fortunately, by this time your siblings have learned how to multiply numbers, so you base your new scheme on that. Specifically, you tell them to:

1. multiply the number to be encrypted by $7$,
2. if the result is bigger than $10$, subtract the first digit from the second, and
3. if the result is now negative, add $11$.

(Steps 2 and 3 are, of course, equivalent to reducing the result modulo $11$, but explaining it like that would be a little too advanced for your little siblings — they've only just started learning about division!)

Again, your siblings quickly come up with the idea of trying to divide the encrypted numbers by $7$, but this works even worse than subtraction did with the first scheme — sure, they can calculate $7 \div 7 = 1$, but none of the other numbers between $1$ and $10$ are divisible by $7$. You, of course, know the trick for decrypting the messages — you just multiply them by $8$, and then repeat steps 2 and 3 above (i.e. reduce the result modulo $11$).

This trick works because $8 \times 7 = 56 = 5 \times 11 + 1$. Thus, for any number $x$, $8 \times 7 \times x$ equals $5 \times 11 \times x + 1 \times x$; and when you take the remainder modulo $11$, you're just left with the original number $x$! In other words, $8 \times 7 \equiv 1 \pmod{11}$, so $8$ is the modular multiplicative inverse of $7$ modulo $11$.

This new scheme is a lot harder for your siblings to break, because their grade school math curriculum doesn't really cover modular arithmetic. Eventually, they do come up with a brute force solution — they just write down every number from $1$ to $10$ and its encrypted result, and use this table to look up which number each encrypted message corresponds to:

$$\begin{array}{lrrrrrrrrrr} \text{Plaintext:} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \text{Encrypted:} & 7 & 3 & 10 & 6 & 2 & 9 & 5 & 1 & 8 & 4 \\ \end{array}$$

But you just change your scheme to work on two-digit numbers instead, using $101$ as the modulus. It's a bit more work for you, since you now have to multiply by $29$ to decrypt, but at least your siblings are too lazy to compile a 100-element table. As long as they choose their messages to be large enough (so that multiplying by $7$ gives a result over $100$) and don't repeat a message whose encryption the other one already knows, this means they can't easily decrypt each other's encrypted messages.

You even briefly think about increasing the modulus to $1{,}001$, but realize that you'd have to choose a different public multiplier, since $1{,}001 = 7 \times 11 \times 13$, and so $7$ is not invertible modulo $1{,}001$. You kind of like the number $7$, but in this case, $6$ or $8$ would work better. Or you could just skip all the way to $10{,}001$, which has no small factors.

The multiplicative encryption scheme works great (at least with a large enough modulus to resist brute force tabulation), until your sister one day stumbles across a web page about the extended Euclidean algorithm. Being clever, she realizes that she can use it to quickly calculate the modular inverse for any public multiplier, and thus read any encrypted message, no matter what the public multiplier or the modulus is!

Suddenly, you need to come up with something even more secure. The obvious next step would be to replace the multiplication with exponentation, something like this:

1. raise the number to be encrypted to the $e$-th power, and
2. take the remainder of the result modulo $n$.

You're hoping that, if you choose the right exponent $e$ and modulus $n$, you might be able to find another exponent $d$ such that raising the encrypted number to the $d$-th power modulo $n$ would just happen to "cancel out" the $e$-th power, leaving you with the original number. In other words, you'd need a modulus $n$ and two exponents $e$ and $d$, such that $(x^e)^d \equiv x \pmod n$ for all numbers $x$.

It's not exactly obvious that such pairs of exponents should exist, but you're feeling optimistic — after all, it worked for addition and multiplication, so why not exponentiation too? In fact, you remember a number theory class you took in college mentioned something about modular multiplicative groups that might've been relevant.

Looking through your notes, you realize that, since $(x^e)^d = x^{e \times d}$, you really just need to find a number $\lambda$ such that $x^{\lambda+1} \equiv x \pmod n$ for all $x$; then adding or subtracting multiples of $\lambda$ from the exponent won't change the result, and so you can simply use the same extended Euclidean algorithm you used to generate the private keys for the previous encryption scheme (and which your sister used to break it!) to find $e$ and $d$ such that $e \times d \equiv 1 \pmod \lambda$.

You can even choose $e$ freely (as long as it doesn't share a factor with $\lambda$!) to make the calculations easier for your siblings. For example, letting $e = 3$ might be a good choice. Of course, the resulting secret exponent $d$ probably won't be so convenient, but that's all right — you know an efficient algorithm for exponentiation modulo $n$.

Your notes even mention that the smallest such $\lambda$, for a given modulus $n$, is given by Carmichael's reduced totient function. (Euler's totient function $\phi$, which is always a multiple of $\lambda$, could of course be used, too.)

But there's a problem! On one hand, you need to know $\lambda$ to calculate $e$ and $d$ — but if anyone else (like your too-clever-by-half sister) could figure it out, they could break the encryption! So you somehow need to choose the modulus $n$ so that you can easily calculate $\lambda(n)$, but nobody else can.

Obviously, choosing a prime modulus like $101$ would be right out (never mind that your siblings have had programming classes at school by now, and could easily write a program to calculate a 100-element lookup table), since $\lambda(n) = n-1$ for prime $n$. But what if you took two random primes $p$ and $q$, and multiplied them together? Then $\lambda(p \times q)$ would just be the least common multiple of $p-1$ and $q-1$, which is easy to calculate. But you're pretty sure that, given just $n = p \times q$, even your sister won't find it easy to break $n$ back into its prime factors, and so won't be able to calculate $\lambda$.

And that's basically where we are today with RSA.

As long as we choose the prime factors $p$ and $q$ of the modulus $n$ to be large enough (and they do need to be quite large, at least several hundred digits long, to resist the most advanced factoring algorithms and the most powerful computers) and make sure that our messages don't repeat and aren't too small (to resists brute force attacks and simple attempts to take the $e$-th root; this is generally achieved by padding the messages appropriately), there's no known efficient way to calculate $x$ from $x^e \bmod n$.

That is, unless you happen to know the secret number $d$, chosen so that $e \times d \equiv 1 \pmod \lambda$, in which case you can just raise the encrypted message to the $d$-th power modulo $n$, and obtain $(x^e)^d = x^{e \times d} = x^{k\lambda+1} \equiv x \pmod n$.

• I love the progression in your example story, this is very helpful. – jeremy radcliff Apr 27 at 9:37

Theorem: Let $gcd(a,n)=1$ and $\phi(n)$ be Euler's totient function, then $a^{\phi(n)} \pmod n=1$.

One of this famous methods for encrypting is RSA. In this method we use above theorem.

Let $e,n$ are public and $\phi(n) , d$ are private such that $e\cdot d =1\pmod {\phi(n)}$$(e\cdot d=1-t\cdot \phi(n)). For encryption we have:$$\operatorname{Enc(M)}=M^e \pmod n$$Also for decryption we have:$$\operatorname{Dec(c)}=c^d \pmod n$$Now suppose$c=M^e\pmod n$, so$c^d=M^{e\cdot d}=M^{1-t\cdot \phi(n)} =M\cdot {(M^{\phi(n)})}^{-t}\pmod n=M\$