1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Conrado
    Commented Apr 12, 2020 at 23:52
  • 2
    $\begingroup$ Start from here Explaining RSA to non-scientists $\endgroup$
    – kelalaka
    Commented Apr 13, 2020 at 0:10
  • $\begingroup$ 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). $\endgroup$
    – Maarten Bodewes ♦
    Commented Apr 13, 2020 at 2:22

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.