If something can be encrypted with a public key, why can’t someone just reverse engineer the encryption using the public key to get the original data?
In: Technology
Best 1/2 answered by an example:
You want to trasmit the letter A disguised as the number 1.
You broadcast the number 22.
Your public key is 3. Anyone who has your public key can quickly figure out that the real message is 22 – (7 times * Public Key 3) = 1 == Letter A.
Your private key is actually 7. So to encrypt your message, you would have gone 22 – (Private Key 7 * 3 times) == 1 == A
The key to notice: The real message is the remainder of division, NOT the transmitted number itself.
When taken to very large numbers, the number of possible private keys to a public key is so high that it is practically unguessable.
Note that if you transmit 43 the end results are the same: 43 divided by 7 leaves remainder 1, with 7 as the encryption key.
For decryption: 43 divided by 3 again yields 1.
== ANYONE can decrypt if they have your public key. Only you can encrypt: 43 / 7 yields one as remainder.
They can, it’s just *really* hard. As in *Lifetime of the universe* hard.
How the encryption works is public knowledge. It’s essentially just raising a message “m” to the power “p” (modulo N) It can be reversed by raising the resulting secret message to a different power “k” so that pk cancel each other out and you get m^1 , or just the message out.
however, if you don’t know what “k” is knowing “p” doesn’t help you. You’re stuck at guessing randomly what “k” is until you happen to guess the correct answer. Given how many numbers are candidates (billions and billions) even the fastest computers are too slow to manage the task in a reasonable timeframe, and even then you can always just make the secret keys bigger to make the task harder.
It works using two extremely large numbers. Multiplying these out gives you a third even larger number. These numbers are so huge that you have to have special maths libraries in order to handle them on a computer.
When the numbers are as big as they are, if you are given only the result, trying to work out which two numbers were multiplied together to create the total is extremely difficult without checking every possible number in between, which can take longer than the age of the universe (because the numbers used are just that large).
So what you end up with is two secret numbers that multiply out to a third public number.
With a bit of clever maths (far too clever for an ELI5), you can thus distribute the third number to anyone. Only you are likely to know the numbers that made it. But once you *know* even one number that made it, finding the other is instantaneous.
Using the clever maths, you can thus “encrypt” the message with the big number. And it’s almost impossible to decrypt. But if you have one of the numbers that started out, and you know the big number (which is given away) you can *easily* decrypt it. You’ve made a lock that’s incredibly simple to lock, yet incredibly difficult to open unless you know a secret number. With the secret number, it’s incredibly simple to open. Or, to use encryption terminology, the “public key” encrypts data, and ANYONE can know that and encrypt data. The “private” key associated with it is kept secret and only the person who needs to receive the message has it. They never give it to anyone else. And it is the only thing that can decrypt the data. Without the private key, there are just FAR TOO MANY possibilities of two numbers that might multiply out to the public key that you can’t try them all before the universe finishes.
(For example, say you chose 20 as the big number. That could be 1 x 20. or 2 x 10. Or 4 x 5. One small number gives you three possibilities. As the numbers get bigger, the number of possibilities can get insane – a number with trillions of digits will have trillions of possible factors).
It’s not *quite* that simple, but that’s the basic principle. In reality the “public” number is a mix of a small number and a big number, and the “private” number is a different mix. And both numbers are incredibly large prime numbers. But the maths is basically just that.
A x B = C.
Tell everybody C and let them use it to encrypt messages in a special way. But C alone is useless, because of the way encryption is done.
There are now so many possible A’s and B’s that multiply out to C that you can never know if you have the right one (not just trillions but trillions upon trillions upon trillions upon trillions…)
But if you happen to know A, and C is something that you’ve told everyone, then finding B is very easy. And if you make it so that you need the right A and B to unlock a message encrypted with C (using clever maths), then you’ve just invented public key cryptography.
The maths to turn this into an encryption scheme where you can’t just “guess” at A and B, and where C can never decrypt a message on its own is some of the best mathematics in the world. It’s held your bank and credit card info secure, and even military secrets, for nearly 80 years (the UK GCHQ invented PKC back after beating Enigma in WW2 but never told anyone… three Americans (RSA) discovered the exact same thing for themselves in the 70’s… we didn’t tell them that we already had it until late into the 90’s).
So, in the typical implementation of it, you will have a Certification Authority that issues and digitally signs all of the certificates. When you encrypt something with someone’s public key to send it to them, the CA checks that the public key you are using is valid and signed. If not, it will be rejected. If it is signed, the CA verifies it and sends it along, and the message is then decrypted with the other users *private* key.
It can’t be decrypted with the private key, only encrypted.
On top of that, actually breaking the encryption is incredibly difficult nearing impossible. The hashing algorithms now take hundreds of thousands of years to brute strength crack.
Think of it like a lock with two key holes. One key can lock it, one can unlock it, and the lock verifies that any key put in is a legitimate key that was issued. I send you something and lock it with the verified key you gave out to have people lock stuff, but only you have the key to unlock it.
Public key encryption relies on the fact that some math operations are more difficult than others. Multiplication is easier than division, squaring is easier than taking a square root, exponentiation is easier then taking a logarithm, etc.
In particular, it is very easy to multiply numbers, but incredibly difficult to factor them. How quickly can you factor 1147 by hand? There’s not really a fast way to do it other than just guessing every prime number until you get to the answer.
Encryption works by using extremely large prime numbers multiplied together, so large that factoring the result takes computers so long by brute force that it’s typically not worth it. It then uses some number theory properties of these numbers to generate a private key and public key, and those number theory manipulations are a pain in the butt to reverse engineer.
Certain mathematical operations are difficult to reverse.
It’s easy to take two prime numbers and multiply them. But it’s hard taking the product of that multiplication and figuring out the two original numbers. The larger the numbers, the more difficult the problem becomes, so public key mechanisms such as RSA use numbers that are hundreds of digits long.
Without going into detail, this problem (prime number factorization) along with other difficult problems (discrete root and discrete logarithm) are the basis for the RSA public key encryption.
If you want to actually know how RSA works, you can search this sub, since this question was asked many times.
Public Key encryption is used to _encrypt_ the data only. The private key is use to _decrypt_ only.
But yes, it is susceptible to Brute Force attacks, although it would typically take _a long time_.
> Confidentiality can be achieved using Public Key Encryption. In this the Plain text is encrypted using receiver public key. This will ensures that no one other than receiver private key can decrypt the cipher text.
[source](https://www.geeksforgeeks.org/public-key-encryption)
Latest Answers