Generating bitcoin public key - question for a school project :)

[jovica888]

So yes I did choose a topic for my college final exam. I will make a presentation about bitcoin and everything...

I know how technically the bitcoin address is generated but I just do not know how to generate a public key but just calculating with a "calculator"

So I tried to do it by myself...

I know that Sha256 1st private key 0000000...001 will give this public  key 0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C 4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
because this is the start point of G point (04 is the prefix then 64 letters are X and next 64 letters are Y)... So I understand this...

But in the case where I choose the second private key 0000000...002 I tried to do this...

I know for this multiplication so in my case number 2 is "10" binary so my multiplication will look like this

0 1*G

1 2*G

0 4*G

0 8*G

0 16*G

0 32*G

0 64*G

0 128*G

...

So I tried to do this manually (I know PHP GMP functions)

Hex to decimal "79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C46 55DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8" = 6376237641841063197511976314280597438149211753541909917794154839912978489307502 705320406087313832827571435203289817719151821525032884964596839752540411064

Then I did 2G and I got
1275247528368212639502395262856119487629842350708381983558830967982595697861500 5410640812174627665655142870406579635438303643050065769929193679505080822128

Now dec to hex
F37CCCFDF3B97758AB40C52B9D0E160E0537F9B65B9C51B2B3E502B62DF02F309075B4EE4D4788C ABB49F7F81C221151FA2F68914D0AA833388FA11FF621A970
And I should add 04 on the beginning ... but I found that this is not a public key of private key 2
Correct public key is
04C6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE51AE168FEA63DC 339A3C58419466CEAEEF7F632653266D0E1236431A950CFE52A

so what I did wrong?

[achow101]

Public keys are elliptic curve points, not scalars. You can't just multiple x and y by 2. You need to do elliptic curve point multiplication, which is non-trivial. Wikipedia has an entry on elliptic curve point multiplication, you should start there.

[o_e_l_e_o]

As achow has said, it's not as simple as just multiplying a point by 2.

When you add points on an elliptic curve, then what you are actually doing is drawing a straight line between those two points and finding the third point at which this line intersects the curve, and then negating it.

Adding points P and Q, to find point R:

(x_p, y_p) + (x_q, y_q) = (x_r, y_r)

To work this out, you first need to calculate the slope of the line as follows, if P and Q are different:

s = (y_q - y_p)/(x_q - x_p)

Or, if adding a point to itself as you would in your case, you calculate the slope of the line tangent to this point:

s = (3x_p² + a)/(2y_p)

You would then use the following equations to calculate the coordinates for R:

x_r = s² - x_p - x_q
y_r = -y_p + s(x_p - x_r)

[jovica888]

Can you tell me in your formulas what each element means... Also, can you tell me where is the part where the private key value  is added to equation

xr = s2 - xp - xq
yr = -yp + s(xp - xr)

I saw this so my question is - if I want to calculate only X value and get compressed key then I do not need to calculate other part

[DannyHamilton]

Can you tell me in your formulas what each element means... Also, can you tell me where is the part where the private key value  is added to equation

The private key is the number of times that the base point, G, must be added (using elliptic curve point addition) to get to the point on the curve that is the public key.  So, if your private key is 4, then your public key is the point that you get to when you perform G + G + G + G. If your private key is 7 then your public key is the point that you get to when you perform G + G + G + G + G + G + G

I suggest you do a little bit of reading and searching to learn about secp256k1 (the specific elliptic curve parameters that are used by the Bitcoin protocol) and elliptic curve point addition in geneeral, then come back with any specific questions you have about pieces of it that you don't understand.  You'll learn a lot more that way and understand it a lot better than if someone here just does your school work for you.

[o_e_l_e_o]

Can you tell me in your formulas what each element means... Also, can you tell me where is the part where the private key value  is added to equation

P, Q, and R are simply points on the elliptic curve.
x and y refer to the x and y coordinates of each point.
s refers to the slope of the line you are calculating.
a is taken from the elliptic curve equation, y² = x³ + ax + b. In bitcoin's case a = 0.

As you point out, the private key 0000...001 gives the public key which is equal to the generator point (G):

Code:

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

If you want to find the public key for private key 0000...002, then you need to calculate 2G.

So, let P = G, and let R = 2G. You then take the equation I gave above:

s = (3x_p² + a)/(2y_p)

And plug in all the numbers. Three multiplied by the x coordinate of G squared, over two multiplied by the y coordinate of G. That gives you s.

You then take the next two equations:

x_r = s² - x_p - x_q
y_r = -y_p + s(x_p - x_r)

s squared minus the x coordinate of G twice (x_p and x_q are the same since we are adding the same point (G) to itself) to find the x coordinate of 2G.
Subtract the x coordinate of 2G from the x coordinate of G, multiply by s, and subtract the y coordinate of G.

This will give you the x and y coordinates of 2G.

All this will be done modulo p, the field of the curve.

So, if your private key is 4, then your public key is the point that you get to when you perform G + G + G + G. If your private key is 7 then your public key is the point that you get to when you perform G + G + G + G + G + G + G

You wouldn't do that, though. You would do G + G = 2G, 2G + 2G = 4G, 4G + 2G = 6G, and 6G + G = 7G. Four calculations rather than six.

[garlonicon]

Step-by-step explanation: https://www.coindesk.com/markets/2014/10/19/the-math-behind-the-bitcoin-protocol/
You can start by working on small numbers, then try to use the real 256-bit values.

Can you tell me in your formulas what each element means

You have three points: P, Q, and R, where P+Q=R. Each point has its (x,y) coordinates. So you have xp, yp, xq, yq, xr, and yr.

Also, can you tell me where is the part where the private key value  is added to equation

Private key is multiplied by the base point. If you have private key equal to one, you have just the base point. If two, then it is doubled. If three, then it is the base point added to the doubled base point, and so on...

if I want to calculate only X value and get compressed key then I do not need to calculate other part

Yes, for example if you want to double your point, you can just keep your x-value and calculate "new_x=(x^4-56x)/(4x^3+28)".