Digital signatures often use elliptic curves. For example, Bitcoin and Ethereum use the elliptic curve secp256k1 [1]. This post will discuss the elliptic curve Ed25519 [2] using in Monero and in many other applications.
Ed25519 has the equation
y² − x² = 1 + d x² y²
over the finite field Fq where q = 2255 − 19 and d = −121665/121666. The general form of the equation above makes Ed25519 a “twisted Edwards curve.”
The expression for d is not the rational number it appears to be. Think of it as
d = −121665 × 121666−1
where the multiplication and the multiplicative inverse are calculated mod q.
We could calculate d in Python as follows.
>>> q = 2**255 - 19 >>> d = (-121665*pow(121666, -1, q)) % q >>> d 37095705934669439343138083508754565189542113879843219016388785533085940283555
The equation above does not look like an elliptic curve if you think of an elliptic curve having the form
y² = x³ + ax + b.
But that form, known as Weierstrass form, is not the most general definition of an elliptic curve. Elliptic curves can be written in that form [3] but they do not have to be. There are computational advantages to writing curves in the form
y² − x² = 1 + d x² y²
when possible rather than in Weierstrass form [4].
Elliptic curve digital signatures require a specified base point. The Monero whitepaper describes the base point simply as
G = (x, −4/5).
That’s leaving out a fair bit of detail. First of all, 4/5 is interpreted as 4 times the multiplicative inverse of 5 mod q, similar to the calculation for d above.
>>> y = (-4*pow(5, -1, q)) % q; y 11579208923731619542357098500868790785326998466564056403945758400791312963989
Now we have two tasks. How do we solve for x, and which solution do we take?
We need to solve
x² = (y² − 1)/(1 + d y²) mod q.
We can do this in Python as follows.
>>> from sympy import sqrt_mod >>> roots = sqrt_mod((y**2 - 1)*pow(1 + d*y**2, -1, q), q, all_roots=True) >>> roots [15112221349535400772501151409588531511454012693041857206046113283949847762202, 42783823269122696939284341094755422415180979639778424813682678720006717057747]
So which root to we choose? The convention is to use the even solution, the first one above. (The two roots add to 0 mod q; one will be odd and one will be even because q is odd.)
Related posts
[1] The name secp256k1 was created as follows. The “sec” comes from “Standards for Efficient Cryptography,” referring to the group that specified the curve parameters. The “p” means the curve is over a finite field of prime order. The order of the curve is slightly less than 2256. The “k” indicates that this is a Koblitz curve.
[2] The “Ed” part of the name refers to Harold Edwards, the mathematician who studied the family of elliptic curves now known as Edwards curves. The “25519” part of the name refers to the fact that the curve is over the finite field with 2255 − 19 elements.
[3] Provided the elliptic curve is not over a field of characteristic 2 or 3.
[4] Group operations can be implemented more efficiently and the point at infinity can be handled without exception logic.