Asymmetric Encryption

Question

I understand Asymmetric Encryption works by having the private key known only to your computer, while the public key is given by your computer to any computer that wants to communicate securely with it. To decode an encrypted message, a computer must use the public key, provided by the originating computer, and its own private key.

What stops an attacker listening in from just grabbing the key which you send alongside the data? If it's not actually being sent alongside the encrypted data, then at what point does the server receive the key that it needs to decrypt?

I know it's likely an obvious answer but Cryptography is my weak spot in IT. Googling it didn't help either, the answers were just too simplified or never covered the networking side (When a key is sent, received, and by whom).

Answer 1

Your understanding of how asymmetric cryptography works is somewhat flawed. In general the public key is NOT used to decrypt anything. It is used to encrypt. The private key is used to decrypt.

There are several mechanisms to get secret communication going starting with a public/private key pair held by the server. For the most part they involve the client and server exchanging messages to establish a shared symmetric key which both use for subsequent communication.

In the simplest, but somewhat disfavoured, method the client picks the symmetric session key, encrypts it with the server's public key and sends it to the server. Since the session key is encrypted with the server's public key any observer won't be able to determine what it is.

More complex methods of establishing the session key include Diffie-Hellman Key Exchange and Elliptic-Curve Diffie-Hellman key exchange. These avoid sending any key over the network and preserve secrecy in the event of a future compromise of the server's key but involve some maths to allow both server and client to derive the same key.

In no case is the private part of a public-key pair ever sent over the network.

Answer 2

It isn't the public key that is used for decryption it's the private key.

So for example Alice sends Bob a message. That means Alice uses Bobs public key to encrypt the message and Bob uses his private key to decrypt the message.

Hopfully this was helpful just for clearification i am not a security expert.

Here is an example of such an encryption/decryption process: en.wikipedia.org/wiki/RSA_(cryptosystem)

Answer 3

With at least some asymmetric encryption algorithms, e.g. RSA, either of the keys can be used to encrypt a message and the other key will decrypt the result.

If I keep my private key secret and publish my public key, then there are two ways to communicate:

I can encrypt a message with my private key and send it to you. You can decrypt it with my public key. Anyone who intercepts the message can also decrypt it with my public key. So what have I achieved? Well, you and everyone else know that only I have the private key, so for the decryption to have worked, I must have been the writer of the message. In addition, since modification of the encrypted message would cause decryption to fail, you also know the message is exactly what I wrote.

Hence, this method provides message integrity and authentication, and is the basis of digital signatures.

Alternatively, you can encrypt a message with my public key and send it to me. I can decrypt it with my private key. No-one else has the private key, so they cannot decrypt the message. So, this method provides secrecy, but with no verification of who created the message and no assurance of message integrity, since anyone can create a message.

Both of these methods work, regardless of how well-known the public key becomes, as long as the private key is kept secret.

Both of them provide useful building blocks for more complex algorithms that overcome other problems. For example, when you receive my public key, how do you know that it actually comes from me? I can't digitally sign it with my private key, because you don't yet trust my public key. A chicken-and-egg problem, with solutions ranging from meeting up in person to Certificate Authorities.

Other asymmetric algorithms may only be able to encrypt with one of the keys and decrypt with the other. e.g. DSA only supports digital signatures, not secrecy.

Even RSA is not really used for message secrecy. It is too slow to encrypt long messages. Instead, it is used to negotiate a short-lived symmetric key for faster encryption. See https://security.stackexchange.com/a/185544/30469 for a great answer that explains this a bit more.

One final warning: there are weaknesses in using the same private and public key pair for both authentication and secrecy. Don't do that.

Answer 4

I offer a different view that helped me to understand things back in the day.

Asymmetric cryptography works using as base a couple of two big numbers that are computed in some way, so they are related. We call them keys or 2 parts of one key.

However the following property holds:

• if you have only them, you can not compute one just from the other
• the algorithms in place give you the fact that anything encrypted by one of this number can only be decrypted by the other number (and not even by using the first number, this is a key property).

Now, on top of that we decide that one of the two is public and we will distribute it globally (in X.509 certificates, on public OpenPGP keyservers, etc.) while the other is private and everything should be made secure so that only the entity (it can be an individual, an organization, an host, an email address, etc.) covered by it is the only one knowing this "private" part.

So if you imagine everyone has these 2 parts and all public parts are known, trusted and secure (we will see there are problems here) you can have the following things, if we take Alice and Bob:

• everything Alice encrypts with Bob public key can only be decrypted by Bob (because he should be the only one having the corresponding private key)
• everything Alice encrypts with her private key can be decrypted by anyone using her public key (which is by definition public and available to everyone).

You may find the second point useless. It is not, it is the basis of authentication in fact. Because normally only Alice has her private key so if you are able to decrypt something with her public key then you know that it was encrypted with Alice private key so it means it was done by Alice, you have proved authentication.

Now of course the problem is how you publish all public keys, because anyone could publish a key saying it is for "alice@example.com".

How is this solved?

• in the X.509 PKI world, public keys are not managed like that but through a X.509 certificate (often called "SSL certificate" which is doubly wrong because TLS superseded SSL 20 years ago and because you can do TLS without certificates at all), which is basically a public key plus a begin and an end date and a signature. What is the signature? It is a computation carried over all the content of the certificate (hence the public key) done by the private key tied to another certificate, typically a "certificate authority" (normally there is a chain of them but that does not change the generic idea). And you ultimately trust some CAs, so that you have their public key and you validate any certificate that is validly signed by private keys of these CAs.
• in the OpenPGP web of trust, in fact anyone as a local/individual decision can say how much he trusts a given key; the idea is that normally the two individuals meet in real life, even show official ID documents, and only after that can say "yes key X is really belonging to such individual".

So my question is, what stops an attacker listening in from just grabbing the key which you send alongside the data? If it's not actually being sent alongside the encrypted data, then at what point does the server receive the key that it needs to decrypt?

Let us take a typical HTTPS handshake that uses HTTP over TLS (see https://en.wikipedia.org/wiki/Transport_Layer_Security#TLS_handshake for a complete explanation)

You can look at this diagram for TLS 1.3: https://www.rfc-editor.org/rfc/rfc8446#section-2 ; you will see there that each Certificate message is in fact itself encrypted with keys derived from previous exchanges (the ClientHello and ServerHello messages that each include a random secret). Remember also that if you trust a given CA (that it its private key) you trust anything signed by it, that is any end client certificate having a signature made by its private key (that hence everyone could verify using its public key).

Anyone intercepting the ServerHello and replying it will not be able later to prove it has the corresponding key associated to the certificate sent with the Certificate message. This is also why authentication is so important: without it you can have a secure as in encrypted stream but without any idea on who you are talking to, which could be a man in the middle relaying the traffic.

See the ClientKeyExchange message: "which may contain a PreMasterSecret, public key, or nothing. (Again, this depends on the selected cipher.) This PreMasterSecret is encrypted using the public key of the server certificate." and hence only the server (having the corresponding private key) will be able to decrypt it and go forward. Same for the other direction.