Algorithmique des réseaux euclidiens et applications
Master Pro ISFA, filière Codes, Cryptographie et Sécurité, Hiver 2008.
Un réseau euclidien est une grille de points
régulièrement espacés dans Rn pour un certain
n. L'étude mathématique de ces objets date de la fin du
19e siècle, avec les travaux de Hermite et Minkowski sur la
géométrie des nombres. Leur étude informatique
remonte au début des années 1980, avec l'article
fondateur de Arjen Lenstra, Hendrik Lenstra et Laszló
Lovász, dans lequel ils décrivent ce qui est maintenant
connu sous le nom d'algorithme LLL. L'algorithmique des réseaux
a alors connu un essor considérable, qui s'explique par la
grande diversité de ses applications:
- Théorie algorithmique des nombres : factorisation de
polynômes, équations diophantiennes, calculs dans les
corps de nombres, ...
- Cryptanalyse : cassage des chiffrements de type “sac-à-dos”,
cryptanalyses modernes de RSA, ...
- Cryptographie : cryptosystèmes reposant sur la
difficulté algorithmique de problèmes liés aux
réseaux (Ajtai-Dwork, GGH, NTRU)
- Arithmétique des ordinateurs : arrondi des fonctions
élémentaires, approximation polynomiale à coefficients
contraints
- Mais aussi : optimisation combinatoire, théorie de
l'information, théorie algorithmique des groupes, ...
Dans ce cours, nous introduirons les réseaux euclidiens, les
problèmes algorithmiques qui leur sont propres et les
principaux algorithmes qui leur sont consacrés. Nous
insisterons particulièrement sur les applications (destructives
et constructives) en cryptographie.
Beaucoup de matériel lié au cours se trouve
là.
Un exemple
d'exécution de l'algorithme LLL.
Travaux pratiques
Voici du code PARI/GP de solutions possibles.
- TP1 : bases aléatoires, orthogonalisation de Gram-Schmidt.
- TP2 : algorithmes de Gauss et de proprification.
- TP3 : algorithme LLL.
- TP4 : Méthode de Coppersmith.
- TP5 : GGH et NTRU.