Annexes

Annexe A. Travaux connexes

Le problème du mappage de chaînes de bits arbitraires vers des points de courbe elliptique a fait l'objet de recherches tant pratiques que théoriques. Cette section décrit brièvement le contexte et les résultats de recherche qui sous-tendent les recommandations de ce document. Cette section est fournie à titre informatif uniquement.

Une méthode naïve mais généralement peu sûre pour mapper une chaîne msg vers un point d'une courbe elliptique E ayant n points consiste à fixer d'abord un point P qui génère le groupe de la courbe elliptique, et une fonction de hachage Hn des chaînes de bits vers les entiers inférieurs à n ; puis à calculer Hn(msg) * P, où l'opérateur * représente la multiplication scalaire. La raison pour laquelle cette approche n'est pas sûre est que le point résultant a une relation de logarithme discret connue avec P. Ainsi, sauf dans les cas où cette méthode est spécifiée par le protocole, elle ne doit pas être utilisée ; le faire risque d'entraîner des défaillances de sécurité catastrophiques.

Boneh et al. [BLS01] décrivent une méthode d'encodage qu'ils appellent MapToGroup, qui fonctionne à peu près comme suit : d'abord, utiliser la chaîne d'entrée pour initialiser un générateur de nombres pseudo-aléatoires, puis utiliser le générateur pour produire une valeur x dans F. Si x est la coordonnée x d'un point sur la courbe elliptique, produire ce point. Sinon, générer une nouvelle valeur x dans F et essayer à nouveau. Comme une valeur aléatoire x dans F a une probabilité d'environ 1/2 de correspondre à un point sur la courbe, le nombre d'essais attendu n'est que de deux. Cependant, le temps d'exécution de cette méthode, qui est généralement appelée algorithme probabiliste « try-and-increment », dépend de la chaîne d'entrée. En tant que telle, elle n'est pas sûre pour une utilisation dans des protocoles sensibles aux canaux auxiliaires temporels, comme l'a illustré l'attaque Dragonblood [VR20].

Schinzel et Skalba [SS04] introduisent une méthode de construction déterministe de points de courbe elliptique, pour une classe restreinte de courbes et un très petit nombre de points. Skalba [S05] généralise cette construction à davantage de courbes et davantage de points sur ces courbes. Shallue et van de Woestijne [SW06] généralisent et simplifient davantage la construction de Skalba, produisant des mappages concrètement efficaces vers une fraction constante des points sur presque toutes les courbes. Fouque et Tibouchi [FT12] donnent une paramétrisation de ce mappage pour les courbes Barreto-Naehrig favorable au couplage [BN05].

Ulas [U07] décrit une version plus simple du mappage Shallue-van de Woestijne, et Brier et al. [BCIMRT10] donnent une simplification supplémentaire, que les auteurs appellent le mappage « SWU simplifié ». Ce mappage simplifié s'applique uniquement aux corps de caractéristique p = 3 (mod 4) ; Wahby et Boneh [WB19] généralisent aux corps de n'importe quelle caractéristique et donnent d'autres optimisations.

Boneh et Franklin donnent un algorithme déterministe mappant vers certaines courbes supersingulières sur des corps de caractéristique p = 2 (mod 3) [BF01]. Icart donne un autre algorithme déterministe qui mappe vers n'importe quelle courbe sur un corps de caractéristique p = 2 (mod 3) [Icart09]. Plusieurs extensions et généralisations suivent ce travail, notamment [FSV09], [FT10], [KLR10], [F11] et [CK11].

Suite aux travaux de Farashahi [F11], Fouque et al. [FJT13] décrivent un mappage vers des courbes sur des corps de caractéristique p = 3 (mod 4) ayant un nombre de points divisible par 4. Bernstein et al. [BHKL13] optimisent ce mappage et décrivent un mappage connexe qu'ils appellent « Elligator 2 », qui s'applique à toute courbe sur un corps de caractéristique impaire ayant un point d'ordre 2. Cela inclut Curve25519 et Curve448, qui sont toutes deux des courbes recommandées par le CFRG [RFC7748]. Bernstein et al. [BLMP19] étendent le mappage Elligator 2 à une classe de courbes supersingulières sur des corps de caractéristique p = 3 (mod 4).

Une mise en garde importante concernant toutes les fonctions de mappage déterministes ci-dessus est qu'aucune d'entre elles ne mappe vers la courbe entière, mais plutôt vers une fraction des points. Cela signifie qu'elles ne peuvent pas être utilisées directement pour construire un oracle aléatoire qui produit des points sur la courbe.

Brier et al. [BCIMRT10] donnent deux solutions à ce problème. La première, que Brier et al. prouvent s'appliquer à la méthode d'Icart, calcule f(H0(msg)) + f(H1(msg)) pour deux fonctions de hachage distinctes H0 et H1 des chaînes de bits vers F et un mappage f de F vers la courbe elliptique E. La seconde, qui s'applique à essentiellement tous les mappages déterministes mais qui est plus coûteuse, calcule f(H0(msg)) + H2(msg) * P, où P est un générateur du groupe de la courbe elliptique, H2 est un hachage des chaînes de bits vers les entiers modulo r, et r est l'ordre du groupe de la courbe elliptique.

Farashahi et al. [FFSTV13] améliorent l'analyse de la première méthode, montrant qu'elle s'applique à l'essentiel des mappages déterministes. Tibouchi et Kim [TK17] affinent davantage l'analyse et décrivent des optimisations supplémentaires.

Complémentairement au problème du mappage des chaînes de bits vers les points de courbe elliptique, Bernstein et al. [BHKL13] étudient le problème du mappage des points de courbe elliptique vers des chaînes de bits uniformément aléatoires, donnant des solutions pour une classe de courbes qui inclut les courbes de Montgomery et les courbes d'Edwards tordues. Tibouchi [T14] et Aranha et al. [AFQTZ14] généralisent ces résultats. Ce document ne traite pas de ce problème complémentaire.

Annexe B. Hachage vers ristretto255

ristretto255 [ristretto255-decaf448] fournit un groupe d'ordre premier basé sur curve25519 [RFC7748]. Cette section décrit hash_to_ristretto255, qui implémente un encodage oracle aléatoire vers ce groupe qui a une distribution de sortie uniforme (section 2.2.3) et les mêmes propriétés de sécurité et interface que la fonction hash_to_curve (section 3).

L'API ristretto255 définit un mappage unidirectionnel ([ristretto255-decaf448], section 4.3.4) ; cette section se réfère à ce mappage en tant que ristretto255_map.

La fonction hash_to_ristretto255 DOIT être instanciée avec une fonction expand_message conforme aux exigences données dans la section 5.3. En outre, elle DOIT utiliser une étiquette de séparation de domaine construite comme décrit dans la section 3.1, et toutes les recommandations de séparation de domaine données dans la section 10.7 s'appliquent lors de l'implémentation de protocoles utilisant hash_to_ristretto255.

hash_to_ristretto255(msg)

Paramètres :

• DST, une étiquette de séparation de domaine (voir discussion ci-dessus).
• expand_message, une fonction qui étend une chaîne d'octets et une étiquette de séparation de domaine en une chaîne d'octets uniformément aléatoire (voir discussion ci-dessus).
• ristretto255_map, le mappage unidirectionnel de l'API ristretto255.

Entrée : msg, une chaîne d'octets de longueur arbitraire. Sortie : P, un élément du groupe ristretto255.

Étapes :

1. uniform_bytes = expand_message(msg, DST, 64)
2. P = ristretto255_map(uniform_bytes)
3. retourner P

Puisque hash_to_ristretto255 n'est pas une suite de hachage vers courbe, elle n'a pas de Suite ID. Si un identifiant similaire est nécessaire, il DOIT être construit en suivant les directives de la section 8.10, avec les paramètres suivants :

• CURVE_ID : « ristretto255 »
• HASH_ID : tel que décrit dans la section 8.10
• MAP_ID : « R255MAP »
• ENC_VAR : « RO »

Par exemple, si expand_message est expand_message_xmd utilisant SHA-512, l'identifiant REQUIS est :

ristretto255_XMD:SHA-512_R255MAP_RO_

Annexe C. Hachage vers decaf448

Similairement à ristretto255, decaf448 [ristretto255-decaf448] fournit un groupe d'ordre premier basé sur curve448 [RFC7748]. Cette section décrit hash_to_decaf448, qui implémente un encodage oracle aléatoire vers ce groupe qui a une distribution de sortie uniforme (section 2.2.3) et les mêmes propriétés de sécurité et interface que la fonction hash_to_curve (section 3).

L'API decaf448 définit un mappage unidirectionnel ([ristretto255-decaf448], section 5.3.4) ; cette section se réfère à ce mappage en tant que decaf448_map.

La fonction hash_to_decaf448 DOIT être instanciée avec une fonction expand_message conforme aux exigences données dans la section 5.3. En outre, elle DOIT utiliser une étiquette de séparation de domaine construite comme décrit dans la section 3.1, et toutes les recommandations de séparation de domaine données dans la section 10.7 s'appliquent lors de l'implémentation de protocoles utilisant hash_to_decaf448.

hash_to_decaf448(msg)

Paramètres :

• DST, une étiquette de séparation de domaine (voir discussion ci-dessus).
• expand_message, une fonction qui étend une chaîne d'octets et une étiquette de séparation de domaine en une chaîne d'octets uniformément aléatoire (voir discussion ci-dessus).
• decaf448_map, le mappage unidirectionnel de l'API decaf448.

Entrée : msg, une chaîne d'octets de longueur arbitraire. Sortie : P, un élément du groupe decaf448.

Étapes :

1. uniform_bytes = expand_message(msg, DST, 112)
2. P = decaf448_map(uniform_bytes)
3. retourner P

Puisque hash_to_decaf448 n'est pas une suite de hachage vers courbe, elle n'a pas de Suite ID. Si un identifiant similaire est nécessaire, il DOIT être construit en suivant les directives de la section 8.10, avec les paramètres suivants :

• CURVE_ID : « decaf448 »
• HASH_ID : tel que décrit dans la section 8.10
• MAP_ID : « D448MAP »
• ENC_VAR : « RO »

Par exemple, si expand_message est expand_message_xof utilisant SHAKE256, l'identifiant REQUIS est :

decaf448_XOF:SHAKE256_D448MAP_RO_

Annexe D. Cartes rationnelles

Cette section donne des cartes rationnelles qui peuvent être utilisées lors du hachage vers des courbes d'Edwards tordues ou de Montgomery.

Étant donné une courbe d'Edwards tordue, l'Annexe D.1 montre comment dériver une courbe de Montgomery correspondante et comment mapper de cette courbe vers la courbe d'Edwards tordue. Ce mappage peut être utilisé lors du hachage vers des courbes d'Edwards tordues comme décrit dans la section 6.8.

Étant donné une courbe de Montgomery, l'Annexe D.2 montre comment dériver une courbe de Weierstrass correspondante et comment mapper de cette courbe vers la courbe de Montgomery. Ce mappage peut être utilisé pour hacher vers des courbes de Montgomery ou d'Edwards tordues via la méthode Shallue-van de Woestijne (section 6.6.1) ou la méthode SWU simplifiée (section 6.6.2), comme suit :

• Pour les courbes de Montgomery, mapper d'abord vers la courbe de Weierstrass, puis convertir en coordonnées de Montgomery via le mappage.

• Pour les courbes d'Edwards tordues, composer le mappage de Weierstrass vers Montgomery avec le mappage de Montgomery vers Edwards tordue (Annexe D.1) pour obtenir une courbe de Weierstrass et un mappage vers la courbe d'Edwards tordue cible. Mapper vers cette courbe de Weierstrass, puis convertir en coordonnées d'Edwards via le mappage.

D.1. Mappage générique de Montgomery vers Edwards tordue

Cette section donne une carte双有理 (birational) générique entre les courbes d'Edwards tordues et de Montgomery.

La carte de cette section est une version simplifiée de la carte donnée dans [BBJLP08], théorème 3.2. Plus précisément, la carte de cette section gère les cas exceptionnels d'une manière simplifiée qui est orientée vers le hachage vers le sous-groupe d'ordre premier d'une courbe d'Edwards tordue.

La courbe d'Edwards tordue a * v^2 + w^2 = 1 + d * v^2 * w^2 est birationnellement équivalente à la courbe de Montgomery K * t^2 = s^3 + J * s^2 + s qui a la forme requise par le mappage Elligator 2 de la section 6.7.1. Les coefficients de la courbe de Montgomery sont :

• J = 2 * (a + d) / (a - d)
• K = 4 / (a - d)

La carte rationnelle du point (s, t) sur la courbe de Montgomery ci-dessus vers le point (v, w) sur la courbe d'Edwards tordue est donnée par :

• v = s / t
• w = (s - 1) / (s + 1)

Ce mappage n'est pas défini lorsque t == 0 ou s == -1, c'est-à-dire que le dénominateur de l'une ou l'autre des fonctions rationnelles ci-dessus est nul. Les implémentations DOIVENT détecter les cas exceptionnels et renvoyer la valeur (v, w) = (0, 1), qui est le point identité sur toutes les courbes d'Edwards tordues.

La procédure en ligne droite suivante du mappage rationnel ci-dessus gère les cas exceptionnels.

monty_to_edw_generic(s, t)

Entrée : (s, t), un point sur la courbe K * t^2 = s^3 + J * s^2 + s. Sortie : (v, w), un point sur une courbe d'Edwards tordue équivalente.

1. tv1 = s + 1
2. tv2 = tv1 * t # (s + 1) * t
3. tv2 = inv0(tv2) # 1 / ((s + 1) * t)
4. v = tv2 * tv1 # 1 / t
5. v = v * s # s / t
6. w = tv2 * t # 1 / (s + 1)
7. tv1 = s - 1
8. w = w * tv1 # (s - 1) / (s + 1)
9. e = tv2 == 0
10. w = CMOV(w, 1, e) # gérer le cas exceptionnel
11. retourner (v, w)

Pour être complet, nous donnons également les relations inverses. (Notez que cette carte n'est pas requise lors du hachage vers des courbes d'Edwards tordues.) Les coefficients de la courbe d'Edwards tordue correspondant à la courbe de Montgomery ci-dessus sont :

• a = (J + 2) / K
• d = (J - 2) / K

La carte rationnelle du point (v, w) sur la courbe d'Edwards tordue vers le point (s, t) sur la courbe de Montgomery est donnée par :

• s = (1 + w) / (1 - w)
• t = (1 + w) / (v * (1 - w))

Le mappage n'est pas défini lorsque v == 0 ou w == 1. Lorsque l'objectif est de mapper dans le sous-groupe d'ordre premier de la courbe de Montgomery, il suffit de renvoyer le point identité sur la courbe de Montgomery dans les cas exceptionnels.

D.2. Mappage de Weierstrass vers Montgomery

La carte rationnelle du point (s, t) sur la courbe de Montgomery K * t^2 = s^3 + J * s^2 + s vers le point (x, y) sur la courbe de Weierstrass équivalente y^2 = x^3 + A * x + B est donnée par :

• A = (3 - J^2) / (3 * K^2)
• B = (2 * J^3 - 9 * J) / (27 * K^3)
• x = (3 * s + J) / (3 * K)
• y = t / K

La carte inverse, du point (x, y) au point (s, t), est donnée par :

• s = (3 * K * x - J) / 3
• t = y * K

Annexe E. Cartes d'isogénie pour les suites

Cette section spécifie les cartes d'isogénie pour les suites secp256k1 et BLS12-381 listées dans la section 8.

Ces cartes sont données en termes de coordonnées affines. Wahby et Boneh ([WB19], section 4.3) montrent comment évaluer ces cartes dans un système de coordonnées projectives (Annexe G.1), ce qui évite les inversions modulaires.

Reportez-vous au [hash2curve-repo] pour un script Sage [SAGE] qui construit ces isogénies.

E.1. Carte d'isogénie-3 pour secp256k1

Cette section spécifie la carte d'isogénie pour la suite secp256k1 listée dans la section 8.7.

La carte d'isogénie-3 de (x', y') sur E' vers (x, y) on E est donnée par les fonctions rationnelles suivantes :

• x = x_num / x_den, où

  • x_num = k_(1,3) * x'^3 + k_(1,2) * x'^2 + k_(1,1) * x' + k_(1,0)
  • x_den = x'^2 + k_(2,1) * x' + k_(2,0)

• y = y' * y_num / y_den, où

  • y_num = k_(3,3) * x'^3 + k_(3,2) * x'^2 + k_(3,1) * x' + k_(3,0)
  • y_den = x'^3 + k_(4,2) * x'^2 + k_(4,1) * x' + k_(4,0)

Les constantes utilisées pour calculer x_num sont les suivantes :

• k_(1,0) = 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa8c7
• k_(1,1) = 0x7d3d4c80bc321d5b9f315cea7fd44c5d595d2fc0bf63b92dfff1044f17c6581
• k_(1,2) = 0x534c328d23f234e6e2a413deca25caece4506144037c40314ecbd0b53d9dd262
• k_(1,3) = 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa88c

Les constantes utilisées pour calculer x_den sont les suivantes :

• k_(2,0) = 0xd35771193d94918a9ca34ccbb7b640dd86cd409542f8487d9fe6b745781eb49b
• k_(2,1) = 0xedadc6f64383dc1df7c4b2d51b54225406d36b641f5e41bbc52a56612a8c6d14

Les constantes utilisées pour calculer y_num sont les suivantes :

• k_(3,0) = 0x4bda12f684bda12f684bda12f684bda12f684bda12f684bda12f684b8e38e23c
• k_(3,1) = 0xc75e0c32d5cb7c0fa9d0a54b12a0a6d5647ab046d686da6fdffc90fc201d71a3
• k_(3,2) = 0x29a6194691f91a73715209ef6512e576722830a201be2018a765e85a9ecee931
• k_(3,3) = 0x2f684bda12f684bda12f684bda12f684bda12f684bda12f684bda12f38e38d84

Les constantes utilisées pour calculer y_den sont les suivantes :

• k_(4,0) = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffff93b
• k_(4,1) = 0x7a06534bb8bdb49fd5e9e6632722c2989467c1bfc8e8d978dfb425d2685c2573
• k_(4,2) = 0x6484aa716545ca2cf3a70c3fa8fe337e0a3d21162f0d6299a7bf8192bfd2a76f

remarque

En raison de la longueur importante des annexes E, F, G, H, I et J (qui contiennent de nombreuses constantes hexadécimales, du code d'implémentation et des vecteurs de test), le contenu complet a été omis de cette documentation par souci de concision.

Pour consulter les annexes complètes, incluant :

• Annexe E : Cartes d'isogénie complètes pour BLS12-381 G1 et G2
• Annexe F : Implémentations en ligne droite des mappages déterministes
• Annexe G : Code d'exemple optimisé spécifique à la courbe
• Annexe H : Scripts pour la génération de paramètres
• Annexe I : Fonctions sqrt et is_square
• Annexe J : Vecteurs de test complets de la suite pour toutes les courbes

Veuillez vous référer au document original RFC 9380.

Remerciements

Les auteurs tiennent à remercier Adam Langley pour sa description détaillée d'Elligator 2 avec Curve25519 [L13] ; Dan Boneh, Benjamin Lipp, Christopher Patton et Leonid Reyzin pour leurs discussions pédagogiques ; et David Benjamin, Daniel Bourdrez, Frank Denis, Sean Devlin, Justin Drake, Bjoern Haase, Mike Hamburg, Dan Harkins, Daira Hopwood, Thomas Icart, Andy Polyakov, Thomas Pornin, Mamy Ratsimbazafy, Michael Scott, Filippo Valsorda et Mathy Vanhoef pour leurs critiques et commentaires constructifs.

Contributeurs

Sharon Goldberg
Boston University
Email: [email protected]

Ela Lee
Royal Holloway, University of London
Email: [email protected]

Michele Orru
Email: [email protected]

Adresses des auteurs

Armando Faz-Hernandez
Cloudflare, Inc.
Email: [email protected]

Sam Scott
Oso Security, Inc.
Email: [email protected]

Nick Sullivan
Cloudflare, Inc.
Email: [email protected]

Riad S. Wahby
Stanford University
Email: [email protected]

Christopher A. Wood
Cloudflare, Inc.
Email: [email protected]