The Cryptographic Backbone of Bitcoin
Elliptic Curve Cryptography (ECC) is at the heart of Bitcoin transactions because it allows participants in the Bitcoin network to sign a transaction with their private key and anyone in the network can verify that the transaction was signed by the “owner” of the private keys, without ever revealing these private keys. This is possible thanks to some clever cryptographic principles and a bit of abstract mathematics.
The term “Elliptic Curve Cryptography” might sound scary at first, but the underlying mathematics are actually not that complicated to learn, they are just abstract and will be new to most people who haven’t studied higher-level math. My goal is to break down the key principles underpinning ECC and deconstruct them in a way that anyone with a basic understanding of mathematics can understand how they work. There are really only two fields of abstract math that one needs to understand in order to understand ECC and they are finite fields and elliptic curves. Once one understands these two fields one can combine the two to get elliptic curves over finite fields, which is exactly what the cryptography used in Bitcoin is based on. From there it is only a small step to understanding the exact elliptic curve that Bitcoin uses and how the signing and verification algorithm works at a deep and technical level.
In order to break down the math behind ECC I have written 5 articles in a series of articles that walk the reader through each of the key components, step by step. Here’s a breakdown of the article series:
-
Finite Fields: Covered in this article. They form the basis for mathematical operations of the elliptic curve used in Bitcoin.
-
Elliptic Curves (over real numbers): They define the key operation used in ECC, which is how we generate a public key from a private key.
-
Elliptic Curves over Finite Fields: Combining elliptic curves and finite fields brings us to the type of elliptic curve that Bitcoin uses. Understanding this section is the key to understanding public key cryptography.
-
Bitcoin’s Curve: Bitcoin uses an elliptic curve defined by specific parameters, which will be easy to understand after understanding the third article.
-
Elliptic Curve Cryptography and ECDSA: The cryptographic signature scheme used in Bitcoin. This is where the magic happens.
Finite Fields
Finite Fields are algebraic structures with a finite number of elements, where you can perform addition, subtraction, multiplication, and division (except by zero) just like in regular arithmetic. However, unlike the familiar field of real numbers, finite fields have a limited number of elements, which leads to some intriguing properties that make them perfect for cryptographic applications. Each operation within a finite field results in another element from the same set, making it a closed system. But how could a field with a finite set of elements and operations such as addition and multiplication possibly guarantee that each operation results in another element from the same set? For example, if we had a set with 11 elements, 0 to 10, inclusive, and we added 9 and 10, we should get 19, which is not in the set… how does this work?
This is where modular arithmetic comes in, which is at the heart of finite field mathematics.
Modular Arithmetic
The simplest example of a finite field is the set of integers modulo a prime number p, denoted as Fₚ. This field consists of integers 0, 1, 2, …, p−1 and all arithmetic operations are performed modulo p. For example, in the field F5, addition and multiplication wrap around when they exceed 4, making 4 + 2 equivalent to 1. This works thanks to the modulo operation.
The modulo operation (often denoted as “%”) is a common operation in programming to do things like creating cycles or doing time calculations. This is often called Modular Arithmetic and is sometimes referred to as “clock math”. To understand why this is the case, think about an analogue clock, where the hour hand wraps around after 12. The result of this wrapping around is that the 14th hour of the day looks the same as the 2nd hour of the day on the clock. This is exactly the same logic that underlies the modulo operation, which simply computes the remainder after dividing one number by another. 2 divided by 12 is zero with a remainder of 2 and 14 divided by 12 is 1 with a remainder of 2. But the modulo operation only returns the modulo so in modular math 14 and 2 are “congruent” modulo 12, which is usually indicated using a triple-equal sign: 14 ≡ 2 mod 12.
Fun fact: Some European countries actually have a 24-hour time system so they might refer to 2pm as 14 o’clock and mean exactly the same thing.
Modular arithmetic “wraps around” not only for addition but for multiplication and subtraction as well.
The set of integers modulo a prime is the kind of finite field that we are dealing with for Bitcoin’s cryptography so we will only focus on this type of finite field here.
Properties of a finite field
Finite fields have 6 key properties:
-
Closure: If a and b are in the set, a + b and a ⋅ b are in the set.
-
Associativity: The way in which elements are grouped in operations does not change the result, i.e. (a + b) + c = a + (b + c) and (a ⋅ b) ⋅ c = a ⋅ (b ⋅ c).
-
Commutativity: The order of the elements does not affect the outcome of addition and multiplication, i.e. a + b = b + a and a ⋅ b = b ⋅ a.
-
Distributivity: Multiplication distributes over addition, i.e. a ⋅ (b + c) = a ⋅ b + a ⋅ c.
-
Identity Elements: There exist identity elements for addition (0) and multiplication (1).
-
Inverses: Every non-zero element has a multiplicative inverse, and every element has an additive inverse.
Let’s briefly walk through each one of these properties using an example to illustrate that a finite field consisting of a set of integers modulo a prime fulfills all of them:
Closure
Let’s use the finite field with prime order 23 (i.e. all integers from 0 to 22) as our finite field. In this field the result of the addition 15 + 21 is equal to 13 because (15 + 21) % 23 = 36 % 23 = 13. In other terms, the remainder when dividing 36 by 23 is 13. Remember that all of our operations are defined using the modulus, that’s why this is the case.
Modulo operations actually work on negative values as well. -15 % 23 is equal (congruent) to 8 because -15 is 8 away from -23. Similar to “normal” math where the negative of a given number is its additive inverse, which means that the sum of a number and its additive inverse is zero, we have the same in finite field addition: 15 + (-15) = 0 because -15 ≡ 8 mod 23 and therefore (15 + 8) % 23 = 0.
The same is true for multiplication, where (10 ⋅ 15) % 23 = 12 because 10 ⋅ 15 = 150, which is divisible by 23 6 times (138) with a remainder of 12. Multiplicative inverse is a bit more complicated, and we’ll talk about it more below.
Associativity
For addition we have: ((10 + 12) + 15) % 23 = (10 + (12 + 15)) % 23 = 14. This is obvious when we first sum all of the integers up and then do the modulus operation, but it still works if we do the modulus operation after every addition. For the second equation above, for example, we first add 12 and 15, which is 27. 27 % 23 = 4 and that added to 10 is 14.
For multiplication we have: ((10 ⋅ 12) ⋅ 15) % 23 = (10 ⋅ (12 ⋅ 15)) % 23 = 6. This is because 10 ⋅ 12 ⋅ 15 = 1800, which is divisible by 23 78 times with a remainder of 6.
Commutativity
The fact that the order of operation doesn’t matter for both addition and multiplication should be obvious at this point.
Distributivity
Multiplication distributes over addition, so that (10 ⋅ (12 + 15)) % 23 = (10 ⋅ 12 + 10 ⋅ 15) % 23 = 17, because 10 ⋅ (12 + 15) is 270, which is divisible by 23 11 times with a remainder of 17.
Identity Elements
It should be clear at this point that adding 0 to any element modulo the prime order as well as multiplying any element by 1 modulo a prime order leave the original element unchanged, as the identity elements do in normal math as well.
Inverses
We already showed that a non-zero element has an additive inverse, which is the element that results in zero when added to the original element. For 15 in the finite field of order 23, the additive inverse is 8. This is congruent to -15 % 23 but is also equal to 23–15. The additive inverse of any non-zero element a in a finite field with prime order p will always be equal to p-a.
The multiplicative inverse of a non-zero finite field element is the most difficult concept to grasp about finite fields but it is essential to understand because it also explains how division works and it’s what makes finite fields a field.
Multiplicative Inverse
The multiplicative inverse of a non-zero element a in a finite field Fₚ is another element b in Fₚ such that:
a ⋅ b ≡ 1 mod p
In simpler terms, multiplying a by b will result in 1 (the identity element for multiplication) within the finite field. This is similar to normal math, where the reciprocal of a number x is just 1/x, so that for example 7 ⋅ 1/7 = 1.
Suppose we are working in the finite field F23. If we want to find the multiplicative inverse of 7, we need to find a number x such that:
7 ⋅ x ≡ 1 mod 23
After checking different values, we find that x=10 works because 7 ⋅ 10 = 70 and 70 % 23 = 1.
Solving for x in F23 is easy because we can just try out all the integers from 0 to 22 until we find the answer but what if we are dealing with a much larger field with a prime order in the billions, trillions or even higher?
There are two commonly used efficient ways of finding the multiplicative inverse of a finite field element: Extended Euclidean Algorithm and a clever trick using a mathematical theorem called Fermat’s Little Theorem.
How the multiplicative inverse enables division
Having a way to get the multiplicative inverse allows us to do division in a finite field. Dividing by a finite field element then just turns into multiplying by the multiplicative inverse of that element. This might sound complicated, but it’s very similar to regular division.
In regular arithmetic, dividing by a number a is the same as multiplying by its reciprocal 1/a. For example, dividing 6 by 2 is the same multiplying 6 by 1/2, i.e. 6/2 = 6 ⋅ 1/2 = 3.
In a finite field, the concept is the same, but instead of a reciprocal, we use the multiplicative inverse.
Let’s continue using our finite field F23. Suppose we want to divide 6 by 7 in this field. This means we need to multiply 6 by the multiplicative inverse of 7.
From our previous discussion, we know that the multiplicative inverse of 7 in F23 is 10 because:
7 ⋅ 10 ≡ 1 mod 23
So, instead of dividing 6 by 7, we multiply 6 by 10:
6 ⋅ 10 mod 23 = 14
This means that in F23, 6/7 ≡ 14 mod 23.
This approach is consistent across all operations in a finite field, making the field a closed and well-defined system where every non-zero element has an inverse, ensuring that division is always possible (except by zero).
It might seem strange and a bit abstract to see something like 6/7 = 14 but that is why this type of math is called “abstract math”. The important thing is that using the operations as defined above using modulo p, we have a perfectly well-defined system that has all of the properties that a finite field needs to have.
At this point you’ve learned everything about fintie fields that is relevant to understanding ECC as it is used in Bitcoin. The next article covers elliptic curve, the second pillar of the mathematics underpinning ECC: