Introduction

La cryptologie, ou science du secret, a apparemment vu le jour au même moment que l'écri­tu­re, soit environ 4000 ans avant JC. C'est en tout cas ce qu'historiens et archéologues con­jec­tu­rent. La cryptologie est devenue depuis un demi-siècle une discipline scien­ti­fi­que à part entière qui connaît un engouement spectaculaire à la mesure du rôle de plus en plus important que jouent les réseaux de communication au sein de notre société moderne. La cryp­to­gra­phie est l'étude des techniques d'écriture de messages secrets tandis que la crypt­a­na­ly­se en fait l'analyse pour les valider ou les invalider.

La cryptographie et la cryptanalyse s'appuient sur de nombreuses théories mathématiques et in­for­ma­ti­ques dont les plus importantes sont

• la combinatoire ;
• la théorie des probabilités ;
• la théorie de l'information ;
• l'algorithmique ;
• la théorie de la complexité et de l'approximation ;
• l'arithmétique et la théorie des nombres ;
• l'algèbre discrète.

Ce terme est décliné suivant la nature de ces transformations : encodage, codage de source, codage de canal ou codage correcteur, codage secret. Par exemple et respectivement, le American Standard Code for Information In­ter­chan­gecode ascii est une re­pré­sen­ta­tion par­ti­cu­liè­re des lettres et des symboles usuels avec des nombres entiers, le code de Huffman permet de compresser des données, le code de Hamming de les protéger contre des erreurs de transmission, le code de César de les rendre incompréhensibles.

La cryptographie est donc le terme consacré quand le codage a pour finalité de rendre les données secrètes. Les codes correcteurs et les codes secrets peuvent paraître antinomiques à première vue : le codage correcteur s'emploie à rajouter des informations à un message pour le rendre plus intelligible alors que la cryptographie tente au contraire et par tous les moyens de le rendre incompréhensible. En réalité les deux théories se complètent, car le message secret doit être intelligible pour pouvoir être déchiffré. Il est en effet de peu d'intérêt d'employer le javanais au téléphone pour ne pas dévoiler le contenu d'une conversation si votre interlocuteur (qui comprend le javanais) n'entend que de la friture sur la ligne…

La transmission d'une information subit généralement plusieurs codages successifs. Le premier est l'encodage qui permet de représenter des données concrètes en données abstraites, par exemple des triplets d'entiers \((R,V,B)\) pour représenter des couleurs, eux-mêmes compressés (codage de source) pour éventuellement être chiffrés (si l'on veut protéger la transmission d'une photo par exemple) auxquels on ajoute de la redondance (codage correcteur) avant de les transmettre pour resister aux perturbations du canal de transmission.

Les trois grands objectifs de la cryptologie sont :

1. La confidentialité, qui assure que l'information n'est accessible qu'aux personnes autorisées.
2. L'intégrité ou l'authentification, qui assure qu'un document n'a pas été altéré, que ce soit par des perturbations ou par un tiers malveillant.
3. L'identification qui certifie l'origine d'un message.

Plus récemment, des problèmes de partage de secret ont vu le jour. Pour donner une idée de cette nouvelle problématique, imaginons que dans une hypothétique défense européenne, les \(m\) chefs d'états disposent d'une clef leur permettant de déclencher une attaque nucléaire. Tout le monde s'accordera à dire qu'il est inconcevable qu'une seule clef puisse autoriser l'accès à cette ressource. D'un autre coté, il peut être hasardeux de conditionner l'accès à une telle ressource uniquement si les \(m\) clefs sont activées ! On peut donc souhaiter que \(l\) clefs suffisent, avec bien sûr \(1 < l < m\). C'est de ce type de questions que traite le partage de secret.

Ce cours introductif s'adresse aux étudiants de mathématiques ayant le niveau de la licence, mais il est tout à fait accessible à un informaticien ayant une culture mathématique solide. Le volume d'en­sei­gne­ment étant relativement restreint, deux alternatives étaient envisageables pour une introduction à la cryptologie. La première consistait à faire un panorama très superficiel de ce domaine de recherche aujourd'hui très vaste, la seconde était de me restreindre à un petit nombre de protocoles illustratifs de cette théorie.

Pour les protocoles de chiffrement à clef secrète, j'ai choisi principalement le système de Vigenère, qui a l'avantage d'être simple, d'introduire une démarche générale, et qui peut être mise en oeuvre dans un délai raisonnable pour des mathématiciens peu familiarisés avec la programmation. Le des et l'aes sont bien sûr abordés.

Pour les protocoles de chiffrement à clef publique, j'ai choisi le protocole rsa, parce qu'il est largement utilisé et surtout pour illustrer quelques théorèmes fondamentaux d'arithmétique. Je mets également en avant les aspects algorithmiques incontournables quand on veut faire des calculs effectifs.

Le cours est décomposé en 5 chapitres:

1. Cryptographie à clef privée, méthodes naïves, notion de clef.
2. Le système de Vigenère. Introduction au des. Cryptanalyse.
3. Introduction à l'aes.
4. Cryptographie à clef publique. Chiffrement d'ElGamal. Arithmétique et rsa. Système de McEliece.
5. Algorithmes et complexité liés à rsa. Problèmes NP-complets. Problèmes Prime et Co-Prime.
6. Analyse de rsa et problèmes relatifs à la primalité/décomposition.

Documents pédagogiques

1. Planche A
2. Planche B
3. Planche C