Présentation

Le Séminaire Codes, Cryptographie et Algorithmique (anciennement Groupe de travail sur les codes, puis séminaire IC5) se réunit tous les mois à l'ENSTA à Paris, le matin de 9h30 à 12h00. Le séminaire se propose de réunir des personnes travaillant autour des thèmes de la protection de l'information tant du point de vue théorique qu'appliqué. Chaque réunion se compose de deux exposés de 45 minutes environ.

Les sujets abordés sont notamment : théorie des codes correcteurs, géométrie algébrique, théorie des nombres, cryptographie, cryptanalyse, marquage d'images, théorie de la complexité...

Apres une annee d'interruption, le seminaire CCA va reprendre a la rentree 2008. Il sera co-organise par les equipes ALI (de l'ENSTA) et SALSA (du LIP6). Nous reprendrons le rythme mensuel, avec deux exposes par session. La premiere session aura lieu le 19 Septembre a l'ENSTA (salle precisee ulterieurement).

Solving RSA problems with Lattice Reduction

Alexander May (Universite de Bochum)

Abstract:
this survey addresses the problems of factoring and inverting the RSA function. We define practically relevant relaxed instances of these problems that can be solved in polynomial time. These problem instances are modelled by polynomial equations with small roots. In order to recover the roots, we make use of a method due to Coppersmith which is in turn based on the famous LLL lattice reduction.

As new applications of the method we present an improved Hastad attack on RSA in the case of several RSA encryptions of the same underlying message, and an algorithm for factoring N=pq given 70% of the bits of p in any positions.

Attaques algébriques sur des systèmes sous-déterminés issus de la cryptographie

Luk Bettale (LIP6/SALSA)

Résumé :
Dans cet exposé, je vais vous présenter le travail que j'ai réalisé sur des schémas de signature (TRMS) et de hachage basés sur des systèmes polynomiaux multivariés. Ces systèmes ont la particularité d'être sous-déterminés, et nous avons tenté de trouver un compromis pour une approche hybride résolution par base de Gröbner/spécialisation de variables.