Parisian Master of Research in Computer Science

Master Parisien de Recherche en Informatique (MPRI)

Cryptologie (48h, 6 ECTS)

Responsables : G. Hanrot, D. Pointcheval

Plan du cours et intervenants prévus pour 2008-2009

1. Algorithmique des entiers et des polynômes (9h, Emmanuel Thomé)
2. Courbes elliptiques et hyperelliptiques (9h, Ben Smith)
3. Réseaux euclidiens (6h, Phong Nguyen)
4. Cryptographie asymétrique et preuves de sécurité (12h, David Pointcheval)
5. Cryptographie symétrique (12h, Pierre-Alain Fouque)

Planning, année 2008-09

Le lundi, de 12h45 à 15h45, en salle UouV, à l'ENS, 45 rue d'Ulm.

Objectifs

L'objectif du cours est de présenter aux étudiants les concepts et les outils de la cryptologie moderne tant en ce qui concerne la cryptographie conventionnelle que les méthodes à clé publique. On insiste sur le rôle joué, dans la conception de protocoles éprouvés, par les méthodes de la théorie algorithmique des nombres ou de la théorie de la complexité. On relie également les procédés cryptographiques aux fonctionnalités qu'ils assurent, en termes de sécurité : intégrité, authentification, chiffrement, signature. Ainsi, ce cours se compose de cinq parties : algorithmique des entiers et des corps finis ; courbes elliptiques et hyperelliptiques ; réseaux euclidiens ; cryptographie asymétrique et preuves de sécurité ; cryptographie symétrique.

Plan du cours

Le cours est découpé en 5 parties:

Algorithmique des entiers et des polynômes -- 9 heures (Emmanuel Thomé)

Cette partie débutera par une étude de l'algorithmique des anneaux Z/NZ et des corps finis. On étudiera brièvement le problème de la primalité, via l'angle des tests de composition.

Dans une deuxième partie, on étudiera les deux problèmes algorithmiques fondamentaux soulevés par l'étude de deux des principales primitives asymétriques : la factorisation des entiers et le logarithme discret. Cette étude permettra d'identifier des clés faibles et d'estimer la sécurité correspondant à une taille de clé donnée au vu des connaissances contemporaines.

Courbes elliptiques et hyperelliptiques - 9 heures (Ben Smith)

Le but de cette partie est de donner les définitions et les propriétés des courbes sur les corps finis qui sont utiles pour construire un cryptosystème à base de courbes. Nous étudierons les diverses problématiques soulevées par la construction d'un tel système : arithmétique efficace, cardinalité, difficulté du problème du logarithmet discret, dans le cas des courbes elliptiques et des jacobiennes de courbes hyperelliptiques de genre 2.

Une seance sera consacrée aux couplages, abordera leur calcul et leur sécurité, et presentera une application aux cryptosystèmes fondés sur l'identité.

Réseaux euclidiens — 6 heures (Phong Nguyen)

L'algorithmique des réseaux euclidiens est la principale technique d'attaque en cryptographie a clef publique, à cause des liens profonds entre réseaux et théorie des nombres. Les réseaux ont ainsi permis de casser les cryptosystèmes à base de sacs à dos, mais surtout certains cas particuliers des normes RSA et DSA, etc. On donnera la définition des réseaux ainsi que des problèmes difficiles qui les accompagnent (plus court vecteur, plus proche vecteur). On présentera les principaux algorithmes de réduction de réseau, notamment le célèbre algorithme LLL, qui peut être vu comme une généralisation vectorielle de l'algorithme d'Euclide pour le calcul du pgcd. Si le temps le permet, on abordera des constructions cryptographiques à base de reseaux. La cryptographie à base de réseaux suscite beaucoup d'intérêt depuis une douzaine d'années, suite à l'invention du cryptosystème NTRU et à des résultats spectaculaires d'Ajtai en théorie de la complexité.

Références utiles:

• chapitre 3 (pages 39-79) en français sur l'algorithmique des réseaux euclidiens.
• Notes de cours de cryptanalyse en anglais.
• Livre de Micciancio et Goldwasser sur la complexité des réseaux.
• Cours d'Oded Regev sur les réseaux.
• Cours de Daniele Micciancio sur les réseaux.

Cryptographie asymétrique et preuves de sécurité — 12 heures (David Pointcheval)

Les schémas « classiques » ne peuvent pas être utilisés tels quels pour des niveaux de sécurité élevés. En effet, après avoir formalisé les notions de sécurité souhaitables, aussi bien pour la confidentialité (schémas de chiffrement) et l'authentification (schémas de signature), on montrera comment on peut décrire des schémas, et « prouver » leur sécurité (avec quelques exemples concrets, tels que normes RSA-PKCS #1 (OAEP et PSS). Ensuite, on abordera la cryptographie interactive, avec notamment les protocoles Zero-Knowledge. Ce seront les briques de base de la cryptographie distribuée: partage de secret (vérifiable), signature (de Schnorr) et déchiffrement (ElGamal) distribués. Enfin, on abordera les protocoles cryptographiques récents, qui exploitent les propriétés particulières de couplages : cryptographie à base d'identité, cryptographie dans les groupes.

Vous trouverez les supports du cours "Cryptographie asymétrique et preuves de sécurité" ainsi que des exercices sur la page web: MPRI - Cryptologie.

Cryptographie symétrique - 12 heures (Pierre-Alain Fouque)

Les quatre séances seront découpées ainsi :

1. Stream Cipher. On rappelera ce qu'est la primitive de chiffrement de flot (générateur pseudo-aléatoire and One-Time Pad) et son modèle de sécurité. Les développements porteront sur les stream ciphers construits à partir d'un registre à décalage linéaire comme celui de Geffe, ou d'autres stream comme celui de PKZIP, RC4 et A5/1 (description et attaques).
2. Block cipher. On rappellera ce qu'est la primitive de chiffrement par blocs (permutation pseudo-aléatoire) et son modèle de sécurité. Les développements porteront sur le design du DES et de l'AES. On présentera quelques attaques comme la cryptanalyse différentielle et linéaire et les attaques par saturation sur l'AES.
3. Fonction de hachage. On étudiera la sécurité des fonctions de hachage (fonction de compression et mode opératoire). On prendra comme exemples les récentes attaques sur MD4 et MD5.
4. Modes. On étudiera les modes opératoire qui assurent la confidentialité des réseaux et des disques durs et l'intégrité des données (MAC).

Vous trouverez les supports du cours "Cryptographie symétrique" sur la page web: Cryptographie.

Pré-requis

Prérequis spécifiques

Nous attendons que les élèves aient déjà suivis un cours d'introduction à la cryptologie. Les principes généraux de la cryptologie (intégrité, authenticité, confidentialité) devront être connus ainsi que les techniques artisanales (Vigénère). On supposera que les étudiants ont déjà quelques notions sur les PKI, sur les canaux sécurisés (avec un exemple comme SSL), et sur les preuves de connaissances.

En théorie des nombres, les résultats de base sur les corps finis, sur l'arithmétique des entiers et sur la structure des entiers modulaires devront être connus ainsi que quelques résultats sur les polynômes (algorithme de Berlekamp).

On s'attend à ce que les étudiants aient déjà vu des exemples de primitives cryptographiques symétriques: fonctions de hachage, chiffrement par blocs (DES, AES), chiffrement par flot (RC4, A5), modes ECB, CBC. De même, les primitives asymétriques classiques (RSA et Diffie-Hellman) devront être connues.

Remarque: Aucune connaissance préalable n'est demandée sur les courbes elliptiques et la cryptanalyse.

Pour information, voici les sujets d'examen du cours MPRI de niveau 1 Initiation à la cryptologie donnés en 2005 et en 2006.

Prérequis généraux

Ces prérequis ne sont pas spécifiques à la cryptologie et sont déjà essentiellement inclus dans la liste générale.

On aura besoin des notions de classes de complexité, de machine de Turing, de problèmes NP. Un minimum de connaissance en algèbre et en probabilité sera aussi requis. Enfin les outils algorithmiques de base doivent être maîtrisés.

Langue

Examens passés

Bibliographie

• D. Stinson, Cryptography Theory and Practice, CRC Press.
• A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography, CRC Press.

Les années précédentes

• Année 2009-2010
• Année 2008-2009
• Année 2006-2007
• Année 2007-2008

Équipe pédagogique