________________________________________________________________ ____ __ __ / ___________________________________________________________ ____ __ _ / ` \ / \[17]/ + ,\_____ ___/ . ` |\/ , \__/ . \____ /:/=[ un affaire de cryptographie ] =\:\ _____/ ` x || , . " :X \_______________________________ ____ ____ / , ` ` || + , () . x , . ` ' ` \_ \ ,\\_ +\_ \ 'M ` | . || ` | ` , ` , + , ` ,--, + . \\_ \_ \ , \\_ K -+- / |+ -+- . , ` , ,',/ ,'. \_ \ . \\_ \_ \ - | ` / . | ; + + . ` | : . :`` ,_): ' ` \\_ \_ \ \\_` 1 , / ` . . x , .-=+=- `. ,. ,' ` , \_ \ + \\_` \_ \ 1 /\_____ x ' , . . X | ` `--' ` ` \\_ \_ \ , \\_ 1 + \\_ \___________________ , . . ` , + ' , , ; x ._\ \___\\___\ \ . \_ \ \__________________________________/ \ ` , \\_ /:/=[ Aka: ¤hZi7ZlyvWYTma0kOQTy6LgFS0UZN ]=\:\ \ \__\__________________________________________ ______________________________ \` \__\ /__/ \\_ /:/=[ steck ]=\:\ _// \__\________________________/__/ Introduction à la cryptographie Dans cet article je vais expliquer les bases de la cryptographie. Je ne vais pas détailler les algorithmes, je vais juste les citer pour que vous puissiez demander à votre ami google si vous voulez plus de renseignements. Tout d'abord commençons par quelques définitions pour mettre tout le monde d'accord. La cryptographie est la science de garder des messages secrets, la cryptologie est la branche mathématique qui s'en charge, et la cryptanalyse est la science de retrouver le message original sans en avoir la clé. Un texte clair, après chiffrement ou encryption, devient un texte chiffré ou cryptogramme. Celui ci redeviendra un texte clair après déchiffrement ou décryptage. Les deux protagonistes qui veulent s'échanger un message sont appelés Alice et Bernard. La sécurité d'un algorithme ne doit pas dépendre de la non connaissance de cet algorithme, au contraire il doit être approuvé et testé par la communauté afin de trouver des failles. On distingue deux types principaux d'algorithmes : les algorithmes à clé secrète et les algorithmes à clé publique. LES ALGORITHMES A CLE SECRETE La même clé est utilisée pour chiffrer et déchiffrer les messages, et doit donc n'être connue que par les personnes impliquées. Si une personne avec la clé obtient un message chiffré, elle pourra la déchiffrer sans que les autres personnes ne s'en rendent compte. La sécurité du message dépend uniquement du nombre de personnes connaissant la clé. Ce type d'algorithme est le plus souvent utilisé pour le chiffrement de fichiers sur disque. L'ancien standard était le DES (Data Encryption Standard), depuis peu un nouveau l'a remplacé, l'AES (Advanced Encryption Standard). Il y a deux types de chiffrement à clé privée : le chiffrement en continu, qui chiffre bit par bit (ou lettre par lettre), et le chiffrement par blocs, qui découpe le texte en blocs (souvent 64 bits) et chiffre blocs par blocs (éventuellement en fonction du bloc précédent pour plus de sécurité). Dans cette catégorie on retrouve tous les algorithmes à substitution simple (lettre par lettre, comme le code de césar ou la rotation 13), à substitution homophonique (à une même lettre correspond plusieurs lettres chiffrées), toutes leurs variantes et compositions (plusieurs substitutions en séries, substitution par blocs de 3, Vigenère, ENIGMA...). Ces algorithmes ne cachent pas assez les caractéristiques de la langue utilisée et sont perdus face à une attaque statistique (basée sur la fréquence d'apparition des lettres). On retrouve aussi les algorithmes à transposition, où c'est juste la place des lettres qui change, et qui se cassent aussi très facilement. Dans les "vrais" algorithmes, outre le DES et l'AES, on peut citer l'IDEA, Skipjack, RC5... et le masque jetable (utilisation du OU EXCLUSIF, qui est réellement incassable si la clé est de la longueur du texte et ne peut pas être devinée... La génération des nombres aléatoires est cruciale en cryptographie). On considère actuellement que la taille suffisante des clés secrètes est de 128 ou 256 bits, selon les algorithmes. Voici comment fonctionne en gros DES (AES, dont le vrai nom de l'algorithme est Rijndael, est nettement plus compliqué) : Le texte est découpé en blocs de 64 bits. Après une permutation initiale, le bloc est divisé en deux blocs de 32 bits. Ensuite vient 16 rondes d'une même fonction qui combine ces blocs avec la clé de 56 bits. Ensuite ces blocs sont rassemblés et une dernière permutation donne le bloc final. C'est le même algorithme qui est utilisé pour le chiffrement et le déchiffrement, en inversant simplement la clé. Les opérations dans la fonction sont des décalages de bits, des permutations, des ou exclusifs avec certaines parties de la clé et des substitutions. La sécurité du DES a été testée et approuvée après des années d'études. Il n'y a que 4 clés dites faibles qui rendent l'algorithme peu sûr et 60 autres sont semi-faibles. Mais il reste quand même 72 057 594 037 927 872 autres clés tout à fait valables. Une attaque pour tester toutes le clés ne devrait en fait tester la moitié des clés possibles (2^55 au lieu des 2^56). En 1993 fut conçue une machine à 1 million de dollars qui peut faire une attaque exhaustive contre le DES en 3.5 heures. De nos jours le DES n'est plus utilisé mais une telle machine actuellement le ferait en quelques minutes et pour bien moins cher. Pour améliorer la sécurité du DES il y a eu des variantes comme le DES triple : trois DES à la suite avec trois clés différentes LES ALGORITHMES A CLE PUBLIQUE Dans ces algorithmes, une clé différente est utilisée pour chiffrer et pour déchiffrer. Une partie de la clé est connue de vous seul, et une partie est publique, accessible au monde entier, dans un répertoire de clés. Ainsi si quelqu'un veut vous envoyer un message, il le chiffre avec votre clé publique, et vous seul pourra le déchiffrer. On peut également chiffrer un message avec sa clé privée, et tout le monde pourra le déchiffrer. Ce type d'algorithme permet de résoudre d'autres problèmes liés aux transferts de données : - l'authentification : Si Alice veut envoyer un message à Bernard, avant de le chiffrer avec la clé publique de Bernard, elle le chiffre avec sa clé privée. Ainsi Bernard recevra un message qu'il déchiffrera avec sa clé privée, puis déchiffrera le message obtenu avec la clé publique d'Alice pour obtenir le message d'origine. Etant donné que le message a été chiffré avec la clé privée d'Alice, il peut être certain que le message provient d'elle. Ce procédé s'appelle Signer le message. - l'intégrité : En signant son message, il n'y a que Alice et Bernard qui ont accès au message clair, donc personne ne peut le modifier, car il lui faudrait posséder une clé privée. - le non désaveu : Toujours en signant son message, Alice ne peut pas nier dans le futur l'avoir envoyé. C'est ce type d'algorithmes qui sont utilisés pour les transferts bancaires ou sur internet (SSL, SSH...), et la longueur des clés respectable est des 2048 bits minimum. Les principaux algorithmes sont RSA, Rabin, ElGamal, et repose sur des impossibilités mathématiques (factorisation de produit de grands nombres premiers, calculs de racines carrés modulo un nombre composite, calculs de logarithmes discrets...) Voici le fonctionnement de RSA (Rivest Shamir Adleman) : prenons deux grands nombres premiers p et q (plus de 100 chiffres chacun) posons n=p*q et m=(p-1)(q-1) et choisissons e premier avec m. il suffit enfin de trouver un nombre d vérifiant e*d=1 modulo n Le couple (n,e) est la clé publique accessible à tout le monde, et (n,d) la clé privée. Pour chiffrer un message, il faut le découper par blocs (pour éviter d'obtenir au final une simple substitution), puis d'appliquer la formule suivante pour chiffrer le bloc B : C = B^e modulo n Pour déchiffrer, il suffit d'appliquer : B = C^d modulo n Sous ce miracle se cache de l'arithmétique car ces nombres vérifient (B^e)^d=B^(e*d)=(B^d)^e=B modulo n, on peut donc également chiffrer avec sa clé privée. L'avantage de RSA est que trouver p et q est très facile avec des algorithmes probabilistes de primalité, tant que le nombre n'est pas premier on en génère aléatoirement un autre. Le calcul de n et m est très rapide, e aussi avec l'algorithme d'Euclide, et d grâce à une équation de type bezout. Enfin le calcul de x^y modulo k se fait grâce à l'exponentielle rapide. Cette méthode est donc très rapide à mettre en place, par contre à l'heure actuelle il est pratiquement impossible de factoriser n (donc retrouver p et q, nécessaires pour le calcul de d). La société RSA offre de l'argent aux personnes réussissant à factoriser des grands nombres, le dernier en date est un nombre de 200 chiffres : "The sieving effort is estimated to have taken the equivalent of 55 years on a single 2.2 GHz Opteron CPU. The matrix step reportedly took about 3 months on a cluster of 80 2.2 GHz Opterons." [http://www.rsasecurity.com/rsalabs/node.asp?id=2094] LA CRYPTANALYSE La cryptanalyse doit, si elle réussi, permettre de trouver soit le texte original, soit la clé d'un message chiffré. On suppose donc pour cela que l'espion connaît le fonctionnement de l'algorithme. L'histoire de la cryptanalyse est assez longue, avec pas mal de réussites, surtout pendant les guerres comme la seconde guerre mondiale, avec la machine allemande Enigma qui a été cassée, et qui a joué un rôle dans l'issue de cette guerre. Il existe plusieurs méthodes, selon ce qu'il possède : - l'attaque à texte chiffré seulement : l'espion possède plusieurs textes chiffrés avec la même clé, et doit retrouver le texte clair ou la clé. - l'attaque à texte clair connu : l'espion possède les textes chiffrés et leur texte clair correspondant, il doit retrouver la clé ou un algorithme pour déchiffrer les autres messages chiffrés avec la même clé. - l'attaque à texte clair choisi : l'espion peut obtenir le texte chiffré à partir des textes clairs qu'il veut, son but est le même qu'avec le texte clair connu, mais est bien plus efficace. - l'attaque à texte chiffré choisi : l'espion peut choisir de déchiffrer les textes qu'il veut, et doit retrouver la clé (une sorte de reverse engineering ;) Les deux premières sont les plus courantes, car il est assez facile de deviner certaines parties de messages (en-têtes... #define, int pour du code C), ou lorsque qu'Alice transmet tout ce que lui donne l'espion pour l'envoyer à Bob. La cryptanalyse est une étape obligatoire dans la vie d'un algorithme de chiffrement : après avoir soumis au monde entier son algorithme, si celui ci n'a pas réussi à être cryptanalysé on peut supposé que c'est un bon algorithme : énormément d'études ont par exemple étaient faites sur le DES, il faut 2^47 textes clairs choisis pour cryptanalyser un DES classique, mais seulement 2^20 en remplaçant les tables utilisées dans les rondes par des tables aléatoires... Certains algorithmes se cassent en deux secondes (substitution ou transposition), alors que d'autres nécessitent de tester toutes les clés possibles, mais une taille suffisante de ces dernières exclue cette possibilité, même avec des ordinateurs les plus puissants imaginables. La cryptanalyse est une science très complexe, comprenant beaucoup de méthodes (cryptanalyses linéaires, différentielles, ...) et nécessite des bases mathématiques très solides dès que les algorithmes sont compliqués. CONCLUSION Cet article offre un petit tour d'horizon du monde de la cryptographie. Il y a encore énormément de choses à dire, sur les protocoles, les algorithmes, la stéganographie, les fonctions de hachage à sens unique, les générateurs de nombres aléatoires, la sécurité des algorithmes et la cryptanalyse réelle… Un autre type de cryptographie est en train de voir le jour : la cryptographie quantique, qui ne se base plus sur des difficultés mathématiques, mais sur une impossibilité physique (cloner des photons). Un protocole de transmission a été proposé et fonctionne, mais cette technique fait pour le moment face à quelques difficultés comme les grandes distances et la rapidité. Des études sont en cours pour pallier à ces problèmes, mais le coût de cette technique la réserve pour le moment aux gouvernements et grosses entreprises. Avant de finir je voudrai vous citer le début de la préface de "Cryptographie appliquée" (de Bruce Schneier), que je recommande fortement à tout ceux que cet article a intéressé : "Il existe deux types de cryptographie dans le monde : la cryptographie qui empêche votre petite soeur de lire vos fichiers, et la cryptographie qui empêche les principaux gouvernements de lire vos fichiers". Il est évident que pour un petit usage, du DES ou un autre petit algorithme suffira. Pour les gouvernements, il ne faut pas oublier qu'ils ont de l'argent et les moyens de casser pas mal de codes. Avant de valider le DES, la NSA (National Security Agency pour les incultes) a modifié certaines tables définies dans l'algorithme. Personne ne sait pourquoi, les tables initiales (par IBM) proposaient le même niveau de sécurité... Je vous laisse allez à la paranoïa (certains disent que c'est juste par méfiance d'IBM), et j'ajouterai même que la NSA embauche les meilleurs mathématiciens et cryptologues du monde... Il ne faut pas non plus oublier que la cryptographie doit faire parti d'une politique complète de sécurité : à quoi sert le chiffrement de messages si l'espion peut voir votre écran (TEMPEST par exemple ou de simples caméras) ou voir ce que vous tapez au clavier... N'oubliez pas que dans le monde de la cryptographie, la paranoïa est nécessaire pour survivre... Steck