63 lines
1.7 KiB
Python
63 lines
1.7 KiB
Python
# ECDSA
|
|
from math import sqrt
|
|
|
|
# secp256k1 constants
|
|
P = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
|
|
A = 0x0
|
|
B = 0x7
|
|
GX = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
|
|
GY = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 # even
|
|
GP = (int(GX), int(GY))
|
|
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
|
|
|
|
def modinv( a, n=P ):
|
|
lm, hm = 1, 0
|
|
low, high = a % n, n
|
|
while low > 1:
|
|
r = high // low
|
|
nm, new = hm - lm * r, high - low * r
|
|
lm, low, hm, high = nm, new, lm, low
|
|
return lm % n
|
|
|
|
def ecAdd( a, b ):
|
|
ladd = ((b[1] - a[1]) * modinv( b[0] - a[0], P )) % P
|
|
x = (ladd * ladd - a[0] - b[0]) % P
|
|
y = (ladd * (a[0] - x) - a[1]) % P
|
|
return (x, y)
|
|
|
|
def ecDouble( a ):
|
|
lam = ((3 * a[0] * a[0] + A) * modinv( (2 * a[1]), P )) % P
|
|
x = (lam * lam - 2 * a[0]) % P
|
|
y = (lam * (a[0] - x) - a[1]) % P
|
|
return (x, y)
|
|
|
|
# multiply generator point by scalar
|
|
def ecMult( gen, sc ):
|
|
assert sc != 0 and sc < N, 'Invalid scalar'
|
|
scbin = bin( sc )[2:]
|
|
Q = gen
|
|
for i in range( 1, len( scbin ) ):
|
|
Q = ecDouble( Q )
|
|
if scbin[i] == '1':
|
|
Q = ecAdd( Q, gen )
|
|
return Q
|
|
|
|
# helper for returning point result of gen point multiplied by int p
|
|
def getPoint( p ): return ecMult( GP, p )
|
|
|
|
# return bytes of point p in compressed format. bip32 calls this serialization
|
|
def compressPoint( p ):
|
|
return bytes.fromhex( ('02' if p[1] % 2 == 0 else '03') + hex( p[0] )[2:].zfill( 64 ) )
|
|
|
|
# return point coord pair of compressed point bytes
|
|
def decompressPoint( p ):
|
|
x = int( p[1:].hex(), 16 )
|
|
ys = (pow( x, 3, P ) + (A * x) + B) % P
|
|
y = pow( ys, (P + 1) // 4, P )
|
|
|
|
if (y % 2) != (p[0] - 2):
|
|
y = (-y) % P
|
|
|
|
return (x, y)
|
|
|