Understand Public Key Encryption

[fog37]

TL;DR Summary

understand and appreciate the strength of public key encryption

Hello Forum,

I think I understand how private key encryption works: there are two keys, one for Alice sender $K_{s}$ and one for Bob the receiver $K_{r}$ . The two keys are identical, correct? By analogy, I envision a mechanical lock that can be opened/closed with the same key.

Alice encrypts the message for Bob, Bob receives the encrypted message and uses his key to decrypt it. The problem is that if someone, Eve, intercepts the message and has an illegal copy of the key, she can read the message too. It can be hard to prevent someone to intercept the key when the key is exchanged between Alice and Bob.

Public key encryption: the sender has a set of two keys (a public key and a private key. The set is called a pad). The two keys are "mathematically related").
Bob the receiver also has two keys (a public key and a private key that are mathematically related). When Alice send an encrypyed message to Bob, she encrypts it using Bob's public key (everybody knows that). Bob decrypts the message using his own secret private key (nobody knows that). Is that correct? Eve would need to know Bob's private key but she cannot reverse engineer Bob's public key to find Bob's private key. It is mathematically really hard (impossible?).

Using simple mechanical locks, what would be a good mechanical analogy for public key encryption? Would it simply be a lock that has inserts for two different keys?

Thank you!

 

[Vanadium 50]

Using simple mechanical locks, what would be a good mechanical analogy for public key encryption?

Why must there be one?

It's more like a mailbox. Anyone can drop mail in the slot, but only the postal worker can take mail out.

 

[anorlunda]

In mathematical terms, if f is a trapdoor function, then there exists some secret information t, such that given f(x) and t, it is easy to compute x. Consider a padlock and its key. It is trivial to change the padlock from open to closed without using the key, by pushing the shackle into the lock mechanism. Opening the padlock easily, however, requires the key to be used. Here the key is the trapdoor and the padlock is the trapdoor function.

Public Key Encryption can use any trapdoor function. Prime number factorization is a popular choice.

 

[PeroK]

I noticed that when I emailed an encrypted file (using PKI) to several recipients, the sent email was no larger than if there had been only one recipient. This was puzzling given the assumption that the file was encrypted separately using each recipient's public key.

The answer I got was that the PKI was used only to exchange a separate key. In other words, the file was encrypted once using a randomly selected key and that key was itself encrypted using each recipient's public key. The recipient then decoded the key using their private key and the file itself using the decoded key.

This is called key encipherment:

https://security.stackexchange.com/...etween-key-encipherment-and-data-encipherment

 

[Vanadium 50]

Public key encipherment is very, very slow. So it is common to use it to exchange a one-use symmetric key rather than the entire message.

 

[jack action]

When Alice send an encrypyed message to Bob, she encrypts it using Bob's public key (everybody knows that). Bob decrypts the message using his own secret private key (nobody knows that). Is that correct?

I don't think so. From what I understand, it uses the Diffie–Hellman key exchange.

Using simple mechanical locks, what would be a good mechanical analogy for public key encryption?

Although difficult to execute in a mechanical way, here how I would explain it:

Alice & Bob agree to use a certain blank key for their locks. They also agree on a method to modify those blank keys based on how they are already cut. Alice cuts her blank key - according to the agreed method - and she starts at a position she keeps secret (her private "key"). She sends this new key to Bob (her public key). Bob does the same thing to his blank key (starting at another secret position, his private "key") and sends it (his public key) to Alice.

Now both Alice & Bob have two different keys. But Alice regrinds the key sent by Bob using the same common method, starting at the same secret position (her private "key") and gets a new key. Bob does the same to his key sent by Alice, using his secret starting position - his private "key". The result is that now both keys are identical and can be used to lock/unlock the same padlock.

Eve knows which blank key and grinding method they used. She also knows what the keys look like when they are "half-grinded" (the public keys), both starting at different unknown points (the private "keys"). But she doesn't know what the end key looks like when both modifications are done (in either order).

 

[jbriggs444]

I don't think so. From what I understand, it uses the Diffie–Hellman key exchange.

If you are sending an e-mail message in a one-way trip, you cannot use Diffie-Hellman key exchange to encrypt it. Diffie-Hellman requires bi-directional communication.

You would typically use Diffie-Hellman if you have a two-way channel open. For instance, a client connecting to a web page and wanting to negotiate a session key using TLS.

In the case at hand, we have a one-way communication. An email is going out on a store-and-forward messaging network. The recipient has no way to get a message back to the sender. The message from sender to recipient must be self-contained.

Traditionally, email messages to distribution lists are sent over the store-and-forward network economically. You send one copy of the message to your outbound relay complete with a distribution list of recipients. That relay splits the distribution list up -- "one envelope to company A with five recipients", "one to company B with two recipients", ...

You can read more about that in RFC 5321 (message envelope) and RFC 5322 (message body). I came in when RFC 821 and 822 were the rules of the road. The 'gist of it has not changed much.

If you want to keep to the style of one body in an envelope with many recipients, you will have to include keying information separately for each recipient. If you want to use public key cryptography and not use CPU profligately, you'll want to encrypt the message once using a randomly chosen symmetric key and then encrypt the symmetric key somehow once per recipient using that recipient's public key.

S/MIME is one approach. A quick glance at the spec does not make the nitty gritty on the implementation technique obvious. However, it is clear that multiple recipients of a single message body are contemplated by the standard:

2.7.3. Multiple Recipients
If a sending agent is composing an encrypted message to a group of
recipients where the encryption capabilities of some of the
recipients do not overlap, the sending agent is forced to send more
than one message. Please note that if the sending agent chooses to
send a message encrypted with a strong algorithm and then send the
same message encrypted with a weak algorithm, someone watching the
communications channel could learn the contents of the strongly
encrypted message simply by decrypting the weakly encrypted message.

 

[jack action]

Thank you @jbriggs444 for bringing that point. I'm no expert in the field and I'm trying to understand it as much as the OP. So my analogy still holds, it is just that this is only one of the Public-Private keys methods of encryption.

So I found 2 other methods (which are basically the same) where the message is encrypted with one key and decrypted with the other key. If it is encrypted with a public key, it is called Public key encryption (such as RSA), if it is encrypted with a private key, it is called Digital signatures.

So to go back with the analogy of mechanical locks, you are using a special lock that can only be lock with one key and unlock with another key.

When you are encrypting with a private key, you make the public (decrypting) key available to anyone. So when someone receives an encrypted message (supposedly) from you and that person can decrypt the message with your available public key, that person is sure that it was encrypted with your private key (and thus comes from you), hence the term digital signature. In this case, anyone who intercepted the message can read it (since the decrypting key is publicly available), so there is no confidentiality.

When you are encrypting with the public key of the receiver, the receiver is the only one who can decrypt it. Thus, this ensure confidentiality, but you cannot be sure who sent the message.

@jbriggs444 , as far as I know, these are the methods used for encryption, but I don't understand how they can exist with a one-way trip, as you mentioned. Somehow, your public key must be fetched by the other party (the recipient's public key, as mentioned by @PeroK ).

 

[jbriggs444]

@jbriggs444 , as far as I know, these are the methods used for encryption, but I don't understand how they can exist with a one-way trip, as you mentioned. Somehow, your public key must be fetched by the other party (the recipient's public key, as mentioned by @PeroK ).

You are correct that the sender needs to somehow obtain a copy of the recipient's public key.

The transport of the recipient's public key into the hands of the sender can take place in advance (populating a client's cache of recipient keys) or on demand from a repository. It does not require that the sender and recipient be on-line simultaneously. No two-way communications are required in that sense.

Diffie Hellman key exchange, by contrast, requires a two-way communication to exchange copies of random numbers that have been made up on the spot and which are discarded after use. The peers need to be on-line simultaneously with a two way channel up and running.

Probably what the sender would actually retrieve or have cached would be a certificate -- a copy of the recipient's public key together with a cryptographically signed assertion from a trustworty Certificate Authority that the name on the cert actually belongs to the recipient in question. How you know whether to trust the Certificate Authority is another can of worms.