In this series of articles, we aim to provide a solid foundation for blockchain development. In a previous blog post, we presented an overview of foundational math, specifically finite fields and elliptic curves. In this article, our goal is to get you comfortable with elliptic curve cryptography (ECC). This lesson builds upon the last one, so be sure to read that before continuing.
The magic of elliptic curve cryptography
Finite fields and elliptic curves are distinct concepts. We can combine them by defining an elliptic curve over a finite field. All the equations for an elliptic curve are applicable over a finite field. By “applicable”, we mean that we can do the same addition, subtraction, multiplication and division as defined in a particular finite field, and all the equations stay true. If this sounds confusing, it is. Abstract algebra is abstract!
How to calculate elliptic curves over finite fields
Let’s look at how to calculate points on elliptic curves over finite fields. To confirm that the point (73, 128) lies on the curve y2 = x3 + 7 within the finite field F137, we can do the following calculations in Python:
$ python3
>>> 128**2 % 137
81
>>> (73**3 + 7) % 137
81
The left side of the equation (y2) is treated exactly the same as in a finite field. That is, we do field multiplication of y * y. The right side is processed similarly, and both sides yield the same value, confirming that the point is indeed on the curve.
Exercise 1
True or False: The point is on the y2 = x3 + 7 curve over F223
- (192, 105)
- (17, 56)
- (200, 119)
- (1, 193)
- (42, 99)
Highlight to reveal answers: 1. True, 2. True, 3. False, 4. True, 5. False
Group law
The group law for an elliptic curve also works over a finite field:
Curve: y2 = x3 + ax + b
P1 = (x1, y1) P2 = (x2, y2)
P1 + P2 = (x3, y3)
When x1 ≠ x2:
s = (y2 – y1)/(x2 – x1)
x3 = s2 – x1 – x2
y3 = s(x1 – x3) – y1
As discussed in the previous article, the above equation is used to find the third point that intersects the curve when given two other points on the curve. In a finite field, this still holds true, although it might not be as intuitive since the graph is a large scattershot. Essentially, all of these equations work in a finite field. Let’s see in an example:
Curve: y2 = x3 + 7
Field: F137
P1 = (73, 128) P2 = (46, 22)
Find P1+P2
First, we can confirm both points are on the curve:
1282% 137 = 81 = (733 + 7) % 137
222% 137 = 73 = (463 + 7) % 137
Now we apply the formula above:
s = (y2 – y1)/(x2 – x1) = (22 – 128)/(46 – 73) = 106/27
To get 106/27, we have to use field division as we learned last time.
$ python3
>>> pow(27, 135, 137)
66
>>> (106*66) % 137
9
We get s =106/27 = 106*66 % 137 = 9. Now we can calculate the rest:
x3 = s2 – x1 – x2 = 92 – 46 – 73 = 99
y3 = s(x1 – x3) – y1 = 9(73 – 99) – 128 = 49
We can confirm that this is on the curve:
492% 137 = 72 = (993 + 7) % 137
P1 + P2 = (99, 49)
Exercise 2
Calculate the following on the curve: y2 = x3 + 7 over F223
1. (192, 105) + (17, 56)
2. (47, 71) + (117, 141)
3. (143, 98) + (76, 66)
Highlight to reveal answers: 1. (170, 142), 2. (60, 139), 3. (47, 71)
Using the group law
Given a point on the curve, G, we can create a nice finite group. Remember, a is a set of numbers that are closed under a single operation that’s associative, commutative, invertible and has an identity.
We produce this group by adding the point to itself. We can call that point 2G. Then, we can add G again to get 3G, 4G and so forth. This continues until we reach some nG where nG=0. This set of points {0, G, 2G, 3G, 4G, … (n-1)G} is a mathematical group. 0, by the way, is the “point at infinity.” You get this point by adding (x,y) + (x,-y). Since (x,y) is on the curve, so is (x,-y) because the left side of the elliptic curve equation has a y2. When you add these together, you get a point that’s basically infinity for both x and y. This is what we call the identity in the group.
It turns out that calculating sG = P is pretty straightforward. However, given G and P, finding the value of s becomes challenging, especially without checking every possible number from 1 to n-1. This challenge is known as the Discrete Log problem, and it’s very hard to solve in reverse if n is a very large number. This complexity is the basis of what we call the secret key.
Since the field is finite, the group formed is also finite. What’s more, if we carefully choose the elliptic curve and the prime number of the field, we can ensure that the group has a large prime number of elements. This characteristic is, in fact, what defines an elliptic curve for the purposes of elliptic curve cryptography.
Defining a curve
Specifically, each ECC curve defines:
- elliptic curve equation (usually defined as a and b in the equation y2 = x3 + ax + b)
- p = Finite Field Prime Number
- G = Generator point
- n = prime number of points in the group
The curve used in Bitcoin is called secp256k1 and it has these parameters:
- Equation y2 = x3 + 7 (a = 0, b = 7)
- Prime Field (p) = 2256 – 232 – 977
- Base point (G) = (79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
- Order (n) = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
The curve’s name is secp256k1, where ‘SEC’ stands for Standards for Efficient Cryptography, and ‘256’ represents the number of bits in the prime field.
A key point to note about this curve is that the value of n is relatively close to p. This implies that most points on the curve are included in the group, a characteristic that is not necessarily shared by other curves. As a result, we have something pretty close to 2256 possible secret keys.
How big is 2256?
Note that 2256 is an extraordinarily large number. It’s around 1077, which is way more than the number of atoms in our galaxy (1057). The enormity of 2256 makes it virtually impossible to calculate all possible secret keys as there are simply too many of them. A trillion computers doing a trillion operations every picosecond (10–12 seconds) for a trillion years is still less than 1056 operations.
Human intuition often breaks down when it comes to numbers this big, perhaps because, until recently, we’ve never had a reason to think like this. If you’re thinking that all you need is more or faster computers, then the staggering numbers above haven’t sunk in!
Working with elliptic curves
To begin working with elliptic curves, let’s confirm that the generator point (G) is on the curve (y2 = x3 + 7)
G = (79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
p = 2256 – 232 – 977
y2 = x3 + 7
$ python3
>>> x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
>>> y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
>>> p = 2**256 - 2**32 - 977
>>> y**2 % p == (x**3 + 7) % p
True
Remember, we’re always working in the Prime Field of p, which means that we always apply mod p to these operations.
Next, let’s verify that G has order n. That is, nG = 1. This is going to require the use of a Python library called pycoin, which contains all of the secp256k1 curve parameters that we can check. Similar libraries exist for other programming languages. It’s important to note that the actual process is a bit more complicated, so we encourage you to explore the implementation for more details.
G = (79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
n = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
$ python3
>>> n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD036414
>>> from pycoin.ecdsa import generator_secp256k1 as g
>>> (n*g).pair() (None, None)
(None, None) is actually the point at infinity, or the identity for point-addition.
Utilizing ECC for public key cryptography
Private keys are the scalars, usually denoted with “s” or some other lowercase letter. The public key is the resulting point of the scalar multiplication or sG, which is usually denoted with “P”. P is actually a point on the curve and is thus two numbers, the x and y coordinate or (x,y).
Here’s how you can derive the public key from the private key:
$ python3
>>> from pycoin.ecdsa import generator_secp256k1 as g
>>> secret = 999
>>> x, y = (secret*g).pair()
>>> print(hex(x), hex(y))('0x9680241112d370b56da22eb535745d9e314380e568229e09f7241066003bc471L', '0xddac2d377f03c201ffa0419d6596d10327d6c70313bb492ff495f946285d8f38L')
Exercise 3
- Get the public points for s in (7, 1485, 2128, 2240+231) in the secp256k1 curve.
- Confirm the resulting points lie on the secp256k1 curve.
Highlight to reveal answers: (5CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC, 6AEBCA40BA255960A3178D6D861A54DBA813D0B813FDE7B5A5082628087264DA), (C982196A7466FBBBB0E27A940B6AF926C1A74D5AD07128C82824A11B5398AFDA, 7A91F9EAE64438AFB9CE6448A1C133DB2D8FB9254E4546B6F001637D50901F55), (8F68B9D2F63B5F339239C1AD981F162EE88C5678723EA3351B7B444C9EC4C0DA, 662A9F2DBA063986DE1D90C2B6BE215DBBEA2CFE95510BFDF23CBF79501FFF82), (9577FF57C8234558F293DF502CA4F09CBC65A6572C842B39B366F21717945116, 10B49C67FA9365AD7B90DAB070BE339A1DAF9052373EC30FFAE4F72D5E66D053)
SEC format
Private keys in ECC are represented as 256-bit numbers. However, public keys are comprised of 2 separate 256-bit numbers. This means that we need to serialize them. The same organization (Standards for Efficient Cryptography) developed a specific format for this very purpose, available in two versions: compressed and uncompressed. Let’s start with the uncompressed version:
Consider the first point from exercise 1 above is:
(x, y) = (5CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC, 6AEBCA40BA255960A3178D6D861A54DBA813D0B813FDE7B5A5082628087264DA)
In the uncompressed SEC format, we start with the byte “04”, followed by the X-coordinate and then the Y-coordinate. In hexadecimal, it looks something like this:
045CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC6AEBCA40BA255960A3178D6D861A54DBA813D0B813FDE7B5A5082628087264DA
Because the x and y coordinates are 32 bytes (256 bits), the length of an uncompressed SEC format public key totals 65 bytes.
However, this method can be somewhat inefficient. Knowing the x coordinate, there are only two possible y-coordinates, the positive and negative (odd and even in a finite field). Thus, they came up with a compressed SEC format. The first byte is “02” if y is even, “03” if y is odd. Then we concatenate the x-coordinate.
The compressed SEC format for the above point is:
025CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC
This is because the y-coordinate ends in ‘A’, which is even in hexadecimal. Notably, compressed keys are always 33 bytes (1 byte for the first part + 32 bytes for the x-coordinate)
Exercise 4
-
Find the compressed and uncompressed SEC format for the public keys where the secret key is:
- 9993
- 123
- 42424242
Highlight to reveal answers: 049D5CA49670CBE4C3BFA84C96A8C87DF086C6EA6A24BA6B809C9DE234496808D56FA15CC7F3D38CDA98DEE2419F415B7513DDE1301F8643CD9245AEA7F3F911F9, 039D5CA49670CBE4C3BFA84C96A8C87DF086C6EA6A24BA6B809C9DE234496808D5
04A598A8030DA6D86C6BC7F2F5144EA549D28211EA58FAA70EBF4C1E665C1FE9B5204B5D6F84822C307E4B4A7140737AEC23FC63B65B35F86A10026DBD2D864E6B, 03A598A8030DA6D86C6BC7F2F5144EA549D28211EA58FAA70EBF4C1E665C1FE9B5
04AEE2E7D843F7430097859E2BC603ABCC3274FF8169C1A469FEE0F20614066F8E21EC53F40EFAC47AC1C5211B2123527E0E9B57EDE790C4DA1E72C91FB7DA54A3, 03AEE2E7D843F7430097859E2BC603ABCC3274FF8169C1A469FEE0F20614066F8E
Conclusion
In this blog post, we covered how to combine finite fields and elliptic curves to create a finite group that’s crucial in public key cryptography. These foundational mathematics concepts are what enable the ownership of assets on a blockchain. If you are interested in learning more about cryptography, browse through this “awesome cryptography” Github repo to get inspired.
To read more from this series on blockchain 101 topics, check out our previous blog post on Foundational Math.
Considering a career in blockchain? Explore our open engineering roles.