Fact-checked by Grok 2 weeks ago

Elliptic curve point multiplication

Elliptic curve point multiplication, also known as scalar multiplication, is a fundamental operation in elliptic curve cryptography (ECC) that computes the result of adding a point P on an elliptic curve to itself k times, denoted as kP, where k is an integer scalar, using the curve's group law.^[1]^[2] This operation leverages the algebraic structure of elliptic curves defined over finite fields, typically via the Weierstrass equation y^2 = x^3 + ax + b (mod p) for prime fields, ensuring the curve is non-singular with discriminant $4a^3 + 27b^2 \neq 0.^[1]^[3] The group law on an elliptic curve enables point addition: for distinct points P = (x_1, y_1) and Q = (x_2, y_2), the sum R = P + Q is found by drawing the line through P and Q, finding its third intersection with the curve at -R, and reflecting over the x-axis to get R.^[2] Doubling a point P uses the tangent line at P. Scalar multiplication builds on these via efficient algorithms like the double-and-add method, which processes the binary representation of k to perform roughly $1.5 \log_2 k additions and doublings on average, making it computationally feasible while the inverse problem—solving for k given P and kP (the elliptic curve discrete logarithm problem)—is intractable for large curves.^[2]^[3] In cryptographic applications, such as the Elliptic Curve Digital Signature Algorithm (ECDSA) standardized in FIPS 186-5, scalar multiplication generates public keys as Q = dG (where d is the private key and G is the base point) and verifies signatures by computing multiples like u_1 G + u_2 Q.^[3] Recommended curves like NIST P-256 provide 128 bits of security with 256-bit keys, offering efficiency advantages over RSA by requiring smaller parameters for equivalent strength.^[3] Implementations must resist side-channel attacks, such as timing or power analysis, often using constant-time methods or coordinate systems like Jacobian to avoid costly inversions.

Introduction

Definition and notation

In elliptic curve cryptography, point multiplication, commonly referred to as scalar multiplication, is defined as follows: for an elliptic curve E and an integer k \geq 0, the product kP of a point P on E is the result of adding P to itself k times using the elliptic curve group operation.^[4] This operation forms the basis of the discrete logarithm problem in elliptic curve groups, which underpins the security of related cryptographic systems.^[5] Standard notation for this context includes E(\mathbb{F}_q) to denote the abelian group of rational points on the elliptic curve E over the finite field \mathbb{F}_q, where q is a prime power; a point P \in E(\mathbb{F}_q); and an integer scalar k \in \mathbb{Z}_{\geq 0}, with the scalar multiple denoted kP \in E(\mathbb{F}_q).^[6] For k = 0, the convention is $0P = \mathcal{O}, the point at infinity serving as the group identity.^[4] The use of elliptic curve point multiplication in cryptographic applications originated in the mid-1980s, with independent proposals by mathematicians Neal Koblitz and Victor S. Miller in 1985, who recognized its potential for efficient public-key protocols based on the elliptic curve discrete logarithm problem.^[5] As a conceptual example, consider a point P on an elliptic curve and scalar k = 3; then $3P = P + P + P, where each + represents the single point addition in the curve's group law, yielding another point on the same curve without requiring explicit computation of intermediate steps here.^[6]

Applications in cryptography

Elliptic curve point multiplication is the core primitive enabling several prominent cryptographic protocols within elliptic curve cryptography (ECC). In the elliptic curve Diffie-Hellman (ECDH) key agreement scheme, it allows parties to compute a shared secret by performing scalar multiplication of their private key with the peer's public key point, facilitating secure key exchange without direct transmission. The Elliptic Curve Digital Signature Algorithm (ECDSA) employs point multiplication to generate public keys from private scalars and to produce signatures on message hashes, verifying authenticity and non-repudiation. Similarly, the Elliptic Curve Integrated Encryption Scheme (ECIES) uses it to derive ephemeral shared secrets for symmetric encryption keys, ensuring data confidentiality in hybrid systems.^[7] ECC's efficiency advantages arise from its ability to achieve high security with compact keys, outperforming alternatives like RSA in computational and bandwidth demands. A 256-bit ECC key delivers roughly 128 bits of security strength, equivalent to a 3072-bit RSA key, which reduces processing time and storage needs—critical for deployment on embedded systems, mobile devices, and low-power networks.^[8] This scalability has driven ECC adoption in standards prioritizing performance without compromising protection. The robustness of these applications rests on the elliptic curve discrete logarithm problem (ECDLP), deemed computationally intractable: given a base point P and multiple Q = kP, recovering the scalar k remains infeasible for large, securely parameterized curves.^[9] NIST's FIPS 186-2, published in 2000, marked a pivotal milestone by standardizing ECDSA with elliptic curves, including recommended domain parameters.^[10] Curves like secp256r1, specified that same year, became foundational for interoperability.^[11] Today, point multiplication powers modern protocols such as TLS 1.3, ratified in 2018, where it supports mandatory elliptic curve groups like secp256r1 for ephemeral key exchanges, bolstering web security with forward secrecy.^[12] In blockchain technology, Bitcoin leverages ECDSA with point multiplication for transaction signatures since 2009, authenticating ownership and preventing double-spending on its distributed ledger.^[13]

Fundamentals

Elliptic curve equations

Elliptic curves used in point multiplication are typically defined by the Weierstrass equation over a field K:

y^2 = x^3 + ax + b,

where a, b \in K and the discriminant \Delta = -16(4a^3 + 27b^2) \neq 0 ensures the curve is nonsingular.^[14] This form, known as the short Weierstrass equation, is applicable when the characteristic of K is not 2 or 3, allowing for simplified arithmetic in point operations.^[14] In cryptographic applications, elliptic curves are primarily defined over finite fields, such as \mathbb{F}_p where p is a large prime or \mathbb{F}_{2^m} for binary fields, to enable efficient discrete logarithm computations.^[15] Over the real numbers \mathbb{R}, the equation provides geometric intuition, visualizing the curve as a smooth cubic with a bounded oval component and an unbounded branch.^[14] Curves over different fields are classified up to isomorphism by the j-invariant, given by

j = 1728 \frac{(4a)^3}{\Delta}.

This modular invariant determines whether two curves are isomorphic over an algebraic closure of K.^[14] For example, the curve E: y^2 = x^3 - 3x + 3 over \mathbb{R} illustrates the typical real topology, featuring a single connected component: an unbounded smooth curve symmetric about the x-axis when plotted, aiding in understanding the geometric structure before moving to finite fields.^[14]

Points on elliptic curves

The points on an elliptic curve E defined over a field K by the Weierstrass equation y^2 = x^3 + ax + b (with a, b \in K and discriminant nonzero) consist of all affine points (x, y) \in K^2 satisfying this equation.^[1] These points form the affine part of the curve, where each solution pair (x, y) represents a location in the plane over K. For the curve to be nonsingular, the discriminant $4a^3 + 27b^2 \neq 0 must hold, ensuring the set of points defines a smooth algebraic variety.^[16] To form an abelian group under a suitable addition law, the set of points is augmented by a distinguished identity element, denoted \mathcal{O} or the point at infinity. Geometrically, this point arises in the projective closure of the curve in \mathbb{P}^2(K), where it corresponds to the unique point (0 : 1 : 0) at infinity, serving as the neutral element for the group operation.^[17] Thus, the full group E(K) comprises the affine points together with \mathcal{O}. When K is a finite field \mathbb{F}_q with q elements, the group E(\mathbb{F}_q) is finite, and its order \#E(\mathbb{F}_q) satisfies Hasse's theorem: |\#E(\mathbb{F}_q) - (q + 1)| \leq 2\sqrt{q}.^[18] This bound provides an interval of possible group sizes, typically around q + 1, and is crucial for applications requiring knowledge of the group structure. In computations, especially for efficient point operations, projective coordinates are often used, representing points as (x : y : z) \in \mathbb{P}^2(K) with the affine points corresponding to z \neq 0 via (x/z, y/z), and \mathcal{O} as (0 : 1 : 0).^[1] This avoids divisions in arithmetic, though details of coordinate systems are beyond the scope here. For a concrete example, consider the curve y^2 = x^3 + x over \mathbb{F}_5. The affine points are found by testing x \in \{0, 1, 2, 3, 4\}: for x=0, y^2 = 0, so y=0; for x=1, y^2 = 2 (not a quadratic residue mod 5); for x=2, y^2 = 0, so y=0; for x=3, y^2 = 0, so y=0; for x=4, y^2 = 3 (not a quadratic residue). Thus, the affine points are (0,0), (2,0), and (3,0), and including \mathcal{O}, the group order is 4, consistent with Hasse's bound |N - 6| \leq 2\sqrt{5} \approx 4.47.^[19]

Point Operations

Point at infinity

In elliptic curve cryptography and algebraic geometry, the point at infinity, denoted \mathcal{O}, serves as the identity element in the abelian group formed by the points on an elliptic curve E over a field K. For any point P on E, the group operation satisfies P + \mathcal{O} = P, ensuring \mathcal{O} acts as the neutral element under point addition.^[14] Geometrically, \mathcal{O} arises as the unique intersection point of the elliptic curve with the line at infinity in the projective plane \mathbb{P}^2(K). When the affine Weierstrass equation y^2 = x^3 + ax + b is homogenized to Y^2 Z = X^3 + a X Z^2 + b Z^3, substituting Z = 0 yields X^3 = 0, so X = 0, and the point is represented in projective coordinates as [0 : 1 : 0], independent of the choice of Y \neq 0. This point compactifies the curve, allowing vertical lines in the affine plane—such as those connecting a point P = (x, y) to its negation -P = (x, -y)—to intersect the curve at \mathcal{O}.^[14] Algebraically, \mathcal{O} emerges in point addition formulas when the denominator vanishes, indicating a vertical line or tangent. For instance, adding a point to itself (doubling) results in a vertical tangent if the point has order 2, or in the general addition law, when two distinct points share the same x-coordinate, the slope is undefined, leading to the sum being \mathcal{O}. This handling ensures the group law remains well-defined across all cases, with \mathcal{O} represented without affine coordinates in implementations.^[14] Key properties include self-addition yielding the identity, \mathcal{O} + \mathcal{O} = \mathcal{O}, and the negation of the identity being itself, -\mathcal{O} = \mathcal{O}, consistent with the group's structure where \mathcal{O} has order 1. These properties underpin the associative and commutative nature of the group operation on E(K).^[14] As an example, consider points P = (x_0, y_0) and -P = (x_0, -y_0) on the curve y^2 = x^3 + ax + b. The line through them is vertical, x = x_0, which intersects the curve at P, -P, and \mathcal{O} in the projective plane, so their sum is P + (-P) = \mathcal{O}, illustrating the identity's role in inverses.^[14]

Point negation

In elliptic curve arithmetic, the negation of a point P = (x, y) on a curve given by the Weierstrass equation y^2 = x^3 + ax + b (with characteristic not 2) is defined as -P = (x, -y), where -y denotes the additive inverse of y in the underlying field. This operation arises from the symmetry of the curve with respect to the x-axis, as established by the form of the Weierstrass equation. For the point at infinity \mathcal{O}, the negation is itself, i.e., -\mathcal{O} = \mathcal{O}. The negation satisfies key group properties: P + (-P) = \mathcal{O} for any point P, confirming that -P is the additive inverse of P in the abelian group of points on the curve; and -(-P) = P, showing that negation is an involution. These properties hold generally for elliptic curves and are essential for the group law. In projective coordinates, where a point is represented as [X : Y : Z] with affine coordinates x = X/Z and y = Y/Z, the negation swaps the sign of the Y-coordinate, yielding [X : -Y : Z]. As an illustration, consider the point P = (1, 1) on y^2 = x^3 - x + 1, since $1 = 1 - 1 + 1 = 1, with -P = (1, -1). Computationally, point negation is inexpensive, requiring only a single field negation or subtraction operation and thus running in constant time O(1), in contrast to more involved operations like addition or doubling.

Point addition

In elliptic curve arithmetic, the addition of two distinct points P = (x_1, y_1) and Q = (x_2, y_2) on a curve given by the Weierstrass equation y^2 = x^3 + ax + b follows the chord-and-tangent law. This law states that the line passing through P and Q intersects the curve at a third point R', and the sum P + Q is the reflection of R' over the x-axis, denoted -R'.^[20] The reflection, or negation, of a point (x, y) is (x, -y). For distinct points where x_1 \neq x_2, the slope \lambda of the line through P and Q is given by

\lambda = \frac{y_2 - y_1}{x_2 - x_1}.

The coordinates of the sum P + Q = (x_3, y_3) are then

x_3 = \lambda^2 - x_1 - x_2, \quad y_3 = \lambda(x_1 - x_3) - y_1.

^[21] If x_1 = x_2 but y_1 \neq y_2, the points P and Q are negatives of each other, and the line through them is vertical, intersecting the curve at the point at infinity \mathcal{O}. Thus, P + Q = \mathcal{O}.^[21] To derive these formulas, consider the line equation y = \lambda(x - x_1) + y_1. Substituting into the curve equation yields a cubic polynomial in x: x^3 + ax + b - [\lambda(x - x_1) + y_1]^2 = 0. The roots are x_1, x_2, and x_3, and by Vieta's formulas, their sum is \lambda^2, so x_3 = \lambda^2 - x_1 - x_2. The y-coordinate of R' is y' = \lambda(x_3 - x_1) + y_1, and reflecting gives y_3 = -y'.^[21] For example, on the curve y^2 = x^3 - 7x + 10 over the reals, consider P = (1, 2) and Q = (3, 4). Here, \lambda = (4 - 2)/(3 - 1) = 1, so x_3 = 1^2 - 1 - 3 = -3 and y_3 = 1(1 - (-3)) - 2 = 2. Thus, P + Q = (-3, 2).^[22]

Point doubling

Point doubling is the operation of computing 2P = P + P for a point P on an elliptic curve, which requires finding the third intersection point of the tangent line to the curve at P with the curve itself.^[21] This operation arises as a special case of the general point addition law, where the two points coincide; geometrically, it corresponds to the limit of the secant line slope as the second point approaches P, yielding the derivative (tangent slope) instead.^[21] For a point P = (x_1, y_1) on the Weierstrass equation y^2 = x^3 + a x + b with y_1 ≠ 0, the tangent slope λ at P is \lambda = \frac{3 x_1^2 + a}{2 y_1}. The resulting point 2P = (x_3, y_3) has coordinates x_3 = \lambda^2 - 2 x_1, y_3 = \lambda (x_1 - x_3) - y_1. ^[21] In the special case where y_1 = 0, the tangent line at P is vertical (x = x_1), which intersects the curve at infinity, so 2P = O, the point at infinity; such points have order 2 in the group.^[21] For example, on the curve y^2 ≡ x^3 + 3x + 4 (mod 7) with a = 3 and b = 4, doubling P = (2, 2) uses λ ≡ (3·2^2 + 3)/(2·2) ≡ 15/4 ≡ 2 (mod 7), yielding x_3 ≡ 2^2 - 2·2 ≡ 0 (mod 7) and y_3 ≡ 2(2 - 0) - 2 ≡ 2 (mod 7), so 2P = (0, 2).^[23]

References

[1]
[PDF] 18.783 Elliptic Curves Lecture 1 - MIT Mathematics
Feb 8, 2017 · Definition. An elliptic curve is a smooth projective curve of genus 1 with a distinguished point. Definition (more precise). An elliptic curve ( ...
[2]
[PDF] An Introduction to Elliptic Curves and their Cryptographic Applications
What makes elliptic curve cryptography so effective is the simplicity of comput- ing scalar multiplication of a point P times constant a on an elliptic curve E, ...
[3]
[PDF] Digital Signature Standard (DSS) - NIST Technical Series Publications
Feb 5, 2024 · D.4 Scalar Multiplication on Koblitz Curves. This section describes a particularly efficient method of computing the scalar multiple nP on the.
[4]
[PDF] Secure outsourcing of scalar multiplication on elliptic curves
We follow the definition of elliptic curves in [8, Chapter 5] and [9, Chapter 13]. An elliptic curve E over a field K is the set of solutions to the ...
[5]
Use of Elliptic Curves in Cryptography - SpringerLink
Dec 1, 2000 · We discuss the use of elliptic curves in cryptography. In particular, we propose an analogue of the Diffie-Hellmann key exchange protocol.
[6]
[PDF] Elliptic curves and their cryptographic applications
Definition 2.18 For a given integer n and point P from the elliptic curve. E(K), elliptic curve point multiplication will be defined as. nP = P +E P +E P +E ...
[7]
[PDF] SEC 1: Elliptic Curve Cryptography
Sep 20, 2000 · Cryptographic schemes based on ECC rely on scalar multiplication of elliptic curve points ... variety of efficient general techniques for ...
[8]
https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r5.pdf
[9]
[PDF] Certicom ECC Challenge
The elliptic curve discrete logarithm problem (ECDLP): Given an elliptic curve E defined over a finite field Fq , and two points P, Q ∈ E(Fq), find an integer l ...Missing: hardness | Show results with:hardness
[10]
FIPS 186-2, Digital Signature Standard (DSS) | CSRC
FIPS 186-2 specifies algorithms for digital signatures, used to detect unauthorized modifications, authenticate the signatory, and ensure nonrepudiation.
[11]
[PDF] SEC 2: Recommended Elliptic Curve Domain Parameters
Sep 20, 2000 · [5] FIPS 186-2, Digital Signature Standard. Federal Information ... Standards for Efficient Cryptography Group, September, 2000.
[12]
RFC 8446 - The Transport Layer Security (TLS) Protocol Version 1.3
RFC 8446 TLS August 2018 Elliptic Curve Groups (ECDHE): Indicates support for the corresponding named curve, defined in either FIPS 186-4 [DSS] or [RFC7748] ...
[13]
None
### Summary of ECDSA in Bitcoin from https://bitcoin.org/bitcoin.pdf
[14]
[PDF] Joseph H. Silverman - The Arithmetic of Elliptic Curves
In the preface to the first edition of this book I remarked on the paucity of intro- ductory texts devoted to the arithmetic of elliptic curves.
[15]
[PDF] Chapter 4 - Elliptic Curves over Finite Fields - Koc Lab
Hasse's theorem gives bounds for the group of points on an elliptic curve over a finite field. In this section and in Section 4.5, we'll discuss some methods.
[16]
[PDF] A quick introduction to elliptic curves
An elliptic curve is the set of points (x, y) satisfying a Weierstrass equation, including the point at infinity, and is a special case of a plane algebraic ...
[17]
Elliptic Curves - Group of Points
When in (projective) Weierstrass form, an elliptic curve always contains exactly one point of infinity, ( 0 , 1 , 0 ) ("the point at the ends of all lines ...Missing: definition | Show results with:definition
[18]
[PDF] 18.783 S2021 Lecture 7: Hasse's Theorem and Point Counting
Mar 10, 2021 · We are now ready to prove Hasse's theorem. Theorem 7.3 (Hasse). Let E/Fq be an elliptic curve over a finite field. Then #E(Fq) = q + 1 − t, ...
[19]
[PDF] elliptic curves and cryptography - UChicago Math
Aug 29, 2016 · The discriminant of a Weierstrass equation is defined as. ∆=4a3 + 27b2. Page 3. ELLIPTIC CURVES AND CRYPTOGRAPHY. 3. Let's look at some ...
[20]
[PDF] Elliptic Curves - UCSD Math
Jul 10, 2013 · If P = Q, “the line through P and Q” means the tangent line. This way of defining the group law is called the “chord and tangent process”.
[21]
Elliptic Curves - Explicit Addition Formulae
Point Addition ; P · and ; Q · is ; Y = λ X − λ x 1 + y 1 . Substituting this into the curve gives the equation.
[22]
[PDF] Contents 5 Elliptic Curves in Cryptography - Evan Dummit
Example: Given the points P1 = (1, 2) and P2 = (3, 4) on the elliptic curve y2 = x3 − 7x + 10, find the sums. P2 + P2 and (P1 + P2) + P2. ◦ By differentiating ...
[23]
[PDF] Elliptic curves. - Purdue Computer Science
Example: Add the points (1,1) + (2,5) on the curve whose points were just listed. We have s = (5−1)/(2−1) = 4, x3. = 4. 2.Missing: y² = x³ -
[24]
None
Below is a merged summary of the scalar multiplication methods (Double-and-Add Algorithm) from SEC 1 v2.0 and related sources, combining all information from the provided segments into a concise yet comprehensive response. To maximize detail and clarity, I’ll use a table in CSV format to organize key aspects, followed by additional context and references. This ensures all information is retained while maintaining a dense and structured representation.
[25]
[PDF] Fast and Regular Algorithms for Scalar Multiplication over Elliptic ...
The core operation of elliptic curve cryptosystems is the scalar multiplication which multiplies some point ... multiply algorithm – or double-and-add algorithm.
[26]
[PDF] Side Channel Attacks on Implementations of Curve-Based ...
Jan 23, 2005 · Power analysis breaks elliptic curve cryptosystems even secure against the timing attack. In Progress in Cryptology – Indocrypt 2000, volume ...<|control11|><|separator|>
[27]
[PDF] MINIMALITY AND OTHER PROPERTIES OF THE WIDTH-w ...
A base 2 representation is called a width-w nonadjacent form (w-NAF, for short) if it satisfies the following conditions: (1) Each nonzero digit is an odd ...Missing: ary | Show results with:ary
[28]
[PDF] The Montgomery Powering Ladder
The Montgomery ladder is an algorithm for fast exponentiation in any abelian group, initially for elliptic curves, and is not very memory-intensive.
[29]
[PDF] Montgomery curves and the Montgomery ladder
Mar 30, 2017 · Abstract. The Montgomery ladder is a remarkably simple method of computing scalar multiples of points on a broad class of elliptic curves.