Cryptographie symétrique et complexité

Cours du Master 2 MIC, Mathématiques, Informatique et application à la Cryptologie.

Année 2012-2013

• Quelques rappels de C.
• Semaine 1 :
  • Fiche du premier TD (polynômes irréductibles) ; programmation : calcul sur les polynômes sur F₂ et sur les corps finis de caractéristique 2, recherche de polynômes irréductibles et primitifs.
  • Exemple d'utilisation de la cryptographique symétrique : une session https.
  • Bref panorama historique. Les systèmes cryptographiques, le principe de Kerckhoffs (Auguste Kerckhoffs, Cryptographie militaire, Journal des sciences militaires, janvier et février 1883). La cryptographie classique : substitutions (exemple du chiffre de César), et permutations (ou transpositions) ; le chiffrement de Vigenère. La méthode de Kasiski. Indice de coïncidence.
• Semaine 2 :
  • Indices de coïncidence mutuels (voir exercices de cryptographie classique).
  • Les divers types d'attaques (texte chiffré connu, texte clair connu, texte clair choisi, texte chiffré choisi). Produit de systèmes cryptographiques, confusion et diffusion.
  • Sécurité calculatoire et sécurité inconditionnelle. Théorie de Shannon (C. E. Shannon, "Communication Theory of Secrecy Systems") : la confidentialité parfaite, chiffrement de Vernam.
  • Fiche du second TD.
  • fausses clefs, distance d'unicité.
• Semaine 3 :
  • LFSR (Linear Feedback Shift Register, registre à décalage à rétroaction linéaire) et suites récurrentes linéaires sur un corps fini F_q : définition, écriture matricielle ; la suite est périodique à partir d'un certain rang ; si la matrice de la suite est inversible, elle est périodique ; l'initialisation (0, ... ,0,1) donne toujours une période maximale, pour une relation de récurrence donnée.
  • Fiche du troisième TD , les fichiers référencés sont ici.
  • Retour sur le principe des Chiffrements par flot.
  • LFSR : propriétés statistiques d'une suite de période de longueur maximale ; polynôme caractéristique ; cas où celui-ci est irréductible ; s'il est primitif la période de la suite est de longueur maximale q^m-1 pour une relation de récurrence d'ordre m ; nombre de polynômes primitifs.
  • Séries formelles.
• Semaine 4 :
  • Exercices des fiches 1 et 2 ; fiche du quatrième TD.
  • Les LFSR (Linear Feedback Shift Register) et les suites récurrentes linéaires sur F_q : anneau des séries formelles sur un corps fini ; série génératrice d'une suite ; polynôme de connexion d'un LFSR ; la série génératrice d'une suite périodique est engendrée par une fraction rationnelle ; une suite engendré par un LFSR de taille m sur F_q est de période maximale q^m-1 si et seulement si le polynôme caractéristique (ou son polynôme réciproque, le polynôme de connexion) est primitif.
  • Polynôme minimal d'une suite. Matrices de Hankel. Complexité linéaire, profil de complexité linéaire, premières propriétés.
  • Fiche du cinquième TD (algorithme de Berlekamp-Massey).
• Semaine 5 :
  • Profil de complexité linéaire, propriétés ; algorithme de Berlekamp-Massey.
  • Chiffrements à flot utilisant des LFSR. Combinaison booléenne de LFSR ; fonction de filtrage sur le vecteur d'état ; contrôle de l'horloge et désynchronisation des sorties des LFSR - - - exemple de A5/1, chiffrement du GSM
• Semaine 6 :
  • Attaques par corrélations. Fonctions booléennes, équilibrées, résistantes aux corrélations à l'ordre m, m-résilientes.
  • Fiche du sixième TD.
  • Chiffrements à flot (fin) : conception et mise en œuvre des chiffrements à flots ; exemple de A5/1 ; quelques faiblesses liées aux protocoles de mise en oeuvre ; quelques exemples d'attaques sur le chiffrement A5/1 et le protocole du GSM ; quemques indications sur une attaque par compromis temps-mémoire.
  • Chiffrements par bloc, principes (confusion-diffusion, ...) ;
• Semaine 7 :
  • Chiffrements par bloc, principes (confusion-diffusion, ...) ; modes opératoires ; Fiche du septième TD.
  • (Pas de cours le 1er novembre)
• Semaine 8 :
  • Un exemple de chiffrement par bloc simplifié de type SPN ; attaques différentielles sur les chiffrements par bloc ; mise en œuvre sur l'exemple (cf. article de Heys) Fiche du huitième TD.
  • Conception des chiffrements par bloc : S-box, P-box, tour, procédure d'ordonnancement et de diversification de clefs (key schedule) ; SPN et schéma de Feistel ; exemple du DES ; exemple de l'AES. Propriétés de la fonction inverse sur F_2ⁿ et attaque différentielle (S-box de l'AES).

Références.

Ouvrages généralistes.

• Douglas R. Stinson : Cryptographie Theory and practice, Chapmann & Hall 1995 (première édition), 2006 (3ème édition), une traduction française des deux premières éditions existe. Les trois éditions sont assez différentes, la troisième édition reprend en première partie la seconde édition.
• Alfred Menezes, Paul J. van Oorschot et Scott A. Vanstone. Handbook of applied cryptography. CRC Press, 1997, une version électronique est en accès libre.
• Gille Zémor : "cours de Cryptographie", ed. Cassini 2000.

Références par sujet (compléments).

Langage C

• Le cours de "Programmation en langage C" d'Anne Canteaut.
• Le cours "Introduction au langage C" de Bernard Cassagne.

Protocole SSL/TLS

• les premières spécifications de SSL (2.0, 3.0), développé par netscape, accessibles sur le site de la fondation mozilla.
• TLS (version 1.2 est spécifié par la rfc5246 (site de l'IETF) ; pour la première version 1.0, héritière directe de SSL 3, voir la rfc2246.

Aspects historiques, théorie de Shannon.

En plus des livres de Stinson et Zémor, et du "Handbook of applied cryptography"

• Simon Singh : "Histoire des codes secrets", livre de Poche.
• Brochure (pdf) qui reprend les deux parties de l'article de Kerckoffs de 1883, et leurs transcriptions en html.
• Une copie de l'article de C. E. Shannon, Communication Theory of Secrecy Systems (1949).

Chiffrements à flots.

En plus du livre de Zémor et du "Handbook of applied cryptography"

• plusieurs articles (vulgarisation, extrait d'encyclopédie) sur la page web d'Anne Canteaut.
• Michel Demazure "Cours d'algèbre, primalité, divisibilité, codes", Cassini, 1997 (cours d'algèbre avec un point de vue algorithmique, mais rien sur les LFSR et la cryptographie en général).
• Rudold Lidl et Harald Niederreiter "Introduction to finite fields and their applications", Cambridge University press 1994, ou "Finite Fields", Addison Wesley 1983 (chapitre "Linear recuring Sequences" à peu près identiques dans les deux livres), point de vue algébrique, très complet.
• Rainer A. Rueppel, "Analysis and design of Stream Ciphers", Springer-Verlag 1986 ; (étude en particulier du filtrage et de la composition des LFSR, résistance aux corrélations ....).
• La page du projet européen eSTREAM (2004-2008), analyses et recommandations pour des chiffrements à flot de conception récente.
• Sur A5/1, chiffrement du GSM :
  • Elad Barkan, Eli Biham, Nathan Keller, "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication", 2006 (version longue d'un papier de 2003), attaques sur A5/2, A5/1, récapitulatif des attaques existantes, "man in the middle attack", ...
  • Karsten Nohl "Attacking phone privacy" (2010), présentation rapide de l'attaque sur le GSM, et des attaques par compromis temps-mémoire.

Chiffrements par bloc.

En plus du livre de Stinson, et du "Handbook of applied cryptography",

• les publications de la division du NIST (agence fédérale américaine) chargée de la sécurité informatique, par exemple :
  • Les recommandations pour les modes opératoires des chiffrements par bloc sp800-38a,
  • La dernière version de la spécification du DES fips46-3 (1999), et du triple DES (TDEA) SP800-67 (révision 1 janvier 2012)
  • La description du standard AES fips97, et des archives du concours.
• Attaques différentielles et attaques linéaires voir A tutorial on linear and differential cryptanalysis, Howard M. Heys, et l'errata (repris également dans la 3ème édition du livre de Stinson).

Fonctions de hashage.

En plus du livre de Stinson, et du "Handbook of applied cryptography",

• La spécification des algorithmes de la famille SHA fips180-3 (révision d'octobre 2008).
• Fonctions de hachage cryptotographique avec clef : HMAC (Keyed-Hash Message Authentication Code) fips198-a (révision de mars 2002).
• Le site du Cryptographic hash project, concours organisé par le NIST pour une nouvelle famille de fonctions cryptographiques (SHA3).

Autres

• Le site de l'ANSSI, Agence nationale de la sécurité des systèmes d'information, accès à la législation française, recommandations (référentiel général de sécurité) ...

(dernière modification le jeudi 08/11/2012, 17:42:18 CET)