Public-key cryptography

Public-key cryptography is a major encryption paradigm (also called asymmetric encryption). The core idea is simple — every user owns a pair of keys: a public and private key.

• The public key is distributed widely, often in a well-known location.
• The private key is kept in a safe location by the user.

Notably, the private and public key are generated with a cryptographic hash function, so they don’t reveal any information about the other. The communication workflow for a plaintext message $M$ between Alice and Bob is as follows:

• Alice encrypts $M$ using Bob’s public key: c = E(pub(b), m)
• This encrypted message c is sent to Bob.
• Bob decrypts c using his private key: m = D(pri(b), c)

This solves the problem faced by symmetric encryption, by not requiring agreement on what key to use.

Applications

One key application of public-key cryptography is in digital signatures, which are used to provide integrity and authentication in insecure channels. It is very similar to the workflow above:

• First, Alice constructs a digital signature: sig(a) = E(pri(a), H(m))
• Then, both the message and signature are sent: [m, sig(a)]
• Then, Bob verifies that D(pub(a), sig(a)) == H(m)

This allows the receiver to be highly sure of the safety of the message (i.e., you can verify the “sender” was the actual sender). They would know broadly that:

• Whoever generated sig(a) must know the private key pri(a). This authenticates the message sender, since it shows that m must’ve been generated by the sender.
• And that the message m hasn’t been changed/tampered with (integrity).