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!

  • @[email protected]OP
    6•9 months ago

    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.
    • @[email protected]
      6•9 months ago

      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.

    • @mumblerfish
      5•9 months ago

      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

    • @[email protected]
      3•9 months ago

      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.