Fail at coding my private to public key converter script for Bitcoin (Secp256k1)
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:
Tried to debug the 1st code by myself, but failed. If you could help, I'd appreciate it!