Aller au contenu principal

Annexes (Appendices)

L'envoi de chaînes de bits arbitraires vers des points de courbes elliptiques a fait l'objet d'études tant pratiques que théoriques. Cette section décrit brièvement le contexte et les travaux de recherche qui sous-tendent les recommandations de ce document. Cette section n'a qu'une valeur informative.

Une méthode naïve mais généralement non sûre consiste à envoyer une chaîne msg vers un point d'une courbe elliptique E ayant n points comme suit : fixer d'abord un point P qui engendre le groupe de la courbe elliptique, ainsi qu'une fonction de hachage Hn allant des chaînes de bits vers les entiers inférieurs à n ; calculer ensuite Hn(msg) * P (où l'opérateur * désigne la multiplication scalaire). Cette méthode n'est pas sûre car il existe une relation de logarithme discret connue entre le point obtenu et P. Par conséquent, à moins qu'un protocole ne prescrive explicitement cette méthode, elle NE DOIT PAS être utilisée, sous peine d'engendrer des défaillances de sécurité catastrophiques.

Boneh et al. [BLS01] décrivent une méthode d'encodage qu'ils appellent MapToGroup et qui fonctionne approximativement comme suit : initialiser d'abord un générateur pseudo-aléatoire à partir de la chaîne d'entrée, puis générer avec ce générateur une valeur x de F. Si x est l'abscisse d'un point de la courbe elliptique, renvoyer ce point ; sinon, générer une nouvelle valeur x dans F et réessayer. Comme une valeur aléatoire x de F correspond à un point de la courbe avec une probabilité d'environ 1/2, le nombre d'essais attendu n'est que de deux. Toutefois, le temps d'exécution de cette méthode, généralement appelée algorithme « try-and-increment » probabiliste, dépend de la chaîne d'entrée. Son utilisation dans des protocoles sensibles aux canaux auxiliaires temporels n'est donc pas sûre : l'attaque Dragonblood [VR20] en est précisément un exemple.

Schinzel et Skalba [SS04] ont introduit une méthode de construction déterministe de points de courbes elliptiques, pour une classe restreinte de courbes et un très petit nombre de points. Skalba [S05] a généralisé cette construction à davantage de courbes et à davantage de points sur ces courbes. Shallue et van de Woestijne [SW06] ont encore généralisé et simplifié la construction de Skalba, obtenant ainsi une méthode concrète et efficace applicable à une fraction constante des points de presque n'importe quelle courbe. Fouque et Tibouchi [FT12] donnent un paramétrage de cette application pour les courbes pairing-friendly de Barreto-Naehrig [BN05].

Ulas [U07] décrit une version plus simple de l'application de Shallue-van de Woestijne, et Brier et al. [BCIMRT10] donnent une simplification supplémentaire que les auteurs appellent l'application « SWU simplifiée ». Cette application simplifiée ne s'applique qu'aux corps de caractéristique p = 3 (mod 4). Wahby et Boneh [WB19] la généralisent aux corps de caractéristique quelconque et donnent des optimisations supplémentaires.

Boneh et Franklin ont donné un algorithme déterministe envoyant vers certaines courbes supersingulières sur des corps de caractéristique p = 2 (mod 3) [BF01]. Icart a donné un autre algorithme déterministe envoyant vers n'importe quelle courbe sur un corps de caractéristique p = 2 (mod 3) [Icart09]. Plusieurs extensions et généralisations ont suivi, notamment [FSV09], [FT10], [KLR10], [F11] et [CK11].

À la suite des travaux de Farashahi [F11], Fouque et al. [FJT13] ont décrit une application vers des courbes dont le nombre de points est divisible par 4, sur des corps de caractéristique p = 3 (mod 4). Bernstein et al. [BHKL13] ont optimisé cette application et décrit une application apparentée qu'ils appellent « Elligator 2 », définie sur des corps de caractéristique impaire et applicable à toute courbe possédant un point d'ordre 2. Cela inclut Curve25519 et Curve448 [RFC7748], toutes deux courbes recommandées par le CFRG. Bernstein et al. [BLMP19] ont étendu l'application Elligator 2 à une classe de courbes supersingulières sur des corps de caractéristique p = 3 (mod 4).

Une réserve importante s'applique à toutes les fonctions d'application déterministes ci-dessus : aucune d'entre elles ne peut atteindre la totalité de la courbe, mais seulement une fraction des points. Cela signifie qu'elles ne peuvent pas être utilisées directement pour construire un oracle aléatoire produisant des points de la courbe.

Brier et al. [BCIMRT10] donnent deux solutions à ce problème. La première, dont Brier et al. ont prouvé qu'elle s'applique à la méthode d'Icart, consiste à calculer f(H0(msg)) + f(H1(msg)), pour deux fonctions de hachage distinctes H0 et H1 allant des chaînes de bits vers F, et pour une application f de F vers la courbe elliptique E. La seconde solution s'applique à presque toutes les applications déterministes, mais elle est plus coûteuse : elle consiste à calculer f(H0(msg)) + H2(msg) * P, où P est un générateur du groupe de la courbe elliptique, H2 est une fonction de hachage allant 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] ont amélioré l'analyse de la première méthode, montrant qu'elle s'applique à presque toutes les applications déterministes. Tibouchi et Kim [TK17] ont encore affiné l'analyse et décrivent des optimisations supplémentaires.

De manière complémentaire au problème consistant à envoyer des chaînes de bits vers des points de courbes elliptiques, Bernstein et al. [BHKL13] ont étudié le problème consistant à envoyer des points de courbes elliptiques vers des chaînes de bits uniformément aléatoires, et ont donné une solution pour une classe de courbes comprenant 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 (Hashing to ristretto255)​

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

L'API de ristretto255 définit une application à sens unique ([ristretto255-decaf448], Section 4.3.4). Cette section appelle cette application ristretto255_map.

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

hash_to_ristretto255(msg)

Parameters:
- DST, a domain separation tag (see discussion above).
- expand_message, a function that expands a byte string and
  domain separation tag into a uniformly random byte string
  (see discussion above).
- ristretto255_map, the one-way map of the ristretto255 API.

Input: msg, an arbitrary-length byte string.
Output: P, an element of the ristretto255 group.

Steps:
1. uniform_bytes = expand_message(msg, DST, 64)
2. P = ristretto255_map(uniform_bytes)
3. return P

Comme hash_to_ristretto255 n'est pas une suite hash-to-curve, elle n'a pas de Suite ID. Si un identifiant similaire est requis, il DOIT être construit en suivant les indications de la Section 8.10 avec les paramètres suivants :

  • CURVE_ID : "ristretto255"
  • HASH_ID : comme décrit à la Section 8.10
  • MAP_ID : "R255MAP"
  • ENC_VAR : "RO"

Par exemple, lorsque expand_message est expand_message_xmd utilisant SHA-512, l'identifiant REQUIS est le suivant :

ristretto255_XMD:SHA-512_R255MAP_RO_

Annexe C. Hachage vers decaf448 (Hashing to decaf448)​

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

L'API de decaf448 définit une application à sens unique ([ristretto255-decaf448], Section 5.3.4). Cette section appelle cette application decaf448_map.

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

hash_to_decaf448(msg)

Parameters:
- DST, a domain separation tag (see discussion above).
- expand_message, a function that expands a byte string and
  domain separation tag into a uniformly random byte string
  (see discussion above).
- decaf448_map, the one-way map of the decaf448 API.

Input: msg, an arbitrary-length byte string.
Output: P, an element of the decaf448 group.

Steps:
1. uniform_bytes = expand_message(msg, DST, 112)
2. P = decaf448_map(uniform_bytes)
3. return P

Comme hash_to_decaf448 n'est pas une suite hash-to-curve, elle n'a pas de Suite ID. Si un identifiant similaire est requis, il DOIT être construit en suivant les indications de la Section 8.10 avec les paramètres suivants :

  • CURVE_ID : "decaf448"
  • HASH_ID : comme décrit à la Section 8.10
  • MAP_ID : "D448MAP"
  • ENC_VAR : "RO"

Par exemple, lorsque expand_message est expand_message_xof utilisant SHAKE256, l'identifiant REQUIS est le suivant :

decaf448_XOF:SHAKE256_D448MAP_RO_

Annexe D. Applications rationnelles (Rational Maps)​

Cette section donne des applications rationnelles utilisables lors du hachage vers des courbes d'Edwards tordues ou des courbes de Montgomery.

Étant donné une courbe d'Edwards tordue, l'Annexe D.1 montre comment en dériver une courbe de Montgomery correspondante et comment envoyer cette courbe de Montgomery vers cette courbe d'Edwards tordue. Cette application peut être utilisée lors du hachage vers une courbe d'Edwards tordue comme décrit à la Section 6.8.

Étant donné une courbe de Montgomery, l'Annexe D.2 montre comment en dériver une courbe de Weierstrass correspondante et comment envoyer cette courbe de Weierstrass vers cette courbe de Montgomery. Cette application peut être utilisée pour hacher vers une courbe de Montgomery ou une courbe d'Edwards tordue au moyen de la méthode de Shallue-van de Woestijne (Section 6.6.1) ou de la méthode SWU simplifiée (Section 6.6.2), comme suit :

  • Pour une courbe de Montgomery, envoyer d'abord vers la courbe de Weierstrass, puis convertir en coordonnées de Montgomery au moyen de cette application.

  • Pour une courbe d'Edwards tordue, composer l'application de Weierstrass vers Montgomery avec l'application de Montgomery vers Edwards tordue (Annexe D.1), afin d'obtenir une application allant d'une courbe de Weierstrass vers la courbe d'Edwards tordue cible. Envoyer d'abord vers cette courbe de Weierstrass, puis convertir en coordonnées d'Edwards au moyen de cette application.

D.1. Application générique de Montgomery vers Edwards tordue (Generic Mapping from Montgomery to Twisted Edwards)​

Cette section donne une application birationnelle générique entre les courbes d'Edwards tordues et les courbes de Montgomery.

L'application de cette section est une version simplifiée de celle donnée au Théorème 3.2 de [BBJLP08]. Plus précisément, l'application de cette section traite les cas exceptionnels d'une manière simplifiée, adaptée au 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

cette dernière ayant la forme requise par l'application Elligator 2 de la Section 6.7.1. Les coefficients de la courbe de Montgomery sont les suivants :

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

L'application rationnelle allant d'un point (s, t) de la courbe de Montgomery ci-dessus vers un point (v, w) de la courbe d'Edwards tordue est donnée par

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

Cette application est indéfinie lorsque t == 0 ou s == -1, c'est-à-dire lorsque 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 l'élément neutre de toute courbe d'Edwards tordue.

L'implémentation en ligne droite suivante de l'application rationnelle ci-dessus traite ces cas exceptionnels.

monty_to_edw_generic(s, t)

Input: (s, t), a point on the curve K * t^2 = s^3 + J * s^2 + s.
Output: (v, w), a point on an equivalent twisted Edwards curve.

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)  # handle exceptional case
11. return (v, w)

Par souci d'exhaustivité, nous donnons également la relation inverse. (Notons que cette application n'est pas nécessaire lors du hachage vers une courbe d'Edwards tordue.) Les coefficients de la courbe d'Edwards tordue correspondant à la courbe de Montgomery ci-dessus sont les suivants :

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

L'application rationnelle allant d'un point (v, w) de la courbe d'Edwards tordue vers un point (s, t) de la courbe de Montgomery est donnée par

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

Cette application est indéfinie lorsque v == 0 ou w == 1. Lorsque l'objectif est d'envoyer vers le sous-groupe d'ordre premier de la courbe de Montgomery, il suffit de renvoyer l'élément neutre de la courbe de Montgomery dans les cas exceptionnels.

D.2. Application de Weierstrass vers Montgomery (Mapping from Weierstrass to Montgomery)​

L'application rationnelle allant d'un point (s, t) de la courbe de Montgomery

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

vers un point (x, y) de 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

L'application inverse, allant du point (x, y) vers le point (s, t), est donnée par

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

Cette application peut être utilisée pour appliquer la méthode de Shallue-van de Woestijne (Section 6.6.1) ou la méthode SWU simplifiée (Section 6.6.2) à une courbe de Montgomery.

Annexe E. Applications d'isogénie pour les suites (Isogeny Maps for Suites)​

Cette section spécifie les applications d'isogénie utilisées par les suites secp256k1 et BLS12-381 énumérées à la Section 8.

Ces applications sont données en coordonnées affines. Wahby et Boneh ([WB19], Section 4.3) montrent comment évaluer ces applications dans un système de coordonnées projectives (Annexe G.1), ce qui permet d'éviter les opérations d'inversion modulaire.

Voir [hash2curve-repo] pour les scripts Sage [SAGE] qui construisent ces applications d'isogénie.

E.1. Application de 3-isogénie pour secp256k1 (3-Isogeny Map for secp256k1)​

Cette section spécifie l'application d'isogénie utilisée par la suite secp256k1 énumérée à la Section 8.7.

L'application de 3-isogénie allant d'un point (x', y') de E' vers un point (x, y) de 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
À propos du contenu de l'Annexe E.2 et suivantes

Les annexes restantes à partir de l'Annexe E.2 (Annexes E.2, E.3, F, G, H, I, J et K) contiennent un grand nombre de constantes hexadécimales, de code d'implémentation en ligne droite, de scripts de génération de paramètres et de vecteurs de test. Il s'agit de contenu purement composé de code et de données : sa valeur de traduction est limitée, tandis que le risque d'introduire des erreurs lors de la transcription est très élevé. Afin de garantir l'exactitude, ce contenu n'est pas retranscrit ici ; les liens vers le texte original sont donnés directement :

Texte original complet : https://www.rfc-editor.org/rfc/rfc9380.html

Remerciements (Acknowledgements)​

Les auteurs remercient Adam Langley [L13] pour son exposé détaillé sur l'utilisation d'Elligator 2 avec Curve25519. Ils remercient également Dan Boneh, Benjamin Lipp, Christopher Patton et Leonid Reyzin pour leurs discussions utiles, ainsi que 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 relectures et retours précieux.

Contributeurs (Contributors)​

Sharon Goldberg Boston University Email: goldbe@cs.bu.edu

Ela Lee Royal Holloway, University of London Email: Ela.Lee.2010@live.rhul.ac.uk

Michele Orru Email: michele.orru@ens.fr

Adresses des auteurs (Authors' Addresses)​

Armando Faz-Hernandez Cloudflare, Inc. 101 Townsend St San Francisco, CA 94107 United States of America Email: armfazh@cloudflare.com

Sam Scott Oso Security, Inc. 335 Madison Ave New York, NY 10017 United States of America Email: sam.scott89@gmail.com

Nick Sullivan Cloudflare, Inc. 101 Townsend St San Francisco, CA 94107 United States of America Email: nicholas.sullivan@gmail.com

Riad S. Wahby Stanford University Email: rsw@cs.stanford.edu

Christopher A. Wood Cloudflare, Inc. 101 Townsend St San Francisco, CA 94107 United States of America Email: caw@heapingbits.net

Dernière mise à jour le