Public-Key Cryptography

Public-key cryptography refers to a class of cryptographic systems in which each actor uses two keys: a public key that is known to all, and a corresponding private key that is known only to the actor. The guiding principle is that messages intended for a specific person should be encrypted using their public key in such a way that the message can only be decrypted through the use of the corresponding private key.

Public-key cryptography is important for securely transmitting messages across a potentially insecure channel, meaning that it is assumed all communications can be read by a malicious attacker. As such, public-key cryptography is especially important for ensuring the security of the internet.

Suppose Alice is trying to send a message to Bob, without Eve knowing what the message is. Unfortunately for Alice, Eve can hear and see everything that Alice says or sends. The goal of encryption, in general, is for Alice to be able to send the message successfully without Eve being able to determine what the message is.

There are a number of approaches that Alice can use. One of the simplest is to simply write the message down, place it somewhere that only Bob has access to (e.g. Bob's house), and simply wait for Bob to access the message. This forms the basic principle behind public-key cryptography: only the intended recipient should be able to "unlock" the message, given that the message was encrypted using the corresponding public key (in this case, the public key is the address of Bob's house).

In practice, this approach has a number of issues, the most obvious of which being that it is impractical to physically travel to a mutually accessible site every time a message needs to be transmitted. Additionally, if the message is stolen at any point during the journey, Eve will be able to determine the message (by simply reading it). Still, the analogy provides some use, particularly since it extends well into the following example:

Suppose Alice wishes to send Bob a valuable diamond, but the jewel will be stolen if sent unsecured. Both Alice and Bob have a variety of padlocks, but they don't own the same ones, meaning that their keys cannot open the other's locks.

How did Alice send the diamond to Bob?

---

Here is how it's done:

1. Bob first sends Alice an unlocked padlock. Note that Bob would give anyone an unlocked padlock, as the only use for one is to send Bob something.
2. Alice adds Bob's lock and sends the package to Bob.
3. Bob removes his lock and opens the package. $_\square$

Another approach is for Alice to encrypt the message using some agreed-upon scheme, such as a Caesar cipher or Vigenère cipher. When Bob receives the encrypted message, he can "reverse" the encryption scheme in question to retrieve the original message, provided that reversing the encryption scheme is easy enough to accomplish (as it is in the two examples above). However, this approach has major weaknesses as well, the most obvious being that it is necessary to agree upon an encryption scheme—which cannot be communicated without Eve observing. This leads to a class of algorithms known as symmetric key algorithms, so named because both actors must have access to the same key (e.g. an encryption system) in order for the algorithm to be secure. Symmetric key algorithms are easier to work with, so if a symmetric key can be generated, they are generally used.

More modern approaches take a seemingly counterintuitive approach: the encryption algorithm is entirely public and thus known to the attacker as well. There are two guiding principles at play here:

1. Encrypting the message with the public key, followed by encrypting the result with the corresponding private key, should result in the original message.
2. "Reversing" the encryption should be computationally difficult.

In this sense, "computationally difficult" has a particular meaning specific to the context, but in general it (roughly) means that a computer would take an unacceptably long time to decrypt the message. For example, public-key systems might be based on NP problems such as the integer factorization problem, the traveling salesperson problem, elliptic curve discrete logarithm problem, and so on. Thus knowing the encrypted message is not enough for Eve to determine the original, but Bob can retrieve the original message by encrypting the already-encrypted message with his own private key.

Number theory is an important tool for encryption since it can be used to satisfy both properties from the end of the previous section, stated again below:

1. Encrypting the message with the public key, followed by encrypting the result with the corresponding private key, should result in the original message.
2. "Reversing" the encryption should be computationally difficult.

In particular, Euler's theorem is extremely useful:

If $a,n$ are relatively prime, then

$$a^{\phi(n)} \equiv 1 \pmod n,$$

where $\phi(n)$ is Euler's totient function.

A special case of this, Fermat's little theorem, is also very useful:

If $p$ is a prime number, then

$$a^p \equiv a \pmod p$$

for any integer $a$.

Essentially these two theorems give conditions for the powers of a number to "repeat" themselves (in modular arithmetic), which allows the first property from above to be satisfied with proper choices of the public and private keys. Additionally, because the discrete log problem is computationally difficult, number theory with exponents can be used to satisfy the second property as well. Overall, this makes number theory (especially with modular arithmetic) an ideal choice for most public-key cryptographic systems; this can be even further improved through the use of group theory, especially the theory of elliptic curves.

These ideas are fully present in the most popular public-key encryption scheme, RSA encryption. In this system, a public key $e$ and private key $d$ are chosen so that $ed \equiv 1 \pmod{\phi{\small(n)}}$. This allows the sender to calculate $m^e \pmod n$ $($where $m$ is an integer of the $M$ message, where $0 \leq m<n,$ and $n$ is coprime to $m),$ and since the discrete log problem is computationally difficult, an attacker cannot easily determine $e$ from $m^e \pmod n$. The receiver, however, can easily calculate $m$ by calculating $m^{ed} \pmod n$, since $m^{ed} \equiv m \pmod{n}$ due to Euler's theorem.

Main article: Diffie-Hellman

The Diffie-Hellman protocol is a public-key encryption scheme, usually used to establish a shared key that can then be used in symmetric key algorithms. The guiding principle is the difficulty of the discrete log problem and the simple fact that $(g^a)^b=(g^b)^a$; in particular, the algorithm itself is quite simple:

1. Alice and Bob both choose secret numbers $a$ and $b$, and agree on a public key $n$ and $g$ $($usually, $g=2$ and $n$ is very large$).$
2. Alice sends Bob the value $g^a \pmod n$, and Bob sends Alice the value $g^b \pmod n.$
3. Alice and Bob both calculate $g^{ab} \pmod n$, and they now have a shared key to use in a number of potential ways.

This illustrates a second approach to public-key cryptography: "mixing" the two private keys in order to achieve a shared key.

Though the algorithms behind public-key cryptography are sound in theory, there are a number of practical attacks that can be attempted. The most common and well-known is the man-in-the-middle attack, in which an attacker attempts to intercept and decrypt an incoming communication, and then re-encrypt it before sending it along to the intended target (to avoid suspicion). To use a practical analogy, a man-in-the-middle attack is roughly equivalent to opening and re-sealing an envelope.

Generally speaking, man-in-the-middle attacks are achieved by opening two lines of communication: one with the sender, and one with the receiver. The goal is to trick the sender into thinking that the attacker is the reciever, and to trick the receiver into thinking that the attacker is the sender; this is done by having the sender encrypt their message using the attacker's public key rather than the intended receiver's, allowing the attacker to decrypt the intended message by using their own private key. They then encrypt the message again using the receiver's public key, thus leaving both the sender and the receiver unaware of the deception.

For example, in the Diffie-Hellman protocol in the last section, an attacker Mallory can choose a secret number $m$. Alice and Mallory then agree on a shared key $g^{am} \pmod n$, and Bob and Mallory agree on a shared key $g^{bm} \pmod n$, where Alice and Bob both think that Mallory is the other person. Any communications then necessarily go through Mallory, and the deception cannot be discovered until Mallory chooses not to answer a communication (at which point both Alice and Bob will know they have been duped since their shared-key algorithm will fail due to the fact that they both have different keys).

In particular, the security of public-key cryptography rests on the assurance that a particular person's public key is actually their public key, otherwise, man-in-the-middle attacks are possible. Returning to an example above, if Alice wants to deliver a letter to Bob's house so that only Bob can access it, Alice needs to trust that Bob's published address (his public key) is, in fact, his real address and not the address of an attacker. Unfortunately, no entirely robust solution to this issue has yet been determined, though attempts have been made through the use of digital signatures and certificates.

• RSA Encryption
• Diffie-Hellman