M2 Algèbre Appliquée et Cryptologie

Bases d'algèbre, d'algorithmique et de programmation

• Multiplication de matrices 32 × 32 dans GF(2).
• Eléments de base de calcul dans GF(p), avec les opérateurs C d’abord (limite à 16 puis 32 bits environ), avec la librairie GMP ensuite. Illustration sur RSA. Calcul de racines carrées.
• Calcul sur les polynômes à une et plusieurs variables.
• Algorithmes de Tri. Algorithmes de tri à base d’arbres équilibrés.
• Applications en cryptographie et théorie des nombres des algorithmes de tri. « Collisions généralisées » entre 4 listes.
• Courbes elliptiques. Comptage de points par pas de bébé – pas de géant.
• Compléments sur les courbes elliptiques : diviseurs, fonctions, couplage de Weil–Tate. Algorithmes pour les couplages. Applications cryptographiques : Diffie–Hellman tripartite, chiffrement basé sur l’identité, signatures courtes.
• Transformées de Fourier et applications. Multiplication de polynômes, recherche d’approximation linéaires.
• Problématique des accès en mémoire et des effets de cache. Application au crible d’Eratostène.
• Algèbre linéaire et calcul de base de Gröbner sur GF(2).

Le but de ce cours est l’apprentissage de techniques algorithmiques visant à programmer efficacement, ainsi que du langage C, afin d’illustrer ces techniques. Un aperçu des outils d’analyse et de débogage gprof et gdb, ainsi que de la librairie de grands nombres GMP vient compléter ces objectifs. Chaque cours consiste en une étude approfondie d’un exemple, choisi en relation avec les autres modules du master. L’objectif étant, pour chacun d’eux, de comprendre les facteurs limitants et d’étudier comment les contourner afin d’obtenir des performances améliorées.

Introduction to Algorithms (Second Edition). Cormen, Leiserson, Rivest et Stein, MIT Press et McGraw-Hill, 2001. A course in computational algebraic number theory. Henri Cohen. Springer GTM 138.

Bases en algèbre et en cryptographie.

• Le RSA revisité : diverses attaques de protocoles RSA, les normes actuelles, programmation rapide du RSA.
• Les techniques de cryptanalyse à clé secrète : cryptanalyse différentielle, cryptanalyse linéaire, cryptanalyse multivariable (algébrique), autres techniques.
• Cartes à puce : présentation des cartes à puces, les attaques physiques (SPA, DPA, DFA, etc.) et contre-mesures, exemples de protocoles pour certaines applications (cartes bancaires, de téléphone, de sécurité sociale, de télévision, etc.).
• Courbes elliptiques et cryptographie : ECC (Elliptic Curve Cryptography).
• La recherche actuelle en cryptographie : les grandes conférences annuelles, les revues et les ouvrages de recherche, les principaux articles récents.

L’objectif est ici d’une part de donner aux étudiants une réelle expertise sur les grands algorithmes cryptographiques (la façon de les générer, et de les utiliser pour des applications réelles de l’industrie), et d’autre part d’introduire les principaux axes de recherche en cryptographie actuellement. On met ainsi l’accent sur les diverses techniques modernes de cryptanalyse, sur les contre-mesures de sécurité, sur les techniques de programmation efficaces des algorithmes, et sur divers problèmes ouverts.

Bases d'algèbre et de cryptographie.

À partir de résultats de théorie algorithmique des nombres, on étudiera la sécurité des algorithmes de chiffrement et de signature qui s’appuient sur la factorisation (RSA), le logarithme discret sur le groupe multiplicatif des entiers modulo p (ElGamal, Schnorr, DSA...), ou encore la réduction de réseaux (Merkle–Hellman, Chor–Rivest, NTRU...). Une autre partie du cours sera consacrée aux cryptosystèmes « multivariables », qui s’appuient sur le problème MQ de résolution des systèmes d’équations polynomiales quadratiques à plusieurs variables, sur la notion d’isomorphismes de polynômes (IP), et sur la détermination d’une combinaison linéaire de matrices ayant un petit rang (MinRank).

L’objectif du cours est d’aborder les notions modernes de sécurité pour les algorithmes cryptographiques, en particulier dans le cas asymétrique.

Douglas Stinson, Cryptographie – Théorie et Pratique (Vuibert, 2003) Gilles Zemor : Cours de Cryptographie (Cassini, 2000) Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography (CRC Press, 1997) Oded Goldreich, Foundations of Cryptography – Volume I : Basic Tools (Cambridge University Press, 2001) Oded Goldreich, Foundations of Cryptography – Volume II : Basic Applications (Cambridge University Press, 2004) Neal Koblitz, A Course in Number Theory and Cryptography (GTM 114, Springer, 1994) Neal Koblitz, Algebraic Aspects of Cryptography (Springer, 1998) M. Garey, D. Johnson, Computers and Intractability (Freeman, 1979) Eric Bach, Jeffrey Shallitt, Algorithmic Number Theory – Volume I : Efficient Algorithms (MIT Press, 1996) Henri Cohen, A course in computational algebraic number theory (4e édition, GTM 138, Springer-Verlag, 2000) Henri Cohen, Advanced topics in computational number theory (GTM 193, Springer-Verlag, 2000)

Algèbre commutative et Théorie de Galois.

• Topologie de Zariski.
• Variétés projectives, courbes projectives planes.
• Corps de fonctions.
• Morphisme de variétés projectives.
• Diviseurs, diviseurs sur les courbes, degré.
• Groupe de Picard.
• Cas des courbes elliptiques

W. Fulton, Algebraic curves, Benjamin 1969. R. Hartshorne, Algebraic Geometry, Springer 1977. R.J. Walker, Algebraic curves, Princeton University Press

Algèbre commutative, théorie de Galois, courbes algébriques.

• Courbes planes affines et projectives : propriétés locales, diviseurs.
• Courbes elliptiques : généralités, forme de Weierstraß, loi de groupe, couplage de Weil.
• Courbes elliptiques sur les corps finis
• Courbes elliptiques sur le corps des nombres rationnels
• Applications des courbes elliptiques

Ce cours est consacré à l’étude des courbes elliptiques en vue de leurs utilisations en cryptographie

D. Perrin, Géométrie Algébrique, Une introduction, Savoirs Actuels, 1995. W. Fulton, Algebraic Curves, Benjamin, 1969. J. H.Silverman, The Arithmetic of Elliptic Curves, Springer, Graduate Texts in Math. 106, 1986.

Il est nécessaire d'avoir une bonne formation en algèbre commutative et théorie de Galois ainsi que des bases en calcul formel. Les étudiants travaillerons sur SAGE.

• Bases de Gröbner, algorithme de Buchberger.
• Théorie de l’élimination.
• Résultants.
• Applications.

D. Cox, J. Little et D. O’Shea, Ideal, varieties and algorithms, Springer, 1997. D. Cox, J. Little et D. O’Shea, Using algebraic geometry, Springer, 1998. T. Becker et V. Weispfenning, Gröbner Bases : A Computational Approach to Commutative Algebra, Springer-Verlag, 1993. D. Eisenbud, Commutative Algebra with a View toward Algebraic Geometry, Springer-Verlag, 1995. Computations in algebraic geometry with Macaulay 2, édité par D. Eisenbud, D. R. Grayson, M. E. Stillman, and B. Sturmfels, Springer, 2001.