6. Mappages déterministes

Les mappages de cette section sont adaptés à l'implémentation d'encodages non uniformes ou uniformes en utilisant les constructions de la section 3. Certains mappages restreignent la forme de la courbe ou ses paramètres. Pour chaque mappage présenté, ce document énumère les restrictions pertinentes.

Notez que les mappages de cette section ne sont pas interchangeables : des mappages différents produiront presque certainement des points différents lorsqu'ils sont évalués sur la même entrée.

6.1. Choix d'une fonction de mappage

Cette section donne de brèves directives sur le choix d'une fonction de mappage pour une courbe elliptique donnée. Notez que les suites données dans la section 8 sont des mappages recommandés pour les courbes respectives.

Si la courbe elliptique cible est une courbe de Montgomery (section 6.7), la méthode Elligator 2 (section 6.7.1) est recommandée. De même, si la courbe elliptique cible est une courbe d'Edwards tordue (section 6.8), la méthode Elligator 2 pour Edwards tordue (section 6.8.2) est recommandée.

Les cas restants sont des courbes de Weierstrass. Pour les courbes supportées par la méthode Shallue-van de Woestijne-Ulas (SWU) simplifiée (section 6.6.2), ce mappage est celui recommandé. Sinon, la méthode SWU simplifiée pour AB == 0 (section 6.6.3) est recommandée si l'objectif est une meilleure performance, tandis que la méthode Shallue-van de Woestijne (section 6.6.1) est recommandée si l'objectif est la simplicité de l'implémentation. (La raison de cette distinction est que la méthode SWU simplifiée pour AB == 0 nécessite l'implémentation d'une carte d'isogénie en plus de la fonction de mappage, tandis que la méthode Shallue-van de Woestijne ne le nécessite pas.)

La méthode Shallue-van de Woestijne (section 6.6.1) fonctionne avec n'importe quelle courbe et peut être utilisée dans les cas où un mappage générique est requis. Notez cependant que ce mappage est presque toujours plus coûteux en termes de calcul que les recommandations spécifiques à la courbe ci-dessus.

6.2. Interface

L'interface générique partagée par tous les mappages de cette section est la suivante :

(x, y) = map_to_curve(u)

L'entrée u et les sorties x et y sont des éléments du corps F. Les coordonnées affines (x, y) spécifient un point sur une courbe elliptique définie sur F. Notez cependant que le point (x, y) n'est pas un point aléatoire uniforme.

6.3. Notation

À titre de guide approximatif, les conventions suivantes sont utilisées dans le pseudo-code :

• Toutes les opérations arithmétiques sont effectuées sur un corps F, sauf indication contraire explicite.

• u : l'entrée de la fonction de mappage. Il s'agit d'un élément de F produit par la fonction hash_to_field.

• (x, y), (s, t), (v, w) : les coordonnées affines du point produit par le mappage. Des variables indexées (par exemple, x1, y2, ...) sont utilisées pour les valeurs candidates.

• tv1, tv2, ... : variables temporaires réutilisables.

• c1, c2, ... : valeurs constantes, qui peuvent être calculées à l'avance.

6.4. Signe du point résultant

En général, les courbes elliptiques ont des équations de la forme y^2 = g(x). Les mappages de cette section identifient d'abord un x tel que g(x) est un carré, puis prennent une racine carrée pour trouver y. Puisqu'il existe deux racines carrées lorsque g(x) != 0, cela peut entraîner une ambiguïté concernant le signe de y.

Le cas échéant, les mappages de cette section lèvent cette ambiguïté en spécifiant le signe de la coordonnée y en fonction de l'entrée de la fonction de mappage. Deux raisons principales soutiennent cette approche : premièrement, cela couvre les courbes elliptiques sur n'importe quel corps de manière uniforme, et deuxièmement, cela laisse aux implémenteurs une marge de manœuvre pour optimiser les implémentations de racines carrées.

6.5. Cas exceptionnels

Les mappages peuvent avoir des cas exceptionnels, c'est-à-dire des entrées u sur lesquelles le mappage n'est pas défini. Ces cas doivent être gérés avec soin, en particulier pour les implémentations en temps constant.

Pour chaque mappage de cette section, nous discutons des cas exceptionnels et montrons comment les gérer en temps constant. Notez que toutes les implémentations DEVRAIENT utiliser inv0 (section 4) pour calculer les inverses multiplicatifs, afin d'éviter les cas exceptionnels résultant d'une tentative de calcul de l'inverse de 0.

6.6. Mappages pour les courbes de Weierstrass

Les mappages de cette section s'appliquent à une courbe cible E définie par l'équation

y^2 = g(x) = x^3 + A * x + B

où 4 * A^3 + 27 * B^2 != 0.

6.6.1. Méthode Shallue-van de Woestijne

Shallue et van de Woestijne [SW06] décrivent un mappage qui s'applique à essentiellement n'importe quelle courbe elliptique. (Notez cependant que ce mappage est plus coûteux à évaluer que les autres mappages de ce document.)

La paramétrisation donnée ci-dessous est pour les courbes de Weierstrass ; sa dérivation est détaillée dans [W19]. Cette paramétrisation fonctionne également pour les courbes de Montgomery (section 6.7) et les courbes d'Edwards tordues (section 6.8) via les cartes rationnelles données dans l'Annexe D : d'abord, évaluer le mappage Shallue-van de Woestijne vers une courbe de Weierstrass équivalente, puis mapper ce point vers la courbe cible de Montgomery ou d'Edwards tordue en utilisant la carte rationnelle correspondante.

Préconditions : Une courbe de Weierstrass y^2 = x^3 + A * x + B.

Constantes :

• A et B, les paramètres de la courbe de Weierstrass.

• Z, un élément non nul de F répondant aux critères ci-dessous. L'Annexe H.1 donne un script Sage [SAGE] qui produit le Z RECOMMANDÉ.

  1. g(Z) != 0 dans F.
  2. -(3 * Z^2 + 4 * A) / (4 * g(Z)) != 0 dans F.
  3. -(3 * Z^2 + 4 * A) / (4 * g(Z)) est un carré dans F.
  4. Au moins l'un de g(Z) et g(-Z / 2) est un carré dans F.

Signe de y : Les entrées u et -u donnent la même coordonnée x pour de nombreuses valeurs de u. Ainsi, nous fixons sgn0(y) == sgn0(u).

Exceptions : Les cas exceptionnels pour u se produisent lorsque (1 + u^2 * g(Z)) * (1 - u^2 * g(Z)) == 0. Les restrictions sur Z données ci-dessus garantissent que les implémentations qui utilisent inv0 pour inverser ce produit sont sans exception.

Opérations :

1. tv1 = u^2 * g(Z)
2. tv2 = 1 + tv1
3. tv1 = 1 - tv1
4. tv3 = inv0(tv1 * tv2)
5. tv4 = sqrt(-g(Z) * (3 * Z^2 + 4 * A)) # peut être précalculé
6. Si sgn0(tv4) == 1, fixer tv4 = -tv4 # sgn0(tv4) DOIT égaler 0
7. tv5 = u * tv1 * tv3 * tv4
8. tv6 = -4 * g(Z) / (3 * Z^2 + 4 * A) # peut être précalculé
9. x1 = -Z / 2 - tv5
10. x2 = -Z / 2 + tv5
11. x3 = Z + tv6 * (tv2^2 * tv3)^2
12. Si is_square(g(x1)), fixer x = x1 et y = sqrt(g(x1))
13. Sinon Si is_square(g(x2)), fixer x = x2 et y = sqrt(g(x2))
14. Sinon fixer x = x3 et y = sqrt(g(x3))
15. Si sgn0(u) != sgn0(y), fixer y = -y
16. retourner (x, y)

L'Annexe F.1 donne un exemple d'implémentation en ligne droite de ce mappage.

6.6.2. Méthode Shallue-van de Woestijne-Ulas simplifiée

La fonction map_to_curve_simple_swu(u) implémente une simplification du mappage Shallue-van de Woestijne-Ulas [U07] décrite par Brier et al. [BCIMRT10], qu'ils appellent le mappage « SWU simplifié ». Wahby et Boneh [WB19] généralisent et optimisent ce mappage.

Préconditions : Une courbe de Weierstrass y^2 = x^3 + A * x + B où A != 0 et B != 0.

Constantes :

• A et B, les paramètres de la courbe de Weierstrass.

• Z, un élément de F répondant aux critères ci-dessous. L'Annexe H.2 donne un script Sage [SAGE] qui produit le Z RECOMMANDÉ. Les critères sont les suivants :

  1. Z est un non-carré dans F,
  2. Z != -1 dans F,
  3. le polynôme g(x) - Z est irréductible sur F, et
  4. g(B / (Z * A)) est un carré dans F.

Signe de y : Les entrées u et -u donnent la même coordonnée x. Ainsi, nous fixons sgn0(y) == sgn0(u).

Exceptions : Les cas exceptionnels sont les valeurs de u telles que Z^2 * u^4 + Z * u^2 == 0. Cela inclut u == 0 et peut inclure d'autres valeurs qui dépendent de Z. Les implémentations doivent détecter ce cas et fixer x1 = B / (Z * A), ce qui garantit que g(x1) est un carré par la condition sur Z donnée ci-dessus.

Opérations :

1. tv1 = inv0(Z^2 * u^4 + Z * u^2)
2. x1 = (-B / A) * (1 + tv1)
3. Si tv1 == 0, fixer x1 = B / (Z * A)
4. gx1 = x1^3 + A * x1 + B
5. x2 = Z * u^2 * x1
6. gx2 = x2^3 + A * x2 + B
7. Si is_square(gx1), fixer x = x1 et y = sqrt(gx1)
8. Sinon fixer x = x2 et y = sqrt(gx2)
9. Si sgn0(u) != sgn0(y), fixer y = -y
10. retourner (x, y)

L'Annexe F.2 donne une implémentation en ligne droite générale et optimisée de ce mappage. Pour plus d'informations sur l'optimisation de ce mappage, voir la section 4 de [WB19] ou le code exemple trouvé sur [hash2curve-repo].

6.6.3. SWU simplifié pour AB == 0

Wahby et Boneh [WB19] montrent comment adapter le mappage SWU simplifié aux courbes de Weierstrass ayant A == 0 ou B == 0, ce qui n'est pas supporté par le mappage de la section 6.6.2. (Le cas A == B == 0 est exclu car y^2 = x^3 n'est pas une courbe elliptique.)

Cette méthode s'applique aux courbes comme secp256k1 [SEC2] et aux courbes favorables au couplage dans la famille Barreto-Lynn-Scott [BLS03], la famille Barreto-Naehrig [BN05], et d'autres familles.

Cette méthode nécessite de trouver une autre courbe elliptique E' donnée par l'équation

y'^2 = g'(x') = x'^3 + A' * x' + B'

qui est isogène à E et a A' != 0 et B' != 0. (Voir [WB19], Annexe A, pour une façon de trouver E' en utilisant [SAGE].) Cette isogénie définit une carte iso_map(x', y') donnée par une paire de fonctions rationnelles. iso_map prend en entrée un point sur E' et produit en sortie un point sur E.

Une fois que E' et iso_map sont identifiées, ce mappage fonctionne comme suit : sur l'entrée u, appliquez d'abord le mappage SWU simplifié pour obtenir un point sur E', puis appliquez la carte d'isogénie à ce point pour obtenir un point sur E.

Notez que iso_map est un homomorphisme de groupe, ce qui signifie que l'addition de points commute avec iso_map. Ainsi, lors de l'utilisation de ce mappage dans la construction hash_to_curve traitée dans la section 3, on peut effectuer une petite optimisation en mappant d'abord u0 et u1 vers E', en ajoutant les points résultants sur E', puis en appliquant iso_map à la somme. Cela donne le même résultat tout en ne nécessitant qu'une seule évaluation de iso_map.

Préconditions : Une courbe elliptique E' avec A' != 0 et B' != 0 qui est isogène à la courbe cible E avec une carte d'isogénie iso_map de E' vers E.

Fonctions auxiliaires :

• map_to_curve_simple_swu est le mappage de la section 6.6.2 vers E'

• iso_map est la carte d'isogénie de E' vers E

Signe de y : Pour cette carte, le signe est déterminé par map_to_curve_simple_swu. Aucun autre ajustement de signe n'est nécessaire.

Exceptions : map_to_curve_simple_swu gère ses cas exceptionnels. Les cas exceptionnels de iso_map sont les entrées qui font que le dénominateur de l'une ou l'autre fonction rationnelle s'évalue à zéro ; de tels cas DOIVENT renvoyer le point identité sur E.

Opérations :

1. (x', y') = map_to_curve_simple_swu(u) # (x', y') est sur E'
2. (x, y) = iso_map(x', y') # (x, y) est sur E
3. retourner (x, y)

Voir [hash2curve-repo] ou la section 4.3 de [WB19] pour plus de détails sur l'implémentation de la carte d'isogénie.

6.7. Mappages pour les courbes de Montgomery

Le mappage défini dans cette section s'applique à une courbe cible M définie par l'équation

K * t^2 = s^3 + J * s^2 + s

6.7.1. Méthode Elligator 2

Bernstein, Hamburg, Krasnova et Lange donnent un mappage qui s'applique à toute courbe avec un point d'ordre 2 [BHKL13], qu'ils appellent Elligator 2.

Préconditions : Une courbe de Montgomery K * t^2 = s^3 + J * s^2 + s où J != 0, K != 0, et (J^2 - 4) / K^2 est non nul et non carré dans F.

Constantes :

• J and K, les paramètres de la courbe elliptique.

• Z, un élément non carré de F. L'Annexe H.3 donne un script Sage [SAGE] qui produit le Z RECOMMANDÉ.

Signe de t : Ce mappage fixe le signe de t comme spécifié dans [BHKL13]. Aucun ajustement supplémentaire n'est requis.

Exceptions : Le cas exceptionnel est Z * u^2 == -1, c'est-à-dire 1 + Z * u^2 == 0. Les implémentations doivent détecter ce cas et fixer x1 = -(J / K). Notez que cela ne peut se produire que lorsque q = 3 (mod 4).

Opérations :

1. x1 = -(J / K) * inv0(1 + Z * u^2)
2. Si x1 == 0, fixer x1 = -(J / K)
3. gx1 = x1^3 + (J / K) * x1^2 + x1 / K^2
4. x2 = -x1 - (J / K)
5. gx2 = x2^3 + (J / K) * x2^2 + x2 / K^2
6. Si is_square(gx1), fixer x = x1, y = sqrt(gx1) avec sgn0(y) == 1.
7. Sinon fixer x = x2, y = sqrt(gx2) avec sgn0(y) == 0.
8. s = x * K
9. t = y * K
10. retourner (s, t)

L'Annexe F.3 donne un exemple d'implémentation en ligne droite de ce mappage. L'Annexe G.2 donne des procédures en ligne droite optimisées qui s'appliquent à des classes spécifiques de courbes et de corps de base.

6.8. Mappages pour les courbes d'Edwards tordues

Les courbes d'Edwards tordues (une classe de courbes qui inclut les courbes d'Edwards) sont données par l'équation

a * v^2 + w^2 = 1 + d * v^2 * w^2

avec a != 0, d != 0 et a != d [BBJLP08].

Ces courbes sont étroitement liées aux courbes de Montgomery (section 6.7) : chaque courbe d'Edwards tordue est birationnellement équivalente à une courbe de Montgomery ([BBJLP08], théorème 3.2). Cette équivalence donne un moyen efficace de hacher vers une courbe d'Edwards tordue : d'abord, hacher vers une courbe de Montgomery équivalente, puis transformer le résultat en un point sur la courbe d'Edwards tordue via une carte rationnelle. Cette méthode de hachage vers une courbe d'Edwards tordue nécessite donc d'identifier une courbe de Montgomery correspondante et une carte rationnelle. Nous décrivons comment identifier une telle courbe et une telle carte immédiatement ci-dessous.

6.8.1. Cartes rationnelles de Montgomery vers les courbes d'Edwards tordues

Il existe deux façons de sélectionner une courbe de Montgomery et une carte rationnelle à utiliser lors du hachage vers une courbe d'Edwards tordue donnée. La courbe de Montgomery et la carte rationnelle sélectionnées DOIVENT être spécifiées comme faisant partie de la suite de hachage vers courbe pour une courbe d'Edwards tordue donnée ; voir la section 8.

1. Lors du hachage vers une courbe d'Edwards tordue normalisée pour laquelle une forme de Montgomery correspondante et une carte rationnelle sont également normalisées, la forme de Montgomery et la carte rationnelle standard DEVRAIENT être utilisées pour assurer la compatibilité avec les logiciels existants.

   Dans certains cas, par exemple edwards25519 [RFC7748], le signe de la carte rationnelle de la courbe d'Edwards tordue vers sa forme de Montgomery correspondante n'est pas donné explicitement. Dans ce cas, le signe DOIT être fixé de telle sorte que l'application de la carte rationnelle au point de base de la courbe d'Edwards tordue produise le point de base de la courbe de Montgomery avec le signe correct. (Pour edwards25519, voir [RFC7748] et [Err4730].)

   Lors de la définition de nouvelles courbes d'Edwards tordues, un équivalent de Montgomery et une carte rationnelle DEVRAIENT également être spécifiés, et le signe de la carte rationnelle DEVRAIT être indiqué explicitement.

2. Lors du hachage vers une courbe d'Edwards tordue qui n'a pas de forme de Montgomery ou de carte rationnelle normalisée, la carte donnée dans l'Annexe D DEVRAIT être utilisée.

6.8.2. Méthode Elligator 2

Préconditions : Une courbe d'Edwards tordue E et une courbe de Montgomery équivalente M répondant aux exigences de la section 6.8.1.

Fonctions auxiliaires :

• map_to_curve_elligator2 est le mappage de la section 6.7.1 vers la courbe M.

• rational_map est une fonction qui prend un point (s, t) sur M et renvoie un point (v, w) sur E. Cette carte rationnelle doit être choisie comme défini dans la section 6.8.1.

Signe de t (et v) : Pour cette carte, le signe est déterminé par map_to_curve_elligator2. Aucun autre ajustement de signe n'est requis.

Exceptions : Les exceptions pour le mappage Elligator 2 sont celles données dans la section 6.7.1. Les exceptions pour la carte rationnelle sont celles données dans la section 6.8.1. Aucune autre exception n'est possible.

La procédure suivante implémente le mappage Elligator 2 pour une courbe d'Edwards tordue. (Notez que le point de sortie est noté (v, w) car il s'agit d'un point sur la courbe d'Edwards tordue cible.)

map_to_curve_elligator2_edwards(u)

Entrée : u, un élément de F. Sortie : (v, w), un point sur E.

1. (s, t) = map_to_curve_elligator2(u) # (s, t) est sur M
2. (v, w) = rational_map(s, t) # (v, w) est sur E
3. retourner (v, w)