# 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 𝔽_{13},
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 -l444/1334.15384615384615386514444 - 34*132^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*1311^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
𝔽_{13},
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*^{2} = *x*^{3}
− 2*x* + 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*^{2} modulo 13

and

(*x*^{3} − 2*x* + 2) modulo 13

y |
y^{2} |
modulo 13 |

0 | 0 | → 0 |

1 | 1 | → 1 |

2 | 4 | → 4 |

3 | 9 | → 9 |

4 | 16 | → 3 |

5 | 25 | → 12 |

6 | 36 | → 10 |

7 | 49 | → 10 |

8 | 64 | → 12 |

9 | 81 | → 3 |

10 | 100 | → 9 |

11 | 121 | → 4 |

12 | 144 | → 1 |

x |
x^{3}
− 2x + 2 |
modulo 13 |

0 | 2 | → 2 |

1 | 1 | → 1 |

2 | 6 | → 6 |

3 | 23 | → 10 |

4 | 58 | → 6 |

5 | 117 | → 0 |

6 | 206 | → 11 |

7 | 331 | → 6 |

8 | 498 | → 4 |

9 | 713 | → 11 |

10 | 982 | → 7 |

11 | 1311 | → 11 |

12 | 1706 | → 3 |

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 𝔽_{13}
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.

y |
y^{2} |
modulo 13 |

0 | 0 | → 0 |

1 | 1 | → 1 |

2 | 4 | → 4 |

3 | 9 | → 9 |

4 | 16 | → 3 |

5 | 25 | → 12 |

6 | 36 | → 10 |

7 | 49 | → 10 |

8 | 64 | → 12 |

9 | 81 | → 3 |

10 | 100 | → 9 |

11 | 121 | → 4 |

12 | 144 | → 1 |

x |
x^{3}
− 2x + 2 |
modulo 13 |

0 | 2 | → 2 |

1 | 1 | → 1 |

2 | 6 | → 6 |

3 | 23 | → 10 |

4 | 58 | → 6 |

5 | 117 | → 0 |

6 | 206 | → 11 |

7 | 331 | → 6 |

8 | 498 | → 4 |

9 | 713 | → 11 |

10 | 982 | → 7 |

11 | 1311 | → 11 |

12 | 1706 | → 3 |

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

*y*= 0 in the

*y*table we calculate:

*y*

^{2}modulo 13

= 0

^{2}modulo 13

= 0 modulo 13

= 0

*x*= 5 in the

*x*table we calculate:

(

*x*

^{3}− 2

*x*+ 2) modulo 13

= (5

^{3}− 2·5 + 2) modulo 13

= (125 − 10 + 2) modulo 13

= 117 modulo 13

= 0

And so for the (*x,y*) point (5,0)
the equation:

*y*^{2} modulo *p* =
(*x*^{3} + *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*^{2} = *x*^{3} + 7

with a prime modulus:

p= 2^{256}− 2^{32}− 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:

y^{2}=x^{3}+ 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:

SafeCurvesp= 2^{256}- 2^{224}+ 2^{192}+ 2^{96}- 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.*

`/dev/random`

and Entropy

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*= public key

_{A}(calculated from

*d*)

_{A}G
Bob has a key pair:

*d _{B}* = private key,

*Q*= public key

_{B}(calculated from

*d*)

_{B}G
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*

_{A}Q_{B}Bob says:

*K*=

*d*

_{B}Q_{A}But look at what that really means:

Alice says:

*K*=

*d*=

_{A}Q_{B}*d*

_{A}d_{B}GBob says:

*K*=

*d*=

_{B}Q_{A}*d*

_{B}d_{A}GAnd 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^{256} or more choices.

2^{256}= 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:

#NIST: Recommended Elliptic Curves for Government Use Certicom/SECG: SEC 2, Recommended Elliptic Curve Domain Parametersopenssl versionOpenSSL 1.1.1g-fips 21 Apr 2020 #openssl ecparam -list_curvessecp224r1 : 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 versionOpenSSL 3.0.2 15 Mar 2022 (Library: OpenSSL 3.0.2 15 Mar 2022) #openssl ecparam -list_curvessecp112r1 : 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