How to calculate public key manually?

c_atlas

member

Activity: 140

Merit: 56

Quote from: archyone on September 08, 2020, 07:39:55 AM

Hello everyone !

I know it is a very old thread but is it possible for someone to explain what is the differential at the generator point (slope ?) and why it is use in calculation ?
I see this function give the result for the private key 2 (doubling Gx) but is it possible with this formula to obtain the result for 200 (for example) or is it and another formula.

Thanks in advance

I think this graph should clear things up. The differential is the slope of the tangent line. The tangent line to G will intersect the curve at some other point, that point is -2G. On reflection over the x axis, you obtain 2G. You can keep playing this game and jumping around to get (+/-)(2^k)G for any natural number k.

archyone

newbie

Activity: 25

Merit: 1

Quote from: kn_b_y on April 19, 2016, 07:10:28 PM

Here's some working python code that generates the point of the public key for private key = 2

Code:

# Inversion using Extended Euclidean algorithm.
def EEA_invert(a, b):
   r = {}; s = {}; r[0] = a; r[1] = b; s[0] = 1; s[1] = 0
   i = 1;
   while True:
   if r[i]==0: break
   q = r[i-1]//r[i]; r[i+1] = r[i-1] - q*r[i]; s[i+1] = s[i-1] - q*s[i]
   i += 1
   return s[i-1] % b

# Bitcoin's EC parameters: see https://en.bitcoin.it/wiki/Secp256k1
G = '79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'.replace(' ', '')
gx, gy = int(G[:64], 16), int(G[64:], 16)
p = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1

# Calculate differential at the generator point.
slope = (3*gx**2)*EEA_invert(2*gy, p) % p

# Calculate x, y.
x = (slope**2 - 2*gx) % p
y = (slope*(gx - x) - gy) % p

print(hex(x), hex(y))

which yields:

Code:

('0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5',
'0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a')

Hello everyone !

I know it is a very old thread but is it possible for someone to explain what is the differential at the generator point (slope ?) and why it is use in calculation ?
I see this function give the result for the private key 2 (doubling Gx) but is it possible with this formula to obtain the result for 200 (for example) or is it and another formula.

Thanks in advance

kn_b_y

newbie

Activity: 26

Merit: 3

Here's some working python code that generates the point of the public key for private key = 2

Code:

# Inversion using Extended Euclidean algorithm.
def EEA_invert(a, b):
   r = {}; s = {}; r[0] = a; r[1] = b; s[0] = 1; s[1] = 0
   i = 1;
   while True:
   if r[i]==0: break
   q = r[i-1]//r[i]; r[i+1] = r[i-1] - q*r[i]; s[i+1] = s[i-1] - q*s[i]
   i += 1
   return s[i-1] % b

# Bitcoin's EC parameters: see https://en.bitcoin.it/wiki/Secp256k1
G = '79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'.replace(' ', '')
gx, gy = int(G[:64], 16), int(G[64:], 16)
p = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1

# Calculate differential at the generator point.
slope = (3*gx**2)*EEA_invert(2*gy, p) % p

# Calculate x, y.
x = (slope**2 - 2*gx) % p
y = (slope*(gx - x) - gy) % p

print(hex(x), hex(y))

which yields:

Code:

('0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5',
'0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a')

gmaxwell

staff

Activity: 4172

Merit: 8419

A simplistic construction that does an inversion for every add, even using extgcd (which is far from constant time), is going to be horribly slow. And probably infeasible to do by hand. Though it's more complex to explain, protective coordinates would likely be needed to have any hope of performing a point-scalar multiply by hand, along with a big precomputed table.

Evil-Knievel

legendary

Activity: 1260

Merit: 1168

apxu, it is not that hard. You just have to take care of the different operations in such factor rings.

For example the division is not a real division but the multiplication with the multiplicative inverse in the factor ring (you will need the extended euclid for that).

apxu

member

Activity: 229

Merit: 13

Quote from: Evil-Knievel on April 18, 2016, 02:27:22 PM

Exactly as Hamilton has pointed it out.
What has not yet be mentioned is that all operations are performed in the factor ring Z/nZ with n being the prime modulus of the secp256k1 curve.

Example: if n was 7 (which it isn't) then 4*4 = 16 mod 7 == 2

The modulo operations were clear for me.
I just needed a formula for point multiplication G by the private key.
Now I understand my error.
I haven't checked it yet, but I will try to calculate the public key manually and compare it with bitaddress.org

Evil-Knievel

legendary

Activity: 1260

Merit: 1168

Exactly as Hamilton has pointed it out.
What has not yet be mentioned is that all operations are performed in the factor ring Z/nZ with n being the prime modulus of the secp256k1 curve.

Example: if n was 7 (which it isn't) then 4*4 = 16 mod 7 == 2

DannyHamilton

legendary

Activity: 3388

Merit: 4615

https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Point_addition

Quote

With 2 distinct points, P and Q, addition is defined as the negation of the point resulting from the intersection of the curve, E, and the straight line defined by the points P and Q, giving the point, R.

Assuming the elliptic curve, E, is given by y² = x³ + ax + b, this can be calculated as:

apxu

member

Activity: 229

Merit: 13

I have some troubles with understanding bitcoin math.
For example, my private key is '2'
So, the public key should be (Gx,Gy) * 2
Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
So, Gx * 2 will be 0x79... + 0x79... = 0xf3... (I can calculate it in mind)
But the public key for '2' is 04C6047F9... (or 02C6047F9... in compressed form)
What is wrong with my calculations?
How to multiply the base point 0x79be66... by two and receive 0xC6047F9 ?

Topic: How to calculate public key manually? (Read 1427 times)