0
$\begingroup$

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 )

$\endgroup$
  • $\begingroup$ I'm pretty sure the $A$ was chosen to be the smallest $A$ that satisfies all of DJB's security requirements. $\endgroup$ – SEJPM Apr 7 at 11:03
  • $\begingroup$ I think he wants a basic level explanation of those requirements. DJB explains those on his website SafeCurves. $\endgroup$ – corpsfini Apr 7 at 11:40
  • 1
    $\begingroup$ 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 . $\endgroup$ – dave_thompson_085 Apr 8 at 0:30
2
$\begingroup$

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

| improve this answer | |
$\endgroup$
2
$\begingroup$

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

| improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.