2. Contexte
Ce qui suit est une brève définition des courbes elliptiques, en mettant l'accent sur les paramètres importants et leur relation avec le hachage vers les courbes. Pour plus de références sur les courbes elliptiques, consultez [CFADLNV05] ou [W08].
2.1. Courbes elliptiques
Soit F le corps fini GF(q) de caractéristique première p > 3. (Ce document ne considère pas les courbes elliptiques sur des corps de caractéristique 2 ou 3.) Dans la plupart des cas, F est un corps premier, donc q = p. Sinon, F est un corps d'extension, donc q = p^m pour un entier m > 1. Ce document écrit les éléments des corps d'extension dans une base d'élément primitif ou polynomiale, c'est-à-dire sous la forme d'un vecteur de m éléments de GF(p) écrits par ordre croissant de degré. Les entrées de ce vecteur sont indexées par ordre croissant en commençant par 1, c'est-à-dire x = (x_1, x_2, ..., x_m). Par exemple, si q = p^2 et que la base d'élément primitif est (1, I), alors x = (a, b) correspond à l'élément a + b * I, où x_1 = a et x_2 = b. (Notez que tous les choix de base sont isomorphes, mais certains choix peuvent entraîner une implémentation plus efficace ; ce document ne fait aucune hypothèse particulière sur le choix de la base.)
Une courbe elliptique E est spécifiée par une équation à deux variables et un corps fini F. Une équation de courbe elliptique prend l'une des plusieurs formes standard, incluant (mais sans s'y limiter) Weierstrass, Montgomery et Edwards.
La courbe E induit un groupe algébrique d'ordre n, ce qui signifie que le groupe possède n éléments distincts. (Ce document utilise la notation additive pour l'opération de groupe de la courbe elliptique.) Les éléments d'un groupe de courbe elliptique sont des points de coordonnées affines (x, y) satisfaisant l'équation de la courbe, où x et y sont des éléments de F. En outre, tous les groupes de courbes elliptiques ont un élément distingué, le point à l'infini ou point identité, qui agit comme l'élément identité pour l'opération de groupe. Sur certaines courbes (y compris les courbes de Weierstrass et de Montgomery), le point identité ne peut pas être représenté sous la forme d'une paire de coordonnées (x, y).
Pour des raisons de sécurité, les applications cryptographiques des courbes elliptiques nécessitent généralement l'utilisation d'un (sous-)groupe d'ordre premier. Soit G un tel sous-groupe de la courbe d'ordre premier r, où n = h * r. Dans cette équation, h est un entier appelé le cofacteur. Un algorithme qui prend en entrée un point arbitraire sur la courbe E et produit en sortie un point dans le sous-groupe G de E est dit « effacer le cofacteur ». De tels algorithmes sont discutés dans la section 7.
Certains algorithmes de hachage vers courbe restreignent la forme de l'équation de la courbe, la caractéristique du corps ou les paramètres de la courbe. Pour chaque algorithme présenté, ce document énumère les restrictions pertinentes.
Le tableau ci-dessous résume les quantités pertinentes pour le hachage vers les courbes :
| Symbole | Signification | Pertinence |
|---|---|---|
| F,q,p | Un corps fini F de caractéristique p et #F = q = p^m. | Pour les corps premiers, q = p ; sinon, q = p^m et m>1. |
| E | Courbe elliptique. | E est spécifiée par une équation et un corps F. |
| n | Nombre de points sur la courbe elliptique E. | n = h * r, pour h et r définis ci-dessous. |
| G | Un sous-groupe d'ordre premier des points sur E. | G est un groupe de destination vers lequel les chaînes d'octets sont encodées. |
| r | Ordre de G. | r est un facteur premier de n (généralement, le plus grand de ces facteurs). |
| h | Cofacteur, h >= 1. | h est un entier satisfaisant n = h * r. |
Tableau 1 : Résumé des symboles et de leurs définitions
2.2. Terminologie
Dans cette section, nous définissons les termes importants utilisés tout au long du document.
2.2.1. Mappages
Un mappage est une fonction déterministe d'un élément du corps F vers un point sur une courbe elliptique E définie sur F.
En général, l'ensemble de tous les points qu'un mappage peut produire sur toutes les entrées possibles peut n'être qu'un sous-ensemble des points d'une courbe elliptique (c'est-à-dire que le mappage peut ne pas être surjectif). En outre, un mappage peut produire le même point pour deux ou plusieurs entrées distinctes (c'est-à-dire que le mappage peut ne pas être injectif). Par exemple, considérons un mappage de F vers une courbe elliptique ayant n points : si le nombre d'éléments de F n'est pas égal à n, alors ce mappage ne peut pas être bijectif (c'est-à-dire à la fois injectif et surjectif), puisque le mappage est défini comme étant déterministe.
Les mappages peuvent également être inversibles, ce qui signifie qu'il existe un algorithme efficace qui, pour tout point P produit par le mappage, produit un x dans F tel que l'application du mappage à x produit P. Certains des mappages donnés dans la section 6 sont inversibles, mais ce document ne traite pas des algorithmes d'inversion.
2.2.2. Encodages
Les encodages sont étroitement liés aux mappages. Comme un mappage, un encodage est une fonction qui produit un point sur une courbe elliptique. Contrairement à un mappage, cependant, l'entrée d'un encodage est une chaîne d'octets de longueur arbitraire.
Ce document construit des encodages déterministes en composant une fonction de hachage Hf avec un mappage déterministe. En particulier, Hf prend en entrée une chaîne arbitraire et produit un élément de F. Le mappage déterministe prend cet élément en entrée et produit un point sur une courbe elliptique E définie sur F. Étant donné que Hf prend des chaînes d'octets de longueur arbitraire en entrée, elle ne peut pas être injective : l'ensemble des entrées est plus grand que l'ensemble des sorties, il doit donc y avoir des entrées distinctes qui donnent la même sortie (c'est-à-dire qu'il doit y avoir des collisions). Ainsi, tout encodage construit à partir de Hf n'est pas non plus injectif.
Comme les mappages, les encodages peuvent être inversibles, ce qui signifie qu'il existe un algorithme efficace qui, pour tout point P produit par l'encodage, produit une chaîne s telle que l'application de l'encodage à s produit P. Cependant, l'instanciation de Hf utilisée par tous les encodages spécifiés dans ce document (section 5) n'est pas inversible ; ainsi, ces encodages ne sont pas non plus inversibles.
Dans certaines applications de hachage vers des courbes elliptiques, il est important que les encodages ne divulguent pas d'informations par des canaux auxiliaires. [VR20] est un exemple de ce type de fuite menant à une vulnérabilité de sécurité. Voir la section 10.3 pour plus de détails.
2.2.3. Encodages à oracle aléatoire
Un encodage à oracle aléatoire satisfait une propriété forte : il peut être prouvé indifférenciable d'un oracle aléatoire [MRH04] sous une hypothèse appropriée.
Les deux constructions décrites dans la section 3 sont indifférenciables des oracles aléatoires [MRH04] lorsqu'elles sont instanciées en suivant les conseils de ce document. Les constructions diffèrent par leurs distributions de sortie : l'une donne un point aléatoire uniforme sur la courbe, l'autre donne un point échantillonné à partir d'une distribution non uniforme.
Un encodage à oracle aléatoire avec une distribution de sortie uniforme convient à une utilisation dans de nombreux protocoles cryptographiques dont la sécurité est prouvée dans le modèle de l'oracle aléatoire. Voir la section 10.1 pour plus de détails.
2.2.4. Sérialisation
Une procédure liée à l'encodage est la conversion d'un point de courbe elliptique en une chaîne de bits. C'est ce qu'on appelle la sérialisation, et elle est généralement utilisée pour stocker ou transmettre des points de manière compacte. L'opération inverse, la désérialisation, convertit une chaîne de bits en un point de courbe elliptique. Par exemple, [SEC1] et [p1363a] donnent des méthodes standard pour la sérialisation et la désérialisation.
La désérialisation est différente de l'encodage par le fait que seules certaines chaînes (à savoir celles produites par la procédure de sérialisation) peuvent être désérialisées. En revanche, ce document concerne les encodages de chaînes arbitraires vers des points de courbe elliptique. Ce document ne couvre pas la sérialisation ou la désérialisation.
2.2.5. Séparation de domaine
Les protocoles cryptographiques dont la sécurité est prouvée dans le modèle de l'oracle aléatoire sont souvent analysés sous l'hypothèse que l'oracle aléatoire ne répond qu'aux requêtes associées à ce protocole (y compris les requêtes effectuées par des adversaires) [BR93]. En pratique, cette hypothèse ne tient pas si deux protocoles utilisent la même fonction pour instancier l'oracle aléatoire. Concrètement, considérons les protocoles P1 et P2 qui interrogent un oracle aléatoire RO : si P1 et P2 interrogent tous deux RO sur la même valeur x, l'analyse de sécurité de l'un ou des deux protocoles peut être invalidée.
Une façon courante d'aborder ce problème est appelée séparation de domaine, ce qui permet à un seul oracle aléatoire de simuler plusieurs oracles indépendants. Ceci est réalisé en s'assurant que chaque oracle simulé voit des requêtes qui sont distinctes de celles vues par tous les autres oracles simulés. Par exemple, pour simuler deux oracles RO1 et RO2 à partir d'un seul oracle RO, on pourrait définir
RO1(x) := RO("RO1" || x) RO2(x) := RO("RO2" || x)
où || est l'opérateur de concaténation. Dans cet exemple, « RO1 » et « RO2 » sont appelés étiquettes de séparation de domaine (DST) ; elles garantissent que les requêtes vers RO1 et RO2 ne peuvent pas entraîner des requêtes identiques vers RO, ce qui signifie qu'il est sûr de traiter RO1 et RO2 comme des oracles indépendants.
En général, la séparation de domaine nécessite de définir un encodage injectif distinct pour chaque oracle simulé. Dans l'exemple ci-dessus, « RO1 » et « RO2 » ont la même longueur et satisfont donc cette exigence lorsqu'ils sont utilisés comme préfixes. Les algorithmes spécifiés dans ce document adoptent une approche différente pour garantir l'injectivité ; voir les sections 5.3 et 10.7 pour plus de détails.