A couple of reader alerts:

In order to (somewhat) simplify the description process and tighten the volume of the article we are going to write, it is essential to make a significant remark and state the primary constraint right away — everything we are going to tell you today on the practical side of the problematics is viable only in terms of TLS 1.3. Meaning that while your ECDSA certificate would still work in TLS 1.2 if you wish it worked, providing backwards compatibility, the description of the actual handshake process, cipher suits and client-server benchmarks covers TLS 1.3 only. Of course, this does not relate to the mathematical description of algorithms behind modern encryption systems.

This article was written by neither a mathematician nor an engineer — although those helped to find a way around scary math and reviewed this article. Many thanks to Qrator Labs employees.

### (**E**lliptic **C**urve) **D**iffie-**H**ellman (**E**phemeral)

**The Diffie–Hellman legacy in the 21 century**

Of course, this has started with neither Diffie nor Hellman. But to provide a correct timeline, we need to point out main dates and events.

There were several major personas in the development of modern cryptography. Most notably, Alan Turing and Claud Shannon both laid an incredible amount of work over the field of theory of computation and information theory as well as general cryptanalysis, and both Diffie and Hellman, are officially credited for coming up with the idea of public-key (or so-called asymmetric) cryptography (although it is known that in the UK there were made serious advances in cryptography that stayed under secrecy for a very long time), making those two gentlemen pioneers.

In what exactly?

Well, this may sound peculiar; however, before November 6, 1976, there was no public knowledge of public-key encryption systems. Whitfield Diffie and Martin Hellman (and, by the matter of fact, Ralph Merkle) — mathematicians, computer engineers and enthusiasts, as well as cryptologists were the first.

For those not aware — due to the role cryptanalysis overtook during the World War II and its enormous impact on keeping information in secret, the two countries that believed they had most advanced cryptography knowledge — the U.S. and U.K. included encryption into their Munitions Lists and leveraged a heavy export ban (simultaneously weakening encryption implementation for domestic private and commercial use). For this reason, the U.K. researchers working at the asymmetric key exchange technique in Government Communications Headquarters and developing an analogous scheme weren’t recognized for this invention until 1997, when restrictions on cryptography algorithms and their description were rendered ineffective.

Back to our dual inventors — what has Diffie and Hellman revolutionized specifically?

Let’s take a look at their original paper, perfectly illustrating the giant leap they’ve introduced (even theoretically with their research paper):

And the following one:

These two pictures perfectly illustrate the huge change Whitfield Diffie and Martin Hellman introduced after cryptography and cryptanalysis centuries of evolution — the establishment of a shared secret key as a result of a cryptographic computation.

Let’s take a look at another good picture with colors:

It explains what is going on. Before Diffie and Hellman key agreement invention, there was only one symmetric key — it was used both to encrypt and decrypt the message. If you want to give someone such a “key”, it must be transferred over a “secure” channel. You can imagine all the restrictions of such a previous generation scheme right away — you need an already established secure channel, you cannot reuse the key, and, ideally, the length of the key should be the same as the length of the message.

Claude Shannon in his wartime classified work “Communication Theory of Secrecy Systems” proved that all theoretically unbreakable ciphers must have the same requirements as the one-time pad — famously known as the Vernam cipher, by the author of this symmetrical polyalphabetic stream cipher.

Again, we’re going to take a look at the original paper:

Before we go any further, let’s ask ourselves — how two, even if brilliant, however, human beings came up with such a significant improvement in an applied field with such a history, especially at the time of war? Well, because of the:

- Information theory, formulated by Claude Shannon;
- Theory of computation influenced by, most notably, Alonzo Church, John von Neumann, and Alan Turing;
- And, more importantly, computability theory based mostly on Turing’s work, which we could say all developed and matured at the same period of the 20th century. Diffie and Hellman both mentioned Claude Shannon as the most significant influencer of their work.

Lenstra’s “Universal Security” illustrates the quantity of energy needed to “break” the symmetric cryptosystem with various key lengths. It turned out that breaking a 228-bit long, elliptic curve key would require the same amount of energy that is needed to boil all the water on Earth. It is, however, valid only under consideration of known algorithms and hardware, as, strictly speaking, no one knows if significantly more efficient algorithms or hardware exist. 228-bit EC key is comparable to the 2380-bit long RSA key, more on that later. Although in this estimation both RSA and EC keys are used in an asymmetric encryption scheme, such key lengths are somewhat equivalent to a 128-bit symmetric encryption key.

It is easy to imagine that something “hard to calculate” would require much energy and/or time needed for the computation. We tend to think that computers can “calculate everything”, but it turns out that it is not true. First, there exist undecidable examples, like the halting problem, though in the field of cryptography, we can avoid this pitfall. Second, if we consider the time needed for a particular algorithm to run, it may be arbitrary high. That is what we exploit in cryptography. A problem is considered “easy” to calculate if the time required to run the respective algorithm depends on the input size (measured in bits) like a polynomial: \(T(n) = O(n^k)\), for some positive constant \(k\). In the computational complexity theory field, such problems form the P complexity class.

The P complexity class is almost central, as it represents the problem for which a deterministic polynomial time algorithm exists. Another complexity class is the NP (the problems that are “hard” to calculate), representing a set of decision problems, i.e., problems requiring “yes” or “no” answer, that have a proof verifiable in polynomial time. You see the word “proof” here? That is where we get to the trapdoor functions, belonging to the NP complexity class.

Credits: xkcd

### One-way functions; Trapdoor functions

By definition, a one-way function is such a function that is easy to compute on every input but is hard to reverse, i.e. compute original input given output only. “Easy” and “hard” refer to the computational complexity theory definitions above. Interestingly, that one-way functions existence is not (mathematically) proved because their existence would prove that the P and NP complexity classes are not equal, while either P equal NP or not is nowadays an open problem. So, keep in mind that all modern cryptography relies on unproven hypotheses.

Now, in their original paper Diffie and Hellman introduce another generation of the one-way functions they called “trapdoor functions”. How do they differ?

As they explain in their landmark paper:

In a public-key cryptosystem enciphering and deciphering are governed by distinct keys, E and D, such that computing D from E is computationally infeasible (e.g. requiring \(10^{100}\) instructions). The enciphering key E can be disclosed [in a directory] without compromising the deciphering key D. This enables any user of the system to send a message to any other user enciphered in such a way that only the intended recipient is able to decipher it ...The problem of authentication is perhaps an even more serious barrier to the universal adoption of telecommunications for business transactions than the problems of key distribution…[it]…is at the heart of any system involving contracts and billing.

By convention, cryptography characters “Alice” and “Bob” (seeking secure communication) are frequently used to explain the public-key concept. Alice and Bob agree on large integers \(n\) and \(g\) with \(1< g< n\). The selection impacts the security of the system. “The modulus \(n\) should be a prime; more importantly \((n-1)/2\) should also be a prime <…> and \(g\) should be a primitive root modulo \(n\) <…> [and] \(n\) should be <…> at least 512 bits long.” The Diffie–Hellman protocol can be stated in elemental form in 5 steps.

- Alice chooses \(x\) (a large random integer) and computes \(X=g^x \bmod n\)
- Bob chooses \(y\) (a large random integer) and computes \(Y=g^y \bmod n\)
- Alice sends \(X\) to Bob, while Bob sends \(Y\) to Alice (they keep \(x\) and \(y\) secret from each other)
- Alice computes \(k = Y^x \bmod n\)
- Bob computes \(k' = X^y \bmod n\)

As a result Alice and Bob have the same value \(k=k'\) that serves as a shared secret.

Trapdoor function is a one-way function that makes it possible to find its inverse if one has a piece of special information called the “trapdoor”. Sounds easy, though it was rather hard to find such functions — the first feasible method was found in the implementation of a public-key cryptography asymmetric encryption algorithm named RSA after its creators: Ron Rivest, Adi Shamir and Leonard Adleman.

### RSA

In RSA the hardness of inverting the function is based on the fact that factoring (finding prime multipliers of a number) takes much more time than multiplication, or should we say here that no polynomial-time method for factoring large integers on a classical computer has been found, however, it has not been proven that none exists.

In RSA, like in any other public-key encryption system, there are two keys: public and private. RSA takes the input message (represented as a bit string) and applies a mathematical operation (exponentiation modulo a big integer) to it to get a result looking indistinguishable from random. Decryption takes this result and applies a similar operation to get back the original message. In asymmetric cryptography, the encryption is made with the public key and decryption with the private one.

How? Because the operands belong to a finite cyclic group (a set of integers with multiplication in modular arithmetic). Сomputers don’t deal great with arbitrarily big numbers, but, luckily, our cyclic group of integers is to perform an operation called “wrap around” — a number larger than the maximum allowed is wrapped around to a number in the valid range we operate. This allows us to operate with keys of “no longer than” length. In elliptic curve cryptography cyclic (multiplicative) groups are used too but constructed a bit differently as we will see later.

Basically what RSA does is taking two large prime numbers and multiplying them to get the so-called modulus. All the other numbers to be dealt with reside between zero and the modulus. The modulus is to be a part of the public key, and its bit length determines the key length. The second part of the public key is a number chosen between zero and the Euler’s totient (modern RSA implementation takes the Carmichael’s totient instead of Euler’s) of the modulus with some additional restrictions. Finally, the private key is to be calculated by solving some modular equation. To encrypt a number we simply raise it to the power equal to the public key, and to decrypt a number back, we raise it to the power equal to the private key. Thanks to the cyclic nature of the group, we get back the initial number.

There are two significant problems with the RSA nowadays, one being a consequence of the other. As the length of a key (i.e., the number of its bits) grows, the complexity factor grows not so fast as one may expect. That is because there exists sub-exponential (but still super-polynomial) factorisation algorithm. So, in order to keep an appropriate security level, the length of the RSA key needs to grow somewhat faster than the ECC key length. That is why most widespread RSA keys nowadays are either 2048 or 3072 bit long.

A bit later, we will see in numbers how the length of the key affects overall cryptosystem efficiency by comparing the RSA and ECDSA certificate signed with Let’s Encrypt authority.

### (**E**lliptic **C**urve) **D**igital **S**ignature **A**lgorithm

The search for a better trapdoor function eventually led cryptographers to an actively evolving in the mid-80s branch of mathematics dedicated to elliptic curves.

It would be the ultimate task to describe elliptic curve cryptography in one article, so we shall not. Instead, let's take a look at an elliptic curve trapdoor function based on the discrete logarithm problem.

There are many primers and more in-depth introductions into elliptic curve cryptography, and we would especially recommend Andrea Corbellini’s “ECC: a gentle introduction” if you are interested in math.

What we are interested in are rather “simple” parameters. The elliptic curve is defined by an equation like this: \(y^2 = x^3 + ax + b\)

Such a curve is needed to construct a cyclic subgroup over a finite field. Therefore, the following parameters are being used:

- The
**prime \(p\)**that specifies the size of the finite field; - The
**coefficients \(a\) and \(b\)**of the elliptic curve equation; - The
**base point \(G\)**that generates the mentioned subgroup; - The
**order \(n\)**of the subgroup; - The
**cofactor \(h\)**of the subgroup.

In conclusion, the **domain parameters** for our algorithms is the **sextuplet** \((p, a, b, G, n, h)\).

Such elliptic curves work over the finite field \(\mathbb{F}_p\), where \(p\) is a rather large prime number. So we have a set of integers modulo \(p\), where operations, such as addition, subtraction, multiplication, additive inverse, multiplicative inverse are possible. Addition and multiplication work similarly to the modular or so-called “clock” arithmetic we saw in the RSA “wrap arounds”.

Since the curve is symmetrical about the x-axis, given any point \(P\), we can take \(−P\) to be the point opposite it. We take \(−O\) to be just \(O\).

Addition for curve points is defined in a way that given points \(P\) and \(Q\), we can draw line intersecting both those points and intersecting curve in a third point \(R\) so that \(P+Q=-R\) and \(P+Q+R=0\).

Let’s take a look at Marc Hughes explanation:

A line of constant slope that travels along the surface of the torus is shown above. This line passes through two randomly selected integer points on the curve.

To add two points on the graph, draw a line from the first selected point \(P\) to the second selected point \(Q\), and extend the line until it intersects another point on the graph \(-R\), extending it across the plot boundaries if necessary.

Once you intercept an integer point, reflect the point vertically across the middle of the graph (an orange dotted line) to find the new point \(R\) on the graph. Therefore \(P+Q=R\).

Multiplication by a scalar is now trivial: \(n\cdot P = P + P + P + \dots + P\) (here are \(n\) summands).

The trapdoor function here lies within the discrete logarithm (for elliptic curves) problem, not the factorisation we took a look at within the RSA section. The problem is: if we know \(P\) and \(Q\), what is such \(k\), that \(Q=k\cdot P\)?

Both the factorisation problem (underlying the RSA) and the discrete logarithm for elliptic curves (which is the basis for ECDSA and ECDH) are supposed to be hard, i.e., there are no known algorithms for solving this problem in polynomial time for a given key length.

While, typically, anyone would be shamed for mixing the key exchange (ECDH) with the signature (ECDSA) algorithm, we need to explain how they work together. A modern TLS certificate contains a public key, in our case, of the elliptic curve algorithm-generated key pair, usually signed by a higher-level authority. The client verifies the signature of the server and obtains the shared secret. The shared secret is used in a symmetric encryption algorithm, such as AES or ChaCha20. However, the principle remains the same: agree upon domain parameters (the sextuplet), get the key pair, where the private key is a randomly selected integer (the multiplicand from \(Q=k\cdot P\)), and the public key is a point at the curve. Signature algorithms use the base point \(G\), which is a generator for a subgroup of large prime order \(n\), such that \(n\cdot G=0\), where 0 is the identity element. The signature proves that the secure connection is being established with the authentic party — a server which has the TLS certificate (public key) signed by some certificate authority for the given server name.

### (EC)DH(E)+ECDSA= Current handshake form

In modern TLS (1.3) the client and the server generate their public-private key pair on the fly, while establishing the connection, this is called Ephemeral version of key exchange. Most popular browser TLS libraries support this. Mostly they use Edwards 25519 elliptic curve, introduced by Daniel J. Bernstein (djb), offering 128-bit security. Since 2014 openssh uses this curve for the key pair creation. In 2019 though, browsers still don’t support TLS sessions with servers having a certificate with EdDSA public key.

But let’s get back to how things work at the end of 2019 with TLS 1.3.

The key exchange mechanisms in TLS 1.3 are restricted to (EC)DH(E)-based (with the x25519 is the one supported in client-side TLS libraries of most popular browsers as well as server-side TLS libraries, such as OpenSSL, which we will inspect a bit later), and the cipher suite list contains only three entries: TLS_AES_128_GCM_SHA256, TLS_AES_256_GCM_SHA384 and TLS_CHACHA20_POLY1305_SHA256. For those of you aware of how the cipher suites were named in the TLS 1.2 version it is apparent right away that the key exchange mechanism is now “detached” from the cipher suite name, also the static RSA and static Diffie–Hellman exchange modes removed from the specification entirely. Even the session resumption based on PSK is made over ECDHE in TLS 1.3. It is also true for custom DH parameters, which aren’t allowed now, leaving only those generally agreed to be secure in the final protocol specification.

It is interesting that there is a rather significant difference in how asymmetric encryption algorithms work nowadays. With ECC (and ECDSA certificates in particular) we use smaller keys to get to “convenient” levels of security, compared with RSA. That enables usage of a stronger asymmetric encryption algorithm and key exchange mechanisms on smaller devices and sometimes even in things that are not generally considered a device (smartcard).

First of all, it is necessary to mention what “hybrid cryptosystem” means in terms of TLS 1.3. A hybrid cryptosystem is the one that uses asymmetric (public key) encryption to establish a shared secret, that is further used as a key in a symmetric stream or block cipher.

Secondly, public-key infrastructure and certificates. It is interesting that in his 2004 interview Martin Hellman mentioned an “unsung hero” Loren Kohnfelder, whose MIT bachelor’s thesis introduced a tree structure of what we now know as public key infrastructure. Nevertheless, let’s roll back to certificates.

The fact that the server really has the private key is ensured by his signature, which can be verified with the server public key. And the certificate ensures that some public key belongs to a specific server. It means that you are establishing secure communication with the specific party and not with an imposter. Your bank, not a cybercriminal. In TLS 1.3 there is a significant improvement over previous negotiation format — the server signs all the information it has up to this moment: the client hello and the server hello, including negotiated cipher. Let’s take a look at the corresponding section of the RFC 8446:

Client Server Key ^ ClientHello Exch | + key_share* | + signature_algorithms* | + psk_key_exchange_modes* v + pre_shared_key* --------> ServerHello ^ Key + key_share* | Exch + pre_shared_key* v {EncryptedExtensions} ^ Server {CertificateRequest*} v Params {Certificate*} ^ {CertificateVerify*} | Auth {Finished} v <-------- [Application Data*] ^ {Certificate*} Auth | {CertificateVerify*} v {Finished} --------> [Application Data] <-------> [Application Data]

In TLS 1.3 client sends the key share (along with needed parameters), signature algorithms right away in the first message (Client Hello). The keys needed to exchange with the server are created in the background, without the user even noticing that fact. They are further exchanged with the server to create a common secret, from pre-master secret keys that were established when the server sent his message (Server Hello) answering the client.

On the “Server Hello” side you can see the Certificate* being transferred to the client, along with the CertificateVerify* part which verifies that the party possesses the private key for the corresponding public key entry, and creates the session (symmetric) key if everything goes as planned — meaning, that the side requesting the data (client) successfully verified the answering side (server), further creating a common secret.

There are two essential operations hidden in this transmissions — signature creation and signature verification. Those are made on both sides of communication since “signature” is essentially a proof that the party actually has the private key corresponding with the public key, that the data comes from signatory and the message was not altered in transit.

With RSA, as we will further see, the signing operation is the most expensive. Since we’re signing with a 2048 or 3072-bit long key, such operation loads the server significantly, much more than it loads the client verifying such a signature.

With ECDSA, we have smaller keys (we are going to look at the ECDSA with NIST P-256 (or the secp256v1)) but more complex operations. As a result, it could be viewed as the “upside-down” RSA — the client is loaded most, by the signature verification computation, while the server easily handles the signature creation. The measurements verify that, see “A bit of benchmark” section.

This effect handily scales the nowadays Internet — since modern clients are almost equally powerful as the servers (taking in mind just the CPU core frequency), so they could effectively take the expensive operation to bare. The server, in its turn, can use the freed capabilities to create more signatures and establish more sessions.

### Let’s Encrypt certificate signature

So, in order to provide the reader with a bit of practical and handy instructions on how to create a TLS-enabled server with the ECDSA key pair signed by the Let’s Encrypt authority, we decided to illustrate a full process of creating a key pair needed to create a CSR (certificate signing request) for the Let’s Encrypt and, as a result, get the needed ECDSA certificate for our server.

We have to generate a private key to proceed. We will use the OpenSSL library. The OpenSSL manual describes the generation of any EC keys through a special command, designated especially to the elliptic curve branch of the generation algorithm.