• Thierry Berger (Université de Limoges) – Une approche globale des automates algébriques (LFSR, FCSR, AFSR…). Application au design des générateurs pseudo-aléatoires

Résumé : Les automates LFSR et FCSR sont des automates qui calculent le développement selon les puissances croissantes de fractions rationnelles. Dans le cas LFSR, il s’agit de quotients de polynômes binaires (ou à coefficients dans un corps fini), dans le cas FCSR, il s’agit du développement 2-adique de quotients d’entiers. La principale différence entre LFSR et FCSR est la propagation de retenues, ce qui rend les automates FCSR non-linéaires au sens de la GF(2)-linéarité. Cette propriété a permis de les utiliser efficacement pour construire une famille de générateurs pseudo-aléatoires pour le chiffrement à flot (F-FCSR).

Dans cet exposé, nous présentons les propriétés de base des LFSR et des FCSR, le fonctionnement des générateurs F-FCSR et l’attaque de Hell et Johansson sur les F-FCSR basés sur des automates FCSR en mode Galois.

Cette attaque nous a poussé à adopter une approche matricielle pour la construction d’automates FCSR. Cette approche nous a permis de contrecarrer l’attaque précédente et de construire ainsi des automates plus performants simultanément en hardware et software.

Cette approche matricielle peut se généraliser à des anneaux munis d’une topologie I-adique relativement à un élément p particulier. Ceci permet de construire des automates appelés AFSR (Algebraic Feedback Shift Register). Nous donnerons plusieurs exemples d’applications, aussi bien dans le cas classique GF(2)[x] que dans certains anneaux non euclidiens.

Thierry.Berger-27-05-2011 (format pdf)

  • Delphine Boucher (Université de Rennes 1) – Autour des codes définis sur des anneaux de polynômes tordus

Résumé : Dans cet exposé, après avoir fait un bref rappel sur les codes d’évaluation et les codes « q-cycliques » inventés par Gabidulin en 1985, on introduit la classe des codes tordus modules. Ces codes sont définis sur des anneaux de polynômes non commutatifs F[x,theta] où F est un corps fini et la multiplication est régie par la règle x*a=theta(a)*x pour a dans F. On s’intéressera en particulier à donner une matrice génératrice et une matrice de contrôle pour ces codes et on construira des codes tordus auto-duaux.

Delphine.Boucher-27-05-2011 (format pdf)

  • Benoît Gérard (Université Catholique de Louvain)– L’entropie de Shannon : un outil générique pour analyser les attaques statistiques

Résumé : L’entropie de Shannon: un outil générique pour analyser les attaques statistiques.

Les liens étroits qu’entretiennent cryptographie et théorie de l’information sont connus depuis la fondation de cette dernière par Claude Shannon en 1948. Dès 1949, il applique sa théorie de la communication à la science du secret et depuis, la théorie de l’information a été principalement employée dans le cadre de la cryptographie à sécurité prouvée.

En 2009, on retrouve la notion d’entropie pour quantifier la force d’une attaque dans deux cadres assez différents: les attaques par canaux auxiliaires et la cryptanalyse linéaire multiple. L’objectif recherché dans le cadres des attaques par canaux auxiliaires est de pouvoir comparer, avec une métrique unique, différentes attaques (ou différentes implémentations). Dans le cadre de l’analyse de la cryptanalyse linéaire multiple, le but est de contourner la difficulté due à l’aspect multidimensionnel de l’attaque.

Nous nous intéresserons à ce dernier point: l’utilisation de la théorie de l’information pour l’analyse des cryptanalyses statistiques. Nous verrons sur plusieurs exemples que cette technique permet, de façon relativement simple, d’obtenir des résultats intéressants.

Benoit.Gerard-27-05-2011 (format pdf)

  • Eleonora Guerrini (Université de Caen)–Deux problèmes difficiles dans les graphes et leurs applications

Résumé : Dans cet exposé nous allons introduire deux problèmes difficiles dans les graphes: la recherche d’un code identifiant et la recherche d’un noyau, et nous discuterons des applications possibles. Un code identifiant est un sous ensemble structuré de sommets d’un graphe et nous verrons comment utiliser cet objet pour détecter une panne dans un réseau d’ordinateurs. L’existence d’un tel code est garantie pour tout graphe à voisinages disjoints, mais il est difficile de trouver des bornes sur sa taille minimale. Nous verrons des solutions pour résoudre cette question. Un noyau est un sous-ensemble de sommets à la fois stable et dominant. Le problème de savoir si un graphe possède un noyau est un problème NP-complet. Nous montrerons d’une part comment utiliser cette propriété en cryptographie (on cache un noyau dans un graphe aléatoire). D’autre part, nous proposerons des algorithmes qui recherchent un noyau et étudierons leur complexité afin de déterminer comment construire des instances difficiles.

Eleonora.Guerrini-27-05-2011 (format pdf)

  • Sorina Ionica (Ecole Polytechnique)– Couplages, volcans d’isogénies et calcul de l’anneau d’endomorphismes d’une courbe elliptique

Résumé : En 1996, D. Kohel propose un premier algorithme pour le calcul de l’anneau d’endomorphismes d’une courbe elliptique. Sa méthode repose, entre autres, sur un algorithme de parcours en profondeur du graphe d’isogénies (ce qu’on appelle un volcan). Les méthodes existantes a nos jours pour déterminer l’anneau d’endomorphismes utilisent des algorithmes de parcours de graphes d’isogénies. J’expliquerai l’algorithme de Kohel et je montrerai, en utilisant des résultats de ma thèse, que l’on peut calculer l’anneau d’endomorphismes sans avoir a parcourir les volcans d’isogénies et juste en calculant un petit nombre de couplages. Cela est possible lorsque la factorisation du conducteur de l’anneau d’endomorphismes contient que des facteurs premiers de taille pas très grande. Néanmoins, cette méthode a l’avantage d’éviter les calculs coûteux d’isogénies, en les remplaçant par un calcul rapide de couplage.

Sorina.Ionica-27-05-2011 (format pdf)