9
$\begingroup$

According to the Curve25519 website:

Computing secret keys. Inside your program, to generate a 32-byte Curve25519 secret key, start by generating 32 secret random bytes from a cryptographically safe source: mysecret[0], mysecret[1], ..., mysecret[31]. Then do

mysecret[0] &= 248;
mysecret[31] &= 127;
mysecret[31] |= 64;

to create a 32-byte Curve25519 secret key mysecret[0], mysecret[1], ..., mysecret[31].

Since $248 = \mathtt{0b11111000}$, $127 = \mathtt{0b01111111}$, and $64 = \mathtt{0b01000000}$, the code above forces five bits of the random string to have a particular value (four are cleared and one is set).

This means that there are $2^{256-5}=2^{251}\approx 3.619 \times 10^{75}$ valid X25519 private keys. However, this answer states that:

given a valid public key $x$, $x^3 + 486662x^2 + x$ must have a square root modulo $2^{255}-19$. On the other hand, a random [255-bit] string will be a square only around $1/2$ of the time.

This statement seems to imply that there are approximately $\frac{1}{2}(2^{255})=2^{254}$ valid X25519 public keys, which means that there are about $2^{254}-2^{251} \approx 2.533 \times 10^{76}$ X25519 public keys for which there are no corresponding private keys. Therefore, it seems that these public keys are all invalid.

The Curve25519 website, however, states that:

The Curve25519 function was carefully designed to allow all 32-byte strings as Diffie-Hellman public keys.

which seems to contradict what I outlined above. So if I were theoretically to compute the corresponding public keys for all $2^{251}$ X25519 private keys, how many (unique*) public keys would I obtain?

Furthermore, since the website does say that "all 32-byte strings" are valid Diffie-Hellman public keys, what output $X$ would I get if I generated a secret key $A_S$ and did

$$ X = \operatorname{ECDH}(A_S,B_P) $$

where $B_P$ is one of the $2^{254}-2^{251}$ public keys without a corresponding private key? Would the result just be some pseudorandom string, or would it be something else?


* As far as I understand, the mapping $K_S \to K_P$ is one-to-one for all X25519 key pairs $(K_S,K_P)$, but please correct me if I am incorrect.

$\endgroup$

2 Answers 2

5
$\begingroup$

This is a tricky topic as it depends on the definition of "valid" in the public key context.

Your enumeration of the private keys for X25519 is obviously correct as it follows the definition of private keys for X25519, there are $2^{251}$ private keys. This is the correct answer to the original question.

Then, if you generate public keys from these private keys accordingly to the definition of X25519, you will end up with $2^{251}-13871158888686176767925968895441824247$ distinct public keys. The value $13871158888686176767925968895441824247$ comes from the fact two private keys whose random part (the 251 bits) adds to $27742317777372353535851937790883648493$ are two private keys that are opposite (modulo the order of the large subgroup) and will result in points with the same x-coordinate. This means the map $K_S \to K_P$ is not one-to-one.

However the implementation of X25519 can handle input public key that are not generated in such procedure. "handle" here means that it will compute correctly and not allow private key recovery attacks.

In fact, it can handle all values represented in 32 bytes that, modulo $2^{255-19}$, are x-coordinates of points belonging to curve25519 (the whole curve, not just the prime-order subgroup) or to the quadratic twist of curve25519. This will cover all the $2^{256}$ possible values.

In case the input represents an x-coordinate on the twist, then the result will be computed on the twist curve, and in that sense it will still be correct.

$\endgroup$
5
$\begingroup$

The Curve25519 curve has $\ell = 2^{252}+27742317777372353535851937790883648493$ possible points in the prime-order group, corresponding to $\ell$ private keys.

However, X25519 refers to a particular method of choosing a private key and performing a Diffie-Hellman exchange.

You could use Curve25519 but avoid X25519 entirely. You would choose any private key $a$ such that $0<a<\ell$, and then use regular variable-base scalar multiplication to compute a shared secret as $aB$, where $B=bG$, $G$ is a well-known base point, and $b$ is the private key of the other party such that $0<b<\ell$.

With X25519, the little-endian private key has the least significant byte clamped so that the private key is a multiple of 8. This is so that the result of the X25519 operation cannot be manipulated if the other party provides you with a public key point which is on the curve, but is not in the prime-order group. Depending on the situation, this prevents another party from learning a tiny bit of information about your private key. If you did not clamp, then you would have to take the extra step of validating that the other party's public key is in the prime-order group, by multiplying it by $\ell$ and checking that the result is the point at infinity.

The most significant byte is altered so that the most significant bit that is set as 1 is always in the same position. This means that the implementation in the original X25519 paper will run in constant time, thus avoiding leaking information about the private key.

What this means is that you can choose any random 32-byte sequence, and then clamp it to produce a private key. This private key may exceed $\ell$, but this will not matter, since the X25519 scalar multiplication operation is designed to accept oversized private keys. The scalar multiplication operation produces points that are in a cyclic group, so $(a+n\cdot\ell)B=aB$ for any integer value of $n$.

public key without a corresponding private key

If $B$ is just a random byte sequence, it will still be treated as a valid point on the curve by X25519. Therefore, if the byte sequence $B$ is not a valid point on the curve, it will be treated as a point $B'$ which is a valid point on the curve. One in 8 valid points on the curve will be in the prime-order group, and so the other 7 will not have an associated private key. The process of converting a private key to a public key will always produce a point in the correct prime-order group, because this involves multiplying by a base point which is definitely on the curve and in the correct prime-order group. Therefore, a valid curve point that is not in the prime-order group could not have been generated by any private key.

Acccording to my understanding, the mapping $K_S \to K_P$ is one-to-one for all X25519 key pairs $(K_S,K_P)$, but please correct me if I am incorrect.

This would be true if you followed the method I described above for using Curve25519 but avoiding X25519, and if the entire resulting coordinate pair was preserved. This would not be true for X25519, since X25519 allows private keys greater than $\ell$, where more than one private key byte sequence will map to the same public key (as described above). Furthermore, X25519 outputs only an x-coordinate and leaves ambiguity over the sign of the y-coordinate that would be recovered from the x-coordinate (Curve25519 is symmetrical across the x-axis).

if I were theoretically to compute the corresponding public keys for all $2^{251}$ X25519 private keys, how many (unique†) public keys would I obtain?

This is equivalent to asking:

How many possible values of $a$ are there, such that $a=x\bmod \ell$, where $2^{253}\leq x<2^{254}$, and $x$ is a multiple of 8. Then, the answer would have to be roughly halved to account for the ambiguity of the y-coordinate sign for each X25519 x-coordinate output. Perhaps a mathematician here can solve this brain teaser. I'd expect there to be collisions due to the $\operatorname{mod} \ell$ operation.

$\endgroup$
4
  • $\begingroup$ [note: this comment refers to a former version of the answer] What's the meaning of "public key" and "corresponding" in "All public keys will have a corresponding private key"? I admit I have trouble reconciling $\ell\ll2^{256}$ and the quote "all 32-byte strings [are] Diffie-Hellman public keys". I'm ready to accept that every 32-byte string can be safely handled as if it was a valid public key, but that does not imply it's actually one, much less one with "a corresponding private key". $\endgroup$
    – fgrieu
    Jan 10, 2023 at 13:57
  • 1
    $\begingroup$ @fgrieu I've cleaned up my answer since your comment. I think the quote "all 32-byte strings [are] Diffie-Hellman public keys" must be referring to the idea that the X25519 function will not fail for any 32-byte input. In contrast, other variable-base scalar multiplication implementations will fail if the point is not on the curve (50% of random byte strings would not be on the curve). Therefore, an invalid point $B$ will be treated as a valid point $B'$ for the purposes of scalar multiplication. $\endgroup$
    – knaccc
    Jan 10, 2023 at 14:18
  • $\begingroup$ I don't like this answer and I have written my own. For example: there are no distinct private keys, generated with the X25519 procedure, that are congruent modulo the order $\endgroup$
    – Ruggero
    Jan 10, 2023 at 16:21
  • $\begingroup$ @Ruggero great point in your answer about the x-coordinate not appearing alongside a sign bit, causing ambiguity over the sign of the y-coordinate. I just realised I totally overlooked the question asked in the title of the post, which is different than the bold section of the post body. I'm not sure whether this was a typo, or if there were genuinely two different questions being asked. $\endgroup$
    – knaccc
    Jan 10, 2023 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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