Aller au contenu principal

8. Suites pour le hachage

Cette section liste les suites recommandées pour le hachage vers des courbes elliptiques standard.

Une suite de hachage vers courbe spécifie entièrement la procédure de hachage de chaînes d'octets vers des points d'un groupe de courbe elliptique spécifique. La section 8.1 décrit comment implémenter une suite. Les applications qui nécessitent le hachage vers une courbe elliptique devraient utiliser soit une suite existante, soit une nouvelle suite spécifiée comme décrit dans la section 8.9.

Toutes les applications utilisant une suite de hachage vers courbe DOIVENT choisir une étiquette de séparation de domaine (DST) conformément aux directives de la section 3.1. En outre, les applications dont la sécurité nécessite un oracle aléatoire renvoyant des points aléatoires uniformes sur la courbe cible DOIVENT utiliser une suite dont le type d'encodage est hash_to_curve ; voir la section 3 et immédiatement ci-dessous pour plus d'informations.

Une suite de hachage vers courbe comprend les paramètres suivants :

  • Suite ID : un nom court utilisé pour se référer à une suite donnée. La section 8.10 traite des conventions de nommage des ID de suite.

  • Type d'encodage : soit uniforme (hash_to_curve), soit non uniforme (encode_to_curve). Voir la section 3 pour les définitions 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é cible de la suite en bits. (Voir la section 10.8 pour plus de détails.)

  • L : le paramètre de longueur pour hash_to_field (section 5).

  • expand_message : l'une des variantes spécifiées dans la section 5.3 plus tous les paramètres requis pour la variante spécifiée (par exemple, H, la fonction de hachage sous-jacente).

  • f : une fonction de mappage de la section 6.

  • h_eff : le paramètre scalaire pour clear_cofactor (section 7).

En plus des paramètres ci-dessus, le mappage f peut nécessiter 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 instanciant des protocoles cryptographiques dont l'analyse de sécurité repose sur un oracle aléatoire qui produit des points avec une distribution uniforme ne DOIVENT PAS utiliser un encodage non uniforme. De plus, les applications qui utilisent un encodage non uniforme DEVRAIENT analyser soigneusement les implications de sécurité de la non-uniformité. Lorsque l'encodage requis n'est pas clair, les applications DEVRAIENT utiliser un encodage uniforme pour la sécurité.

ESuitesSection
NIST P-256P256_XMD:SHA-256_SSWU_RO_
P256_XMD:SHA-256_SSWU_NU_		8.2
NIST P-384P384_XMD:SHA-384_SSWU_RO_
P384_XMD:SHA-384_SSWU_NU_		8.3
NIST P-521P521_XMD:SHA-512_SSWU_RO_
P521_XMD:SHA-512_SSWU_NU_		8.4
curve25519curve25519_XMD:SHA-512_ELL2_RO_
curve25519_XMD:SHA-512_ELL2_NU_		8.5
edwards25519edwards25519_XMD:SHA-512_ELL2_RO_
edwards25519_XMD:SHA-512_ELL2_NU_		8.5
curve448curve448_XOF:SHAKE256_ELL2_RO_
curve448_XOF:SHAKE256_ELL2_NU_		8.6
edwards448edwards448_XOF:SHAKE256_ELL2_RO_
edwards448_XOF:SHAKE256_ELL2_NU_		8.6
secp256k1secp256k1_XMD:SHA-256_SSWU_RO_
secp256k1_XMD:SHA-256_SSWU_NU_		8.7
BLS12-381 G1BLS12381G1_XMD:SHA-256_SSWU_RO_
BLS12381G1_XMD:SHA-256_SSWU_NU_		8.8
BLS12-381 G2BLS12381G2_XMD:SHA-256_SSWU_RO_
BLS12381G2_XMD:SHA-256_SSWU_NU_		8.8

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

8.1. Implémentation d'une suite de hachage vers courbe​

Une suite de hachage vers courbe nécessite les fonctions suivantes. Notez que certaines d'entre elles nécessitent des fonctions utilitaires de la section 4.

  1. 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. Opérations sur les points de courbe elliptique pour la courbe 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 expand_message (section 5.3) et toute fonction de hachage ou XOF constituante.

  4. La fonction de mappage spécifiée par la suite ; voir la sous-section correspondante de la section 6.

  5. Une fonction d'effacement du cofacteur ; voir la section 7. Celle-ci peut être implémentée sous forme de multiplication scalaire par h_eff ou sous forme d'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 = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
  • 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_, sauf que le type d'encodage est encode_to_curve (section 3).

Un exemple d'implémentation optimisée du mappage SWU simplifié vers P-256 est donné dans 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 = 0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef
  • 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_, sauf que le type d'encodage est encode_to_curve (section 3).

Un exemple d'implémentation optimisée du mappage SWU simplifié vers P-384 est donné dans 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 = 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00
  • 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_, sauf que le type d'encodage est encode_to_curve (section 3).

Un exemple d'implémentation optimisée du mappage SWU simplifié vers P-521 est donné dans l'Annexe F.2.

8.5. Suites pour curve25519 et edwards25519​

Cette section définit les suites cryptographiques pour curve25519 et edwards25519 [RFC7748]. Notez que ces suites cryptographiques ne DOIVENT PAS être utilisées lors du hachage vers ristretto255 [ristretto255-decaf448]. Voir l'Annexe B pour plus d'informations sur la façon 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_, sauf pour les paramètres suivants :

  • E : a * v^2 + w^2 = 1 + d * v^2 * w^2, où
    • a = -1
    • d = 0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca135978a3
  • f : Méthode Elligator 2 pour Edwards tordue (section 6.8.2)
  • M : curve25519, définie dans [RFC7748], section 4.1
  • rational_map : les cartes双有理 (birational) définies dans [RFC7748], section 4.1

curve25519_XMD:SHA-512_ELL2_NU_ est identique à curve25519_XMD:SHA-512_ELL2_RO_, sauf 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_, sauf que le type d'encodage est encode_to_curve (section 3).

Des exemples d'implémentations optimisées des mappages ci-dessus sont donnés dans 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]. Notez que ces suites cryptographiques ne DOIVENT PAS être utilisées lors du hachage vers decaf448 [ristretto255-decaf448]. Voir l'Annexe C pour plus d'informations sur la façon 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_, sauf pour les 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 Edwards tordue (section 6.8.2)
  • M : curve448, définie dans [RFC7748], section 4.2
  • rational_map : la carte d'isogénie-4 définie dans [RFC7748], section 4.2

curve448_XOF:SHAKE256_ELL2_NU_ est identique à curve448_XOF:SHAKE256_ELL2_RO_, sauf que le type d'encodage est encode_to_curve (section 3).

edwards448_XOF:SHAKE256_ELL2_NU_ est identique à edwards448_XOF:SHAKE256_ELL2_RO_, sauf que le type d'encodage est encode_to_curve (section 3).

Des exemples d'implémentations optimisées des mappages ci-dessus sont donnés dans 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é pour AB == 0 (section 6.6.3)
  • Z : -11
  • E' : y'^2 = x'^3 + A' * x' + B', où
    • A' : 0x3f8731abdd661adca08a5558f0f5d272e953d363cb6f0e5d405447c01a444533
    • B' : 1771
  • iso_map : la carte d'isogénie-3 de E' vers E donnée dans l'Annexe E.1
  • h_eff : 1

secp256k1_XMD:SHA-256_SSWU_NU_ est identique à secp256k1_XMD:SHA-256_SSWU_RO_, sauf que le type d'encodage est encode_to_curve (section 3).

Un exemple d'implémentation optimisée du mappage SWU simplifié vers la courbe E' isogène à secp256k1 est donné dans 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 : 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
  • m : 1
  • k : 128
  • expand_message : expand_message_xmd (section 5.3.1)
  • H : SHA-256
  • L : 64
  • f : SWU simplifié pour AB == 0 (section 6.6.3)
  • Z : 11
  • E' : y'^2 = x'^3 + A' * x' + B', où
    • A' = 0x144698a3b8e9433d693a02c96d4982b0ea985383ee66a8d8e8981aefd881ac98936f8da0e0f97f5cf428082d584c1d
    • B' = 0x12e2908d11688030018b12e8753eee3b2016c1f0f24f4070a0b9c14fcef35ef55a23215a316ceaa5d1cc48e98e172be0
  • iso_map : la carte d'isogénie-11 de E' vers E donnée dans l'Annexe E.2
  • h_eff : 0xd201000000010001

BLS12381G1_XMD:SHA-256_SSWU_NU_ est identique à BLS12381G1_XMD:SHA-256_SSWU_RO_, sauf que le type d'encodage est encode_to_curve (section 3).

Notez que les valeurs h_eff pour ces suites sont choisies pour leur compatibilité avec la méthode d'effacement rapide du cofacteur décrite par Scott ([WB19], section 5).

Un exemple d'implémentation optimisée du mappage SWU simplifié vers la courbe E' isogène à BLS12-381 G1 est donné dans 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 : 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
    • m : 2
    • (1, I) est la base pour 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é 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 : la carte d'isogénie de E' vers E donnée dans l'Annexe E.3
  • h_eff : 0xbc69f08f2ee75b3584c6a0ea91b352888e2a8e9145ad7689986ff031508ffe1329c2f178731db956d82bf015d1212b02ec0ec69d7477c1ae954cbc06689f6a359894c0adebbf6b4e8020005aaa95551

BLS12381G2_XMD:SHA-256_SSWU_NU_ est identique à BLS12381G2_XMD:SHA-256_SSWU_RO_, sauf que le type d'encodage est encode_to_curve (section 3).

Notez que les valeurs h_eff pour ces suites sont choisies pour leur compatibilité avec la méthode d'effacement rapide du cofacteur décrite par Budroni et Pintore ([BP17], section 4.1) et sont résumées dans l'Annexe G.3.

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

8.9. Définition d'une nouvelle suite de hachage vers courbe​

Pour les courbes elliptiques non listées ailleurs dans la section 8, une nouvelle suite de hachage vers courbe 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é cible de 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 dans la section 5.

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

  6. Choisir un mappage en suivant les directives de la section 6.1, et sélectionner tous les paramètres requis pour ce mappage.

  7. Choisir h_eff comme étant soit le cofacteur de E ou, si une méthode d'effacement rapide du cofacteur doit être utilisée, une valeur appropriée à cette méthode comme discuté dans la section 7.

  8. Construire un Suite ID en suivant les directives de la section 8.10.

8.10. Conventions de nommage des ID de suite​

Les Suite IDs 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 entre 0x21 et 0x7E (inclus), sauf que le trait de soulignement (underscore, c'est-à-dire 0x5F) n'est pas autorisé.

Comme indiqué ci-dessus, chaque champ (y compris le dernier) est suivi d'un trait de soulignement (« _ », ASCII 0x5F). Cela aide à garantir que les Suite IDs sont exempts de préfixes. Les Suite IDs DOIVENT inclure le trait de soulignement final et ne DOIVENT PAS inclure de caractères après le trait de soulignement final.

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

  • CURVE_ID : une représentation lisible par l'homme de la courbe elliptique cible.

  • HASH_ID : une représentation lisible par l'homme 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 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 l'homme pour la primitive de hachage sous-jacente. À titre d'exemple :

    1. Pour expand_message_xof (section 5.3.2) avec SHAKE128, HASH_ID est « XOF:SHAKE128 ».
    2. Pour expand_message_xmd (section 5.3.1) avec SHA3-256, HASH_ID est « XMD:SHA3-256 ».

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

  • MAP_ID : une représentation lisible par l'homme de la fonction map_to_curve telle que définie dans la section 6. Celles-ci sont définies comme suit :

    • « SVDW » pour Shallue et van de Woestijne (section 6.6.1).
    • « SSWU » pour SWU simplifié (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 être utilisé pour encoder d'autres informations utilisées pour identifier des variantes, par exemple un numéro de version. La méthode RECOMMANDÉE pour ce faire est d'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é pour indiquer une variante de cette suite.

Dernière mise à jour le