Elliptic Curve

Mathematics for cryptographic systems

Graph showing the shape of an elliptic curve. Equation for an elliptic curve.

An elliptic curve is used as the basis for some cryptographic systems.

The structure of the elliptic curve allows you to perform a mathematical function ("multiply") to move around the points on the curve in one direction, without being able to travel in the reverse direction. This is known as a "trapdoor function", and it's the key feature of elliptic curves that makes them ideal for use in public key cryptography.

So in short, elliptic curves have mathematical properties that make them useful for cryptography, and they're part of the digital signature system used in Bitcoin (ECDSA).

Parameters (Secp256k1)

Satoshi chose the secp256k1 curve for use with ECDSA, which has the following parameters:

# y² = x³ + ax + b
$a = 0
$b = 7

# prime field
$p = 2 ** 256 - 2 ** 32 - 2 ** 9 - 2 ** 8 - 2 ** 7 - 2 ** 6 - 2 ** 4 - 1

# number of points on the curve we can hit ("order")
$n = 115792089237316195423570985008687907852837564279074904382605163141518161494337

# generator point (the starting point on the curve used for all calculations)
$G = {
  x: 55066263022277343669578718895168534326250603453777594175500187360389116729240,
  y: 32670510020758816978083085130507043184471273380659243275938904335757337482424,
}

Secp256k1 is just the name for one of the specific elliptic curves used in cryptography. It's short for:

Why did Satoshi choose Secp256k1?

I must admit, this project was 2 years of development before release, and I could only spend so much time on each of the many issues. [...] I didn't find anything to recommend a curve type so I just… picked one.
Satoshi Nakamoto, Email to Mike Hearn (Jan 10, 2011)

Finite Field

Finite Field – A ring of integers with a finite number of elements.

The diagrams I'm using in this tutorial show a smooth elliptic curve like this:

Graph showing an elliptic curve over real numbers (showing example point at x=1.123, y=2.90107701845366).
An elliptic curve over real numbers.

However, the actual curve used in Bitcoin looks more like a scatter plot of points like this:

Graph showing an elliptic curve over a finite field mod 47 (showing example point at x=17, y=19).
An elliptic curve over a finite field (mod 47).

This is due to the fact that the curve used in Bitcoin is over a finite field of whole numbers (i.e. using mod p to restrict numbers to within a certain range), and this breaks the continuous curve you're able to get when you use real numbers.

However, even though these plots look wildly different, the mathematical operations you can perform on both of these curves still work in the same way.

Of course, the secp256k1 curve has a very large value for p, so it more closely resembles the graph below, except imagine there are about as many points on it as there are atoms in the universe:

Graph showing an elliptic curve over a finite field mod 2503 (showing example point at x=17, y=19).
An elliptic curve over a finite field (mod 2503).

Sage Math

I made the graphs on this page using Sage Math.

Install on Ubuntu:

sudo apt install sagemath

Create an elliptic curve over a rational field (real numbers):

sage: C = EllipticCurve([0,7]) # y^2 = x^3 + 7, where a=0, b=7
sage: plot(C)
sage: C.lift_x(1.123) # get example y coordinate
sage: C.lift_x(-1.834) # get example y coordinate

Create an elliptic curve over a small finite field:

Sage: F = FiniteField(47)
sage: C = EllipticCurve(F, [0, 7]) # y^2 = x^3 + 7, where a=0, b=7
sage: plot(C)
sage: C.lift_x(17) # get example y coordinate

Create the elliptic curve used in Bitcoin (will be slow):

sage: F = FiniteField(115792089237316195423570985008687907853269984665640564039457584007908834671663)
sage: C = EllipticCurve(F, [0, 7])

Why use a finite field?

Because when implementing cryptography on computers, it's easier to work with the whole numbers in a finite field (e.g. 1, 2, 3, 4, ..., p) than it is to work with an infinite amount of the real numbers (e.g. 0.911722707844879, 2.90107701845366, ...).

You risk losing accuracy when working with decimal numbers on a computer, so the precision you get with a finite set of whole numbers is better suited for cryptography.

In this rest of this tutorial I'll be showing the smooth curve just for illustrative purposes.

Elliptic Curve Mathematics

There are a few mathematical operations that you can perform on points on the elliptic curve. The two main operations are double() and add(), and these can then be combined to perform multiply().

These operations are the building blocks of elliptic curve cryptography, and are used for generating public keys and signatures in ECDSA.

Modular Inverse

tool-6623ff71192fb
Tool Icon

Modular Inverse

Find the inverse of a number with a specific modulus.

0d
0d
0d
0 secs

Before we can perform the double() and add() operations on points on the curve, we first need to be able to find the modular inverse of a number in a finite field.

The is because the double() and add() equations include the division / operation.

However, there is no straightforward division operation within a finite field of numbers. Instead, you can multiply by the inverse of a number to achieve the same result as division:

Animation showing showing the modular inverse of a number within a finite field.
In the finite field of 47, the modular multiplicative inverse of 13 is 29.

In other words, if you start at a specific number in a finite field and multiply by another number, you can "go backwards" to the number you started with by multiplying again by the inverse of the number you used for multiplication.

Obviously this is a confusing first step in to elliptic curve math, but just think of "multiplying by the inverse" as a replacement for division in modular arithmetic.

This always works if you have a prime number of elements in the finite field. A prime number cannot be divided by any other number, so it will distribute the results from modular multiplication back across each of the numbers in the field evenly (without repeating or missing some numbers). So by using a prime number as the modulus, you can guarantee that each number in the finite field will have a multiplicative inverse (or a "division" operation).

So the first step in elliptic curve mathematics is to be able to find the inverse of a number in a finite field:

Code

def inverse(a, m = $p)
  m_orig = m         # store original modulus
  a = a % m if a < 0 # make sure a is positive
  prevy, y = 0, 1
  while a > 1
    q = m / a
    y, prevy = prevy - q * y, y
    a, m = m % a, a
  end
  return y % m_orig
end
  • This function uses the extended Euclidean algorithm (you don't need to know how it works) to find the modular inverse of a number. It's just a quicker method than trying to find the inverse via brute-force.
  • Not all programming languages have a built-in "modular inverse" function, which is why you sometimes have to implement one yourself to get started with elliptic curve mathematics.

Modular inverse notation

The modular inverse of a number is typically denoted by ⁻¹ in mathematical equations.

Diagram showing the mathematical notation for the modular inverse of a number.

In the upcoming operations, the inverse of a number is sometimes found mod p (modulo the prime number), and is sometimes found mod n (modulo the number of points on the curve).

Double

tool-6623ff71199e7
Tool Icon

EC Double

Double a point on the secp256k1 elliptic curve.

Point 1
0d
0d
Point 1 + Point 1
0d
0d
0 secs

"Doubling" a point is the same thing as "adding" a point to itself.

From a visual perspective, to "double" a point you draw a tangent to the curve at the given point, then find the point on the curve this line intersects (there will only be one), then take the reflection of this point across the x-axis.

Graph showing how to double a point on an elliptic curve.
P is a general point on the curve.
s refers to the slope of the tangent.
Equation for doubling a point on an elliptic curve.

Code

def double(point)
  # slope = (3x₁² + a) / 2y₁
  slope = ((3 * point[:x] ** 2 + $a) * inverse((2 * point[:y]), $p)) % $p # using inverse to help with division

  # x = slope² - 2x₁
  x = (slope ** 2 - (2 * point[:x])) % $p

  # y = slope * (x₁ - x) - y₁
  y = (slope * (point[:x] - x) - point[:y]) % $p

  # Return the new point
  return { x: x, y: y }
end

Elliptic Curve Operations.

You're not actually "doubling" the values of the x and y coordinates of a point here (like you would do in everyday arithmetic).

The "double", "add", and "multiply" terms on this page refer to specific operations we perform with points on elliptic curves. So even though they have the same names as normal mathematical operations, they are completely different in the domain of elliptic curve mathematics.

This can get a bit confusing at times because there are also everyday "add" and "multiply" operations in amongst these equations too. The trick is to remember that:

Add

tool-6623ff711a240
Tool Icon

EC Add

Add two points on the secp256k1 elliptic curve.

Point 1
0d
0d
Point 2
0d
0d
Point 1 + Point 2
0d
0d
0 secs

As expected, "addition" of two points in elliptic curve mathematics isn't the same as straightforward integer addition, but it's called "addition" anyway.

From a visual perspective, to "add" two points together you draw a line between them, then find the point on the curve this line intersects (there will only be one), then take the reflection of this point across the x-axis.

Graph showing how to add two points on an elliptic curve.
Q is a second general point on the curve.
Equation for adding two points on an elliptic curve.

Code

def add(point1, point2)
  # double if both points are the same
  if point1 == point2
    return double(point1)
  end

  # slope = (y₁ - y₂) / (x₁ - x₂)
  slope = ((point1[:y] - point2[:y]) * inverse(point1[:x] - point2[:x], $p)) % $p

  # x = slope² - x₁ - x₂
  x = (slope ** 2 - point1[:x] - point2[:x]) % $p

  # y = slope * (x₁ - x) - y₁
  y = ((slope * (point1[:x] - x)) - point1[:y]) % $p

  # Return the new point
  return { x: x, y: y }
end

Multiply

This operation is the heart of elliptic curve cryptography.

tool-6623ff711a9da
Tool Icon

EC Multiply

Multiply a point on the secp256k1 elliptic curve.

Point 1
0d
0d
0d
Point 1 x Multiplier
0d
0d
Steps  
0 secs

Most multiplication operations in ECDSA start at the generator point G.

Now that we can double() and add() points on the curve, we can now take any point on the curve and multiply() it by an integer to get to a completely new point.

The simplest method for elliptic curve multiplication would be to repeatedly add() a point to itself until you reach the number you want to multiply by, which would work, but these incremental add() operations would make this approach impossibly slow when multiplying by large numbers (like the ones used in Bitcoin).

Thankfully, there is a faster way to perform multiplication on elliptic curves…

Double-and-add algorithm

Animation showing how to multiply a point on an elliptic curve.
3P = 2P + P (one double, one add)

A faster approach to multiplication is to use the double-and-add algorithm.

This algorithm uses both doubling and adding to reach the target multiple in as few operations as possible.

For example, if you start at 2 and want to get to 128, it's faster to perform six double() operations than it is to perform sixty-four add() operations.

But how do you know how many double and add operations you need to get to your target multiple?

Well, amazingly, if you convert any integer in to its binary representation, the 1s and 0s will provide a map for the sequence of double() and add() operations you need to perform to reach that multiple.

For example:

e.g. 1 * 21

21 = 10101 (binary)
      │││└ double and add = 21
      ││└─ double         = 10
      │└── double and add = 5
      └─── double         = 2
                            1  <- start here

Anyway, here's what elliptic curve multiplication looks like when using the double-and-add algorithm in Ruby code:

Code

def multiply(k, point = $G)
  # create a copy the initial starting point (for use in addition later on)
  current = point

  # convert integer to binary representation
  binary = k.to_s(2)

  # double and add algorithm for fast multiplication
  binary.split("").drop(1).each do |char| # from left to right, ignoring first binary character
    # 0 = double
    current = double(current)

    # 1 = double and add
    current = add(current, point) if char == "1"
  end

  # return the final point
  current
end

Summary

This article just covers the basic mathematical operations used on elliptic curves.

It's important to remember that "multiplication" on the elliptic curve is nothing like everyday multiplication. It's best to think of "elliptic curve multiplication" as a completely unique kind of operation, but we just call it "multiply" so that it has its own name. It's just unfortunate that it's so confusing.

Anyway, this multiply() operation allows you to move around points on the curve in one direction, but there is no mathematical operation that allows you to "undo" this movement, and this property is what makes elliptic curves so useful for cryptography.

All of this elliptic curve mathematics is used as the basis for the digital signature system used in Bitcoin: ECDSA (Elliptic Curve Digital Signature Algorithm).

Resources

References:

Explanations:

Tools: