Comment on With public key cryptography, why can't someone decrypt a message using the public key?
OmegaMouse@pawb.social 7 months agoBut 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?
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.
philoko@ani.social 7 months ago
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.
OmegaMouse@pawb.social 7 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.
hikaru755@feddit.de 7 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@lemmy.world 7 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
howrar@lemmy.ca 7 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.