Des corps, des courbes, des couplages, des messages codés… et des logarithmes discrets.

Piste rouge 14 novembre 2013  - Rédigé par  Vanessa Vitse Voir les commentaires (2)

Le prix Gödel, qui récompense chaque année des travaux remarquables en informatique théorique, a été décerné le 3 juin 2013 à Dan Boneh, Matt Franklin et Antoine Joux pour leurs travaux en cryptologie, reposant sur l’utilisation d’un outil mathématique appelé couplage. Parallèlement, deux équipes de chercheurs se font la course depuis quelques mois et battent record sur record d’un problème difficile, le calcul de logarithmes discrets dans des corps finis, et ces résultats semblent justement menacer l’utilisation des couplages. Ces récents événements sont l’occasion de parler un peu de cryptologie sur Images des Mathématiques.

La cryptologie, c’est quoi ?

D’après le dictionnaire, la cryptologie c’est l’étude des codes et des messages secrets. C’est une discipline très ancienne, dont on retrouve les premières traces dès la plus haute antiquité ; en un sens, vu la proportion de personnes sachant lire à l’époque, on peut considérer que les premiers messages écrits étaient déjà des messages secrets, comparés à des messages transmis par oral ! L’opération qui consiste à transformer un message lisible normalement (on dit en clair) en un message codé (on dit aussi crypté, ou chiffré) s’appelle le chiffrement, et l’opération inverse est bien sûr le déchiffrement. On divise traditionnellement, et un peu artificiellement, la cryptologie entre cryptographie, qui s’intéresse plus à la conception des systèmes de chiffrement, et la cryptanalyse qui cherche à « casser » des codes, c’est-à-dire être capable de les déchiffrer sans connaître les informations secrètes dont dispose le destinataire du message [1]. Pendant très longtemps il s’agissait plutôt d’un artisanat, et c’est seulement au vingtième siècle, avec la mécanisation puis l’essor des ordinateurs qui permettent d’effectuer très rapidement des opérations de chiffrement sophistiquées, que la cryptologie est devenue une discipline scientifique mêlant informatique et mathématiques.

En plus de cet aspect traditionnel du chiffrement, qui protège la confidentialité des transmissions, la cryptographie s’intéresse plus généralement à tout ce qui concerne la sécurité des communications. Elle essaie en particulier de garantir

  • l’intégrité des messages : on doit pouvoir détecter facilement si le message a été modifié par une tierce partie pendant la transmission,
  • l’authenticité : pas de tromperie possible sur l’expéditeur du message,
  • la non-répudiation : l’auteur d’un message ne peut pas contester l’avoir écrit.

Ces propriétés sont par exemple à la base du concept de signature électronique. On ne s’étendra pas sur ces points par la suite, puisque les outils mathématiques ou combinatoires qu’ils utilisent sont proches de ceux du chiffrement.

Cryptographie symétrique

Avant les années 1970, tous les systèmes de chiffrement connus fonctionnaient sur le principe de la cryptographie symétrique. Pour communiquer, Alice et Bob [2] doivent préalablement se rencontrer pour convenir d’une méthode de chiffrement ; ils peuvent ensuite se servir de celle-ci pour s’envoyer des messages cryptés. En pratique, ce n’est pas tout le système de chiffrement qui est secret, mais juste une petite partie, appelée la clé . Cela permet d’utiliser la même méthode pour communiquer avec plusieurs personnes, en changeant juste la clé selon l’interlocuteur. Aussi, si la clé est compromise, il suffit d’en prendre une nouvelle plutôt que de changer tout le système [3].

Un exemple historique : le chiffrement de César

Le chiffrement de César consiste à remplacer chaque lettre du message par une lettre située plus loin dans l’alphabet, et la clé est alors la longueur du décalage [4] . Par exemple, si le décalage est de 3 lettres, on remplace A par D, B par E, C par F,… W par Z, X par A, Y par B et Z par C. Ainsi le mot en clair ATTAQUEZ LES GAULOIS devient DWWDTXHC OHV JDXORLV. Pour déchiffrer, il suffit de faire le décalage dans l’autre sens. Évidemment, le faible nombre de clés possibles (26) rend ce système très vulnérable [5].

JPEG - 93.7 ko
Ceci n’est pas le chiffrement de César...

Il existe actuellement des systèmes de chiffrement symétrique très rapides et très sûrs, comme le standard AES. Mais la difficulté principale est l’échange préalable à la communication : c’est le problème de la diffusion des clés, expliqué dans cet article d’Images des Mathématiques.

Cryptographie asymétrique

En 1976, Whitfield Diffie et Martin Hellman proposent une méthode d’échange de clé, qui permet précisément à Alice et Bob d’éviter d’avoir à se rencontrer au préalable. Dans ce protocole, Alice et Bob calculent interactivement un secret commun, qu’une personne ayant espionné la communication ne peut pas reconstruire, et qui peut ensuite servir de clé pour un échange avec un système symétrique standard. (On verra les détails plus loin.)

C’est un premier pas vers la cryptographie asymétrique, dont le fonctionnement, proposé en 1974 par Ralph Merkle, est le suivant. Désormais, Alice et Bob disposent chacun d’une paire de clés : une clé publique, à qui tout le monde a accès par exemple en consultant un annuaire et qui sert à chiffrer, et une clé privée (ou secrète), qui n’est divulguée à personne et qui sert à déchiffrer. Pour envoyer un message à Bob, Alice va récupérer la clé publique de Bob et s’en servir pour coder son message. Bob va ensuite utiliser sa clé privée pour déchiffrer le message qu’il a reçu. Autrement dit, tout le monde peut envoyer un message chiffré à Bob, mais lui seul est capable de le déchiffrer. On peut faire l’analogie avec le fonctionnement d’une boîte aux lettres : n’importe qui peut déposer une lettre dans la boîte de Bob à partir du moment où il connaît son adresse postale (qui est publique), par contre seul Bob, qui a la clef de sa boîte aux lettres, peut lire le courrier qu’il lui est destiné.

Pour réaliser ceci mathématiquement, il faut une fonction de chiffrement $C$, qui à un message en clair $m$ et une clé $K$ associe un nouveau message (crypté) $C(m,K)$, et une fonction de déchiffrement $D$ qui prend un message et une clé et ressort un message en clair. Pour que le système marche, il faut bien sûr que si $K_p$ et $K_s$ sont les clés publique et secrète de Bob, on ait $m = D(C(m,K_p),K_s)$ pour tout message $m$.

PNG - 47.2 ko
Chiffrement asymétrique

Concevoir un tel système de chiffrement asymétrique n’a rien d’évident. Le premier inventé, et qui a popularisé le concept, est le système RSA (on renvoie encore à cet article) ; il a été rapidement suivi par le chiffrement d’ElGamal, qui reprend le principe de l’échange de clé de Diffie-Hellman. Dans tous les cas, on a besoin de ce qu’on appelle une fonction à sens unique : la clé publique doit pouvoir se déduire facilement de la clé privée, mais inversement, il faut qu’il soit très difficile de trouver la clé privée en connaissant seulement la clé publique [6]. Un exemple de telle fonction est la multiplication de deux (grands) nombres premiers : n’importe quel ordinateur fait ça en une fraction de seconde [7], par contre le problème inverse de factoriser un grand nombre est incommensurablement plus difficile. C’est sur la difficulté de la factorisation que se fonde la sécurité du système RSA. Le chiffrement d’ElGamal et l’échange de Diffie-Hellman se basent eux sur la fonction à sens unique donnée par l’exponentiation rapide (ou modulaire), et le problème réciproque difficile est celui du logarithme discret.

JPEG - 48.8 ko
Whit Diffie, Martin Hellman, Ralph Merkle et Taher Elgamal

Exponentiation modulaire ? Logarithme discret ??

Si $g$ et $x$ sont deux entiers positifs, le produit
\[\underbrace{g \times g \times \dots \times g}_{x \mbox{ fois}}\]
se note $g^x$ et se lit $g$ puissance $x$ ; on appelle exponentielle en base $g$ la fonction qui à l’entier $x$ associe l’entier $g^x$. Réciproquement, si on connait $g$ et un entier $y$ qui est une puissance de $g$, alors l’entier $x$ tel que $y=g^x$ s’appelle le logarithme en base $g$ de $y$. La fonction logarithme en base 10 est d’usage assez courant et est présente sur toutes les calculatrices (c’est la touche $\log$ [8]).

En cryptographie, on va faire quelque chose de légèrement différent. On commence par choisir un entier $n$, appelé le modulo. Dans la pratique, le modulo doit être très grand [9], ce qui ici veut dire qu’il s’écrit avec plusieurs centaines de chiffres (ce n’est pas ce que l’on prendra pour les exemples !). Puis on va calculer $r$, le reste de $g^x$ dans la division par $n$, ce qui se note
\[r \equiv g^x\ [n].\]
Cette opération (calculer $r$ à partir de $g$, $x$ et $n$) s’appelle l’exponentiation modulaire. Attention, pour obtenir $r$ quand les nombres sont grands, il ne faut surtout pas multiplier $x$ fois $g$ par lui-même et ensuite faire la division, ça serait beaucoup trop long ! On utilise plutôt un algorithme d’exponentiation rapide.

L’exponentiation rapide

La première idée, c’est qu’au lieu de calculer $g^2 =g\times g$, puis $g^3 = g \times g \times g = g^2 \times g$, puis $g^4 = g \times g \times g \times g = g^3 \times g$ etc., on va multiplier entre eux les résultats des calculs intermédiaires déjà obtenus. Par exemple, pour calculer $g^{10}$, on commence par $g^2 = g \times g$, puis $g^4 = g^2 \times g^2$, puis $g^8 = g^4 \times g^4$, et enfin $g^{10} = g^8 \times g^2$, soit quatre multiplications au lieu de neuf.

La deuxième idée, c’est de prendre le reste dans la multiplication par $n$ (ou « modulo $n$ », comme disent les mathématiciens) à chaque étape intermédiaire au lieu de ne le faire qu’à la fin. Ça diminue de beaucoup la taille des nombres impliqués dans les calculs.

Exemple : pour calculer 1125 modulo 47, on procède ainsi

  • $11^2 = 11 \times 11 = 121 \equiv 27 \ [47],$
  • $11^4 = 11^2 \times 11^2 \equiv 27 \times 27 = 729 \equiv 24 \ [47],$
  • $11^8 = 11^4 \times 11^4 \equiv 24 \times 24 = 576 \equiv 12 \ [47],$
  • $11^{16} = 11^8 \times 11^8 \equiv 12 \times 12 = 144 \equiv 3 \ [47],$
  • $11^{24} = 11^{16} \times 11^{8} \equiv 3 \times 12 = 36 \ [47],$
  • et finalement $11^{25} = 11^{24} \times 11 \equiv 36 \times 11 = 396 \equiv 20 \ [47].$

Les opérations à effectuer dépendent en fait de l’écriture en base 2 de l’exposant $x$. Avec cette méthode d’exponentiation rapide, un ordinateur peut calculer $g^x$ modulo $n$ en une fraction de seconde, même pour des nombres de plusieurs centaines de chiffres.

L’idée de Diffie et Hellman est d’utiliser l’exponentiation modulaire pour construire un secret commun entre deux intervenants :

  • Alice et Bob, qui communiquent à distance par un canal non sécurisé, commencent par se mettre d’accord pour choisir les deux entiers $g$ et $n$.
  • De son côté, Alice choisit un entier $a$ qu’elle garde secret, calcule $r_a \equiv g^a \ [n]$ et envoie le résultat de l’exponentiation modulaire $r_a$ à Bob.
  • Dans le même temps, Bob choisit un entier secret $b$, calcule $r_b \equiv g^b \ [n]$ et l’envoie à Alice.
  • Quand Alice reçoit $r_b$, elle fait une deuxième exponentiation modulaire et calcule $C_a \equiv (r_b)^a \ [n]$.
  • De même, quand Bob reçoit $r_a$ il calcule $C_b = (r_a)^b \ [n]$.

Les propriétés de l’exponentielle font que $C_a = C_b$, c’est-à-dire qu’Alice et Bob ont obtenu une valeur commune, qui dépend des entiers secrets $a$ et $b$ qu’ils ont choisis (en effet, $C_a \equiv r_b^a \equiv (g^b)^a \equiv g^{ab} \equiv (g^a)^b \equiv (r_a)^b \equiv C_b \ [n]$). Ils peuvent alors s’en servir comme clé pour une méthode de chiffrement symétrique.

Pour que cette méthode ait un intérêt, il faut que la valeur finale $C_a = C_b$ soit secrète. Supposons qu’une troisième personne, qu’on nommera Ève, espionne les communications d’Alice et de Bob. Elle connaît alors les entiers $g$, $n$, $r_a \equiv g^a \ [n]$ et $r_b \equiv g^b \ [n]$. Si elle peut en déduire la valeur d’un entier secret $a$ ou $b$, elle peut facilement retrouver la valeur finale $C_a =C_b$ ! Par analogie avec le logarithme usuel, étant donné des entiers $g$, $n$ et $r$, l’entier $x$ tel que $r \equiv g^x \ [n]$ s’appelle le logarithme discret [10] de $r$ en base $g$ (modulo $n$). Heureusement pour Alice et Bob, calculer des logarithmes discrets est un problème difficile qui devient infaisable en pratique si les entiers mis en jeu sont suffisamment grands, et c’est ce qui assure la sécurité du protocole de Diffie-Hellman [11].

Par exemple, avec $n=23$ et $g=17$, comment trouver le logarithme discret de 10 ? Une possibilité est de faire la liste de toutes les puissances de 17 modulo 23 et d’en déduire la liste des logarithmes :

Puissances de 17 modulo 23
$x$12345678910111213141516171819202122
$17^x \ [23]$17131482112201874226109152113516191

Logarithme discret en base 17 modulo 23
$r$12345678910111213141516171819202122
$\log_{17}( r)$22161810191294141317623152018217511

Une remarque sur ces tables

On observe que $17^{22} \equiv 1 \ [23]$ : c’est le petit théorème de Fermat appliqué au nombre premier 23. Du coup les puissances suivantes de 17 se lisent en repartant au début du tableau : $17^{23} \equiv 17^{22} \times 17^1 \equiv 1 \times 17^1 \equiv 17 \ [23]$, $17^{24} \equiv 17^{22} \times 17^2 \equiv 1 \times 17^2 \equiv 13 \ [23]$, etc. Autrement dit, le logarithme discret en base 17 (modulo 23) est lui-même défini modulo 22.
Enfin, comme pour le logarithme usuel, le logarithme discret de 0 n’est pas défini.

On trouve ainsi que le logarithme discret de 10 vaut 13. Sur le deuxième tableau, il est difficile d’observer une quelconque régularité de la fonction logarithme discret : les entiers de 1 à 22 semblent avoir été mélangés de façon aléatoire. C’est exactement ce que l’on attend d’une fonction à sens unique.

Cette méthode de résolution du logarithme discret, qui consiste à essayer toutes les valeurs possibles jusqu’à trouver la bonne, s’appelle une attaque par force brute. Il en existe des variantes améliorées (comme l’algorithme « pas de bébé, pas de géant » basé sur le paradoxe des anniversaires), mais il est impossible de les mettre en œuvre quand les entiers concernés sont vraiment grands.

Les corps finis

On peut très facilement définir des analogues de l’exponentiation rapide et du logarithme discret dans des cadres plus généraux que celui des entiers modulo $n$. Tout ce qu’il faut, c’est un ensemble fini $G$ muni d’une loi de composition $\ast$ qui a les mêmes propriétés que la multiplication : en langage mathématique, on demande que $(G,\ast)$ soit un groupe. Si $g$ est un élément de $G$, l’exponentielle en base $g$ est la fonction qui à un entier $x$ positif associe
\[g^x = \underbrace{g \ast g \ast g \dots \ast g}_{x \mbox{ fois}}.\]
Réciproquement, si $h$ est un autre élément de $G$, l’entier $x$ (s’il existe) tel que $h = g^x$ est encore appelé logarithme discret de $h$ en base $g$. Pour être utilisable en pratique, il faut que les éléments du groupe $G$ puissent se représenter simplement et de façon unique sur un ordinateur et que l’opération de composition $\ast$ se calcule efficacement [12]. L’algorithme d’exponentiation présenté plus haut permet alors de calculer $g^x$ rapidement, même quand l’entier $x$ est très grand. Par contre, la difficulté du problème du logarithme discret va dépendre du groupe utilisé.

Le premier cadre qui a été proposé par les cryptographes est celui des corps finis. Sans trop rentrer dans les détails, un corps est un ensemble muni d’une opération d’addition et d’une opération de multiplication, qui se comportent « comme » l’addition et la multiplication des nombres réels ou complexes. En particulier, dans tout corps il y a un élément neutre pour l’addition et absorbant pour la multiplication, noté 0, ainsi qu’un élément neutre pour la multiplication, noté 1, et tout élément différent de 0 admet un inverse ; on peut alors utiliser le groupe des éléments différents de 0 pour l’échange de clé de Diffie-Hellman. Un corps fini est un corps ayant un nombre fini d’éléments, et ce nombre (aussi appelé sa cardinalité) est toujours une puissance d’un nombre premier : il y a ainsi des corps à 2, 3, 4, 5, 7, 8, 9, 11 éléments par exemple, mais pas de corps de cardinalité 6, 10 ou 12. Quand le nombre d’éléments $n$ est un nombre premier, on retrouve exactement l’arithmétique des entiers modulo $n$. Les autres cas (quand le nombre d’éléments est de la forme $n=p^d$, avec $p$ premier et $d>1$) sont plus délicats à décrire. Néanmoins l’architecture binaire des ordinateurs, qui s’appuie sur l’utilisation de la base 2, est particulièrement adaptée à l’emploi des corps dits binaires [13] dont le nombre d’éléments est une puissance de 2.

JPEG - 41.5 ko
Carl Friedrich Gauss et Évariste Galois, deux précurseurs de la théorie des corps finis

Un exemple : le corps à 8 éléments

Les corps binaires ont cette particularité que $x+x=0$ pour tout élément $x$ ; en particulier $1+1=0$, et l’addition s’apparente à l’opérateur logique « OU exclusif ». Le corps à 8 éléments contient, en plus de 0 et 1, six autres éléments. Si j’appelle $a$ un de ces éléments, le corps doit aussi contenir $a+1$, et aussi $a\times a = a^2$, et $a^2+1$, etc. En notant les éléments de cette façon on met déjà en lumière une partie de la structure additive et multiplicative du corps, qui est alors complètement déterminé par la relation $a^3 = a+1$. Voici les tables d’addition et de multiplication complètes :

Table d’addition
$0$$1$$a$$a+1$$a^2$$a^2+1$$a^2+a$$a^2+a+1$
$0$$0$$1$$a$$a+1$$a^2$$a^2+1$$a^2+a$$a^2+a+1$
$1$$1$$0$$a+1$$a$$a^2+1$$a^2$$a^2+a+1$$a^2+a$
$a$$a$$a+1$$0$$1$$a^2+a$$a^2+a+1$$a^2$$a^2+1$
$a+1$$a+1$$a$$1$$0$$a^2+a+1$$a^2+a$$a^2+1$$a^2$
$a^2$$a^2$$a^2+1$$a^2+a$$a^2+a+1$$0$$1$$a$$a+1$
$a^2+1$$a^2+1$$a^2$$a^2+a+1$$a^2+a$$1$$0$$a+1$$a$
$a^2+a$$a^2+a$$a^2+a+1$$a^2$$a^2+1$$a$$a+1$$0$$1$
$a^2+a+1$$a^2+a+1$$a^2+a$$a^2+1$$a^2$$a+1$$a$$1$$0$

Table de multiplication
$0$$1$$a$$a+1$$a^2$$a^2+1$$a^2+a$$a^2+a+1$
$0$$0$$0$$0$$0$$0$$0$$0$$0$
$1$$0$$1$$a$$a+1$$a^2$$a^2+1$$a^2+a$$a^2+a+1$
$a$$0$$a$$a^2$$a^2+a$$a+1$$1$$a^2+a+1$$a^2+1$
$a+1$$0$$a+1$$a^2+a$$a^2+1$$a^2+a+1$$a^2$$1$$a$
$a^2$$0$$a^2$$a+1$$a^2+a+1$$a^2+a$$a$$a^2+1$$1$
$a^2+1$$0$$a^2+1$$1$$a^2$$a$$a^2+a+1$$a+1$$a^2+a$
$a^2+a$$0$$a^2+a$$a^2+a+1$$1$$a^2+1$$a+1$$a$$a^2$
$a^2+a+1$$0$$a^2+a+1$$a^2+1$$a$$1$$a^2+a$$a^2$$a+1$



On peut maintenant calculer les puissances de $a$ et les logarithmes discrets en base $a$ :

Puissances de $a$
$x$1234567
$a^x$$a$$a^2$$a+1$$a^2+a$$a^2+a+1$$a^2+1$1

Logarithmes discrets en base $a$
$r$1$a$$a+1$$a^2$$a^2+1$$a^2+a$$a^2+a+1$
$\log_a( r)$7132645

Dans les corps finis, le problème du logarithme discret est difficile, mais pas autant qu’on pourrait l’imaginer. En effet les algorithmes dits de calcul d’indices, qui ressemblent fortement aux meilleurs algorithmes connus pour la factorisation des grands nombres entiers, sont nettement plus efficaces que les méthodes de type force brute. Cette famille d’algorithmes a justement fait des progrès considérables très récemment, dont on va reparler plus bas. Pour oser une métaphore, calculer des logarithmes discrets dans un corps fini, c’est comme casser une paroi : c’est difficile, et de plus en plus dur quand l’épaisseur augmente (c’est-à-dire quand la taille du corps augmente), mais on peut utiliser des outils pour s’aider.

Les courbes elliptiques

À cause des algorithmes de calcul d’indices, les cryptologues ont cherché d’autres groupes pour le logarithme discret. Ce sont Neal Koblitz et Victor Miller qui au milieu des années 1980 ont proposé d’utiliser les courbes elliptiques définies sur des corps finis. Ces courbes sont très célèbres en mathématiques, car c’est avec elles qu’Andrew Wiles a démontré le grand théorème de Fermat et elles sont au coeur d’un des problèmes ouverts à un million de dollars de la fondation Clay. Pourtant leur simplicité est déconcertante puisqu’une courbe elliptique est juste une courbe dans le plan, d’équation de la forme
\[y^2+a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6\]
où les $a_i$ sont des coefficients fixés, à laquelle on rajoute un point à l’infini. Dans les réels, ça ressemble à ça :

JPEG - 82.2 ko
Courbes elliptiques d’équations $y^2=x^3+3x^2+1$ (en bleu) et $y^2=x^3+2x^2-x-1$ (en rouge)
PNG - 253.3 ko
Deux images de la courbe elliptique d’équation $y^2=x^3+1$. Sur la version de droite, le point à l’infini est représenté ainsi quelques relations sur les points, comme par exemple $P_3+P_4=P_1=-P_5$.

La première subtilité, c’est que l’on peut prendre les coefficients $a_i$ ainsi que les coordonnées $x$ et $y$ dans un corps fini. On obtient ainsi un ensemble fini de couples $(x,y)$, solution dans le corps choisi de l’équation ci-dessus ; évidemment, ça n’a plus vraiment de sens de vouloir faire un dessin ! La deuxième subtilité, et la plus importante, c’est que l’on peut définir une loi de groupe, une addition, sur les points d’une courbe elliptique ; on ne va pas rentrer dans les détails (on peut en trouver dans cet article — attention, piste noire !) mais cette opération d’addition de points est simple à calculer, et ne demande que quelques additions, multiplications et divisions dans le corps choisi.

L’ensemble des points d’une courbe elliptique définie sur un corps fini est un candidat tout naturel pour être le cadre de l’échange de clé de Diffie-Hellman ou du chiffrement d’ElGamal. Une difficulté malgré tout : ces systèmes ne sont pas sûrs si le nombre de points n’est pas divisible par un grand nombre premier [14]. Or compter le nombre de points d’une courbe n’est pas évident : on peut les énumérer si le corps de base est petit, mais cela devient impossible pour les tailles de corps utilisés en cryptographie. À la fin des années 1980, on ne savait pas comment calculer rapidement la cardinalité d’une courbe elliptique définie sur un grand corps fini. On connaissait cependant les travaux de Hasse qui affirment que sur un corps à $q$ éléments, une courbe elliptique a toujours un nombre de points de l’ordre de $q$, et plus précisément compris entre $q+1-2\sqrt{q}$ et $q+1+2\sqrt{q}$ ; c’est même ce résultat qui a motivé l’énoncé des conjectures de Weil, dont la démonstration a été achevée en 1974 par Pierre Deligne et dont on parle dans cet article. Il y a quand même des courbes, appelées supersingulières, pour lesquelles il est facile d’obtenir le nombre de points, et c’est pourquoi les cryptologues ont commencé par s’y intéresser.

Coffre-fort et perceuse à main {JPEG}
On peut comparer le logarithme discret sur une courbe elliptique à un coffre-fort. En général, on n’a pas d’autre méthode pour accéder à l’intérieur du coffre que d’essayer toutes les combinaisons jusqu’à trouver celle qui ouvre la serrure, et la sécurité est très bonne. Mais en 1993, bouleversement dans la communauté cryptographique : Menezes, Okamoto et Van Stone d’une part, Frey et Rück d’autre part, découvrent qu’on peut transférer le problème du logarithme discret d’une courbe elliptique vers un corps fini. Autrement dit, ils ont réalisé que pour ouvrir un coffre, on pouvait aussi percer sa paroi, et qu’on disposait justement d’outils pour le faire avec les algorithmes de calcul d’indices ! Pour la plupart des coffres, la paroi est en fait tellement épaisse que ce n’est pas plus efficace que de passer par la serrure. Mais pour les courbes supersingulières, c’est la catastrophe : la paroi est toujours très fine… Autrement dit, pour le problème du logarithme discret les courbes supersingulières sont autant vulnérables que les corps finis de taille comparable, et ne présentent donc de ce point de vue plus d’intérêt pour la cryptographie.

Les couplages

L’objet mathématique qui permet de transférer le logarithme discret d’une courbe elliptique vers un corps fini s’appelle un couplage. C’est l’équivalent pour les groupes des applications bilinéaires non dégénérées ; la définition précise est dans le premier bloc dépliable ci-dessous.

Définition

Soit $G_1$ et $G_2$ deux groupes dont tous les éléments sont d’ordre qui divise $n$, et $G_3$ un groupe cyclique d’ordre $n$, où $n$ est un entier fixé (on note les groupes multiplicativement). Un couplage de $G_1$ et $G_2$ à valeurs dans $G_3$ est une application $e : G_1 \times G_2 \to G_3$ qui est

  • bilinéaire : $ e(a\cdot b,c) = e(a,c)\cdot e(b,c)$ et $e(a,c\cdot d) = e(a,c) \cdot e(a,d)$ pour tous éléments $a, b$ dans $G_1$ et $c, d$ dans $G_2$ ;
  • non dégénérée : pour tout $a \neq 1$ dans $G_1$, il existe $c$ dans $G_2$ tel que $e(a,c) \neq 1$ ; de même, pour tout $c \neq 1$ dans $G_2$ il existe $a$ dans $G_1$ tel que $e(a,c) \neq 1$.

Comment transférer le logarithme discret

Soit $g$ et $h$ deux éléments d’un groupe $G_1$, et on cherche l’entier $x$ tel que $h = g^x$ (on suppose qu’un tel entier existe). Supposons qu’il existe un couplage $e : G_1 \times G_2 \to G_3$. Si $c$ est un élément de $G_2$, alors par bilinéarité,
\[e(h,c) = e(g^x,c) = e(g,c)^x,\]
et on va pouvoir trouver $x$ en cherchant le logarithme de $e(h,c)$ en base $e(g,c)$. L’hypothèse de non-dégénérescence permet de s’assurer qu’en faisant ce transfert, on ne tombe pas sur équation de la forme $1 = 1^x$ qui n’apprend rien sur la valeur $x$. Evidemment, cela n’a d’intérêt que si le calcul de logarithmes discrets est plus facile dans $G_3$ que dans $G_1$.

Sur une courbe elliptique, il existe toujours de tels objets (les couplages de Weil et de Tate-Lichtenbaum sont les plus connus), qui prennent leurs valeurs parmi les éléments d’un corps. Comme on l’a évoqué plus haut, pour la plupart des courbes ce corps d’arrivée est très gros, tellement gros en fait que les calculs sont impossibles. Mais pour certaines courbes dites bien couplées, et en particulier pour les courbes supersingulières, ce corps n’est pas tellement plus gros que le corps de définition de la courbe. On peut utiliser un algorithme dû à Miller pour calculer efficacement ces couplages, et transférer le logarithme discret vers le corps fini, où il y est plus vulnérable. La découverte de cette faille dans la sécurité des courbes supersingulières fit l’effet d’une douche froide : ainsi en 1997, le célèbre cryptologue Ron Rivest (le R de RSA) déclarait [15]

Mais la sécurité des cryptosystèmes basés sur les courbes elliptiques est mal comprise, en grande partie à cause de la nature absconse des courbes elliptiques. Peu de cryptographes comprennent les courbes elliptiques […]. Cela peut changer avec le temps, mais pour l’instant, essayer d’évaluer la sécurité d’un cryptosystème sur courbe elliptique est un peu comme essayer d’évaluer des poèmes chaldéens récemment découverts. Tant que les courbes elliptiques n’auront pas été plus étudiées et évaluées, je recommanderais de ne pas déployer à grande échelle des applications s’appuyant dessus. [16]

Qu’est-ce qui a changé depuis alors ? Et bien premièrement, des méthodes efficaces de comptage des points d’une courbe elliptique ont été développées, ainsi que des méthodes pour construire directement des courbes de cardinalité données. Cela permet de se passer complètement des courbes supersingulières et de travailler de cette façon avec des courbes invulnérables au transfert par couplage. Deuxièmement, on s’est rendu compte qu’en plus de leur application en cryptanalyse, les couplages permettaient de nouvelles propriétés cryptographiques.

Applications constructives des couplages

Une troisième personne, qu’on appellera Charlie, veut aussi communiquer confidentiellement avec Alice et Bob. On peut facilement modifier l’échange de clés de Diffie-Hellman pour qu’il fonctionne à trois :

  • Alice, Bob et Charlie se mettent d’accord sur un groupe $G$ et un élément $g$.
  • Alice choisit un entier secret $a$, calcule $g^a$ et l’envoie à Bob ; dans le même temps, Bob choisit un entier secret $b$, calcule $g^b$ et l’envoie à Charlie, tandis que Charlie choisit un entier secret $c$, calcule $g^c$ et l’envoie à Alice.
  • Alice reçoit $g^c$ de Charlie, l’élève à la puissance $a$ et envoie le résultat $g^{ca}$ à Bob ; dans le même temps, Bob reçoit $g^a$ d’Alice, l’élève à la puissance $b$ et envoie le résultat $g^{ab}$ à Charlie, tandis que Charlie reçoit $g^b$ de Bob, l’élève à la puissance $c$ et envoie le résultat $g^{bc}$ à Alice.
  • Enfin, Alice reçoit $g^{bc}$ de Charlie, et l’élève à la puissance $a$ : le résultat $g^{abc}$ est le secret commun. Bob fait de même en élevant le message reçu d’Alice $g^{ca}$ à la puissance $b$, et Charlie pareil avec son message reçu de Bob $g^{ab}$ et son entier $c$.
JPEG - 13.2 ko
Antoine Joux

Au final, il faut deux tours d’échange pour arriver à un secret commun. Dans son article récompensé par le prix Gödel, Antoine Joux montre qu’en utilisant un couplage, on peut arriver au même résultat en seulement un tour :

  • Alice, Bob et Charlie se mettent d’accord sur des groupes $G_1$ et $G_3$, un élément $g$ de $G_1$ et un couplage $e : G_1 \times G_1 \to G_3$.
  • Alice choisit un entier secret $a$, calcule $g^a$ et l’envoie aux deux autres ; de même, Bob choisit un entier secret $b$, calcule $g^b$ et l’envoie aux deux autres, et Charlie fait la même chose avec son entier secret $c$.
  • Alice reçoit $g^b$ et $g^c$ de Bob et Charlie, et elle calcule $K = e(g^b,g^c)^a$. Bob fait pareil, avec les valeurs reçues $g^a$ et $g^c$ il calcule $e(g^a,g^c)^b$, et Charlie similairement calcule $e(g^a,g^b)^c$.

Les trois résultats sont en fait les mêmes : par bilinéarité $e(g^b,g^c)^a =e(g^a,g^c)^b =e(g^a,g^b)^c =e(g,g)^{abc}$. Alice, Bob et Charlie disposent ainsi d’un secret commun.

PNG - 104 ko
Dan Boneh et Matt Franklin

Bien que très simple, cette méthode d’échange tripartite en un tour a stimulé l’imagination des cryptologues en leur montrant qu’on pouvait se servir des couplages pour inventer de nouveaux protocoles. Et en effet, peu de temps après, Dan Boneh et Matt Franklin (les deux autres récipiendaires du prix Gödel) utilisent les couplages pour construire le premier système de chiffrement basé sur l’identité. Dans un tel système, la clé publique d’un intervenant est la plus simple possible, à savoir son nom. Plus besoin d’annuaires ou de recueils de clés certifiées par une autorité : une fois connus les paramètres du système, n’importe qui peut envoyer un message chiffré à n’importe qui. Dans ce système, il y a un serveur central, ou tiers de confiance, qui possède un passe-partout ; pour récupérer sa clé privée personnelle, un participant doit en faire la demande auprès de ce serveur central. Mais son rôle s’arrête à la création initiale des paramètres et aux calculs des clés privées : il n’intervient ni dans le chiffrement, ni dans le déchiffrement des messages. Par ailleurs, on peut tout à fait envoyer des messages cryptés à une personne qui n’a pas encore récupéré sa clé personnelle (mais elle ne pourra bien sûr pas les déchiffrer avant de l’avoir fait). Un tel système est bien adapté pour assurer la confidentialité des échanges dans une entreprise ou un organisme gouvernemental.

La construction de Boneh et Franklin, d’après l’idée de Joux, est très élégante et ne pourrait pas fonctionner sans les couplages. Mais la sécurité de l’ensemble impose des conditions assez fortes, puisque l’on a besoin :

  • de trois groupes $G_1, G_2, G_3$ dont la loi de groupe se calcule facilement mais où le problème du logarithme discret est difficile ;
  • d’un couplage $e : G_1 \times G_2 \to G_3$ qui doit aussi être une fonction à sens unique, c’est-à-dire calculable de façon efficace mais difficile à inverser.

Ces contraintes sont satisfaites dans le cadre des courbes, c’est d’ailleurs le seul exemple simple connu. Dans ce cas $G_1$ et $G_2$ font partie du groupe des points d’une courbe elliptique $E$ définie sur un corps fini, et $G_3$ est un sous-ensemble d’un deuxième corps fini $K$, dont la taille dépend directement d’un paramètre de $E$ appelé le degré de plongement. Mais toutes les courbes elliptiques ne conviennent pas. En effet, comme le problème du logarithme discret est un peu moins difficile dans les corps finis, il faut que le corps d’arrivée $K$ soit suffisamment gros ; mais s’il est très gros (ce qui est le cas pour la plupart des courbes) on ne peut plus manipuler ni le couplage ni les opérations dans $G_3$. Il y a donc un équilibre à trouver : pour reprendre notre analogie, il faut que la paroi du coffre-fort soit proportionnée à la serrure, ni trop fine ni trop épaisse. L’étude des courbes bien couplées, pour lesquelles le degré de plongement satisfait les critères de sécurité et d’efficacité, a été un domaine de recherche très actif durant la dernière décennie.

Des records en pagaille

Mais l’équilibre optimal, le degré de plongement adapté à un niveau de sécurité donné, dépend de l’efficacité des attaques potentielles par calcul d’indices sur les corps finis. Pour les évaluer, des équipes de chercheurs essayent régulièrement de battre le record du corps le plus gros dans lequel le problème du logarithme discret a été résolu. Le but n’est jamais de déchiffrer un message crypté d’une importance stratégique, mais bien plutôt de mettre en évidence les progrès réalisés par les algorithmes de résolution et leurs implémentations ou, plus rarement, l’évolution des performances des ordinateurs. Les résultats donnent des informations pratiques sur les types de corps à considérer pour obtenir la sécurité voulue.

En 2005, le plus gros corps dans lequel des logarithmes discrets avaient été calculés mesurait 613 bits [17]. Ce record fut battu une première fois en 2010 (676 bits) puis en juin 2012 (971 bits) par la même équipe japonaise. À partir de là, tout s’accélère :

PNG - 911 octets
  • En décembre 2012, A. Joux (déjà co-détenteur du record de 2005) annonce la résolution du problème du logarithme discret dans un corps de 1175 bits. Ce record est ensuite amélioré, passant à 1425 bits en janvier 2013 puis à 1778 bits en février.
  • Une semaine après cette dernière annonce, F. Gologlu, R. Granger, G. McGuire et J. Zumbragel battent ce record en calculant des logarithmes discrets dans un corps à 1971 bits.
  • En mars 2013, un mois plus tard, Joux monte sensiblement la barre avec une résolution du logarithme discret dans un corps de taille 4080 bits.
  • En avril 2013, le mois suivant, il est rattrapé par l’équipe de McGuire, qui font monter les enchères avec un corps de 6120 bits.
  • Enfin en mai 2013 Joux récupère son record avec un calcul dans un corps de 6168 bits.

Pour saisir l’énormité de la progression, il faut bien comprendre que l’échelle de mesure utilisée (en bits) n’est pas linéaire mais logarithmique [18] : un corps de taille 2000 bits n’a pas 1000 éléments de plus qu’un corps de taille 1000 bits, ni même 1000 fois plus, il en a 21000 fois plus ! (En gros, pour passer du nombre d’éléments d’un corps de 1000 bits à celui d’un corps de 2000 bits, il faut rajouter 300 zéros à droite…) Et calculer des logarithmes discrets dans un corps de 6168 bits est beaucoup, beaucoup plus que 10 fois plus dur que dans un corps de 613 bits. C’est grâce à l’amélioration des méthodes de calcul d’indices que de tels records ont été obtenus, bien davantage que grâce à celle du matériel informatique.

À un tel rythme, la communauté cryptologique a un peu du mal à suivre, d’autant plus qu’il semble clair que le dernier record peut être facilement battu avec des moyens matériels supplémentaires. Cependant, il ne faut pas en déduire que tous les corps finis de taille inférieure à 6000 bits sont vulnérables, loin de là : les derniers résultats ont tous été obtenus sur des corps binaires, c’est-à-dire dont le nombre d’éléments est une puissance de deux $2^d$, avec de plus des valeurs de l’exposant $d$ ayant beaucoup de diviseurs. Il semble que les corps finis dont le nombre d’éléments est un grand nombre premier, ainsi que les corps binaires dont l’exposant $d$ est premier, sont moins concernés par ces progrès récents. À titre d’exemple, le record actuel de calcul de logarithmes discrets est seulement de 530 bits dans un corps de cardinalité première (T. Kleinjung, 2007), et de 809 bits dans un corps binaire d’exposant premier (équipe CARAMEL, 2013). Par contre, les conséquences pour la sécurité des couplages sur courbes elliptiques sont importantes, puisque les corps finis d’arrivée sont toujours de cardinalité une puissance d’un nombre premier, dont l’exposant est divisible par le degré de plongement. Il s’agit donc de cibles potentielles pour les dernières méthodes de calcul d’indices ! Il est d’ores et déjà certain que plusieurs familles de courbes elliptiques définies sur des corps binaires, qui avaient été proposées dans la littérature scientifique, ne peuvent plus être considérées comme sures, et il est indispensable de réévaluer la sécurité de toutes les autres.

Au final, il est amusant de constater qu’Antoine Joux est récompensé par le prix Gödel pour l’introduction constructive des couplages en cryptographie, au moment même où ses derniers travaux menacent justement leur utilisation ! Et pour les chercheurs qui s’intéressent au sujet, il y a du travail à faire pour déterminer les courbes bien couplées résistantes à ces attaques, et éventuellement développer un autre cadre où des couplages peuvent être définis.

Post-scriptum :

L’auteur et la rédaction d’Images des mathématiques remercient les relectrices et relecteurs dont les noms (ou pseudonymes) sont les suivants : Jean-Michel Muller, Irène Marcovici, Kereneur, Olivier Reboux, subshift, janpol3, Monique Pencréach.

Notes

[1En pratique, la distinction entre ces termes est rarement faite et les spécialistes du domaine parle familièrement de « crypto », sans plus de précision.

[2En cryptologie, les personnages intervenants dans la description d’un protocole ou d’une attaque ont traditionnellement toujours les mêmes prénoms : Alice et Bob bien sûr, mais aussi Charlie, Eve, Mallory… voir cette page.

[3C’est le principe de Kerckhoffs.

[4Ce système est très certainement antérieur à Jules César, mais d’après Suétone celui-ci s’en servait souvent dans ses communications, avec un décalage de trois lettres.

[5Le rot13, qui correspond à un décalage de 13 lettres, est fréquemment utilisé dans les forums de discussion, mais ce n’est pas la sécurité du message codé qui est visée.

[6Il n’est par contre pas du tout évident de construire un système de cryptographie symétrique à partir d’une fonction à sens unique (c’est une condition nécessaire mais pas suffisante, si l’on veut…).

[7Même à la main, multiplier deux nombres d’une centaine de chiffres est certainement fastidieux mais tout à fait réalisable.

[8Alors que la touche $\ln$ calcule le logarithme népérien ou naturel.

[9Et même, pour plus de sécurité $n$ doit être un nombre premier, et $n-1$ (qui est pair) doit être divisible par un grand nombre premier. Le lecteur qui connait le théorème des restes chinois devrait pouvoir trouver pourquoi…

[10En mathématiques, discret s’oppose à continu. Le logarithme usuel peut s’appliquer à tous les réels positifs, alors qu’ici il n’y a qu’un nombre fini de restes possibles dans la division par $n$.

[11En tout cas tant que l’adversaire Ève se contente d’écouter les transmissions. Par contre si les données échangées sont susceptibles d’être interceptées et modifiées (attaque dite « de l’homme du milieu »), il faut prendre des précautions supplémentaires pour assurer la sécurité.

[12Pour un autre exemple de l’utilisation des groupes en cryptographie, voir cet article.

[13Les mathématiciens disent plutôt de caractéristique 2.

[14Sinon on peut calculer les logarithmes discrets en combinant des méthodes par force brute avec le théorème des restes chinois (et le lemme d’Hensel) : c’est l’attaque de Pohlig-Hellman.

[15À cause des intérêts financiers en jeu liés aux brevets sur le système RSA, on peut cependant douter de l’impartialité de l’auteur de la citation…

[16But the security of cryptosystems based on elliptic curves is not well understood, due in large part to the abstruse nature of elliptic curves. Few cryptographers understand elliptic curves […] Over time, this may change, but for now trying to get an evaluation of the security of an elliptic-curve cryptosystem is a bit like trying to get an evaluation of some recently discovered Chaldean poetry. Until elliptic curves have been further studied and evaluated, I would advise against fielding any large-scale applications based on them. D’autres citations similaires sont lisibles dans ces transparents.

[17En informatique, on mesure souvent la taille d’un objet en bits. Un corps fini est de taille $b$ bits s’il a environ $2^b$ éléments. Le corps de 613 bits dont il est question ici contient en fait précisément
\[\scriptstyle 33992831540273094316133645219357992149093959534530043084764424844825827831094543535306400144974674282808917087119776064982181077609773263322209278641061590524405201333465166018030600192\]
éléments, ce qui n’est pas vraiment parlant…

[18Comme l’échelle de Richter, par exemple.

Partager cet article

Pour citer cet article :

Vanessa Vitse — «Des corps, des courbes, des couplages, des messages codés… et des logarithmes discrets.» — Images des Mathématiques, CNRS, 2013

Crédits image :

Image à la une - D’après « Les hommes dansants », une aventure de Sherlock Holmes (Sir Arthur Conan Doyle).
img_10572 - Y.Mrabet d’après J.Brette, licence Creative Commons CC-BY-SA-3.0,2.5,2.0,1.0
Whit Diffie, Martin Hellman, Ralph Merkle et Taher Elgamal - Wikicommons - photo Diffie : M.Holzer, CC-BY-2.0 ; photo Hellman : M.Hellman, CC-BY-SA-3.0 ; photo Merkle : D.Orban, CC-BY-2.0 ; photo Elgamal : A.Klink, CC-BY-3.0
Coffre-fort et perceuse à main - Wikicommons - photo Brace Drill (auteur Dolev, licence CC-BY-SA-3.0) & image Safe icon (auteur Tanemori, licence CC-BY-2.1-JP)
Ceci n’est pas le chiffrement de César... - (C) Uderzo/Goscinny
img_10584 - Partie droite : wikicommons, Y.Mrabet d’après J.Brette (CC-BY-SA)
Chiffrement asymétrique - Figurines (C) R. Munroe, http://xkcd.com/

Commentaire sur l'article

  • Des corps, des courbes, des couplages, des messages codés… et des logarithmes discrets.

    le 27 novembre 2013 à 21:39, par Tino

    Merci pour cet article très intéressant. Une petite question.
    Y’-a-t-il un impact sur les courbes elliptiques utilisées dans l’industrie ? ces courbes sont sur basées sur des courbes de 160 bits (si je ne me trompe pas) et au vu des records, l’article semble très inquiétant.
    Olivier (un ancien camarade de l’UPS :-))

    Répondre à ce message
  • Des corps, des courbes, des couplages, des messages codés… et des logarithmes discrets.

    le 27 novembre 2013 à 21:55, par Vanessa Vitse

    A priori aucun impact sur la majorité des courbes elliptiques, sauf celles sur lesquelles on peut calculer le couplage... notamment les courbes supersingulières. De toute façon la cryptographie à base de couplage est encore trop récente pour qu’elle soit déployée dans le monde industriel. Et pour l’instant personne ne connait d’attaque efficace du problème du logarithme discret sur une courbe elliptique « ordinaire » définie sur un corps premier.
    Bien implémentée, la cryptographie sur courbes elliptiques est ce qui se fait de plus sûr actuellement en asymétrique et est en train de supplanter ce bon vieux RSA !

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM