# Why is a public key insufficient to decrypt a message?

I'm curious about how E2EE encryption works, but the high-level descriptions I've been able to find aren't quite as clear as I'd like them to be. My current understanding is as follows:

Suppose one party, Alice, wishes to send a secret message to another, Bob. They both have "public" and "private" keys. Alice uses Bob's public key to encrypt her message, which is only decryptable using his private key.

This leads me to imagine that the public key basically specifies some kind of algorithm that Alice will need to run on the message before sending it, to make sure nobody but Bob will know what it says. But couldn't a third party, Claire, just use Bob's public key to determine exactly what algorithm Alice ran on her message and reverse those steps on Alice's encrypted message to determine what it said, with no private key involved? Why can you do this process one way with just the public key but not the other?

Put in other words, what information does the private key contain that the public key doesn't?

To give some idea of the level of depth I'm hoping for an answer in, I have a mathematical background but (obviously) no particular knowledge of cryptography.

• It's hard to give a generic answer. I suggest you read about how RSA encryption works, there's a lot of material about it on the internet. – Conrado Apr 12 at 23:52
• Start from here Explaining RSA to non-scientists – kelalaka Apr 13 at 0:10
• The whole idea of public / private keys is that the operation with the public key requires the private key to reverse it. The technicalities (the mathematical problem) that public / private schemes rely on depends on the algorithm. There is the RSA problem, the DL problem etc. For RSA, it contains the private exponent (and / or the CRT parameters required to calculate the private exponent). – Maarten Bodewes Apr 13 at 2:22

But couldn't a third party ... reverse those steps?

Simply said - no, it is impossible to reverse those steps. (this is true under certain conditions, how the keys are generated, etc.)

Why not? One of reasons is that RSA uses modular arithmetic. All operations are done using some modulo. If you know that $$X mod A = B$$, can you find the X? There are unlimited solutions: X = B, X = A + B, X = 2A + B, X = 3A + B, etc. In the reality it is more complex, like $$X^{C} mod A = B$$. We can say that such operation is not (easily) reversible.

For further reading see the link suggested by @kelalaka. When you have then further questions, welcome.

You cannot invert algorithmic steps in general. To simplify things, suppose you have a function $$f:\{0,1\}^n\to\{0,1\}$$ and suppose you know the algorithmic steps to evaluate $$f$$. Now, let's say that you know that the output is $$1$$ and you are looking for an $$x$$ such that $$f(x)=1$$.

This is probably the most studied problem in complexity theory it is called the satisfiability problem and it is NP-Complete, meaning, the best known algorithms to solve it run in time exponential in $$n$$.