[Solved] Fail at coding my own Secp256k1 function (Pyhon)

[SamYezi]

Fail at coding my private to public key converter script for Bitcoin (Secp256k1)

Currently going through the book "Programming Bitcoin by Jimmy Song", got stuck on page 61 (Chapter 3), but completed the exercise 5 from chapter 3. You can view the source code: here or in Github .

Even though the book is great for understanding cryptographic different concepts, highly abstracted OOP code from the book makes it somewhat harder to gaining the intuition of the fundamental low-level concepts behind key principles. That's why apart from completing exercises, I like to also code my own procedural functions that solve the same problems.

I've tried to code an ECC Secp256k1 priv-to-pub key conversion function, but my implementation... just doesn't work.

It converts numbers incorrectly.

The code for the script is down below, I've highlighted the part where the function stops

Code:

#Secp256k1 Bitcoin private to public key converter script
a = 0
b = 7
#Order of the finite field
prime = 2**256 - 2**32 - 977
#G coordinates
gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
#Order of the group G
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
#n -1 => is the number of all possible private keys
privateKey = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140

def addition(currentX, currentY, gx, gy, a, b, prime):
    if gy == 0:
        return (None, None)
    elif currentX is None and currentY is None:
        return (gx, gy)
    elif currentX == gx and currentY != gy:
        return (None, None)
    elif currentX == gx and currentY == gy and currentY == 0:
        return (None, None)
    elif currentX == gx and currentY == gy:
        s1 = (3 * pow(gx, 2, prime) + a) % prime
        s2 = (gy * 2) % prime
        s = (s1 * pow(s2, (prime - 2), prime)) % prime
        currentX = (s ** 2 - 2 * gx) % prime
        currentY = (s * (gx - currentX) - gy) % prime
    elif currentX != gx:
        s1 = (currentY - gy)
        s2 = (currentX - gx)
        s = (s1 * pow(s2, (prime - 2), prime)) % prime
        currentX = ((s ** 2) - gx - currentX) % prime
        currentY = ((s * (gx - currentX)) - gy) % prime

    return (currentX, currentY)


def secp256k1BinaryExpansion(privateKey, gx, gy, a, b, prime):
    if pow(gy, 2, prime) != (pow(gx, 3, prime) + a * gx + b) % prime:
        return "The point is not on the curve"
    coef = privateKey
    currentX, currentY = gx, gy
    resultX, resultY = None, None
    while coef:
        if coef & 1:
            resultX, resultY = addition(resultX, resultY, currentX, currentY, a, b, prime)
        currentX, currentY = addition(currentX, currentY, currentX, currentY, a, b, prime)
        coef >>= 1
    return (resultX, resultY)

#privateKey, gx, gy, a, b, prime
#Smaller numbers (Not Secp256k1). Right output for this is: (116, 55)
print(secp256k1BinaryExpansion(8, 47, 71, a, b, 223))

#Test case 2
priv = 0x45300f2b990d332c0ee0efd69f2c21c323d0e2d20e7bfa7b1970bbf169174c82
xPub, yPub = secp256k1BinaryExpansion(priv, gx, gy, a, b, prime)
xPub, yPub = xPub, yPub
print("Public key coordinates:", xPub,",", yPub)
#The right values for test case 2:
#x = 40766947848522619068424335498612406856128862642075168802372109289834906557916
#y = 70486353993054234343658342414815626812704078223802622900411169732153437188990

#Test case 2.1. Full Pulic key for test case 2:
print("Public key (hex), (Uncompressed) :", "04" + (str(hex(xPub)[2:])) + (str(hex(yPub)[2:])))
#The right public key (Uncormpressed):
#045A2146590B80D1F0D97CC7104E702011AFFF21BFAF817F5C7002446369BA9DDC9BD5DCD1B4A737244D6BB7B96E256391B8597D3A7972A6F8CA9096D4AEA1F37E
print("Public key (hex), (Compressed) :", "02" + (str(hex(xPub)[2:])))
#The right public key (Compressed):
#025A2146590B80D1F0D97CC7104E702011AFFF21BFAF817F5C7002446369BA9DDC

Link for the script

The main function uses "Binary expansion" technique, but it seems like the problem lies in the "Addition" function that doesn't have it.

To see some results I copied OOP code from the book, refactored it a bit uploaded to github and it works:

https://github.com/MaltoonYezi/Python-DSA/blob/main/Cryptography/SECP256K1OOP.py

Tried to debug the 1st code by myself, but failed. If you could help, I'd appreciate it!

Edit 1: Updated the code, here on GitHub. Works for big numbers but works correctly for small numbers.
In test case 2 coordinates for public key are right, but the public key itself is wrong

Edit 2: I've refactored the script once again and everything works now. The test case 1 values in the comments were incorrect and now it outputs the right values. Also the public key outputs are also working properly.
Thanks for your help!
 

[1713975539]

1713975539

[1713975539]

1713975539

[NotATether]

Code:

    while coef:
        if coef & 1:
            resultX, resultY = addition(currentX, currentY, gx, gy, a, b, prime)
        currentX, currentY = addition(currentX, currentY, gx, gy, a, b, prime)
        coef >>= 1

Let's unroll this loop:

- Current (x,y) is set to G
- Start at the least-significant bit
- If the bit is odd:
-- Then set Result = Current(x,y) + G [for the first iteration this means G+G]
- Set CurrentX += G [again, for the first iteration, it is G+G].

Do you see the problem here?

As you go through all of the bits, you are *adding* G to itself, this will make G, 2G, 3G, and so forth. You have to multiply the CurrentX by 2 each time, to get G, 2G, 4G, 8G, 16G,... (2^256-1)*G.

And each time the bit is odd, you are adding another G to the result which is already full of G's you're adding in succession, when you should set result = 0 in the initialization, and then you add it to Current (x,y). That is to say, Result += Current(x,y).

Binary expansion on private keys doesn't work without multiplication.

[PowerGlove]

You're almost there, change this (in secp256k1BinaryExpansion):

Code:

if coef & 1:
    resultX, resultY = addition(currentX, currentY, gx, gy, a, b, prime)
currentX, currentY = addition(currentX, currentY, gx, gy, a, b, prime)

To this:

Code:

if coef & 1:
    resultX, resultY = addition(resultX, resultY, currentX, currentY, a, b, prime)
currentX, currentY = addition(currentX, currentY, currentX, currentY, a, b, prime)

And your second test case will pass (i.e. 0x45300f2b990d332c0ee0efd69f2c21c323d0e2d20e7bfa7b1970bbf169174c82 => (40766947848522619068424335498612406856128862642075168802372109289834906557916, 70486353993054234343658342414815626812704078223802622900411169732153437188990))

I haven't checked your code carefully though, so I wouldn't consider this "working" just yet.

[SamYezi]

Code:

    while coef:
        if coef & 1:
            resultX, resultY = addition(currentX, currentY, gx, gy, a, b, prime)
        currentX, currentY = addition(currentX, currentY, gx, gy, a, b, prime)
        coef >>= 1

Let's unroll this loop:

- Current (x,y) is set to G
- Start at the least-significant bit
- If the bit is odd:
-- Then set Result = Current(x,y) + G [for the first iteration this means G+G]
- Set CurrentX += G [again, for the first iteration, it is G+G].

Do you see the problem here?

As you go through all of the bits, you are *adding* G to itself, this will make G, 2G, 3G, and so forth. You have to multiply the CurrentX by 2 each time, to get G, 2G, 4G, 8G, 16G,... (2^256-1)*G.

And each time the bit is odd, you are adding another G to the result which is already full of G's you're adding in succession, when you should set result = 0 in the initialization, and then you add it to Current (x,y). That is to say, Result += Current(x,y).

Binary expansion on private keys doesn't work without multiplication.

Ok, It is helpful. I've made a few changes. But it still doesn't work for small numbers (Don't know why),
https://github.com/MaltoonYezi/Python-DSA/blob/main/Cryptography/SECP256k1Procedural.py
Sorry, for a delayed response

[SamYezi]

You're almost there, change this (in secp256k1BinaryExpansion):

Code:

if coef & 1:
    resultX, resultY = addition(currentX, currentY, gx, gy, a, b, prime)
currentX, currentY = addition(currentX, currentY, gx, gy, a, b, prime)

To this:

Code:

if coef & 1:
    resultX, resultY = addition(resultX, resultY, currentX, currentY, a, b, prime)
currentX, currentY = addition(currentX, currentY, currentX, currentY, a, b, prime)

And your second test case will pass (i.e. 0x45300f2b990d332c0ee0efd69f2c21c323d0e2d20e7bfa7b1970bbf169174c82 => (40766947848522619068424335498612406856128862642075168802372109289834906557916, 70486353993054234343658342414815626812704078223802622900411169732153437188990))

I haven't checked your code carefully though, so I wouldn't consider this "working" just yet.

I got it, and  your suggestions are useful. I changed the code here and on Github. However It still doesn't work for small numbers (See the test case 1)
https://github.com/MaltoonYezi/Python-DSA/blob/main/Cryptography/SECP256k1Procedural.py
Sorry, for a delayed response

[j2002ba2]

...
I got it, and  your suggestions are useful. I changed the code here and on Github. However It still doesn't work for small numbers (See the test case 1)
https://github.com/MaltoonYezi/Python-DSA/blob/main/Cryptography/SECP256k1Procedural.py
Sorry, for a delayed response

You got mistaken somewhere (or, as usual, in many places).

Test case 1 asks us to multiply (47,71) by 8 modulo 223 (with a=0, b=7). However with this prime the curve has structure 42x6, it is noncyclic.  Point (47,71) is from the group of (7,166); while (49,71) is from the group of (8,127). So, you could never reach either point from the other one.

You might want to change the test. If you insist on modulo 223, then b=5 is a good choice. Otherwise (b=7) use modulo 67 or 79, they are a bit like p and n in secp256k1, modulo one of them the group size is the other.

[SamYezi]

...
I got it, and  your suggestions are useful. I changed the code here and on Github. However It still doesn't work for small numbers (See the test case 1)
https://github.com/MaltoonYezi/Python-DSA/blob/main/Cryptography/SECP256k1Procedural.py
Sorry, for a delayed response

You got mistaken somewhere (or, as usual, in many places).

Test case 1 asks us to multiply (47,71) by 8 modulo 223 (with a=0, b=7). However with this prime the curve has structure 42x6, it is noncyclic.  Point (47,71) is from the group of (7,166); while (49,71) is from the group of (8,127). So, you could never reach either point from the other one.

You might want to change the test. If you insist on modulo 223, then b=5 is a good choice. Otherwise (b=7) use modulo 67 or 79, they are a bit like p and n in secp256k1, modulo one of them the group size is the other.

Yeah that's a good idea. However these test case 1 values I took from the book, and I checked the values once again and the problem was that the right values in the comments were incorrect. Now that I've refactored the script, it works fine. Also, Public keys outputs are being correct as well.
Thanks for your tips!