Discover elliptic-curve cryptography

07/05/2023 · 20 min read · cybersecurity cryptography ecc ellipticcurves keyexchange ecdh signature ecdsa encryption ecies cryptauditor ·

Share on:

Translations

Overview

In this article, I invite you to delve with me once again into the world of cryptography, this time to discover and understand a concept that may seem obscure: elliptic-curve cryptography. Indeed, the mention of the term “elliptic curves” implies the use of mathematics, which may put some people off. The aim of this article is to give you a simplified understanding of the concept of elliptic curves, and to show how they can be used in cryptography for key exchange, digital signatures and encryption.

Introduction

Cryptography is omnipresent in securing our data. Thanks to cryptography, we can guarantee essential security properties such as:

Confidentiality of data: information cannot be read by unauthorized persons;
Integrity of data: information cannot be modified by an unauthorized person;
Authenticity of data: information is attributed to its legitimate author;
Non-repudiation of data: information cannot be denied by its author.

Various techniques, methods, protocols and algorithms exist for encrypting (guaranteeing confidentiality), hashing (guaranteeing integrity or authenticity) or signing (guaranteeing integrity, authenticity and non-repudiation) data. Among these means, asymmetric cryptography or public key cryptography is a set of methods for ensuring the confidentiality, authenticity or non-repudiation of data, based on a private key (not disclosed by its owner) and a public key (disclosed to entities communicating with its owner).
These techniques call on mathematics, an abstract discipline that manipulates numbers, functions, geometry, planes, spaces… Among these objects, elliptic curves were integrated into cryptography in 1985 and have been widely used since the 2000s.
First, we will refresh our memories of geometry, curves and equations, so that we can get to grips with elliptic curves and how to perform operations on them. Then we will take a closer look at how elliptic curves are used in cryptography to encrypt data, exchange encryption keys or sign data.

Now you get it, we'll go into some maths!

Geometry, curves and equations

An elliptic curve is a mathematical object that belongs to algebraic geometry: it is an algebraic curve. Don’t panic, I will explain all those crazy terms!

First of all, geometry is the study of figures in space or on a plane. There are several types of geometry: Euclidean (probably the best known, and the first to be taught), affine, projective, differential… In fact, each type of geometry is associated with a context that includes techniques specific to certain branches of mathematics in order to study shapes and their multiple properties. For example, in Euclidean geometry, points, lines, segments, angles, surfaces, volumes, etc. are studied based on Euclid’s axioms (assertions serving the theory).

Then there’s algebraic geometry, a geometry that studies figures composed of points whose coordinates are governed by equations using only sums (results of additions) and products (results of multiplications).
An elliptic curve is a so-called algebraic curve, defined by a very specific equation. How about a short refresher on equations?

A mathematical equation is an expression (a set of numbers, variables and operators) that describes an equality involving one or more variables or unknowns (usually represented by letters), i.e. numbers whose value is not known. These numbers whose values we are looking for are the equation’s solutions.
For example, here’s a mathematical equation: $y = 2 x$ . Here, we say that the variable $y$ is twice the value of the variable $x$ . There are lots of solutions, such as: $y = 2, x = 1$ . If we have fun drawing a curve that plots the values of $y$ (ordinates) against those of $x$ (abscissa) in the plane, we get a straight line:

Equation curve $y = 2x$ — Equation curve $y = 2 x$

Let’s take another example of an equation:

y = 3

. This is a very simple equation where

y

is always equal to 3 (there is no variable

x

!) with a curve which is then a horizontal straight line:

OK, so what about elliptical curves?

Elliptic curves and operations

Now that we arre clear on what a curve and an equation are, let’s move to elliptic curves.

Elliptic curves and the Weierstrass equation

An elliptic curve is an algebraic curve whose points lie according to an equation of the form $y^{2} = x^{3} + a x + b$ . This is known as the Weierstrass form (named after a 19th-century German mathematician). In addition to $x$ and $y$ , there are two other parameters $a$ and $b$ . The square of $y$ ( $y$ multiplied by itself) is equal to the cube of $x$ ( $x$ multiplied by itself twice) to which we add $a$ multiplied by $x$ and to which we add $b$ . $a$ and $b$ are constant values that we fix, allowing us to define elliptic curves of different shapes. Basically, by varying $a$ and $b$ , the curve changes shape.
If we fix $a = - 4$ and $b = 5$ , we have an equation of the form $y^{2} = x^{3} - 4 x + 5$ . The associated drawing gives:

Equation curve $y^2 = x^3 -4x + 5$ — Equation curve $y^{2} = x^{3} - 4 x + 5$

If we take $a = - 6$ and $b = 2$ , we have an equation of the form $y^{2} = x^{3} - 6 x + 2$ . The associated drawing gives:

Equation curve $y^2 = x^3 -6x + 2$ — Equation curve $y^{2} = x^{3} - 6 x + 2$

Hmm… not exactly “elliptical”, is it? Well, no. Elliptic curves are actually more like circlesa and parabolas… The term actually “elliptic” comes from the fact that elliptic curves emerged from the study of elliptic integrals, initially used to determine the arc length of an ellipse.

The orbit of the planets is eventually more elliptical than the elliptical curves.

Elliptic curves have some interesting geometric properties, especially because you can perform addition and multiplication on them.

Addition on elliptic curves

An addition on an elliptic curve involves selecting two points on the curve, noted $P$ and $Q$ for example, then drawing a straight line between these two points, and at the intersection of this line with the curve, noted $R$ , and simply choosing the opposite point, noted $R^{'}$ , i.e. the point whose $x$ coordinate value is the opposite of the $R$ point. This method is illustrated below.

Geometric rule for adding two points on an elliptic curve

I won’t bore you with the mathematical calculations to determine the coordinates of $R^{'}$ . The geometric rule for finding $P + Q = R^{'}$ is handy, but it does not work in all cases.
What if the points $P$ and $Q$ are in the same place ( $P = Q$ )? If $P$ and $Q$ are at the same point, we want to add $P$ to $P$ and the technique for adding $P$ to $P$ is to draw a tangent to find $R$ and deduce $R^{'}$ , its opposite, which is the result of $P + P = 2 P$ .

What happens if $P$ and $Q$ are on the same abscissa (equal $x$ coordinate values)? Well, the straight line we can draw is a vertical line that never crosses the curve to find $R$ and then $R^{'}$ . We then define a point at infinity, $O$ , such that $P + O = P$ or $P + (- P) = O$ .

Geometric rule for adding two points with the same abscissa on an elliptic curve

Multiplication on elliptic curves

Multiplication is a series of additions. Indeed, if we do $2 \times 3$ , we do $2 + 2 + 2$ or $3 + 3$ to find $6$ . On an elliptic curve, if we multiply a point $P$ by a value $k$ (so we do $k \times P$ or $k P$ ), we could repeat $k - 1$ times the operation $P + P$ . But there are more efficient ways, especially if $k$ is a very large number. Operations can be grouped to reduce the total number of operations. For example, if $k$ is $16$ , we could naively proceed with $16 - 1 = 15$ operations to calculate $k P$ : $16 P = P + P + P + P + P + P + P + P + P + P + P + P + P + P + P + P + P$ . However, we can actually proceed as follows:

Calculate $P_{1} = P + P$ .
Calculate $P_{2} = P_{1} + P_{1}$ .
Calculate $P_{3} = P_{2} + P_{2}$ .
Calculate $P_{4} = P_{3} + P_{3} = 16 P$ .

With 4 addition operations instead of 15, we get the same result!

Elliptic curves in cryptography

We have seen what elliptic curves are and how to perform addition and multiplication operations on them. So how are they used in cryptography?

Elliptic curves over finite fields

So far, we have analyzed curves that are drawn with the set of real numbers. This set is denoted $R$ and includes numbers that can be represented in integer and decimal form, such as $103.00000032$ , $0$ , $5$ , $- 4.7524454$ , $\frac{3}{2}$ … However, in cryptography, the set of integers (examples: $0$ , $1$ , $- 6$ , $4$ , $16$ , $19$ , etc.), denoted $Z$ , is used. So we are talking about a finite field. But we don’t stop there, we use integers modulo a certain prime number, which we can call $p$ , i.e. a prime field. Wait… what does that mean?
Simply put, it means that the elliptic curve will be drawn with a set of integers modulo a number $p$ . Let’s call this set $Z_{p}$ . Modulo is a mathematical operation (denoted $mod$ ) used to calculate the remainder of a Euclidean division of two integers. For example, $5 mod 2 = 1$ , because $2$ can be put twice into $5$ , leaving $1$ : $5 - 2 \times 2 = 1$ . Another example, $378 mod 59 = 24$ , because we can put six times $59$ in $378$ and that leaves $24$ : $378 - 6 \times 59 = 24$ .
Back to our elliptic curves. When we draw the elliptic curve with equation $y^{2} = x^{3} - 6 x + 2$ in $Z_{59}$ , the set of possible values is bounded between $0$ and $59$ and we obtain a kind of cloud of points.

This looks less and less like an ellipse

In fact, there is no longer any real smooth curve, since only a few values (integers) are manipulated over a given range (modulo), rather than an infinite number (real numbers). Moreover, as the modulo “loops” the values back into the finite field, the points bud into the set.

The set of points forms what we call a group. The number of points in a group is called the cardinality. In the end, cardinality depends on the equation chosen (the values of $a$ and $b$ are fixed) and the value of $p$ . The operations on curves discussed above remain valid in this set.

We now know what an elliptic curve is, how to perform operations on it, and how they are derived from algebraic curves for usage in public key cryptography.

Types of elliptic curves proposed for cryptography

Several initiatives have proposed elliptic curves for cryptography. Here are the most common.

The National Institute of Standards and Technology (NIST) proposes elliptic curves over prime fields and curves over binary polynomials (mathematical expressions whose coefficients are binary values: $0$ or $1$ ). The most famous is the P-256 curve with equation $y^{2} = x^{3} - 3 x + b$ , where $b$ is a constant encoded on 256 bits (a very large number indeed). This curve uses a modulo $p$ parameter coded on 256 bits, where $p = 2^{256} - 2^{224} - 2^{192} - 2^{96} - 1$ , which is also a very large number: $115792089237316195423570985008687907853269984665640564039457584007913129639935$ .
Other NIST curves are available for 192, 224, 384 and 521 bits.

There is also the Curve25519 curve proposed by Daniel J. Bernstein, whose equation is $y^{2} = x^{3} + 486662 x^{2} + x$ and uses a modulo $p = 2^{255} - 19$ . The equation does not exactly looks like what we ve seen so far, but still belongs to the family of elliptic curves. This curve offers very interesting software performance and is widely used.

Finally, let’s mention Curve448, developed by Mike Hamburg, whose equation is $y^{2} = x^{3} + 156326 x^{2} + x$ and which uses a modulo $p = 2^{448} - 2^{224} - 1$ . This curve is therefore defined on 448 bits and is designed for high performance.

Discrete logarithm problem on elliptic curves

A cryptographic algorithm seeks to make a problem unsolvable for anyone (an attacker, for instance) who does not legitimately possess the necessary elements to achieve it, usually keys. A well-known cryptographic problem is the Discrete Logarithm Problem (DLP). This consists, if we know a value $A$ , in finding a value $a$ such that $A = g^{a} mod p$ (raising $g$ to the power $a$ is called exponentiation) with $g$ a given number and $p$ a very large prime number. It is extremely difficult to find $a$ . This problem is notably used by the Diffie-Hellman (DH) key exchange protocol. It allows two entities (often referred to as Alice and Bob in cryptography educational content) to agree on a common secret without explicitly transmitting it to each other, which is very commonly used in network protocols to exchange a symmetrical encryption key:

Alice and Bob (no, I’m not being original here) choose a prime number $p$ and a number $g$ .
Alice chooses a number $a$ which she keeps secret.
Alice calculates $A = g^{a} mod p$ and sends it to Bob. Even if an attacker intercepts $A$ , he won’t be able to find the secret number $a$ .
Bob chooses a number $b$ which he keeps secret.
Bob calculates $B = g^{b} mod p$ and sends it to Alice. Even if an attacker intercepts $B$ , he won’t be able to find the secret number $b$ .
Alice calculates the secret $s = g^{b a} mod p = g^{b a} mod p$ on her side and Bob calculates the same secret $s = g^{a b} mod p = g^{a b}$ on his side.

We’re all set. Alice and Bob are in possession of the same shared secret. I recommend the associated Wikipedia page, where this can be understood with color exchanges in addition to numbers.
We have manipulated numbers here, whereas the use of elliptic curves in cryptogaphy sets out a similar problem but manipulating curves, where, starting from a point $P$ on the curve, we seek to find the number $k$ such that $Q = k P$ . This problem is called the Elliptic Curve Discrete Logarithm Problem (ECDLP). The differences with DLP are the use of points on an elliptic curve rather than numbers, and the use of multiplication instead of exponentiation. The parameters to be chosen are the type of equation (choose $a$ and $b$ ) and the prime number $p$ . This determines the number of points in the cloud of points that is the elliptic curve. The more points there are (the greater the cardinality), the higher the level of security, as the problem (ECDLP) is complex to solve. The advantage of ECDLP over DLP is the use of smaller numbers.
Now, let’s take a look at the cryptographic applications in which ECDLP is used in practice.

ECDH key exchange

The adaptation of the Diffie-Hellman protocol for key exchange using elliptic curves is called Elliptic Curve Diffie-Hellman (ECDH) and is a fairly simple protocol in the final analysis:

Alice and Bob (them again!) choose an elliptic curve (they fix $a$ and $b$ ), the prime number $p$ (the modulo) and a point $G$ (the chosen letter $G$ - of the point $G$ - comes from the word “generator”, nothing else…) on the curve.
Alice chooses a number $a$ which she keeps secret.
Alice calculates the point $A = a G$ and sends it to Bob.
Bob chooses a number $b$ which he keeps secret.
Bob calculates the point $B = b G$ and sends it to Alice.
Alice calculates the secret $s = a B = a b G$ on her side and Bob calculates $s = b A = b a G$ on his side.

That’s it. Alice and Bob are in possession of the same shared secret, but having operated on an elliptic curve. Here, I’ve noted the points calculated on the curve $A$ and $B$ just not to always use $P$ and $Q$ …

ECDSA digital signatures

Digital signatures validate the authenticity and non-repudiation of an electronic document, and are widely used in our daily lives: digital certificates for websites, emails, software, etc. Digital signatures are based on public key cryptography. The signature is generated from a hash of the document (calculated using a hash function) by encrypting this hash with the signer’s private key. It is sent along with the document. The receiver can then verify the signature by decrypting it with the signer’s public key and comparing the obtained hash with that of the document, which it recalculates on its own. If the hashes are the same, the signature is valid.

Digital signature process and verification

Several algorithms exist for signature generation and verification. These include the Digital Signature Algorithm (DSA) and Rivest-Shamir-Adleman Probabilistic Signature Scheme (RSA-PSS).
With elliptic curves, there are two main algorithms: Elliptic Curve Digital Signature Algorithm (ECDSA) and Edwards-curve Digital Signature Algorithm (EdDSA). I propose to analyze ECDSA, which is widely used in network protocols such as Transport Layer Security (TLS) or Secure SHell (SSH), or in cryptocurrency transactions such as bitcoin.
Generating signatures on elliptic curves with ECDSA gives the following procedure (you’ll have to get a bit hung up, but I have made a diagram below):

Alice, the signer, and Bob, the receiver, choose an elliptic curve (they fix $a$ and $b$ ), the prime number $p$ (the modulo) and a point $G$ on the curve. The number of points on the curve is $n$ .
Alice has a private key which is in fact a number $d$ .
Bob knows Alice’s public key, which corresponds to a point $P = d G$ .
Alice generates a hash of the document to be signed. This hash, noted $h$ , is assimilated to a number between $0$ and $n - 1$ .
Alice chooses a random number $k$ between $1$ and $n - 1$ and calculates $Q = k G$ , a point on the curve whose coordinates are noted $(x, y)$ . Here $k$ is a nonce (a random or pseudo-random number used only once), which makes the process probabilistic and not deterministic.
Alice calculates $r = x mod n$ and $s = \frac{h + r d}{k} mod n$ .
The document signature is then the pair of values $(r, s)$ and is sent to Bob along with the document.
Note that the size of the signature is directly dependent on the size of the coordinates used for the curve. For example, if the curve is defined on 256 bits, $r$ and $s$ will each have a size of 256 bits, giving a signature of 256 + 256 = 512 bits.

To verify a document’s $(r, s)$ signature, here’s what Bob has to do (let’s hang on a little longer, the diagram is not far away):

Bob generates a fingerprint of the received document, which we write down as $h$ .
Bob calculates $Q = \frac{h}{s} G + \frac{r}{s} P$ , where $P$ (which is $d G$ ) is Alice’s public key, known to Bob, and $G$ is the base point on the curve. We can therefore write $Q =$ frac{h+rd}{s}G$.
In his calculation of $Q$ , Bob replaces $s$ with its value (as a reminder, $s = \frac{h + r d}{k} mod n$ ): $Q = k G$ .
If the document fingerprint $h$ recalculated by Bob is the correct one, from the signature (containing the fingerprint calculated by Alice and the abscissa of $Q$ calculated by Alice) and Alice’s public key, if $Q$ (of coordinates $(x, y)$ ) recalculated by Bob has an abscissa $x$ of the same value as the $x$ transmitted via the signature by Alice, then the signature is valid.

ECDSA signature and verification process

To sum up, the signature of a sent document comprises the abscissa of a point calculated by multiplying by a random number a base point known to the signer and receiver on an elliptical curve, as well as a value calculated from the abscissa of this point, the fingerprint of the document and the signer’s private key. Verification of this signature involves calculating a point from the base point on the curve, the recalculated fingerprint of the received document, the values of the received signature and the signer’s public key. If the abscissa of this calculated point corresponds to the abscissa value transmitted in the signature, the signature is correct.

Clearly, the ECDSA algorithm is more complex than RSA, which consists in performing the following operation:

Alice generates a signature $y = x^{d} mod n$ , where $x$ is the fingerprint of the document to be signed and $d$ and $n$ are Alice’s private key.
Bob verifies the signature by first calculating $x = y^{e} mod n$ , where $y$ is the received signature and $e$ and $n$ are Alice’s public key. Then it compares $x$ with the fingerprint of the received message.

So what is the advantage of ECDSA over RSA?
The use of elliptic curves actually makes it possible to handle shorter keys. With RSA, it is generally considered that a key of at least 2048 bits is required to guarantee a satisfactory level of security. With ECDSA, a 256-bit elliptic curve is considered satisfactory. Signature generation with ECDSA is therefore faster, but the length of ECDSA signatures is shorter (at least 4 times shorter). Verification time remains equivalent or slightly faster with RSA, due to the simplicity of the operation undertaken via RSA.

To illustrate this, I have integrated and tested the execution speed calculation of RSA, ECDSA and EdDSA signatures in my tool called cryptauditor, which measures the execution speed of cryptographic algorithms. At the time of writing this, the measurements were carried out on a MacBook Pro with an Intel Core i5 2.4 GHz Quad-Core processor with 16 GB memory and running macOS Ventura (version 13.3.1). When using a 3072-bit RSA key and 256-bit ECDSA and EdDSA elliptic curves, here’s the result:

$ python3 cryptauditor.py -s SIGN-ALL -k 3072 -r 10000
Performing 10000 rounds of RSA-PSS signature and verification with a 3072-bit random key on 1KB of random data hashed with SHA-256
Performing 10000 rounds of ECDSA signature and verification with a 256-bit (P-256) elliptic curve on 1KB of random data hashed with SHA-256
Performing 10000 rounds of EdDSA signature and verification with a 256-bit (Ed25519) elliptic curve on 1KB of random data hashed with SHA-512
Signature speed ranking:
1 - EdDSA - 0.693ms (+0.0ms)
2 - ECDSA - 0.785ms (+0.092ms)
3 - RSA-PSS - 4.188ms (+3.495ms)
Verification speed ranking:
1 - RSA-PSS - 0.732ms (+0.0ms)
2 - ECDSA - 1.552ms (+0.82ms)
3 - EdDSA - 2.128ms (+1.396ms)

Practice has confirmed theory!

ECIES Encryption

There are a number of encryption algorithms adapted to elliptic curves. Probably the most famous elliptic curve encryption algorithm is the Elliptic Curve Integrated Encryption Scheme (ECIES), which is described as hybrid because it combines asymmetric and symmetric cryptography. For Alice to encrypt a $M$ message for Bob:

Alice and Bob agree on a curve and a base point $G$ , a Key Derivation Function (KDF) and an authenticated encryption algorithm (such as AES-GCM).
Bob generates a public-private key pair where a secret random number $k$ is the private key and $P = k G$ is the corresponding public key.
Alice shares her public key $P$ with Bob.
Alice chooses a random number $r$ and calculates the point $Q = r G$ which is an ephemeral key (valid for one use only).
Alice calculates an ECDH shared secret $S = r P$ .
Bob derives a key $K$ from $S$ using KDF.
Bob encrypts the message $M$ with the key $K$ and the authenticated encryption algorithm, then transmits the encrypted or ciphertext $C$ , the tag $T$ and $Q$ to Alice.

For Alice to decrypt the cipher $C$ and verify the received tag $T$ :

Bob calculates a shared ECDH secret $S = k Q$ . Here $k Q = k r G = r P$ , which is the same secret calculated by Alice on her side.
Alice derives the key $K$ from $S$ using the KDF.
Alice checks the tag $T$ and decrypts the cipher $C$ using $K$ and the authenticated encryption algorithm to recover the message $M$ . We observe that ECIES clearly uses symmetrical encryption (using a shared key K) determined by asymmetrical cryptography (using ECDH).

Data encryption with elliptic curves is less common than key exchange or signatures, due to limitations on the size of data that can be encrypted.

Conclusion

In this article, we discovered together what elliptic curves are and how they are useful in cryptography for key exchange, digital signature or encryption. Elliptic curves are now widely used in many network protocols and software applications, offering excellent security and interesting performance.

Sources

Jean-Philippe AUMASSON, Serious Cryptography - No Starch Press, 312 pages, 2017.
IETF - RFC 6090 - Fundamental Elliptic Curve Cryptography Algorithms: https://datatracker.ietf.org/doc/html/rfc6090. Consulted on 07/05/2023.
Miximum - Un peu de crypto avec les courbes elliptiques: https://www.miximum.fr/blog/cryptographie-courbes-elliptiques-ecdsa/. Consulted on 07/05/2023.
Desmos - Graphing Calculator: https://www.desmos.com/calculator. Consulted on 07/05/2023.
www.graui.de - Elliptic Curves over Finite Fields : https://graui.de/code/elliptic2/. Consulted on 07/05/2023.
Wikipedia - Curve448: https://en.wikipedia.org/wiki/Curve448. Consulted on 07/05/2023.
Wikipédia - Diffie-Hellman key exchange: https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange. Consulted on 07/05/2023.
Wikipedia - Curve448: https://en.wikipedia.org/wiki/Curve448. Consulted on 07/05/2023.
GitHub - thibaut-probst - cryptauditor: https://github.com/thibaut-probst/cryptauditor. Consulted on 07/05/2023.
Wikipedia - Integrated Encryption Scheme: https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme. Consulted on 07/05/2023.