Aller au contenu principal

3. Encodage de chaînes d'octets vers des courbes elliptiques

Cette section présente un cadre général et une interface pour l'encodage de chaînes d'octets vers des points sur une courbe elliptique. Les constructions de cette section reposent sur trois fonctions de base :

  • La fonction hash_to_field hache des chaînes d'octets de longueur arbitraire vers une liste d'un ou plusieurs éléments d'un corps fini F ; son implémentation est définie dans la section 5.

    hash_to_field(msg, count)

    Entrée :

    • msg, une chaîne d'octets contenant le message à hacher.
    • count, le nombre d'éléments de F à produire.

    Sortie :

    • (u_0, ..., u_(count - 1)), une liste d'éléments du corps.

  • La fonction map_to_curve calcule un point sur la courbe elliptique E à partir d'un élément du corps fini F sur lequel E est définie. La section 6 décrit les mappages pour une gamme de familles de courbes.

    map_to_curve(u)

    Entrée : u, un élément du corps F. Sortie : Q, un point sur la courbe elliptique E.

  • La fonction clear_cofactor envoie tout point sur la courbe E vers le sous-groupe G de E. La section 7 décrit les méthodes pour effectuer cette opération.

    clear_cofactor(Q)

    Entrée : Q, un point sur la courbe elliptique E. Sortie : P, un point dans G.

Les deux encodages (section 2.2.2) définis dans cette section ont la même interface et sont tous deux des encodages à oracle aléatoire (section 2.2.3). Les deux sont implémentés comme une composition des trois fonctions de base ci-dessus. La différence entre les deux est que leurs sorties sont échantillonnées à partir de distributions différentes :

  • encode_to_curve est un encodage non uniforme de chaînes d'octets vers des points dans G. C'est-à-dire que la distribution de sa sortie n'est pas uniformément aléatoire dans G : l'ensemble des sorties possibles de encode_to_curve n'est qu'une fraction des points dans G, et certains points de cet ensemble sont plus susceptibles d'être produits que d'autres. La section 10.4 donne une définition plus précise de la distribution de sortie de encode_to_curve.

    encode_to_curve(msg)

    Entrée : msg, une chaîne d'octets de longueur arbitraire. Sortie : P, un point dans G.

    Étapes :

    1. u = hash_to_field(msg, 1)
    2. Q = map_to_curve(u[0])
    3. P = clear_cofactor(Q)
    4. retourner P

  • hash_to_curve est un encodage uniforme de chaînes d'octets vers des points dans G. C'est-à-dire que la distribution de sa sortie est statistiquement proche de l'uniformité dans G.

    Cette fonction convient à la plupart des applications nécessitant un oracle aléatoire renvoyant des points dans G, lorsqu'elle est instanciée avec l'une des fonctions map_to_curve décrites dans la section 6. Voir la section 10.1 pour plus de détails.

    hash_to_curve(msg)

    Entrée : msg, une chaîne d'octets de longueur arbitraire. Sortie : P, un point dans G.

    Étapes :

    1. u = hash_to_field(msg, 2)
    2. Q0 = map_to_curve(u[0])
    3. Q1 = map_to_curve(u[1])
    4. R = Q0 + Q1 # Addition de points
    5. P = clear_cofactor(R)
    6. retourner P

Chaque suite de hachage vers courbe de la section 8 instancie l'une de ces fonctions d'encodage pour une courbe elliptique spécifique.

3.1. Exigences de séparation de domaine​

Toutes les utilisations des fonctions d'encodage définies dans ce document DOIVENT inclure une séparation de domaine (section 2.2.5) pour éviter d'interférer avec d'autres utilisations de fonctionnalités similaires.

Les applications qui instancient plusieurs instances indépendantes de hash_to_curve ou de encode_to_curve DOIVENT appliquer une séparation de domaine entre ces instances. Cette exigence s'applique à la fois dans le cas de plusieurs instances ciblant la même courbe et dans le cas de plusieurs instances ciblant des courbes différentes. (En effet, la primitive interne hash_to_field (section 5) nécessite une séparation de domaine pour garantir des sorties indépendantes.)

La séparation de domaine est appliquée à l'aide d'une étiquette de séparation de domaine (DST), qui est une chaîne d'octets construite selon les exigences suivantes :

  1. Les étiquettes DOIVENT être fournies en tant que paramètre DST à hash_to_field, comme décrit dans la section 5.

  2. Les étiquettes DOIVENT avoir une longueur non nulle. Une longueur minimale de 16 octets est RECOMMANDÉE pour réduire le risque de collisions avec d'autres applications.

  3. Les étiquettes DEVRAIENT commencer par une chaîne d'identification fixe qui est unique à l'application.

  4. Les étiquettes DEVRAIENT inclure un numéro de version.

  5. Pour les applications qui définissent plusieurs suites cryptographiques, l'étiquette de chaque suite DOIT être différente. À cette fin, il est RECOMMANDÉ d'inclure un identifiant de suite cryptographique dans chaque étiquette.

  6. Pour les applications qui utilisent plusieurs encodages, vers la même courbe ou vers des courbes différentes, chaque encodage DOIT utiliser une étiquette différente. À cette fin, il est RECOMMANDÉ d'inclure l'ID de suite de l'encodage (section 8) dans l'étiquette de séparation de domaine. Pour les encodages indépendants basés sur la même suite, chaque étiquette DEVRAIT également inclure un identifiant distinct, par exemple « ENC1 » et « ENC2 ».

À titre d'exemple, considérons une application fictive nommée Quux qui définit plusieurs suites cryptographiques différentes, chacune pour une courbe différente. Un choix raisonnable d'étiquette est « QUUX-V-CS- », où et sont des nombres à deux chiffres indiquant respectivement la version et la suite cryptographique, et est l'ID de suite de l'encodage utilisé dans la suite .

À titre d'autre exemple, considérons une application fictive nommée Baz qui nécessite deux oracles aléatoires indépendants vers la même courbe. Des choix raisonnables d'étiquettes pour ces oracles sont respectivement « BAZ-V-CS--ENC1 » et « BAZ-V-CS--ENC2 », où , et sont tels que décrits ci-dessus.

Les exemples d'étiquettes donnés ci-dessus sont supposés être des chaînes d'octets encodées en ASCII sans terminaison nulle, ce qui est le format RECOMMANDÉ. D'autres encodages peuvent être utilisés, mais dans tous les cas, l'encodage sous forme de séquence d'octets DOIT être spécifié de manière non ambiguë.

Dernière mise à jour le