Depuis de début des articles, nous avons vu que la plus grande difficulté pour préserver le clé est de la conservé cachée des espions. La scytale perdue ne permet pas facilement l’enroulement de la lanière. Le mot clé de César oublier rend le message indéchiffrable. Le carnet journalier d’Enigma subtiliser et les messages ne sont plus secrets dans quelques semaines.
Depuis la seconde guerre mondiale, les mathématiciens ont commencés à mettre leur grain de sel. Comment transmettre une clé pouvant être interceptée mais qui ne permet pas a un espion lambda de déchiffrer les messages ?
Ce n’est qu’en 1974 que deux cryptographes et mathématiciens, travaillant chacun de leurs côtés, vont se rencontrer et concevoir la plus belle clé de cryptage avec un outil mathématique connu depuis l’Antiquité.
Quand Alice et Bernard s’affichent en public
Whitfield Diffie et Martin Hellman, respectivement nés en 1944 et 1945, furent mis en contact suite à la conférence de Diffie, sur les enjeux de la cryptographie, dans les locaux d’IBM. Sans plus attendre, il prit l’avion et traversa le continent pour rencontrer le professeur Hellman qui travaillait sur le même sujet : l’utilisation de clés publiques ou privées.
Un petit exemple expliquant la contrainte de clés privées :
Alice souhaite transmettre un objet à Bernard sans qu'Ève - l'espionne - puisse voir ce que c'est.
Alice introduit l'objet dans une mallette hermétique et met un cadenas dont elle seule possède la clé.
Bernard reçoit la mallette, mais ne pouvant l'ouvrir, ajout un second cadenas dont lui seul possède la clé.
De retour chez Alice, elle retire son cadenas de la mallette pour la retournée à Bernard.
Celui-ci retire son cadenas et obtient l'objet qu'Alice voulait lui transmettre.
A aucun moment, Ève n'a pu voir l'objet, car elle n'a jamais pu avoir en sa possession aucunes des deux clés.
Malheureusement, pour crypter et décrypter un message, se fonctionnement n'est pas adapter.
Supposons qu'Alice souhaite inviter Bernard à manger ce midi : VIENS MANGER CE MIDI qu'elle souhaite chiffrer avec le mot clé HFSUGTAKVDEOYJBPNXWCQRIMZL.
Elle envoie donc le message codé suivant : RVGJWYHJAGXSGYVUV
De son côté, Bernard chiffre ce message avec la clé CPMGATNOJEFWIQBURYHXQDZKLV et retourne : YDNEZLOECNKHNLDQD
Alice, récupérant le message doublement chiffrer, le déchiffre avec sa clé et renvoie : MJQKYZLKTQHAQZJUJ
Bernard n'a plus alors qu'à le déchiffrer avec sa clé pour découvrir l'invitation : CIUXRWYXFUSEUWIPI
Malheureusement, le chiffrement et déchiffrement n'est pas commutatif. Il faut absolument déchiffrer dans l'ordre inverse du chiffrement : Chiffrement d'Alice - Chiffrement de Bernard - Déchiffrement de Bernard - Déchiffrement d'AliceL’idée était de trouver un moyen de transmettre une information, interceptable par un espion, mais ne lui donnant pas la possibilité d’utiliser cette information pour déchiffrer les messages. L’outil le plus efficace pour concevoir une clé non réversible sera trouvé en 1976, avec la collaboration supplémentaire de Ralph Merkle,.
Le modulo sur l’horloge
La lecture de l’heure sur une horloge peut se faire de deux façons différentes l’après-midi. A l’anglaise, les heures se lisent comme dans la matinée : il est 2h de l’après-midi. A la française, les heures se lisent sur 24h, il est donc 14h. Sur l’horloge, 14h correspond à 2h de l’après-midi. En mathématique, on dit que 14 est égale à 2 modulo 12. C’est à dire que si l’on continue de compter sur un cadran à 12 graduations, alors 2, 14, 26, 38 valent la même valeur 2, dans ces 12 graduations.
Appliqué à l'arithmétique, cette valeur est le reste de la division par 12. 2 = 0 x 12 + 2 14 = 1 x 12 + 2 26 = 2 x 12 + 2 38 = 3 x 12 + 2 Ce modulo s'écrit : 2, 14, 26, 38 = 2 (mod 12) Ainsi 9 + 7 = 16 = 4 (mod 12)
Ce premier outil permet de ne pas savoir de quel nombre on part, même si l’on connait le modulo. Pour 2 (mod 12), étions-nous partis de 14, 38 ou même 254 ?
La fonction exposant
L’autre outil qui résout le problème de Whitfield et Martin est la fonction exposant. Comme par exemple la fonction 3x, où si x = 2 alors 32 = 3 x 3=9. Coupler avec le modulo, nous obtenons :
| x | 1 | 2 | 3 | 4 | 5 | 6 |
| 3x | 3 | 9 | 27 | 81 | 243 | 729 |
| 3x (mod 7) | 3 | 2 | 6 | 4 | 5 | 1 |
La fonction exposant modulo est née : Yx (mod P), où P doit être premier et Y inférieur à P. Ces deux valeurs peuvent être transmissent entre Alice et Bernard, même en clair. Ève n’aura pas la possibilité de décrypter leurs messages.
Alice et Bernard se sont mis d'accord sur les valeurs Y = 7 et P = 11 Alice choisis sa clé secrète a = 3, tandis que Bernard choisis b = 6 Par la fonction exposant modulo, ils obtiennent les clés : - Alice : 7a (mod 11) = 73 (mod 11) = 343 (mod 11) = 2 - Bernard : 7b (mod 11) = 76 (mod 11) = 117 649 (mod 11) = 4 Alice envoie son résultat (A = 2) à Bernard et reçoit celui de Bernard (B = 4). Ève intercepte le 2 d'Alice et le 4 de Bernard. Alice et Bernard calcul à présent la clé unique avec les valeurs choisies et transmises. - Alice : Ba (mod 11) = 43 (mod 11) = 64 (mod 11) = 9 - Bernard : Ab (mod 11) = 26 (mod 11) = 64 (mod 11) = 9 C'est la même clé, qu'Ève aura du mal à trouver.
Cette technique de calcul à sens unique revient à mélanger deux pots de peintures. Même si Ève connait les caractéristiques de la couleur azur d’Alice et la bordeaux de Bernard, seul Alice et Bernard savent la quantité d’azur et de bordeaux qu’ils mélangent dans le pot final. Et heureusement pour eux, Ève ne réussira pas à dissocier les couleurs ainsi mélangées.
RSA – Rivest, Shamir & Adleman
Alors que que l’échange de clé de Diffie-Hellman-Merkle permet de s’affranchir d’une interception de clé, les deux parties devaient tout de même effectuer un échange avant de chiffer un message. L’idéal serait que seule Alice construise une clé utiliser par Bernard sans avoir besoin d’en comprendre la conception.
Un trio de jeune diplômés du MIT se penche sur cette question et tente en vain de trouver la méthode infaillible. Ron Rivest et Adi Shamir conçoivent tandis que Leonard Adleman démonte chaque proposition. Ce n’est qu’en avril 1977, que Rivest, Shamir et Adleman purent breveter leur révolutionnaire méthode de construction des clés : la clé publique et la clé privée.
Le nom du brevet est RSA et non ARS comme nous pourrions nous y attendre, car les auteurs sont habituellement mentionnés par ordre alphabétique. Leonard Adleman, ne se considérant pas comme un contributeur majeur, demanda à ce qu’il ne soit pas mentionné comme co-auteur de l’article, mais R. Rivest l’inscrivit comme troisième auteur.
Construction et utilisation des clés : 1. Choisir deux nombres premiers p et q distincts (ex. 3 et 11) 2. Calculer leur produit n (ex. n=3*11=33) 3. Calculer l'indicatrice d'Euler φ(n)=(p-1)(q-1) (ex. : φ(n)=(3-1)(11-1)=2*10=20) 4. Choisir un entier naturel e - exposant de chiffrement - premier avec φ(n) et strictement inférieur à φ(n) (ex. e=3 ; 3 et 20 étant premiers entre eux) 5. Calculer d, l'inverse modulaire e par multiplication modulo φ(n) (ex. d=7 car e*d=3x7=1 (mod 20)) La clé publique est le couple (n, e) et la clé privée est d
Pour chiffrer un message M < n, il suffit de calculer C = Me (mod n)
Le déchiffrement d’effectue par le calcul : M=Cd (mod n)
Cette méthode ne demande pas à Alice et Bernard de se coordonner sur leurs choix de nombre au préalable, car seule Alice communique une clé que tout le monde peux utiliser. Elle peut même inscrire sur sa carte de visite sa clé publique sans qu’Ève puisse déchiffrer les messages qu’Alice reçoit.
Une analogie simple est celle de la boîte aux lettres. Tout le monde peut mettre une lettre dans la boîte aux lettres d’Alice, mais seule Alice – possédant la clé privé – peut accéder à son contenu.
Conclusion
Actuellement, le système RSA est le plus utiliser. Il est considéré comme étant le plus sûr et est donc intégrer dans des milliers d’applications, systèmes de communications et transactions. Et comme on pouvait s’y attendre dans l’histoire de la cryptographie, cette méthode avait déjà été créer en 1969 par James Ellis et Clifford Cocks, membres des services secrets britannique. De la même manière que Babbage ayant décrypter Vigenère, mais dont tout le mérite fut porté par Friedrich Kasiski, les secrets autour de la cryptographie sont légions.
Casser une clé RSA est pratiquement impossible avec la technologie du début du XXIème siècle. Mais les experts prédisent qu’à l’avenir, les ordinateurs quantiques pourraient être les décrypteurs de clés. Mais ceci est une autre histoire.
