In previous post, we’ve got some general ideas about ECDSA, this post will focus on intuitions behind secp256k1
, the set of parameters Bitcoin used. Before we dive in, we can get a glimpse of what it looks like(secp256k1.png).
More info: Recommended Elliptic Curve Domain Parameters: page 15.
I. Base point and order
1. Base point and it’s generated group
The example in previous post is : . Or state in another away
We started from , a base point. By multiplying with respectivly, we generated a group of 28 points(the last point is the point at infinity):$$(0, 1), (6, 19), (3, 13), (13, 16), (18, 3), (7, 11), (11, 3), (5, 19), (19, 18),$$
If we starts from another point in the above group, we will see a very interesting property: the points generated by multiply this point are still in this group. Figure 3.1-3.27 show 27 base points and the group generated by them respectivly. One last base point does not show here is infinity point .By definition , the generated group of consisits of one point: itself.
If we count the number of generated points of each group we will find another interesting property. There are 12 base points, each of them generates the same 28 points group(27 points + ). There are 6 base points, each of them generates a group of 14 points. There are 6 other base points each of them genertates a group of 7 points. There are 3 base points each of them generates a group of 3 points. Point generates a group of 1 point.
Base Point | # of Generated Points | Divisor of 28? |
---|---|---|
(0,1)(0,22)(1,7)(1,16)(3,10)(3,13)(9,7)(9,16)(18,3)(18,20)(19,5)(19,18) | 28 | yes |
(6,4)(6,19)(7,11)(7,12)(12,4)(12,19) | 14 | yes |
(5,4)(5,19)(13,7)(13,16)(17,3)(17,20) | 7 | yes |
(4,0)(11,3)(11,20) | 4 | yes |
1 | yes |
The interesting property is: 28,14,7,4,1 are all divisors of 28. Is it a coincidence? No, it’s not. Before prove this property, let’s see where does this 28 come from.
2. The order of the curve
This 28 is called the order of the curve. It is determined by the elliptic curve and . Why? Let’s figure it out step by step.
First, have 23 possible results:
If is an integer, how many possible results will have? Since in the ‘mod’ world only remainders matter, so it has at most 23 results. Actually, it’s far less than 23,since
Specifically, there are 12 possible results:
How about ? Still only remainders matter, so it has at most 23 results. Since , we need to check whether these 23 results match the above 12 results.
There are 27 matched points:
plus point , altogether 28 points. Use the same method, we can get the order of is 48 and the order of is 520, etc. Actually, there is a better method called Schoof Algorithm, with which we can get the order of the curve without go through every candidate points. In practice, such as Bitcoin, the order of the curve is very high. It’s impossible to go through every point. With Schoof Algorithm we can still get the order. You can find the Python code of Schoof Algorithm here. Try some small parameters youself.
Reference:
Elliptic Curve Cryptography
3. The order of a base point
The nubmer of points in the generated group of a base point is called the order of a base point. In the case of , the order of each base point is a divisor of 28. For example, the order of (0,1) is 28 and the order of (6,4) is 14. Based on Lagrange’s theorem, we can prove that the order of a base point is a divisor of the order of the curve. Sometimes the order of the curve is a prime. And a prime has only two divisors: 1, and the prime itself. Therefore, except the order of point is 1, the order of all other base points is equal to the order of the curve.
II. Parameters in secp256k1
1. The elliptic curve
In secp256k1, . So the elliptic curve is
where
2. The order of the curve
In secp256k1, the order of the curve, denoted by , is
in decimal, it’s
3. Base point
In secp256k1, base point is , where
4. The order of the base point
We can verify the order of the curve is a prime, with the help of this Python code. Therefore, except the order of point is 1, the order of all other base points, including G, is .
5. Cofactor
By definition, cofactor
Obviousely, in secp256k1, .