Je présenterai un nouveau cryptosystème du même type que le chiffrement El Gamal sur une courbe elliptique. J'introduirai brièvement les objets mathématiques y intervenant. Puis après l'avoir décrit, j'en dicuterai les avantages et les inconvénients. Malgré un taux de transmission quatre fois plus long qu'un chiffrement El Gamal sur une courbe elliptique, ce cryptosystème ne présente aucun problème de codage. De plus, ses propriétés de sécurité (OW-CPA et IND-CPA) sont analogues à celles du chiffrement El Gamal sur la courbe elliptique sous-jacente.

La cryptographie à clé publique nécessite d'effectuer des opérations arithmétiques sur des corps (ECC) ou des anneaux (RSA). Il existe plusieurs classes de moduli offrant des propriétés intéressantes pour effectuer cette arithmétique modulaire: Mersenne, pseudo Mersenne, Mersenne généralisés... Nous verrons comment un système de représentation plus adapté à l'arithmétique modulaire peut permettre de créer toute une classe de moduli efficaces. Ce changement de représentation offre de nombreuses possibilités mais amène de nombreuses problématiques liées entre autre aux réseaux euclidiens.

Je présenterai un algorithme de génération de courbes hyperelliptiques de genre 2 à multiplication complexe. Ces courbes se regroupent par classe des polynômes, dont les racines sont les invariants de ces courbes, que nous calculons. Toutes les courbes d'une seule classe ont la particularité que leur anneau d'endomorphismes est isomorphe à l'anneau des entiers d'un même corps quartique à multiplication complexe. De manière classique, la méthode de la multiplication complexe utilise des calculs sur le corps des complexes. Nous travaillons sur un corps 2-adiques ce qui nous permet d'abaisser la complexité du calcul des j-invariants par rapport à l'évaluation classique des theta-constantes. La reconnaissance des polynômes de classes se fait alors par LLL. Ainsi, alors que la méthode classique aboutissait à un calcul de polynômes de classe de degré inférieur à 10, nous pouvons atteindre des degrés de polynômes de classe de l'ordre de la centaine.

Travail commun avec P. Gaudry (CNRS, LIX), D. Kohel (University of Sydney), C. Ritzenthaler (UAB) et A. Weng

Nous décrivons un algorithme de calcul d'index pour résoudre le problème du logarithme discret sur la jacobienne d'une courbe hyperelliptique. Cet algorithme utilise l'idée classique de l'emploi de large primes. Alors que le cadre usuel d'application de cette idée a donné lieu jusqu'alors à des analyses empiriques, nous sommes en mesure, dans le cas précis qui nous intéresse, de fournir une analyse du gain apporté. La complexité de l'algorithme est abaissée par rapport aux travaux antérieurs (elle demeure exponentielle). Par exemple, pour une courbe de genre 3 définie sur GF(q), on passe de O(q^1.42) à O(q^1.33). La mise en pratique de l'algorithme montre qu'expérimentation et théorie s'accordent.

Travail commun avec P. Gaudry (CNRS, LIX) et N. Thériault (CACR).

Sébastien Kunz-Jacques
Frédéric Muller
Frédéric Valette

Dans cet exposé, nous présentons plusieurs attaques par mesure de courant contre le DES s'inspirant de la cryptanalyse "conventionnelle".

Tout d'abord, nous parlons des attaques par collision. Cette famille d'attaque illustre l'utilisation de la cryptanalyse différentielle dans le domaine des attaques par mesure de courant. Ces résultats ont été publiés à CHES 2004. Ensuite, nous présentons une application de la célèbre cryptanalyse de Davies et Murphy, qui a été publiée à ASIACRYPT 2004. Ces deux attaques ont quelques avantages par rapport aux techniques classiques (comme la DPA) : elles peuvent cibler d'autres tours du DES que les premiers ou les derniers. Par ailleurs, elles peuvent permettre de parer certaines contre-mesures (comme le masquage des données intermédiaires).

Tous ces résultats récents montrent que les techniques de cryptanalyse "traditionnelle" peuvent être utilisées pour construire des attaques par canaux auxiliaires.

La construction de Maiorana-McFarland a été initialement proposée pour construire des fonctions courbes. Elle a été étendue pour construire des fonctions résilientes fortement non-linéaires. La construction classique partage les variables en deux sous-ensembles disjoints. Ici, nous l'étendons en décomposant l'espace en deux sous-espaces supplémentaires. Un des sous-espaces peut être vu comme un code linéaire dont les paramètres induisent des propriétés cryptographiques à la fonction construite. Les propriétés cryptographiques auquelles nous nous intéressons sont la non-linéarité, la résilience et les critères d'avalanche et de propagation.

Nous introduisons le concept de vérification assistée par serveur qui consiste à accélérer la phase de vérification d'une authentification ou d'une signature en déléguant une partie des calculs à un serveur ayant une forte puissance de calcul mais pas nécessairement de confiance. Nous définissons alors un modèle réaliste qui s'applique à la plupart des situations de la vie courante. Nous analysons ensuite, dans ce modèle, les quelques solutions déjà existantes, à savoir la modification de Lim-Lee du schéma de Schnorr et la variante RSA-like du schéma GPS. Enfin, nous proposons une solution générique dans le cas de schémas de signature basés sur l'utilisation d'applications bilinéaires, tels que le schéma de Boneh-Boyen et le schéma de Zhang-Safavi-Naini-Susilo.

Nous décrirons un algorithme pour calculer des logarithmes discrets sur une courbe elliptique définie sur un corps fini de la forme GF(p^n), avec n supérieur ou égal à 3. Notre stratégie s'appuie sur une restriction de Weil. La différence principale avec les attaques connues précédemment est que nous ne travaillons pas dans la Jacobienne d'une courbe potentiellement compliquée; nous utilisons une méthode de calcul d'index qui fonctionne dans une variété abélienne quelconque.

Nous obtenons ainsi un algorithme qui est asymptotiquement plus rapide que la méthode Rho de Pollard pour tout n > 2. Les cas les plus intéressants sont n=3 et n=4, car pour des n plus grands, les constantes impliquées deviennent gigantesques si bien que l'on sort de n'importe quel contexte réaliste.

We introduce a new computational problem related to the interpolation of group homomorphisms which generalizes many famous cryptographic problems including discrete logarithm, Diffie-Hellman, and RSA. As an application, we propose a generic undeniable signature scheme. Our scheme is generic in the sense that we transform a private group homomorphism from public groups G to H (the order of $H$ being public) into an undeniable signature scheme. It is provably secure in the random oracle model provided that the interpolation problem is hard and it offers the advantage of making the signature size arbitrarily short (depending on a security level). We propose an example with complexity similar to RSA and with 3-byte signatures. We will also discuss an example where the homomorphism is a group character (MOVA scheme).

La sécurité de nombreuses primitives cryptographiques est basée sur la difficulté de la résolution de systèmes polynomiaux : parfois la clef publique est elle-même le système algébrique à résoudre (système HFE), parfois un schéma cryptographique peut être attaqué en construisant et en résolvant un système algébrique associé. Ces méthodes sont regroupées sous l'appellation Cryptanalyse Algébrique, et peuvent fournir de nouvelles techniques d'attaque sur des schémas qui résistent aux cryptanalyses linéaires et différentielles.

Les bases de Gröbner constituent un outil important pour la résolution de systèmes d'équations algébriques, et leur calcul est souvent la partie difficile de la résolution. Je présenterai dans cet exposé des résultats de complexité du calcul de bases de Gröbner, pour des systèmes surdéterminés, et en particulier pour des systèmes booléens (systèmes modulo 2 contenant les équations de corps $x_i^2=x_i$ pour chaque variable $x_i$).

Dans le cas générique ("aléatoire"), des outils existent pour analyser cette complexité pour un système non surdéterminé (suites régulières, borne de Macaulay). Je montrerai comment ces résultats s'étendent au cas surdéterminé et au cas booléen : suites semi-régulières, degré de régularité, analyse asymptotique précise du degré de régularité. Ces résultats de complexité permettent d'analyser la complexité d'attaques algébriques (système HFE, systèmes de chiffrement symétriques).

Le but de la stéganographie est d'assurer la confidentialité d'un message. Cette confidentialité est obtenue en dissimulant l'existence même du message. Pour cela, la stéganographie utilise une communication anodine, qu'elle détourne de son but original, en y insérant le message. Cette insertion doit introduire le moins de distorsion possible dans le document d'origine, afin de passer inaperçue.

Dans un premier temps, je présenterai les différents domaines où la stéganographie peut être mise en place, ainsi que quelques techniques représentatives. Dans une seconde partie, je donnerai une formalisation du problème de dissimulation dans des documents numériques et détaillerai des résultats obtenus, au court d'une collaboration avec G. Kabatiansky, en reliant la dissimulation d'information à des problèmes de théorie des codes.

Essentiellement, le principal problème intervenant est celui de construire des recouvrements disjoints de l'espace de Hamming binaire. Je montrerai comment exploiter les résultats connus sur ces objets pour étudier et construire des schémas de dissimulation.

Nous proposons un nouveau générateur pseudoaléatoire, basé sur des registres FCSR (Feedback with Carry Shift Registers). La principale différence entre les FCSRs et les LFSRs plus usuels est la prise en comptes de retenues lors des additions élémentaires. Il en résulte que les propriétés des FCSRs s'obtiennent en interprétant leur structure à l'aide de quotients 2-adiques, au lieu des quotients de polynômes qui permettent classiquement d'étudier les LFSRs.

Nous associons au FCSR une fonction de filtrage pour que le générateur résiste à la cryptanalyse, mais comme la structure du FCSR n'est pas linéaire, la fonction de filtrage peut être très simple. Nous obtenons un générateur particulièrement rapide en Hardware (mais aussi en software) et résistant à toutes les attaques connues.

En 1990, Wiener a montré comment appliquer les fractions continues pour casser les cryptosystèmes RSA, de module n=pq, si la clée secrète est inférieure à n^0.25. Cette borne fut ameliorée en 2001 par de Weger dans le cas où les deux nombres premiers p et q sont voisins. Nous montrons comment étendre ce résultat si p et q ne sont pas obligatoirement voisins mais ont une forme particulière.

Récemment, Blomer et May ont introduit la notion de clée faible et ont montré comment cryptanalyser RSA utlisant ces clées. Cette méthode est basée sur une combinaison des fractions continues et de l'algorithme LLL, via le théorème de Coppersmith. Nous montrons qu'il existe plusieurs sortes de clées faibles et nous indiquons les moyens de casser les cryptosystèmes utilisant une de ces clées.

Often presented as a new technological revolution, Radio Frequency Identification (RFID) makes possible the identification of objects in open environments, with neither physical nor visual contact. They consist of transponders inserted into the objects, of readers which communicate with the transponders using radiofrequencies and usually of a database which contains information on the tagged objects.

The boom which RFID technology is enjoying today rests essentially on a willingness to develop tiny and inexpensive transponders, called tags. This has opened the door to new applications from which unexplored issues emerged. Among these issues, we will consider the traceability problem: How to allow only authorized parties to identify tags without allowing adversaries to trace them?

After having presented this technology, its applications and its issues, we will suggest an adversarial model suited to RFID systems. We will review some existing RFID protocols and will show that most of those which are based on 3 rounds suffer from weaknesses. We will then present RFID protocols based on identifier self-refreshment and we will discuss the relevance in terms of traceability of using hash functions and symmetric or asymmetric encryption algorithms in such protocols.

Les reseaux sont des sous-groupes discrets de R^n. On represente un reseau par une Z-base, c'est-a-dire d vecteurs lineairement independants tels que le reseau soit l'ensemble des combinaisons lineaires (a coefficients entiers) de ces d vecteurs. Le but de la reduction de reseau est de trouver de bonnes bases, comme celles formees de vecteurs relativement courts. Ce probleme a beaucoup d'applications en mathematiques et en informatique, particulierement en cryptologie et en theorie de la complexite.

Gauss a invente un algorithme de reduction efficace en dimension deux, qui est en quelque sorte une adaptation du celebre algorithme d'Euclide pour calculer des pgcds. En 1982, Lenstra, Lenstra et Lovasz ont invente le premier algorithme de reduction efficace en dimension arbitraire. Cet algorithme legendaire est connu sous le nom de LLL: c'est l'un des algorithmes les plus importants de la theorie des nombres algorithmique.

Dans cet expose, nous revisiterons la reduction de reseau, en partant de Gauss jusqu'a LLL, en presentant des resultats recents obtenus en collaboration avec Damien Stehle (LORIA), qui permettent "intuitivement" de faire le lien entre Gauss et LLL. Aucune connaissance prealable de Gauss ou LLL n'est requise.

Les protocoles cryptographiques sont des petits programmes concurrents destinés à garantir la sécurité des échanges entre des participants dans un milieu non sûr. Le bon fonctionnement de ces protocoles devient crucial avec le développement très important des échanges électronique sur le réseau (commerce électronique notamment).

Le modèle d'intrus généralement utilisé par les démonstrateurs automatiques est le modèle standard dit de Dolev-Yao reposant sur l'hypothèse du chiffrement parfait qui idéalise les algorithmes de chiffrement: on ne peut acquérir aucune connaissance sur un message chiffré si on ne connaît pas la clef de déchiffrement. D'autre part, les primitives cryptographiques sont le plus souvent représentées par des symboles de fonctions libres.

Ces hypothèses simplificatrices ont été prises à cause de la complexité des problèmes de vérification, mais s'avèrent trop fortes: certaines attaques, voire même le déroulement honnête de certains protocoles, utilisent les propriétés algébriques des opérateurs.

Concernant la vérification formelle de protocoles cryptographiques en présence de propriétés algébriques, des résultats existent depuis peu. Je vous présenterai un certain nombre de résultats dans ce domaine.

Soient b_1, ..., b_n, n vecteurs linéairement indépendants de Z^n. On note L = L(b_1,...,b_n) l'ensemble des combinaisons linéaires entières des vecteurs b_1, ...,b_n. L forme alors ce que l'on appelle un réseau. Un réseau est un ensemble infini de points (ici des points de Z^n). La façon la plus naturelle et la plus utilisée en algorithmique pour représenter un tel objet, est d'en donner une base, ici constituée des vecteurs b_1, ..., b_n.

Dans l'exposé nous proposons de répondre à la question suivante : Soit L un réseau de Z^n et O_L une fonction (appelée oracle) qui prend en entrée des points x de Z^n et qui renvoie 1 (répond OUI) si x est un point de L, 0 (NON) sinon. Peut-on lorsque l'on détient un tel oracle associé à L, en déduire une base de L ? L'oracle est en quelque sorte une abstraction de toute représentation possible d'un réseau, partant du principe qu'une représentation permet au minimum de tester l'appartenance d'un point au réseau.

Joint work with : Pierre-Alain Fouque and David Pointcheval (ENS)

Password-based authenticated key exchange are protocols which are designed to be secure even when the secret key or password shared between two users is drawn from a small set of values. Due to the low entropy of passwords, such protocols are always subject to on-line guessing attacks. In these attacks, the adversary may succeed with non-negligible probability by guessing the password shared between two users during its on-line attempt to impersonate one of these users. The main goal of password-based authenticated key exchange protocols is to restrict the adversary to this case only.

In this talk, we consider password-based authenticated key exchange in the three-party scenario, in which the users trying to establish a secret do not share a password between themselves but only with a trusted server. Towards our goal, we recall some of the existing security notions for password-based authenticated key exchange protocols and introduce new ones that are more suitable to the case of generic constructions. We then present a natural generic construction of a three-party protocol, based on any two-party authenticated key exchange protocol, and prove its security without making use of the Random Oracle model. Next, we present a more efficient construction based on the two-party encrypted key exchange protocol of Bellovin and Merritt, whose proof of security is in the random oracle model and based on new and apparently stronger variants of the decisional Diffie-Hellman problem. To the best of our knowledge, these protocols are the first provably-secure password-based protocols in the three-party setting.

In 1996, Don Coppersmith proposed a method for finding small solutions of polynomial equations. This method in turn is based on the famous LLL lattice reduction algorithm of Lenstra, Lenstra and Lovasz. The talk gives a brief introduction to Coppersmith's method and shows new applications for the RSA cryptosystem:

1. Partial Key Exposure Attacks on RSA: Assume an attacker succeeds to obtain a fraction of the bits of the secret key d. How many of the bits does he need in order to find the entire secret key? With the help of Coppersmith's method, one can construct polynomial time algorithms that find the entire key using only a fraction of the secret key bits, provided that the public key e is not too large.

2. A Generalized Wiener Attack: In 1990, Wiener showed that small RSA secret keys d < N^0.25 yield the factorization of the RSA-modulus N in polynomial time. Using Coppersmith's method, one can extend this attack to secret keys of the form d=d1/d2 modulo phi(N) with small d1 and d2.

3. Computing d vs. Factoring: One can show that the problem of computing the RSA secret key is deterministic polynomial time equivalent to the problem of factoring the RSA-modulus N.

Les cryptosystèmes basés sur les codes comme le schéma de Mc Eliece ont beaucoup d'avantages par rapport aux cryptosystèmes basés sur la théorie des nombres. Ils ont cependant un inconvénient majeur, la taille très imortante de leur clé publique. On propose dans cet exposé une méthode pour raccourcir la taille de ces clés publiques. L'idée principale de cette méthode consiste à utiliser la quasi-cyclicité de certains codes. En utilisant des sous-codes quasi-cycliques de la classe des codes BCH primitifs on montre qu'on peut arriver à obtenir une taille de clé en O(n) pour n la longueur du code et ce pour les paramètres de sécurité habituels. A titre d'exemple, on propose des valeurs de paramètres de clé publique d'une valeur de 12 kilobits en longueur 2047 ou de 20 kilobits en longueur 4095.

Les signatures digitales classiques ont la propriété, parfois indésirable, d'être universellement vérifiables par toute personne possédant la clé publique du signataire. D. Chaum et H. van Antwerpen ont introduit, en 1989, le concept de signature indéniable dont la vérification ne peut s'effectuer sans interaction avec le signataire. Dans cet exposé, nous présenterons deux protocoles de signatures indéniables.

Le premier protocole, issu d'un travail en collaboration avec Fabien Laguillaumie (Time-Selective Convertible Undeniable Signatures, CT-RSA 2005 à paraitre) offre au signataire la possibilité additionnelle de convertir des signatures indéniables en des signatures universellement vérifiables. Ce schéma, basé sur les couplages, est performant et produit des signatures courtes ; sa sécurité, dans le modèle de l'oracle aléatoire, repose sur le problème Diffie-Hellman et un problème décisionnel non standard.

Le second protocole revisite le schéma de signatures indéniables basé sur l'identité proposé par C. H. Lim et P. J. Lee en 1992. Ce protocole, publié sans analyse de sécurité et reposant sur le problème RSA, est beaucoup plus efficace que celui récemment présenté par B. Libert et J.-J. Quisquater. Nous prouverons la sécurité du schéma, sous des hypothèses algorithmiques classiques, dans le modèle de l'oracle aléatoire et nous montrerons que le protocole devient significativement plus efficace une fois considéré dans un contexte de groupes de classes.

En 1997, le National Institute of Standards and Technology lancait un appel d'offre pour choisir un nouvel algorithme de chiffrement à clé secrète pour le 21éme siécle, la longueur de ses clés devait le prémunir contre les attaques connues. C'est finalement Rijndael qui a été choisi comme AES le premier octobre 2000.

Cet exposé tentera donc de faire une présentation exhaustive des attaques connues à ce jours contre l'AES sur des versions possédant un nombre d'étages réduit. En effet, il parait encore aujourd'hui irréaliste de vouloir attaquer l'AES dans sa version complète.

La plupart des attaques se sont donc concentrées sur le "défi" proposé par les auteurs de l'AES quand ils écrivaient, dans le premier article décrivant Rijndael : "For the different block lenghts of Rijndael, no extensions to 7 rounds [of a known attack] faster than an exhaustive key search have been found". Naturellement, aujourd'hui plusieurs cryptanalyses ont atteint ce but, notamment l'amélioration de la "Square Attack" proposée par Ferguson et al. et la Bottleneck Attack.

Cet exposé s'intéressera également aux avancées plus récentes et notamment à toutes les attaques reposant sur les équations quadratiques construites à partir de la boite S de l'AES.

Group Key Agreement (GKA) protocols enable the participants to agree on a common secret value based on each one's contribution. They also provide efficient ways to change this secret value when the participants change. Thus they are well-suited to the security (key setup) needs of dynamic networks of "equals" as in Ad hoc networks. Many GKA protocols have been proposed till date. While some are too resource consuming for the constraint devices often present in Ad hoc networks, others lack a formal security analysis. In this talk, we propose a simple and efficient GKA protocol well suited for dynamic Ad hoc networks. We also prove it secure in the "standard model".

Dans cet exposé, nous présentons un nouveau générateur pseudoaléatoire, dénommé "Bit-Search Generator" (BSG). De même que le Self-Shrinking Generator, le BSG transforme une unique suite d'entrée suivant des règles simples. Nous montrons comment formaliser le fonctionnement du BSG, à l'aide notamment de permutations, qui permettent de déduire des propriétés intéressantes, en particulier dans le cas où l'entrée est donnée par un LFSR de période maximale. Nous donnons enfin une borne inférieure sur la période de la suite de sortie, ainsi que quelques résultats statistiques.

Travail commun avec Aline Gouget.

Nous étudions les propriétés cryptographiques des fonctions booléennes telles que la résilience, le critère de propagation (PC) et le degré algébrique. Nous introduisons également un algorithme permettant d'augmenter la robustesse des systèmes de chiffrement symétrique en renforçant la confusion de ces systèmes.

Nous présentons tout d'abord un état de l'art des bornes inférieures et supérieures sur le nombre de fonctions booléennes m-résilientes à n variables, que nous enrichissons de quelques compléments. Nous proposons ensuite une nouvelle borne supérieure sur le nombre de ces fonctions qui améliore significativement les bornes supérieures connues pour des ordres m compris entre n/2 et 3n/4. Puis, nous nous intéressons à la construction de fonctions booléennes équilibrées satisfaisant PC(l) et nous recherchons le plus haut degré algébrique atteint par ces fonctions. Nous étudions les fonctions de Maiorana-MacFarland dans ce contexte et construisons des fonctions booléennes équilibrées ayant un degré algébrique élevé et satisfaisant PC(l) pour des valeurs de l pour lesquelles de telles fonctions n'étaient pas connues auparavant. Nous étudions ensuite les fonctions booléennes symétriques. Nous montrons que celles qui vérifient PC(l) pour tout l fixé avec l>= 2 sont les fonctions symétriques quadratiques. Ce résultat, dont la preuve est très simple, implique en particulier comme corollaire immédiat un résultat connu~: les seules fonctions symétriques courbes sont les fonctions symétriques quadratiques. Enfin, nous proposons une nouvelle brique de confusion pour le chiffrement symétrique.