Les objectifs du parcours "Algèbre Appliquée" sont d'acquérir une formation moderne et solide au calcul formel, à la géométrie et la cryptographie et de préparer aussi bien à la recherche fondamentale qu'à la recherche et au développement dans l'industrie et les services. A l'issue de la formation, les étudiants doivent être capable de modéliser algébriquement un problème concret en estimer la complexité et utiliser des algorithmes récents pour procéder à sa résolution.
Pour plus d'informations, vous pouvez consulter le site web de cette formation M2 Algèbre appliquée.
Lieu(x) d'enseignement
VERSAILLES
Pré-requis, profil d’entrée permettant d'intégrer la formation
Les étudiants doivent avoir obtenu une première année de Master en mathématiques. Une formation solide en algèbre est particulièrement recommandée : théorie de Galois, algèbre commutative, ensembles algébriques affines. Il est préférable d'avoir quelques notions d'informatique : complexité, notions de cryptographie, algorithmes de base. Voir le programme du M1 Mathématiques et interactions, Site UVSQ qui prépare spécifiquement au M2 Algèbre Appliquée.
Compétences
Modéliser algébriquement un problème concret en estimer la complexité et utiliser des algorithmes récents pour procéder à sa résolution.
Maitriser et mettre en oeuvre des outils et méthodes mathématiques de haut niveau.
Analyser un document de recherche en vue de sa synthèse et de son exploitation.
Maitriser des outils numériques et langages de programmation de référence.
Concevoir et rédiger une preuve mathématique rigoureuse.
Expliquer clairement une théorie et des résultats mathématiques.
Profil de sortie des étudiants ayant suivi la formation
A la fin de la formation, nos étudiants se répartissent de manière à peu près égale en deux groupes : une moitié de la proposition s'engage dans une thèse, le plus souvent dans le laboratoire de recherche où le stage a été effectué. Une autre moitié se dirige vers une activité professionnelle dans une entreprise (industrie ou service). Il est fréquent que les étudiants aient trouvé un travail à la sortie du M2.
Débouchés de la formation
Nous avons deux types de débouchés :
- dans le monde académique ce qui se traduit le plus souvent pas une thèse dans un laboratoire de recherche,
- en entreprise (industrie ou service) pour un emploi en recherche et développement par exemple.
Collaboration(s)
Laboratoire(s) partenaire(s) de la formation
Laboratoire de mathématiques de Versailles.
Programme
Introduction aux bases mathématiques de l'algèbre effective et de la cryptographie.
Ce cours se déroule sur 7 semaine et comporte 21 heures de cours et 21 heures de TD.
Objectifs pédagogiques visés :
Contenu :
Ce cours est consacré à l’étude des courbes elliptiques en vue de leurs utilisations en cryptographie.
- Courbes planes affines et projectives : propriétés locales, diviseurs.
- Courbes elliptiques : généralités, forme de Weierstrass, loi de groupe, couplage de Weil.
- Courbes elliptiques sur les corps finis
- Courbes elliptiques sur le corps des nombres rationnels – Application des courbes elliptiques.
Prérequis :
Algèbre commutative, théorie de Galois, courbes algébriques.
Bibliographie :
- 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.
Ce cours se déroule sur 7 semaines et comporte 21 heures de cours et 21 heures de TD.
Objectifs pédagogiques visés :
Contenu :
Le but du cours est de définir mathématiquement les courbes elliptiques :
- 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.
Prérequis :
Algèbre commutative et Théorie de Galois.
Bibliographie :
- W. Fulton, Algebraic curves, Benjamin 1969
- R. Hartshorne, Algebraic Geometry Springer 1977
- R.J. Walker, Algebraic curves Princeton University Press
- D. Perrin, Géométrie algébrique : une introduction, CNRS Editions, 1995.
Ce cours se déroule sur 7 semaine et comporte 21 heures de cours et 21 heures de TD.
Objectifs pédagogiques visés :
Contenu :
L’objectif du cours est d’aborder les notions modernes de sécurité pour les algorithmes cryptographiques.
1. Chiffrement et signature :
- factorisation (RSA)
- logarithme discret (ElGamal, Schnorr, DSA)
- réduction de réseaux (Merkle–Hellman, Chor–Rivest, NTRU)
RSA :
- attaques multiplicatives
- preuves de sécurité : chiffrement (PKCS#1v1.5, OAEP, REACT)
- signature (ISO/IEC 9796, Full-domain-hash, Probabilistic Signature Scheme)
- générateurs pseudo-aléatoires prouvés sûrs (résiduosité quadratique)
- tests de primalité des entiers (Solovay–Strassen, Miller–Rabin, AKS)
Logarithme discret :
- problème de la chasse au pirate (Boneh–Franklin)
- diffusion sécurisée de contenus audiovisuels
- courbes elliptiques et algorithmes de signature (ECDSA et Nyberg–Ruppel)
- jacobienne d’une courbe hyperelliptique
- couplage de Weil
2. Cryptosystèmes multivariables
- problème MQ : résolution des systèmes d’équations quadratiques
- isomorphismes de polynômes (IP)
- détermination d’une combinaison linéaires de matrices ayant un petit rang (MinRank)
- algorithmes C* (Matsumoto–Imai) et HFE : signatures électroniques ultra-rapides (SFLASH) ou extrêmement courtes (QUARTZ)
- cryptanalyse, y compris symétrique (AES, chiffrement par flot)
3. Attaques physiques :
- cas asymétrique : attaques par injection de faute sur RSA
- mesure de la consommation électrique sur les courbes elliptiques
- mesure du temps de calcul sur le protocole SSL (paiement sur internet).
Prérequis :
Bases d'algèbre et de cryptographie.
Bibliographie :
- 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.
Ce crois se déroule sur 14 semaines et comprends 21 heures de cours et 21 heures de TD.
Objectifs pédagogiques visés :
Contenu :
Le but de ce cours est l’apprentissage de techniques algorithmiques visant à programmer efficacement, ainsi que du langage C. 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.
– Multiplication de matrices 32 × 32 dans GF (2)
– Eléments de base de calcul dans GF(p)
– 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.
– 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).
Prérequis :
Bases d'algèbre, d'algorithmique et de programmation.
Bibliographie :
- 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.
Période(s) et lieu(x) d’enseignement :
Période(s) :
Septembre - Octobre - Novembre - Décembre - Janvier - Février.
Cette UE se déroule sur 7 semaines et comporte 21 heures de cours et 21 heures de TD devant les machines.
Objectifs pédagogiques visés :
Contenu :
Les principaux points étudiés dans ce cours sont :
- Bases de Gröbner,
- Algorithme de Buchberger
- Théorie de l’élimination.
- Résultants.
- Applications et utilisation effective.
Prérequis :
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.
Bibliographie :
- 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,.
Période(s) et lieu(x) d’enseignement :
Période(s) :
Septembre - Octobre - Novembre.
Lieu(x) :
VERSAILLES
Perfectionnement et mise en oeuvre de l'algèbre effective et de la cryptographie.
Algorithmes avancés de la cryptographie, Cryptanalyse
ECTS :
6
Détail du volume horaire :
Cours :21
Travaux dirigés :21
Modalités d'organisation et de suivi :
Coordinateur :Patarin Jacques
Déroulement et organisation pratique :
Ce cours se déroule sur 7 semaines et comporte 21 heures de cours et 21 heures de TD.
Objectifs pédagogiques visés :
Contenu :
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. On détaillera en particulier les points suivants :
– 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, cryp- tanalyse 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.
Prérequis :
Bases en algèbre et en cryptographie.
Bibliographie :
- Douglas Stinson, Cryptographie – Théorie et Pratique (Vuibert, 2003)
– Gilles Zemor : Cours de Cryptographie (Cassini, 2000).
Le stage de déroule sur 6 mois environ dans une entreprise ou dans un laboratoire de recherche. Il débute en mars/avril et se termine par une soutenance en septembre.
Le stage se déroule sous la responsabilité d'un enseignant-chercheur associé au master.
Ce stage comporte obligatoirement un projet de programmation, il fait l'objet d'un rapport de stage et d'une soutenance.
Objectifs pédagogiques visés :
Contenu :
Le but du stage est d'introduire les étudiants à la recherche en laboratoire ou en entreprise ou plus directement à un travail en entreprise qui auront alors à lire, comprendre et appliquer un ou plusieurs articles de recherche ou développement industriel. Ce stage comporte obligatoirement un projet de programmation.
Le but du stage étudiant est de faire le point sur l'avancement du stage a mi-parcours. Il consiste en la rédaction d'un pré-rapport et/ou d'un exposé de présentation du stage.
Période(s) et lieu(x) d’enseignement :
Période(s) :
Juin - Juillet.
Lieu(x) :
VERSAILLES
Modalités de candidatures
Période(s) de candidatures
Du 01/03/2021 au 22/08/2021
Pièces justificatives obligatoires
Curriculum UE (descriptifs des UE suivies) des deux dernières années.
Lettre de motivation.
Tous les relevés de notes des années/semestres validés depuis le BAC à la date de la candidature.
Curriculum Vitae.
Pièces justificatives complémentaires
Attestation de français (obligatoire pour les non francophones).
