# Curve25519 Specification

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 )

• I'm pretty sure the $A$ was chosen to be the smallest $A$ that satisfies all of DJB's security requirements. – SEJPM Apr 7 '20 at 11:03
• I think he wants a basic level explanation of those requirements. DJB explains those on his website SafeCurves. – corpsfini Apr 7 '20 at 11:40
• 25519 has a strength of almost exactly 126 bits, which is estimated equal to about 3000 bits RSA (and the same for classic/FF/modp/Zp*/non-EC DSA DH and EG), (all of) which are considered sufficient unless/until quantum works, which at this point nobody knows (at least openly). See keylength.com . – dave_thompson_085 Apr 8 '20 at 0:30

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).

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$$).

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.