Ecole de Recherche CIMPA-Mauritanie
Théorie Algorithmique des Nombres et Cryptographie
Nouakchott, 15-26 Février
2016
|
|
Cours 1 : Michel Waldschmidt (Université de
Paris, France) : Titre : Arithmétique
modulaire, fractions continues, attaques basées sur les fractions continues,
corps finis. Résumé : Dans la cryptanalyse du cryptosystème RSA, une méthode, due à Michael J. Wiener,
consiste à développer en fraction continue le quotient e/N, où e est
l'exposant de chiffrement; elle montre qu'il faut choisir l'exposant secret d
supérieur à la racine quatrième de N. La description complète de cette
attaque nécessite des bases sur l'arihmétique
modulaire et les fractions continues qui seront introduites dans le cours.
Une introduction à la théorie des corps finis complétera ce cours. Cours 2 : Djiby Sow
(Université de Dakar, Sénégal) et Abdelmalek Azizi
(Université de Oujda, Maroc) : Titre : Tests de primalité,
générateurs, logarithme discret, Diffie-Hellman, El
Gamal classiques. Résumé : En 1976 Whitfield Diffie et Martin Hellman ont introduit le concept de cryptologie
asymétrique basé sur des fonctions à sens unique avec trappe. Cette dernière
fonction se base sur l’utilisation de certaines opérations mathématiques :
par exemple on peut calculer rapidement l’exponentiation modulaire, mais le
calcul de son inverse, le logarithme discret, reste de complexité
sous-exponentielle, en général. Pour le cas du logarithme discret, on obtient
une meilleure sécurité sur un groupe sur les courbes elliptiques. Dans ce
cours, 1ere
partie : (Abdelmalek Azizi) on va examiner les tests de primalité, les
générateurs et certains problèmes liés aux fonctions à sens unique, notamment
le problème du logarithme discret et la difficulté de sa résolution, la
méthode d’échange de clés de Diffie-Hellman, le
chiffrement d’ElGamal et la signature DSA. 2eme
Partie (Djiby Sow) : on va présenter le concept de preuve de sécurité
pour la cryptographie asymétrique (à clés publique), puis on examinera la
preuve de quelques algorithmes (Signature PSS, Chiffrement EL Gamal, GHR,
chiffrement RSA-OAEP, Signature OTS, etc). Course 3 : Brigitte Vallée and Abderrahmane Nitaj (Université de Caen,
France) : Title : The RSA and Rabin
cryptosystems, factorization, digital signatures. Abstract :
RSA, the first public key cryptosystem to be proposed, is still the most
widely used public key cryptosystem. Its security is based on a problem which
is believed to be difficult: the integer factorization problem. In this
course, we first review the principles of the RSA cryptosystem and the
related Rabin cryptosystem, as well as the accompanying signature schemes.
Then we study some techniques of factorization, including the p-1 method, the
Pollard Rho method, and the Quadratic Sieve. Cours 4 : Brigitte Vallée (Université de
Caen, France) : Titre : Géométrie des nombres et
réseaux euclidiens ; diverses notions de réduction des réseaux :
algorithmique de la réduction : algorithmes LLL et BKZ ; problèmes difficiles
dans les réseaux. Résumé : Dans ce cours, on présente les notions
fondamentales de la géométrie des nombres et des réseaux euclidiens. Puis on
présente différentes notions de réduction, qu’on compare du double point de
vue de leur qualité et de la complexité des algorithmes associés. On
différencie ainsi des problèmes faciles des réseaux des problèmes difficiles.
On présente ensuite un puissant algorithme de réduction, inventé en 1982 par Lenstra, Lenstra et Lovasz et baptisé algorithme LLL. Cet algorithme présente
un bon compromis entre la qualité de la base obtenue et le temps mis à
l’obtenir. C’est pourquoi cet algorithme a de multiples applications, dans
beaucoup de domaines des mathématiques ou de l’informatique théorique. On
présente quelques applications frappantes de l’algorithme LLL. Cours 5 : Abderrahmane Nitaj (Université de
Caen, France) : Titre : Applications de
l’algorithme LLL en cryptographie (méthode de Coppersmith;
cassage de cryptosystèmes Knapsack,
GGH, NTRU, RSA, LWE). Résumé : Ce cours est la suite du
Cours 4. L’algorithme LLL est aussi très utilisé en cryptographie. Nous présentons
en détail comment casser le cryptosystème appelé Knapsack. Aussi, nous montrons comment appliquer
l'algorithme LLL pour attaquer des cryptosystèmes
plus sophistiqués, en particulier les cryptosystèmes
GGH, NTRU et LWE. Enfin, nous présentons en détail la méthode de Coppersmith qui permet d’attaquer le cryptosystème
RSA dans certaines situations. Cette méthode utilise les techniques de
réduction des réseaux et donne des résultats remarquables dans la
cryptanalyse du cryptosystème RSA. Cours 6 : Sylvain Duquesne (Université de Rennes, France) : Titre : Courbes
elliptiques, ECC, Couplages, Schoof, ECM, Diffie-Hellman, El Gamal elliptiques. Résumé : En raison d'algorithmes
de factorisation (cours 2) de plus en plus efficaces, le système RSA requiert
des clés de plus en plus grandes et implique donc des temps de calculs de
plus en plus longs. Les cryptosystèmes basés sur le
logarithme discret (cours 5) permettent de pallier une partie du problème
mais il ne peut être résolu de façon satisfaisante qu'en utilisant les
courbes elliptiques. Nous introduirons donc cet objet issu de la géométrie
algébrique, expliquerons comment il est utilisé en cryptographie et nous
donnerons certains algorithmes basés sur les courbes elliptiques et utiles en
cryptographie. |