Saturday, October 13, 2018

What is ECC(Elliptic Curve Cryptography)?

If you want to see the real math behind secp256k1 and don't want your time to be wasted reading my unfinished article, check out https://www.coindesk.com/math-behind-bitcoin/ and https://www.cryptocompare.com/wallets/guides/how-do-digital-signatures-in-bitcoin-work/ for the math and as much explanation as possible.

The post title is a bit misleading as it is both a real question and a rhetorical one as well. I admit that when it comes to cryptography, I am very much in the dark.

Why though? Because cryptography requires a very solid understanding of algebra and I suppose geometry. The disambiguation of a 'curve' is literally the following on Wikipedia

curve is a geometrical object in mathematics.

And because both Algebra and Geometry fall within the broad subject of Mathematics, and because I said cryptography requires a very solid understanding of algebra, then you can infer I also mean Mathematics in general.
So you can also infer that if I am in the dark with cryptography, then I am actually pretty bad at maths.

How can someone who is bad at math, maintain a blog about reverse engineering? Well, programming in general does not always require the use of math operations more complex than a+b,a*b,a/b. On a fundamental level it's all maths, but the logic can be easy to follow.

Anyway, I set out to understand more about ECC, specifically the secp256k1 parameters which some of you might know are what power Bitcoin. Yes, it's Bitcoin that motivated me to write this post.
To be more specific it was Vanitygen, I've used the program before but the inner workings were...more mysterious and so I wanted to learn a bit more and boy is the rabbit hole deep.

Very often these 'curves' are represented as such a graph as shown below:


But then you are told that it actually looks like a scattered plot that seemingly looks random rather than the curve you see above.

In the Bitcoin wiki(not Wikipedia) has an article on secp256k1 with all the information taken from the SEC whitepaper located on http://www.secg.org/sec2-v2.pdf

And to save you some clicks, here is what it says:

The elliptic curve domain parameters over Fp associated with a Koblitz curve secp256k1 are specified by the sextuple T = (p, a, b, G, n, h) where the finite field Fp is defined by: 
  • p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
  • = 2256 - 232 - 29 - 28 - 27 - 26 - 24 - 1
The curve Ey2 = x3+ax+b over Fp is defined by:
  • a = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
  • b = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007
The base point G in compressed form is:
  • G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
and in uncompressed form is:
  • G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
Finally the order n of G and the cofactor are:
  • n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
  • h = 01
Properties
  • secp256k1 has characteristic p, it is defined over the prime field ℤp. Some other curves in common use have characteristic 2, and are defined over a binary Galois field GF(2n)(fancy word to mean finite field), but secp256k1 is not one of them.
  • As the a constant is zero, the ax term in the curve equation is always zero, hence the curve equation becomes y2 = x3 + 7.

And finally, from OpenSSL's ec_curve.c file, we have this little structure here that defines the above data

 static const struct {  
   EC_CURVE_DATA h;  
   unsigned char data[0 + 32 * 6];  
 } _EC_SECG_PRIME_256K1 = {  
   {  
     NID_X9_62_prime_field, 0, 32, 1  
   },  
   {  
     /* no seed */  
     /* p */  
     0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,  
     0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,  
     0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFC, 0x2F,  
     /* a */  
     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  
     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  
     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  
     /* b */  
     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  
     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  
     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x07,  
     /* x */  
     0x79, 0xBE, 0x66, 0x7E, 0xF9, 0xDC, 0xBB, 0xAC, 0x55, 0xA0, 0x62, 0x95,  
     0xCE, 0x87, 0x0B, 0x07, 0x02, 0x9B, 0xFC, 0xDB, 0x2D, 0xCE, 0x28, 0xD9,  
     0x59, 0xF2, 0x81, 0x5B, 0x16, 0xF8, 0x17, 0x98,  
     /* y */  
     0x48, 0x3a, 0xda, 0x77, 0x26, 0xa3, 0xc4, 0x65, 0x5d, 0xa4, 0xfb, 0xfc,  
     0x0e, 0x11, 0x08, 0xa8, 0xfd, 0x17, 0xb4, 0x48, 0xa6, 0x85, 0x54, 0x19,  
     0x9c, 0x47, 0xd0, 0x8f, 0xfb, 0x10, 0xd4, 0xb8,  
     /* order */  
     0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,  
     0xFF, 0xFF, 0xFF, 0xFE, 0xBA, 0xAE, 0xDC, 0xE6, 0xAF, 0x48, 0xA0, 0x3B,  
     0xBF, 0xD2, 0x5E, 0x8C, 0xD0, 0x36, 0x41, 0x41  
   }  
 };  

Although it isn't clear what 'NID_X9_62_prime_field, 0, 32, 1' is, those are field_type, seed_len, param_len and cofactor in ec_curve.c.
Right off the bat, we can identify that we have no seed, it even says so in the description, 

My very first question looking at everything was, what the hell is G ? What is a generator 'G'? Well, if you look closely it's actually the two x and y coordinates.

The order, is apparently the maximum number of valid private keys that could be generated using this curve.

Now, there is a very basic formula posted out there on the internet is 'public key = private key * base point(which would be G)'
Cool! But not really, apparently it's not that simple. Apparently the calculation involes x,y but also a and b and p, because 'a' is 0, it's essentially omitted. More on the calculation here https://www.coindesk.com/math-behind-bitcoin/

I'll update the post as we try(and likely fail often) to deconstruct everything related to ECC, so until then:

to be continued...


2 comments:

  1. Looking to get in touch, common interest, any mail/irc twitter ?

    ReplyDelete