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 encoder des chaînes d'octets vers des points d'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 à la Section 5.
hash_to_field(msg, count)

Input:
- msg, a byte string containing the message to hash.
- count, the number of elements of F to output.

Output:
- (u_0, ..., u_(count - 1)), a list of field elements.

Steps: defined in Section 5.
  • La fonction map_to_curve calcule un point de la courbe elliptique E à partir d'un élément du corps fini F sur lequel E est définie. La Section 6 décrit des applications (mappings) pour toute une gamme de familles de courbes.
map_to_curve(u)

Input: u, an element of field F.
Output: Q, a point on the elliptic curve E.
Steps: defined in Section 6.
  • La fonction clear_cofactor envoie tout point de la courbe E vers le sous-groupe G de E. La Section 7 décrit des méthodes pour effectuer cette opération.
clear_cofactor(Q)

Input: Q, a point on the elliptic curve E.
Output: P, a point in G.
Steps: defined in Section 7.

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

  • encode_to_curve est un encodage non uniforme des chaînes d'octets vers les points de G. Autrement dit, la distribution de sa sortie n'est pas uniformément aléatoire dans G : l'ensemble des sorties possibles de encode_to_curve ne représente qu'une fraction des points de G, et certains points de cet ensemble ont une probabilité d'être produits plus élevée 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)

Input: msg, an arbitrary-length byte string.
Output: P, a point in G.

Steps:
1. u = hash_to_field(msg, 1)
2. Q = map_to_curve(u[0])
3. P = clear_cofactor(Q)
4. return P
  • hash_to_curve est un encodage uniforme des chaînes d'octets vers les points de G. Autrement dit, la distribution de sa sortie est statistiquement proche de la distribution uniforme sur G.

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

hash_to_curve(msg)

Input: msg, an arbitrary-length byte string.
Output: P, a point in G.

Steps:
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              # Point addition
5. P = clear_cofactor(R)
6. return P

Chaque suite hash-to-curve 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) afin d'éviter toute interférence avec d'autres usages de fonctionnalités similaires.

Les applications qui instancient plusieurs instances indépendantes de hash_to_curve ou de encode_to_curve DOIVENT imposer une séparation de domaine entre ces instances. Cette exigence s'applique aussi bien au cas de plusieurs instances visant la même courbe qu'au cas de plusieurs instances visant des courbes différentes. (En effet, la primitive interne hash_to_field (Section 5) requiert une séparation de domaine pour garantir l'indépendance des sorties.)

La séparation de domaine est imposée au moyen d'une étiquette de séparation de domaine (DST, domain separation tag), qui est une chaîne d'octets construite conformément aux exigences suivantes :

  1. Les étiquettes DOIVENT être fournies comme paramètre DST à hash_to_field, comme décrit à la Section 5.

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

  3. Les étiquettes DEVRAIENT commencer par une chaîne d'identification fixe et propre à 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, que ce soit 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'identifiant de suite (Suite ID, Section 8) de l'encodage dans l'étiquette de séparation de domaine. Pour des encodages indépendants fondé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<xx>-CS<yy>-<suiteID> », où <xx> et <yy> sont des nombres à deux chiffres indiquant respectivement la version et la suite cryptographique, et où <suiteID> est l'identifiant de suite de l'encodage utilisé dans la suite cryptographique <yy>.

Autre exemple : considérons une application fictive nommée Baz qui requiert deux oracles aléatoires indépendants vers la même courbe. Des choix raisonnables d'étiquettes pour ces oracles sont respectivement « BAZ-V<xx>-CS<yy>-<suiteID>-ENC1 » et « BAZ-V<xx>-CS<yy>-<suiteID>-ENC2 », où <xx>, <yy> et <suiteID> sont tels que décrits ci-dessus.

Les étiquettes données en exemple ci-dessus sont supposées être des chaînes d'octets encodées en ASCII sans terminaison nulle, ce qui constitue 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é sans ambiguïté.

Dernière mise à jour le