Curve25519 Specification

Question

The Curve25519 is defined over the prime $2^{255}-19$ with $A = 486662$, so that the curve equation is: $y^2 = x^3 + 486662x^2 + x$

I'm trying to understand, why the parameters are what they are.

First of all the Prime. I already have some ideas from the Bernstein Paper, why he chose this prime. Can someone say, if one of them is false, or if i'm not mentioning an important point?:

• Faster field operations, when a prime is close to a power of 2
• no space wasted, when having a key length close to $32 \cdot k$ for any $k$
• pretty high security level because of 255 Bit key length (not sure, but is it equal to a 15000 Bit RSA system?)

Bernstein described the choice of the prime pretty well. But i dont unterstand why he chose A = 486662. I read his reasons for that choice, but i simply don't understand them. Can someone explain it to me, on a more basic level?

Edit:

I tried to understand the choice of 486662 an hopefully got questions that help me understand it:

• How can a subgroup be created by a point ( So the base points creates a subgroup, which has a prime order. But this order is also the order of the curve25519. I'm a bit confused by that )

• So the order of the subgroup is a prim, but the order of the Curve25519 is also a prime. I dont understand how A makes a curves, which has the order ${4 \cdot n, 8 \cdot n}$, when the order is in fact a prime

• What are the attacks, that can't be used, when A is chosen this way? ( I think: only small subgroup attacks, e.g. Pohlig–Hellman. But Bernstein wrote in his paper, that there are various attacks )

Answer 1

From the paper:

I selected (A − 2)/4 as a small integer, as suggested by Montgomery, to speed up the multiplication by (A − 2)/4

The smaller the value (A-2)/4 is, the faster is the multiplication by that value (which is required by the point doubling formula).

So basically the curve was found by incrementing the A value, restricting to the values where (A-2)/4 is an integer, until it generates a curve with order $4n$ or $8n$ where $n$ is prime (and some other criteria described in the paper: the twist order should be in the same format; and $n$ should be larger than $2^{252}$ so that the private key can be generated by simply randomly filling a byte buffer and not having to bother with the case where the private key is equal to the curve order).

Answer 2

How can a subgroup be created by a point ( So the base points creates a subgroup, which has a prime order. But this order is also the order of the curve25519. I'm a bit confused by that )

Take an element $g$ in a group $G$. You can create the subgroup generated by $g$, by taking all the elements $1$, $g$, $g^2$, $\ldots$, $g^{q-1}$ and eventually, $g^q=1$, which goes back full circle. Here, $l$ is the order of $g$, and is a divisor of the order of $G$.

An elliptic curve is a group, so it works the same. Take a point $P$, and then the subgroup will be $\infty$, $P$, $2P$, $\ldots$, $(q-1)P$, and again, eventually we have $qP=\infty$ for a value $q$. The point $P$ has order $q$, and $q$ is a divisor of the curve cardinality.

$q$ is not necessarily prime, but for cryptographic purposes, we want a point $P$ that generates a subgroup of prime order $q$ with $q$ big enough. Therefore, the curve cardinality must have a large prime factor.

So the order of the subgroup is a prime, but the order of the Curve25519 is also a prime. I dont understand how A makes a curves, which has the order $4\cdot𝑛$,$8\cdot n$, when the order is in fact a prime

You might be confused, because Curve25519 has order $8\cdot q$ where $q$ is a large prime number.

What are the attacks, that can't be used, when A is chosen this way? ( I think: only small subgroup attacks, e.g. Pohlig–Hellman. But Bernstein wrote in his paper, that there are various attacks )

A list of security criterias was chosen. You can find a list on SafeCurves (there is even a script to verify the criterias.) Then, the algorithm to find $A$ was simple and completely transparent: find the smallest integer $A$ such that the curve satisfies all the criterias.

The main criteria is that the cardinalities of the curve and its quadratic twist are $8\cdot q$ and $4\cdot q'$ where $q$ and $q'$ are prime, since he explains in his paper that those are the best possible choice (Montgomery curves always have a cardinality that is a multiple of $4$).

Answer 3

Meta: I know this answers is a basic copy and paste. It should be a comment to better understand the question, but it's too long, so I posted it as answer.

It's very clear from the curve25519 paper.

I selected $(A − 2)/4$ as a small integer, as suggested by Montgomery, to speed up the multiplication by $(A − 2)/4$; this has no effect on the conjectured security level. To protect against various attacks discussed in Section 3, I rejected choices of $A$ whose curve and twist orders were not $\{4 · prime, 8 · prime\}$; here $4, 8$ are minimal since $p \in 1+4\mathbb{Z}$. The smallest positive choices for $A$ are $358990$, $464586$, and $486662$. I rejected $A = 358990$ because one of its primes is slightly smaller than $2^{252}$, raising the question of how standards and implementations should handle the theoretical possibility of a user’s secret key matching the prime; discussing this question is more difficult than switching to another $A$. I rejected $464586$ for the same reason. So I ended up with $A = 486662$.

Maybe it would be better if you could ask for details of a specific choice.