Elliptic Curve Cryptography (ECC) plays a crucial role in securing digital assets like Bitcoin. Unlike traditional cryptographic methods, ECC provides a high level of security with smaller key sizes, making it more efficient and suitable for modern needs. This article explores the fundamentals of elliptic curves and their properties. By understanding ECC, you gain insight into the backbone of Bitcoin technology.
Definition of Elliptic Curves
An Elliptic Curve is a smooth curve in a two-dimensional plane which consists of the points satisfying the equation:
y^2 = x^3 + ax + b
and a point at infinity. We get different curves by varying the coefficients a,b.
 |
|---|
| Curves for (a=-1, b=0) and (a=-1, b=1) By GYassineMrabetTalk |
Finite Fields
In cryptography, we define the Elliptic Curve over a finite field. This means that the values of x in the curve equation are taken from a special set called a finite field. The Finite Field is a finite set of elements that satisfy the following rules under multiplication, addition, subtraction, and division operations:
Closure: The set is closed under addition and multiplication, meaning that if you add or multiply any two elements in the field, the result is also an element in the field.
Associativity: Addition and multiplication in the field are associative, meaning that the grouping of operations does not change the result. For any elements a, b, and c, this means (a + b) + c = a + (b + c) and (a * b) * c = a * (b * c).
Commutativity: Addition and multiplication are commutative in the field, which means the order of elements does not matter. For any elements a and b, a + b = b + a and a * b = b * a.
Identity Elements:
There is an additive identity (often denoted as 0), which means for any element a, a + 0 = a.
There is a multiplicative identity (often denoted as 1), which means for any element a, a * 1 = a.Inverses:
For every element a in the field, there is an additive inverse -a such that a + (-a) = 0.
For every non-zero element a, there is a multiplicative inverse a^(-1) such that a * a^(-1) = 1.Distributivity: Multiplication distributes over addition, meaning for any elements a, b, and c, the equation a * (b + c) = (a * b) + (a * c) holds true.
 |
|---|
| A plot of an Elliptic Curve over a finite field By Trshaffer |
It is a closed system for numbers where we can only use a certain limited set of values. Think of it like the numbers on a clock. If you add 9 hours to 5 o'clock, you get 2 o'clock. This is because, after 12, the numbers "wrap around." A finite field is similar: it has a fixed set of numbers, and whenever an operation exceeds this range, it wraps around, just like on a clock.
Why can't we define the curve over Real Numbers?
We could, but that would make the curve unsuitable for cryptography. Real Numbers are infinite and continuous. We cannot use this for cryptography because we want a finite set of keys, and we want each key to be discrete. Discrete values are easier to represent and operate on in binary.
In ECC, the Public key is a point on the Elliptic curve. It has x and y coordinates which look like real numbers, but they are part of a defined finite field for the curve.
Order of a Finite Field
The order of a set is the number of elements in that set. A Finite field of order n, GF(n), has n elements:
{0, 1, ..., n-1}
Modular Arithmetic
Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after reaching a certain value called the modulus. It can be thought of like a clock, where after reaching 12, it wraps around to 1 again. If we have two integers a and n, the modulus n divides a and leaves a remainder r, and we say that r is a modulo n or a mod n:
a≡r (mod n)
We can perform arithmetic operations by finding the result of the operation in mod n. See the following examples:
5 + 4 = 9
9 ≡ 4 (mod 5)
therefore: 5 + 4 ≡ 4 (mod 5)
Simple n-modulo Finite Fields
We can create a finite field using modular arithmetic. An n-modulo finite field is a set of n numbers where all operations like addition, subtraction, multiplication, and division (except by zero) are performed "modulo n"—meaning that the results are taken as the remainder after division by n. An n-modulo finite field, GF(n), where n is a prime number, satisfies the rules of a field defined above. If n is not a prime number, the set will not have multiplicative inverses for all elements which breaks the requirements for a valid field.
The Elliptic Curve Group
A group is a set with a binary operation that satisfies the closure property, associativity, every element in the set has an inverse element and it has an identity element.
The closure property means that passing any two elements of the set, through the group binary operation, will produce a result also in the set. Consider our Finite field above under the addition operator as an example.
Associativity means that in the expression a . b . c where a, b, and c are elements of the group and . is the group operator, it doesn't matter where we put parenthesis so we can freely move it around.
(a . b) . c = a . (b . c)
The identity element, O, of the group is the element that has no effect when applied to another element using the group operator:
a . O = a
For example, in basic addition, 1 + 0 = 1, adding 0 to any real number has no effect. 0 is the identity element for real numbers under addition.
The inverse of an element is its opposite and cancels it out in the group operation:
a . a^-1 = O
The Elliptic Curve points, together with the point at infinity(the identity element) form a group under the addition operator. This allows us to apply other theories from groups to Elliptic Curves. Note that the order of the group does not have to be the order of the finite field. The finite field can have elements that are not on the elliptic curve.
Inverting an Elliptic Curve Point
Given a point, P(x, y), the inverse, -P is (x, -y).
Addition of Elliptic Curve Points
The addition of points in EC is geometrically based. We:
- Add two points by drawing a straight line between them and finding the third point where the line intersects the curve then inverting this point. We invert the points to preserve the group axioms of the curve.
- When the two points are the same, we draw a tangent to the curve at this point, the inverse of the point where the tangent intersects the curve again is the result.
- Adding a point to its inverse results in the point at infinity. This is because the line between
Pand-Pis vertical and will only intersect the curve at the point at inifinity. - Adding a point to the point at infinity results in the original point.
 |
|---|
| Addition of Elliptic Curve Points By SuperManu |
Scalar Multiplication
In linear algebra, a "scalar" is a single number used to "scale" a vector. In the context of Elliptic Curve Group theory, the scalar is a single number that scales a point on the elliptic curve. We do this by adding the point, P to itself n times where n is the scalar. This is represented as n.P or nP.
Elliptic Curve Subgroups
A subgroup is a subset of elements taken from a larger group that itself forms a group under the same operation as the larger group. We can form a subgroup by taking an element, G, of the group and repeatedly scaling that element G until we reach a scalar, n, where:
nG = O (the identity element)
Trying to scale G with n + 1 will return 1G. Hence, there is a "wrap-around" at nG. The scalar n is the order of the subgroup because the subgroup has n elements and scaling beyond n results in elements we have already seen.
A subgroup generated with an element G, contains the following elements:
{O, 1G, 2G, 3G, ..., nG}
This theory applies to Elliptic Curves too. We can create an Elliptic Curve subgroup from a generator point, G, with order n. Note that a subgroup can also contain all the elements of the supergroup.
Elliptic Curve Parameters
We describe an Elliptic Curve Subgroup with the following parameters:
Order of the field, p
This refers to the number of elements of the field. Recall from our discussion on Finite Fields that our simple finite field which uses modular arithmetic must have a prime order. Therefore, when choosing the order of the field, it must be a prime number.
Generator Point, G
Recall from our discussion on "Elliptic Curve Subgroups", that, by scaling a generator element, we can create a subgroup. The Generator Point, G, is the generator for the elliptic curve subgroup.
Order of the subgroup, n
This the number of points in the elliptic curve subgroup. It is the scalar, n, where:
nG = O (identity element)
The Coefficients of the curve, a, b
Recall the curve equation for elliptic curves:
y^2 = x^3 + ax + b
The coefficients a and b are important parameters that affect the shape of the curve.
The cofactor, h
This is the ratio of the order of the group to the order of the subgroup. It tells you how much bigger the group is than the subgroup. h cannot be less than 1 because this would mean that the subgroup does not fit inside the group. When h is 1, it means that all the elements in the group are in the subgroup. When h is greater than 1, it means there are elements in the group that are not in the subgroup. In EC, for h > 1, we must check that a given point, P is in our desired subgroup before working with it. h = 1 simplifies things and we do not need to check that the point is in our subgroup.
Projected Coordinates
Some implementations of ECC, do not represent the EC point coordinates as (x, y), instead, they may use projected coordinates like the Jacobian system (X, Y, Z, T).
This allows the addition of points in a more efficient way than in affine coordinates.
The secp256k1 Curve
Bitcoin uses the secp256k1 Curve. The parameters are:
p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1
G = (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)
a = 0
b = 7
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
h = 1
Notice that n is a large prime number. This ensures a large cyclical subgroup and makes it difficult to solve the Discrete Logarithm problem.
Discrete Logarithm Problem
The discrete logarithm problem is like knowing a blender recipe for a smoothie but not being able to figure out the exact ingredients just by tasting it. Imagine you have a secret recipe where you combine a certain number of berries, but after blending, it's hard to reverse-engineer how many berries were used without trying every possibility.
In the case of elliptic curves, if you scale a point, it’s easy to get the new point. But if someone sees the result (the "smoothie") and wants to figure out what number you multiplied by (how many berries you used), it’s incredibly hard to do. This protects our secret keys in cryptography.
For any element, a, in our finite field of order p, GF(p), we can multiply a by itself n times to get a new number x which will be in our field:
x = a^n mod p
But given x and a, it is difficult to find n.
For example, In GF(5) above, we can do:
4^5 (mod 5)
4 * 4 * 4 * 4 * 4 = 1024
1024 / 5 = 204 remainder 4
4^5 = 4 (mod 5)
We can't reverse the operation and find n without checking all the possible values for n. For a large group, the possible values of n are too many, making this problem practically infeasible.
In Elliptic Curves, the problem becomes finding the scalar k such that:
Q = k.P
Secret and Public Keys
We generate pairs of keys in Public Key cryptography. Each key pair contains a public key and a secret key. A public key encrypts a message, producing a Cyphertext that can only be decrypted by the corresponding secret key. The public key can be distributed openly for anyone to use for encryption.
In Elliptic Curve Cryptography, we choose a large random scalar as our secret key, k, and generate a public key by scaling the curve's generator, G, with k. The public key is therefore a point on the curve given by:
K = k.G
With carefully selected curve parameters, we can release K to the public and the secret key, k, will remain secret, thanks to the intractability of the Discrete Logarithm Problem.
In a future article, we will discuss the signatures used in Bitcoin, how they are generated and verified.
Conclusion
In conclusion, elliptic curves provide a powerful mathematical framework for cryptographic applications, especially in systems like Bitcoin. Understanding the group structure, the importance of finite fields, and how elliptic curve points are manipulated through addition and scalar multiplication is crucial to understanding Bitcoin technology and its underlying security mechanisms.
Top comments (0)