Salle Jacques-Louis Lions, INRIA Paris, 2 rue Simone Iff, Paris 12ème, Métro Dugommier (ligne 6)
- 10h00, François Morain, LIX, INRIA Saclay-Ile de France : Factorisation d’entiers — hier, aujourd’hui, demain
Résumé : de tous temps, il y a eu des passionnés des nombres pour factoriser des entiers. De nos jours, c’est devenu un enjeu de sécurité. Les techniques ont évolué avec le temps, le matériel également. Après un bref survol du passé et du présent, nous présenterons l’algorithme de factorisation de Shor, qui fonctionne dans le modèle quantique, et qui sert de motivation à une grande partie des recherches sur les ordinateurs quantiques. Nous montrerons que l’arithmétique classique peut apporter son aide à certaines parties des implantations physiques de cet algorithme.
Travail conjoint avec F. Grosshans, T. Lawson, B. Smith. - 11h15, Pierre Karpman, LIX, INRIA Saclay-Ile de France et NTU : Collisions explicites pour la fonction de compression de SHA-1
Résumé : Il y a dix ans, Wang et al. publièrent la première attaque théorique sur la fonction de hachage SHA-1 en montrant comment obtenir des collisions pour un coût d’environ 2^69 appels à la fonction au lieu des 2^80 requis par une attaque générique (W2005). Ces travaux ont eu un impact considérable sur la recherche sur SHA-1 en particulier et sur les fonctions de hachage en général. Cependant, malgré plusieurs améliorations qui ont fait baisser le coût estimé de la meilleure attaque à 2^61 (Stevens, 2013), aucune collision n’a encore été publiquement calculée et beaucoup de travaux se sont concentrés sur l’attaque de versions réduites.Dans cet exposé nous présenterons des améliorations récentes de l’état de l’art sur trois points : 1) nous montrons comment monter des attaques sur la fonction de compression de SHA-1 plutôt que sur la fonction de hachage complète ; 2) nous avons explicitement calculé une collision pour la fonction de compression complète de SHA-1, pour un coût moyen estimé de 2^57 (ainsi que pour une version réduite à 76/80 tours pour un coût moyen de 2^50) ; 3) la recherche de collision a été implémentée sur cartes graphiques et a permis de démontrer l’intérêt de ce type de plateforme pour le calcul d’attaques de cryptographie symétrique (Karpman et al., 2015), (Stevens et al., 2016).
Travaux communs avec Marc Stevens et Thomas Peyrin.
- 14h15, Gwezheneg Robert, IRMAR, Université de Rennes 1 : Décodage des codes de Gabidulin généralisés
Résumé : Les codes de Gabidulin sont l’analogue en métrique rang des codes de Reed-Solomon. Parmi leurs propriétés notables, ils sont optimaux et disposent d’algorithmes de décodage efficaces. Cela explique leur utilisation dans diverses applications, comme par exemple le codage espace-temps. Concevoir un tel code consiste à décrire une famille finie de matrices complexes, éloignées les unes des autres en métrique rang. C’est dans ce but que nous avons généralisé les codes de Gabidulin à des corps de nombres. Dans cet exposé, nous allons nous intéresser à leur décodage, et plus précisément à deux aspects de ce décodage.Nous commencerons par définir les codes de Gabidulin généralisés. Pour cela, nous présenterons les $\theta$-polynômes et la métrique rang. Nous établirons que ce sont des codes MRD (ils atteignent la borne de Singleton pour la métrique rang).La première partie est consacrée au décodage d’erreurs et d’effacements. Cela concerne aussi bien les codes originaux sur les corps finis que leur généralisation. Dans le modèle d’erreur seule, décoder un code de Gabidulin revient à résoudre un problème appelé reconstruction linéaire. Nous verrons un algorithme quadratique résolvant ce problème. Nous présenterons ensuite deux modèles d’effacements, et expliquerons que corriger des effacements revient à décoder un autre code de Gabidulin, avec des paramètres différents.Dans la seconde partie, nous allons considérer des codes dont les coefficients sont dans un anneau d’entiers. Nous serons alors confrontés à un problème spécifique aux corps infinis : la croissance des coefficients. Bien que le nombre d’opérations soit quadratique, la taille des nombres sur lesquels elles portent augmente exponentiellement, rendant l’algorithme inutilisable en pratique. Nous allons donc nous intéresser à la réduction des codes de Gabidulin généralisés, modulo certains idéaux de l’anneau des entiers. Nous montrerons que notre algorithme de décodage calcule le mot du code modulo cet idéal. - 15h30, Marc Kaplan, TelecomParisTech : attaquer les cryptosystèmes symétriques en utilisant l’algorithme quantique de recherche de période
Résumé : au milieu des années 90, la découverte par Peter Shor de l’algorithme qui porte son nom a révélé au monde que les ordinateurs quantiques, quand ils seront disponibles, seront une grande menace pour la cryptographie à clé publique telle qu’on la pratique aujourd’hui. Au coeur de cet algorithme se trouve une procédure de recherche de période dans un groupe. Dans notre exposé, nous montrerons que le plus simple algorithme quantique de recherche de période, connu sous le nom d’algorithme de Simon, peut également être utilisé pour attaquer la cryptographie symétrique.Pour certains groupes assez simples, l’algorithme de Simon permet de trouver la période d’un fonction avec O(n) requêtes quantiques à la fonction alors qu’il faut O(2^n) requêtes classiques. Cela permet de construire des attaques simples en faisant des requêtes en superposition à l’oracle cryptographique. Nous appliquons cette idée à plusieurs cryptosystèmes, incluant certains modes d’operation utilisés pour l’authentification ou le chiffrement authentifié, ainsi que des candidats à la compétition CEASAR. Enfin, nous montrons que les slide attacks reposent sur une structure similaire et peuvent être exponentiellement plus efficaces pour un adversaire quantique que pour un adversaire classique.
