2.2 Elliptic curves over prime fields

Elliptic curves over prime fields form the foundation of modern cryptography. These smooth algebraic curves, defined by cubic equations, create finite abelian groups that enable secure and efficient computations. Their unique properties make them ideal for encryption, digital signatures, and key exchange protocols.

The Weierstrass equation y^2 = x^3 + ax + b defines elliptic curves over prime fields. Points on these curves form a group under addition, with the point at infinity as the identity element. This group structure, combined with the hardness of the discrete logarithm problem, underpins elliptic curve cryptography's strength.

Definition of elliptic curves

• Elliptic curves are smooth, projective, algebraic curves of genus one, which means they have no cusps or self-intersections
• They are defined by a cubic equation in two variables, often referred to as the Weierstrass equation
• Elliptic curves have a rich algebraic structure, forming an abelian group under a geometric addition operation

Weierstrass equation

Top images from around the web for Weierstrass equation

• 

  Elliptic curve cryptography (in Technology > Encryption @ iusmentis.com) View original

  Is this image relevant?

• 

  The Math Behind Elliptic Curves in Weierstrass Form - Sefik Ilkin Serengil View original

  Is this image relevant?

• 

  Elliptic curve primality - Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  Elliptic curve cryptography (in Technology > Encryption @ iusmentis.com) View original

  Is this image relevant?

• 

  The Math Behind Elliptic Curves in Weierstrass Form - Sefik Ilkin Serengil View original

  Is this image relevant?

1 of 3

Top images from around the web for Weierstrass equation

• 

  Elliptic curve cryptography (in Technology > Encryption @ iusmentis.com) View original

  Is this image relevant?

• 

  The Math Behind Elliptic Curves in Weierstrass Form - Sefik Ilkin Serengil View original

  Is this image relevant?

• 

  Elliptic curve primality - Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  Elliptic curve cryptography (in Technology > Encryption @ iusmentis.com) View original

  Is this image relevant?

• 

  The Math Behind Elliptic Curves in Weierstrass Form - Sefik Ilkin Serengil View original

  Is this image relevant?

1 of 3

• The Weierstrass equation for an elliptic curve over a field $K$ is given by $y^2 = x^3 + ax + b$, where $a, b \in K$ and the discriminant $\Delta = 4a^3 + 27b^2 \neq 0$
• The coefficients $a$ and $b$ determine the shape and properties of the elliptic curve
• The Weierstrass equation can be transformed into other forms, such as the Montgomery or Edwards form, which may have computational advantages

Elliptic curves vs elliptic functions

• Elliptic curves are not the same as elliptic functions, despite the similar name
• Elliptic functions are doubly periodic meromorphic functions on the complex plane, while elliptic curves are algebraic curves defined by a cubic equation
• The name "elliptic" comes from the historical connection between elliptic functions and the arc length of ellipses

Discriminant and singularities

• The discriminant $\Delta = 4a^3 + 27b^2$ of an elliptic curve $y^2 = x^3 + ax + b$ determines whether the curve is smooth or singular
• If $\Delta \neq 0$, the curve is smooth and has no cusps or self-intersections
• If $\Delta = 0$, the curve is singular and has a node (self-intersection) or a cusp, depending on the multiplicity of the roots of the cubic equation

Affine vs projective coordinates

• Elliptic curves can be represented using affine coordinates $(x, y)$ or projective coordinates $(X : Y : Z)$
• Affine coordinates are the standard Cartesian coordinates on the plane, while projective coordinates introduce a third variable $Z$ to represent points at infinity
• Projective coordinates are often used in elliptic curve arithmetic to avoid special cases and improve efficiency by eliminating the need for field inversions

Elliptic curves over prime fields

• Elliptic curves over prime fields are a fundamental building block for elliptic curve cryptography and other applications
• Prime fields provide a finite set of elements with a well-defined arithmetic structure, which is essential for secure and efficient computations

Prime fields and finite fields

• A prime field $\mathbb{F}_p$ is a finite field with $p$ elements, where $p$ is a prime number
• Elements of a prime field are represented by integers modulo $p$, with addition and multiplication performed modulo $p$
• Finite fields, also known as Galois fields, are fields with a finite number of elements and include prime fields as a special case

Elliptic curve equations over prime fields

• An elliptic curve over a prime field $\mathbb{F}_p$ is defined by the Weierstrass equation $y^2 \equiv x^3 + ax + b \pmod{p}$, where $a, b \in \mathbb{F}_p$ and $4a^3 + 27b^2 \not\equiv 0 \pmod{p}$
• The coefficients $a$ and $b$ are chosen to ensure that the curve is smooth and has no singularities over the prime field
• Elliptic curves over prime fields have a finite number of points, which form a group under the addition operation

Point representation and uniqueness

• Points on an elliptic curve over a prime field are represented by pairs $(x, y)$, where $x, y \in \mathbb{F}_p$ satisfy the curve equation
• Each $x$-coordinate corresponds to at most two $y$-coordinates, which are negatives of each other modulo $p$
• The point at infinity, denoted by $\mathcal{O}$, is a special point that serves as the identity element for the group of points on the curve

Point at infinity

• The point at infinity $\mathcal{O}$ is a unique point that does not have a finite $x$ or $y$ coordinate
• It is the neutral element for the group of points on the elliptic curve, meaning that $P + \mathcal{O} = P$ for any point $P$ on the curve
• In projective coordinates, the point at infinity is represented as $(0 : 1 : 0)$, while in affine coordinates, it is often treated as a special case

Group law for elliptic curves

• The set of points on an elliptic curve, together with the point at infinity, forms an abelian group under a geometric addition operation
• The group law defines how to add two points on the curve to obtain a third point, also on the curve
• The group structure of elliptic curves is the foundation for their use in cryptography and other applications

Geometric definition of addition

• The addition of two points $P$ and $Q$ on an elliptic curve is defined geometrically by the following steps:
  1. Draw a line through $P$ and $Q$ (if $P = Q$, draw the tangent line at $P$)
  2. The line intersects the curve at a third point $R'$
  3. Reflect $R'$ across the $x$-axis to obtain the sum $R = P + Q$
• If the line through $P$ and $Q$ is vertical, the sum is defined as the point at infinity $\mathcal{O}$

Algebraic formulas for addition

• The geometric definition of addition can be translated into algebraic formulas for the coordinates of the sum point $R = (x_r, y_r)$
• For two distinct points $P = (x_p, y_p)$ and $Q = (x_q, y_q)$, the sum $R = P + Q$ is given by:
  • $x_r = \lambda^2 - x_p - x_q$
  • $y_r = \lambda(x_p - x_r) - y_p$
  • where $\lambda = \frac{y_q - y_p}{x_q - x_p}$
• For doubling a point $P = (x_p, y_p)$, the sum $R = 2P$ is given by:
  • $x_r = \lambda^2 - 2x_p$
  • $y_r = \lambda(x_p - x_r) - y_p$
  • where $\lambda = \frac{3x_p^2 + a}{2y_p}$

Associativity and commutativity

• The addition operation on elliptic curves is associative, meaning that $(P + Q) + R = P + (Q + R)$ for any points $P$, $Q$, and $R$ on the curve
• Addition is also commutative, so $P + Q = Q + P$ for any points $P$ and $Q$
• These properties are essential for the group structure of elliptic curves and their use in cryptographic protocols

Identity element and inverses

• The point at infinity $\mathcal{O}$ serves as the identity element for the group of points on an elliptic curve, so $P + \mathcal{O} = P$ for any point $P$
• Every point $P = (x, y)$ on the curve has an inverse $-P = (x, -y)$, which satisfies $P + (-P) = \mathcal{O}$
• The inverse of the point at infinity is itself, i.e., $-\mathcal{O} = \mathcal{O}$

Graphical examples of addition

• Consider the elliptic curve $y^2 = x^3 - x$ over the real numbers. To add the points $P = (0, 0)$ and $Q = (1, 0)$:
  1. Draw a line through $P$ and $Q$, which is the $x$-axis
  2. The line intersects the curve at the point $R' = (-1, 0)$
  3. Reflect $R'$ across the $x$-axis to obtain the sum $R = P + Q = (-1, 0)$
• To double the point $P = (0, 0)$:
  1. Draw the tangent line to the curve at $P$, which is the $y$-axis
  2. The tangent line intersects the curve at the point at infinity $\mathcal{O}$
  3. Therefore, $2P = P + P = \mathcal{O}$

Elliptic curve arithmetic

• Elliptic curve arithmetic involves computing scalar multiples of points on the curve, which is the foundation for elliptic curve cryptography
• Efficient computation techniques are essential for practical implementations of elliptic curve algorithms

Scalar multiplication and repeated addition

• Scalar multiplication is the operation of adding a point $P$ on an elliptic curve to itself $k$ times, denoted as $kP = P + P + \cdots + P$ ($k$ times)
• Scalar multiplication can be computed using repeated addition, but this is inefficient for large values of $k$
• More efficient methods, such as the double-and-add algorithm or window-based methods, are used in practice

Efficient computation techniques

• The double-and-add algorithm for scalar multiplication works by expressing $k$ in binary and iteratively doubling and adding points:
  • For each bit of $k$ (from most to least significant):
    • Double the current point
    • If the current bit is 1, add $P$ to the current point
• Window-based methods, such as the sliding window or w-NAF method, precompute multiples of $P$ and use them to reduce the number of additions required
• Other techniques, such as projective coordinates, Jacobian coordinates, or Montgomery ladders, can be used to improve efficiency by reducing the number of field inversions or providing resistance against side-channel attacks

Doubling vs addition formulas

• Point doubling (computing $2P$) and point addition (computing $P + Q$) have different algebraic formulas and costs
• Doubling formulas are typically more efficient than addition formulas, as they require fewer field operations
• For example, in affine coordinates, point doubling requires 1 field inversion and 4 field multiplications, while point addition requires 1 field inversion and 3 field multiplications
• Using projective or Jacobian coordinates can eliminate the need for field inversions, which are often the most expensive operations

Finite cyclic subgroups

• The group of points on an elliptic curve over a finite field is a finite abelian group, which means it can be decomposed into a product of cyclic subgroups
• A cyclic subgroup is a subgroup generated by a single element, i.e., all elements in the subgroup are scalar multiples of a generator point
• The order of a cyclic subgroup is the number of elements in the subgroup, which is also the order of its generator point
• Lagrange's theorem states that the order of a subgroup divides the order of the group, so the order of any point on the curve divides the total number of points on the curve

Torsion points and orders

• A torsion point on an elliptic curve is a point of finite order, i.e., a point $P$ for which there exists an integer $k$ such that $kP = \mathcal{O}$
• The order of a torsion point is the smallest positive integer $k$ satisfying $kP = \mathcal{O}$
• The set of all torsion points on an elliptic curve forms a subgroup called the torsion subgroup
• For elliptic curves over prime fields, the torsion subgroup is either cyclic or the product of two cyclic subgroups
• The possible torsion subgroup structures for elliptic curves over prime fields are: $\mathbb{Z}_n$ for $n = 1, 2, \ldots, 10, 12$, or $\mathbb{Z}_2 \times \mathbb{Z}_{2n}$ for $n = 1, 2, 3, 4$

Elliptic curve discrete logarithm problem

• The security of elliptic curve cryptography relies on the difficulty of solving the elliptic curve discrete logarithm problem (ECDLP)
• The ECDLP is the problem of finding an integer $k$ given points $P$ and $Q$ on an elliptic curve such that $Q = kP$
• The hardness of the ECDLP is essential for the security of elliptic curve-based cryptographic protocols

Hardness assumption and security

• The hardness of the ECDLP is assumed to be exponential in the size of the underlying field, meaning that the best known algorithms for solving the ECDLP have a running time that is exponential in the number of bits required to represent field elements
• This is in contrast to the integer factorization problem and the discrete logarithm problem in finite fields, which have subexponential-time algorithms (e.g., the number field sieve)
• As a result, elliptic curve cryptography can achieve the same level of security as RSA or finite field-based systems with much smaller key sizes

Comparison to integer factorization

• The security of RSA, the most widely used public-key cryptosystem, relies on the difficulty of factoring large integers
• While the best known algorithms for integer factorization, such as the number field sieve, have a subexponential running time, they are still much faster than the best known algorithms for solving the ECDLP
• This means that elliptic curve cryptography can use significantly smaller key sizes than RSA while maintaining the same level of security
• For example, a 256-bit elliptic curve key provides a similar level of security as a 3072-bit RSA key

Pollard's rho algorithm for ECDLP

• Pollard's rho algorithm is a probabilistic algorithm for solving the ECDLP that has an expected running time of $O(\sqrt{n})$, where $n$ is the order of the cyclic subgroup generated by the base point
• The algorithm works by generating a pseudorandom sequence of points on the elliptic curve and looking for a collision in the sequence
• When a collision is found, the ECDLP can be solved with high probability by solving a linear equation in the exponents
• Pollard's rho algorithm is the most efficient general-purpose algorithm for solving the ECDLP, but it is still exponential in the size of the underlying field

Attacks and security considerations

• The security of elliptic curve cryptography can be compromised if the elliptic curve parameters are not chosen carefully
• Some classes of elliptic curves, such as supersingular curves or curves with small embedding degrees, are vulnerable to specific attacks and should be avoided
• Side-channel attacks, which exploit information leaked during the execution of elliptic curve algorithms (e.g., timing or power consumption), can also pose a threat to the security of elliptic curve cryptosystems
• To mitigate these risks, it is important to use standardized, well-studied elliptic curves and to implement side-channel countermeasures, such as constant-time algorithms or randomized projective coordinates

Applications of elliptic curves over prime fields

• Elliptic curves over prime fields have numerous applications in cryptography and secure communication protocols
• The security and efficiency of elliptic curve-based systems make them an attractive choice for resource-constrained environments, such as mobile devices or embedded systems

Elliptic curve cryptography

• Elliptic curve cryptography (ECC) is a public-key cryptography approach that uses the algebraic structure of elliptic curves over finite fields
• ECC can be used for encryption, digital signatures, and key exchange protocols
• Some common elliptic curve-based cryptographic algorithms include the Elliptic Curve Digital Signature Algorithm (ECDSA), the Elliptic Curve Integrated Encryption Scheme (ECIES), and the Elliptic Curve Diffie-Hellman (ECDH) key exchange protocol

Digital signature algorithms

• The Elliptic Curve Digital Signature Algorithm (ECDSA) is a widely used digital signature scheme based on elliptic curves
• ECDSA is the elliptic curve analogue of the Digital Signature Algorithm (DSA) and is used in numerous cryptographic protocols, such as Transport Layer Security (TLS) and Bitcoin
• The security of ECDSA relies on the difficulty of solving the ECDLP, and it offers smaller signature sizes compared to RSA or DSA for the same level of security

Diffie-Hellman key exchange

• The Elliptic Curve Diffie-Hellman (ECDH) key exchange protocol is an adaptation of the classic Diffie-Hellman protocol that uses elliptic curve arithmetic
• In ECDH, two parties agree on a common elliptic curve and a base point $P$. Each party generates a private key $k$ and comp