Elligator 2 for indistinguishable from random points

Start by reviewing the Elligator 2 research paper, the existing documentation in Monocypher source code and Covert Encryption source code, and the referenced GitHub discussions and Reddit comments. Done means producing proper documentation that explains secure implementation, subgroup randomisation, and the Curve25519/Ed25519 context without requiring readers to repeat the original trial and error.

I don't know to which extent you plan to document less well known algorithms, but here is one that is crucial for designing cryptographic formats that do not reveal that they are encrypted text but can still have public key encryption.

While there is some documentation on the Elligator 2 itself, namely a research paper, and while the use of the algorithm is somewhat general knowledge among cryptographic circles, almost no-one knows how to actually implement it securely.

The background is that most formats need to store an ephemeral public key in plain text, and if this is a Curve25519 point, what is stored is a 32-byte value, where the highest bit is always zero, only half of the remaining 255 bit values encode valid points, only 1/8 of those are in the prime group. All these combined, 32 bytes of random data have only 1/32 chance of being a normal public key. An adversary can quickly test for all these things and thus keys can be easily distinguished from random bytes.

Fixing it is a whole lot more complicated than just using Elligator 2 and inserting a few random bits to fill in the blanks. One also has to randomise the subgroups, to avoid only using the prime group, which fortunately stays compatible with standard ECDH (no need to project back to prime group first).

The existing documentation is within Monocypher source code, Covert Encryption source code, and in some Github discussions and old Reddit comments. It would be quite valuable if someone created proper documentation for it, so that not everybody else needs to do the same trial and error that we had to. Let me know if you are interested and I'll collect you the relevant links to get started.

Such documentation could work as a good primer to Ed25519/Curve25519 in general, as all the points can be visualised as a simple rectangle with 8 columns and q rows (~2**252), the low order points on the top row and the prime group on the left column. The neutral element (zero point) is at the top left corner. To hide points, we want to make use of all the columns but still correspond to the standard point on the left column on that same row. It turns out that point add/scalarmult are just adding or multiplying vectors in these rectangle coordinates (columns mod 8, rows mod q), so it can be visualised neatly. The base point is (row 1, column 0) so multiplying it by any number goes to row by that number but stays in the left column.