Archive 2022
Program requirementsCC+examen
Weekly hours 20 h CM , 30 h TP
Years M2 double master mathématiques, informatique cryptologie et sécurité M2 mathématiques, informatique et applications à la cryptologie

Syllabus

Ce cours a pour but de comprendre les protocoles de la cryptologie à clé publique et les mathématiques sur lesquelles ils reposent.

Contents

  • Ordres de complexité pratiques (linéaire et quasi-linéaire, quadratique, polynomiale, sous-exponentielle, exponentielle). Exemples: opérations en multiprécision, algorithme d'Euclide, exponentiation modulaire, opérations sur les matrices, complexité actuelle des tests de primalité, factorisation et logarithme discret.
  • Primalité et factorisation. Divisions successives, théorème de Fermat, d'Euler--Fermat, nombres pseudo-premiers forts, test de Rabin--Miller, description détaillée de l'exponentiation modulaire, faux témoins. Preuves de primalité : Pocklington--Lehmer. Exemple Mersenne et Fermat. Factorisation: méthode rho de Pollard, méthode p-1 (première et deuxième phase), utilisation du sous-groupe d'ordre $p+1$ du corps à $p^2$ éléments. Méthodes sous-exponentielles de factorisation: Dixon, crible quadratique, crible algébrique.
  • Courbes elliptiques (utilité pour la factorisation, la primalité, le logarithme discret en cryptographie). Equations, loi de groupe, coordonnées affines et projectives. Courbes sur un corps fini, théorème de Hasse, comptage des points (élémentaire) par la loi de réciprocité quadratique. La méthode ECM de Lenstra, importance de la méthode de Montgomery. Test ECPP d'Atkin--Morain (notions de multiplication complexe). Utilisation du log discret en cryptographie.
  • Cryptographie à clef publique (chiffrement et signature). Méthode RSA, problème de la taille de la clef, vulnérabilité à certaines attaque (nécessité de padding et de hachage). Echange de clef bipartite de Diffie--Hellman. Méthode de chiffrement et de signature El Gamal. Calcul d'un logarithme discret: méthode de Pohlig--Hellman (nécessité d'un cardinal ayant un gros facteur premier), méthodes génériques d'attaque (Baby Step Giant Step de Shanks, Pollard rho à nouveau, le théorème de Shoup), méthode du calcul d'indices.