Petite histoire de la cryptographie: Sur la piste de la cryptographie asymétrique

Nous vous proposons dans une série d'articles de revoir les fondements de la cryptologie, de passer en revue les grandes étapes de son développement, du Chiffre de César à la cryptologie asymétrique, en insistant sur le rôle clef joué par le chiffrement dans le Bitcoin et sur les promesses de l’ordinateur quantique.

Notre série doit beaucoup à l’ouvrage de vulgarisation scientifique Histoire des codes secrets de Simon Singh dont nous avons tiré une grande majorité de nos exemples.

Adi Shamir, Ronald Rivest et Leonard Adleman: les créateurs de l'algorithme de cryptographie asymétrique, utilisé dans le commerce électronique.

Chiffrer un message grâce à un calculateur est assez similaire aux méthodes traditionnelles. Là où l’ordinateur innove c’est qu’il peut être programmé pour simuler l’action d’une machine à chiffrer virtuelle d’une grande complexité et impossible à réaliser «en vrai». Il est par ailleurs bien plus rapide, les brouilleurs électroniques opérant beaucoup plus efficacement que les brouilleurs mécaniques. Il permet d’augmenter la puissance de calcul. Enfin, l’ordinateur brouille des chiffres plutôt que des lettres, travaillant sur des nombres binaires (des suites de 0 et 1 appelés «bits» en anglais). Une fois les lettres du message converties en chiffres binaires, le codage peut commencer. Celui-ci s’effectue cependant toujours selon les principes élémentaires de substitution et de transposition.

Crypter un message requiert dans un premier temps de convertir ce message selon un protocole de chiffres binaires tel que l’American Standard Code for Information Interchange (ASCII) par exemple qui assigne à chaque lettre de l'alphabet un nombre binaire à 7 chiffres:

Faisons l’essai avec le mot «SECRET». Ce mot converti grâce à l’ASCII donne le résultat suivant:

SECRET = 1010011 1000101 1000011 1010010 1000101 1010100

Nous pouvons alors lui appliquer un chiffre de transposition, en permutant les chiffres du message par exemple, ou un chiffre de substitution, qui comme nous l'avons vu nécessite une clef partagée par l'expéditeur et le destinataire. Le mot-clef, comme le message, est converti via l’ASCII. Le message chiffré naît de l'addition binaire du message et du mot-clef convertis. Rappelons que l’addition binaire de deux chiffres identiques, 0 ou 1, donne 0 et que l’addition binaire de deux chiffres différents donne 1. 

Ainsi, crypter le mot «SECRET» grâce au mot-clef «BINAIRE» donne le résultat suivant :

Avec la démocratisation des ordinateurs commerciaux dans les années 1950 se pose la question de la standardisation du cryptage pour permettre aux entreprises de communiquer entre elles en toute confidentialité. L'un des algorithmes de chiffrement les plus reconnus, en lice pour devenir la norme accréditée par le National Bureau of Standards américain, est développé pour IBM au début des années 1970 par Horst Feistel, un Allemand naturalisé Américain, sous le nom de Lucifer. 

Lucifer traduit le message en une suite de nombres binaires répartie en blocs de 64 bits. Le cryptage s’effectue séparément sur chaque bloc. Chaque bloc de 64 bits est séparé en deux demi-blocs de 32, appelés Gauche⁰ et Droite⁰ (G⁰ et D⁰). On applique à D⁰ une opération de substitution complexe. Après cette intervention, le D⁰ est ajouté au G⁰ pour trouver un nouveau bloc de 32 bits appelé D¹. Le D⁰ d'origine est rebaptisé G¹. Cet enchaînement d'opérations constitue un cycle. Ce processus est répété une deuxième fois, partant des demi-blocs G¹ et D¹ pour obtenir les blocs G² et D², jusqu’à 16 fois en tout. Le texte chiffré peut alors être envoyé. Il sera déchiffré en effectuant les opérations inverses.

Les modalités précises de la fonction de transformation peuvent varier, et sont déterminées par une clef partagée par l'expéditeur et le destinataire. Le même message peut donc être crypté selon une infinité de possibilités, en fonction de la clef choisie. Ces clefs sont de simples nombres. L'expéditeur et le receveur s'entendent sur ce nombre, puis l'expéditeur rentre ce nombre-clef et le message en clair dans le système Lucifer. Le destinataire, lui, n'a qu'à rentrer la même clef et le message crypté dans sa version de Lucifer pour déchiffrer le message. 

Il semblait inévitable que Lucifer, l'un des crypto-systèmes les plus sûrs du moment, s’impose comme la norme de communication entre les entreprises. Mais la National Security Agency (NSA) s'oppose aux travaux de Feistel sous prétexte qu’ils offrent un système de cryptage trop sophistiqué qu’elle n’est pas en mesure de pouvoir briser, le nombre de clefs possibles étant infini. La NSA exige que le nombre de clefs soit limité à environ 100 000 000 000 000 000 (soit une clef de chiffrement de 56 bits, ce nombre s'écrivant en 56 chiffres binaires). Une telle clef assure une confidentialité suffisante au public, aucun organisme privé ne disposant d'un ordinateur capable de vérifier un tel nombre de clefs en un temps raisonnable. Le remodelage du système Lucifer est adopté comme standard officiel en 1976, sous le nom de Data Encryption Standard (DES).

L'adoption du DES impose une norme qui encourage les entreprises à recourir à la cryptographie pour assurer la sécurité de leurs échanges d’information. Cependant, bien que le DES résiste aux attaques, trop puissant pour les ordinateurs civils, il subsiste un défi de taille, celui de la distribution des clefs.

Mettons ce défi en image. Prenons trois personnages fictifs nommés Alice, Bob et Eve (ces noms sont une convention informatique). Alice veut envoyer un message confidentiel à Bob et Eve les espionne. Comment permettre à Alice d’envoyer son message malgré la surveillance d’Eve qui met en péril le partage de la clef? La communiquer par téléphone ou par courrier? Bien trop hasardeux. La remettre en main propre? Cela est certes sécurisé mais quelle perte d’efficacité! C’est pourtant l’option longtemps choisie par le gouvernement américain qui confiait la distribution des clefs à l’agence Communication Security dont les crypto-gardes acheminaient tous les jours des milliers de clefs cadenassées dans des valisettes. Les premiers films de James Bond n’ont rien inventé !

D’une époque à l’autre, ce problème de la distribution des clefs demeure un défi constant des cryptographes. Si la cryptographie peut désormais compter sur des chiffres impénétrables, elle doit toujours faire face à ce problème. S’en remettre à un tiers pour communiquer la clef introduit une lourdeur logistique et affaiblit la sécurité du code. Vers 1975, une bande d’intrépides – Whitfield Diffie, Martin Hellman et Ralph Merkle – trouve la solution, mettant au point un système de chiffrement qui résout le problème de la distribution des clefs. C’est la plus grande découverte en cryptologie depuis l’invention du Chiffre de César.

Ralph Merkle, Martin Hellman et Whitfield Diffie

Hellman, professeur à Stanford, Diffie et Merkle sont tous les trois travaillés par les bouleversements que l’ARPANet, l’ancêtre d’Internet, et le développement des ordinateurs personnels annoncent. Très tôt se pose à eux la question d’un système de cryptage capable d’assurer la confidentialité des transactions en ligne, le volume des informations échangées rendant la distribution des clefs impossible. Ensemble ils se penchent sur un type particulier de fonctions mathématiques: les fonctions à sens unique, c’est-à-dire les fonctions qui ne sont pas réversibles. Rappelons que la plupart des fonctions sont réversibles, elles peuvent se faire dans un sens puis se défaire: si l’on double un nombre par exemple, on peut aisément retrouver le nombre d’origine à partir de son double.

Revenons un instant sur l'arithmétique modulo, un domaine riche en fonctions à sens unique, domaine dans lequel les mathématiciens considèrent un ensemble fini de nombres arrangés en boucle, un peu comme les heures d’une horloge. 

Ci-dessous une horloge dont les heures sont de modulo 12: 

Sur cette horloge, pour calculer 3 + 4, nous partons de 3 et avançons de 4 places, pour arriver à 7, comme en arithmétique normale. Mais pour calculer 10 + 4, nous effectuons un tour complet de l'horloge pour arriver à 2. On écrit alors que: 3 + 4 = 7 (mod 12) et 10 + 4 = 2 (mod 12). Dans la vie de tous les jours nous recourons souvent à l’arithmétique modulo. Ainsi, si à 9h du matin nous prenons un rendez-vous qui aura lieu 6h plus tard, nous disons que cette rencontre aura lieu à 3h de l’après-midi aussi bien qu’à 15h. 

Pour simplifier les calculs modulo, les mathématiciens effectuent d'abord le calcul en arithmétique normale, divisent le résultat par le modulo, et le reste de cette division constitue le résultat. 

Ainsi, pour trouver le résultat de 12 x 14 (mod 9), nous procédons comme suit:

12 x 14 = 168

168 / 9 = 18, reste 6

12 x 14 = 6 (mod 9)

Les fonctions effectuées en arithmétique modulo se transforment parfois en fonctions à sens unique. On peut s'en rendre compte en comparant une fonction simple en arithmétique normale et en arithmétique modulo. 

Prenons par exemple la fonction 2^x, qui multiplie 2 par lui-même x fois. Si x = 3:

2^x = 2³ = 2 x 2 x 2 = 8

Cette fonction transforme 3 en 8, et plus la valeur de x croît, plus le résultat croît. Si l'on nous donne le résultat de l'opération, il est facile d’en déduire x. 

Ceci est beaucoup moins évident en arithmétique modulo. Si l'on nous dit par exemple que 2^x en modulo 9 est égal à 1, et que l'on cherche la valeur de x, Il faut alors procéder par calcul de force brute, c’est-à-dire tester différentes solutions. Au contraire de l'arithmétique normale, nous ne pouvons pas fonctionner par intuition ou par tâtonnement, et nous n'avons d'autre choix que de constituer une table avec diverses valeurs attribuées à x, jusqu'à ce que l'on tombe sur la bonne solution, x = 6: 

Ce travail, assez fastidieux pour des petits nombres, devient extrêmement pénible avec une fonction comme 517^x (mod 31 745). C'est un exemple de fonction à sens unique, car si l'on peut attribuer une valeur à x et calculer le résultat de cette fonction très rapidement, retrouver la valeur de x qui donne par exemple 21 345 prendra beaucoup plus de temps. 

En 1976, après deux années de recherche consacrées aux fonctions à sens unique, Martin Hellman voit la lumière et résout le problème de l'échange des clefs. Il prouve qu'Alice et Bob peuvent convenir d'une clef sans se rencontrer, et ce malgré la surveillance d'Ève. 

Son idée repose sur une fonction de la forme Y^x (mod P). D'abord, Alice et Bob se concertent sur les valeurs de Y et P, avec deux restrictions: P doit être un nombre premier (qui n'a pas d'autre diviseur que lui-même et 1) et Y inférieur à P. Les valeurs de Y et P ne sont pas secrètes, Alice peut téléphoner à Bob pour lui communiquer ces valeurs, par exemple Y = 5 et P = 13, malgré la surveillance d'Ève. Alice et Bob ont maintenant convenu de la fonction 5^x (mod 13). Ils peuvent alors entamer le processus visant à établir une clef secrète sans se rencontrer, en travaillant en parallèle :

Bien qu’Ève espionne Alice et Bob, elle ne connaît que les éléments suivants: la fonction 5^x (mod 13), le nombre α = 12 qu'Alice envoie à Bob, et le nombre β = 9 que Bob envoie à Alice. Pour trouver la clef, Ève doit soit faire comme Bob, c'est-à-dire calculer la clef comme étant le résultat de α^B (mod 13), soit faire comme Alice, donc calculer la clef comme étant le résultat de β^A (mod 13). Mais Ève ne connaît ni A, ni B. Il faut qu’elle trouve A et B à partir des valeurs d'α et β mais la fonction qui transforme A en α et B en β est à sens unique, et s'il est facile pour Alice et Bob de transformer A en α et B en β, il est très difficile pour Ève d'inverser le procédé, surtout si les nombres sont très grands (comme c'est le cas pour un chiffrement en DES).

La solution d’Hellman permet à Alice et Bob de convenir d’un secret au cours d’une conversation publique. Lorsque les travaux de Diffie-Hellman-Merkle sont rendus publics en 1976, ils prennent le monde de la cryptographie par surprise.

Mais si cette solution d'échange de clefs est une révolution dans l'histoire de la cryptographie, elle est encore perfectible. En effet, imaginons qu'Alice habite à New York, et Bob à Tokyo. Si Alice veut envoyer un message crypté à Bob, elle a besoin de s’accorder sur la clef avec Bob, par téléphone ou par e-mail. Mais Bob dort probablement à ce moment là, et Alice doit attendre son réveil, ce qui ralentit l’opération. 

Pendant que Martin Hellman élabore sa solution d'échange de clefs, Diffie, poursuivant une piste différente, réfléchit à un nouveau type de chiffre qui incorpore une clef asymétrique. 

Depuis l’origine de la cryptologie, les différentes techniques de chiffrement ont toujours été symétriques, c’est-à-dire que le procédé de déchiffrement est simplement l'inverse du procédé de chiffrement. Ainsi, la clef de la machine Enigma est la même pour crypter et décrypter le message, le déchiffrement  étant en fait l’action de défaire le chiffrement. Il en est de même pour le chiffrement DES qui utilise une clef pour opérer les 16 tours de brouillage, et la même clef pour exécuter les 16 tours en sens inverse permettant le déchiffrement.

Au contraire, dans un système à clef asymétrique, la clef de chiffrement utilisée par l'émetteur et la clef de déchiffrement utilisée par le destinataire du message sont différentes. Ce concept à lui seul est révolutionnaire. Alice peut ainsi créer sa propre paire de clefs: une clef de chiffrement et une clef de déchiffrement. Elle garde secrète sa clef de déchiffrement, qu’elle appelle sa clef privée. Mais elle peut diffuser sa clef de chiffrement de façon à ce que tout le monde y ait accès: c’est sa clef publique. Si Bob veut envoyer un message à Alice, il va se servir de la clef publique d'Alice pour crypter son message, qu'il envoie à Alice. Alice utilise alors sa clef privée pour déchiffrer le message. D'ailleurs, n'importe qui peut envoyer un message crypté à Alice, en se servant de sa clef publique, et Alice n'a besoin que de sa clef privée pour les déchiffrer.

La grande force de ce système de chiffre à clef asymétrique est qu'il se défait de la contrainte que représentait l'échange de Y, P, α et β dans le schéma de Diffie-Hellman-Merkle. Bob n'a plus besoin d'attendre cet échange avec Alice pour crypter son message et inversement. Au contraire, Alice et Bob peuvent afficher leurs clefs publiques librement puisqu’elles ne servent pas au déchiffrement des messages. Pour le déchiffrement, le destinataire du message n’a besoin que de sa clef privée, qui comme son nom l’indique, n’est connue que de lui seul. 

Il restait cependant à mettre au point une façon d’appliquer cette découverte, trouver une fonction mathématique qui permette d’engendrer un couple de clefs privée/publique indépendantes l’une de l’autre. En effet, Alice doit pouvoir créer une clef publique qui soit une fonction permettant aux expéditeurs des messages qu’elle reçoit de les crypter, et une clef privée restée secrète qui lui permette, à elle seule, de les décrypter. Cette fonction doit être à sens unique mais réversible par Alice sous certaines conditions. Les deux clefs ne peuvent être déduites l’une de l’autre. 

Quand Diffie publie les grandes lignes de son projet en 1975, il est confiant et pense pouvoir parvenir rapidement à une solution d’application. Mais la solution se fait attendre. Le chiffre asymétrique, venant à bout du problème de la distribution des clefs, demeure théorique. 

La résolution du problème vient d’ailleurs. En août 1977, Ronald Rivest, Adi Shamir et Leonard Adleman, tous chercheurs au MIT, mettent au point un algorithme de cryptographie baptisé de leurs initiales, RSA, qui combine pour la première fois l’utilisation d’une clef privée et d’une clef publique. Le trio s’était initialement intéressé aux recherches de Diffie pour prouver qu’il était impossible de mettre au point un système cryptographique à clef publique. Ils échouèrent en découvrant que ce système était en fait réalisable. Le chiffre RSA marque les débuts de la cryptographie asymétrique et s’impose comme le chiffre le plus influent de la cryptographie moderne.

Au cœur du système RSA, Rivest introduit un nombre N, la clef publique, qui rend la fonction à sens unique réversible sous certaines conditions par le détenteur de la clef privée. Le chiffrement asymétrique persiste. N est une composante variable: chaque personne peut choisir pour N sa propre valeur, personnalisant ainsi la fonction de chiffrement.

Revenons à Alice et Bob. Pour obtenir N, Alice doit multiplier deux nombres premiers de son choix, p et q, qu’elle garde pour elle. Alice choisit p = 14 879 et q = 19 697, ce qui donne N = 14 879 X 19 697 = 293 071 663. Ce nombre N devient la clef publique d'Alice, qu'elle peut afficher ouvertement. Si Bob veut crypter un message pour Alice, il se procure sa clef publique, soit 293 071 663, et l'insère ainsi que le corps de son message dans la fonction à sens unique utilisée par le RSA, elle aussi publique. Bob note le résultat et peut l'envoyer à Alice en toute sécurité, car le message a été chiffré par une fonction à sens unique, indéchiffrable par un tiers. 

Pour lire les messages qu'on lui adresse, Alice doit avoir un élément lui permettant d'inverser la fonction à sens unique. Dans le système RSA, la fonction à sens unique peut être inversée par quelqu'un qui connait les valeurs de p et q, les deux nombres premiers qui ont été multipliés pour donner N. Alice a bien affiché ouvertement sa clef publique N = 293 071 663, mais elle n'a pas révélé les valeurs de p et q. Seule Alice dispose de cette information pour décrypter les messages. Si N constitue la clef publique, les nombres p et q forment la clef privée. Tant que la clef privée reste secrète, la clef publique peut être diffusée, permettant de réutiliser la même paire de clefs indéfiniment sans compromettre la sécurité. 

En fait, si N est suffisamment grand, il est pratiquement impossible d'en déduire p et q, ceci étant l’un des aspects les plus caractéristiques du chiffre asymétrique RSA. Alice a crée N en multipliant p et q, deux nombres premiers, et cette action en elle-même constitue une fonction à sens unique. 

Notons que l’on peut utiliser le couple clef publique/clef privée dans les deux sens: crypter un message grâce à la clef publique et le décrypter grâce à la clef privée, ou crypter un message grâce à la clef privée et le décrypter grâce à la clef publique. Le système RSA permet donc à Alice d'envoyer un message à Bob en utilisant la clef publique de ce dernier. Bob pourra ensuite décrypter le message grâce à sa clef privée. Le RSA permet de crypter un message et d’authentifier l’émetteur du message.

Si N est assez grand, le protocole de cryptage RSA se révèle tout à fait incassable, garantissant aux informations échangées une sécurité infaillible. RSA exploite la difficile factorisation des grands nombres premiers. Pour N = 293 071 663, on trouve aujourd'hui rapidement les facteurs premiers à l'aide d'un programme informatique. Avec N = 114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541 par exemple, la décomposition en facteurs premiers est bien plus laborieuse. En effet, il n’existe pas aujourd’hui d’algorithme suffisamment rapide pour résoudre la question de la factorisation.   

La cryptographie à clef publique RSA, devenue un système universel, s’est imposée comme la façon la plus sûre de protéger le flux constant d’informations qui circule. Elle se cache derrière la plupart des transactions sécurisées qui ont lieu sur le Net. Depuis près de 40 ans, toutes les tentatives de casser ce chiffre ont échoué. Mais l’algorithme RSA n’offre pas une sécurité inconditionnelle. Il serait sage de garder en tête que tant que l’on ne peut prouver mathématiquement la sûreté du RSA, il n’est pas à l’abri d’une attaque. Plusieurs fois dans l’histoire de l’espionnage un système de codage considéré comme inviolable par ses utilisateurs était en réalité décodé en secret par ses ennemis. La découverte d’une façon rapide de factoriser N, avec l’augmentation de la puissance de calcul des ordinateurs par exemple, viendrait à bout de la sécurité du crypto-système RSA.

Lire aussi:

• Petite histoire de la cryptographie: de Jules César à l’ordinateur quantique
• Petite histoire de la cryptographie: de la machine Enigma à l’ordinateur

• À propos
• Articles récents

Les Experts

Olivier Ezratty, Rodrigo Sepulveda, Gregory Renard, Laurence Faguer, retrouvez les analyses de nos experts dans les deeptech, investissement, IA, retail, santé...

Pour contacter la rédaction: redaction@frenchweb.fr

Pour plus d'informations sur nos abonnements, merci de nous contacter à abonnement@frenchweb.fr

Vous souhaitez contribuer régulièrement en tant qu'expert sur FRENCHWEB.FR, merci de nous contacter à redaction@frenchweb.fr

Les derniers articles par Les Experts (tout voir)

• Ask A VC : comment modéliser un compte de résultat — Partie 6/6 : analyse de sensitivité - 21/05/2024
• Ask A VC : comment modéliser un compte de résultat — Partie 3/6 : les Coûts Fixes - 16/01/2024
• Question à un VC : Pourquoi les marges unitaires sont-elles si importantes pour votre modèle d’affaires? - 13/11/2023