6. Applications déterministes

Les applications (mappings) de cette section conviennent à l'implémentation d'encodages non uniformes ou uniformes au moyen des constructions de la Section 3. Certaines applications imposent des restrictions sur la forme de la courbe ou sur ses paramètres. Pour chaque application présentée, ce document énumère les restrictions pertinentes.

Notons que les applications de cette section ne sont pas interchangeables : des applications différentes produiront presque certainement des points différents lorsqu'elles sont évaluées sur la même entrée.

6.1. Choix d'une fonction d'application

Cette section donne de brèves recommandations sur le choix d'une fonction d'application pour une courbe elliptique donnée. Notons que les suites données à la Section 8 constituent les applications recommandées 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 courbes d'Edwards tordues (Section 6.8.2) est recommandée.

Les cas restants sont les courbes de Weierstrass. Pour les courbes prises en charge par la méthode Shallue-van de Woestijne-Ulas simplifiée (SWU simplifiée, Section 6.6.2), cette application est celle qui est recommandée. Sinon, la méthode SWU simplifiée pour AB == 0 (Section 6.6.3) est recommandée si l'objectif est la meilleure performance, tandis que la méthode de Shallue-van de Woestijne (Section 6.6.1) est recommandée si l'objectif est la simplicité d'implémentation. (La raison de cette distinction est que la méthode SWU simplifiée pour AB == 0 requiert d'implémenter une application d'isogénie en plus de la fonction d'application, ce que ne fait pas la méthode de Shallue-van de Woestijne.)

La méthode de Shallue-van de Woestijne (Section 6.6.1) fonctionne avec n'importe quelle courbe et peut être utilisée dans les cas où une application générique est requise. Notons toutefois que cette application est presque toujours plus coûteuse en calcul que les recommandations spécifiques aux courbes ci-dessus.

6.2. Interface

L'interface générique partagée par toutes les applications 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 d'une courbe elliptique définie sur F. Notons toutefois que le point (x, y) n'est pas un point uniformément aléatoire.

6.3. Notation

À titre indicatif, les conventions suivantes sont utilisées dans le pseudocode :

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

• u : l'entrée de la fonction d'application. 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 l'application. Des variables indicé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 applications de cette section identifient d'abord un x tel que g(x) soit un carré, puis prennent une racine carrée pour trouver y. Comme il existe deux racines carrées lorsque g(x) != 0, cela peut engendrer une ambiguïté quant au signe de y.

Lorsque cela est nécessaire, les applications 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 d'application. Deux raisons principales justifient cette approche : premièrement, cela couvre de manière uniforme les courbes elliptiques sur n'importe quel corps, et deuxièmement, cela laisse aux implémenteurs une marge de manœuvre pour optimiser les implémentations de racine carrée.

6.5. Cas exceptionnels

Les applications peuvent comporter des cas exceptionnels, c'est-à-dire des entrées u pour lesquelles l'application n'est pas définie. Ces cas doivent être traités avec soin, en particulier pour les implémentations en temps constant.

Pour chaque application de cette section, nous discutons des cas exceptionnels et montrons comment les traiter en temps constant. Notons 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. Applications pour les courbes de Weierstrass

Les applications 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 de Shallue-van de Woestijne

Shallue et van de Woestijne [SW06] décrivent une application qui s'applique à essentiellement n'importe quelle courbe elliptique. (Notons toutefois que cette application est plus coûteuse à évaluer que les autres applications de ce document.)

Le paramétrage donné ci-dessous concerne les courbes de Weierstrass ; sa dérivation est détaillée dans [W19]. Ce paramétrage fonctionne également pour les courbes de Montgomery (Section 6.7) et les courbes d'Edwards tordues (Section 6.8) via les applications rationnelles données à l'Annexe D : d'abord, évaluer l'application de Shallue-van de Woestijne vers une courbe de Weierstrass équivalente, puis envoyer ce point vers la courbe de Montgomery ou d'Edwards tordue cible au moyen de l'application 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 satisfaisant les 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 posons sgn0(y) == sgn0(u).

Exceptions : les cas exceptionnels pour u surviennent 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 exemptes d'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))    # can be precomputed
6. If sgn0(tv4) == 1, set tv4 = -tv4        # sgn0(tv4) MUST equal 0
7. tv5 = u * tv1 * tv3 * tv4
8. tv6 = -4 * g(Z) / (3 * Z^2 + 4 * A)      # can be precomputed
9.  x1 = -Z / 2 - tv5
10. x2 = -Z / 2 + tv5
11. x3 = Z + tv6 * (tv2^2 * tv3)^2
12. If is_square(g(x1)), set x = x1 and y = sqrt(g(x1))
13. Else If is_square(g(x2)), set x = x2 and y = sqrt(g(x2))
14. Else set x = x3 and y = sqrt(g(x3))
15. If sgn0(u) != sgn0(y), set y = -y
16. return (x, y)

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

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

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

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 satisfaisant les 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 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 posons 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 dépendant de Z. Les implémentations doivent détecter ce cas et poser x1 = B / (Z * A), ce qui garantit que g(x1) est un carré en vertu de 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.  If tv1 == 0, set 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.  If is_square(gx1), set x = x1 and y = sqrt(gx1)
8.  Else set x = x2 and y = sqrt(gx2)
9.  If sgn0(u) != sgn0(y), set y = -y
10. return (x, y)

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

6.6.3. SWU simplifiée pour AB == 0

Wahby et Boneh [WB19] montrent comment adapter l'application SWU simplifiée aux courbes de Weierstrass ayant A == 0 ou B == 0, que l'application de la Section 6.6.2 ne prend pas en charge. (Le cas A == B == 0 est exclu car y^2 = x^3 n'est pas une courbe elliptique.)

Cette méthode s'applique à des courbes comme secp256k1 [SEC2] et aux courbes compatibles avec les couplages (pairing-friendly) de la famille Barreto-Lynn-Scott [BLS03], de la famille Barreto-Naehrig [BN05] et d'autres familles.

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

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

qui soit isogène à E et vérifie A' != 0 et B' != 0. (Voir [WB19], Annexe A, pour une manière de trouver E' à l'aide de [SAGE].) Cette isogénie définit une application iso_map(x', y') donnée par une paire de fonctions rationnelles. iso_map prend en entrée un point de E' et produit en sortie un point de E.

Une fois E' et iso_map identifiées, cette application fonctionne comme suit : sur l'entrée u, appliquer d'abord l'application SWU simplifiée pour obtenir un point de E', puis appliquer l'application d'isogénie à ce point pour obtenir un point de E.

Notons que iso_map est un homomorphisme de groupes, ce qui signifie que l'addition de points commute avec iso_map. Ainsi, lors de l'utilisation de cette application dans la construction hash_to_curve décrite à la Section 3, on peut réaliser une petite optimisation en envoyant d'abord u0 et u1 vers E', en additionnant 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 l'application d'isogénie iso_map de E' vers E.

Fonctions auxiliaires :

• map_to_curve_simple_swu est l'application de la Section 6.6.2 vers E'

• iso_map est l'application d'isogénie de E' vers E

Signe de y : pour cette application, le signe est déterminé par map_to_curve_simple_swu. Aucun ajustement de signe supplémentaire n'est nécessaire.

Exceptions : map_to_curve_simple_swu traite ses propres cas exceptionnels. Les cas exceptionnels de iso_map sont les entrées qui font s'annuler le dénominateur de l'une ou l'autre fonction rationnelle ; de tels cas DOIVENT renvoyer le point neutre (identité) de E.

Opérations :

1. (x', y') = map_to_curve_simple_swu(u)    # (x', y') is on E'
2.   (x, y) = iso_map(x', y')               # (x, y) is on E
3. return (x, y)

Voir [hash2curve-repo] ou la Section 4.3 de [WB19] pour les détails d'implémentation de l'application d'isogénie.

6.7. Applications pour les courbes de Montgomery

L'application définie 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 une application qui s'applique à toute courbe possédant 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 et 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 : cette application 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 poser x1 = -(J / K). Notons que cela ne peut se produire que lorsque q = 3 (mod 4).

Opérations :

1.  x1 = -(J / K) * inv0(1 + Z * u^2)
2.  If x1 == 0, set 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.  If is_square(gx1), set x = x1, y = sqrt(gx1) with sgn0(y) == 1.
7.  Else set x = x2, y = sqrt(gx2) with sgn0(y) == 0.
8.   s = x * K
9.   t = y * K
10. return (s, t)

L'Annexe F.3 donne un exemple d'implémentation en ligne droite de cette application. 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. Applications 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) : toute courbe d'Edwards tordue est birationnellement équivalente à une courbe de Montgomery ([BBJLP08], Théorème 3.2). Cette équivalence fournit 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 de la courbe d'Edwards tordue au moyen d'une application rationnelle. Cette méthode de hachage vers une courbe d'Edwards tordue requiert donc d'identifier une courbe de Montgomery correspondante et une application rationnelle. Nous décrivons immédiatement ci-dessous comment identifier une telle courbe et une telle application.

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

Il existe deux façons de sélectionner une courbe de Montgomery et une application rationnelle à utiliser lors du hachage vers une courbe d'Edwards tordue donnée. La courbe de Montgomery et l'application rationnelle sélectionnées DOIVENT être spécifiées dans le cadre de la suite hash-to-curve 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 application rationnelle sont également normalisées, la forme de Montgomery et l'application rationnelle standard DEVRAIENT être utilisées afin de garantir la compatibilité avec les logiciels existants.

   Dans certains cas, par exemple edwards25519 [RFC7748], le signe de l'application rationnelle allant de la courbe d'Edwards tordue vers sa courbe de Montgomery correspondante n'est pas donné explicitement. Dans ce cas, le signe DOIT être fixé de telle sorte que l'application de l'application 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 application rationnelle DEVRAIENT également être spécifiés, et le signe de l'application rationnelle DEVRAIT être indiqué explicitement.

2. Lors du hachage vers une courbe d'Edwards tordue qui ne dispose pas d'une forme de Montgomery ou d'une application rationnelle normalisée, l'application donnée à 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 satisfaisant les exigences de la Section 6.8.1.

Fonctions auxiliaires :

• map_to_curve_elligator2 est l'application de la Section 6.7.1 vers la courbe M.

• rational_map est une fonction qui prend un point (s, t) de M et renvoie un point (v, w) de E. Cette application rationnelle devrait être choisie comme défini à la Section 6.8.1.

Signe de t (et de v) : pour cette application, le signe est déterminé par map_to_curve_elligator2. Aucun ajustement de signe supplémentaire n'est requis.

Exceptions : les exceptions de l'application Elligator 2 sont celles indiquées à la Section 6.7.1. Les exceptions de l'application rationnelle sont celles indiquées à la Section 6.8.1. Aucune autre exception n'est possible.

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

map_to_curve_elligator2_edwards(u)

Input: u, an element of F.
Output: (v, w), a point on E.

1. (s, t) = map_to_curve_elligator2(u)      # (s, t) is on M
2. (v, w) = rational_map(s, t)              # (v, w) is on E
3. return (v, w)