Aller au contenu principal

8. Suites pour le hachage

  1. Suites pour le hachage

Cette section énumère les suites recommandées pour le hachage vers les courbes elliptiques standard.

Une suite hash-to-curve spécifie intégralement la procédure de hachage de chaînes d'octets vers des points d'un groupe de courbe elliptique donné. La Section 8.1 décrit comment implémenter une suite. Les applications qui requièrent un hachage vers une courbe elliptique devraient utiliser soit une suite existante, soit une nouvelle suite spécifiée comme décrit à la Section 8.9.

Toutes les applications utilisant une suite hash-to-curve DOIVENT choisir une étiquette de séparation de domaine (DST) conformément aux recommandations de la Section 3.1. En outre, les applications dont la sécurité requiert un oracle aléatoire renvoyant des points uniformément aléatoires sur la courbe cible DOIVENT utiliser une suite dont le type d'encodage est hash_to_curve ; voir la Section 3 et le texte ci-dessous pour plus d'informations.

Une suite hash-to-curve comprend les paramètres suivants :

  • Suite ID, un nom court utilisé pour désigner une suite donnée. La Section 8.10 traite des conventions de nommage des Suite ID.

  • type d'encodage, soit uniforme (hash_to_curve), soit non uniforme (encode_to_curve). Voir la Section 3 pour la définition de ces types d'encodage.

  • E, la courbe elliptique cible sur un corps F.

  • p, la caractéristique du corps F.

  • m, le degré d'extension du corps F. Si m > 1, la suite DOIT également spécifier la base polynomiale utilisée pour représenter les éléments du corps d'extension.

  • k, le niveau de sécurité visé par la suite, en bits. (Voir la Section 10.8 pour une discussion.)

  • L, le paramètre de longueur pour hash_to_field (Section 5).

  • expand_message, l'une des variantes spécifiées à la Section 5.3, ainsi que tous les paramètres requis par la variante spécifiée (par exemple, H, la fonction de hachage sous-jacente).

  • f, une fonction d'application issue de la Section 6.

  • h_eff, le paramètre scalaire pour clear_cofactor (Section 7).

Outre les paramètres ci-dessus, l'application f peut requérir des paramètres supplémentaires Z, M, rational_map, E' ou iso_map. Le cas échéant, ceux-ci DOIVENT être spécifiés.

Le tableau ci-dessous énumère les suites RECOMMANDÉES pour certaines courbes elliptiques. Les paramètres correspondants sont donnés dans les sous-sections suivantes. Les applications qui instancient des protocoles cryptographiques dont l'analyse de sécurité repose sur un oracle aléatoire produisant des points selon une distribution uniforme NE DOIVENT PAS utiliser d'encodage non uniforme. De plus, les applications qui utilisent un encodage non uniforme DEVRAIENT analyser soigneusement les implications de sécurité de cette non-uniformité. Lorsque l'encodage requis n'est pas clair, les applications DEVRAIENT utiliser un encodage uniforme par sécurité.

  +==============+===================================+=========+
  | E            | Suites                            | Section |
  +==============+===================================+=========+
  | NIST P-256   | P256_XMD:SHA-256_SSWU_RO_         | 8.2     |
  |              | P256_XMD:SHA-256_SSWU_NU_         |         |
  +--------------+-----------------------------------+---------+
  | NIST P-384   | P384_XMD:SHA-384_SSWU_RO_         | 8.3     |
  |              | P384_XMD:SHA-384_SSWU_NU_         |         |
  +--------------+-----------------------------------+---------+
  | NIST P-521   | P521_XMD:SHA-512_SSWU_RO_         | 8.4     |
  |              | P521_XMD:SHA-512_SSWU_NU_         |         |
  +--------------+-----------------------------------+---------+
  | curve25519   | curve25519_XMD:SHA-512_ELL2_RO_   | 8.5     |
  |              | curve25519_XMD:SHA-512_ELL2_NU_   |         |
  +--------------+-----------------------------------+---------+
  | edwards25519 | edwards25519_XMD:SHA-512_ELL2_RO_ | 8.5     |
  |              | edwards25519_XMD:SHA-512_ELL2_NU_ |         |
  +--------------+-----------------------------------+---------+
  | curve448     | curve448_XOF:SHAKE256_ELL2_RO_    | 8.6     |
  |              | curve448_XOF:SHAKE256_ELL2_NU_    |         |
  +--------------+-----------------------------------+---------+
  | edwards448   | edwards448_XOF:SHAKE256_ELL2_RO_  | 8.6     |
  |              | edwards448_XOF:SHAKE256_ELL2_NU_  |         |
  +--------------+-----------------------------------+---------+
  | secp256k1    | secp256k1_XMD:SHA-256_SSWU_RO_    | 8.7     |
  |              | secp256k1_XMD:SHA-256_SSWU_NU_    |         |
  +--------------+-----------------------------------+---------+
  | BLS12-381 G1 | BLS12381G1_XMD:SHA-256_SSWU_RO_   | 8.8     |
  |              | BLS12381G1_XMD:SHA-256_SSWU_NU_   |         |
  +--------------+-----------------------------------+---------+
  | BLS12-381 G2 | BLS12381G2_XMD:SHA-256_SSWU_RO_   | 8.8     |
  |              | BLS12381G2_XMD:SHA-256_SSWU_NU_   |         |
  +--------------+-----------------------------------+---------+

    Tableau 2 : Suites pour le hachage vers des courbes elliptiques.

8.1. Implémentation d'une suite hash-to-curve

Une suite hash-to-curve requiert les fonctions suivantes. Notons que certaines d'entre elles nécessitent les fonctions utilitaires de la Section 4.

  1. Les opérations arithmétiques du corps de base pour la courbe elliptique cible, par exemple l'addition, la multiplication et la racine carrée.

  2. Les opérations sur les points de la courbe elliptique cible, par exemple l'addition de points et la multiplication scalaire.

  3. La fonction hash_to_field ; voir la Section 5. Cela inclut la variante de expand_message (Section 5.3) ainsi que toute fonction de hachage ou XOF constitutive.

  4. La fonction d'application spécifiée par la suite ; voir la sous-section correspondante de la Section 6.

  5. Une fonction d'élimination du cofacteur ; voir la Section 7. Celle-ci peut être implémentée par multiplication scalaire par h_eff ou par une méthode équivalente plus rapide.

  6. La fonction d'encodage souhaitée ; voir la Section 3. Il s'agit soit de hash_to_curve, soit de encode_to_curve.

8.2. Suites pour NIST P-256

Cette section définit les suites cryptographiques pour la courbe elliptique NIST P-256 [FIPS186-4].

P256_XMD:SHA-256_SSWU_RO_ est définie comme suit :

  • type d'encodage : hash_to_curve (Section 3)

  • E : y^2 = x^3 + A * x + B, où

    • A = -3

    • B = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e2 7d2604b

  • p : 2^256 - 2^224 + 2^192 + 2^96 - 1

  • m : 1

  • k : 128

  • expand_message : expand_message_xmd (Section 5.3.1)

  • H : SHA-256

  • L : 48

  • f : méthode SWU simplifiée (Section 6.6.2)

  • Z : -10

  • h_eff : 1

P256_XMD:SHA-256_SSWU_NU_ est identique à P256_XMD:SHA-256_SSWU_RO_, à ceci près que le type d'encodage est encode_to_curve (Section 3).

Un exemple d'implémentation optimisée de l'application SWU simplifiée vers P-256 est donné à l'Annexe F.2.

8.3. Suites pour NIST P-384

Cette section définit les suites cryptographiques pour la courbe elliptique NIST P-384 [FIPS186-4].

P384_XMD:SHA-384_SSWU_RO_ est définie comme suit :

  • type d'encodage : hash_to_curve (Section 3)

  • E : y^2 = x^3 + A * x + B, où

    • A = -3

    • B = 0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5 013875ac656398d8a2ed19d2a85c8edd3ec2aef

  • p : 2^384 - 2^128 - 2^96 + 2^32 - 1

  • m : 1

  • k : 192

  • expand_message : expand_message_xmd (Section 5.3.1)

  • H : SHA-384

  • L : 72

  • f : méthode SWU simplifiée (Section 6.6.2)

  • Z : -12

  • h_eff : 1

P384_XMD:SHA-384_SSWU_NU_ est identique à P384_XMD:SHA-384_SSWU_RO_, à ceci près que le type d'encodage est encode_to_curve (Section 3).

Un exemple d'implémentation optimisée de l'application SWU simplifiée vers P-384 est donné à l'Annexe F.2.

8.4. Suites pour NIST P-521

Cette section définit les suites cryptographiques pour la courbe elliptique NIST P-521 [FIPS186-4].

P521_XMD:SHA-512_SSWU_RO_ est définie comme suit :

  • type d'encodage : hash_to_curve (Section 3)

  • E : y^2 = x^3 + A * x + B, où

    • A = -3

    • B = 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b4899 18ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451f d46b503f00

  • p : 2^521 - 1

  • m : 1

  • k : 256

  • expand_message : expand_message_xmd (Section 5.3.1)

  • H : SHA-512

  • L : 98

  • f : méthode SWU simplifiée (Section 6.6.2)

  • Z : -4

  • h_eff : 1

P521_XMD:SHA-512_SSWU_NU_ est identique à P521_XMD:SHA-512_SSWU_RO_, à ceci près que le type d'encodage est encode_to_curve (Section 3).

Un exemple d'implémentation optimisée de l'application SWU simplifiée vers P-521 est donné à l'Annexe F.2.

8.5. Suites pour curve25519 et edwards25519

Cette section définit les suites cryptographiques pour curve25519 et edwards25519 [RFC7748]. Notons que ces suites cryptographiques NE DOIVENT PAS être utilisées pour le hachage vers ristretto255 [ristretto255-decaf448]. Voir l'Annexe B pour des informations sur la manière de hacher vers ce groupe.

curve25519_XMD:SHA-512_ELL2_RO_ est définie comme suit :

  • type d'encodage : hash_to_curve (Section 3)

  • E : K * t^2 = s^3 + J * s^2 + s, où

    • J = 486662

    • K = 1

  • p : 2^255 - 19

  • m : 1

  • k : 128

  • expand_message : expand_message_xmd (Section 5.3.1)

  • H : SHA-512

  • L : 48

  • f : méthode Elligator 2 (Section 6.7.1)

  • Z : 2

  • h_eff : 8

edwards25519_XMD:SHA-512_ELL2_RO_ est identique à curve25519_XMD:SHA- 512_ELL2_RO_, à l'exception des paramètres suivants :

  • E : a * v^2 + w^2 = 1 + d * v^2 * w^2, où

    • a = -1

    • d = 0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca1 35978a3

  • f : méthode Elligator 2 pour courbes d'Edwards tordues (Section 6.8.2)

  • M : curve25519, définie dans [RFC7748], Section 4.1

  • rational_map : les applications birationnelles définies dans [RFC7748], Section 4.1

curve25519_XMD:SHA-512_ELL2_NU_ est identique à curve25519_XMD:SHA- 512_ELL2_RO_, à ceci près que le type d'encodage est encode_to_curve (Section 3).

edwards25519_XMD:SHA-512_ELL2_NU_ est identique à edwards25519_XMD:SHA-512_ELL2_RO_, à ceci près que le type d'encodage est encode_to_curve (Section 3).

Des exemples d'implémentations optimisées des applications ci-dessus sont donnés à l'Annexe G.2.1 et à l'Annexe G.2.2.

8.6. Suites pour curve448 et edwards448

Cette section définit les suites cryptographiques pour curve448 et edwards448 [RFC7748]. Notons que ces suites cryptographiques NE DOIVENT PAS être utilisées pour le hachage vers decaf448 [ristretto255-decaf448]. Voir l'Annexe C pour des informations sur la manière de hacher vers ce groupe.

curve448_XOF:SHAKE256_ELL2_RO_ est définie comme suit :

  • type d'encodage : hash_to_curve (Section 3)

  • E : K * t^2 = s^3 + J * s^2 + s, où

    • J = 156326

    • K = 1

  • p : 2^448 - 2^224 - 1

  • m : 1

  • k : 224

  • expand_message : expand_message_xof (Section 5.3.2)

  • H : SHAKE256

  • L : 84

  • f : méthode Elligator 2 (Section 6.7.1)

  • Z : -1

  • h_eff : 4

edwards448_XOF:SHAKE256_ELL2_RO_ est identique à curve448_XOF:SHAKE256_ELL2_RO_, à l'exception des paramètres suivants :

  • E : a * v^2 + w^2 = 1 + d * v^2 * w^2, où

    • a = 1

    • d = -39081

  • f : méthode Elligator 2 pour courbes d'Edwards tordues (Section 6.8.2)

  • M : curve448, définie dans [RFC7748], Section 4.2

  • rational_map : l'application de 4-isogénie définie dans [RFC7748], Section 4.2

curve448_XOF:SHAKE256_ELL2_NU_ est identique à curve448_XOF:SHAKE256_ELL2_RO_, à ceci près que le type d'encodage est encode_to_curve (Section 3).

edwards448_XOF:SHAKE256_ELL2_NU_ est identique à edwards448_XOF:SHAKE256_ELL2_RO_, à ceci près que le type d'encodage est encode_to_curve (Section 3).

Des exemples d'implémentations optimisées des applications ci-dessus sont donnés à l'Annexe G.2.3 et à l'Annexe G.2.4.

8.7. Suites pour secp256k1

Cette section définit les suites cryptographiques pour la courbe elliptique secp256k1 [SEC2].

secp256k1_XMD:SHA-256_SSWU_RO_ est définie comme suit :

  • type d'encodage : hash_to_curve (Section 3)

  • E : y^2 = x^3 + 7

  • p : 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1

  • m : 1

  • k : 128

  • expand_message : expand_message_xmd (Section 5.3.1)

  • H : SHA-256

  • L : 48

  • f : SWU simplifiée pour AB == 0 (Section 6.6.3)

  • Z : -11

  • E' : y'^2 = x'^3 + A' * x' + B', où

    • A' : 0x3f8731abdd661adca08a5558f0f5d272e953d363cb6f0e5d405447c01 a444533

    • B' : 1771

  • iso_map : l'application de 3-isogénie de E' vers E donnée à l'Annexe E.1

  • h_eff : 1

secp256k1_XMD:SHA-256_SSWU_NU_ est identique à secp256k1_XMD:SHA- 256_SSWU_RO_, à ceci près que le type d'encodage est encode_to_curve (Section 3).

Un exemple d'implémentation optimisée de l'application SWU simplifiée vers la courbe E' isogène à secp256k1 est donné à l'Annexe F.2.

8.8. Suites pour BLS12-381

Cette section définit les suites cryptographiques pour les groupes G1 et G2 de la courbe elliptique BLS12-381 [BLS12-381].

8.8.1. BLS12-381 G1

BLS12381G1_XMD:SHA-256_SSWU_RO_ est définie comme suit :

  • type d'encodage : hash_to_curve (Section 3)

  • E : y^2 = x^3 + 4

  • p : 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f 6241eabfffeb153ffffb9feffffffffaaab

  • m : 1

  • k : 128

  • expand_message : expand_message_xmd (Section 5.3.1)

  • H : SHA-256

  • L : 64

  • f : SWU simplifiée pour AB == 0 (Section 6.6.3)

  • Z : 11

  • E' : y'^2 = x'^3 + A' * x' + B', où

    • A' = 0x144698a3b8e9433d693a02c96d4982b0ea985383ee66a8d8e8981aef d881ac98936f8da0e0f97f5cf428082d584c1d

    • B' = 0x12e2908d11688030018b12e8753eee3b2016c1f0f24f4070a0b9c14f cef35ef55a23215a316ceaa5d1cc48e98e172be0

  • iso_map : l'application de 11-isogénie de E' vers E donnée à l'Annexe E.2

  • h_eff : 0xd201000000010001

BLS12381G1_XMD:SHA-256_SSWU_NU_ est identique à BLS12381G1_XMD:SHA- 256_SSWU_RO_, à ceci près que le type d'encodage est encode_to_curve (Section 3).

Notons que les valeurs de h_eff pour ces suites sont choisies pour assurer la compatibilité avec la méthode rapide d'élimination du cofacteur décrite par Scott ([WB19], Section 5).

Un exemple d'implémentation optimisée de l'application SWU simplifiée vers la courbe E' isogène à BLS12-381 G1 est donné à l'Annexe F.2.

8.8.2. BLS12-381 G2

BLS12381G2_XMD:SHA-256_SSWU_RO_ est définie comme suit :

  • type d'encodage : hash_to_curve (Section 3)

  • E : y^2 = x^3 + 4 * (1 + I)

  • le corps de base F est GF(p^m), où

    • p : 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6 b0f6241eabfffeb153ffffb9feffffffffaaab

    • m : 2

    • (1, I) est la base de F, où I^2 + 1 == 0 dans F

  • k : 128

  • expand_message : expand_message_xmd (Section 5.3.1)

  • H : SHA-256

  • L : 64

  • f : SWU simplifiée pour AB == 0 (Section 6.6.3)

  • Z : -(2 + I)

  • E' : y'^2 = x'^3 + A' * x' + B', où

    • A' = 240 * I

    • B' = 1012 * (1 + I)

  • iso_map : l'application d'isogénie de E' vers E donnée à l'Annexe E.3

  • h_eff : 0xbc69f08f2ee75b3584c6a0ea91b352888e2a8e9145ad7689986ff0315 08ffe1329c2f178731db956d82bf015d1212b02ec0ec69d7477c1ae954cbc06689 f6a359894c0adebbf6b4e8020005aaa95551

BLS12381G2_XMD:SHA-256_SSWU_NU_ est identique à BLS12381G2_XMD:SHA- 256_SSWU_RO_, à ceci près que le type d'encodage est encode_to_curve (Section 3).

Notons que les valeurs de h_eff pour ces suites sont choisies pour assurer la compatibilité avec la méthode rapide d'élimination du cofacteur décrite par Budroni et Pintore ([BP17], Section 4.1) et sont résumées à l'Annexe G.3.

Un exemple d'implémentation optimisée de l'application SWU simplifiée vers la courbe E' isogène à BLS12-381 G2 est donné à l'Annexe F.2.

8.9. Définition d'une nouvelle suite hash-to-curve

Pour les courbes elliptiques non listées ailleurs dans la Section 8, une nouvelle suite hash-to-curve peut être définie comme suit :

  1. E, F, p et m sont déterminés par la courbe elliptique et son corps de base.

  2. k est une borne supérieure du niveau de sécurité visé par la suite (Section 10.8). Un choix raisonnable de k est ceil(log2(r) / 2), où r est l'ordre du sous-groupe G de la courbe E (Section 2.1).

  3. Choisir le type d'encodage, soit hash_to_curve, soit encode_to_curve (Section 3).

  4. Calculer L comme décrit à la Section 5.

  5. Choisir une variante de expand_message à la Section 5.3, ainsi que toutes les primitives cryptographiques sous-jacentes (par exemple, une fonction de hachage H).

  6. Choisir une application en suivant les recommandations de la Section 6.1, et sélectionner tous les paramètres requis par cette application.

  7. Choisir h_eff égal soit au cofacteur de E, soit, si une méthode rapide d'élimination du cofacteur doit être utilisée, à une valeur appropriée à cette méthode, comme discuté à la Section 7.

  8. Construire un Suite ID en suivant les recommandations de la Section 8.10.

8.10. Conventions de nommage des Suite ID

Les Suite ID DOIVENT être construits comme suit :

CURVE_ID || "" || HASH_ID || "" || MAP_ID || "" || ENC_VAR || ""

Les champs CURVE_ID, HASH_ID, MAP_ID et ENC_VAR sont des chaînes encodées en ASCII d'au plus 64 caractères chacune. Les champs DOIVENT contenir uniquement des caractères ASCII compris entre 0x21 et 0x7E (inclus), à l'exception du tiret bas (c'est-à-dire 0x5F) qui n'est pas autorisé.

Comme indiqué ci-dessus, chaque champ (y compris le dernier) est suivi d'un tiret bas (« _ », ASCII 0x5F). Cela contribue à garantir que les Suite ID sont sans préfixe (prefix free). Les Suite ID DOIVENT inclure le tiret bas final et NE DOIVENT PAS inclure de caractère après ce tiret bas final.

Les champs des Suite ID DOIVENT être choisis comme suit :

  • CURVE_ID : une représentation lisible par un humain de la courbe elliptique cible.

  • HASH_ID : une représentation lisible par un humain de la fonction expand_message et de toutes les primitives de hachage sous-jacentes utilisées dans hash_to_field (Section 5). Ce champ DOIT être construit comme suit :

    EXP_TAG || ":" || HASH_NAME

    EXP_TAG indique la variante de expand_message :

    • « XMD » pour expand_message_xmd (Section 5.3.1).

    • « XOF » pour expand_message_xof (Section 5.3.2).

    HASH_NAME est un nom lisible par un humain désignant la primitive de hachage sous-jacente. À titre d'exemples :

    1. Pour expand_message_xof (Section 5.3.2) avec SHAKE128, HASH_ID vaut « XOF:SHAKE128 ».

    2. Pour expand_message_xmd (Section 5.3.1) avec SHA3-256, HASH_ID vaut « XMD:SHA3-256 ».

    Les suites qui utilisent une fonction hash_to_field alternative satisfaisant aux exigences de la Section 5.1 DOIVENT l'indiquer en ajoutant au champ HASH_ID une étiquette identifiant cette fonction, séparée par un deux-points (« : », ASCII 0x3A).

  • MAP_ID : une représentation lisible par un humain de la fonction map_to_curve telle que définie à la Section 6. Elles sont définies comme suit :

    • « SVDW » pour Shallue et van de Woestijne (Section 6.6.1).

    • « SSWU » pour SWU simplifiée (Sections 6.6.2 et 6.6.3).

    • « ELL2 » pour Elligator 2 (Sections 6.7.1 et 6.8.2).

  • ENC_VAR : une chaîne indiquant le type d'encodage et d'autres informations. Les deux premiers caractères de cette chaîne indiquent si la suite représente une opération hash_to_curve ou encode_to_curve (Section 3), comme suit :

    • Si ENC_VAR commence par « RO », la suite utilise hash_to_curve.

    • Si ENC_VAR commence par « NU », la suite utilise encode_to_curve.

    • ENC_VAR NE DOIT PAS commencer par une autre chaîne.

    ENC_VAR PEUT également servir à encoder d'autres informations utilisées pour identifier des variantes, par exemple un numéro de version. La façon RECOMMANDÉE de procéder consiste à ajouter un ou plusieurs sous-champs séparés par des deux-points. Par exemple, « RO:V02 » est une valeur ENC_VAR appropriée pour la deuxième version d'une suite d'encodage uniforme, tandis que « RO:V02:FOO01:BAR17 » pourrait être utilisée pour indiquer une variante de cette suite.

Dernière mise à jour le