With public key cryptography, why can't someone decrypt a message using the public key?
With public key cryptography, why can't someone decrypt a message using the public key?
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!
If you turn a sausage machine backwards, you don't get a pig coming out the top.
If I add a dozen numbers together, there's only one total.
But if I only have that total, there's no way to tell what the original dozen numbers were.
Same kind of principle.
You can brute-force it, but when it comes to the product of stupendously large primes, it would take until the heat death of the universe to do so, by which time you probably don't care any more.
Public key cryptography is a bit like one of those blue public mailboxes. There is an input slot where anybody can drop something in, but only people with the private key can open the door to get things out. You can't run that input in reverse because gravity and the mechanics of the slot do not allow that to happen. The same thing exists mathematically for public key cryptography.
Basically, asymmetric key cryptography is based on the idea that some algorithms are one-way roads. Or trap doors - falling down is easy, climbing up is much, much harder.
For a simple example, take adding numbers. I've got a thousand numbers, I add them up, and hand you the sum. Will you be able to find the thousand numbers I have from that sum? Probably not. The math involved in the actual cryptography is a bit more complex, but the principle holds.
Look at the Diffie Helman scheme, with the example used in the Wikipedia page.
- Alice and Bob agree in public, for everyone to see, that they're gonna start with p=23 and g=5.
- Alice has a secret key 4, and doesn't tell anyone (not even Bob). She plugs her secret into the formula g^secret mod p, or 5^4 mod 23. 5^4 is 625, and dividing 625 into 23 gives a remainder of 4. So she tells Bob in public that she derived the number 4 from her secret.
- Bob has a secret key of 3, does the same thing, and calculates 5^3 mod 23, which results in the number of 10, tells Alice.
The magic of this scheme is that taking each side's result and applying the same secret gets to the same final result. 10^4 mod 23 turns out to be the exact same number as 4^3 mod 23. So both sides get to the secret shared key 18, without disclosing that their secret numbers were 4 and 3, respectively.
But if you try to drive the secret key from the information publicly exchanged, you'll basically have to try each number until you get to the right one. It's inefficient, and basically impossible to do once you're using very large integers (300+ digits long).
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.
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.
Surely a public key contains a set of instructions
Not exactly. But that is not the point.
and anyone could just run those instructions in reverse to decrypt a message?
No, you can't, and that's exactly the great thing about the invention of public key crypto (or asymmetric encryption in general).
You can encrypt something with a private key, and then you need the public key to decrypt it. That is used for a digital signature.
You can encrypt something with a public key, and then you need the private key to decrypt it. That is used for a private message to one person.
It think the common analogy is a padlock and a key. One party gets the padlock and the other one the key. Now with the padlock you can just lock the box but not open it. And with the key you can just unlock and open the box. That's assymetric. You hand out padlocks (your public key) to everyone, but keep the key (your private key).
The maths behind that is a bit difficult to explain but not that difficult. I think it's about one-way functions that are easy to calculate in one direction and impossible to solve the other way around. There are several ways to do it. Like the old approaches with prime numbers. It's easy to multiply two prime numbers. But given an arbitrary large number, it's difficult to tell which prime numbers it consists of.
So using the formula in that guide, you get a numerical value for O. But surely someone else could follow the same process and also get the same answer? Unless the primes change each time? But then how would the sender and receiver know the way in which the values change?
This post on Stack Overflow does a good job of explaining the issue.
I'm not sure I get your question... Sure other people can also follow the same process and encrypt stuff to you. They can also do the calculations with your private key and arrive at the same result, sure. But the calculation involves your private key. Your secret. If that's known to someone, they can do the calculations. In the example you need to keep the "53" a secret and give the "221" to other people. Everyone with the "53" can decrypt. Everyone with the "221" can encrypt. It's just with the "221" you can't decrypt. That part of the calculation needs people to put in the other number.
I liked this YouTube video about Diffie-Hellman key exchange [start at 2:25] that explains the concept using color mixtures.
The Wikipedia page explains it pretty well: