Private key to public key equation

[nofiat]

Hi,

I'm trying to convert a private key to a public key.
Let's assume the following private key:
18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725
Which translates in decimal to:
11253563012059685825953619222107823549092147699031672238385790369351542642469

Now, we have the constant G:
GX : 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 -> 55066263022277343669578718895168534326250603453777594175500187360389116729240
GY : 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 ->32670510020758816978083085130507043184471273380659243275938904335757337482424

I've tried reading about the elliptic curve and some papers about it but I haven't figured out what's my next move in order to get the public key.

[1715014712]

1715014712

[1715014712]

1715014712

[aplistir]

With the right tools it is easy:
This is one example in how it can be done in Sagemath http://www.sagemath.org/, the free math program.

Code:

modi =0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
E=EllipticCurve(GF(modi), [0,7])
print E

# generator used with this curve
G=E(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8) 

PrivK=0x18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725

PubK=PrivK*G
print "Public key :", PubK

So you basically just multiply your private key with the Generator (G) and get the public key. Easy.

Actually the code could be a lot shorter, because you do not have to tell sagemath the modulus, Generator point and elliptic curve. You could just say that you want to use the secp256k1 -curve and sage will then know all the needed parameters. But I do not know how to do that, so I do it the "hard" way.

The above code prints the public key in decimal format.

Here is the output of the above code:

Code:

         	
Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size
115792089237316195423570985008687907853269984665640564039457584007908834671663
Public key :
(36422191471907241029883925342251831624200921388586025344128047678873736520530 :
20277110887056303803699431755396003735040374760118964734768299847012543114150 : 1)

[nofiat]

Thanks for your reply. Appreciated. However, it does seem like the tool is doing all the work for me. I'm trying to learn how the calculation works myself.
I did understand that you need to multiple the decimal representation of my private key with base point G, however, I did not understand how the multiplication actually works.

I did try to simply convert the private key (0x18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725 -> 11253563012059685825953619222107823549092147699031672238385790369351542642469) and multiply it by base point Gx (55066263022277343669578718895168534326250603453777594175500187360389116729240) which gives us BD4FD5FB7A2267DCBAFA00828EF916804FE307BE10C66D70DF06E7504A7252B5ACA70B176876047 473923124DD35521DC45FF99FDC337551BCE746CC7AA10F8 (which is not the public key).

[aplistir]

Thanks for your reply. Appreciated. However, it does seem like the tool is doing all the work for me. I'm trying to learn how the calculation works myself.

With numbers as big as these, it usually is a program, or programming language library that does do all the actual work. Doing these calculations by hand would take too much time.

If you are interested, here is a pdf, which explains ECC really easily and well
https://www.entrust.com/wp-content/uploads/2014/03/WP_Entrust_Zero-to-ECC_March2014.pdf

If you want to practice actually doing these calculations I recommend trying them on smaller field first.
eg:
y²=x³+7 mod 1051
would create a prime field of 1093 points.
you can choose any point from the field to be G

For doing the multiplication with actual bitcoin curve you would first need to multiple the G by 2, then multiple the result by 2  and so on. until you have done it 255 times. And save the results.
Then you will have a list of points
G, 2*G, 4*G, 8*G, 16*G ... 57896044618658097711785492504343953926634992332820282019728792003956564819968*G

for the multiplications of 2 you use these formulas:

Code:

s=(3x²+a)/(2y1) mod p
x2=s²-2x1 mod p
y2=-y1+s(x1-x2) mod p

Then you transform your private key to a binary number and lets say it is 1001101 (very short priv key )
then you can do the additions.
1 G
0 (2)
1 4G
1 8G
0 (16)
0 (32)
1 64G

The resulting public key would be:
G+4G+8G+64G

For the additions you use these formulas:

Code:

s=(y2-y1)/(x2-x1) mod p
x3=s²-x2-x1 mod p
y3=-y2+s(x2-x3) mod p

The pdf will explain these better.
Have fun  

[Anti-Cen]

Thanks for your reply. Appreciated. However, it does seem like the tool is doing all the work for me. I'm trying to learn how the calculation works myself.
I did understand that you need to multiple the decimal representation of my private key with base point G, however, I did not understand how the multiplication actually works.

I did try to simply convert the private key (0x18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725 -> 11253563012059685825953619222107823549092147699031672238385790369351542642469) and multiply it by base point Gx (55066263022277343669578718895168534326250603453777594175500187360389116729240) which gives us BD4FD5FB7A2267DCBAFA00828EF916804FE307BE10C66D70DF06E7504A7252B5ACA70B176876047 473923124DD35521DC45FF99FDC337551BCE746CC7AA10F8 (which is not the public key).

Like you, I like doing things myself and tend to work in C# on windows machines using Visual Studio and my options are to use NBitcoin from Github which is a mega large
project and build a wrapper around it or cheat and use BTC HTTP API's when really i want to use Net.Sockets and post my own bytedata off over TCP but it seems like talking to
nodes directly has been implemented in such a way that makes this far too complicated even to someone like me that before now has written a bit-torrent client from scratch.

Maybe we should team up if using the same tools

[shensu]

This part of Mastering Bitcoin may be of use to you:

https://github.com/bitcoinbook/bitcoinbook/blob/8d01749bcf45f69f36cf23606bbbf3f0bd540db3/ch04.asciidoc#elliptic-curve-cryptography-explained