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.
Section 1: Parameters used in ECC
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
256 - 2
32 - 2
9 - 2
8 - 2
7 - 2
6 - 2
4 - 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:
![](https://ip.bitcointalk.org/?u=https%3A%2F%2Fwebtricks.website%2Fimage%2FeccGraph2.png&t=665&c=RLrB2qk5OITuBA)
Similarly G point is nothing but a point on graph with very large coordinates like this:
![](https://ip.bitcointalk.org/?u=https%3A%2F%2Fwebtricks.website%2Fimage%2FeccGraph1.png&t=665&c=oLi3zeCFh3HTkg)
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.
Section 2: Formulas used in ECC
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.
Section 3: ECC in Bitcoin
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://bitcointalk.org/index.php?topic=5223167.0 . 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.
Section 4: What makes ECC safe?
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.