Requirementsalgèbre effective
Program requirementsCC+examen
TeacherPascal Molin
Weekly hours 2 h CM , 3 h TD
Years M1 MIC M1 Mathématiques et Informatique

Syllabus

Le codage consiste à protéger une information de la dégradation physique, en lui ajoutant une redondance structurée. L'enjeu de la cryptographie est de maîtriser l'accès à des données ou des services, et les protéger de modifications ou copies malveillantes.

Ce cours est à la fois une introduction détaillée à ces domaines, et un cours d'algorithmique algébrique Dans ce cours, on décrit les bases théoriques de ces domaines et les principaux systèmes utilisés. On apprend aussi les techniques d'algorithmique algébrique employées pour les mettre en œuvre, ou pour attaquer les cryptosystèmes.

Le module de projet est l'occasion d'approfondir des thèmes qui ne sont qu'évoqués dans ce cours.

Contents

  • Cryptographie:
    • Théorie de Shannon, chiffres classiques, théorème du secret parfait
    • Chiffrement symétrique, LFSR, AES
    • Chiffrement à clef publique
    • Chiffrement RSA, primalité, factorisation, attaques
    • Chiffrement de Rabin, résidus quadratiques
    • Factorisation d'entiers (méthodes de Pollard, crible quadratique)
    • El Gamal, courbes elliptiques
    • Calcul de logarithme discret (BSGS, réductions, calcul d'indice)
    • Protocoles : signature, preuves sans apport d'information
  • Codes correcteurs:
    • Espace de Hamming, distance de Hamming
    • Bornes de Hamming, Singleton, Plotkin.
    • Codes t-correcteurs, codes parfaits, codes MDS.
    • Codes linéaires. Codes cycliques.
    • Codes classiques : Hamming, Golay, Goppa, Reed-Muller, Reed-Solomon, BCH.
    • Décodage des codes cycliques

Bibliography

  • M. Demazure, Cours d'algèbre : primalité, divisibilité, codes, Cassini, 1997.
  • N. Koblitz, A course in number theory and cryptography, 2nd edition, Springer, 1994.
  • J. H. Van Lint, Introduction to coding theory, 3rd edition, Springer, 1999.
  • G. Zémor, Cours de cryptographie, Cassini, 2000.