🔮
Roll your own crypto
  • 🗞️Roll your own crypto* 🔮
  • 👩‍🏫Introduction to ECC
  • 🕓Galois Fields
  • ➰Elliptic Curve in Python
  • 🎯Representing a point
  • ➰Group Theory
  • ➕Point Addition in Python
  • ✖️Scalar Multiplication in Python
  • 🖋️ECDSA
  • 🎮Quiz: The Playstation 3 Hack
  • ❤️Conclusion
Powered by GitBook
On this page

Was this helpful?

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

The binary expansion technique can significantly speed the scalar multiplication process, and ensure that any scalar multiplication would require no more than 510 point addition operations.

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

The security of elliptic curve cryptography relies on the difficulty of reversing the scalar multiplication. This is is known as the discrete logarithm problem.

If one didG + G + G + G + ... + G = P, it is computationally impossible to find out how many times she added Gto itself, in order to obtain P.

Resources

PreviousPoint Addition in PythonNextECDSA

Last updated 1 year ago

Was this helpful?

Let's say we want to compute the value of 10P10P10P. Then instead of doing point additions naively, like: P+P+P+P+P+P+P+P+P+PP + P + P + P + P + P + P + P + P + PP+P+P+P+P+P+P+P+P+P , we can use binary expansion to achieve the same with just 4 point additions: P+P=2PP + P = 2PP+P=2P 2P+2P=4P2P + 2P = 4P2P+2P=4P 4P+4P=8P4P + 4P = 8 P4P+4P=8P 8P+2P=10P8P + 2P = 10P8P+2P=10P

Goundar, Raveen R., et al. "Scalar multiplication on Weierstraß elliptic curves from Co-Z arithmetic." Journal of cryptographic engineering 1.2 (2011): 161.

✖️
https://hackernoon.com/what-is-the-math-behind-elliptic-curve-cryptography-f61b25253da3
https://www.matthieurivain.com/files/jcen11b.pdf