Fail at coding my private to public key converter (Pyhon)

Question

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.

#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(currentX, currentY, gx, gy, a, b, prime)
        currentX, currentY = addition(currentX, currentY, gx, gy, a, b, prime)
        coef >>= 1
    return (resultX, resultY)

#privateKey, gx, gy, a, b, prime
#Smaller numbers (Not Secp256k1). Works, but incorrecly. Right output for this is: (49, 71)
print(secp256k1BinaryExpansion(8, 47, 71, a, b, 223))
#Test case 2
priv = 0x45300f2b990d332c0ee0efd69f2c21c323d0e2d20e7bfa7b1970bbf169174c82
print(secp256k1BinaryExpansion(priv, gx, gy, a, b, prime))
#Works incorrectly. The right values for test case 2:
#x = 40766947848522619068424335498612406856128862642075168802372109289834906557916
#y = 70486353993054234343658342414815626812704078223802622900411169732153437188990

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!

Answer 1

Your immediate problem is that you replaced the python '3-arg pow' used for modular exponentiation with separate power and modulo operations -- i.e. x ** y % p instead of pow(x,y,p). While these appear mathematically equivalent their implementations are radically different -- the pow3 approach takes microseconds while according to my very rough projections the **/% approach for 256-bit numbers will take approximately the lifetime of the universe. See cross https://stackoverflow.com/questions/14133806/why-is-powa-d-n-so-much-faster-than-ad-n and more linked there.

Your addition() function also handles the cases involving the identity element, aka the 'point at infinity', inconsistently and sometimes wrongly. Plus using pow(,prime-2,prime) to get modular inverse -- which you apparently copied from the linked book/repo -- is not the best way, but I leave it on the grounds your code won't be used for anything important or material. See How do you get a Bitcoin Public Key from a Private Key for several examples, including python, of using Extended Euclidean Algorithm for modular inverse. (added) Or I just discovered you can simply use pow(,-1,p) and python does it for you, see https://stackoverflow.com/questions/60019932/what-does-powa-b-c-do-when-the-exponent-is-negative .

However, after addition() is fixed you have a much bigger problem. I don't know where you got 'binary expansion' from since there's no such thing in ECC, but from its structure it looks like you are trying to do scalar multiplication, which is indeed the correct way to compute public key from private key. However, your logic here is almost completely wrong even used with a correct addition(). Mostly it appears you think the second point passed to addition() (as the third and fourth arguments) is always G whereas in fact it almost never is, and I suspect naming the parameters of addition() as currentX/Y, gx/y either reflects or contributes to this.

I have therefore slightly modified your addition() to use pow3 and handle the identity cases, changing the test order to simplify it some, and changed the parameter names (to simply 'one' and 'two'); and replaced entirely your 'binary expansion' with a correct scalarmult(), and it now works:

#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

def addition(onex,oney, twox,twoy, a,b,prime):
  if onex is None and oney is None: return (twox,twoy)
  elif twox is None and twoy is None: return (onex,oney)
  elif onex != twox: # normal addition
    s = (oney-twoy) * pow(onex-twox, prime-2,prime) %prime;
    newx = (s*s - onex - twox) %prime;
    newy = (s * (twox-newx) - twoy) %prime;
    return (newx,newy)
  elif oney == (prime - twoy)%prime: # cancellation potentially including +-0
    # (although +-0 will never actually occur for secp256k1 or any other
    # X9/SECG curve over Fp because they were chosen to have cofactor 1)
    return (None,None)
  else: # doubling (one==two)
    s = (onex**2*3+a)%prime * pow(oney*2, prime-2, prime) %prime;
    newx = (s*s - onex*2) %prime;
    newy = (s * (onex-newx) - oney) %prime;
    return (newx, newy)

def scalarmult(k, inx,iny, a,b,prime):
  outx,outy = (None,None);
  while k:
    if k&1: outx,outy = addition(outx,outy, inx,iny, a,b,prime);
    k>>=1; inx,iny = addition(inx,iny, inx,iny, a,b,prime);
  return (outx,outy);

# main routine: if run with no arguments use n-1 as private key,
# if run with one argument use that hex number as private key,
# if run with two arguments use those two hex numbers as a point
# and do just a single addition for debugging/demo purposes
import sys;
if len(sys.argv)==1: x,y = scalarmult(n-1, gx,gy, a,b,prime);
elif len(sys.argv)==2: x,y = scalarmult(int(sys.argv[1],16), gx,gy, a,b,prime);
else: x,y = addition(int(sys.argv[1],16),int(sys.argv[2],16), gx,gy, a,b,prime);
print( hex(x) ); print( hex(y) );

Also note b could be removed and not passed because it isn't used for addition or multiplication, as could a because it is zero for a Koblitz curve like secp256k1, but I left them to keep your structure.