Accueil      Séminaire Crypto

CAEN'03 Algorithmique des Réseaux et ses Applications en Cryptographie. Contact : Fabien Laguillaumie [18 et 19 Juin 2003 | Campus II]

Méthode A.G.M. pour les courbes de genre 3 non-hyperelliptiques Le succés des méthodes AGM pour le comptage des points sur les courbes de genre 1 et 2 en caractéristique 2 n'est plus à démontrer. Nous proposons donc dans cet exposé un algorithme permettant de mettre en oeuvre ce type de méthodes dans le cas des courbes de genre 3 non hyperelliptiques. Nous montrons en particulier comment on choisit un bon modèle relevant la courbe et comment on peut alors déterminer les thêta constantes initiales par la connaissance de ses bitangentes. Christophe Ritzenthaler  (Institut de Mathématiques de Jussieu) [Jeudi 5 Juin 2003 | 17:00 | Campus II - Salle S3 124]

Protocoles d'authentification sur le groupes de tresses Nous présentons trois protocoles d'authentification basés sur le groupe de tresses. L'un d'eux est basé sur une variante du problème de conjugaison, tandis que la sécurité des deux autres repose sur le problème de conjugaison général. Ces deux derniers protocoles sont, dans un cas idéal non pratique, à divulgation nulle de connaissance, et nous décrirons une méthode pour conserver cette caractéristique lors de leur implémentation. Hervé Sibert  (LMNO Caen) [Mercredi 14 Mai 2003 | 17:00 | Campus II - Salle S3 124]

Introduction à la cryptographie sur les tresses Nous introduirons le groupe de tresses, sa structure et les raisons qui le rendent propice à l'établissement de protocoles de cryptographie. En particulier, nous décrirons les problèmes difficiles dans le groupe, et les premiers schémas (échange de clés, PKC) proposés ainsi que les attaques récentes. Hervé Sibert  (LMNO Caen) [Mercredi 7 Mai 2003 | 17:00 | Campus II - Salle S3 124]

Protocoles Zero-Knowledge et Marquage de Logiciels dans les graphes aléatoires Il est possible de définir des cryptosystèmes en cachant une clique ou un noyau dans un graphe aléatoire. Nous avons défini avec Fabrice Boudot un protocole Zero-Knowledge basé sur un noyau caché dans un graphe orienté. Nous verrons que celui-ci peut être utilisé pour le marquage de logiciel pour la protection de la propriété intellectuelle. Il est en effet possible de reprendre les techniques introduites par G.Qu et M. Potkonjak déjà utilisées sur des logiciels approximant des problèmes NP-complets comme SAT ou le coloriage de graphes. Jean-Marie Le Bars  (GREYC Caen) [Jeudi 17 Avril 2003 | 17:00 | Campus II - Salle S3 124]

Cryptographie sur les Graphes Aléatoires Beaucoup de problèmes difficiles sont basés sur la recherche d'un sous-graphe d'un graphe. Un des plus étudiés est la recherche d'une clique (sous-graphe complet) de grande taille. Considérons un graphe aléatoire G, il est conjecturé qu'il n'existe pas d'algorithme probabiliste polynomial qui trouve dans G une clique de grande taille avec une probabilité significative. Soit G' le graphe obtenu en cachant dans G une k-clique (clique de taille k). Est-il aussi difficile de trouver une k-clique dans G' que dans G? Nous verrons comment A. Juels and M. Peinado répondent à cette question. Nous montrerons ensuite comment adapter ce résultat sur les graphes orientés à la recherche d'un noyau. Ce problème étant plus difficile, nous avons la même conjecture que précédemment. Nous évoquerons pour finir une méthode pour "prouver" une telle conjecture : une réduction "pire des cas-cas moyen" utilisée par Ajtai et Dwork pour prouver sûr un cryptosystème basé sur le plus court vecteur dans les réseaux. Jean-Marie Le Bars  (GREYC Caen) [Jeudi 10 Avril 2003 | 17:00 | Campus II - Salle S3 124]

Comptage de points sur des variétés abéliennes en caracteristique 2 Nous présentons une methode, rapide en petite dimension, permettant de calculer le nombre de points d'une variété abélienne (et donc d'une courbe algebrique) définie sur un corps fini de caractéristique 2 Jean-François Mestre  (Institut de Mathématiques de Jussieu) [Jeudi 27 Mars 2003 | 17:00 | Campus II - Salle S3 124]

Cryptanalyses des chiffrements itératifs par blocs Un algorithme de chiffrement itératif par blocs est un algorithme de chiffrement symétrique qui chiffre des blocs de message de taille fixe (en général 64 ou 128 bis). Le système est constitué d'une fonction dite "de tour", aux propriétés cryptographiques assez faibles mais conduisant après un certain nombre d'itérations à un chiffrement résistant. Ces systèmes sont définis sur la base de principes très généraux et il n'existe pas de théorie globale garantissant leur sécurité. Les systèmes doivent résister aux crytanalyses connues. La découverte des cryptanalyses très générales que sont les cryptanalyses différentielle et linéaire en 1991 et 1993 ont permis de formaliser certains critères de résistance, en particulier l'utilisation de fonctions à haute non-linéarité comme composante des fonctions de tour. Cependant, ces fonctions très structurées permettent d'isoler des propriétés discriminantes dans le cadre d'attaques sur le dernier tour. Dans cet exposé, je présenterai le principe des attaques sur le dernier tour et les critères de sécurité qui en ont été déduits. Marion Videau  (INRIA Rocquencourt, Projet CODES) [Jeudi 20 Mars 2003 | 17:00 | Campus II - Salle S3 124]

Systèmes chaotiques et hyperchaotiques pour la transmission sécurisée de données Le développement croissant de réseaux et services à haut débit, en parallèle avec la demande récente du secteur privé et des services payés, a induit un besoin d'exploitation de systèmes complexes et de développement d'algorithmes pour chiffrer l'information. D'où l'intérêt d'une partie de la communauté des automaticiens pour la transmission sécurisée, celle-ci est basée sur deux concepts : l'un vieux comme le monde, mais très mal connu jusqu'au XIXème siècle : le chaos. Et l'autre : la synchronisation de systèmes dynamiques, en particulier les systèmes chaotiques, ce qui a fait l'objet, d'un travail énorme, depuis les années 80. En fait, l'idée de la transmission sécurisée par la synchronisation de systèmes chaotiques consiste dans l'utilisation du phénomène du chaos pour modifier le messages. Ceci en transmettant au récepteur un signal chaotique sommaire, produit par l'émetteur, ce signal en question contient comme information le message confidentiel. Enfin, ce message peut être recouvré en synchronisant le récepteur avec le signal scalaire envoyé par l'émetteur. L'avantage d'employer des méthodes basées sur la théorie du chaos se trouve dans le haut niveau de sécurité qu'offre ce type de systèmes ainsi que la rapidité de calcul due à leur structure dynamique. Ainsi ils sont très compétitifs en raison du fait, qu'ils sont peu coûteux à mettre en oeuvre et à implémenter. Aussi, comme l'information telle qu' elle apparaît de nos jours : de plus en plus numérisée, traitée, échangée, par des organes «pensants »; il devient primordiale d'étudier les systèmes dynamiques en temps discret. Je présente dans ce contexte, en premier lieu, quelques résultats sur un outil mathématique majeure qui m'a permis d'appréhender les caractéristiques des systèmes chaotiques étudiés : la théorie des formes normales. Je propose par la suite un nouvel algorithme de chiffrement basé sur des modèles chaotiques. Le scénario classique d'application de chiffrement chaotique étant un système de communication par addition du message, dans lequel l'émetteur et le récepteur doivent être synchronisés pour avoir une phase de décodage correcte. Je décrirai alors le potentiel de nouveaux crypto-systèmes chaotiques, basés sur l'inclusion du message dans la structure de l'émetteur. Inâm Belmouhoub  (ENSEA Cergy-Pontoise) [Jeudi 13 Mars 2003 | 17:00 | Campus II - Salle S3 124]

Attaques par corrélation des générateurs pseudo-aléatoires pour le chiffrement à flot Dans un algorithme de chiffrement à flot, le chiffré est obtenu en additionnant bit-à-bit le message clair à une suite pseudo-aléatoire, appelée suite chiffrante. Cette suite est produite par un générateur pseudo-aléatoire dont l'initialisation correspond à la clef secrète du système. Dans ce contexte, une attaque à clair connu consiste donc à retrouver cette initialisation à partir de la connaissance de certains bits de la suite chiffrante. Dans ce type d'applications, le générateur pseudo-aléatoire est généralement composé de registres à décalage à rétroaction linéaire, car il s'agit de composants très rapides et faciles à implémenter en hardware. Ces registres peuvent être combinés de différentes manières (combinaison par une fonction booléenne, utilisation d'une fonction de filtrage, contrôle de l'horloge...). Dans ces systèmes, la clef secrète correspond donc à l'ensemble des initialisations des registres utilisés. Tous ces générateurs sont vulnérables aux attaques par corrélation. Cette technique de cryptanalyse, introduite par Siegenthaler, est de type "diviser pour mieux régner" : elle consiste à retrouver l'initialisation de chacun des registres indépendemment des autres. Pour cela, on exploite l'existence d'une éventuelle corrélation entre la sortie du générateur pseudo-aléatoire et celle d'un des registres utilisés. Meier et Staffelbach ont montré que ce type d'attaques pouvait être vu comme un problème de correction d'erreurs, dans lequel la suite chiffrante est assimilée à une version bruitée de la sortie d'un des registres du système. Dans cet exposé, nous présenterons le principe général de ces attaques ainsi que plusieurs techniques proposées récemment pour résoudre ce problème. Ces méthodes reposent sur l'utilisation de différents types de codes correcteurs et d'algorithmes de décodage. Anne Canteaut  (INRIA Rocquencourt, Projet CODES) [Jeudi 20 Février 2003 | 17:00 | Campus II - Salle S3 124]

NICE : un système de chiffrement à clef publique dans les corps quadratiques imaginaires NICE est un système de chiffrement à clef publique dont le principe repose sur des idéaux dans les corps quadratiques imaginaires. Nous allons voir que la structure particulière des idéaux manipulés par le système le rend vulnérable à une attaque à chiffré choisi qui permet de retrouver la clef privée. Eliane Jaulmes  (DCSSI) [Jeudi 13 Février 2003 | 17:00 | Campus II - Salle S3 124]

Attaques sur les petits exposants secrets de RSA Wiener a montré en 1990 qu'il était dangereux d'utiliser des exposants secrets RSA trop petits, sous peine de retrouver la factorisation du module. Son attaque est basée sur des calculs de développement en fractions continues. Cette attaque a été améliorée en 2000 par Boneh et Durfee, qui utilisent les travaux de Coppersmith pour résoudre des équations polynomiales modulaires. Nous montrerons dans cet exposé l'impact de ces attaques sur RSA. Fabien Laguillaumie  (LMNO - France Télécom R&D Caen) [Jeudi 30 Janvier 2003 | 17:00 | Campus II - Salle S3 124]

Signatures de liste et vote électronique II Comme il a été vu dans la première partie de l'exposé, faire une signature de liste revient à prouver qu'on détient un secret lié à la liste. A partir d'un exemple, la seconde partie exposera dans les détails la signature correspondante et démontrera qu'il s'agit effectivement d'une preuve de connaissance d'un certificat de membre. Sébastien Canard  (France Télécom R&D Caen) [Jeudi 23 Janvier 2003 | 17:00 | Campus II - Salle S3 124]

Signatures de liste et vote électronique I Depuis l'introduction des signatures de groupe par Chaum et van Heyst en 1991, il a été dit que de telles signatures sont applicables au vote électronique. Cependant, une modification des propriétés de ces signatures est nécessaire pour qu'un schéma de vote électronique soit mis en place. Il est alors possible d'introduire les signatures de liste, variante non-ouvrable et partiellement reliable des schémas de signature de groupe. L'exposé donnera les propriétés nécessaires des schémas de signature de liste, proposera une solution d'un tel schéma, étudiera la sécurité et montrera comment il est possible d'appliquer ce type de signature au vote électronique. Sébastien Canard  (France Télécom R&D Caen) [Jeudi 16 Janvier 2003 | 17:00 | Campus II - Salle S3 124]

Preuves de connaissance : introduction et applications aux signatures on-line / off-line Cet exposé est en deux parties. En premier lieu, nous analysons un protocole d'authentification classique basé sur RSA, et partons de ses insuffisances pour introduire la notion de preuve (zero-knowledge) de connaissance (et les signatures qui vont avec). Ensuite, nous examinons comment modifier le protocole (sans changer les clés) pour qu'il atteigne le zero-knowledge. Dans l'une des solutions, presque tout le travail peut fait à l'avance, c'est-à-dire préalablement à la procédure d'authentification (ou à la production de signature) proprement dite. On obtient ainsi un schéma à la fois prouvé sûr, "on-line / off-line" et compatible avec RSA (mêmes clés, même sécurité sinon plus). (travail commun avec Jean-Claude Paillès et, pour certains points, avec Jean-Jacques Quisquater). Marc Girault  (France Télécom R&D Caen) [Jeudi 09 Janvier 2003 | 17:00 | Campus II - Salle S3 124]

Suites elliptiques de divisibilité II Dans cette seconde partie, nous précisons les propriétés arithmétiques des EDS (diviseurs, rang d'apparition d'un premier p, périodicité mod p, ...) et nous décrivons rapidement un algorithme efficace de calcul des EDS. Ensuite, nous présentons le problème du logarithme discret sur une EDS, et nous montrons comment R. Shipsey résoud, dans certains cas, ce problème, puis en déduit, par des arguments astucieux, de nouvelles attaques sur le problème du logarithme discret sur une courbe elliptique (supersingulière ou "anomalous") définie sur un corps premier fini. Damien Vergnaud  (LMNO Caen) [Jeudi 5 Décembre 2002 | 17:00 | Campus II - Salle S3 124]

Suites elliptiques de divisibilité Dans cet exposé, en deux parties, nous présentons les résultats récemment obtenus par R. Shipsey dans sa thèse (University of London - 2000), sur l'arithmétique des suites elliptiques de divisibilité (EDS) et leurs applications à la cryptographie elliptique. Dans cette première partie, nous présentons les suites de Lucas (analogues en genre 0 des EDS) et survolons leurs utilisations en cryptographie (LUC, LUCELG, ...). Après un bref rappel sur les polynômes de division des courbes elliptiques, nous donnons la définition et les premières propriétés des EDS. Damien Vergnaud  (LMNO Caen) [Jeudi 28 Novembre 2002 | 17:00 | Campus II - Salle S3 124]

Analyse de la méthode de Gallant-Lambert-Vanstone pour les courbes elliptiques We analyse the method of Gallant, Lambert and Vanstone (CRYPTO 2001) which uses a fast endomorphism $\Phi$ with minimal polynomial $X^2+rX+s$ to compute any multiple $kP$ of a point $P$ of order $n$ lying on an elliptic curve. This method constructs the following decomposition: $$kP = k_1P + k_2\Phi(P), \quad\text{with } \max\{|k_1|,|k_2|\}\leq A\sqrt n.$$ The problem is that until recently no value for $A$ was known and indeed it was conjectured that $A\leq 1$. In February 2002, Park, Jeong, Kim, and Lim~(PKC 2002) gave the first bounds, although they did not manage to prove this conjecture.  In this talk we will produce another value for $A$, based on the original GLV paper. Then we will derive a careful analysis of~(PKC 2002) to find the optimal value of $A$, thus proving the conjecture in the known examples but disproving it in general. One consequence of this work is that the GLV method is not effective for a generic elliptic curve. If time permits, we will also describe a DPA-resistant variant of this algorithm. Francesco Sica  (UCL Crypto Group Louvain-la-Neuve) [Mercredi 20 Novembre 2002 | 17:30 | Campus II - Salle S3 124]

Cryptosystèmes basés sur les réseaux et prouvés sûrs II Guillaume Dabosville  (GREYC Caen) [Jeudi 14 Novembre 2002 | 17:00 | Campus II - Salle S3 124]

Cryptosystèmes basés sur les réseaux et prouvés sûrs I Nous présenterons une connection cas le pire - cas moyen introduite par Ajtai dans son article "Generating Hard Instances of Lattice Problems", qui comme son nom l'indique utilise des problèmes algorithmiques dans les réseaux. Pour cela, nous ferons un bref rappel sur les réseaux et poserons quelques notations. Puis nous donnerons la connection entre le problème d'approximer un plus court vecteur dans le pire des cas et une variante de ce dernier dans une classe bien particulière des réseaux.. Guillaume Dabosville  (GREYC Caen) [Jeudi 07 Novembre 2002 | 17:00 | Campus II - Salle S3 124]

Sur les fonctions booléennes utilisées en cryptographie symétrique L'exposé contiendra une introduction des fonctions booléennes utilisées dans les générateurs pseudo-aléatoires (ainsi que sur les critères de sécurité associés). Il sera présenté ensuite une nouvelle borne sur le nombre de fonctions booléennes m-résilientes. (résultat très récent publié dans les actes d'Asiacrypt'2002) Aline Gouget  (GREYC Caen) [Jeudi 31 octobre 2002 | 17:00 | Campus II - Salle S3 124]

La primalité est décidable en temps polynomial, d'après Agrawal, Kayal, Saxena Eric Reyssat  (LMNO Caen) [Jeudi 24 Octobre 2002 | 17:00 | Campus II - Salle S3 124]

Archives :  2002  2004