Asymmetric Encryption & PKI: Digital Signatures, RSA, and Future Security

Asymmetric Ciphers: Why Do We Need Something Different?

An asymmetric cipher (or public key cipher) is a cipher where the encryption and decryption keys are different.

Asymmetric ciphers were born to solve two main problems related to symmetric ciphers:

1. Symmetric ciphers cannot provide authenticity;

2. The security of a symmetric cipher is based on the precondition that the key has been previously exchanged in a secure way. But there is no way to do it, other than encrypting the key itself, which would recursively raise the same problem of exchanging another key.

The trade-off? Efficiency. Asymmetric ciphers are from 10x to 1000x slower than symmetric encryption.

In an asymmetric cipher, each one of the two endpoints has two keys, called public key and private key (or secret key), where the public key is built starting from the private key: $k_{pub}=f(k_{pri})$ .
As the name suggests, the public key can be visible to everyone, while the private key is only known by the respective endpoint. The cipher is based on three main features:

• If the message has been encrypted with the private (public) key of a certain endpoint, it can be only decrypted with public (private) key of the same endpoint;

• If the message has been encrypted with the public key, decrypt it without knowing the private key must be computationally hard;

• Compute the private key given the public key (i.e. compute $f^{-1}(k_{pub})$ ) must be computationally hard.

To give a concrete example, a private key can be the set of two large prime numbers $p$ and $q$ , while the public key the product $p\cdot q$ . At this point, finding the prime factors that make up the public key means solving a famous NP problem known as prime factorization.

As for symmetric ciphers and cryptographic hash functions, since we cannot prove the exponential lower bound complexity of an algorithm, asymmetric ciphers are the outcome of public contests.

Confidentiality & Key Encapsulation

Asymmetric encryption can be used to provide confidentiality against a ciphertext-only attack as follows:

• Bob (receiver) generates a keypair $(k_{pri}, k_{pub})$ . He sends $k_{pub}$ to Alice;

• Alice (sender) encrypts the plaintext with Bob's public key: $ctx = E(ptx, k_{pub})$ . She sends it to Bob;

• Bob decrypts the ciphertext using his private key: $ptx = D(ctx, k_{pr})$ .

Symmetrically, if Alice in turn generates another pair of private and public key, Bob can send messages to Alice too, producing a secure bi-directional communication.
However, since asymmetric encryption is so much slower than symmetric encryption, in practice an asymmetric cipher is never used to entirely manage a communication. Instead, it is used to do what is called key encapsulation, i.e. to securely exchange the key to use from there on with a symmetric cipher. Since the key is the only message being exchanged, just a pair $(k_{pri}, k_{pub})$ for only one of the two endpoints is enough. Moreover, for this reason we don't really need to consider known-plaintext attacks for asymmetric ciphers.

The standard cryptosystem used to provide confidentiality through asymmetric encryption is the Rivest-Shamir-Adleman, commonly known as RSA, which is actually based on the prime factorization problem.

Maintaining Integrity

For the property of integrity, nothing changes with respect to a symmetric cipher: we can still use a MAC tag in the same way.

Solving Authenticity: Digital Signatures

With an asymmetric cipher, we can actually provide authenticity. In this scenario, we are not interested anymore in hiding the content of the message, but in guaranteeing the identity of the sender. The way we can do it is by adopting the digital equivalent of a handwritten signature:

• Alice (sender) generates a keypair $(k_{pri}, k_{pub})$ . She sends $k_{pub}$ to Bob;

• Alice sends the message $msg_A$ in clear text to Bob;

• Alice encrypts the message with her private key: $ds = E(msg_A, k_{pri})$ , where $ds$ is called digital signature. She sends the digital signature to Bob;

• Bob (receiver) decrypts the digital signature with Alice's public key: $msg_B = D(ds, k_{pub})$

• Bob compares $msg_B$ with the message $msg_A$ previously sent in clear text by Alice: if they are equal authenticity is guaranteed.

The role of the digital signature is therefore to guarantee that the endpoint who sent the message is the same one that originally transmitted the public key. This mechanism works in theory, but there's a practical problem: usually we want to provide authenticity in exchanging big documents, and when the message is particularly long the encryption is slow.
We can solve the problem by exploiting the cryptographic hash functions: Alice also sends the hash $h(msg_A)$ of the message, and produces the digital signature by encrypting $h(msg_A)$ instead of $msg_A$ . At this point Bob can decrypt it and compare the result with the hash sent in clear by Alice.
Since the hash has a fixed length regardless of the size of $msg_A$ , we are gaining in efficiency.

Another problem is due to the difference between digital signatures and paper signatures. In the physical world, to sign means to sign the output, while in the digital world it means to sign the code.
To understand this concept, let's imagine that we are signing a digital document. In reality, we are not signing what is written in the document at that specific moment, since the document can contain dynamic content, such as a date that changes according to the current day: when the date updates, the signature remains the same, and this is not the desired behavior.
Actually, there is no real way to solve this problem, other than signing only the types of document that can't change.

As last observation, let's imagine we want to provide confidentiality together with authenticity. In this case, we can combine the mechanisms seen for both properties, in a "matrioska" structure.
We are not going to see this in an explicit way, but in general both Alice and Bob will generate their own $(k_{pri}, k_{pub})$ pair. Then, Alice will first encrypt the message using her private key, and then she will encrypt the result another time with Bob's public key. Bob will decrypt the ciphertext received with his private key first, and then with Alice's public key.

The RSA standard, other than confidentiality, is built to provide authenticity as well.

How Secure Are They Compared to Symmetric Ciphers?

We have seen that the only possible attack to a secure symmetric cipher is brute-forcing the key, which has a cost of $T(\lambda)=O(2^\lambda)$ .
Asymmetric ciphers, instead, rely on hard problems for which brute-forcing is not the best attack. This implies that break a secure asymmetric cipher requires little less than $O(2^\lambda)$ operations, depending on the particular algorithm employed. Thus:

It's not possible to rely on the length of the key to compare the security of an asymmetric cipher with the security of a symmetric cipher.

We can only use the length of the key to compare two symmetric ciphers. If, instead, we want to compare the security of an asymmetric cipher, we need to know the computational complexity needed to break it.

Public Key Infrastructure

We're not done yet. For the moment, we cannot yet guarantee the full security of an asymmetric cipher. In fact, the asymmetric cipher architecture presented so far is sensitive to another kind of attack, called Man In The Middle (MITM) attack. In a MITM attack, the attacker can intercept any message exchanged between Alice and Bob, and send messages in turn. For this reason, he can be (logically) seen as a "man in the middle" of the communication.
A MITM attack can pose a threat to the communication since we have not yet seen a way to "bind" the public key to the endpoint that produced it. To understand this, let us suppose that Alice wants to send her public key $k_{pub(A)}$ to Bob. If the attacker generates his keypair $(k_{pri(E)}, k_{pub(E)})$ , he can intercept $k_{pub(A)}$ and send $k_{pub(E)}$ to Bob instead. At this point, Bob will treat $k_{pub(E)}$ believing it to be Alice's key. The attacker can now use his private key $k_{pri(E)}$ to decrypt the messages sent by Bob, violating the confidentiality constraint, and to sign messages towards Bob, violating the authenticity constraint. He can furthermore carry on the communication in both directions, talking to Alice pretending to be Bob, and to Bob pretending to be Alice.

To prevent a MITM attack, we need to apply the same mechanism we just saw for providing authenticity on the message, but now providing authenticity on the public key that Alice sends to Bob. To do that, we introduce a new endpoint, called Certificate Authority (CA).
The communication consists of two phases. In the first phase, Alice communicates with the Certificate Authority:

• Alice generates a keypair $(k_{pri(A)},k_{pub(A)})$ . She sends $k_{pub(A)}$ to the CA;

• The CA generates a keypair $(k_{pri(C)},k_{pub(C)})$ . It signs Alice's public key: $ds=E(k_{pub(A)},k_{pri(C)})$ ;

• The CA sends to Alice a collection of data containing: the digital signature $ds$ , the subject's public key $k_{pub(A)}$ , the CA public key $k_{pub(C)}$ and other details, as the signature algorithm or information about Alice. This collection is called digital certificate;

The second phase involves the communication between Alice and Bob. Now, we assume that Bob has a list of public keys owned by CAs he trust:

• Alice sends the digital certificate to Bob;

• Bob verifies that $k_{pub(C)}$ is in his list of trusted public keys. If not, he discards the digital certificate;

• If $k_{pub(C)}$ is trusted, Bob decrypts the digital signature $ds$ with $k_{pub(C)}$ : $k=D(ds,k_{pub(C)})$ ;

• Bob compares $k$ with $k_{pub(A)}$ : if they are equal, authenticity on Alice's public key is guaranteed.

This communication scheme as it stands works in theory, but in practice there exists a large number of Certificate Authorities, and Bob can only have a small number of them in his list of trusted public keys. So, whenever he receives a public key from a new legitimate CA, he will discard the digital certificate. We therefore need to reduce the number of CAs to trust.
To do this, the key $k_{pub (C)}$ of the CA is in turn authenticated by another higher-level CA, responsible for signing multiple low-level CA's public keys. For the same reason, the public keys of the high-level CAs are signed by other CAs on a higher level, and so on. The top-level CAs are called Root CAs: they are the only CAs that self-sign their certificates, and therefore the only CAs we need to trust.

All this mechanism of creation and distribution of digital certificates is known as Public Key Infrastructure (PKI).

What's Still Unsolved?

Despite everything we've covered, there are still some open problems in cryptography. Among these we can mention:

• Homomorphic encryption: Homomorphic encryption is a form on encryption that allows users to perform computation over encrypted data without decrypting it. It's pretty useful when the user wants to give this data to a third-party as a public cloud infrastructure. We are already able to do it, but in the state-of-the-art the process it's quite slow. The challenge is to find more efficient ways to do it;

• Quantum computing: Several NP problems underlying cryptographic algorithms, such as the prime numbers factorization, can be actually quickly solved by quantum computers. Nowadays there exists a research field, called post-quantum cryptography, that studies algorithms that are difficult to solve even for a quantum computer;

• Side-channel information: Another, different kind of attack that can compromise a secure communication, is the side-channel attack. In a side-channel attack, instead of exploiting vulnerabilities in the cipher, the attacker exploits extra information derived from the implementation of the cipher, as power consumption or electromagnetic radiations emitted by the encryption device. The prevention of side-channel attacks is still a much debated and studied topic.

If you've made it this far, you now have a solid foundation to understand how modern cryptography works under the hood: from perfect ciphers that are beautiful in theory but impractical, to the block ciphers and hash functions that actually protect your data every single day. Which of these topics are you most curious to explore further?