1: Elliptic curve crytography¶
In this notebook, we give an introduction to elliptic curve cryptography (ECC). Elliptic curves are everywhere nowadays, e.g.
- Crypto: Many cryptocurrencies, like Bitcoin and Ethereum, utilize ECC as part of their cryptographic algorithms. ECC is used for generating digital signatures to ensure the integrity and authenticity of transactions. It offers strong security with relatively smaller key sizes, which is crucial for efficient blockchain operations. We will explain and build the ECDSA algorithm that they use.
- Email encryption: ECC is used in email encryption and digital signatures, protecting sensitive email communications between individuals and organizations. For example, it is used in in OpenPGP, the most widely used email encryption standard. We will explain and build the ECDH algorithm that they use.
- Web browser and server connection: ECC is used in Transport Layer Security (TLS) and its predecessor Secure Sockets Layer (SSL), which provide encrypted connections between web browsers and servers (both using ECDSA and ECDH).
Hence, elliptic curve cryptography constitute a fundamental concept for a secure and private digital world.
In this tutorial, we will describe the algorithms behind these use-cases:
- Mathematical introduction The mathematical background behind elliptic curves and what they do.
- Elliptic curve cryptography An elliptic curve crytopgrahic system.
- Elliptic-curve Diffie–Hellman (ECDH): a key exchange protocol based on elliptic curve cryptography. It allows two parties to generate a shared secret over an insecure channel, which can be used for secure communication or encryption, without ever transmitting the secret directly.
- Elliptic Curve Digital Signature Algorithm (ECDSA): this is a widely used digital signature algorithm. ECDSA provides a way to generate and verify digital signatures, ensuring the authenticity, integrity, and non-repudiation of messages or data.
Code: you can download the jupyter notebook that created this post here.
Acknowledgement: I took inspiration from other tutorials on the interent,in particular I want to acknowledge Andrea Corbellini's posts and Nick Sullivan's post.
A few tools that we will need later:
from typing import List, Union, Tuple, Literal
import numpy as np
import matplotlib.pyplot as plt
#!pip install bitarray
import bitarray
class Timer:
"""Function to time a piece of code"""
def __init__(self,message):
self.message = message
def __enter__(self):
self.start = time.perf_counter()
return self
def __exit__(self, *args):
self.end = time.perf_counter()
self.interval = self.end - self.start
print(f"Time to execute {self.message} in seconds = {self.interval:.2e}")
def get_binary_representation(number: int):
"""function to get binary representation of number"""
binary_representation = ""
while number:
new_string = str(number % 2)
binary_representation = new_string + binary_representation
number = number // 2
return binary_representation
1. Elliptic Curves¶
Let's start by defining what we mean with elliptic curves. Let $\mathbb{K}$ be a field). In our case, this will be
- $\mathbb{K}=\mathbb{R}$: we use the real number for illustration purposes as it allows us to develop geometric intuition. However, they are generally not used in cryptography.
- $\mathbb{K}=GF(p)=\mathbb{Z}/p\mathbb{Z}$: this field is used for cryptographic purposes for a large primer number $p$.
For two elements $a,b\in\mathbb{K}$, an elliptic curves is a subset $E_{a,b}\subset \mathbb{K}\times \mathbb{K}$ defined by the equation: $$y^2 = x^3+ax+b$$ i.e. $E_{a,b}$ consists of all pairs $(x,y)$ satisfying this equation.
Symmetry of elliptic curves: An immediate property of an elliptic curve is clear: if $(x,y)\in E_{a,b}$, then $(x,-y)\in E_{a,b}$ (as $y^2=(-y)^2$). Therefore, elliptic curves are symmetric around the $x$-axis.
Excluding singular curves: A technnical requirement for elliptic curves is that $4*a^3+27*b^2\neq 0$. The reason for that is that singularities have to be avoided. If you would like to know more about this, we are going to give a full explanation later in the appendix chapter.
1.1. Elliptic Curve Class¶
Let's define an elliptic curve class.
class EllipticCurve:
def __init__(self, a: int, b: int, mod_n=None, allow_singularity: bool = False):
if mod_n is not None: assert isinstance(mod_n,int)
assert ((isinstance(a,int) and isinstance(b,int) and mod_n is not None))|\
((isinstance(a,float) and isinstance(b,float) and mod_n is None)),\
"""K=GF(p) requires ints a,b. K=R requires floats a,b."""
self.a = a
self.b = b
self.mod_n = mod_n
if not allow_singularity:
self._check_singularity()
@property
def determinant(self):
determinant = -4*(self.a**3)-27*(self.b**2)
if self.mod_n is not None:
determinant = determinant % self.mod_n
return determinant
def _check_singularity(self):
assert self.determinant != 0, "Singular curve not allowed."
def __str__(self):
equation = f"y^2 = x^3 + {self.a}*x + {self.b}"
if self.mod_n is not None:
equation = f"{equation} mod {self.mod_n}"
return equation
def __eq__(self, op):
return (self.a == op.a) & (self.b == op.b) & (self.mod_n == op.mod_n)
def mask_points_in_curve(self,x_arr,y_arr):
"""Function that finds in input all points that allow on the curve"""
y_side = y_arr**2
x_side = x_arr**3+self.a*x_arr+self.b
if self.mod_n is not None:
y_side = y_side % self.mod_n
x_side = x_side % self.mod_n
return x_side == y_side
else:
return np.abs(x_side-y_side)<1e-5
def give_point_cloud(self, n_grid: int = 20, min_x: float = -3.0, max_x: float = 3.0):
"""
Returns cloud of points on elliptic curve
"""
if self.mod_n is None:
x_arr = np.linspace(min_x,max_x,n_grid)
y_pos = np.sqrt(x_arr**3+self.a*x_arr+self.b)
x_pos = x_arr
x_neg = x_arr[::-1]
y_neg = - y_pos[::-1]
x = np.concatenate([x_neg,x_pos])
y = np.concatenate([y_neg,y_pos])
mask_nan = np.isnan(y)
x,y = x[~mask_nan], y[~mask_nan]
else:
#Test out all possibilities for x:
x_wanted = np.arange(0,self.mod_n)
y2_wanted = (x_wanted**3+self.a*x_wanted+self.b)%self.mod_n
#Test our all possibilities for y:
y_query = np.arange(0,self.mod_n)
y2_query = (y_query**2)%self.mod_n
#Find combinations that are zero modulo self.mod_n
bool_mask = (((y2_wanted[:,None]-y2_query[None,:])%self.mod_n)==0)
#Extract corresponding x's and y's:
y_query_mat = (bool_mask.astype('int')*y_query[None,:])
x_wanted_mat = (x_wanted[:,None]*bool_mask.astype('int'))
y = y_query_mat[bool_mask]
x = x_wanted_mat[bool_mask]
#Ensure that points are on the curve:
assert self.mask_points_in_curve(x,y).all()
return x,y
def random_points(self,n_samples: int = 1):
"""Give some random points on elliptic curve"""
x,y = self.give_point_cloud()
ids = np.random.randint(len(x),size=n_samples)
return x[ids],y[ids]
def plot(self, ax, label=None,scatter=True,**kwargs):
"""plot the curve"""
if scatter:
return ax.scatter(*self.give_point_cloud(**kwargs),label=label)
else:
return ax.plot(*self.give_point_cloud(**kwargs),label=label)
Let's define some curves:
$\mathbb{K}=GF(p)$
curve_1 = EllipticCurve(10,12,14)
curve_2 = EllipticCurve(10,11,16)
print(curve_1)
print(curve_2)
y^2 = x^3 + 10*x + 12 mod 14 y^2 = x^3 + 10*x + 11 mod 16
$\mathbb{K}=\mathbb{R}$
curve_3 = EllipticCurve(1.0,2.0)
curve_4 = EllipticCurve(1.0,3.0)
print(curve_3)
print(curve_4)
try:
curve_5 = EllipticCurve(-3,2)
except AssertionError:
print("Singular curve. Not allowed...")
y^2 = x^3 + 1.0*x + 2.0 y^2 = x^3 + 1.0*x + 3.0 Singular curve. Not allowed...
1.2. Plot a few curves¶
We plot a few curves for various $a,b$ and for $\mathbb{K}=\mathbb{R},GF(p)$:
fig, axs = plt.subplots(1,3,figsize=(15,5))
for b in np.linspace(-100,100,10):
curve = EllipticCurve(.0,b)
curve.plot(ax=axs[0],min_x=-10.0,max_x=10.0,n_grid=10000,label=f"{curve.b:.0f}")
axs[0].legend(title="b")
axs[0].set_title("a=0| K = R")
for a in np.linspace(-100,100,10):
curve = EllipticCurve(a,0.0)
curve.plot(ax=axs[1],min_x=-10.0,max_x=10.0,n_grid=10000,label=f"{curve.a:.2f}")
axs[1].legend(title="a")
axs[1].set_title("b=1 | K = R")
for a in np.linspace(-100,100,10):
curve = EllipticCurve(a,-1.0)
curve.plot(ax=axs[2],min_x=-10.0,max_x=20.0,n_grid=10000,label=f"{curve.a:.2f}")
axs[2].legend(title="a")
axs[2].set_title("b=-1 | K = R")
fig, axs = plt.subplots(1,3,figsize=(15,5))
curve = EllipticCurve(1,2,23)
curve.plot(ax=axs[0],min_x=-10.0,max_x=10.0,n_grid=10000,label=f"{curve.b:.0f}")
axs[0].set_title("a=1,b=2,K=GF(23)");
curve = EllipticCurve(4,2,231)
curve.plot(ax=axs[1],min_x=-10.0,max_x=10.0,n_grid=10000,label=f"{curve.b:.0f}")
axs[1].set_title("a=4,b=2,K=GF(231)");
curve = EllipticCurve(4,12,2311)
curve.plot(ax=axs[2],min_x=-10.0,max_x=10.0,n_grid=10000,label=f"{curve.b:.0f}")
axs[2].set_title("a=4,b=12,K=GF(2311)");
/var/folders/z8/hy1b8vjj63xfzqjbz_r7pz2nx23r5d/T/ipykernel_11969/817109513.py:54: RuntimeWarning: invalid value encountered in sqrt y_pos = np.sqrt(x_arr**3+self.a*x_arr+self.b)
1.3. Find modular inverse¶
We define the algorithm that finds the modular inverse of an object. As discussed in the RSA tutorial, this is the extended Euclidean algorithm.
def xgcd(a, b):
"""Extended Euclidean Algorithm (Iterative)
Args:
a: int
b: int
NOTES
=====
We can represent gcd(a,b) = a.x + b.y
This function returns gcd(a, b), x, y
REFERENCES
==========
https://anh.cs.luc.edu/331/notes/xgcd.pdf
EXAMPLES
========
>>> xgcd(15, 35)
(5, -2, 1)
>>> xgcd(30, 20)
(10, 1, -1)
"""
assert a > 0 and b > 0
xprev, x = 0, 1
yprev, y = 1, 0
while a:
q = b // a
x, xprev = xprev - q * x, x
y, yprev = yprev - q * y, y
a, b = b % a, a
return b, xprev, yprev
def inverse(a, n):
"""Modular Multiplicative Inverse
Args:
a: integer whose inverse is to be found
n: modular base
NOTES
=====
Returns the modular multiplicative inverse of 'a' under mod n
Return value is always positive
EXAMPLES
========
>>> inverse(2, 5)
3
>>> inverse(17, 39)
23
>>> inverse(2,4)
Traceback (most recent call last):
Exception: Inverse does not exist.
"""
g, x, _ = xgcd(a, n)
if g != 1:
raise Exception("Inverse does not exist.")
return (x % n + n) % n
1.4 Elliptic Curve Algebra¶
The fascinating property of elliptic curves is that we can define an algebraic operation on elliptic curves, i.e. for two points $P,Q\in E_{a,b}$ we can define a new point $P+Q\in E_{a,b}$. The goal of this section is to motivate and to define what "$P+Q$" means.
1.4.1 Geometric intuition¶
Let's start with the geometric idea behind addition in elliptic curves. This intution only holds for $\mathbb{K}=\mathbb{R}$, i.e. for elliptic curves in our known Euclidean geometry. However, it is a good starting point.
The main idea behind elliptic curve addition is that we can add two points $P=(x_P,y_P)$ and $Q=(x_Q,y_Q)$ on a curve by performing the following operation:
- Find the line that intersects $Q$ and $P$ (in green below)
- Find the 3rd point that intersects with the elliptic curve (intersection between orange and green line)
- Mirror this point along the x-axis to reach $P+Q$.
However, there might be a few edge cases when the line $L=\bar{QP}$ does not intersect with a third point on the curve:
- Mirrored points: if $x_P=x_Q$ and $y_P=-x_Q$, then the line connecting both points will have no third intersection as it is just vertical. We define an additional point at infinity which we simply denote as $0$. We set in this case $P+Q=0$. In this case, we also write $Q=-P$.
- Point at infinity: if $P=0$, then set $P+Q=Q$. If $Q=0$, set $P+Q=P$.
- Equal points: if $P=Q$, then one takes the tangential at $P$. In the appendix, we will show that there is exactly one other point where that lines intersects with the curve. Mirror that point to get $P+P$.
- Tangentials: if 1. and 2. are not the case and the line $\bar{PQ}$ does not intersect with a third point, we will show in the appendix that the line $L=\bar{PQ}$ must be tangential either at $P$ or at $Q$. In this case, pick the point where the line is not tangential and mirror that point.
1.4.2 From geometry to algebra¶
Let's make the definition more exact and write it down in equations.
Trivial cases (edge case 1 and 2). If $P=-Q$, $P=0$, or $Q=0$, we already have simple rules on what to do by definition. This defines equations for edge case 1 and 4.
Two distinct points (including edge case 4). Let $R=P+Q=(x_R,y_R)$. One can then show that equations
$$ \begin{aligned} \lambda &= (y_Q - y_P)(x_Q - x_P)^{-1}\\ x_R &= \lambda^2 - x_P - x_Q \\ y_R &= \lambda \cdot (x_P - x_R) - y_P, \end{aligned}$$
define a point on the elliptic curve (by simply inserting the above formula in the equation). One can also see that $-R=(x_R,-y_R)$ is on the line $L(x)=\lambda (x-x_P)+y_P$ connecting $P$ and $Q$. Note that this includes edge case $4$ (Tangentials).
Equal points (edge case 3). 4. If $P = Q$ (i.e., the points are the same), then the sum $R = P + P$ is computed as follows:
$$ \begin{aligned} \lambda &= (3x_P^2 + a)(2y_P)^{-1}\\ x_R &= \lambda^2 - 2x_P \\ y_R &= \lambda \cdot (x_P - x_R) - y_P \end{aligned}$$ One can see that $-R$ lies on the tangential by computing the derivative of the function $f(x)=\sqrt{x^3+ax+b}$ at $x_P$:
$$f'(x_P)=\frac{1}{2}(3x_P^2+a)(x_P^3+ax_P+b)^{-\frac{1}{2}}=(3x_P^2+a)(2y_P)^{-1}=\lambda$$
Therefore, the tangential is given by $L(x)=\lambda (x-x_P)+y_P$ and hence, $-R$ lies on that tangential. To see that the point lies on the elliptic, simply insert the above formula into the elliptic curve equation (you won't learn a lot, so I would not do that and trust that smart people have done it correctly).
Important!: the above rules define an addition on purely algebraic terms. Therefore, we can use the above equations to also define an addition on elliptic curves from other fields such as $GF(p)$ that don't represent our classical Euclidean geometry. This is a completely way of adding points!
Let's implement the addition for an elliptic curve element:
class EllipticCurveElement:
def __init__(self, coordinates: Union[Tuple[float,float],Tuple[int,int],Literal[0]],
curve: EllipticCurve):
if coordinates:
self.x = coordinates[0]
self.y = coordinates[1]
self.is_zero = False
elif coordinates == 0:
self.is_zero = True
else:
raise ValueError("Invalid input for EllipticCurveElement. Must be either tuple or 0")
self.curve = curve
if not self.is_zero:
valid_input_for_reals = ((isinstance(self.x,int) and \
isinstance(self.y,int) and \
curve.mod_n is not None))
valid_input_for_galois = ((isinstance(self.x,float) and \
isinstance(self.y,float) and \
curve.mod_n is None))
assert valid_input_for_reals | valid_input_for_galois,\
"Invalid input. Floats for reals and ints for galois field."
assert self.curve.mask_points_in_curve(np.array([self.x]),np.array([self.y])).all(),\
"Coordinates are not part of that curve."
def __str__(self):
if self.is_zero:
return "0=inf"
else:
return f"({self.x},{self.y})"
def __add__(self, op):
"""Addition on elliptic curves.
op: must be another EllipticCurveElement
Returns a new EllipticCurveElement representing the sum."""
assert self.curve == op.curve, "Elliptic curves are different. Can't add."
#Identity elements:
if self.is_zero:
return op
elif op.is_zero:
return self
else:
#Compute lambda, the slope of the line
#connecting both points:
if self.x!= op.x:
den = (op.x-self.x)
if self.curve.mod_n is not None:
den = den % self.curve.mod_n
inverse_den = inverse(den,self.curve.mod_n)
lambda_ = ((op.y-self.y)*inverse_den) % self.curve.mod_n
else:
lambda_ = (op.y-self.y)/den
else:
#If self=-op, then return 0=inf
sum_ = self.y + op.y
if self.curve.mod_n is not None:
sum_ = sum_ % self.curve.mod_n
if sum_ == 0:
return EllipticCurveElement(0,curve=self.curve)
#Otherwise, they are equal and compute tangential:
nominator = (3*(op.x**2)+self.curve.a)
denominator = (2*op.y)
if self.curve.mod_n is not None:
nominator = nominator % self.curve.mod_n
denominator = denominator % self.curve.mod_n
inverse_den = inverse(denominator,self.curve.mod_n)
lambda_ = (nominator*inverse_den) % self.curve.mod_n
else:
lambda_ = nominator/denominator
x_R = lambda_**2 - self.x - op.x
y_R = lambda_*(op.x-x_R) - op.y
if self.curve.mod_n is not None:
x_R = x_R % self.curve.mod_n
y_R = y_R % self.curve.mod_n
return EllipticCurveElement((x_R,y_R),curve=self.curve)
def __rmul__(self, n: int):
cum_sum = EllipticCurveElement(0,self.curve)
exponent = EllipticCurveElement((self.x,self.y),self.curve)
while n>0:
if n % 2:
cum_sum = cum_sum + exponent
exponent = exponent + exponent
n = n //2
return cum_sum
def __eq__(self, el):
if not isinstance(el, EllipticCurveElement):
return False
if self.curve != el.curve:
return False
if self.is_zero:
return el.is_zero
if el.is_zero:
return False
if (el.x != self.x) | (el.y != self.y):
return False
return True
Let's look at a few additions:
curve = EllipticCurve(10,11,mod_n=31)
point = curve.random_points(1)
el_1 = EllipticCurveElement((point[0].item(),point[1].item()),curve)
print("Element 1: ", el_1)
el_2 = EllipticCurveElement(0,curve)
print("Element 2: ", el_2)
el_3 = EllipticCurveElement(0,curve)
print("Element 3: ", el_3)
print("Sum 1+2: ", el_1+el_2)
try:
el_1 + el_3
except AssertionError:
print("Expected error: elements from different curves can't be combined.")
Element 1: (24,30) Element 2: 0=inf Element 3: 0=inf Sum 1+2: (24,30)
1.4.1 Plottting summation for $\mathbb{K}=\mathbb{R}$¶
curve = EllipticCurve(1.0,10.0)
x_sol,y_sol = curve.give_point_cloud()
n_plots = 5
fig, axs = plt.subplots(1,n_plots,figsize=(6*n_plots,6))
for i in range(n_plots):
ax = axs[i]
rand_idx_1 = np.random.randint(len(x_sol))
rand_idx_2 = np.random.randint(len(x_sol))
el_1 = EllipticCurveElement((x_sol[rand_idx_1],y_sol[rand_idx_1]),curve=curve)
el_2 = EllipticCurveElement((x_sol[rand_idx_2],y_sol[rand_idx_2]),curve=curve)
el_sum = el_1 + el_2
curve.plot(ax=ax,min_x=-10.0,max_x=max(10.0,el_sum.x),n_grid=10000,label=f"{curve.b:.0f}",scatter=False)
m = (el_2.y-el_1.y)/(el_2.x-el_1.x)
x_min,x_max = ax.get_xlim()
x_arr = np.linspace(x_min,x_max,100)
ax.plot(x_arr,m*(x_arr-el_1.x)+el_1.y,color='tab:green',linestyle='--')
ax.plot([el_sum.x,el_sum.x],[el_sum.y,-el_sum.y],color='tab:orange',linestyle='--')
ax.scatter([el_1.x],[el_1.y],marker='X',color='black')
ax.scatter([el_2.x],[el_2.y],marker='X',color='black')
ax.scatter([el_sum.x],[el_sum.y],marker='X',color='red')
#ax.scatter([el_sum.x],[-el_sum.y],marker='X',color='red')
ax.scatter([el_sum.x],[el_sum.y],marker='X',color='red',s=32)
fig, axs = plt.subplots(1,n_plots,figsize=(6*n_plots,6))
curve = EllipticCurve(1.0,10.0)
x_sol,y_sol = curve.give_point_cloud()
for i in range(n_plots):
ax = axs[i]
rand_idx_1 = np.random.randint(len(x_sol))
rand_idx_2 = np.random.randint(len(x_sol))
el_1 = EllipticCurveElement((x_sol[rand_idx_1],y_sol[rand_idx_1]),curve=curve)
el_2 = el_1
el_sum = el_1 + el_2
curve.plot(ax=ax,min_x=-10.0,max_x=max(10.0,el_sum.x),n_grid=10000,label=f"{curve.b:.0f}",scatter=False)
m = (3*el_1.x**2+curve.a)/(2*el_1.y)
x_min,x_max = ax.get_xlim()
x_arr = np.linspace(x_min,x_max,100)
ax.plot(x_arr,m*(x_arr-el_1.x)+el_1.y,color='tab:green',linestyle='--')
ax.plot([el_sum.x,el_sum.x],[el_sum.y,-el_sum.y],color='tab:orange',linestyle='--')
ax.scatter([el_1.x],[el_1.y],marker='X',color='black')
ax.scatter([el_2.x],[el_2.y],marker='X',color='black')
ax.scatter([el_sum.x],[el_sum.y],marker='X',color='red')
#ax.scatter([el_sum.x],[-el_sum.y],marker='X',color='red')
#ax.scatter([el_sum.x],[el_sum.y],marker='X',color='red',s=32)
/var/folders/z8/hy1b8vjj63xfzqjbz_r7pz2nx23r5d/T/ipykernel_11969/817109513.py:54: RuntimeWarning: invalid value encountered in sqrt y_pos = np.sqrt(x_arr**3+self.a*x_arr+self.b)
1.4.2 Plottting summation for $\mathbb{K}=GF(p)$¶
curve = EllipticCurve(1,10,31)
n_plots = 5
size = 50
fig, axs = plt.subplots(1,n_plots,figsize=(6*n_plots,6))
x_sol,y_sol = curve.random_points(n_plots+1)
for i in range(n_plots):
ax = axs[i]
el_1 = EllipticCurveElement((x_sol[i].item(),y_sol[i].item()),curve=curve)
el_2 = EllipticCurveElement((x_sol[i+1].item(),y_sol[i+1].item()),curve=curve)
while el_2 == el_1:
idx = np.random.choice(len(x_sol))
el_2 = EllipticCurveElement((x_sol[idx].item(),y_sol[idx].item()),curve=curve)
el_sum = el_1 + el_2
curve.plot(ax=ax,label=f"{curve.b:.0f}",scatter=True)
m = (el_2.y-el_1.y)
diff = (el_2.x-el_1.x) % curve.mod_n
inv_diff = inverse(diff,curve.mod_n)
m = (m * inv_diff) % curve.mod_n
x_min,x_max = ax.get_xlim()
x_arr = np.arange(0,curve.mod_n)
ax.plot(x_arr,(m*(x_arr-el_1.x)+el_1.y)%curve.mod_n,color='tab:green',linestyle='--')
ax.plot([el_sum.x,el_sum.x],[el_sum.y,-el_sum.y%curve.mod_n],color='tab:orange',linestyle='--')
ax.scatter([el_1.x],[el_1.y],marker='X',color='black',s=size)
ax.scatter([el_2.x],[el_2.y],marker='X',color='black',s=size)
ax.scatter([el_sum.x],[el_sum.y],marker='X',color='red',s=size)
fig, axs = plt.subplots(1,n_plots,figsize=(6*n_plots,6))
for i in range(n_plots):
ax = axs[i]
rand_idx_1 = np.random.randint(len(x_sol))
el_1 = EllipticCurveElement((x_sol[i].item(),y_sol[i].item()),curve=curve)
el_2 = el_1
el_sum = el_1 + el_2
curve.plot(ax=ax,label=f"{curve.b:.0f}",scatter=True)
m = (3*(el_1.x**2)+curve.a)%curve.mod_n
den = (2*el_1.y) % curve.mod_n
inv_den = inverse(den,curve.mod_n)
m = (m * inv_den) % curve.mod_n
x_min,x_max = ax.get_xlim()
x_arr = np.arange(0,curve.mod_n)
ax.plot(x_arr,(m*(x_arr-el_1.x)+el_1.y)%curve.mod_n,color='tab:green',linestyle='--')
ax.plot([el_sum.x,el_sum.x],[el_sum.y,curve.mod_n-el_sum.y],color='tab:orange',linestyle='--')
ax.scatter([el_1.x],[el_1.y],marker='X',color='black',s=size)
ax.scatter([el_2.x],[el_2.y],marker='X',color='black',s=size)
1.5. Elliptic Curves as algebraic Groups¶
An elliptic curve $E_{a,b}$ together with the "addition" defined above forms an Abelian group, i.e. it satisfies the following properties:
- Closed operation: For every $P,Q\in E_{a,b}$: $P+Q\in E_{a,b}$
- Associativity: For every $P,Q,S\in E_{a,b}$: $(P+Q)+S=P+(Q+S)$
- Identity element: there is an element $0$ such that $P+0=0+P=P$ for all $P\in E_{a,b}$
- Inverse element: for every $P\in E_{a,b}$ there is an element $-P$ such that $P+(-P)=0$
- Commutativity: for every $P,Q\in E_{a,b}$: $P+Q=Q+P$.
Properties $3$ and $4$ hold by definition. The group is commutative because the line intersecting $Q$ and $P$ is the same line intersecting $P$ and $Q$ (an algebraic argument would be that interchanging $P$ and $Q$ in the above equations does not change $R=P+Q$). Properties $1$ and $2$ are not trivial but reading the proofs, I did not learn a lot as it is basically a big bunch of algrebraic operations. So I refer to the literature for this, e.g. here.
1.6. Scalar multiplication in elliptic curves¶
The most important mathematical operations in elliptic curves will be a scalar multiplication: $$n * g = g + g + ... +g \text{ }(n\text{ additions})$$
The naive algorithm solves this problem in $\mathcal{O}(n)$ time (i.e. exponential in the number of bits $k=\log_2(n)$). However, we can do much better using the "double and add" algorithm. Basically, if $n=\sum\limits_{i=0}^{n}b_i 2^i$, then $$n * g = \sum\limits_{i=0}^{k}b_i*(2^i*g)$$
So we can simply compute iteratively $2^i*g=2^{i-1}*g+2^{i-1}*g$ and we can compute $n*g$ in $\mathcal{O}(k)$ time (see the implementation above in the EllipticCurveElement class.
Let's look at an example
3*el_1 == el_1 + el_1 + el_1
True
We can compare it with a naive scalar multiplication and see that it much faster:
import time
def naive_scalar(element: EllipticCurveElement, n: int):
cum_sum = EllipticCurveElement(0, element.curve)
for idx in range(n):
cum_sum = cum_sum + element
return cum_sum
x,y = curve.give_point_cloud()
el_1 = EllipticCurveElement((int(x[9]),int(y[9])),curve=curve)
n = 100000
with Timer(f"naive exp(m,k,n) for n = {n} and element = {el_1}"):
result_naive = naive_scalar(el_1,n)
with Timer(f"efficient exp(m,k,n) for n = {n} and element = {el_1}"):
result_efficient = n * el_1
assert result_naive == result_efficient
Time to execute naive exp(m,k,n) for n = 100000 and element = (5,27) in seconds = 1.57e+00 Time to execute efficient exp(m,k,n) for n = 100000 and element = (5,27) in seconds = 4.94e-04
Similar to the RSA system that leverages the above algorithm for modulo multiplication, this algorithm allows us to compute scalar multiplication for very large $n$:
n = int(1e100) #ridiciculously large number
print(n*el_1)
(0,17)
Summary: we are done with the math, we have defined a new algebraic structure on elliptic curves! The significance of this is that we defined a group structure that appears pretty random and is hardly predictable. Perfect for cryptography purposes!
2. Elliptic Curve Cryptographic System¶
The above allows us to define a cryptographic system via elliptic curves. We will need the following parameters:
- $p$=
p: The prime that specifies the size of the finite field $\mathbb{K}=GF(p)$. - $a,b$=
a,b: The coefficients of the elliptic curve equation. - $g$=
base_point: The base point in the elliptic curve - $n$=
order: The order of the cyclic subgroup generated bybase_point - $h$=
cofactor: The cofactor of the subgroup.
To communicate, two participants must agree on the above parameters. Such parameters are standardized by now and there are several examples of such systems available. These are given as parameter sextuples $(p,a,b,g,n,h)$. For example, the Standards for Efficient Cryptography Group (SEC) sets such standard ECCs as an industry consortium.
Note: technically, order and cofactor are not parameters but they are derived from parameters 1.-3. However, we basically rely on other people's computation and can simply check them. Computing the order of an element is not trivial but relies on Schoof's algorithm. For our purposes, it is important that this algorithm is polynomial, i.e. we can compute the order in efficient time.
Let's implement such a system:
class ECCSystem:
"""Abstract meta class for a cryptographic system"""
def __init__(self, p: int, a: int, b: int, base_point: tuple, order: int = None, cofactor: int = None):
self.p = p
self.a = a
self.b = b
assert a<p and b<p and a>=0 and b>=0
self.curve = EllipticCurve(a,b,p)
self.base_point = EllipticCurveElement(base_point,curve=self.curve)
self.order = order
self.cofactor = cofactor
self.n_bits = len(get_binary_representation(self.order))
assert (self.order * self.base_point) == EllipticCurveElement(0,curve=self.curve),\
"Group order that has been given is not valid."
def __eq__(self, ecc):
output = True
output = output & (self.p == ecc.p)
output = output & (self.a == ecc.a)
output = output & (self.b == ecc.b)
output = output & (self.base_point == ecc.base_point)
output = output & (self.order == ecc.order)
output = output & (self.cofactor == ecc.cofactor)
return output
2.1. The SECP256K1 system¶
As an example, we define here the secp256k1 curve as given by the SEC Group. This ECC system is now widely in use as the basis for the verification for all bitcoin transactions, i.e. for digital signatures. Fun fact: Apparently, "secp256k1 was almost never used before Bitcoin became popular" -- Bitcoin Wiki.
class SECP256K1(ECCSystem):
def __init__(self):
p = "0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f"
a = 0
b = 7
x_base = "0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798"
y_base = "0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8"
order = "0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141"
cofactor = 1
p = self.convert_hexstring_to_int(p)
x_base = self.convert_hexstring_to_int(x_base)
y_base = self.convert_hexstring_to_int(y_base)
order = self.convert_hexstring_to_int(order)
super().__init__(p=p,a=a,b=b,base_point=(x_base,y_base),order=order,cofactor=cofactor)
@staticmethod
def convert_hexstring_to_int(string):
string = "".join(string.split(" "))
return int(string,16)
ecc_system = SECP256K1()
3. ECDH (Elliptic-curve Diffie–Hellman)¶
One of the main application of elliptic curves is to enable two participants to privately exchange keys for secure communication. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel. Before that algorithm, secure encrypted communication between two parties required that they first exchange keys by some secure physical means, such as paper key lists transported by a trusted courier. Given that the internet is an insecure channel, this is impractical and not scalable. Fortunately, the Diffie-Hellman key exchange provide an efficient and secure way of doing exactly that.
If Alice and Bob participate in a Diffie-Hellman key exchange, the result will be that Alice and Bob have a shared secret, i.e. a key $k$ (an int) that only they both know but nobody else. This key can then be used further for symmetric encryption, i.e. cyphers that use the same key for encryption and decryption. The most widely used symmetric is the Advanced Encryption Standard that I describe in this tutorial.
3.1. Diffie-Hellman key exchange¶
Diffie-Hellman uses the simple fact that $b*(a*g)=(ba)*g=a*(b*g)$ for a group element $g\in G$ and integers $a,b\in\mathbb{Z}$. More specifically, the process of Diffie-Hellman is as follows (green is public and shared, red is private):
- Alice and Bob agree on a mathematical group $G$ and a base element $g\in G$.
- Alice (resp. Bob) picks secret element $a\in\mathbb{Z}$ (resp. $b\in\mathbb{Z}$) as private keys.
- Alice (resp. Bob) compute $K_{\text{Alice}}=a*g$ (resp. $K_{\text{Bob}}=b*g$) as public keys and exchange them.
- Alice computes $k_{\text{Alice}}=a*K_{\text{Bob}} = a*(b*g) = (ab)*g$. Bob computes $k_{\text{Bob}}=b*K_{\text{Alice}} = b*(a*g) = (ab)*g$.
- Alice and Bob use $k=k_{\text{Alice}}=k_{\text{Bob}}=(ab)*g$ as symmetric key for secure communication.
Differences for Diffie-Hellman are in the group $G$ and the base element $g$ as well as how the random integers $a,b$ are selected. Here, we select $a,b$ by simply selecting from a uniform random distribution on $[0,1,\dots,$ order$-1]$.
Traditionally, finite Field Diffie-Hellman was the standard algorithm for key exchange. In this case, the group $G$ above is the multiplicate group of a finite field $\mathbb{F}_p$ for some prime number $p$. This cryptographic scheme was used in the RFC 7919 protocol. However, we can do even better by using elliptic curves!
3.2. Elliptic Curve Diffie-Hellman (ECDH)¶
In this scheme, the group $G$ is the an elliptic curve over a finite field $\mathbb{F}_p$ for some prime number $p$. Let's implement this:
def get_binary_representation(number: int):
"""function to get binary representation of number"""
binary_representation = ""
while number:
new_string = str(number % 2)
binary_representation = new_string + binary_representation
number = number // 2
return binary_representation
def convert_binary_to_int(string: str):
return int(string,2)
(Since we work with very large ints, I needed to implement my own method to generate a large random number (generate_large_random_int))
class ECDH:
def __init__(self, name: str, ecc_system: ECCSystem):
self.name = name
self.ecc_system = ecc_system
self._private_key = self._generate_private_key()
self._public_key = self._generate_public_key()
self.exchanged_keys = {}
def _generate_private_key(self):
return self.generate_large_random_int(self.ecc_system.order)
def _generate_public_key(self):
return self._private_key * self.ecc_system.base_point
@property
def public_key(self):
return self._public_key
@property
def private_key(self):
raise Exception("You cannot access the private key.")
@public_key.setter
def public_key(self, val):
raise Exception("You are not allowed to alter generated keys")
@staticmethod
def generate_large_random_int(number):
number = number - 1
bin_rep = get_binary_representation(number)
rand_bin_rep = ""
for idx in range(len(bin_rep)-1):
if int(bin_rep[idx]) == 0:
next_flop = "0"
else:
bin_rep_right_side = bin_rep[(idx+1):]
n_flop_one = int(bin_rep_right_side,2)+1
n_flop_zero = int(bin_rep[:(idx+1)]+"0"*(len(bin_rep[(idx+1):])),2)
assert (n_flop_one+n_flop_zero) == number+1
p_flop_one = n_flop_one/(n_flop_zero+n_flop_one)
if float(np.random.uniform())<=float(p_flop_one):
next_flop = "1"
else:
next_flop = "0"
rand_bin_rep = rand_bin_rep + next_flop
if int(next_flop) < int(bin_rep[idx]):
break
leftover_size = len(bin_rep)-len(rand_bin_rep)
if leftover_size>0:
remain_bin_rep = ''.join(np.random.randint(2,size=leftover_size).astype('str').tolist())
rand_bin_rep = rand_bin_rep + remain_bin_rep
rand_number = convert_binary_to_int(rand_bin_rep)
return rand_number
def exchange_keys(self, partner):
exchange_key = self._private_key * partner.public_key
self.exchanged_keys[partner.name] = exchange_key
3.3. ECDH Example¶
Let Alice and Bob exchange their keys:
alice = ECDH("Alice",ecc_system)
bob = ECDH("Bob",ecc_system)
alice.exchange_keys(bob)
bob.exchange_keys(alice)
We can see that their exchanged keys are identitical:
print("Alice's key to communicate with Bob: ", alice.exchanged_keys['Bob'])
print("Bob's key to communicate with Alice: ", bob.exchanged_keys['Alice'])
assert alice.exchanged_keys['Bob']==bob.exchanged_keys['Alice']
Alice's key to communicate with Bob: (1717426092521889969381095628886335111699088619086710983636678707555832726412,33908470532893271647165210424049558988066663286091925021001791320029513886584) Bob's key to communicate with Alice: (1717426092521889969381095628886335111699088619086710983636678707555832726412,33908470532893271647165210424049558988066663286091925021001791320029513886584)
4. ECDAS¶
What is this about? Let's imagine Alice is an author who has written a new novel. She wishes to send a digital copy $m$ to her editor, Bob, via email. However, she wants to ensure that Bob can validate that the digital file indeed comes from her (validation of identity of signatory), and it hasn't been altered during transmission (validation of integrity of message). She also wants to make sure nobody else can falsely claim they sent it. To achieve this, Alice uses the Digital Signature Algorithm (DSA) (or ECDAS).
DSA involves two key components: a private key, which only Alice knows, and a public key, which everyone can access, including Bob. Alice creates a digital signature by using her private key and applying the DSA to her novel's digital file (private key==used to sign a message). This results in a unique digital signature specific to this file and Alice's private key.
Alice then sends the novel and the digital signature to Bob. Upon receiving it, Bob uses Alice's public key and the same DSA to verify the received signature (public key=used to verify a signature). If the signature is validated, Bob knows two things: the digital file is indeed from Alice (authenticity) and the file was not altered during transmission (integrity). In this way, Alice can communicate securely with Bob using the DSA, and Bob has assurance of the document's source and integrity.
DSA is an essential part of secure online communications and transactions, used extensively in different applications ranging from email to e-commerce and more.
4.1. Elliptic Curve Digital Signature Algorithm (ECDSA)¶
In ECDSA, we use the properties of elliptic curves over a finite field.
1. Key Generation:
- Choose a standard ECC system, i.e. parameter sextuple $(p,a,b,g,n,h)$, and agree on a hash function $H$.
- Select a random integer $d$, where $1 < d < n$.
- Compute the public key $q$ as $q = d * g$.
2.Signing: To sign a message $M$
- Compute hash $H(M)$ and set $m=H(M)[:n]$ (truncated hash with same bit size as $n$).
- Choose a random integer $k$, where $1 < k < n$.
- Compute the point $p=(p_x,p_y)=k * g$
- Set $r=p_x$. If $r=0$, choose another $k$ and try again.
- Calculate $s=k^{-1}(m+rd) \text{ mod }n$
- The signature is the pair $(r, s)$. Share it.
3. Verification:
To verify the signature $(r, s)$ on a message $M$, the verifier should have the public key $q$.
- Ensure that $0 < r < n$ and $0 < s < n$.
- Compute hash $H(M)$ and set $m=H(M)[:n]$.
- Compute $u_1 = s^{-1}m \mod n$
- Compute $u_2 = s^{-1}r \mod n$.
- Compute the point $P$ as $P = (P_x,P_y)=u_1*g + u_2*q$.
- The signature is valid if and only if $P_x=r$, i.e. if the x-coordinate of $P$ is equal to $r$.
Proof of correctness¶
For every integer $l$, it holds that $l*g=[l \text{ mod } n]*g$ (as $n*g=0$). In addition, it holds that: $$k=s^{-1}(m+rd)\text{ mod n}$$ Therefore, it holds that: $$P=u_1*g+u_2*(d*g)=[u_1+u_2d]*g=[u_1+u_2d \text{ mod n}]*g=[s^{-1}m+s^{-1}rd\text{ mod n}]*g=[s^{-1}(m+rd)\text{ mod n}]*g=k*g=p$$ It therefore holds that $P_x=p_x=r$. This shows that with the correct signature, we consider the message as verified.
Why the hash function? You might wonder why we need a hash function for this algorithm. The hash function basically reduces the size of the message being signed (the hash value is usually much smaller than the original message), i.e. it has a compressive function, and it reduces it to a fixed size (standardization). It has also other benefits as a hash function is cryptographically secure (see tutorial on hash functions). Here, we will not implement the hash function but simply set $H(M)=M$.
4.3. ECDSA implementation¶
class SignedMessage:
def __init__(self, message: List[Literal[0,1]], r: int, s: int):
self.message = message
self.r = r
self.s = s
class ECDSA:
def __init__(self, name: str, ecc_system: ECCSystem):
self.name = name
self.ecc_system = ecc_system
self._private_key = self._generate_private_key()
self._public_key = self._generate_public_key()
self._public_key_dict = {}
def add_sender(self, sender):
assert sender.ecc_system == self.ecc_system
self._public_key_dict[sender.name] = sender.public_key
@property
def public_key(self):
return self._public_key
@property
def private_key(self):
raise Exception("You cannot access the private key.")
@public_key.setter
def public_key(self, val):
raise Exception("You are not allowed to alter generated keys")
def _generate_private_key(self):
return self.generate_large_random_int(self.ecc_system.order)
def _generate_public_key(self):
return self._private_key * self.ecc_system.base_point
@staticmethod
def generate_large_random_int(number):
number = number - 1
bin_rep = get_binary_representation(number)
rand_bin_rep = ""
for idx in range(len(bin_rep)-1):
if int(bin_rep[idx]) == 0:
next_flop = "0"
else:
bin_rep_right_side = bin_rep[(idx+1):]
n_flop_one = int(bin_rep_right_side,2)+1
n_flop_zero = int(bin_rep[:(idx+1)]+"0"*(len(bin_rep[(idx+1):])),2)
assert (n_flop_one+n_flop_zero) == number+1
p_flop_one = n_flop_one/(n_flop_zero+n_flop_one)
if float(np.random.uniform())<=float(p_flop_one):
next_flop = "1"
else:
next_flop = "0"
rand_bin_rep = rand_bin_rep + next_flop
if int(next_flop) < int(bin_rep[idx]):
break
leftover_size = len(bin_rep)-len(rand_bin_rep)
if leftover_size>0:
remain_bin_rep = ''.join(np.random.randint(2,size=leftover_size).astype('str').tolist())
rand_bin_rep = rand_bin_rep + remain_bin_rep
rand_number = convert_binary_to_int(rand_bin_rep)
return rand_number
@staticmethod
def convert_string_to_bit(string):
ba = bitarray.bitarray()
ba.frombytes(string.encode('utf-8'))
return np.array(ba.tolist())
def convert_M_to_m(self, message: str):
"""Function to convert a bit message of arbitrary length to correct input."""
message_bit = ECDSA.convert_string_to_bit(message)
binary_string = "".join(message_bit[:self.ecc_system.n_bits].astype('str').tolist())
message_int = convert_binary_to_int(binary_string)
return message_int
def sign_message(self, message: List[Literal[0,1]]):
m = self.convert_M_to_m(message)
r = 0
while r == 0:
k = self.generate_large_random_int(self.ecc_system.order)
P = k * self.ecc_system.base_point
r = P.x
k_inv = inverse(k,self.ecc_system.order)
s=k_inv*(m+r*self._private_key)%self.ecc_system.order
return SignedMessage(message,r=r,s=s)
def verify_message(self, message: SignedMessage, name: str):
assert message.r<self.ecc_system.order and message.s<self.ecc_system.order,\
"Signature invalid. r<n and s<n is a requirement."
m = self.convert_M_to_m(message.message)
s = message.s
s_inv = inverse(s,self.ecc_system.order)
u_1 = (s_inv * m) % self.ecc_system.order
u_2 = (s_inv * message.r) % self.ecc_system.order
P = u_1*self.ecc_system.base_point + u_2*self._public_key_dict[name]
return message.r == P.x
4.4. ECDSA example¶
Let's imagine that we have 3 senders: Alice, Bob, and Carl.
alice = ECDSA(name="Alice", ecc_system=ecc_system)
bob = ECDSA(name="Bob", ecc_system=ecc_system)
carl = ECDSA(name="Carl", ecc_system=ecc_system)
Let's imagine Bob wants to set himself up for receiving messages and verifying them. He adds Alice and Carl as senders (adding their public keys):
bob.add_sender(alice)
bob.add_sender(carl)
Let Alice write a message and sign it.
message = "You should go to Turf Tavern tomorrow at 8pm."
signed_message = alice.sign_message(message)
1st scenario: Alice sends message but Carl tries to claim it comes from him
print("Bob's verification on Alice's message with Alice's public key: ", bob.verify_message(signed_message,alice.name))
print("Bob's verification on Alice's message with Carl's public key: ", bob.verify_message(signed_message,carl.name))
Bob's verification on Alice's message with Alice's public key: True Bob's verification on Alice's message with Carl's public key: False
2nd scenario: Carl corrupts message
signed_message.message = "You should go to the Italian restaurant tomorrow at 6pm."
print("Bob's verification on Alice's message with Alice's public key: ", bob.verify_message(signed_message,alice.name))
Bob's verification on Alice's message with Alice's public key: False
4.5. Example of a security failure: the PlayStation 3¶
Sometimes details matter. And in cryptography, they especially do. Note that in the ECDSA algorithm we generate the integer $k$ randomly anew for every novel signature? In fact, this important. It turns out that in 2010, the PlayStation was using the same key $k$ for different signatures. However, in this case $r$ is the same for all signatures and one can recover $k$ in this case: let $(r,s),(r,s')$ be two keys both generates with the same $k$ verifying messages $m,m'$. Then: $$s=k^{-1}(m+rd)\text{ mod }n$$ $$s'=k^{-1}(m'+rd)\text{ mod }n$$ $$\Rightarrow s'-s=k^{-1}(m'-m)\text{ mod }n$$ $$\Rightarrow k=(s'-s)^{-1}(m'-m)\text{ mod }n$$ Note that in the above equation, an attacker would know all variables on the left side. Hence, an attacker would know $k$. Hence, an attacker would know the private key by computing: $$d=r^{-1}(ks-m)\text{ mod }n$$ In this case, hacker's had basically access to the PS3 - a really bad result...
Summary¶
With this, we complete our tutorial on elliptic curve cryptography. Let's summarize the key points:
- Definition: Elliptic curves are curves in $2$d space defined by an equation of the form $y^2=x^3+ax+b$.
- GF(p): For cryptography, one defines elliptic curves over prime Galois fields $GF(p)$ (i.e. via modular arithmetic).
- Group: One can define a group operation on elliptic curves that corresponds to taking intersection with lines crossing points in an elliptic curve.
- Scaler multiplication=Public key generation: efficient scalar multiplication $k*g$ for a base point $g$ allows us to generate public keys efficiently for very large $k$.
- ECC: an elliptic curve cryptography system is defined by a sextuple $(p,a,b,g,n,h)$ defining the field $GF(p)$, a curve $E_{a,b}$, a base point $g$, its order $n$, and its cofactor $h$. Such systems are standardized.
- ECDH: the elliptic curve Diffie Hellman algorithm enables an afficient exchange of secret keys by scalar multiplication of your own private key with the public key of your intended communication partner.
- ECDSA: the Elliptic Curve Digital Signature Algorithm (ECDSA) allows to ensure the integrity and authenticity of a message. Signing works by computing a signature tuple $(r,s)$ via modulator arithmetic using the private key. Verification works by using (r,s) to compute a point $P$ on the elliptic curve, whose x-coordinate $P_x$ should equal $r$.
A. Appendix - Optional: Mathematical DeepDive into Elliptic Curves¶
A.1. Why do we need to avoid singularity? Characterizing all elliptic curves...¶
In this section, we want to explain why we want to avoid singularities and want to classify elliptic curves into two main classes.
Let's consider the polynomial $f(x)=x^3+ax+b$ defining the elliptic curve $E_{a,b}$. As a cubic polynomial, there will be a root $c$, i.e.: $$f(x)=(x-c)(x^2+rx+s)=(x-c)q(x)$$ for some reals $r,s$. There are 4 options:
- $q(x)$ has no roots: then the elliptic curve will be a 1-dimensional smooth manifold intersecting the x-axis at $c$. It is smooth because $\frac{d}{dx}\sqrt{x-c}\to \infty$ for $x\to c$. It will be fully connected (i.e. you can draw the elliptic curve in one line) and will look like this:
c,r,s = -2,-2,3
def f_x(x):
return (x-c)*(x**2+r*x+s)
x_grid = np.linspace(c,5,1000)
y_grid = np.sqrt(f_x(x_grid))
fig, ax = plt.subplots()
ax.plot(np.concatenate([x_grid[::-1],x_grid]),np.concatenate([y_grid[::-1],-y_grid]))
ax.vlines(c,ax.get_ylim()[0],ax.get_ylim()[1],linestyle="--",color="red", label="c")
ax.legend()
<matplotlib.legend.Legend at 0x1142bb940>
- $q(x)$ has a single root $d\neq c$, i.e. $q(x)=(x-d)^2$ and $f(x)=(x-c)(x-d)^2$. If $d<c$, then $I=(d,0)$ would be an isolated point of the curve. That would imply problems when we would define $I+I$. Therefore, let $c<d$. Then this implies that $x\geq c$ for all $(x,y)$ on the curve and $$\begin{align*} y = \pm (x-c)^{1/2}(x-d) \end{align*} $$ For every $c<x<d$ and for every $x>d$, there are two solutions to the above equation. However, for $x=d$, there is only one. That means that the curve would have a self-intersecting point at $d$. It would look something like this:
c,d = -2, 2
def f_x(x):
return (x-c)*(x-d)**2
x_grid = np.linspace(c,5,1000)
y_grid = np.sqrt(f_x(x_grid))
fig, ax = plt.subplots()
ax.plot(np.concatenate([x_grid[::-1],x_grid]),np.concatenate([y_grid[::-1],-y_grid]))
ax.vlines(c,ax.get_ylim()[0],ax.get_ylim()[1],linestyle="--",color="red", label="c")
ax.vlines(d,ax.get_ylim()[0],ax.get_ylim()[1],linestyle="--",color="green", label="d")
ax.legend()
<matplotlib.legend.Legend at 0x11432f700>
We want to avoid this for the following reason: let $p$ be a another point on the curve, then the line $L=\bar{pc}$ would only intersect the curve at two points but none of them is tangential. So how would we define this? Would we set $c+p=c$? But then $p=-c+(c+p)=-c+c=0$ for all other points. So that does not make any sense. Would we set $c+p=p$? Then $c=0$, i.e. it would be the point at infinity. Would we set $c+p=\inf$? But then $p=-c$ for all point and then all points are equal. Therefore, such a curve would not be well-defined as group.
- $q(x)$ has a single root $d=c$, i.e. $q(x)=(x-c)^2$ and $f(x)=(x-c)^3$. This implies that $x\geq c$ and $y=\pm(x-c)^{\frac{3}{2}}$ for all $y\geq c$. This would imply that there is a cusp at $y=c$. We don't want that because that would mean that there is a line intersecting at the cusp point and another point that would not be a tangential to any of the two points. How would we define $c+p$ for a any point $p$ on the curve? By taking the limit for a sequence $c_n\to c$, we would need to set $p+c=c$. But then $p=(p+c)-c=c-c=0$ for every point. That's a contradiction! So the elliptic curve addition would not be well-defined in this case. The curve would look something like this:
c = -2
p_x = 4
def f_x(x):
return (x-c)**3
p_y = np.sqrt(f_x(p_x))
x_grid = np.linspace(c,7,1000)
line_to_p = (p_y)*x_grid/(p_x-c)-c*p_y/(p_x-c)
y_grid = np.sqrt(f_x(x_grid))
fig, ax = plt.subplots()
ax.plot(np.concatenate([x_grid[::-1],x_grid]),np.concatenate([y_grid[::-1],-y_grid]))
ax.scatter([p_x],[p_y],s=100,label="P",marker='X',color='green')
ax.plot(x_grid,line_to_p,linestyle='--',color='black',label='c-->P')
ax.vlines(c,ax.get_ylim()[0],ax.get_ylim()[1],linestyle="--",color="red", label="c")
ax.legend()
<matplotlib.legend.Legend at 0x1143626d0>
- $q(x)$ will have two different roots $d,e\neq c$, i.e. $f(x)$ will have three different roots. Let's assume $c<d<e$ (otherwise exchange labels). Then either $c\leq y\leq d$ or $y\geq e$. Therefore, the curve will not be connected but will have two distinct connected components.
c,d,e = -2,3,5
def f_x(x):
return (x-c)*(x-d)*(x-e)
x_grid = np.concatenate([np.linspace(c,d,1000),np.linspace(e,10,1000)])
y_grid = np.sqrt(f_x(x_grid))
fig, ax = plt.subplots()
ax.scatter(np.concatenate([x_grid[::-1],x_grid]),np.concatenate([y_grid[::-1],-y_grid]))
ax.vlines(c,ax.get_ylim()[0],ax.get_ylim()[1],linestyle="--",color="red", label="c")
ax.vlines(d,ax.get_ylim()[0],ax.get_ylim()[1],linestyle="--",color="green", label="d")
ax.vlines(e,ax.get_ylim()[0],ax.get_ylim()[1],linestyle="--",color="black", label="e")
ax.legend()
<matplotlib.legend.Legend at 0x1226b81f0>
To check the above 4 conditions, one can use the so-called discriminant of a polynomial - a discrimant is zero if and only if the polynomial has a multiple root. As $f(x)=x^3+ax+b$ is a depressed cubic, the discriminant can be computed as: $$D(a,b)=-4a^3-27b^2$$ and it holds that
- $D(a,b)>0$ if $f(x)$ has a single real root (i.e. if the curve has a single connectivity component): this is equivalent to $$a<-\frac{3}{4}|b|^{2/3}$$ In particular, $a$ must be negative.
- $D(a,b)<0$ if it has multiple roots, i.e. if $f(x)$ has multiple connectivity components.
Summary: an elliptic curve is only well-defined as a group, if $f(x)$ has
- A single real root $c$: in this case, $y\geq c$ and the curve has a single connectivity components. This is equivalent to $4a^3+27b^2>0$.
- 3 distinct real roots $c<d<e$: in this case $c\leq y\leq d$ and $y\geq e$, i.e. there are two connectivity components. This is equivalent to $4a^3+27b^2<0$.
If the discriminant is zero, i.e. $4a^3+27b^2=0$ then the curve has singularities (cusps, self-intersecting points, etc.). In this case, we cannot define a group law on elliptic curves.
A.2. Why is the group operation well-defined? I.e. what makes elliptic curves special¶
In chapter 1, we showed that for the elliptic curve addition to be well-defined, we need to show that:
- If a line and an elliptic curve intersect in exactly two points, the line is tangent to the curve at exactly one of the two points.
- Every tangential of an elliptic curve intersects with exactly one other point of the curve.
Proof of statement 1 (from Stack Exchange):
Let $E_{a,b}$ be an elliptic curve given by $y^2=x^3+ax+b$ and let $f(x)=\sqrt{x^3+ax+b}$. Let the line be $L:y=g(x)=mx+n$ such that $L$ and $E$ intersect exactly at 2 points, $(x_1,y_1)$ and $(x_2,y_2)$. This means that $g(x)^2 - f(x)^2$ is a polynomial of degree 3 with only 2 roots, namely $x_1$ and $x_2$, so one of them is a repeated root. Let us say $x_1$ is repeated, then $g(x)^2 - f(x)^2 = (x - x_1)^2(x - x_2)$.
Thus, if we differentiate at a point $x$, we obtain: $$\begin{align*} 2g(x)g'(x) - 2f(x)f'(x) = (x - x_1)(2(x - x_2) + (x - x_1)). \end{align*}$$
1.st case: $y_1 \neq 0$. Then evaluate the above at $x = x_1$ to get: $$\begin{align*} 2g(x_1)g'(x_1)-2f(x_1)f'(x_1)&=0\\ \Rightarrow y_1(m-f'(x_1))&=0 \end{align*} $$ This implies that $f'(x_1)=m$. I.e. $f(x_1)=g(x_1)$ and $f'(x_1)=g'(x_1)$, i.e. the line is a tangent at $x_1$.
2nd case: $y_1 = 0$. Then either (i) $\lim_{x \to x_1^+} f'(x) = \infty$ or (ii) $\lim_{x \to x_1^-} f'(x) = \infty$. Either way, by taking an appropriate limit in the equation, we find that $\lim_{x \to a1} g'(x) = \infty$ which implies that $L$ must be a vertical line $x = x_1$.
Proof of statement 2
Let again be $E_{a,b}$ be an elliptic curve given by $y^2=x^3+ax+b$ and let $f(x)=\sqrt{x^3+ax+b}$. Let $g(x)=mx+n$ be a line and $g(x_1)=f(x_1)$. It holds that the number of intersections between $g$ and $f$ equals the number of roots of the polynomial $p(x)=f(x)^2-g(x)^2$. If $g(x)$ is a tangential of $f(x)$, the the polynomial must have a multiple root. Therefore, there must exactly one other root, the other intersecting point.