Your fast downside is that you just changed the python ‘3-arg pow’ used for modular exponentiation with separate energy and modulo operations — i.e. x ** y % p as an alternative of pow(x,y,p). Whereas these seem mathematically equal their implementations are radically totally different — the pow3 strategy takes microseconds whereas in line with my very tough projections the **/% strategy for 256-bit numbers will take roughly the lifetime of the universe. See cross https://stackoverflow.com/questions/14133806/why-is-powa-d-n-so-much-faster-than-ad-n and extra linked there.
Your addition() operate additionally handles the instances involving the id ingredient, aka the ‘level at infinity’, inconsistently and typically wrongly. Plus utilizing pow(,prime-2,prime) to get modular inverse — which you apparently copied from the linked e-book/repo — shouldn’t be one of the simplest ways, however I go away it on the grounds your code will not be used for something vital or materials. See How do you get a Bitcoin Public Key from a Non-public Key for a number of examples, together with python, of utilizing Prolonged Euclidean Algorithm for modular inverse. (added) Or I simply found you may merely 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 .
Nonetheless, after addition() is fastened you have got a a lot larger downside. I do not know the place you bought ‘binary growth’ from since there is not any such factor in ECC, however from its construction it seems to be like you are attempting to do scalar multiplication, which is certainly the proper strategy to compute public key from non-public key. Nonetheless, your logic right here is sort of utterly incorrect even used with an accurate addition(). Largely it seems you assume the second level handed to addition() (because the third and fourth arguments) is at all times G whereas in truth it nearly by no means is, and I think naming the parameters of addition() as currentX/Y, gx/y both displays or contributes to this.
I’ve due to this fact barely modified your addition() to make use of pow3 and deal with the id instances, altering the check order to simplify it some, and altered the parameter names (to easily ‘one’ and ‘two’); and changed totally your ‘binary growth’ with an accurate scalarmult(), and it now works:
#Secp256k1 Bitcoin non-public to public key converter script
a = 0
b = 7
#Order of the finite area
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: # regular 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 doubtlessly together with +-0
# (though +-0 won't ever really happen for secp256k1 or another
# X9/SECG curve over Fp as a result of they have been 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(ok, inx,iny, a,b,prime):
outx,outy = (None,None);
whereas ok:
if ok&1: outx,outy = addition(outx,outy, inx,iny, a,b,prime);
ok>>=1; inx,iny = addition(inx,iny, inx,iny, a,b,prime);
return (outx,outy);
# major routine: if run with no arguments use n-1 as non-public key,
# if run with one argument use that hex quantity as non-public key,
# if run with two arguments use these two hex numbers as a degree
# and do only a single addition for debugging/demo functions
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) );
Additionally observe b might be eliminated and never handed as a result of it is not used for addition or multiplication, as may a as a result of it’s zero for a Koblitz curve like secp256k1, however I left them to maintain your construction.