3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Note that this is about implementation specifics, which should be asked on StackOverflow instead. Or indeed the BC mailing list, which you probably should prefer. $\endgroup$ – Maarten Bodewes Sep 22 '17 at 9:55
  • $\begingroup$ This is not a Bouncycastle specific question, since the 33 byte format is part of an IETF standard. Therefore the answer is broadly applicable and is not an implementation specific question for Bouncycastle. tools.ietf.org/id/… $\endgroup$ – knaccc Sep 22 '17 at 10:43
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hmm, that may be tricky when importing keys generated on another location. But I personally would recommend you to discuss this on the developer mailing list of Bouncy Castle instead. $\endgroup$ – Maarten Bodewes Sep 22 '17 at 9:55
  • $\begingroup$ @Lery Are you therefore saying that the Wikipedia article is wrong? I'd imagine that "accepting any 32 byte sequence without validation" implies there would not have to be a mod Q operation. $\endgroup$ – knaccc Sep 22 '17 at 10:44
  • $\begingroup$ @knaccc What I'm saying is that it appears that the Curve25519FieldElement in BC cannot have a x value bigger than $2^{255}-19$ and that depending on the way they've implemented it, it might cause you problems depending on how you are using the implementation... $\endgroup$ – Lery Sep 22 '17 at 11:43

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.