Why can't you decrypt an encrypted message with just the public key? [duplicate]

Question

How does asymmetric crypto work?

For example, if you use PGP in emails, you generate a private key that is known only to you and a public key, which is available to everyone.

Is there a simple way to explain, why you need a private key and why no one can decrypt the message with just the public key?

I think of an explanation like for example with prime numbers:

• If you multiply two large prime numbers, you get a huge non-prime number with only two (large) prime factors.
• Factoring that number is a non-trivial operation, and that fact is the source of a lot of Cryptographic algorithms. (See one-way functions for more information.)
• The product of the two prime numbers can be used as a public key
• The primes themselves as a private key. So the private key is the knowledge of two very large prime numbers

for easy understanding lets take the simple example (very large) prime numbers: 3 and 5:

• private key: the knowlege of 3 and 5
• the public key is just those numbers multiplied: 15
• you cannot find out 3 and 5, so the message encrypted with 15 is ...

Here is a quite good explanation already, but it is not clear enough:
Is there an intuitive explanation as to why only the private key can decrypt a message encrypted with the public key?

Can you please add an example with those numbers?

Answer 1

I stumbled onto this great write up by Cloudflare a while ago as I was trying to understand Elliptic Curve Crypto better. It however starts of with some background on Public Key Cryptography followed by a detailed explanation and example of RSA key pair genaration AND how those keys (smallish primes) are used to encrypt a basic message. I suspect you will find that example answers some of your questions.

Specifically refer to the sections titled "The dawn of public key cryptography" and "A toy RSA algorithm".

All subsequent sections deal with ECC and go into a fair amount of detail (a great article on the whole).

Edit: If you tinker with the values in the example it should illustrate why the mathematics would not allow you to decrypt a message using the public key.

Answer 2

Symmetric encryption works with a single key because the function that is used to encrypt/decrypt is symmetric: f(f(x)) = x. In asymmetric encryption, you have two functions that inverse each other (called inverse functions). You get security only from the fact that only one of these functions is public, and the other one is hidden.

To make it more practical, we set functions (crypto algorithms) that are always known but are instantiated with a parameter (the key) in a large input space. So, there is a space of possible functions once the key is set, and they have only one inverse function in the other set of inverse functions.

You set a public key parameter for the encryption function and then there is only one possible private key parameter that would make the decryption function an inverse of the encryption function. Alternatively when you want to sign a message, you use the private key parameter for the encryption function (applied on a hash of your message) and only the public key parameter will make the decryption function the correct inverse.

Since the functions are known to everyone, we must protect the secret parameter. It must be very hard to guess the private parameter from the public one, which is why functions that are computationally expensive are used to build pairs of keys that maintain the inversion of crypto functions. Any arithmetic operations that are easy to perform in one way and hard to perform the other way around allow you to build such a pair, and you can then build inverse functions that can be instantiated with this pair of keys.

Answer 3

Here is a very basic analogy. Modular exponentiation is far more complex, but say we have two numbers.

If I have one number (Say, 1537) and I divide it by another number (say, 3) and I said "find the remainder", that would be very easy. You would simply divide 1537/3 with the remainder of 1.

However,, if I said "the remainder is 4 and the divisor is 6. Find the number." that would be nearly impossible without trial and error. It could be 4, 10, 16, 22, 28, etc...

Answer 4

In the case of RSA, the key element is modular exponentiation.

Modular means that you are doing all computations modulo a given integer n: whenever you add, subtract, or multiply integers together, you then do a division of the result by n, and you keep only the remainder.

For instance, if you multiply 8 with 11 modulo 15, you first get 8×11 = 88, and 88 is equal to 5×15+13. The remainder of the division of 88 by 15 is then 13. Therefore, we say that the product of 8 by 11 modulo 15 is 13.

A lot of properties of addition and multiplication on integers also work on modular integers. E.g. you still have distributivity: a(b+c) = ab+ac for all integers a, b and c. Some properties are not maintained, in particular modular integers have no order: none can be said to be greater or lower than any other.

Exponentiation is about doing many multiplications. To make things simple: with RSA, there is a modulus n. Given an integer x modulo n, everybody can compute x₃_ modulo n: just multiply x with itself, then again, and do the divide by n to keep the remainder. Thus, computing the cube of an integer is feasible with knowledge of n alone. The reverse operation, i.e. computing a cube root, appears to be much harder: we have no idea how it could be done, except if we know the prime factors of n, in which case it becomes easy again.

So there you have it: you encrypt by computing the cube, you decrypt by computing the cube root. The encryption requires knowledge of the public part (n) only, decryption needs knowledge of the private part (the factors p and q).

For instance, with n = 15, the encryption of x = 7 is 13 (because 7×7×7 = 343 = 22×15+13).

An important point to notice is that modulo 15, every value is a cube of some other value:
  0³ = 0 mod 15
  1³ = 1 mod 15
  2³ = 8 mod 15
  3³ = 12 mod 15
  4³ = 4 mod 15
  5³ = 5 mod 15
  6³ = 6 mod 15
  7³ = 13 mod 15
  8³ = 2 mod 15
  9³ = 9 mod 15
  10³ = 10 mod 15
  11³ = 11 mod 15
  12³ = 3 mod 15
  13³ = 7 mod 15
  14³ = 14 mod 15

Of course, n = 15 is a very small modulus which allows for trying out all values. With a 300-digit integer, such enumeration would be... more difficult.

(Note: I am describing things with cubes and cube roots, but in all generality, RSA uses a public exponent denoted e, which is not necessarily equal to 3. e = 3 is a valid and efficient choice, which works as long as neither p-1 or q-1 is a multiple of 3, where p and q are the prime factors of n.)

See also this answer.

Answer 5

One way to look at public / private key-pairs is to view it as yin and yang.

The yin can encrypt things that only the yang can decrypt.

At the same time

The yang can encrypt things that only the yin can decrypt.

This is used by public key cryptography

• We publish our public keys.
• We keep our private keys private.
• We can send messages that only the designated receiver can decrypt.
• We can verify signatures of senders that only the authorised sender can create.

Note 1: The PGP algorithm documented at Wikipedia makes it clear that both symmetric and asymmetric keys are used in tandem to actually implement the encryption / decryption.

Note 2: The definitions above such as authorised sender, designated receiver etc are backed by processes to try to ensure the parties involved are correct but on the internet anyone may be a dog and any communication, private key or endpoint may also be compromised.