xbe.at

Python / Scientific and math computing

Exploring Elliptic Curve Arithmetic with Python

6 min read, 14 sections

Contents
  1. Introduction to Elliptic Curves
  2. Weierstrass Form
  3. Point Addition
  4. Scalar Multiplication
  5. Order of a Point
  6. Elliptic Curve over Finite Fields
  7. Generating Points on the Curve
  8. Real-life Example: ECDSA (Part 1)
  9. Real-life Example: ECDSA (Part 2)
  10. Elliptic Curve Diffie-Hellman (ECDH)
  11. Elliptic Curve Point Compression
  12. Performance Optimization: Precomputation
  13. Elliptic Curve Cryptography in Practice
  14. Additional Resources

Introduction to Elliptic Curves

Elliptic curves are algebraic structures with applications in cryptography and number theory. In this presentation, we'll explore their arithmetic using Python.

import matplotlib.pyplot as plt
import numpy as np

def plot_elliptic_curve(a, b):
    x = np.linspace(-5, 5, 1000)
    y = np.sqrt(x**3 + a*x + b)
    
    plt.figure(figsize=(10, 6))
    plt.plot(x, y, 'b', label='y² = x³ + {}x + {}'.format(a, b))
    plt.plot(x, -y, 'b')
    plt.title('Elliptic Curve: y² = x³ + {}x + {}'.format(a, b))
    plt.xlabel('x')
    plt.ylabel('y')
    plt.legend()
    plt.grid(True)
    plt.show()

plot_elliptic_curve(2, 3)

Weierstrass Form

Elliptic curves are typically represented in Weierstrass form: y² = x³ + ax + b. Let's define a class for points on the curve.

class EllipticCurvePoint:
    def __init__(self, x, y, a, b):
        self.x = x
        self.y = y
        self.a = a
        self.b = b
    
    def __str__(self):
        return f"({self.x}, {self.y})"
    
    def is_on_curve(self):
        return self.y**2 == self.x**3 + self.a*self.x + self.b

# Example usage
P = EllipticCurvePoint(2, 3, 2, 3)
print(f"P is on curve: {P.is_on_curve()}")

Point Addition

Point addition is a fundamental operation in elliptic curve arithmetic. Let's implement it:

def point_addition(P, Q):
    if P.x == Q.x and P.y != Q.y:
        return None  # Point at infinity
    
    if P.x != Q.x:
        m = (Q.y - P.y) / (Q.x - P.x)
    else:
        m = (3 * P.x**2 + P.a) / (2 * P.y)
    
    x3 = m**2 - P.x - Q.x
    y3 = m * (P.x - x3) - P.y
    
    return EllipticCurvePoint(x3, y3, P.a, P.b)

# Example usage
P = EllipticCurvePoint(2, 3, 2, 3)
Q = EllipticCurvePoint(-1, 4, 2, 3)
R = point_addition(P, Q)
print(f"P + Q = {R}")

Scalar Multiplication

Scalar multiplication is repeated point addition. We'll implement it using the double-and-add algorithm:

def scalar_multiplication(k, P):
    if k == 0:
        return None
    elif k == 1:
        return P
    elif k % 2 == 0:
        return scalar_multiplication(k // 2, point_addition(P, P))
    else:
        return point_addition(P, scalar_multiplication(k - 1, P))

# Example usage
P = EllipticCurvePoint(2, 3, 2, 3)
Q = scalar_multiplication(5, P)
print(f"5P = {Q}")

Order of a Point

The order of a point is the smallest positive integer n such that nP = O (point at infinity).

def order_of_point(P):
    Q = P
    n = 1
    while Q is not None:
        Q = point_addition(Q, P)
        n += 1
        if Q and Q.x == P.x and Q.y == P.y:
            return n
    return None

# Example usage
P = EllipticCurvePoint(2, 3, 2, 3)
order = order_of_point(P)
print(f"Order of P: {order}")

Elliptic Curve over Finite Fields

In cryptography, we often use elliptic curves over finite fields. Let's implement arithmetic modulo a prime p:

class EllipticCurveFiniteField:
    def __init__(self, a, b, p):
        self.a = a
        self.b = b
        self.p = p
    
    def add_points(self, P, Q):
        if P is None:
            return Q
        if Q is None:
            return P
        
        if (P.x, P.y) == (Q.x, Q.y):
            m = (3 * P.x**2 + self.a) * pow(2 * P.y, -1, self.p)
        else:
            m = (Q.y - P.y) * pow(Q.x - P.x, -1, self.p)
        
        x3 = (m**2 - P.x - Q.x) % self.p
        y3 = (m * (P.x - x3) - P.y) % self.p
        
        return EllipticCurvePoint(x3, y3, self.a, self.b)

# Example usage
E = EllipticCurveFiniteField(2, 3, 17)
P = EllipticCurvePoint(5, 1, 2, 3)
Q = EllipticCurvePoint(6, 3, 2, 3)
R = E.add_points(P, Q)
print(f"P + Q = {R}")

Generating Points on the Curve

Let's create a function to generate all points on an elliptic curve over a finite field:

def generate_points(E):
    points = []
    for x in range(E.p):
        for y in range(E.p):
            if (y**2 - x**3 - E.a*x - E.b) % E.p == 0:
                points.append(EllipticCurvePoint(x, y, E.a, E.b))
    return points

# Example usage
E = EllipticCurveFiniteField(2, 3, 17)
points = generate_points(E)
print(f"Number of points: {len(points)}")
for point in points:
    print(point)

Real-life Example: ECDSA (Part 1)

Elliptic Curve Digital Signature Algorithm (ECDSA) is used in cryptocurrencies like Bitcoin. Let's implement key generation:

import random

def generate_keypair(E, G, n):
    d = random.randint(1, n - 1)  # Private key
    Q = scalar_multiplication(d, G)  # Public key
    return d, Q

# Example usage
E = EllipticCurveFiniteField(2, 3, 17)
G = EllipticCurvePoint(5, 1, 2, 3)  # Base point
n = 18  # Order of G (simplified for this example)

private_key, public_key = generate_keypair(E, G, n)
print(f"Private key: {private_key}")
print(f"Public key: {public_key}")

Real-life Example: ECDSA (Part 2)

Now let's implement the signing and verification process:

def sign_message(E, G, n, d, message):
    k = random.randint(1, n - 1)
    R = scalar_multiplication(k, G)
    r = R.x % n
    h = hash(message) % n
    s = (pow(k, -1, n) * (h + r * d)) % n
    return (r, s)

def verify_signature(E, G, n, Q, message, signature):
    r, s = signature
    h = hash(message) % n
    w = pow(s, -1, n)
    u1 = (h * w) % n
    u2 = (r * w) % n
    X = point_addition(scalar_multiplication(u1, G), scalar_multiplication(u2, Q))
    return r == X.x % n

# Example usage
message = "Hello, Elliptic Curves!"
signature = sign_message(E, G, n, private_key, message)
is_valid = verify_signature(E, G, n, public_key, message, signature)
print(f"Signature: {signature}")
print(f"Signature is valid: {is_valid}")

Elliptic Curve Diffie-Hellman (ECDH)

ECDH is a key agreement protocol. Let's implement it:

def ecdh_key_exchange(E, G, n):
    # Alice's key pair
    a = random.randint(1, n - 1)
    A = scalar_multiplication(a, G)
    
    # Bob's key pair
    b = random.randint(1, n - 1)
    B = scalar_multiplication(b, G)
    
    # Shared secret
    s_alice = scalar_multiplication(a, B)
    s_bob = scalar_multiplication(b, A)
    
    return s_alice, s_bob

# Example usage
s_alice, s_bob = ecdh_key_exchange(E, G, n)
print(f"Alice's shared secret: {s_alice}")
print(f"Bob's shared secret: {s_bob}")
print(f"Shared secrets match: {s_alice.x == s_bob.x and s_alice.y == s_bob.y}")

Elliptic Curve Point Compression

To save space, we can compress elliptic curve points:

def compress_point(P):
    return (P.x, P.y % 2)

def decompress_point(E, x, y_bit):
    y_squared = (x**3 + E.a*x + E.b) % E.p
    y = pow(y_squared, (E.p + 1) // 4, E.p)
    if y % 2 != y_bit:
        y = E.p - y
    return EllipticCurvePoint(x, y, E.a, E.b)

# Example usage
P = EllipticCurvePoint(5, 1, 2, 3)
compressed = compress_point(P)
decompressed = decompress_point(E, compressed[0], compressed[1])
print(f"Original point: {P}")
print(f"Compressed: {compressed}")
print(f"Decompressed: {decompressed}")

Performance Optimization: Precomputation

For faster scalar multiplication, we can use precomputation:

def precompute_points(G, n):
    precomputed = [G]
    for i in range(1, n):
        precomputed.append(point_addition(precomputed[-1], G))
    return precomputed

def fast_scalar_multiplication(k, precomputed):
    result = None
    for i in range(len(precomputed)):
        if k & (1 << i):
            result = point_addition(result, precomputed[i])
    return result

# Example usage
precomputed = precompute_points(G, 10)
Q = fast_scalar_multiplication(7, precomputed)
print(f"7G = {Q}")

Elliptic Curve Cryptography in Practice

In practice, standardized curves like secp256k1 (used in Bitcoin) are used. Here's how to use the ecdsa library:

from ecdsa import SigningKey, SECP256k1

# Key generation
sk = SigningKey.generate(curve=SECP256k1)
vk = sk.get_verifying_key()

# Signing
message = b"Hello, Elliptic Curves!"
signature = sk.sign(message)

# Verification
assert vk.verify(signature, message)
print("Signature verified successfully!")

Additional Resources

For further reading on elliptic curves and their applications in cryptography:

  1. "An Introduction to Mathematical Cryptography" by J. Hoffstein, J. Pipher, and J.H. Silverman ArXiv: https://arxiv.org/abs/1305.5795
  2. "Elliptic Curves: Number Theory and Cryptography" by L.C. Washington ArXiv: https://arxiv.org/abs/1906.09632
  3. "A Course in Computational Algebraic Number Theory" by H. Cohen ArXiv: https://arxiv.org/abs/1903.10598

These resources provide in-depth coverage of the mathematical foundations and practical applications of elliptic curves in cryptography.

More in Scientific and math computing

  1. Exponential Equations and Functions Using Python5 min

    Exponential equations involve variables in the exponent. They are crucial in modeling growth and decay processes in various fields like finance, biology, and...

  2. Exploring Abstract Algebra with Python8 min

    Abstract Algebra, also known as Modern Algebra, is a branch of mathematics that studies algebraic structures such as groups, rings, and fields. It provides a...

  3. Finite Differentiation in Python7 min

    Finite differentiation is a numerical method used to approximate derivatives of functions. It's a fundamental concept in calculus and numerical analysis...

  4. Exploration of Monomial Ideals using Python7 min

    Monomial ideals are fundamental objects in commutative algebra and algebraic geometry. They are ideals generated by monomials in a polynomial ring....

  5. Finite Element Analysis with Python:5 min

    Finite Element Analysis is a numerical method for solving complex engineering problems. It involves dividing a large problem into smaller, simpler parts...

  6. Elementary Functional Analysis with Python10 min

    Functional analysis is a branch of mathematics that studies vector spaces and the linear operators acting on them. It combines concepts from linear algebra...