How to use a random 32 byte sequence as a curve25519 public key

Question

According to the Wikipedia Curve25519 article, Curve25519 "accepts any 32-byte string as a valid public key and does not require validation"

However, I need to provide BouncyCastle with a 33 byte key. I have attempted to simply prepend 0x02 or 0x03, and this sometimes is accepted. However I often get the exception "x value invalid for Curve25519FieldElement" or "Invalid point compression".

Is the wikipedia article incorrect, and e.g. do I need to ensure that the x coordinate does not exceed the Curve25519 group order 2^252 + 27742317777372353535851937790883648493?

Answer 1

Indeed, you seems to be right since when taking a look at the BC code, we find in the Curve25519FieldElement object that:

if (x == null || x.signum() < 0 || x.compareTo(Q) >= 0)
{
    new IllegalArgumentException("x value invalid for Curve25519FieldElement");
}

So in BouncyCastle it appears that you have to make sure that x.CompareTo(Q) < 0, which effectively means that you should restrict your x coordinate to something below the $Q$ value, however this is not the group order, but the field order, which is $2^{255}-19$. This is normal, since this represents an element of the Field...

Now, you've remarked that the Curve25519 has been designed to accept all 32 byte public keys as a valid point encoding:

Firstly, a value on 32 bytes is within $\{0,1,\ldots,2^{256}-1\}$, that is $2^{256}$ possibilities, while the field order is $2^{255}-19$, which means that you only have $2^{255}-19$ elements in your field...

But now, the function Curve25519 is actually defined in the paper thanks to the theorem 2.1 as being a function that producing $s$ (in little endian) out of an integer $n$ and a point $Q$ (both encoded in little endian), such that $s$ is the unique $s\in F_{2^{255}-19}$ such that $X_0(nQ)=s$ for the function defined as $X_0:E(F_{(2^{255}-19)^2}) \to F_{(2^{255}-19)^2}$ such that $X_0(\infty)=0; X_0(x,y)=x$, if we let $q\in F_{2^{255}-19}$ and $n$ be an integer for all $Q\in E(F_{(2^{255}-19)^2})$ such that $X_0(Q)=q\bmod 2^{255}-19$, and here this modulo reduction is why you are having a problem, I think.

This is actually pretty well explained in the paper:

Fix $q\in\{0,1,\ldots,2^{256}-1\}$ and $n\in 2^{254}+8\{0,1,\ldots,2^{251}-1\}$. By Theorem 2.1, there is a unique integer $s\in\{0,1,\ldots,2^{255}-20\}$ with the following property: $s=X_0(nQ)$ for all $Q\in E(F_{(2^{255}-19)})$ such that $X_0(Q)=q \bmod 2^{255}-19$.

Here your public key is the value $q$ and $n$ is the secret key.

Which means that we actually have collisions in the Curve25519 function, which are handled within the function. I imagine that BouncyCastle, depending how they've implemented this, might be converting the computed values into Curve25519FieldElement only AFTER having passed the values through the Curve25519 function...

So I think you are probably providing the public key in a wrong way, using the wrong object to store it... Which is not a problem when used as the output of the Curve25519 function, but is a problem when using your own values.

You might want to compute for your point $P$ the output of $X_0(\underline{1}\cdot \underline{P})$ and then encode that value as a public key, to have the correct format.