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:
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.
Well, you use “padding” to solve those things. Like if you type “hello”, your implementation of the whole algorithm should do something like: take the string, add some random string that is tagged in some way, and then encrypt. At decryption, you get a string with some random stuff in it, but you filter the tag and return only the message. Like “hello” -> “[trash]kfkidkeb[/trash] hello”, add and remove the “[trash]” block, before encryption and after decryption, respectively
The same word will be encrypted the same way each time, and that’s actually the basis of one of the known attacks on LLMs like ChatGPT. They send responses back one “word” at a time, so someone who’s snooping can easily figure out what it’s saying from the encrypted messages. The exploit doesn’t affect Bard because it sends larger chunks of text at a time.
Encryption uses pairs of primes, where you know the resulting number, but not the primes used to comprise that number. You can calculate the result given the primes very quickly, but given the result it’s very slow to figure out what the primes were. This asymmetry is the key to this kind of encryption.
Given enough computational power you can do it, that’s why we’ve moved on to more complex algorithms and bigger keys throughout the years to keep up.
Look at it more like this. Say I tell you to pick any number, square it, and then add 5. Say I did this and my answer was 41. What was my original number? 90% of people will answer 6, but my answer was -6. Now only doing that once isn’t hard, but basically it’s because the inverse of the function is not a function that I can’t always get back to it. Now do that a few thousand different ways in the same problem and good fucking luck.
While it’s not what is happening as it’s using pairs of primes, it’s an easy way to explain there’s not always a way to get to something from an equation.