How to calculate public key manually?

[apxu]

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 ?

[DannyHamilton]

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

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:

[Evil-Knievel]

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

[apxu]

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]

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).

[gmaxwell]

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.

[kn_b_y]

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')