- Razvan Barbulescu, LIX, INRIA Saclay – Un algorithme quasi-polynomial pour le calcul du logarithme discret dans les corps finis de petite caractéristique.
Résumé : La sécurité des couplages en petite caractéristique repose sur la difficulté du calcul du logarithme discret dans les corps finis de petite caractéristique. L’algorithme le plus efficace jusque récemment était le crible de corps de fonctions (FFS), avec ses variantes. Ce dernier a une complexité sous-exponentielle, très proche de celle de la factorisation. Les records récents utilisant FFS ont montré que les couplages en petite caractéristique offrent une sécurité plus faible que celle estimée initialement. Mais ce sont les avancées de l’année 2013 qui ont amené une perte de sécurité très importante, rendant lesdits crypto-systèmes inutilisables.
Dans cet exposé, on s’inspire des avancés récentes de Joux et Göloglu et al., mais on n’utilise pas d’outils avancés comme les corps de fonctions et les bases de Gröbner.
L’algorithme consiste à exprimer le logarithme discret recherché comme une somme de logarithmes discrets d’éléments plus petits, pour une notion de taille qu’on va préciser. Ainsi on met en place un arbre dont les feuilles sont des éléments pour lesquels on connaît le logarithme discret. Étant donné que le temps passé à chaque nœud est polynomial et que le nombre de nœuds est quasi-polynomial, on obtient un algorithme quasi-polynomial.
Razvan.Barbulescu-10-01-2014 (format pdf)
- Philippe Gaborit, XLIM, Université de Limoges – Nouveaux résultats pour la cryptographie en métrique rang
Résumé: La cryptographie en métrique rang s’est développée à partir de 1991 et du cryposystème GPT qui est une adaptation du cryptosystème de McEliece en métrique rang.
L’intérêt principal de la métrique rang est que les meilleures attaques connues ont une complexité qui grandit très vite, permettant d’avoir des tailles de clés relativement petites de quelques milliers de bits. Cependant le système GPT étant basé sur des codes très structurés (les codes de Gabidulin qui sont en équivalent des codes de Reed-Solomon en métrique rang), il a fait l’objet d’attaques structurelles fortes et de réparations successives.
Dans cet exposé nous présenterons une nouvelle approche pour la cryptographie en métrique rang à partir d’une nouvelle famille de codes peu structurés décodables: les codes LRPC (Low Rank Parity Check codes), qui permettent d’avoir des tailles de clés de chiffrement de l’ordre de 1500b, tout en étant très rapides. On présentera aussi une nouvelle approche générale pour la signature basée sur les codes, qui à partir des codes LRPC permet d’obtenir un algorithme de signature très efficace avec des tailles de clé et de signature de seulement quelques milliers de bits. Enfin on présentera un nouvel algoritme générique d’attaque en métrique rang qui adapte efficacement les idées traditionnelles de l’approche Information Set Decoding.
Les resultats présentés sont issus de collaborations avec: O. Ruatta, J. Schrek et G. Murat (Univ. Limoges) et G. Zémor (Univ. Bordeaux).
- Christophe Clavier, XLIM, Université de Limoges – Rétro-conception de paramètres secrets d’AES par analyse de canaux auxiliaires et analyse de fautes
Résumé : Dans certains types d’applications des cartes à puce (notamment la téléphonie mobile ou la télévision à péage), les algorithmes de chiffrements ou fonctions d’authentification utilisés sont souvent ‘propriétaires’ c’est à dire que leurs spécifications sont tenues secrètes et connues seulement des opérateurs et fabricants des cartes. Pour des raisons économiques (éviter une étape de conception spécifique) ces fonctions sont parfois des variantes d’algorithmes publiques connus (DES, AES,…) dans lesquelles tout ou partie des paramètres les définissant ont été modifiés (par exemple en choisissant une boite de substitution différente). Dans ce cas, le secret de la fonction ne réside que dans un jeu de paramètres non divulgués. Dans cet exposé nous nous intéressons à la révélation des paramètres secrets des algorithmes propriétaires basés sur l’AES en considérant que tous les paramètres de l’AES ont pu être simultanément modifiés. Sous différents modèles, nous montrons comment un adversaire peut exploiter des fuites d’information apportées par l’observation de la consommation de courant (attaque de type SCARE) ou l’injection de fautes (attaque de type FIRE) pour retrouver les valeurs de ces paramètres. Certaines des attaques présentées révèlent les paramètres secrets y compris lorsque l’implémentation de la fonction cryptographique est protégée contre ces types d’attaques physiques par la présence simultanée de plusieurs contre-mesures.
- Nicolas Estibals, IRISA, Université de Rennes 1, Un algorithme pour trouver toutes les formules calculant une application bilinéaire.
Résumé : La multiplication est une opération arithmétique coûteuse comparativement à l’addition. Aussi il est intéressant, étant donné une application, de minimiser le nombre de produits à effectuer pour la calculer. Dans cette étude, nous nous restreignons au cas des applications bilinéaires.
En effet, parmi les applications bilinéaires, nous étions intéressés en premier lieu par la multiplication polynomiale. Ce problème ancien a déjà été très étudié. La première découverte fut celle de Karatsuba (1962) qui montra que l’on peut effectuer le produit de deux polynômes de degré 2 en n’utilisant que 3 produits au lieu de 4 avec l’algorithme quadratique. Puis Toom & Cook (1963) montrèrent que 5 multiplications suffisent à calculer le produit de polynômes de degré 3. En généralisant le problème aux polynômes de degré n fixé, on définit alors M(n) le nombre minimal de produits à effectuer pour une telle multiplication. Le calcul de M(n) est difficile et on ne dispose bien souvent que de bornes supérieures, de formules sans preuve de leur optimalité. En 2005, Montgomery effectua une recherche exhaustive de formules pour la multiplication de polynômes de degré 5 et trouva de nouvelles formules pour le degré 6 et 7.
Nous avons alors cherché à généraliser son approche et réduire son coût grâce à une formalisation en terme d’espace vectoriel. Nous présentons ainsi un algorithme permettant d’énumérer toutes les formules contenant exactement k produits calculant une application bilinéaire. Cet algorithme permet de calculer le nombre minimal de produits à calculer pour certaines applications bilinéaires.
Enfin, notre algorithme ne se restreignant pas au produit de polynômes, nous avons pu appliquer cet algorithme à d’autres problèmes tels que : le produit court, la multiplication dans une extension de corps ou encore de matrices.
