OFF TOPIC

[ricardosuperx]

HELLO PEOPLE!
I would like a good explanation of how public keys are generated.
EQUATION OR FORMULA

y^2 = x^3 + 7
P = k * G
X = c^2 – 2px
Y = c (px – rx) – py

Private key: 1
Public key compressed : X = 0279BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798

So it should be ...

Private key: 2
Public key compressed: X =02F37CCCFDF3B97758AB40C52B9D0E160E0537F9B65B9C51B2B3E502B62DF02F30

Why public key compressed of 2 is: X = 02C6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5?

[MrFreeDragon]

It does not work in this way.

Keep in mind main thing: private key is a number (just integer), but public key is a point with x and y coordinates.
So you in your example public key was not correct for private key 1.

For private key 1 the public key is:
0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

where 04 is a prefix for uncompressed key, green part is X-coordinate and blue part is Y-coordinate.

The compressed key contains only X coordinate with the prefix 02/03 (02 for Y even, and 03 for Y odd), because Y could be received from the formula y^2 = x^3 + 7, so no need to keep Y.
The compressed key so will be:
0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

In your example you wrote only X coordinate for public key, it was not correct. Prefix 02 should also be there in order to know both coordinates.

Also, you should know that there is a basis point which was determined for elliptic curve selected for bitcoin. Basis point is usually written as G, and has coordinates:

Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

Now the public key for every pk is pk*G, so for 1 public key 1*G - actually the G basis point itself.

For pk=2 the public key is 2*G = G + G, so you should perform scalar addition for basis point with itself (you should use point doubling).
For pk=3 you just add the publik key for pk=2 with basis point G
And so on

For more details have a look at parrt 4 of this reading:
https://pdfslide.net/documents/introduction-to-bitcoin-and-ecdsa.html

[ricardosuperx]

I'm doing this:

Private key 2:

G2 * 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

Public key compressed: X = 02F37CCCFDF3B97758AB40C52B9D0E160E0537F9B65B9C51B2B3E502B62DF02F30

I'm really sad ... I'm trying to learn and the moderator deleted my previous post ... Disappointed! Thanks MrFreeDragon for the explanation

[MrFreeDragon]

-snip-
Thanks for the answer. I will correct my question.
I just wanted to understand the G + G2 point duplication part ... The public key of 2,
X =0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798.
But for me:
X = 02f37cccfdf3b97758ab40c52b9d0e160e0537f9b65b9c51b2b3e502b62df02f30

If you want to doule point P in order to receive R = P + P, you should make the following:

c = 3*P.x*Px*invert(2*P.y) % modulo
R.x = (c*c - 2*P.x) % modulo
R.y = (c*(P.x - R.x) - P.y) % modulo

modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F

For your case with P = G = Point (Gx, Gy) where:
Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

We have the following:
invert(2*P.y) = 0xb7e31a064ed74d314de79011c5f0a46ac155602353dc3d340fbeaeec9767a6a6
c = 0xcb35b28428101a303eb9d1235992ac63f58857c2f631ee6936d3aebbeddcd1b1
R.x = (c*c - 2*Gx) % modulo = 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
R.y = 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a

So we have R.x and R.y of the public key 2G = G + G (public key for private key = 2), and it is written in compressed format like:
02c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5

[ricardosuperx]

I thank you very much!
I'm trying here, I would like to do and understand without scripts or programs. I want to learn manually. I am open to further explanation. Thank MrFreeDragon

[tbct_mt2]

You can read this book, Mastering Bitcoin, of Andreas M. Antonopoulos, and the chapter 4 is what you need

Chapter 4: https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch04.asciidoc

[ricardosuperx]

-snip-
Thanks for the answer. I will correct my question.
I just wanted to understand the G + G2 point duplication part ... The public key of 2,
X =0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798.
But for me:
X = 02f37cccfdf3b97758ab40c52b9d0e160e0537f9b65b9c51b2b3e502b62df02f30

If you want to doule point P in order to receive R = P + P, you should make the following:

c = 3*P.x*Px*invert(2*P.y) % modulo
R.x = (c*c - 2*P.x) % modulo
R.y = (c*(P.x - R.x) - P.y) % modulo

modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F

For your case with P = G = Point (Gx, Gy) where:
Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

We have the following:
invert(2*P.y) = 0xb7e31a064ed74d314de79011c5f0a46ac155602353dc3d340fbeaeec9767a6a6
c = 0xcb35b28428101a303eb9d1235992ac63f58857c2f631ee6936d3aebbeddcd1b1
R.x = (c*c - 2*Gx) % modulo = 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
R.y = 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a

So we have R.x and R.y of the public key 2G = G + G (public key for private key = 2), and it is written in compressed format like:
02c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5

I have a question.
If the private key is 3 ... do I need to change the formula this way?
R = P+P+P
c = 4*P.x*Px*invert(3*P.y) % modulo
R.x = (c*c - 3*P.x) % modulo

[ricardosuperx]

You can read this book, Mastering Bitcoin, of Andreas M. Antonopoulos, and the chapter 4 is what you need

Chapter 4: https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch04.asciidoc

I read. Very interesting! Thanks, but I still have questions

[MrFreeDragon]

-snip-
I have a question.
If the private key is 3 ... do I need to change the formula this way?
R = P+P+P
c = 4*P.x*Px*invert(3*P.y) % modulo
R.x = (c*c - 3*P.x) % modulo

No, formula is ALWAYS the same. That was a formula for double the point:
c = 3*P.x*Px*invert(2*P.y) % modulo
R.x = (c*c - 2*P.x) % modulo
R.y = (c*(P.x - R.x) - P.y) % modulo

If you want to add 2 points P and Q (2 different non-zero Points) there is another formula for R = P + Q:
dx = (Q.x - P.x) % modulo
dy = (Q.y - P.y) % modulo
c = dy * invert(dx) % modulo
R.x = (c*c - P.x - Q.x) % modulo
R.y = (c*(P.x - R.x) - P.y) % modulo

For addition it does not matter if you make P + Q or Q + P, teh result will be the same.

Also, keep in mind that in elliptic curve scalar addition there are only scalar addition and scalar doubling are determined. No, direct multiplication, or no direct substraction, etc. For multiplication, the factor is splited in order to make only doublings and additions.

So, for private key = 3 you have: 3=2+1, and the public key will be 3G = 2G + 1G = doubled G + G, so first of all you should double G and receive 2G (1st formula), and then make the addition of 2 points 2G and G (2dn formula) and finally you will have 3G or pubblic key for pk = 3.

The same for every number. For example, if you want to find the public key for 13, you should present it in this form: 13 = 8 + 4 + 1 = 2^3 + 2^2 + 1, and now calculate public key for every part (for 2^2 it is doubling G, and then doubling te received result again; for 2^3 it is the dubling G 3 times, anf for 1 it is just G); as soon as you have all 3 public keys you should use addition formula 2 times: add 2^3 and 2^2 and then add the received result with G. Finally you will have the public key for pk = 13

Actully all the scripts do the same work: doubling points and adding them, nothing else. Only doubling and addition.

Good luck with manual calcualtions 

[joinfree]

Wait a minute, so are you guys suggesting that you can actually calculate or deduce the private keys of someone by just looking at the public key? I'm lost maybe a bit of clarification would help. Or I am not getting that the OP is trying to say.

[Review Master]

Wait a minute, so are you guys suggesting that you can actually calculate or deduce the private keys of someone by just looking at the public key? I'm lost maybe a bit of clarification would help. Or I am not getting that the OP is trying to say.

No that's not actually going to happen. Because this is just one integer public key, but in reality there are more integer in your private key. No scripts can deduce the private keys of someone. Even if anyone wants to do this, he/she needs a quantum computer with a minimum of 1000 qubits to expose any private key from any algorithm. In this current time, only IBM has 50 qubits of a quantum computer and Google (cooperating with NASA) has 53 qubits of quantum computer. Thought D-wave have 2000 qubits of quantum computer, but that's used only for optimization not for general purpose. So, it's will take more time to break bitcoin or other crypto-currencies private key. Also by the time passed, there will be a solution for it too. 

[ricardosuperx]

Wait a minute, so are you guys suggesting that you can actually calculate or deduce the private keys of someone by just looking at the public key? I'm lost maybe a bit of clarification would help. Or I am not getting that the OP is trying to say.

I just want to understand the math behind Bitcoin in a simple way

[ricardosuperx]

Wait a minute, so are you guys suggesting that you can actually calculate or deduce the private keys of someone by just looking at the public key? I'm lost maybe a bit of clarification would help. Or I am not getting that the OP is trying to say.

No that's not actually going to happen. Because this is just one integer public key, but in reality there are more integer in your private key. No scripts can deduce the private keys of someone. Even if anyone wants to do this, he/she needs a quantum computer with a minimum of 1000 qubits to expose any private key from any algorithm. In this current time, only IBM has 50 qubits of a quantum computer and Google (cooperating with NASA) has 53 qubits of quantum computer. Thought D-wave have 2000 qubits of quantum computer, but that's used only for optimization not for general purpose. So, it's will take more time to break bitcoin or other crypto-currencies private key. Also by the time passed, there will be a solution for it too. 

I agree with you!

[BrewMaster]

I just want to understand the math behind Bitcoin in a simple way

well that math is not very simple to learn it that easily. there is a lot of new concepts involved and the whole algorithm (elliptic curve cryptography) also has certain complexity to it.
but i have found that this page here explains things in simpler terms that could get you started on understanding the whole thing, specially while looking at the curve shapes included helps with understanding the characteristics of elliptic curves:
https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

[Review Master]

I just want to understand the math behind Bitcoin in a simple way

you can check this sources to learn more. I am also a learner and happy to be here.

https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

For more details have a look at parrt 4 of this reading:
https://pdfslide.net/documents/introduction-to-bitcoin-and-ecdsa.html

Thanks both of you for sharing this sources. I am also still learning this and happy to get in touch of you guys. Personally, i do bounty to earn something while i am learning this. But my curiosity take me into this forum while i just start leaning python and other programming language.

[archyone]

-snip-
Thanks for the answer. I will correct my question.
I just wanted to understand the G + G2 point duplication part ... The public key of 2,
X =0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798.
But for me:
X = 02f37cccfdf3b97758ab40c52b9d0e160e0537f9b65b9c51b2b3e502b62df02f30

If you want to doule point P in order to receive R = P + P, you should make the following:

c = 3*P.x*Px*invert(2*P.y) % modulo
R.x = (c*c - 2*P.x) % modulo
R.y = (c*(P.x - R.x) - P.y) % modulo

modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F

For your case with P = G = Point (Gx, Gy) where:
Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

We have the following:
invert(2*P.y) = 0xb7e31a064ed74d314de79011c5f0a46ac155602353dc3d340fbeaeec9767a6a6
c = 0xcb35b28428101a303eb9d1235992ac63f58857c2f631ee6936d3aebbeddcd1b1
R.x = (c*c - 2*Gx) % modulo = 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
R.y = 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a

So we have R.x and R.y of the public key 2G = G + G (public key for private key = 2), and it is written in compressed format like:
02c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5

Hello,

Thanks for your explanation

I'm confuse with this part : c = 3*P.x*Px*invert(2*P.y) % modulo
How get invert(2*P.y) = 0xb7e31a064ed74d314de79011c5f0a46ac155602353dc3d340fbeaeec9767a6a6 ??
Can someone provide an explanation or simply a python formula, is it the inverse modular ?

Thanks in advance

[BrewMaster]

How get invert(2*P.y) =

the full name is Modular Multiplicative Inverse and to compute ModInverse(2*P.y) you have to find a value that when multiplied by your value and divided by the prime gives 1.
you can read more about it on wikipedia:
https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
look at the examples below that.
the computation uses the extended Euclidean algorithm.
here is a python example: https://stackoverflow.com/a/9758173/10401748

[MrFreeDragon]

-snip-
I'm confuse with this part : c = 3*P.x*Px*invert(2*P.y) % modulo
How get invert(2*P.y) = 0xb7e31a064ed74d314de79011c5f0a46ac155602353dc3d340fbeaeec9767a6a6 ??
-snip-

As was explained above, the inverse for k by modulo is such value mwhere (m*k) by modulo is equal to 1.
The best way for python is to use library gmpy2 and its function gmpy2.invert(k,p) which returns the inverse value to k by modulo = p. This function is the best for python and approx. 50 times faster than any other self made calculations.

For ubuntu for example you can easily install it:

Code:

sudo apt update
sudo apt install python3-gmpy2

If it is not in repository, you can download gmpy2  from here (pls, check the correct python version): https://www.lfd.uci.edu/~gohlke/pythonlibs/#gmpy

and install it in this way (example for python ver 3.7):

Code:

python -m pip install gmpy2-2.0.8-cp37-cp37m-win_amd64.whl

If you do not want to use the gmpy2 libriary (however it is the best way), you can also use this self made inversion function:

Code:

def egcd (a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)

def inversion (m, n):
    while m < 0:
        m += n
    g, x, _ = egcd (m, n)
    if g == 1:
        return x % n
    else: print (' no inverse exist')

The function inversion requires 2 parameters: m and n, where n is the modulo and m is the number for which you would like to calculate the inverse.

[archyone]

Thanks to MrFreedragon and BrewMaster for the explanations. However I still have a question on the generation of public key with a private key other than 1 or 2 or 13 like the examples.

MrFreedragon say :
"The same for every number. For example, if you want to find the public key for 13, you should present it in this form: 13 = 8 + 4 + 1 = 2^3 + 2^2 + 1, and now calculate public key for every part (for 2^2 it is doubling G, and then doubling te received result again; for 2^3 it is the dubling G 3 times, anf for 1 it is just G); as soon as you have all 3 public keys you should use addition formula 2 times: add 2^3 and 2^2 and then add the received result with G. Finally you will have the public key for pk = 13"

My question is : why 13 = 8 + 4 +1 ? is 4 + 4 + 4 + 1 give the same result or must there be a certain rule ?
Not sure and i can't retreive the post but it seem i read something with the private key in it's binary form ?

Sorry for my noob question ^^ but bitcoin is really more complicated than I thought at the start ^^

[BrewMaster]

My question is : why 13 = 8 + 4 +1 ? is 4 + 4 + 4 + 1 give the same result or must there be a certain rule ?

they are the same.

Not sure and i can't retreive the post but it seem i read something with the private key in it's binary form ?

that's the idea. one of the methods to compute public key (which is multiplying the key numeric value by generator point) is that key (shown as d) is going to be split into smaller powers of 2 parts  (d0 + 2d1+...) then for each 1 an addition then a doubling occurs and for each 0 only point double is performed.
https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication