Jump to content
Nytro

Blockchain 101 - Elliptic Curve Cryptography

Recommended Posts

Blockchain 101 - Elliptic Curve Cryptography

Blockchain-101-Elliptical-Curve-Cryptography.png

In this series of articles, I’m aiming to give you a solid foundation for blockchain development. In the last article, we gave an overview of the foundational math, specifically, finite fields and elliptic curves. In this article, my aim is to get you comfortable with elliptic curve cryptography (ECC, for short). This lesson builds upon the last one, so be sure to read that one first before continuing.

The Magic of Elliptic Curve Cryptography

Finite fields are one thing and elliptic curves another. We can combine them by defining an elliptic curve over a finite field. All the equations for an elliptic curve work over a finite field. By “work”, 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!

Of course, the elliptic curve graphed over a finite field looks very different than an actual elliptic curve graphed over the Reals. An elliptic curve over real numbers looks like this:

 

Blockchain101-graphs-06.png

 

An elliptic curve over a finite field looks scattershot like this:

Blockchain101-graphs-10.png

How to calculate Elliptic Curves over Finite Fields

Let’s look at how this works. We can confirm that (73, 128) is on the curve y2=x3+7 over the finite field F137.

$ python2
>>> 128**2 % 137
81
>>> (73**3 + 7) % 137
81

The left side of the equation (y2) is handled exactly the same as  in a finite field. That is, we do field multiplication of y * y. The right side is done the same way and we get the same value.

Exercise

True or False: Point is on the y2=x3+7 curve over F223

1. (192, 105)
2. (17, 56)
3. (200, 119)
4. (1, 193)
5. (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 given two other points on the curve. In a finite field, this still holds true, though not as intuitively 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
P= (73, 128)   P= (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 1/27, we have to use field division as we learned last time.

Python:

>>> pow(27, 135, 137)
66
>>> (106*66) % 137
9

We get s=106/27=106*66 % 137=9. Now we can calculate the rest: 

x= s2-x1-x= 92-46-73 = 99
y= s(x1-x3)-y= 9(73-99)-128 = 49 
 

We can confirm that this is on the curve:


492% 137 = 72 = (993+7) % 137 
 

P1+P= (99, 49)

 

Exercise

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. A group, remember, is a set of numbers 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. We can add G again to get 3G, 4G and so on. We do this until we get to 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). Given that (x,y) is on the curve (x,-y) is on the curve since the left side of the elliptic curve equation has a y2. Adding these produces a point that’s got infinity for both x and y. This is what we call the identity. 

 

It turns out that calculating sG = P is pretty easy, but given G and P, it’s difficult to calculate s without checking every possible number from 1 to n-1. This is called the Discrete Log problem and it’s very hard to go backwards if n is really large. This s is what we call the secret key.

Because the field is finite, the group is also finite. What’s more, if we choose the elliptic curve and the prime number of the field carefully, we can also make the group have a large prime number of elements. Indeed, that’s 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 is the number of bits in the prime field.

The big thing to note about this curve is that n is fairly close to p. That is, most points on the curve are in the group. This is not necessarily a property shared in other curves. As a result, we have something pretty close to 2256 possible secret keys.

How Big Is 2256?

Note that 2256 is a really large number. It’s around 1077, which is way more than the number of atoms in our galaxy (1057). It’s basically inconceivable 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 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/faster computers, the 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

$ python2
>>> 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. This means that we always mod p for these operations.

Next, let’s confirm that G has order n. That is, nG = 1. This is going to require the use of a python library called pycoin. It has all of the secp256k1 curve parameters that we can check. Similar libraries exist for other languages. Note that the actual process is a bit more complicated and the reader is encouraged to explore the implementation for more details.

 

G = (79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

n = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

$ python2:
>>> n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
>>> 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 donated with “s” or some other lower case 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:

Python:

>>> from pycoin.ecdsa import generator_secp256k1 as g
>>> secret = 999
>>> x, y = (secret*g).pair()
>>> print(hex(x), hex(y))
('0x9680241112d370b56da22eb535745d9e314380e568229e09f7241066003bc471L', '0xddac2d377f03c201ffa0419d6596d10327d6c70313bb492ff495f946285d8f38L')

Exercise

1. Get the public points for s in (7, 1485, 2128, 2240+231) in the secp256k1 curve.
2. Confirm the resulting points lie on the secp256k1 curve.

Highlight to reveal answers:

  1. (5CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC, 6AEBCA40BA255960A3178D6D861A54DBA813D0B813FDE7B5A5082628087264DA), (C982196A7466FBBBB0E27A940B6AF926C1A74D5AD07128C82824A11B5398AFDA, 7A91F9EAE64438AFB9CE6448A1C133DB2D8FB9254E4546B6F001637D50901F55), (8F68B9D2F63B5F339239C1AD981F162EE88C5678723EA3351B7B444C9EC4C0DA, 662A9F2DBA063986DE1D90C2B6BE215DBBEA2CFE95510BFDF23CBF79501FFF82), (9577FF57C8234558F293DF502CA4F09CBC65A6572C842B39B366F21717945116, 10B49C67FA9365AD7B90DAB070BE339A1DAF9052373EC30FFAE4F72D5E66D053)

SEC Format

The private keys are just 256 bit numbers, but the public keys are actually 2 different 256-bit numbers. This means that we need to serialize them. The same organization (Standards for Efficient Cryptography) created a format for this very purpose. There are two versions, compressed and uncompressed. Let’s start with the uncompressed version:

The first point from exercise 1 above is:

(x, y) = (5CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC, 6AEBCA40BA255960A3178D6D861A54DBA813D0B813FDE7B5A5082628087264DA)

 

In uncompressed SEC, we concatenate the byte “04”, then the X-coordinate and then the Y-coordinate. It looks something like this in hex:

045CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC6AEBCA40BA255960A3178D6D861A54DBA813D0B813FDE7B5A5082628087264DA

 

Because the x and y coordinates are 32-bytes (256 bits) each, the length of an uncompressed SEC format public key is 65 bytes.

It turns out this is a little bit inefficient. If we know 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 above point in Compressed SEC format is this:

025CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC

This is because the y-coordinate ends in A, which is even in hex. Note that compressed keys are always 33 bytes (1 byte + 32 byte x-coordinate)

Exercise

Find the compressed and uncompressed SEC format for the public keys where the secret key is:

1. 9993
2. 123
3. 42424242 

 

Highlight to reveal answers:

  1. 049D5CA49670CBE4C3BFA84C96A8C87DF086C6EA6A24BA6B809C9DE234496808D56FA15CC7F3D38CDA98DEE2419F415B7513DDE1301F8643CD9245AEA7F3F911F9, 039D5CA49670CBE4C3BFA84C96A8C87DF086C6EA6A24BA6B809C9DE234496808D5
     
  2. 04A598A8030DA6D86C6BC7F2F5144EA549D28211EA58FAA70EBF4C1E665C1FE9B5204B5D6F84822C307E4B4A7140737AEC23FC63B65B35F86A10026DBD2D864E6B, 03A598A8030DA6D86C6BC7F2F5144EA549D28211EA58FAA70EBF4C1E665C1FE9B5
     
  3. 04AEE2E7D843F7430097859E2BC603ABCC3274FF8169C1A469FEE0F20614066F8E21EC53F40EFAC47AC1C5211B2123527E0E9B57EDE790C4DA1E72C91FB7DA54A3, 03AEE2E7D843F7430097859E2BC603ABCC3274FF8169C1A469FEE0F20614066F8E

 

Conclusion

In this lesson, we learned how to combine finite fields and elliptic curves to create a finite group for use in public key cryptography. Next time, we’ll show how to convert SEC format public keys to Bitcoin Addresses and how we can sign and verify messages using the math learned here.

 

Sursa: https://eng.paxos.com/blockchain-101-elliptic-curve-cryptography

  • Thanks 1
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.



×
×
  • Create New...