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:
- Generate an Ed25519 (!) key with
- 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)
- Add the low-order point to your Ed25519 key with
- Convert your Ed25519 point to Curve25519 with
- 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).
- 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.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