Topic: What is Elliptic Curve Cryptography? Understand how is it related to Bitcoin. (Read 521 times)

Bump!

Great job. I wrote a supplement of your guide at https://bitcointalksearch.org/topic/elliptic-curve-cryptography-basics-how-it-works-5235482 which explains the basics of elliptic curve cryptography that you didn't discuss here. Reading these two topics together should give people enough knowledge to understand the scenarios which ECC is useful in and how it works.

I have heard the term elliptic curve in my math class, I'm not sure what exact math class it is but essentially I remember it to be an algebraic curve that is non-singular. And upon searching it on google (just elliptic curve), it means


Technically speaking, if I understood correctly, the curve will not intersect again itself. We can see that this topic would be related to the part where Bitcoin addresses are also safe to be publicly seen. This principle has made it impossible to get the Private key from a Public key.

I researched an article where the math behind it is discussed and it's a good read.

https://hackernoon.com/what-is-the-math-behind-elliptic-curve-cryptography-f61b25253da3

There are actually two ways you can apply double and add method. You have already mentioned one above i.e. when index is decreasing. However, there is another when index is increasing. The other one from the same Wikipedia (P is generator):


This formula is also starting from index number 0 but my formula is absolutely correct because in first step Q is 0 so point_add(Q,N) will return N. So the return value of Q after first iteration will be N while the return value of N will be double N. In next iteration (when index is 1), the values which will go in point_add will be:

Q ← point_add(N, point_double(N)).

This is similar if we omit first iteration and double N (generator point) before starting the loop.

Now compare with my formula which I posted in other thread (I remember you objected this issue there too):


I hope it is clear now.

good job on another useful topic.

if i were you, i would add a section 0 to this giving a short explanation on modular arithmetic since ECC means nothing without first understand what modular arithmetic is. it would put P and n in perspective otherwise the parameters make no sense.

minimum value for a private key is 1.
also n is defined as the order of base point G. in simple terms it shows the number of "points" that are on the curve.

technically there are only 2 definitions: point addition and point multiplication. when adding two points if they are the same, the equation can be simplified which creates the simpler version of point addition which libraries call "point double" or ECDouble as you put it.

this part doesn't sound right to me. there are different methods of calculating point multiplication, this method you are describing sounds like the Double and Add method in reverse in all of these methods you start from zero (or point at infinity) double the result and add G instead of doubling G and adding result.
from Wikipedia (P is generator):

and the reason is that we start from point at infinity as the initial value and since O + O = O and O + P = P there is no need to do it.

Thanks for explanation. I read about Secp256k1 >> https://en.bitcoin.it/wiki/Secp256k1 and found a lot of information about it https://bitcoin.stackexchange.com/questions/21907/what-does-the-curve-used-in-bitcoin-secp256k1-look-like

and found some toll for illustration of the secp256k1's elliptic curve y2 = x3 + 7 over the real numbers using calculator https://www.desmos.com/calculator/ialhd71we3.

Ever wonder why it isn't possible to guess private key from bitcoin address? How private key keeps your fund safe? How signatures can only be generated using private key but can be verified using public key? The answer to all these questions is Elliptic Curve Cryptography (ECC). Although ECC is not unique to Bitcoin and was introduced much before Bitcoin but it is one of the most important fundamental of Bitcoin. With just few lines of code, ECC ensures that funds on address remain safe and only person holding private key can access those funds.

Ok! Now let's dive deep into the topic. I will not explain the basics of Elliptic Curve Cryptography in this thread. Rather I will take essential components of ECC which are being used in Bitcoin and only explain things from Bitcoin's point of view so things remain easy to understand.


Bitcoin uses specific elliptic curve known as secp256k1. SECG have defined the exact values for various parameters that are used in the calculation for secp256k1 curve. There are total 6 parameters but we only need 3 for the calculation. Let's have a look at these three parameters first:

P = 2²⁵⁶ - 2³² - 2⁹ - 2⁸ - 2⁷ - 2⁶ - 2⁴ - 1

G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

These values may be bit confusing for now but let's understand them. P is a very large prime number which is used to calculate mod in the formula.

G is generator point. It has 3 parts:
(i) 04 which shows that point is in uncompressed form.
(ii) Next 64 characters are hexadecimal representation of X-axis of generator point which is when converted into integer looks like this: 55066263022277343669578718895168534326250603453777594175500187360389116729240
(iii) Next 64 characters are hexadecimal representation of Y-axis of generator point which is when converted into integer looks like this: 32670510020758816978083085130507043184471273380659243275938904335757337482424

You may have studied in mathematics that point (2,4) means point is 2 on X-axis and 4 on Y-axis. Something like this:



Similarly G point is nothing but a point on graph with very large coordinates like this:



Lastly, n represents the maximum integer value of private key. Any number between 0 and n is valid private key. n when converted into integer is this number: 115792089237316195423570985008687907852837564279074904382605163141518161494337.


Basically there are three formulas that make up Elliptic Curve Cryptography namely, ECAddition, ECDouble and ECMultiplication. Although we use the terms like addition, double and multiplication but these calculations are not like general addition or multiplication. These are much more complex. As I said earlier, this thread is not about Elliptic Curve Cryptography but how is it used in Bitcoin so I won't explain these formulas and how these are derived. Let's keep this thread simple and understandable.


Now comes the most important and interesting part. How ECC is used in Bitcoin!

This is the system of applying ECC on private key to calculate public key:

1. Convert the hex of private key into Binary representation.
2. Ascertain the number of characters our Binary representation have.
3. Let's say, our Binary representation have 256 characters then we have to apply ECMultiply formula 256 times. ECMultiply involves applying ECDouble on G point and then if the binary character is 1, apply ECAdd formula on the resulting value. Else if binary character is 0, ignore ECAdd and move to next character.
4. Note: We don't have to apply ECAdd formula on the first character even if it is 1.
5. Keep on repeating this and the final point we get after 256 rounds will be our public key.

Confusing? Let's understand this with an example: Since private key can be any number between 0 and n, let's assume 145 as our private key. The hex representation of our private key will be: 0xa8.

Now according to step 1, we have to convert our private key into binary which is: 10010001
Now according to step 2, we have to ascertain the length of our binary which is: 8.
Now according to step 3, we have to do ECMultiply 8 times. Let's do it:

(I am using short form D() for ECDouble and A() for ECAdd)

Round	Starting value	Binary Character	ECDouble	ECAdd	Value going next round
First	G	1	Yes	No (read step 4)	D(G)
Second	D(G)	0	Yes	No (0)	D(D(G))
Third	D(D(G))	0	Yes	No (0)	D(D(D(G)))
Fourth	D(D(D(G)))	1	Yes	Yes (1)	A(D(D(D(D(G)))),G)
Fifth	A(D(D(D(D(G)))),G)	0	Yes	No (0)	D(A(D(D(D(D(G)))),G))
Sixth	D(A(D(D(D(D(G)))),G))	0	Yes	No (0)	D(D(A(D(D(D(D(G)))),G)))
Seventh	D(D(A(D(D(D(D(G)))),G)))	0	Yes	No (0)	D(D(D(A(D(D(D(D(G)))),G))))
Eight	D(D(D(A(D(D(D(D(G)))),G))))	1	Yes	Yes (1)	A(D(D(D(D(A(D(D(D(D(G)))),G))))),G)

So this value: A(D(D(D(D(A(D(D(D(D(G)))),G))))),G) will be a point on graph having two coordinates (X,Y). This point will be our public key which is then converted in Bitcoin Address. D() means we are applying ECDouble formula on the value within brackets while A() means we are applying ECAddition formula on the value within brackets. Note that ECAddition requires two points for the calculcation hence the first point is our result value while the second point is G point.

Wanna see this code in action? Check out my other thread where I have created Bitcoin Address from private key from scratch: https://bitcointalksearch.org/topic/how-bitcoin-addresses-are-generated-understand-the-math-behind-bitcoin-5223167 . I have provided the complete ECAdd, ECDouble and ECMultiply formula in that thread as Javascript functions. You can learn in depth about these formulas from various online resources and then check their working through my code.


So we have done immense calculation in step 3. But what actually makes this calculation irreversible? Why can't be calculate private key from public key by applying ECDouble and ECAdd in reverse order (afterall we are using G as the input whose value is known to all)? The reason why ECC is so invincible is due to the use of modulus and modulus inverse in ECDouble and ECAddition formulas. So what is modulus (or mod) and modulus inverse (or mod inverse)?

Mod of any two numbers say, mod(14,6) is the remainder obtained after dividing first number with second. For example, when 14 is divided by 6 remainder is 2. So the mod of 14 and 6 is 2. Whereas mod inverse is the number which is when multiplied with first number and then divided by second number leaves the remainder of 1. For example, mod inverse of 3 and 11 is 4 because when 3 multiplied by 4 gives 12 which when divided by 11 leaves the remainder of 1.

ECC uses these two in both ECDouble and ECAdd. So after every round of ECMultiply, we are only taking remainder in next round. We are discarding any quotient obtain in calculation, which makes the reverse calculation almost impossible. For example, even if you know that the remainder is 2 and the number which divided the first number is 6, you can't certainly say that the first number is 14 because it could be 8 or 14 or 20 or so on. In ECC, we uses mod lots of times and on top of that, we are dealing with very large numbers (remember P from Section 1? P is used to calculate mod in ECDouble and ECAdd functions). So virtually it's impossible to do reverse calculation.

I hope this thread made you little more knowledgeable about Bitcoin and why it is one of the best innovation of 21st century. If you already know about ECC and think something in this thread needs to be improved, please let me know, I will make the necessary amendments.