✖️Scalar Multiplication in Python
Scalar multiplication forms the basis of elliptic curve cryptography. We can easily express multiplication of a point by a scalar in the form of repeated additions.
class Point:
... # add these methods to the previously defined Point class
def __rmul__(self, scalar: int) -> "Point":
# Naive approach:
#
# result = I
# for _ in range(scalar): # or range(scalar % N)
# result = result + self
# return result
# Optimized approach using binary expansion
current = self
result = I
while scalar:
if scalar & 1: # same as scalar % 2
result = result + current
current = current + current # point doubling
scalar >>= 1 # same as scalar / 2
return result
We can now verify the correctness of the generator point used in Bitcoin, as follows:
# Reinitialize I and G, with the updated Point class.
I = Point(x=None, y=None, curve=secp256k1)
G = Point(
x=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
y=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8,
curve=secp256k1
)
# Test case 1
assert N * G == I
# Test case 2
pub = Point(
x=0x9577FF57C8234558F293DF502CA4F09CBC65A6572C842B39B366F21717945116,
y=0x10B49C67FA9365AD7B90DAB070BE339A1DAF9052373EC30FFAE4F72D5E66D053,
curve=secp256k1
)
e: int = 2 ** 240 + 2 ** 31
assert e * G == pub
Resources
Goundar, Raveen R., et al. "Scalar multiplication on Weierstraß elliptic curves from Co-Z arithmetic." Journal of cryptographic engineering 1.2 (2011): 161. https://www.matthieurivain.com/files/jcen11b.pdf
Last updated
Was this helpful?