Logarithme discret en cryptographie

Logarithme discret en cryptographie

Problème de l’échange de clés

La clé est un outil central en cryptographie pour pouvoir mettre en place un protocole qui protège la communication entre deux parties. Dans le cadre de la cryptographie symétrique (également appelée cryptographie à clé secrète), les deux parties, que l’on appelle habituellement Alice et Bob, sont amenées à établir une clé secrète commune. On appelle ce problème le problème de l’échange de clé. Par le passé, les valises diplomatiques ou d’autres formes de canaux « sécurisés » ont été utilisées pour pouvoir transmettre la clé. De nos jours, il est pertinent de supposer qu’Alice et Bob n’ont accès qu’à un canal de communication non protégé. Nous supposons par ailleurs que les deux parties sont authentifiées de sorte à prévenir des attaques de type Homme de milieu (Man in the middle en anglais). Diffie et Hellman ont proposé en 1976 une solution qui répond au problème de la création d’une clé commune [DH76]. De nos jours, le protocole d’échange de clés Diffie-Hellman est intégré dans différents navigateurs web et fait partie de plusieurs protocoles de sécurisation des échanges sur Internet tels que TLS (Transport Layer Security). Le schéma de la figure 1.1 détaille le protocole qui permet à Alice et Bob de créer communément une clé. Une des deux parties, ici Alice, commence par choisir un groupe cyclique G de cardinal n, noté multiplicativement et engendré par g. Nous utilisons la notation G = hgi pour préciser que G est engendré par g. Alice choisit un entier kA ∈ [0, n − 1], calcule g kA et l’envoie à Bob. Idem, Bob choisit un entier kB ∈ [0, n − 1], calcule g kB et l’envoie à Alice. À la fin de l’échange, les deux parties peuvent alors construire la même clé K = (g kA ) kB = (g kB ) kA .

Problème du logarithme discret

Définitions

Reprenons le groupe cyclique G de cardinal n et engendré par g. L’opération d’exponentiation discrète est définie dans le groupe comme suit. Définition 1.1 (Exponentiation discrète). Étant donnés le groupe G, un entier k dans [0, n−1] et un élément g ∈ G, élever g à la puissance k consiste à calculer g k = g × g × · · · × g | {z } k fois . On note que l’exponentiation discrète, en utilisant la méthode d’exponentiation binaire, se calcule en O (log n) opérations dans G. Le logarithme discret correspond à la réciproque de l’exponentiation. Le logarithme discret d’un élément du groupe est défini comme suit. Définition 1.2 (Logarithme discret et problème du logarithme discret). Étant donnés un groupe G cyclique engendré par g et un élément h dans le groupe, le logarithme discret de h, en base g, qu’on note logg h, est l’unique entier k dans [0, n − 1] tel que h = g k . (1.1) Le problème du logarithme discret consiste à calculer k = logg h à partir de h et g. Dès lors que la loi de groupe est calculable en temps polynomial en la taille des entrées, le problème de l’exponentiation discrète est dit « facile », c’est-à-dire, qu’il existe des algorithmes qui permettent de le résoudre en temps « court » avec des ressources de calcul limitées. Le problème inverse, celui du logarithme discret, est « difficile » dans certains groupes, c’est-à-dire nécessite un temps de calcul « long » même en utilisant un grand nombre de ressources. Les notions de « court » et « long » qu’on utilise ici sont évidemment relatives et seront clarifiées dans la suite quand nous allons préciser les complexités des opérations. L’asymétrie entre l’exponentiation et le logarithme discret est utilisée en cryptographie à clé publique pour construire des fonctions à trappe, c’est-à-dire, des fonctions qui peuvent être aisément calculées lorsque la trappe est connue et dures à inverser sans connaissance de la trappe. Dans l’exemple de l’échange de clés Diffie-Hellman, que nous avons précédemment évoqué, la sécurité du protocole repose sur la difficulté pour une troisième partie de pouvoir calculer des logarithmes discrets à partir des données échangées. Cette difficulté est formalisée dans la définition suivante. Définition 1.3 (Problème Diffie-Hellman calculatoire (CDH)). Étant donné le groupe G engendré par g, le problème CDH consiste à calculer g kAkB à partir de g, g kA et g kB . Il est clair que résoudre le problème du logarithme discret permettra à l’attaquant de résoudre le problème CDH. La réciproque est moins triviale [Mau94, MW96].

Groupes proposés

Les groupes proposés pour les applications cryptographiques doivent satisfaire les propriétés suivantes : — les éléments du groupe peuvent être représentés à l’aide de O (log n) bits ;— l’arithmétique dans le groupe G doit être efficace, en particulier l’exponentiation doit pouvoir être faite avec une complexité au plus polynomiale en la taille des entrées ; — le problème du logarithme discret doit être aussi difficile que possible. Idéalement, la complexité des meilleurs algorithmes qui permettent de le résoudre devrait être exponentielle en la taille des entrées. Il existe des groupes qui ne répondent pas à ces critères, tels que les groupes additifs (Z/nZ, +), vu que le problème du logarithme discret dans ces groupes se résout avec l’algorithme d’Euclide, en temps polynomial en la taille des entrées. Parmi les bons groupes au sens de la difficulté du problème du logarithme discret, nous trouvons les groupes multiplicatifs des corps finis Fp k et les groupes des points de courbes elliptiques définies sur des corps finis. Ces deux familles de groupes satisfont les deux premières propriétés. La difficulté de résoudre le problème du logarithme discret varie en fonction du type de groupe. En effet, pour les corps finis, il existe des algorithmes pour résoudre le problème du logarithme discret avec une complexité sous-exponentielle ou quasi-polynomiale en la taille du corps, que nous allons détailler dans la section 1.4. Pour les courbes elliptiques, il existe aujourd’hui des algorithmes sous-exponentiels de cryptanalyse pour des familles particulières de courbes. Toutefois, il n’existe aucun algorithme de complexité sous-exponentielle pour calculer le logarithme discret sur une courbe elliptique générique. 

Applications

Des primitives cryptographiques qui reposent sur la difficulté du logarithme discret ont été développées pour l’échange de clés, pour le chiffrement ou pour la signature. Cryptosystème d’ElGamal. ElGamal a proposé en 1985 un système de chiffrement et de signature, reposant sur le problème du logarithme discret dans un corps fini [ElG85]. L’algorithme de signature est intégré dans la suite GnuPG (GNU Privacy Guard). La signature DSA. L’algorithme DSA (Digital Signature Algorithm) est l’algorithme de signature standardisé par le NIST par le biais du standard DSS (Digital Signature Standard). Dans cet algorithme, un corps fini premier Fp est utilisé. Néanmoins, les opérations de calcul ne sont pas effectuées dans Fp ×, mais dans un sous-groupe d’ordre premier q qui divise p − 1. Nous reviendrons dans la sous-section 1.4.1 sur cette idée de calculer dans un sous-groupe plutôt que dans tout le corps. Les couplages. Définition 1.4 (Couplage). Soient G1, G2 et GT trois groupes cycliques de même cardinal. On note G1 et G2 additivement et GT multiplicativement. Un couplage est une application bilinéaire.