5
$\begingroup$

I'm currently working on a project where I want to map Curve25519 public keys to uniformly random noise. The main idea is that when these transformed public keys are sent over a network, an outsider wouldn't easily recognize them as typical public keys. I came across a solution using Elligator (elligator).

The current code base of my project utilizes libsodium to generate public keys, specifically through the crypto_scalarmult function (you can find it here: libsodium).

However, there's a challenge. Elligator requires both the x and y-coordinates, and libsodium (as with most ECC libraries) only works with the x-coordinate. So, I need to figure out how to obtain the corresponding y-coordinate. I've considered solving the equation $$y^2 = x^3 + 486662x^2 + x \bmod p,$$ but dealing with such large numbers in C seems challenging. The idea of taking the square root in modular arithmetic is also a bit daunting.

Note: I suspect that the sign of the y-coordinate might be sufficient for Elligator, but I need to delve deeper into that. Any insights or help on tackling this issue would be greatly appreciated. Thanks in advance!

$\endgroup$
2
  • 3
    $\begingroup$ I would recommend using Monocypher. The author wrote that Elligator website. Libsodium doesn't fully support Elligator2. $\endgroup$ Dec 2, 2023 at 18:25
  • 1
    $\begingroup$ Thank you for the suggestion. I view that as a last resort since I aim to avoid including a new library. Currently, we are already using libsodium for various other purposes, and we've come across an Elligator implementation (github.com/Kleshni/Elligator-2/tree/master) that doesn't need any new dependencies. The "only" challenge we're facing is obtaining the y-coordinate. $\endgroup$
    – Safari1811
    Dec 2, 2023 at 21:24

1 Answer 1

5
$\begingroup$

Monocypher author here.

First, I can confirm Elligator only needs the sign of the y coordinate… which by definition of X25519, is always "positive". This is not a good thing! You want instead to select the sign at random. X25519 is insensitive to the sign of its y coordinate anyway, so even if you recover it you have to discard it.

But there's worse: there is no easy way to turn a regular X25519 public key into a seemingly random number!!

See, Elligator only works when the point you originally pick was generated at random… over the whole curve. Unfortunately for you, X25519 public keys belong to a strict subset. One eight of the curve to be precise: the prime order subgroup. (Read this tutorial if you don't quite understand what I just said).

Long story short, to get a truly random point over the whole curve, you need to take a public key and add a random low-order point. There are 8 such points by the way. The bad news is, libsodium has no easy way to do this. You need to take the long route and reproduce this procedure by hand:

  1. Generate an Ed25519 (!) key with crypto_scalarmult_ed25519_base().
  2. Select a low-order point at random (you need a list to begin with, and there are ways to do do that selection in constant time)
  3. Add the low-order point to your Ed25519 key with crypto_core_ed25519_add().
  4. Convert your Ed25519 point to Curve25519 with https://libsodium.gitbook.io/doc/advanced/ed25519-curve25519.
  5. At last, you have a truly random point on the entire curve. Select the sign of the y coordinate at random, then use the Elligator reverse map to get a random representative.
    • But wait! This step will fail half the time! If it does, go back to step (1).
  6. Now you have a random number between 0 and 2^254 - 10, and if your implementation is nice enough, the top two bits will be be random. Otherwise they'll be cleared, and you'll have to pad them with random bits one way or another. Do remember to clear those bits when going in the other direction (unless your Elligator implementation is nice).

Now you could be tempted to shorten this procedure by using an unclamped scalarmult instead. I'd suggest you don't: see, X25519 is built in a way that ignores the low-order component of a point. So when you add a random low-order point, you get a public key that is for all intents and purposes equivalent to the normal public key you should have obtained from the same private scalar. This is good, because it makes your hidden points (once recovered from the random representative), compatible out of the box with X25519.

If on the other hand you use the unclamped scalarmult, you'll not only add a random low-order point, you'll add a matching prime-order point. And that throws off your compatibility away, forcing you to use an unclamped scalarmult for your long term public keys and key exchange. Which is possible, but not recommended: not only would you be deviating from the original X25519, you would also reveal the first 3 bits of your long term private keys, which in some situations could be less than ideal (those 3 bits could conceivably be used to help identify you in some circumstance).


Now that's if you insist on using libsodium. Which you may, because libsodium is basically the fastest library around, beating portable C implementations by a factor of 2.

Or you could listen to my sales pitch and use Monocypher. Joke aside, I'm not sure how much of a choice you actually have: Monocypher is the only complete implementation of Elligator2 over Curve25519 I know of.There's Kleshni of course, but it's incomplete, and as such requires that you use the procedure I outlined above.

With Monocypher however it all gets much simpler: Generate an ephemeral key pair with crypto_elligator_key_pair() (you'll get a private key and a random representative of the public key), and on the other side you can just decode the representative with crypto_elligator_map(). You'll get a public key that's compatible with regular X25519 (from libsodium or from Monocypher, there's no difference).

Don't want the extra dependency? You're in luck, Monocypher is exceptionally lightweight: single file, zero dependency, you can just copy monocypher.c and monocypher.h into your project and (if you want) delete the code you don't use. Even if you don't delete anything, Monocypher will add less than 100KB to your binary, even under -O3.

$\endgroup$
4
  • 1
    $\begingroup$ Welcome to Cryptography.SE. $\endgroup$
    – kelalaka
    Dec 3, 2023 at 18:08
  • 1
    $\begingroup$ What an honor! I've already come across your "Surrounded by Elligator" post, which has been incredibly helpful. Thanks for the guide on integrating Elligator with libsodium; I'll give it a try after reading your tutorial. Not that your sales pitch doesn't work (it clearly did), but I am somewhat restricted within the current project I'm working on. $\endgroup$
    – Safari1811
    Dec 3, 2023 at 19:30
  • 1
    $\begingroup$ Just to ensure I don't mess up step 2: following the answer here, can I simply take a random Ed25519 point and multiply it by the order of the prime subgroup? $\endgroup$
    – Safari1811
    Dec 3, 2023 at 19:35
  • 1
    $\begingroup$ @Safari1811, glad you appreciated my answer. I understand your constraints, but if you can use the same parameters as I, you might be interested by the test vectors in my test suite. About your question, yes, that works. Just make sure you check the order by multiplying it by 4. Once you have your point, you can repeatedly add it to itself to generate all low-order points (4 of them will have order 8). You do not need the full list, though, we can apply a few tricks (search for "adding a low order point"). $\endgroup$ Dec 4, 2023 at 21:21

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.