Compatibility of the Elligator2 implementation

[peckto]

Hi libsodium team,

I'm searching for an Elligator2 implementation compatible with the hash-to-curve RFC draft:
https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11

From your documentation, I could not find any details about the Elligator2 implementation in libsodium. I created a sample application to compare the result from libsodium with the test-vectors form the RFC.

Sample application:

#include <sodium.h>
#include <stdio.h>


int main() {
    size_t bin_len;
    char  in_hex[] = "7f3e7fb9428103ad7f52db32f9df32505d7b427d894c5093f7a0f0374a30641d";
    uint8_t  in_bin[32];
    uint8_t p[32];
    char p_hex[32*2+1];

    sodium_hex2bin(in_bin, sizeof(in_bin), in_hex, 32*2, NULL, &bin_len, NULL);
    crypto_core_ed25519_from_uniform(p, in_bin);
    sodium_bin2hex(p_hex, sizeof(p_hex), p, sizeof(p));

    printf("in : %s\n", in_hex);
    printf("out: %s\n", p_hex);

    return 0;
}

test-vector from RFC:

J.5.2.  edwards25519_XMD:SHA-512_ELL2_NU_

   suite   = edwards25519_XMD:SHA-512_ELL2_NU_
   dst     = QUUX-V01-CS02-with-edwards25519_XMD:SHA-512_ELL2_NU_

   msg     =
   P.x     = 1ff2b70ecf862799e11b7ae744e3489aa058ce805dd323a936375a84695e76da
   P.y     = 222e314d04a4d5725e9f2aff9fb2a6b69ef375a1214eb19021ceab2d687f0f9b
   u[0]    = 7f3e7fb9428103ad7f52db32f9df32505d7b427d894c5093f7a0f0374a30641d
   Q.x     = 42836f691d05211ebc65ef8fcf01e0fb6328ec9c4737c26050471e50803022eb
   Q.y     = 22cb4aaa555e23bd460262d2130d6a3c9207aa8bbb85060928beb263d6d42a95

From my understanding, u[0] would be the input for Elligator2 and Q.x the result.
With the sample application, I get a different result compared to the test-vector:

$ ./elligator2
in : 7f3e7fb9428103ad7f52db32f9df32505d7b427d894c5093f7a0f0374a30641d
out: 44b2fa2a6bb0b2adeace690a5a83b7fbe5bb487c34e64dc109b90bc4e00f670b

This leads me to the following questions:
Is my usage from crypto_core_ed25519_from_uniform correct?
Is the libsodium implementation of the Elligator2 algorithm supposed to be compatible with the RFC draft?
If not, which specification do you follow?

Best regards
Tobias

[jedisct1]

The hash-to-curve map is accessible via the following functions, but only in the master branch:

• crypto_core_ed25519_from_string() (_NU)
• crypto_core_ed25519_from_string_ro() (_RO)
• crypto_core_ristretto255_from_string() (_NU)
• crypto_core_ristretto255_from_string_ro() (_RO)

from_string*() and from_uniform() both use Elligator, but handle the sign differently. In from_uniform() the top bit of the string represents the sign of the X coordinate.

[peckto]

Thank you for the answer. This helps me a lot.
What is the exact scope of the from_string*() function?
Does it implement the encode_to_curve function from the RFC:

encode_to_curve(msg):
   u = hash_to_field(msg, 1)
   Q = map_to_curve(u[0])
   P = clear_cofactor(Q)
   return P

(respectively hash_to_curve)

Do you also expose the map_to_curve step itself?

[peckto]

I'm sorry to ask you again.
Is there any news on this topic?

[jedisct1]

The _from_string() function implements what you describe here as encode_to_curve(). The map from a 384 bit field element to a group element is not exposed and there are no plans to expose it.

[peckto]

Thank you for the clarification.