FLASH INFORMATIQUE FI



Les problèmes mathématiques à la base de la sécurité de l’information




Arjen LENSTRA


Les méthodes modernes de protection de l’information sont basées sur quelques problèmes mathématiques qui ont la réputation d’être difficiles à résoudre ! Ici, nous allons présenter ces problèmes et leurs applications en cryptographie.

Introduction

Beaucoup de gens aiment que leurs données personnelles restent confidentielles. Pour garantir cette confidentialité quand ces données sont envoyées sur Internet, lors de transferts e-banking par exemple, les données doivent être protégées. Beaucoup d’applications Web proposent cette protection, souvent sans que l’utilisateur s’en rende compte.
Les méthodes de protection de l’information utilisent le chiffrement (aussi appelé parfois par l’anglicisme cryptage) : avant d’être envoyées, les données sont transformées en une suite de symboles à l’apparence incompréhensible, sauf pour le destinataire prévu qui seul peut retrouver l’information originale. Quiconque écouterait la communication ne saurait rien, hormis le fait que la communication a eu lieu. Des méthodes semblables sont utilisées pour garantir l’identité d’un utilisateur.
Cela n’implique pas que le chiffrement soit suffisant. Des malfaiteurs pourraient vouloir accéder à l’information en utilisant une des nombreuses autres méthodes. La faiblesse des systèmes d’exploitation peut être exploitée pour avoir accès au poste de travail d’un utilisateur, le mot de passe d’un utilisateur peut être volé ou deviné, ou un utilisateur peut lui même être amené à révéler son mot de passe lors d’attaques du type ingénierie sociale, etc. Le chiffrement ne suffit donc pas à garantir la confidentialité des données, mais c’est un élément nécessaire dans la chaîne de protection.
Ici, nous allons nous concentrer sur les outils mathématiques qui sont la base du chiffrement et bien sûr du déchiffrement correspondant. Nous ne parlerons pas de comment ces outils sont intégrés en pratique dans les systèmes actuels ni quelles sont les nombreuses précautions qu’il faut prendre lors de cette intégration.
La théorie des nombres joue un rôle important dans tous les outils de chiffrement les plus utilisés. En simplifiant, c’est la branche des mathématiques qui étudie les nombres entiers naturels (0,1,2,3 ...). Une activité ludique pour certains, longtemps jugée sans intérêt pratique par les autres. Ceci a changé quand les applications de chiffrement basées sur les nombres premiers furent découvertes. Un entier naturel est premier s’il n’admet que deux entiers diviseurs distincts, 1 et lui-même. Par exemple, 17 est un nombre premier, car il ne peut être divisible que par 1 et par 17. Mais 91 n’est pas premier, car 91 = 7 * 13, donc 91 est divisible par d’autres nombres que 1 et 91 (en fait 7 et 13). Le nombre 1 n’est pas premier. Cela fait des siècles que les théoriciens étudient les nombres premiers, mais leur potentiel en cryptographie n’a été découvert que récemment (approximativement dans les années 1970, la date exacte reste sujet de débat,...). Les applications en cryptographie utilisent de manière créative deux problèmes impliquant des nombres premiers :

  • la factorisation des nombres entiers
  • le calcul des logarithmes discrets.

Ces problèmes ont été beaucoup étudiés, en particulier depuis qu’on a découvert leur intérêt en cryptographie. Mais peu de progrès ont été faits, on pense généralement que ces deux problèmes sont difficiles. C’est précisément cette difficulté qui en fait l’intérêt pour la cryptographie, et de ce point de vue, on ne peut qu’espérer qu’ils resteront non résolus. On doit malgré tout garder à l’esprit que des progrès sont possibles et qu’on peut découvrir soit une preuve de la difficulté des problèmes, soit une méthode efficace pour les résoudre. Dans le premier cas, on détiendra la justification théorique qui nous manque aujourd’hui pour la sécurité des applications en cryptographie. Le deuxième signifierait que tous les outils de chiffrement largement utilisés pourraient être cassés : même si ce n’est pas une situation enviable, on ne peut pas l’écarter complètement. Une idée géniale peut changer le monde, proposition dangereuse ou souhaitable, cela dépend du point de vue !
Dans les paragraphes suivants, les nombres premiers et les deux problèmes cités vont être brièvement abordés avec leurs applications en cryptographie.

Les nombres premiers

Les exemples de nombres premiers abondent. Il y a déjà 25 nombres premiers plus petits que 100 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. On peut facilement démontrer qu’il y a une infinité de nombres premiers. S’il y avait une liste finie de nombres premiers, appelons P le produit de tous ces nombres premiers.P est évidemment divisible par les nombres premiers de la liste. Mais, quand on divise P + 1 par les nombres de la liste, le reste est 1, donc soit P + 1 est aussi un nombre premier (et il n’appartient pas à la liste), soit il est divisible par un nombre premier qui n’est pas dans la liste. Toute liste finie de nombres premiers peut être ainsi agrandie d’au moins un autre nombre premier, qui sont donc une infinité. Cette simple observation qu’il y a une infinité de nombres premiers est rendue plus explicite par le théorème du nombre premier, moins évident à comprendre. On n’a pas besoin ici de l’énoncer avec précision. Pour simplifier, ce théorème dit que la probabilité qu’un nombre de d- chiffres tiré au hasard soit premier est proportionnelle à 1/d.
Cela permet de faire des estimations telles que : il y a plus que 10 96 nombres premiers qui ont 100 chiffres. Le fait que les nombres premiers soient si nombreux est important en cryptographie. Par exemple, cela implique que si deux personnes différentes tirent au hasard un nombre premier de, disons, 100 chiffres, la probabilité qu’elles tirent le même chiffre est négligeable.
Cet exemple soulève trois questions : Pourquoi générer des nombres premiers aussi grands ? Et pourquoi est-il important que des personnes différentes choisissent des nombres premiers différents ? On reviendra à ces deux questions dans le prochain paragraphe. Ici, on abordera la dernière question, comment fait-on pour tirer au hasard un nombre premier d’une certaine taille ?
On peut facilement distinguer les nombres premiers de ceux qui ne le sont pas (un nombre non premier est appelé composé). Pour savoir si un entier naturel n est ou non un nombre premier, une méthode évidente serait de tester si n est divisible par un entier plus petit que n (notons qu’il suffit de restreindre le test aux entiers inférieur ou égal à racine de n). Bien que pour certains nombres composés le résultat soit vite obtenu, en général on ne peut s’attendre à avoir une réponse rapide, et même pire, pour certains grands nombres, cela peut ne pas marcher du tout, car cela prendrait trop de temps. Une méthode moins évidente, mais plus efficace de savoir si n est un nombre composé est basée sur le petit théorème de Fermat. Ce théorème dit que si p est un nombre premier alors pour tout entier a le nombre ap- a est divisible par p. Donc, si on peut trouver un entier a tel que an- a ne soit pas divisible par n, alors n ne peut être premier (s’il l’était, n diviserait an- a selon le petit théorème de Fermat).
Si on tient compte de deux autres éléments, le petit théorème de Fermat donne une méthode rapide et pratique pour reconnaître si un nombre est composé. Tout d’abord, en appliquant une version légèrement modifiée du théorème, si n est un composé alors, pour la plupart des valeurs de a comprises entre 2 et n - 1,an- a ne sera pas divisible par n. De plus, même si n a des milliers de chiffres, on peut aisément vérifier sur un ordinateur standard si n divise ou non an- a. On se base sur une méthode de calcul appelée exponentiation modulaire, qui a beaucoup d’applications en cryptographie. Développer des méthodes toujours plus rapides pour l’exponentiation modulaire est un sujet de recherche très actuel. Plus précisément, ce que fait l’exponentiation modulaire est de calculer pour tout entier m, b, et e positifs ou nuls, be mod m, autre façon de dire : le reste de la division de be par m.

Les entiers m, b, e sont souvent appelés modulus, base et exposant. Pour savoir si n divise an- a, l’exponentiation modulaire est appliquée au modulus n, à la base a et à l’exposant n, et on teste si (an mod n) - a est divisible par n.
Donc, pour prouver que n est un nombre composé, on tire aléatoirement des valeurs de a dans l’ensemble 2, 3, ... n - 1 et on utilise l’exponentiation modulaire pour vérifier si n divise an- a, jusqu’à ce que l’on trouve une valeur de a pour laquelle ce n’est pas vrai. Si, après de nombreuses tentatives avec des valeurs de a tirées au hasard, il se trouve que n divise toutes les valeurs correspondantes an- a, on n’a pas pu prouver que n est composé. Dans ce cas, puisque si n était composé, on en aurait trouvé la preuve, on assume que n est premier. C’est juste une assertion, ce n’est pas une preuve mathématique que n est premier. Ces prétendus nombres premiers qui ne résultent pas d’un raisonnement mathématique sans faille sont parfois cités comme des nombres premiers industriels. Pour toutes les applications pratiques, le nombre premier industriel est un nombre premier, sauf qu’on n’a pas prouvé sa primalité.
En associant la possibilité de reconnaître rapidement les nombres composés (et donc les nombres premiers industriels) et la densité importante des nombres premiers (Théorème du Nombre Premier), cela conduit à une méthode relativement rapide pour générer des nombres premiers (industriels) aléatoires de n’importe quel nombre d de chiffres : on tire au hasard des nombres de d chiffres jusqu’à ce qu’on tombe sur un nombre premier industriel. D’un point de vue pratique, on a répondu à la troisième question citée plus haut.
Cette méthode pour générer des nombres premiers a troqué la rigueur mathématique contre la facilité de mise en oeuvre. Une preuve rigoureusement mathématique que le résultat est vraiment premier demanderait des méthodes tout à fait différentes. Pour la grande majorité des nombres premiers industriels utilisés en pratique dans des cas de protection de l’information, de telles preuves n’ont pas été obtenues, mais n’apporteraient rien de plus.

Factorisation d’entiers et RSA

La multiplication des nombres premiers est facile. Les enfants savent que 3 * 5 font 15, et apprennent comment se servir des tables de multiplication pour résoudre des problèmes plus difficiles comme 123 * 456 = 56088 en utilisant les méthodes de multiplication de leurs livres d’école. Dans cette méthode, chaque chiffre du premier nombre est multiplié par chaque chiffre du second, et le résultat est ensuite obtenu avec de simples additions. On peut ainsi multiplier rapidement des nombres quelle que soit leur taille ; un ordinateur multiplie des nombres avec des milliers de chiffres en une fraction de seconde. Il existe des méthodes plus rapides, mais nous n’en parlerons pas ici. Faire une multiplication est facile, mais la défaire paraît plus dur : soit un nombre composé positif n, trouver deux entiers plus grands que 1 qui quand ils sont multipliés donnent n. Ces entiers sont appelés les facteurs de n. Par exemple, si n = 15, trouver 3 et 5 (car 3 * 5 =15). Ce problème est connu sous le nom de factorisation d’entiers. Il est en général considéré comme difficile. Comme dit plus haut, la difficulté de la factorisation d’entiers n’a pas été prouvée. Le problème serait facile sur un ordinateur quantique, mais jusqu’à présent on ne sait pas en construire. Plus loin nous allons montrer comment on peut exploiter la prétendue difficulté de la factorisation d’entiers pour la cryptographie et l’état de l’art des algorithmes de factorisation d’entiers sera rapidement exposé.

Application en cryptographie

Supposons que quelqu’un, disons Alice, veuille recevoir un message crypté de la part de quelqu’un d’autre. Une manière élégante de le faire est le système RSA, appelé d’après ses inventeurs Ronald Rivest, Adi Shamir et Leonard Adleman. On appelle cela un système à clé publique, car Alice doit publier une certaine clé, qui permettra à tout le monde d’encrypter les messages qui lui sont destinés. Mais elle gardera secrète la clé privée correspondante qui lui permet de déchiffrer les messages qu’elle reçoit. Évidemment, dans un tel cadre, il doit être impossible de déduire la clé privée d’Alice à partir de sa clé publique, sinon quelqu’un d’autre pourrait effectuer le déchiffrement. Pour RSA cette impossibilité est liée à la difficulté de factoriser les entiers. Voilà comment ça marche. Comme on l’a dit plus haut, Alice peut raisonnablement rapidement générer des nombres premiers aléatoires de n’importe quelle taille. Soient pA et qA les deux nombres premiers distincts qu’elle a générés, alors on peut penser que leur produit nA = pA * qA n’est pas factorisable facilement. Cela signifie qu’Alice peut publier sans risque nA tout en gardant secrets ses nombres premiers pA et qA ; bien que pA et qA soient déterminés de manière unique par nA il n’y a pas de manière simple (connue) de trouver pA et qA à partir de la seule connaissance de nA (à condition que pA et qA soient choisis judicieusement). En plus de pA et qA Alice choisit aussi un entier eA et calcule un entier dA tel que eA * dA - 1 soit divisible à la fois par pA - 1 et qA - 1. Etant donnés eA, pA et qA le calcul de dA peut être effectué très rapidement en utilisant une autre importante méthode de calcul, l’algorithme d’Euclide étendu. L’entier eA est publié par Alice (en même temps que nA), mais elle garde dA secret (en même temps que pA et qA). La paire (nA, eA) est la clé publique d’Alice, constituée du modulus public nA et de l’exposant public eA. La clé secrète ou privée d’Alice consiste en dA, l’exposant secret ou privé. Les nombres premiers pA et qA peuvent en principe être écartés une fois la phase préliminaire effectuée, mais comme on peut les utiliser pour en déduire l’exposant privé dA (puisque eA est public), ils ne doivent jamais être rendus publics. Il s’ensuit donc que pour garantir la sécurité du système RSA, la factorisation du modulus public nA doit être difficile. Mais on n’a pas prouvé que la factorisation de nA est nécessaire pour déduire dA de eA et nA. L’ensemble peut paraître un peu compliqué. Mais Alice ne doit le faire qu’une fois. Ensuite, quiconque connaît sa clé publique peut facilement chiffrer ses messages que seule Alice pourra déchiffrer : soit M un message, M est un entier positif plus petit que nA, le message chiffré E(M) égale MeA mod nA. Le déchiffrement est tout aussi simple : pour déchiffrer E(M) Alice doit calculer (E(M))dA mod nA qui est égal au M original. Les deux processus relèvent de l’exponentiation modulaire (voir plus haut).
Si RSA est utilisé pour échanger du texte, le message doit être converti en nombres entiers. On peut le faire de beaucoup de manières. Par exemple, on peut encoder « a » comme 01, « b » comme 02, etc. jusqu’à « z » comme 26 (« secret » devient « 190503180520 ») ou utiliser d’autres schémas plus efficaces.
En dépit de la simplicité d’apparence de cette formulation et du fait que beaucoup d’efforts ont été faits pour rendre l’exponentiation modulaire aussi rapide que possible, le chiffrement et le déchiffrement sont trop lents pour traiter en temps réel de grandes quantités de données. En pratique, la méthode est typiquement utilisée pour échanger des clés qui seront ensuite utilisées pour un chiffrement beaucoup plus rapide dit à clé symétrique. Les signatures électroniques sont une autre utilisation importante de RSA. Sans précautions, RSA tel que décrit ici est vulnérable à toutes sortes d’attaques. Mais tous ces sujets n’entrent pas dans le thème de cet article.
L’efficacité du système RSA décroît rapidement avec des modulus de plus grande taille. Dans la pratique, on essaie donc de travailler avec le modulus de la plus petite taille possible qui offre un degré acceptable de sécurité : par exemple, un modulus comme n = 15 n’offre aucune sécurité (ses facteurs 3 et 5 sont faciles à trouver), mais un modulus très sûr d’un million de chiffres est pratiquement inutilisable. Trouver le juste milieu entre la sécurité et la faisabilité dépend de l’état de l’art dans les algorithmes de factorisation de nombres entiers et ceci sera commenté plus loin.
Supposons qu’Alice ait reçu une note confidentielle de Bob, comme décrit ci-dessus. Comment va-t-elle répondre à Bob d’une manière confidentielle ? Simplement en utilisant le même principe avec la clé publique de Bob (nB, eB). Donc, Bob doit aussi passer par la phase préliminaire, pour générer ses nombres premiers pB et qB et ses exposants public et privé. Pour des communications plus générales impliquant plus de monde, chacun doit générer ses clés privée et publique et toutes les clés publiques doivent être accessibles pour tous. Cela conduit à la nécessité de ce qu’on appelle Architecture à Clé Publique (PKI) et Autorité de Certification (CA) pour certifier le lien entre les individus et leur clé publique ; mais là aussi cela dépasse le cadre de cet article.
Un dernier point : comment s’assurer que les différents intervenants choisissent des nombres premiers différents ? S’il arrivait que deux personnes, disons Alice et Bob, choisissent un même nombre premier, alors le plus grand commun diviseur (qui peut être très vite calculé grâce à l’algorithme classique d’Euclide) de leurs moduli publics nA et nB révélerait leur nombre premier commun -et donc les clés secrètes d’Alice et Bob- pour qui voudrait se donner la peine de faire le calcul. Pour répondre à ce souci, il suffit de remarquer qu’il y a tant de nombres premiers (supposés d’une certaine taille) que si Alice et Bob utilisent des générateurs corrects de nombres aléatoires, la probabilité que cela arrive est négligeable : celle de gagner à la loterie 10 fois dans un même tirage est plus élevée, même si beaucoup plus que deux personnes sont impliquées.

La preuve que RSA fonctionne

Pour des lecteurs intéressés à plus de détails, on va montrer que le déchiffrement donne bien M. Remplaçons E(M) = MeA mod nA dans la valeur de déchiffrement (E(M))dA mod nA et on obtient (MeA mod nA)dA mod nA

Il s’ensuit que le déchiffrement égale MeA*dA mod nA Pour que le déchiffrement fonctionne, on doit prouver que ceci est égal à M. Les exposants eA et dA étaient construits tels que eA *dA - 1 soit divisible à la fois par pA - 1 et qA - 1. En particulier, il existe un entier k tel que eA *dA -1 = k * (pA - 1), ce que l’on peut écrire comme eA *dA = 1 + k * (pA - 1). On en déduit que le déchiffrement vaut M 1 + k * (pA - 1) mod nA Ce qui est la même chose que M1 *Mk * (pA- 1) mod nA Selon le petit théorème de Fermat et le fait que pA soit premier, on en déduit que pA divise MpA - M et donc M *(M pA - 1 -1). Comme pA est premier et qu’on peut sans risque assumer que pA ne divise pas M, il s’ensuit que pA divise M pA - 1 - 1. Ce qui est la même chose que dire que M pA - 1 mod pA égale 1. Mais si M pA - 1mod pA égale 1, alors M k * (pA - 1) mod pA égale 1k et donc 1.
Le reste de la division du déchiffrement M1 *M k * (pA - 1) mod nA par pA (en utilisant le fait que pA divise nA) vaut
M1 * 1 mod pA qui est
M mod pA
On peut prouver de la même façon (mais éventuellement avec une autre valeur de k) que le reste de la division du chiffrement par qA égale M mod qA.
Comme le reste de la division du déchiffrement par pA et qA est égal à M mod pA et M mod qA respectivement, le théorème du reste chinois nous dit que le reste de la division du déchiffrement par le produit pA*qA=nA est égal à M mod (pA * qA) = M mod nA, mais comme M est positif et plus petit que nA, il s’ensuit que le déchiffrement vaut M lui-même.


Les algorithmes de factorisation d’entiers

Il y en a de deux types : les méthodes spécialisées et les méthodes généralistes. Pour les premières, le temps de réussite dépend principalement des propriétés spéciales du facteur trouvé, pour les autres, il ne dépend que de la taille du nombre à factoriser.
Les moduli utilisés dans le système RSA n’ont a priori pas de facteurs à propriétés spéciales, nous ne parlerons donc pas ici des méthodes spécialisées.
A table of two sieves (www.ams.org/notices/199612/pomerance.pdf) de Carl Pomerance donne une description des algorithmes de factorisation généralistes facile d’accès. Toutes les méthodes connues aujourd’hui sont basées sur la même idée simple, mais peu de progrès substantiels ont été faits depuis l’invention à la fin des années 80 de l’algorithme NFS (Number Field Sieve), actuellement l’algorithme généraliste de factorisation de nombres entiers le plus rapide. Cette absence de progrès pourrait être l’indice que cette simple idée sur laquelle les chercheurs s’acharnent depuis les années 70 est une impasse et qu’il faudrait une idée totalement nouvelle pour permettre de nouveaux progrès.
Voilà tout ce que l’on sait -ou que l’on peut raisonnablement prédire, même si des prédictions dans ce domaine sont plutôt risquées : à la fin des années 70 on a publié un modulus RSA de 129 chiffres, et on a proclamé qu’il faudrait 40 billiards (1 billiard=1015) années pour le factoriser. A l’époque, cela semblait raisonnable. En 1994, le modulus de 129 chiffres fut factorisé. Au milieu des années 90 des moduli de 155 chiffres étaient largement utilisés dans les systèmes RSA. En 1999, le premier modulus à 155 chiffres fut factorisé, et cela a démontré que cette taille n’était plus suffisante pour assurer la sécurité. Des moduli RSA d’environ 200 chiffres ont été récemment factorisés, mais cela demande beaucoup d’investissement, des centaines d’ordinateurs et des mois de calcul. En supposant que l’on dispose de versions plus raffinées des algorithmes actuels (et de plus grande puissance de calcul) on peut s’attendre à ce que des moduli de 300 chiffres puissent être factorisés dans les 10 ou 20 prochaines années. Actuellement, l’utilisation de moduli RSA d’environ 300 chiffres nous semble adéquate, mais on ne peut compter dessus pour le long terme. Des moduli de 500 ou plus chiffres ne semblent pas possibles avec les méthodes actuelles. Mais combien de temps faut-il attendre avant qu’une nouvelle idée géniale ne vienne s’appliquer à ces moduli ? Seul le futur nous le dira.

Les méthodes spécialisées de factorisation

Voici les plus courantes des méthodes de factorisation spécialisées. Si un entier de d chiffres a un facteur de k chiffres, le facteur peut être trouvé en faisant des essais de division pendant des temps proportionnels à 10sup>k * d, ce qui est acceptable si k est petit. La méthode rho de Pollard trouve le même facteur en un temps proportionnel à 10k/2 * d2, ce qui est beaucoup plus rapide si k est grand. La méthode p - 1 de Pollard trouve un facteur premier p en un temps estimé proportionnel à B * d2, où B est le plus grand facteur premier de p - 1. Actuellement, la méthode spécialisée de factorisation la plus rapide est la méthode de la courbe elliptique. Elle permet de trouver des facteurs premiers de plus de 50 chiffres. Le plus grand facteur qu’elle a trouvé jusqu’à présent a 74 chiffres, facteur d’un nombre composé de 162 chiffres.


Les logarithmes discrets et le protocole Diffie-Hellman

Comme dit plus haut, l’exponentiation modulaire peut être utilisée efficacement pour calculer be mod m, le reste de la division de be par m, pour tout modulus m, base b et exposant e. Inverser une exponentiation modulaire c’est le problème où étant donné un modulus m, une base b et un entier positif y plus petit que m, il faut trouver l’exposant e tel que y = be mod m. Ce problème est souvent appelé problème du logarithme discret. Il y a des parallèles remarquables à faire entre le problème du logarithme discret et la factorisation d’entiers ; pour des valeurs de m et b appropriées :

  • on pense que c’est difficile,
  • la difficulté n’a pas été prouvée,
  • ce serait facile sur un ordinateur quantique,
  • la prétendue difficulté peut être utilisée en cryptographie,
  • tous les algorithmes connus pour calculer les logarithmes discrets sont très proches des algorithmes de factorisation de nombres entiers.

Nous allons rapidement exposer une application connue en cryptographie et quelques algorithmes de logarithmes discrets.

Le protocole de Diffie-Hellman

Le protocole de Diffie-Hellman est un protocole d’échange de clés. Il permet aux deux intervenants, disons Alice et Bob, de s’entendre sur une information secrète, en général appelée clé, tout en communiquant sur un canal public. Ensuite la clé sera utilisée par Alice et Bob pour communiquer confidentiellement (et efficacement) sur le même canal public, en utilisant le chiffrement à clé symétrique.
Dans le protocole de Diffie-Hellman, on suppose qu’un modulus m et une base b adéquats sont connus de tous. Alice va simplement tirer au hasard un exposant eA > = 0, utiliser l’exponentiation modulaire pour calculer beA mod m, et transmettre le résultat à Bob. Symétriquement Bob choisit au hasard un exposanteB > = 0, se sert de l’exponentiation modulaire pour calculer beB mod m, et transmet le résultat à Alice. Alice utilise alors son exposant eA et le résultat beB mod m reçu de Bob, pour calculer beB mod m)eA mod m, pendant que Bob utilise son exposant eB et la valeur beA mod m envoyée par Alice pour calculer (beA mod m)eB mod m. Mais la valeur de (beB mod m)eA mod m, calculée par Alice est égale à beB*eA mod m, et c’est aussi le cas pour la valeur de (beAmod m)eB mod m calculée par Bob (car eB * eA = eA * eB). Ainsi, Alice et Bob se seront mis d’accord sur la clé beA*eB mod m.

Si on peut calculer eA à partir des paramètres m et b et de la valeur beA mod m qui est transmise par Alice sur un canal public, alors la clé partagée beA*eB mod m peut être calculée en utilisant l’exponentiation modulaire à partir de m, eA et la valeur beB mod m transmise par Bob. La sécurité du système résulte donc de la difficulté à calculer le logarithme discret eA de la valeur transmise beA mod m. Donc, m et b doivent donc être choisis tels que le calcul de ce logarithme discret soit trop difficile. Inversement, la sécurité dépend aussi de la difficulté à calculer le logarithme discret eB de l’autre valeur transmise (beB mod m). Bien que pour calculer le logarithme discret il suffise de déduire la clé beA*eB mod m des deux valeurs transmises beA mod m et beB mod m (et des paramètres publics m et b), on n’a pas pu prouver qu’il était nécessaire de calculer un logarithme discret : en principe il pourrait y avoir un raccourci qui conduirait à la clé beA*eB mod m en combinant d’une autre façon les valeurs disponibles m, b, beA mod m et beB mod m. Le problème de trouver beA*eB mod m, étant donnés m, b, beA mod m et beB mod m, est connu sous le nom de problème de Diffie-Hellman. Il est au plus aussi difficile que le problème du logarithme discret, mais pourrait être plus facile. Néanmoins, il est habituel de dire que la sécurité du protocole de Diffie-Hellman repose sur la difficulté de problème du logarithme discret (quoiqu’il puisse être plus facile), car si le problème du logarithme discret peut être résolu, alors le protocole de Diffie-Helllman pourra être cassé (i.e. la clé pourra être trouvée) par quiconque à l’écoute de la communication.
Comme d’habitude, la description élémentaire faite ici est vulnérable à toutes sortes d’attaques si des précautions ne sont pas prises. La plus connue (et commune) est l’attaque dite de l’homme du milieu : si Alice et Bob ne sont pas sûrs qu’ils communiquent entre eux, ils pourraient chacun se retrouver à échanger leur clé secrète avec une tierce personne, qui pourrait ensuite avoir un accès facile aux données confidentielles que Bob et Alice veulent échanger.

Les algorithmes de logarithme discret

La difficulté du problème de l’algorithme discret dépend dans une large part des propriétés du modulus m et de la base b, plutôt que juste de leur taille. On suppose que m et b sont soigneusement choisis pour éviter les cas faciles. Si on part du principe que le problème du logarithme discret ne peut être résolu à partir de propriétés spéciales de m ou b, la difficulté du problème est déterminée par la taille de m. Les meilleures méthodes connues dans ce cas sont très proches des méthodes généralistes de factorisation d’entiers. Pour n et m d’approximativement la même taille, l’effort demandé pour factoriser un modulus RSA n est comparable à celui pour résoudre le problème (général) du logarithme discret avec un modulus m. Des paramètres d’une taille simulaire doivent donc être utilisés pour RSA et le protocole de Diffie-Hellman. Comme dans le cas de la factorisation de nombres entiers, il n’y a pas de preuve mathématique que tout problème pratique de logarithme discret soit réellement difficile.

Autres problèmes de logarithme discret

Les premières applications du problème du logarithme discret proposées en cryptographie utilisaient le cas simple décrit plus haut, basé sur des nombres entiers. Ensuite, on réalisa que d’autres instances du problème du logarithme discret impliquant d’autres structures mathématiques étaient aussi intéressantes pour des applications cryptographiques et qu’elles pouvaient même présenter des avantages comparés aux approches plus traditionnelles avec les nombres entiers. Les systèmes de chiffrement à courbe elliptique sont bien connus, ils utilisent des structures mathématiques avancées appelées courbes elliptiques. Malheureusement, comme avec les entiers, il n’y a pas de preuve de la difficulté du problème du logarithme discret des courbes elliptiques.

Les méthodes spéciÉviter les cas faciles pour le problème du logarithme discret

Si le modulus m est composé, alors en conséquence du théorème du reste chinois, le problème du logarithme discret peut être réduit au problème du logarithme discret concernant les facteurs premiers de m. Dans certaines applications, m est construit de telle façon que sa factorisation est difficile à trouver, mais il est plus habituel de choisir un modulus m premier. Ici on suppose que m est premier.
Le plus petit entier positif l pour lequel bl mod m égale 1 est un nombre important : c’est l’ordre de b modulo m. Résoudre le problème du logarithme discret pour une valeur y consiste à trouver une valeur e telle que be mod m égale y. En écrivant que e=k*l+r pour tout entier r (0<= r < l), il s’ensuit que br mod m égale y parce que bl ? mod m égale 1. Le problème du logarithme discret peut être alors résolu en comparant y aux l valeurs b0 mod m, b1/sup> ? mod m, ... , bl ?- ?1 mod m, une des valeurs doit correspondre si le problème a une solution. Pour rendre impossible cette recherche exhaustive, l’ordre l de b modulo m doit être suffisamment grand. De même que pour la méthode des essais de division pour la factorisation d’entiers, le temps requis est proportionnel à 10k si e est un nombre de k chiffres. Une variante de la méthode rho de Pollard s’applique ici aussi, réduisant 10k à 10k/2. Mais, il y a d’autres contraintes quant à l’ordre l de b modulo m.
La méthode de Pohlig-Hellman suggère que la difficulté du problème du logarithme discret n’est pas déterminée par la taille de l lui-même, mais par la taille du plus grand facteur premier de l. Par conséquence, la base b est alors choisie avec la condition supplémentaire que l’ordre l de b modulo m est premier. Le fait que l’ordre l de b modulo m est un facteur de m - 1 complique encore un peu plus le paysage. C’est une conséquence du petit théorème de Fermat et du fait que m est premier.
Pour résumer, le modulus m est choisi premier, tel que m-1 ait un facteur premier l de k chiffres où k soit suffisamment grand pour que l’effort de calcul proportionnel à 10k/2 soit irréaliste et b est choisi tel que son ordre modulo m égale l. À présent, si l’exposant e est choisi au hasard entre 0 et l-1, le calcul du logarithme discret de y = (be mod m) ne sera, probablement pas trop facile !


Conclusion

Pour une personne extérieure, il peut sembler étrange que, dans le fond, la sécurité de presque toutes les communications électroniques soit basée sur quelques problèmes mathématiques qui ne sont pas bien compris. L’argument de sécurité repose uniquement sur des années de tentatives échouées et non sur un raisonnement mathématique rigoureux. Cela peut être gênant pour certains, mais ne semble pas être un problème pour ceux qui le mettent en pratique. D’autres méthodes basées sur d’autres problèmes mathématiques ont été proposées. Mais ils n’ont jamais atteint le niveau de popularité des systèmes basés sur la factorisation ou les logarithmes discrets, et ces problèmes sont regardés avec encore plus de scepticisme que ceux dont on a parlé ici. À présent, tout ce que nous pouvons faire c’est de rester attentif à de meilleures alternatives et d’espérer que les ordinateurs quantiques ne pourront pas être construits.

Traduction de l’original anglais par Jacqueline Dousson, Domaine IT



Cherchez ...

- dans tous les Flash informatique
(entre 1986 et 2001: seulement sur les titres et auteurs)
- par mot-clé

Avertissement

Cette page est un article d'une publication de l'EPFL.
Le contenu et certains liens ne sont peut-être plus d'actualité.

Responsabilité

Les articles n'engagent que leurs auteurs, sauf ceux qui concernent de façon évidente des prestations officielles (sous la responsabilité du DIT ou d'autres entités). Toute reproduction, même partielle, n'est autorisée qu'avec l'accord de la rédaction et des auteurs.


Archives sur clé USB

Le Flash informatique ne paraîtra plus. Le dernier numéro est daté de décembre 2013.

Taguage des articles

Depuis 2010, pour aider le lecteur, les articles sont taggués:
  •   tout public
    que vous soyiez utilisateur occasionnel du PC familial, ou bien simplement propriétaire d'un iPhone, lisez l'article marqué tout public, vous y apprendrez plein de choses qui vous permettront de mieux appréhender ces technologies qui envahissent votre quotidien
  •   public averti
    l'article parle de concepts techniques, mais à la portée de toute personne intéressée par les dessous des nouvelles technologies
  •   expert
    le sujet abordé n'intéresse que peu de lecteurs, mais ceux-là seront ravis d'approfondir un thème, d'en savoir plus sur un nouveau langage.