I’ve been trying to get my head around this and I’ve watched a few videos but they don’t seem to specifically answer my question.
According to what I’ve found online, messages encrypted with a public key can only be decrypted with a private key. But in practice, how is that possible?
Surely a public key contains a set of instructions, and anyone could just run those instructions in reverse to decrypt a message? If everything you need to encrypt a message is stored within a public key, then how is it a one-way process?
It’s likely that I’m misunderstanding a core element of this!
AfaIk, yes, in principle one could construct the private key from the public key. However, given the current computational power, it would in practice take forever and a day, if the encryption algorithm is sufficiently strong, see e.g. the Wikipedia article on RSA
But say (simplying greatly) the public key tells my computer to multiply my text by a prime number
If the prime number is already known from the public key, then why is any computation required? To decrypt it can’t I (or anyone else) just divide by the prime? Even with a significantly more complex calculation, can’t you just work the steps back in reverse using the instructions from the public key?
As an oversimplification, RSA works by taking two huge prime numbers (the private key) and multiplying them together (the public key). You could get the private key by factoring the public key but the best way to factor a prime number is to basically just try every combination with a few tricks sprinkled in until something works which could take millions of years with modern computers. You can hoard everyone’s public key until computers can crack it in a reasonable amount of time but everyone involved will be long gone by then.
The whole point of private and public keys is to have an operation that’s easy to do one way but would take so long to reverse that it’s virtually impossible. There’s nothing stopping you trying except the time and effort involved.
Ah I think of sort of get it!
The public key is used within a function by the person sending the message, and even someone that knew the function and the public key wouldn’t be able to decrypt the message, because doing so would require knowledge of the original prime numbers which they couldn’t work out unless a computer spend years factoring the public key.
My only other bit of confusion:
- If someone used a public key to encrypt the message “Hello”, maybe it would spit out something like Gh5bsKjbi4
- If someone else sent the exact same message I assume the outcome would also be identical, and therefore it would be possible by using common phrases to work out what was sent? I could type messages like Hi, Goodbye, Hola until I got to ‘Hello’ and realised it was the same output.
- However I assume that a message like ‘Hello, how are you?’ would result in a completely different output (despite Hello appearing in both) and thus trying to work out any messages in a brute force way like this would be pointless.
Yup, you got it. Even the solution to your confusion. Good encryption algorithms are set up so that even the smallest possible change in the input (a single flipped bit) will produce a completely different result. So yeah, if you have just a small set of exact possible messages that could be sent, you can find out which one it was by encrypting it yourself and comparing your result to what was sent. But there is a super easy protection against this - just add some random data to the end of the message before encrypting it. The more, the harder it will be to crack.
