Points On An Elliptic Curve

Calculating Points On An Elliptic Curve

The first big epiphany was on the last page. Arithmetic on elliptic curve points does not work the way I assumed.

However, it is completely normal, in its way. It adheres to the same basic rules as does arithmetic on numbers. Order doesn't matter, grouping doesn't matter, subtraction is built from negating and then adding, and multiplication can be built from adding.

The second big epiphany (at least for me) was realizing how to generate a set of points on an elliptic curve. It is much easier than I thought it would be! The trick is to see how it's based on modulo arithmetic. I knew what the modulo operation did, but I didn't understand how to apply it to this problem.

The modulo operation greatly simplifies what we must do. Only a limited set of numbers can be involved, simplifying matters. But at the same time, the modulo operation helps to make it impractical for an attacker to figure out our private key.

Let's see how it works.

We Will Only Use a Few of the Numbers

From here forward, we do everything with integers — 0, 1, 2, and so on. No floating-point numbers like 12.345 or π or e. So, arithmetic with integers. Grade-school math.

Simplifying things further, we will only use some of the integers.

We need to select a prime number p. Everything we do will be restricted to the range 0, 1, 2, ..., p−1. You will see that described as a prime field and written as 𝔽_p.

We will apply modulo p to everything. You can think of the modulo operator as being division, throwing away what you normally think of as the answer and keeping the remainder.

An easier way to think of it is that the result must be in the range 0, 1, 2, ..., p−1. You simply subtract or add p enough times to get the result into that range.

Let's use 13 for our prime number p. Some numbers are already in 𝔽₁₃, the range 0, 1, 2, ..., 12:
0 modulo 13 = 0
8 modulo 13 = 8
12 modulo 13 = 12

Other numbers, continuing out to infinity, are larger than p−1 and must have p subtracted enough times to get them into the range:
13 modulo 13 = 0
16 modulo 13 = 3
24 modulo 13 = 11
30 modulo 13 = 4
40 modulo 13 = 1
444 modulo 13 = 2

For that last one, we could use a calculator to divide 444 by 13, see what the whole number is (plus a messy remainder), and subtract away the whole number part.

$ bc -l
444/13
34.15384615384615386514
444 - 34*13
2
^D

444 modulo 13 = 2

Negative numbers, continuing out to negative infinity, need to have p added enough times to get them into the range:
−5 modulo 13 = 8
−17 modulo 13 = 9
−444 modulo 13 = 11

$ bc -l
-444/13
-34.15384615384615384615
-444 + 35*13
11
^D

−444 modulo 13 = 11

Modulo On Both Sides

This is what I was missing. The modulo operation applies to both sides, simultaneously. We're doing modulo integer arithmetic. We aren't solving cubic equations, which is difficult. We're finding matches, which is child's play.

Above I showed you that:
24 modulo 13 = 11
-444 modulo 13 = 11
And so, in the prime field 𝔽₁₃, 24 and -444 are the same. That is, they both refer to the same value in the set 0, 1, 2, ..., 12.

Let's Do An Example

Let's use this elliptic curve:
y² = x³ − 2x + 2
That has a pleasant shape if we make a smooth plot over the real numbers:

However, we don't care about the infinite collection of real number x,y points on this curve. We will only use integers, and only those integers in the prime field 𝔽_p. Let's keep using 13 for our prime number p, so that means the range 0, 1, 2, ..., 12.

So, for both x and y in the range 0, 1, 2, ..., 12 we will calculate both
y² modulo 13
and
(x³ − 2x + 2) modulo 13

Now we look for matches, I have highlighted them with color. 0, 1, 3, 4, and 10 all appear in both tables in their third columns. Some other members of field 𝔽₁₃ occur only in one table, or not at all. 9 and 12 appear only in the first table, 2, 6, 7, and 11 appear only in the second table, and 5 and 8 don't appear in either one.

Let's start with 0. Find the row in each table with 0 in the last column.

And so for the (x,y) point (5,0) the equation:
y² modulo p = (x³ + ax + b) modulo p
reduces to:
0 = 0
The two sides are equal, the equation is satisfied, and so (5,0) is a point on the curve. It's no longer a smooth continuous curve, it's a collection of points and we just found one.

The x table has one row with 1 in the last column, where x = 1. But the y table has two such rows, where y = 1 and y = 12.

And so we have found two more points on the discrete version of the curve: (1,1) and (1,12).

For 3 on both sides, there is one value of x and two of y, adding (12,4) and (12,9).

For 4 on both sides, we add (8,2) and (8,11).

For 10 on both sides, we add (3,6) and (3,7).

The full list is: (5,0), (1,1), (1,12), (12,4), (12,9) (8,2), (8,11) (3,6), (3,7)

We can plot these. Other than the point with y = 0, we see vertical symmetry about the horizontal line where y is p/2.

However, the smoothly curving line is nowhere to be seen! All we have is a handful of points, and the shape has been folded in upon itself because of the modulo operation applied to both axes. It's just a handful of points because I'm using a tiny prime modulus to show you how this works. For a real world problem we use an enormous modulus, frustrating any thought of a brute-force search through that space of points.

Making This Real

The above example is intentionally trivial, to make it easy to follow. It uses a ridiculously small prime modulus. Practical curves use much larger prime modulus values, and they usually use much larger constants in the curve equation.

For example, the secp256k1 curve is:
y² = x³ + 7
with a prime modulus:

p = 2256 − 232 − 977
  = 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,908,834,671,663

NIST's P-256 or secp256r1 curve is:

y2 = x3 + 41,058,363,725,152,142,129,326,129,780,047,268,409,114,441,015,993,725,554,835,256,314,039,467,401,291

with a prime modulus:

p = 2256 - 2224 + 2192 + 296 - 1
  = 115,792,089,210,356,248,762,697,446,949,407,573,530,086,143,415,290,314,195,533,631,308,867,097,853,951

See the SafeCurves site for a great explanation of how to select safe curve definitions for use in elliptic-curve cryptography. Spoiler alert: the NIST curves aren't safe.

The Arithmetic Is Fast

You add and double points using the same algebra I showed you on the previous page, with the added step of modulo p on every calculation.

All the calculations are done with integers, and computers are fast with integers, even very large ones.

Below is a YubiKey, a small device that you can use for authentication, physical access control, digital signing, and other security-related tasks. It can handle certificates and key files containing a wide variety of asymmetric and symmetric ciphers, but what it does natively is elliptic-curve cryptography.

So How Do We Encrypt And Decrypt?

We have selected some curve definition and accompanying prime modulus p. We have also openly selected a generator point G on the curve, and a prime number n that is the order of G. (n is the smallest positive number such that nG = 𝒪)

You randomly select your private key d, an integer from the range 1, 2, ..., n−1. You then calculate your public key Q:
Q = dG

A simple way to calculate Q is:
Q = dG = G + G +...+ G    (d times)

Think of what happens. The first G + G addition doubles G, an operation we saw before. Then you add another G to that result, and then another G, each time passing a line through the latest summation point and the original G and finding the third intersection point and negating it:
draw the line, intersect, reflect
draw the line, intersect, reflect
draw the line, intersect, reflect
...

But remember, we also apply the modulo operation to the x and y coordinates. So it's really:
draw the line, intersect, reflect, modulo
draw the line, intersect, reflect, modulo
draw the line, intersect, reflect, modulo
...

The summation points jump all over the curve in what appears to be a chaotic fashion. You would say that it "looks random" but it's totally deterministic, much like a hash output.

The original point G generates the apparently chaotic sequence of summation points in the series to reach the final sum Q.

It is not practical to solve for d given G and Q, because Q is calculated using multiplication based on addition of points on an elliptic curve. P and Q are points on an elliptic curve, they aren't numbers that we can punch into our calculator with:
p ÷ q = d

We can't directly divide points in the arithmetic of elliptic curves. Rather than divide, you would try to find the multiplicative inverse.

If you attack this by adding G over and over, from time to time you will hit the public key but for the wrong reason. You're looking for the private key d that is the number of hops into this sequence, and there are many false-positive possible matches.

Remember that we're dealing with a huge number of curve points. So many that it takes a 256-bit or 384-bit or 521-bit number to count them. That means that the number of false-positive possible matches we would have to test becomes overwhelming. It's possible to discover the private key d this way, but it is not practical.

You could solve for d by calculating a discrete logarithm. However, we know of no efficient solution for the discrete logarithm problem.

Also remember that we don't want to encrypt bulk data with ECC. We want to use elliptic-curve cryptography to create digital signatures, or to agree on a shared secret session key that we will use with a fast symmetric cipher such as AES. And so let's look at...

Elliptic-Curve Diffie-Hellman Key Agreement

We want to do ECDH, or really ECDHE, Elliptic-Curve Diffie-Hellman Ephemeral key agreement. This provides perfect forward secrecy, simplified as "A breach today does not expose secrets from the past." Each session uses an ephemeral key, used only for that one session.

We'll use the usual suspects, Alice and Bob. They have decided on parameters for their system. Parameters a and b for their elliptic curve and a prime modulus p, a generator point G on the curve, and a prime number n that is the order of G.

Now Alice and Bob want to communicate. Each generates a new ephemeral key pair, just for this communication. First, randomly select a private key, an integer d in the range 1 through n−1. This must be unpredictable, unguessable, so it needs a good source of entropy or randomness. Then calculate a public key, Q = dG.

Alice has a key pair:
d_A = private key,
Q_A = public key
(calculated from d_AG)

Bob has a key pair:
d_B = private key,
Q_B = public key
(calculated from d_BG)

They exchange public keys. They must be careful to do that with authentication, each verifying that they're receiving the public key of the legitimate other end, to prevent a MitM or man in the middle attack. So, send your ephemeral public key verified by a digital signature made with your long-term identity, proved by a long-term public key wrapped in a digital certificate created by a trusted CA or Certificate Authority.

Once they are both certain that they have the other's public key, each of them says "Our shared secret key K for this session is my private key multiplied with their public key."
   Alice says: K = d_AQ_B
   Bob says: K = d_BQ_A
But look at what that really means:
   Alice says: K = d_AQ_B = d_Ad_BG
   Bob says: K = d_BQ_A = d_Bd_AG
And so they agree on that shared K. No one else can do anything but try to guess it, because calculating it requires private key information.

This is not unconditional security, in theory it is possible that an attacker could guess one or more private keys. But the private keys should be randomly selected from a field with about 2²⁵⁶ or more choices.

2256 = 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936

What Security Concerns Remain?

If you found an efficient solution for the factoring problem or the discrete logarithm problem or DLP, you would have defeated the security of RSA or ECC, respectively, as you could derive the private key from its public key.

Number theory, including primality and factoring, has been of interest since pre-Classical Greece. Elliptic curves don't have as long a track record, but their study certainly isn't brand new. We probably won't suddenly discover a much better way to factor the product of large primes or calculate discrete logarithms.

But an attacker doesn't necessarily need to.

Solving those trapdoor problems would be sufficient to defeat RSA and ECC, but we don't have absolute knowledge that it's necessary.

That is, there might be a way to derive an RSA private key without factoring the relevant number, or to derive an ECC private key without calculating the discrete logarithm. We don't currently know how to do either of those things, but we don't have proof that they can't happen.

And, the attacker may not have to work mathematically, because the private key might be exposed. It might be leaked by a cryptography library, as the Heartbleed bug in OpenSSL did. Or by information leakage in a speculative execution attack such as Spectre, Meltdown, and several others. Or potentially by flawed memory management in the operating system itself.

Implementations can correctly implement algorithms and protocols, but leak information through branch timing and cache timing, or other side-channel exposures.

The SafeCurves project argues that many commonly used curves have security problems, including the NIST P-224, P-256, and P-384 curves, also known as secp224r1, secp256r1, and secp384r1.

OpenSSL and ECC

On a Red Hat or Oracle Linux system we have limited choices because they have built openssl to only support FIPS 140 algorithms. On Oracle Linux 8 I see:

# openssl version
OpenSSL 1.1.1g-fips  21 Apr 2020
# openssl ecparam -list_curves
  secp224r1 : NIST/SECG curve over a 224 bit prime field
  secp256k1 : SECG curve over a 256 bit prime field
  secp384r1 : NIST/SECG curve over a 384 bit prime field
  secp521r1 : NIST/SECG curve over a 521 bit prime field
  prime256v1: X9.62/SECG curve over a 256 bit prime field 

There are many standards defining elliptic curves, each with their own nomenclature. The five above are part of the U.S. NIST cryptography standard FIPS 140.

prime256v1 is what U.S. NIST calls P-256, and it's also called secp256r1. You can use either the prime256v1 or P-256 parameter (but not secp256r1) with the openssl command.

secp224r1, secp256r1 (a.k.a. P-256 and prime256v1), secp384r1, and secp521r1 have what NIST says are randomly chosen parameters, hence the "r" in their name.

secp256k1 is a Koblitz curve. It instead has parameters that exchange a few bits' worth of security for a significant computational speed advantage. That's just a few bits out of 256, so secp256k1 and secp256r1 should have comparable security. That is, as long as there has been no funny business with the supposedly "random" parameter selection of all the secp*r1 curves.

In 2013 The New York Times reported that NSA had influenced NIST to include a deliberate weakness the the Dual_EC_DRBG random bit stream generator and its associated elliptic curve.

Once that came out, many cryptographers seem to feel that while there's no specific reason to distrust NIST-defined elliptic curve algorithms, we certainly can't have absolute confidence in them.

In other words, just how "random" are those supposedly random curve parameters? Might they look random but actually embody a backdoor? We have no way of knowing.

See the SafeCurves project for analysis and discussion of elliptic curve design. They describe security problems with both secp256k1 and secp256r1.

On a Mint Linux or Debian system we have a much broader list of choices. Not to suggest that these are all good ideas. Why would you choose to use a much smaller prime field as with secp112r1 or sect113r1 when a small device like a YubiKey can handle 256-bit fields, over twice the number of bits?

# openssl version
OpenSSL 3.0.2 15 Mar 2022 (Library: OpenSSL 3.0.2 15 Mar 2022)
# openssl ecparam -list_curves
  secp112r1 : SECG/WTLS curve over a 112 bit prime field
  secp112r2 : SECG curve over a 112 bit prime field
  secp128r1 : SECG curve over a 128 bit prime field
  secp128r2 : SECG curve over a 128 bit prime field
  secp160k1 : SECG curve over a 160 bit prime field
  secp160r1 : SECG curve over a 160 bit prime field
  secp160r2 : SECG/WTLS curve over a 160 bit prime field
  secp192k1 : SECG curve over a 192 bit prime field
  secp224k1 : SECG curve over a 224 bit prime field
  secp224r1 : NIST/SECG curve over a 224 bit prime field
  secp256k1 : SECG curve over a 256 bit prime field
  secp384r1 : NIST/SECG curve over a 384 bit prime field
  secp521r1 : NIST/SECG curve over a 521 bit prime field
  prime192v1: NIST/X9.62/SECG curve over a 192 bit prime field
  prime192v2: X9.62 curve over a 192 bit prime field
  prime192v3: X9.62 curve over a 192 bit prime field
  prime239v1: X9.62 curve over a 239 bit prime field
  prime239v2: X9.62 curve over a 239 bit prime field
  prime239v3: X9.62 curve over a 239 bit prime field
  prime256v1: X9.62/SECG curve over a 256 bit prime field
  sect113r1 : SECG curve over a 113 bit binary field
  sect113r2 : SECG curve over a 113 bit binary field
  sect131r1 : SECG/WTLS curve over a 131 bit binary field
  sect131r2 : SECG curve over a 131 bit binary field
  sect163k1 : NIST/SECG/WTLS curve over a 163 bit binary field
  sect163r1 : SECG curve over a 163 bit binary field
  sect163r2 : NIST/SECG curve over a 163 bit binary field
  sect193r1 : SECG curve over a 193 bit binary field
  sect193r2 : SECG curve over a 193 bit binary field
  sect233k1 : NIST/SECG/WTLS curve over a 233 bit binary field
  sect233r1 : NIST/SECG/WTLS curve over a 233 bit binary field
  sect239k1 : SECG curve over a 239 bit binary field
  sect283k1 : NIST/SECG curve over a 283 bit binary field
  sect283r1 : NIST/SECG curve over a 283 bit binary field
  sect409k1 : NIST/SECG curve over a 409 bit binary field
  sect409r1 : NIST/SECG curve over a 409 bit binary field
  sect571k1 : NIST/SECG curve over a 571 bit binary field
  sect571r1 : NIST/SECG curve over a 571 bit binary field
  c2pnb163v1: X9.62 curve over a 163 bit binary field
  c2pnb163v2: X9.62 curve over a 163 bit binary field
  c2pnb163v3: X9.62 curve over a 163 bit binary field
  c2pnb176v1: X9.62 curve over a 176 bit binary field
  c2tnb191v1: X9.62 curve over a 191 bit binary field
  c2tnb191v2: X9.62 curve over a 191 bit binary field
  c2tnb191v3: X9.62 curve over a 191 bit binary field
  c2pnb208w1: X9.62 curve over a 208 bit binary field
  c2tnb239v1: X9.62 curve over a 239 bit binary field
  c2tnb239v2: X9.62 curve over a 239 bit binary field
  c2tnb239v3: X9.62 curve over a 239 bit binary field
  c2pnb272w1: X9.62 curve over a 272 bit binary field
  c2pnb304w1: X9.62 curve over a 304 bit binary field
  c2tnb359v1: X9.62 curve over a 359 bit binary field
  c2pnb368w1: X9.62 curve over a 368 bit binary field
  c2tnb431r1: X9.62 curve over a 431 bit binary field
  wap-wsg-idm-ecid-wtls1: WTLS curve over a 113 bit binary field
  wap-wsg-idm-ecid-wtls3: NIST/SECG/WTLS curve over a 163 bit binary field
  wap-wsg-idm-ecid-wtls4: SECG curve over a 113 bit binary field
  wap-wsg-idm-ecid-wtls5: X9.62 curve over a 163 bit binary field
  wap-wsg-idm-ecid-wtls6: SECG/WTLS curve over a 112 bit prime field
  wap-wsg-idm-ecid-wtls7: SECG/WTLS curve over a 160 bit prime field
  wap-wsg-idm-ecid-wtls8: WTLS curve over a 112 bit prime field
  wap-wsg-idm-ecid-wtls9: WTLS curve over a 160 bit prime field
  wap-wsg-idm-ecid-wtls10: NIST/SECG/WTLS curve over a 233 bit binary field
  wap-wsg-idm-ecid-wtls11: NIST/SECG/WTLS curve over a 233 bit binary field
  wap-wsg-idm-ecid-wtls12: WTLS curve over a 224 bit prime field
  Oakley-EC2N-3: 
	IPSec/IKE/Oakley curve #3 over a 155 bit binary field.
	Not suitable for ECDSA.
	Questionable extension field!
  Oakley-EC2N-4: 
	IPSec/IKE/Oakley curve #4 over a 185 bit binary field.
	Not suitable for ECDSA.
	Questionable extension field!
  brainpoolP160r1: RFC 5639 curve over a 160 bit prime field
  brainpoolP160t1: RFC 5639 curve over a 160 bit prime field
  brainpoolP192r1: RFC 5639 curve over a 192 bit prime field
  brainpoolP192t1: RFC 5639 curve over a 192 bit prime field
  brainpoolP224r1: RFC 5639 curve over a 224 bit prime field
  brainpoolP224t1: RFC 5639 curve over a 224 bit prime field
  brainpoolP256r1: RFC 5639 curve over a 256 bit prime field
  brainpoolP256t1: RFC 5639 curve over a 256 bit prime field
  brainpoolP320r1: RFC 5639 curve over a 320 bit prime field
  brainpoolP320t1: RFC 5639 curve over a 320 bit prime field
  brainpoolP384r1: RFC 5639 curve over a 384 bit prime field
  brainpoolP384t1: RFC 5639 curve over a 384 bit prime field
  brainpoolP512r1: RFC 5639 curve over a 512 bit prime field
  brainpoolP512t1: RFC 5639 curve over a 512 bit prime field
  SM2       : SM2 curve over a 256 bit prime field