ECC

---

References:

• Elliptic Curve Cryptography: a gentle introduction
• [SEC1v2] SEC 1: Elliptic Curve Cryptography (Version 2.0), Standards for Efficient Cryptography Group (SECG) founded by Certicom
• [SEC2v2] SEC 2: Recommended Elliptic Curve Domain Parameters (Version 2.0)
• [GECC] Guide to Elliptic Curve Cryptography, Darrel Hankerson, Alfred Menezes, and Scott Vanstone. 2004.

Curves:

• https://safecurves.cr.yp.to
• EdDSA Ed25519
  • https://ed25519.cr.yp.to/
• DH Curve25519
• Brainpool curves (non-NIST)
• NIST curves specified in FIPS 186-5 and SP 800-186
• Hyperelliptic calculation code snippets and implementation help

Further reading:

• [GCAC] A Graduate Course in Applied Cryptography, Dan Boneh and Victor Shoup
• [CINTA] A Computational Introduction to Number Theory and Algebra, Victor Shoup
• [HAC] Handbook of Applied Cryptography, Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone
• [ITMC] Introduction to Modern Cryptography, Jonathan Katz and Yehuda Lindell (3rd Edition)

Dependencies:

This notebook uses sage math as kernel

import sage.misc.banner # sage math version info 
rchars = "┘─│┐┌└"
smallbanner = sage.misc.banner.banner_text(full=True)
for c in rchars:
    smallbanner = smallbanner.replace(c,"") # remove ascii art box
print(smallbanner)
#banner() # full banner with box

 SageMath version 9.5, Release Date: 2022-01-30                     
 Using Python 3.10.12. Type "help()" for help.                      

ECC - Elliptic Curve Cryptography

• RSA relies on the hardness of integer factorization
• Diffie-Hellman relies on hardness of discrete logarithm problem
• ECC also relies on discrete logarithm problem, but over the algebraic structure of elliptic curves over finite fields. This makes the (same) problem harder
  • Elliptic Curve Discrete Logarithm Problem (ECDLP)

Advantage:

• Shorter key length without sacrificing high computational security
  • This means faster computation while retaining hardness against attacks

Some example algorithms making use of ECC:

• Elliptic Curve Diffie-Hellman (ECDH)
• Elliptic Curve Digital Signature Algorithm (ECDSA)
• Edwars-curve Digital Signature Algorithm (EdDSA)

Key sizes

• Cryptographic key length recommendation

(image source)

Elliptic curves over finite fields

In ECC elliptic curves are defined over some finite field $\mathbb{F}$, i.e., the $x$ and $y$ coordinates of points on the elliptic curve have to be elements of the underlying finite field, i.e., $x,y \in \mathbb{F}$.

An example for a finite field is the set of non-negative integers modulo a prime number $p$, i.e., $\mathbb{Z}_p$ where $ p \in \textrm{Primes}$. We denote this finite field with $\mathbb{F}_p$

Elliptic curves representations

In ECC there are several different ways to express elliptic curves such as Weierstrass, Montgomery, and (twisted) Edwards representations. Different representations are used for reasons of efficiency and/or implementation-level security, such as, better resistence to side-channel attacks.

(Long) Weierstrass represetation

An elliptic curve $E$ in (long) Weierstrass form is defined by the parameters $a_1,a_2,a_3,a_4,a_5 \in \mathbb{F}_p$ [GECC]: $$ y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_5 $$

Together with a special point at infinity $\mathcal{O}=\infty$. The set of points on $E$ over finite field $\mathbb{F}_p$ is thus defined as: $$ E(\mathbb{F}_p) = \{(x,y) \in \mathbb{F}_p, y^2 + a_1xy + a_3y - x^3 - a_2x^2 - a_4x - a_5=0\} \cup \{ \mathcal{O} \} $$

Every elliptic curve, with a characteristic ($p$) of the underlying finite field not equal to $ 2 $ or $ 3 $, can be transformed into Weierstrass form [ITMC].

(Short) Weierstrass representation

The simplified, or short, Weierstrass form is a simplified representation of the long Weierstrass form which is commonly used instead of the long version as they can be transformed into each other [GECC].

The simplified Weierstrass representation is defined by the parameters $a,b \in \mathbb{F}_p$: $$ y^2 = x^3 + ax + b $$ Moreover, $a,b \in \mathbb{F}_p$ must satisfy $4a^3 + 27b^2 \not \equiv 0 \pmod p$. This should ensure that the curve is smooth, i.e., the equation $ x^3 + ax + b = 0 $ has no repeated roots [ITMC][SEC1v2].

Smooth and Singular curves

A smooth curve has no sharp points, self-intersections, or singularities. More formally, it is a curve in which every point has a well-defined tangent line, and the curve is differentiable at all points. For cryptographic applications we want curves to be smooth!

Singular curves are not smooth. Singular points can take two forms:

1. A node: The curve intersects itself at a point. i.e., two distinct tangent lines intersect at the singular point.
2. A cusp: The curve bends sharply into itself, i.e., a single tangent line touches the curve with higher multiplicity. Singular elliptic curves are no longer elliptic curves in the strict mathematical sense, as they fail to satisfy the smoothness condition.

Example: Singular curve

# y^2 = x^3 + a4x + a5
a1=0; a2=0; a3=0; a4=0; a5=0
try:
    EC = EllipticCurve(RR,[a1, a2, a3,a4 ,a5]) # Weierstrass curve
    p = plot(EC,thickness=3,xmin=-2,xmax=2,ymin=-2,ymax=2)
    p.show()
except ArithmeticError:
    print("ArithmeticError: Sage EllipticCurve won't even allow defining a singular curve!")

ArithmeticError: Sage EllipticCurve won't even allow defining a singular curve!

Singular elliptic cruve $y^2 = x^3$ with a cusp

var('x y'); a = 0; b = 0 
func = y^2 - (x^3 + a*x + b) # y^2 = x^3 # (a cusp) 
p = implicit_plot(func, (x, -3, 3), (y, -3, 3), color='blue', title="Singular elliptic curve $y^2 = x^3$ with cusp")
p.show()

Singular elliptic cruve $y^2 = x^3 - 3x +2 $ with a node

var('x y'); a = 3; b = 2 
func = y^2 - (x^3 - a*x + b) # y^2 = x^3 - 3x +2 # (a node) 
p = implicit_plot(func, (x, -3, 3), (y, -3, 3), color='blue', title="Singular elliptic curve $y^2 = x^3 - 3x +2 $ with node")
p.show()

Elliptic curves over $\mathbb{R}$

The following illustration is often used to depict elliptic curves, but elliptic curves in cryptography are used over finite fields not the real numbers! Nevertheless, such representations are useful to explain the basic operations in ECC.

• Simplified Weierstrass equation over the real numbers $\mathbb{R}$ with $a = -1$ and $b = 1$: $$ y^2 = x^3 + ax + b $$

a=-1; b=1; a1=0;a2=0;a3=0; a4=a; a5=b; # define as long Weierstrass
EC = EllipticCurve(RR,[0, 0, 0,-1 ,1]) # Weierstrass curve
p = plot(EC,thickness=3,xmin=-2,xmax=2,ymin=-2,ymax=2)
if SAVE_FIGURES: p.save("./figures/ecc_over_R.png")
#p.show()

Elliptic curves over $\mathbb{F}_p$

In ECC we define elliptic curves $E(\mathbb{F}_p)$ over $\mathbb{F}_p$ in simplified Weierstrass form as follows:

• Let $ \mathbb{F}_p $ be a prime finite field where $ p \in \textrm{Primes} $
• The parameters $a,b \in \mathbb{F}_p $
• Let $a,b \in \mathbb{F}_p$ satisfy $4a^3 + 27b^2 \not \equiv 0 \pmod p$
• The elliptic curve is set of solutions, i.e., points $ P=(x,y)$ on the curve, for all pairs $x,y \in \mathbb{F}_p$ to the defining equation: $$ \begin{align*} E(\mathbb{F}_p): y^2 \equiv x^3 + ax + b \pmod p \\ \end{align*} $$
• Plus the point at infinity $\infty$ or $\mathcal{O} \in E(\mathbb{F}_p)$, s.t., $P + \mathcal{O} = \mathcal{O} + P = P $

p=103; assert p in Primes(); FF=FiniteField(p); # define finite field 

a=-1; b=1; a1=0;a2=0;a3=0; a4=a; a5=b; # define as long Weierstrass
EC=EllipticCurve(FF,[a1,a2,a3,a4,a5]); EC

Elliptic Curve defined by y^2 = x^3 + 102*x + 1 over Finite Field of size 103

Elliptic curves over $\mathbb{F}_p$

Note that elliptic curves over finite fields are no really "curves", but they are still symmetric along the $ x $ axis (because of $y^2$)

• Therefore, up to two solution for each $ x $ exist, i.e., $y$ and $-y$
• Therefore, for each point $P=f(x,y)$ a symmetric inverse $-P=f(x,-y)$ is defined

Example: Compute the points on an elliptic curve

The following is an example of how to compute all points on a small elliptic curve over $\mathbb{F}_p$, where $p = 103$

p=103; assert p in Primes(); FF=FiniteField(p);
a1=0;a2=0;a3=0; a4=-1; a5=1; EC=EllipticCurve(FF,[a1,a2,a3,a4,a5]); EC

Elliptic Curve defined by y^2 = x^3 + 102*x + 1 over Finite Field of size 103

len(EC.points()) # use built in sage math function

112

# naively compute all points on elliptic curve manually in python (cf. https://stackoverflow.com/questions/76143329/how-to-get-all-the-solution-points-over-a-finite-field-of-an-elliptical-curve)
ec_points = set(); p=103; assert p in Primes();
for x in range(0,p):
    for y in range(0,p):
        if (y**2 - (x**3 - x + 1)) % p == 0: 
            ec_points.add( (x,y) )
len(ec_points)

111

Question: Which point is missing?

ec_diff = list(); ec_match = list() # naively match points  
for Q in EC.points():
    match=False
    for P in ec_points:
        if not Q.is_zero() and Q.xy()[0] == P[0] and Q.xy()[1] == P[1]:
            ec_match.append({"P":P,"Q":Q})
            match=True
            break
    if not match:
        ec_diff.append(Q)

len(ec_match)

111

ec_diff # Point at infinity if ( x : y : 0 ) and 1 otherwise

[(0 : 1 : 0)]

ec_diff[0].is_zero() # check if point at infinity

True

Number of points on elliptic curves over $\mathbb{F}_p$

The number of points $E(\mathbb{F}_p)$ on the elliptic curve $E$ over $\mathbb{F}_p$ is denoted by $\# E(\mathbb{F}_p)$, or $|E(\mathbb{F}_p)|$, and is called the order of the curve. This number is somewhat close to the prime $ p $ and can be approximated by the Hasse Theorem: $$ p + 1 - 2 \sqrt{p} \leq \# E(\mathbb{F}_p) \leq p + 1 + 2 \sqrt{p} $$

p=103; assert p in Primes(); FF=FiniteField(p); 
FF.order()  # order of the underlying FF

103

EC=EllipticCurve(FF,[0,0,0,-1,1]); EC

Elliptic Curve defined by y^2 = x^3 + 102*x + 1 over Finite Field of size 103

assert EC.order() == len(EC.points()); 
EC.order() # order of the EC

112

Generators for elliptic curves

A generator $G$ of an elliptic curve has the same order as the curve and hence can generate all points on the curve: $$ \{G,G\cdot 1,G \cdot 2,\dots,G \cdot \#E(\mathbb{F}_p)\} $$

G = EC.gen(0); G.xy() 

(2, 78)

G # (x :  y : 0 iff point at infinity, 1 otherwise)

(2 : 78 : 1)

G.order()

112

Generators for elliptic curves

EC.order()

112

print(G,G*2,G*111,G*112,G*113) # last point is the starting point G again

(2 : 78 : 1) (4 : 79 : 1) (2 : 25 : 1) (0 : 1 : 0) (2 : 78 : 1)

print(f"point at infinity = {G*112}") 

point at infinity = (0 : 1 : 0)

(G*112).is_zero()

True

ECC operations

The following are some illustrations of basic elliptic curve operations on a Weierstrass curve, either over the real numbers $\mathbb{R}$, or the finite field $\mathbb{F}_{103}$: $$ \begin{align*} y^2 &= x^3 + ax + b \\ a &= -1 \\ b &= 1 \end{align*} $$

Due to the nature of the ECDLP, a important operation in elliptic curve cryptography is point multiplication, or scalar multiplication, which refers to the multiplication of a scalar value $k$ with a point $G$ on an elliptic curve over a finite field, to gain another point $Q$ which is also located on the elliptic curve. To perform these point multiplication operations, two main calculations are needed in general: point addition and point doubling.

Inverse of a point

$$ \begin{align*} P1 &= (x,y) = (1,1) \\ P2 &= -P1 = (x,-y) = (1,-1) \\ \end{align*} $$

Point doubling

This operation refers to the addition of one point to itself, hence the name point doubling. $$ P+P=2P=Q $$

Point doubling formular for $ Q = P + P $

$$ \begin{align*} P &= \langle p_x, p_y \rangle \\ m &= \frac{3p_x^2 + a}{2p_y} \\ r_x &= m^2 - 2p_x \\ r_y &= m \cdot (p_x - r_x) - p_y \\ Q &= \langle r_x, r_y \rangle \end{align*} $$

def point_double_sage(P,a): 
    # EC point doubleing in sage, this function works with 
    # x,y of points over the reals as well as over FF
    if P is None:
        return None 
    xp, yp = P
    m =  (3 * xp ** 2 + a) / (2 * yp) 
    xr =  m**2 - 2*xp 
    yr =  m * (xp - xr) - yp
    return (xr, yr)

p = 31
FF = FiniteField(p)
EC = EllipticCurve(FF, [0,0,0,-1,1]); EC # a=-1 b=1
P = EC.random_element(); P

(1 : 30 : 1)

Q_point = P + P; Q_point # sage point doubling simple implicit notation 

(30 : 30 : 1)

Q_xy = point_double_sage( P.xy(), a=FF(-1) ); Q_xy

(30, 30)

Point doubling - Point at infinity

In the visual example of point doubling the solution is the point at infinity $\mathcal{O}$. All vertical lines (e.g., additions) would also result in the point at infinity. $$ P+P=2P=\infty=\mathcal{O} $$

Point addition

$$ \begin{align*} P1 + P2 = Q \end{align*} $$

Point addition over $\mathbb{F}_p$

This time we use $\mathbb{F}_{103}$ as underlying finite field: $$ \begin{align*} P1 + P2 = Q \end{align*} $$

Point addition formular for $ Q = P1 + P2 $

$$ \begin{align*} P1 &= \langle p1_x, p1_y \rangle; P2 = \langle p2_x, p2_y \rangle \\ m &= \frac{p1_y - p2_y}{p1_x - p2_y} \\ r_x &= m^2 - p1_x - p2_x \\ r_y &= m \cdot (p1_x - r_x) - p1_y \\ Q &= \langle r_x, r_y \rangle \end{align*} $$

def point_addition_sage(P1, P2, a):
    # EC point addition, this function works with 
    # x,y of points over the reals as well as over FF
    if P1 is None or P2 is None: # check for the zero point 
        return P1 or P2
    x1, y1 = P1
    x2, y2 = P2
    if x1 == x2:
        return point_double_sage(P1,a)
    m = (y1 - y2) / (x1 - x2)
    xr = m**2 - x1 - x2
    yr = m * (x1 - xr) - y1
    return (xr, yr)

p = 31; a = FF(-1); b = FF(1)
FF = FiniteField(p)
EC = EllipticCurve(FF, [0,0,0,a,b]); EC
P1 = EC.random_element()
P2 = EC.random_element()
print(P1.xy())
print(P2.xy())
P1x,P1y = P1.xy()
P2x,P2y = P2.xy()

(0, 1)
(6, 26)

Q_point = P1+P2; Q_point

(20 : 18 : 1)

Q_xy = point_addition_sage(P1.xy(),P2.xy(),a=FF(-1)); Q_xy

(20, 18)

Point multiplication

$$ Q=kG=\overbrace{G+G+G+...+G}^{\text{k times G}} $$

This chain of additions can be broken up into several multiplications and additions. For example if $k=17$ the chain of $G+G+G+...+G$ can be expressed as $(2\cdot (2\cdot (2\cdot (2\cdot G))))+G = 17\cdot G$. This reduces $17$ additions to $4$ multiplications and $1$ addition operation.

var("g"); 2*2*2*2*g+g

17*g

Point multiplication formular for $ Q = kG $

def point_multiplication_sage(k, P, a):
    result = None # Initialize with point at infinity 
    addend = P
    for b in [int(bit) for bit in bin(int(k))[2:][::-1]]: # from LSB to MSB
        if b:
            result = point_addition_sage(result, addend, a=a)
        addend = point_double_sage(addend, a=a)
    return result

Example: Point multiplication

p = 31
FF = FiniteField(p)
EC = EllipticCurve(FF, [0,0,0,-1,1]); EC # a=-1 b=1
P = EC.random_element(); P

(25 : 16 : 1)

import random
k = random.randint(1,p); k

21

Q_point = k*P; Q_point

(6 : 5 : 1)

Q_xy = point_multiplication_sage(k, P.xy(), a=FF(-1) ); Q_xy

(6, 5)

ECC domain parameters

In case of ECC over prime fields ($\mathbb{F}_p$), where $p \in \textrm{Prime}$, the following domain parameters have to be defined:

• $p$: The prime defining the field $\mathbb{F}_p$, under which the curve operates. All point operations $(+,\cdot)$ are taken modulo $p$
• $a,b$: Two integers which are the coefficients defining the curve $E$
• $G$: The generator- or base-point used as a starting point for multiplications.
• $n$: The order of $G$, which is the number of distinct points on the curve which can be computed by multiplying $G$ with a scalar value, i.e., $\{1 \cdot G, 2 \cdot G, 3\cdot G, \dots, (n-1) \cdot G\}$
• $\#E(\mathbb{F}_p)$: The order of the curve, i.e., the total number of points on the elliptic curve over $\mathbb{F}_p$.
• $h$: The cofactor, i.e., number of points on the elliptic curve divided by $n$. Ideally $ h = 1 $, thus the order of the generator equals the order of the curve.

Example: Secp256k1

This is an example instanciation of curve secp256k1 specified in [SEC2v2] and allowed in [SP 800-186] for blockchain-related applications. The curve has the following short Weierstrass form: $$ y^2 \equiv x^3 + 7 \pmod p $$

# Secp256k1 from https://www.secg.org/sec2-v2.pdf
p=2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1
a=0;b=7
x_G=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
y_G=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
h=1
FF = FiniteField(p)
EC = EllipticCurve(FF, [0,0,0,a,b]); EC
G = EC.point((x_G,y_G))

Sanity checking of the curve

The trace of an ellipcit curve over a finite field is defined as $ t = p + 1 - | E(\mathbb{F}_o) |$ [ITMC]. Since the order of a curve can be computed efficiently this can be a first sanity check if everything has been defined correctly.

t=p+1 - EC.order(); t 

432420386565659656852420866390673177327

EC.trace_of_frobenius() # also available as function in sage

432420386565659656852420866390673177327

assert EC.order() == G.order() * h == n * h

SK = 104180048334815325830625441518578326979476797852517177973225433558381925820558
PK = SK * G
(hex(PK[0]),hex(PK[1]))

('0x4e7927e13423b2afa70f1299ad041978e55a1d9af1860a826ddb15024ed7da2',
 '0xd369291d811f2df550b1153d12ca5d3132b7f2e658a90300c0daa39a476db17c')

ECDH

---

ECDH

Elliptic Curve Diffi-Hellman (ECDH) is a key agreement protocol that can be used as its finite field (aka. algebraic) counterpart. The major difference is the specification and operation over some elliptic curve defined by the domain parameters $(p,a,b,G,n,h)$. The goal is it to establish a shared secret over some public channel as follows:

• Alice and Bob pick secret keys $d_A,d_B \in [1,n-1]$
• Alice computes his public key $ Q_A = d_A \cdot G$ and sends it to Bob
• Bob computes his public key $ Q_B = d_B \cdot G$ and sends it to Alice
• Alice computes the shared (secret) key $ SK = d_A \cdot Q_B $ (point on curve)
• Bob computes the shared (secret) key $ SK = d_B \cdot Q_A $ (point on curve)
• They end up with the same point because $ d_A \cdot Q_B = d_A \cdot d_B \cdot G = d_B \cdot d_A \cdot G = d_B \cdot Q_A $
• They can now use the $ x $ coordinate of the shared point to derive further keying material, e.g., for encryption

Example: ECDH

def ecdh(p,a,b,P,d):
    FF = FiniteField(p)
    EC = EllipticCurve(FF, [0,0,0,a,b])
    P = EC.point(P)
    return d * P

# Domain parameters for secp256k1 from https://www.secg.org/sec2-v2.pdf
p=2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1
a=0; b=7; n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
x_G=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
y_G=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
G = (x_G, y_G)

Example: ECDH

d_A  = gen_rand_int(int(1),int(n-1)) # secret key (sk) Alice
d_B  = gen_rand_int(int(1),int(n-1)) # secret key (sk) Bob
Q_A  = ecdh(p,a,b,G,d_A) # public key (pk) Alice
Q_B  = ecdh(p,a,b,G,d_B) # public key (pk) Bob
SK_A = ecdh(p,a,b,Q_B,d_A) # shared secret (SK) computed by Alice 
SK_B = ecdh(p,a,b,Q_A,d_B) # shared secret (SK) computed by Bob
print(f"SK_A   = {SK_A}")
print(f"SK_B   = {SK_B}")
print(f"x_k    =  {SK_A[0]}") # shared secret x of point

SK_A   = (103311599230891244196141501519719295246318952618282194758791088695620770368340 : 42089362789046722136743999528395994150103720055565281477524014906859215400990 : 1)
SK_B   = (103311599230891244196141501519719295246318952618282194758791088695620770368340 : 42089362789046722136743999528395994150103720055565281477524014906859215400990 : 1)
x_k    =  103311599230891244196141501519719295246318952618282194758791088695620770368340

ECDSA

---

ECDSA - Signature creation

Given a curve $(p,a,b,G,n)$, and a secret key $d_A$ (a scalar value):

• Compute the public key $Q_A = d_A \cdot G$
• Compute hash of the data/message to be signed $ e = hash(m)$
• Compute the first part of the signature, ephemeral key pair $(k,R)$:
  • Generate a random nonce k such that $0 < k < n$
  • Calculate point $$ R = k \cdot G = \binom{r_x}{r_y} $$
  • Generate $r = r_x \pmod n$, where $ r \not = 0 $
• Generate the rest of the signature: $$ s = \frac{e+d_A \cdot r}{k} \pmod n = k^{-1}\cdot(e+d_A \cdot r) \pmod n $$
• Publish the signature $\textbf{(r,s)}$ together with the public key $Q_A$

ECDSA - Signature verification

Given a curve $(p,a,b,G,n)$, a public key $Q_A$ together with a signature $(r,s)$. The signature $(r,s)$ over $ m $ is valid iff:

• The signature values are plausible, i.e., $0 < r < n$ and $0 < s < n$
• (Re-)compute the hash of the data/message $e = hash(m)$
• Invert $s$ modulo $n$, i.e., $w = s^{-1} \pmod n$
  • Since $n$ is known and especially since $n \in \textrm{Primes}$, finding the multiplicate inverse $s^{-1}$ can be done in poly. time
  • Note: $s^{-1}$ can also be written as $1/s$
• Calculate $u_1 = e\cdot w \pmod n$, and $u_2 = r\cdot w \pmod n$
• Derive point $P$: $$ P = \binom{p_x}{p_y} = u_1\cdot G + u_2 \cdot Q_A $$
• If $p_x = r \pmod n $, the signature is valid

ECDSA - Signature verification

Given a curve $(p,a,b,G,n)$, a public key $Q_A$ together with a signature $(r,s)$. The signature checking algorithm for $(r,s)$ over $m$ is correct because: $$ \begin{align*} P &= u_1 \cdot G + u_2 \cdot Q_A \\ u_1 &= e \cdot w \text{ and } \\ u_2 &= r \cdot w \\ P &= e \cdot w \cdot G + r \cdot w \cdot Q_A \\ P &= e \cdot w \cdot G + r \cdot w \cdot d_A \cdot G \\ P &= (e \cdot w + r \cdot w \cdot d_A) \cdot G \\ P &= w \cdot (e + r \cdot d_A) \cdot G \\ w &= s^{-1} = \left(\frac{e+d_A\cdot r}{k}\right)^{-1} = (({e + d_A \cdot r})\cdot k^{-1})^{-1} \pmod n \\ P &= (({e + d_A \cdot r})\cdot k^{-1})^{-1} \cdot (e + d_A \cdot r) \cdot G \\ P &= ({e + d_A \cdot r})^{-1} \cdot (k^{-1})^{-1} \cdot (e + d_A \cdot r) \cdot G = k \cdot G % alternative notation: %w &= s^{-1} = \left(\frac{e+d_A\cdot r}{k}\right)^{-1} = \frac{k}{e + d_A \cdot r} \pmod n \\ %P &= \frac{k}{e + d_A \cdot r}\cdot (e + d_A \cdot r) \cdot G = k \cdot G \end{align*} $$

ECDSA - Nonce reuse

Do not reuse nonces in ECDSA!

• n-on-ce = number only use once
• Either derive from secure RNG or deterministically
  • http://tools.ietf.org/html/rfc6979
  • In EdDSA deterministic nonces are the default

ECDSA - Nonce reuse

Example: Sony PS3 ECDSA nonce reuse vulnerability

• PS3 used code signing to only allow code from trusted sources to be executed
• Nonce was reused
• Secret key was recovered
• After fail0verflow presented the attack at 27c3 George Hotz (geohot) released the private key of the PS3 together with a "Hello world program" for the PS3
• Lawsuits followed
• Now the case is settled

PS3 code signing private key encoded as image (image source)

ECDSA - Nonce reuse

Example: Bitcoin online web wallet Counterwallet.io (2014)

• Used the same nonce for multiple signatures
• Multiple users transferred coins with the same $ r $ value [1,2].

(image source)

ECDSA - Nonce reuse

Given a curve $(p,a,b,G,n)$, a public key $Q_A$ together with:

• a signature $(r,s_1)$ and a message $m_1$
• a signature $(r,s_2)$ and a message $m_2$

It can be observed that both signatures used the same value $r$ and hence the same random value $k$. This can be used to reconstruct the private key $d_A$

ECDSA - Nonce reuse

The only unknown variables in the this two equations $(1)$ and $(2)$ are $k$ and $d_A$. To solve for $d_A$ first rearrange the equations to $(3)$ and $(4)$ and replace $k$ in $(5)$.

$$ \begin{align} s_1 &= \frac{e_1+d_A \cdot r}{k} \pmod n \\ s_2 &= \frac{e_2+d_A \cdot r}{k} \pmod n \\ k &= \frac{e_1+d_A \cdot r}{s_1} \pmod n \\ k &= \frac{e_2+d_A \cdot r}{s_2} \pmod n \\ \frac{e_1+d_A \cdot r}{s_1} &= \frac{e_2+d_A \cdot r}{s_2} \pmod n \end{align} $$

Then solve for $d_A$: $$ \begin{align*} \frac{e_1+d_A \cdot r}{s_1} &= \frac{e_2+d_A \cdot r}{s_2} &\pmod n \\ s_2 \cdot (e_1+d_A \cdot r) &= s_1 \cdot (e_2+d_A \cdot r) &\pmod n \\ s_2 \cdot e_1 + s_2 \cdot d_A \cdot r &= s_1 \cdot e_2 + s_1 \cdot d_A \cdot r &\pmod n \\ s_2 \cdot e_1 - s_1 \cdot e_2 &= s_1 \cdot d_A \cdot r - s_2 \cdot d_A \cdot r &\pmod n \\ s_2 \cdot e_1 - s_1 \cdot e_2 &= d_A \cdot r \cdot ( s_1 - s_2 ) &\pmod n \\ \frac{s_2 \cdot e_1 - s_1 \cdot e_2}{r \cdot ( s_1 - s_2 )} &= d_A &\pmod n \\ \end{align*} $$

ECDSA - Example usage with secp256k1

The following is an example of ECDSA using curve secp256k1.

def ecdsa_hashtoint(msg):	
  return Integer('0x' + hashlib.sha256(msg.encode()).hexdigest())

message_hash = ecdsa_hashtoint("some string"); hex(message_hash)

'0x61d034473102d7dac305902770471fd50f4c5b26f6831a56dd90b5184b3c30fc'

def ecdsa_keygen(verbose=False):
  d = randint(1, n - 1)
  Q = d * G
  return (Q, d)

(Q_A,d_A) = ecdsa_keygen(verbose=True) # generate keypair 

d   = 0x96a01521e7b28bff0f6e062294c44d192e4d47c216bf105ef3ba47cd40f254a4
Q_x = 0x20aa48b4f7834f26c96d051a841a9e29c8df6d2e479f8c51c142dbb0a1b7ad4e
Q_y = 0x39eaa8214e17938f717d2ea951e85cd01d77067c10ebc1e8dd59c377e2383450

def ecdsa_sign(d, m, nonce=None):
  r = 0; s = 0
  while s == 0:
    while r == 0:
      if nonce:
        k = nonce # for simulating nonce reuse attack!
      else:
        k = randint(1, n - 1)
      R = k * G
      (x1, y1) = R.xy()
      r = Fn(x1)
    e = Fn(m) # assume hashed message
    s = Fn(k) ^ (-1) * (Fn(e) + Fn(d) * Fn(r))
  return (r, s)

(r,s) = ecdsa_sign(d_A,message_hash,verbose=True)

k   = 0x4dfe7bad1b120d36f547002d61086657dc92b8797dbff19d1dc70e1f83c64586
G_x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
G_y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
e   = 0x61d034473102d7dac305902770471fd50f4c5b26f6831a56dd90b5184b3c30fc
r   = 0x2f637666a8cbd30b3b0d6c66947c83e160df432ab98434aad4e4fee9d166344a
s   = 0x5339e3d0ca1a114e7304e115366adc50f24168327a6e27d4c68293f2c5e6071

def ecdsa_verify(Q, m, r, s, verbose=False):
  e = Fn(m) # assume hashed message
  w = Fn(s) ^ (-1)
  u1 = (e * w)
  u2 = (r * w)
  P1 = Integer(u1) * G
  P2 = Integer(u2) * Q
  P = P1 + P2
  (x, y) = P.xy()
  p_x = Fn(x)
  return p_x == r

assert True == ecdsa_verify(Q_A, message_hash, r, s, verbose=True)

w   = 0xfddc1b7d2aaae3eae2182e1fd3dd407b2c33ce56816729ab20e3b4a20d37282d
e   = 0x61d034473102d7dac305902770471fd50f4c5b26f6831a56dd90b5184b3c30fc
u1  = 0x57426b9a4d7cc965ec4184301143a2926f6592fdaf9c017b11371de821486f11
u2  = 0xe8e2e9db6337b1ced787b21055e83b0420eb1791cb7f5ab26ca6c7105050fa5d
r   = 0x2f637666a8cbd30b3b0d6c66947c83e160df432ab98434aad4e4fee9d166344a
p_x = 0x2f637666a8cbd30b3b0d6c66947c83e160df432ab98434aad4e4fee9d166344a

message_hash = ecdsa_hashtoint("other message")
assert False == ecdsa_verify(Q_A, message_hash, r, s, verbose=False)

ECDSA - Nonce reuse using secp256k1

e1 = ecdsa_hashtoint("some string")
same_nonce = 18028843120798948533673493337980837983774482433016311482792706326465477485859
(r1,s1) = ecdsa_sign(d_A, e1, nonce=same_nonce,verbose=False)
print(f"r1 = {hex(r1)}\ns1 = {hex(s1)}")

r1 = 0x8362f4339944b91019606dd91522abc23d653a28cc899437f5109a1d1ceb4641
s1 = 0xfe104e0eb83c9397798e7fefe813b40e551dfa1cbbfd62aa885209341a81cda4

e2 = ecdsa_hashtoint("some other string")
same_nonce = 18028843120798948533673493337980837983774482433016311482792706326465477485859
(r2,s2) = ecdsa_sign(d_A, e2, nonce=same_nonce,verbose=False)
print(f"r2 = {hex(r2)}\ns2 = {hex(s2)}")

r2 = 0x8362f4339944b91019606dd91522abc23d653a28cc899437f5109a1d1ceb4641
s2 = 0x6ac10906fcf21c74104ac4dafde0c312f740eb92703ce466dafe224e05b06efc

assert r1 == r2

ECDSA nonce reuse calculation: $$ \frac{s_2 \cdot e_1 - s_1 \cdot e_2}{r \cdot ( s_1 - s_2 )} = d_A $$

d_recovered = (s2 * e1 - s1 * e2)/(r1 * (s1 - s2))

d_A

68129768668606611660207536433936544511679163492021451989854272372038847059108

d_recovered

68129768668606611660207536433936544511679163492021451989854272372038847059108

assert d_A == d_recovered

Optimizations in ECC

---

Optimizations in ECC

Different representations of curve points, or optimized elliptic curves and parameters can lead to significant performance gains. For example, reduce the size to represent points on the curve (point compression), or speed up the computations required for ECC (e.g., projective coordinates and special curves). In the following we will take a look at some of these optimization techniques.

Affine and Projective Coordinates

There are alternative ways to represent points on elliptic curves using projective coordinates.

• When a point on an elliptic curve is described by a pair of elements $(x,y)$ this is called affine coordinates

• When a point is represented by three alements (from $\mathbb{Z}_p$) then it is given in projective coordinates $(X,Y,Z) \in \mathbb{Z}_p$

Projective coordinates

A point is given by $(X,Y,Z) \in \mathbb{Z}_p$, where

• $X/Z = x \pmod p$
• $Y/Z = y \pmod p$
• The point at infinity $\mathcal{O}$ is given by $(0,Y,0)$ where $Y \neq 0 $ and this is the only point where $Z=0$
• To translate between affine and projective any point $(x,y) \neq \mathcal{O}$ becomes $(x,y,1)$ in projective coordinates and $(X,Y,Z)$ where $Z\neq0$ in projective coordinates can be mapped to $(X/Z \pmod p, Y/Z \pmod p)$ in affine coordinates.

Projective coordinates addition

One advantage of using projective coordinates is that adding two points can now be done without computing inverses modulo $p$ which is the most expensive operation [ITMC] $$ \begin{align} P_3 &= P_1 + P_2 \\ (X_3,Y_3,Z_3) &= (X_1,Y_1,Z_1) + (X_2,Y_2,Z_2) \\ u &= Y_2 Z_1 - Y_1 Z_2 \\ v &= X_2 Z_1 - X_1 Z_2 \\ w &= u^2 Z_1 Z_2 - v^3 - 2v^2 X_1 Z_2 \\ (X_3,Y_3,Z_3) &= (vw, u(v^2 X_1 Z_2 - w) - v^3 Y_1 Z_2, Z_1 Z_2 v^3 ) \end{align} $$

p = 31
FF = FiniteField(p)
EC = EllipticCurve(FF, [0,0,0,-1,1]); EC # a=-1 b=1
P1 = EC.random_element(); 
P2 = EC.random_element();
P1,P2

((16 : 19 : 1), (28 : 15 : 1))

def add_projective(P1, P2, p):
    X1,Y1,Z1 = P1
    X2,Y2,Z2 = P2
    u = Y2 * Z1 - Y1 * Z2 % p
    v = X2 * Z1 - X1 * Z2 % p
    w = u**2 * Z1 * Z2 - v**3 - 2*v**2 * X1 * Z2 
    X3 = v*w 
    Y3 = u * (v**2 * X1 * Z2 - w) - v**3 * Y1 * Z2 
    Z3 = Z1 * Z2 * v**3 
    return ( X3/Z3,Y3/Z3,1 ) # translate to affine and return

P3_proj = add_projective(P1, P2, p); P3_proj

(25, 15, 1)

P3 = P1 + P2; P3

(25 : 15 : 1)

assert P3.xy() == (P3_proj[0],P3_proj[1])

Montgomery representation

The montgomery representation involves elliptic curve equations ($E$) of the following form: $$ By^2 = x^3 + Ax^2 + x \pmod p $$ Here $B\neq 0 \pmod p$ and $ A \neq \pm 2 \pmod p $. Given this elliptic curve equation, we again denote $E(\mathbb{Z}_p)$ the set of points with coordinates $x,y \in \mathbb{Z}_p$ satisfying the equation $E$, together with a point at infinity $\mathcal{O}$.

Not every curve can be expressed in Montgomery representation (the order of any elliptic curve group written in Montgomery form is a multiple of $ 4 $ [ITMC]).

Montgomery curves over $\mathbb{R}$

The following figure shows the Montgomery curve $By^2 = x^3 + Ax^2 + x$ for $A=1/4$ and $B=5/2$ over $\mathbb{R}$.

import numpy as np
import matplotlib.pyplot as plt

B = 5/2
A = 1/4
def equation(x, y):
    # x**3 + B*x**2 + x - A*y**2 == 0
    return x**3 + B*x**2 + x - A*y**2

# Create a grid of x and y values
x = np.linspace(-2.5, 1.5, 500)
y = np.linspace(-3.5, 3.5, 500)
X, Y = np.meshgrid(x, y)

# Calculate Z values based on the equation
Z = equation(X, Y)

# Plot the contour where Z = 0
plt.figure(figsize=(8, 8))
plt.contour(X, Y, Z, levels=[0], colors='blue')
plt.title(rf"${B}y^2 = x^3 + {A}x^2 + x$")
plt.xlabel("x")
plt.ylabel("y")
plt.grid()
plt.axhline(0, color='black', linewidth=0.5)
plt.axvline(0, color='black', linewidth=0.5)
if SAVE_FIGURES: plt.savefig("./figures/ecc_montgomery_over_R.png",format="png", dpi=300)
#plt.show()

Example: Curve25519

The following is the Montgomery curve used for Curve25519, specified in RFC 7748 over $\mathbb{F}_p $ where $ p = 2^{255} - 19$. $$ y^2 = x^3 + 486662 x^2 + x \pmod p $$ This curve is birationally equivalent to a twisted Edwards curve $ -x^2 + y^2 = 1 + dx^2y^2 $, called edwards25519, where $ d = 37095705934669439343138083508754565189542113879843219016388785533085940283555 $

B=1; A=486662
Curve25519 = EllipticCurve(GF(2^255-19),[0,A,0,B,0]) 
Curve25519

Elliptic Curve defined by y^2 = x^3 + 486662*x^2 + x over Finite Field of size 57896044618658097711785492504343953926634992332820282019728792003956564819949

Curve25519.trace_of_frobenius()

-221938542218978828286815502327069187962

Example: Curve25519 over $\mathbb{R}$

This is how the montgomery curve25519 looks over the real numbers $\mathbb{R}$

EC = EllipticCurve(RR,[0,A,0,B,0]) # Montgomery curve used for Curve25519
p = plot(EC,thickness=3) #p = plot(EC,thickness=3,xmin=-500000,xmax=2,ymin=-2,ymax=2)
if SAVE_FIGURES: p.save("./figures/ecc_curve25519_over_R.png")
#p.show()

Twisted Edwards representation

The twisted Edwards representation involves elliptic curve equations ($E$) of the following form: $$ ax^2 + y^2 = 1 + dx^2y^2 \pmod p $$ Here $a,d \neq 0 \pmod p$ and $ a ¸\neq d \pmod p$. The special case where $ a = 1 $ is called the Edwards representation (without the "twist" $ a $). Given this elliptic curve equation, we again denote $E(\mathbb{Z}_p)$ the set of points with coordinates $x,y \in \mathbb{Z}_p$ satisfying the equation $E$, but this representation does not require a special point at infinity since the point $(0,1)$ on the curve is the identity element.

The twisted Edwards representation can express the same set of elliptic curves as the Montgomery representation [ITMC]).

Twisted Edwards curves over $\mathbb{R}$

The following figure shows the Twisted Edwards curve $a\cdot x^2 + y^2 = 1 + d\cdot x^2y^2$ where $ a = 10$ and $d=6$ over $\mathbb{R}$.

import numpy as np
import matplotlib.pyplot as plt

a = 10
d = 6
def equation(x, y):
    # a * x**2 + y**2 - 1 - d * x**2 * y**2 == 0
    return a * x**2 + y**2 - 1 - d * x**2 * y**2

# Create a grid of x and y values
x = np.linspace(-2.5, 2.5, 500)
y = np.linspace(-2.5, 2.5, 500)
X, Y = np.meshgrid(x, y)

# Calculate Z values based on the equation
Z = equation(X, Y)

# Plot the contour where Z = 0
plt.figure(figsize=(8, 8))
plt.contour(X, Y, Z, levels=[0], colors='blue')
plt.title(rf"${a}\cdot x^2 + y^2 = 1 + {d}\cdot x^2y^2$")
plt.xlabel("x")
plt.ylabel("y")
plt.grid()
plt.axhline(0, color='black', linewidth=0.5)
plt.axvline(0, color='black', linewidth=0.5)
if SAVE_FIGURES: plt.savefig("./figures/ecc_twisted_edwards_over_R.png",format="png", dpi=300)
#plt.show()

Example: Ed25519/Edwards25519

Specified in EdDSA RFC 8032 (used by age) and also allowed by NIST FIPS 186-5 as Edwards25519.

$$ -x^2 + y^2 = 1 + dx^2 + y^2 \pmod p $$

p = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
FFp = GF(p)

d = FFp(0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca135978a3)
a = FFp(0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec)

Since sage does not directly support TwistedEdwards curves, the curve has to be converted (cf.)

# This curve is a Weierstrass curve (SAGE does not support TwistedEdwards curves) birationally equivalent to the intended curve.
# You can use the to_weierstrass and to_twistededwards functions to convert the points.
EC = EllipticCurve(FFp, (FFp(-1/48) * (a^2 + 14*a*d + d^2), FFp(1/864) * (a + d) * (-a^2 + 34*a*d - d^2)))

def to_weierstrass(a, d, x, y):
	return ((5*a + a*y - 5*d*y - d)/(12 - 12*y), (a + a*y - d*y -d)/(4*x - 4*x*y))

def to_twistededwards(a, d, u, v):
	y = (5*a - 12*u - d)/(-12*u - a + 5*d)
	x = (a + a*y - d*y -d)/(4*v - 4*v*y)
	return (x, y)
    
G = EC(*to_weierstrass(a, d, FFp(0x216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A), FFp(0x6666666666666666666666666666666666666666666666666666666666666658)))
EC.set_order(0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed * 0x08)

assert EC.trace_of_frobenius() == -221938542218978828286815502327069187962

ECC standards

There are multiple standards which standardized elliptic curves with their paramters to be used for ECC, e.g.,

• NIST [FIPS 186-5] (last update 2023)
• SEC 2 [SEC2v2] (last update 2010)
• Brainpool [RFC 5639] (last update 2010)
• ...

A good (but old) overview of standards and for choosing the right curves for ECC can be found on SafeCurves.

• Hyperelliptic calculation code snippets and implementation help

NIST curves

NIST standardized different elliptic curves (Edwards, Weierstrass, Montgomery, and Koblitz curves). In its current version the recommended curves are defined over prime fields, i.e., $\mathbb{F}_p$ also written as $\mathrm{GF}(p)$ [FIPS 186-5], [SP 800-186].

• With Feb. 2023 curves over binary fields ($\mathbb{F}_{2^m}$) have been depricated

  Due to their limited adoption, elliptic curves over binary fields are deprecated

• With Feb. 2023 Montgomery curve Curve25519 (for ECDH) as well as twisted Edwards curve Edwards25519 (for EdDSA) are included in [FIPS 186-5]. [cf. RFC 7748, RFC 8032]
  • The differences between NIST and IETF specifications have been analyzed here [Taming the many EdDSAs,The Provable Security of Ed25519: Theory and Practice] and test vectors are available here.

EOF