Introduction

"Les sanglots longs des violons de l'automne, blessent mon coeur d'une langueur monotone". Durant la dernière guerre mondiale, à l'écoute de cette phrase, extraite d'un poème de Paul Verlaine, de nombreux réseaux de résistance surent que le débarquement était proche. Ce message chiffré est sûrement l'un des plus célèbres de l'histoire contemporaine française, et illustre parfaitement le principe de base de la cryptographie: modifier un message de façon à ce que son contenu soit inintelligible pour quiconque, sauf pour son destinataire.

La cryptographie est une science qui a occupé les esprits depuis la haute antiquité. Les méthodes de cryptage n'ont cessé d'évoluer de pair avec la puissance de calcul des ordinateurs. La cryptographie n'est plus un domaine réservé aux hommes d'Etat, aux ambassadeurs ou aux militaires, elle s'utilise aussi dans les milieux bancaires et industriels.

Avec l'avènement des réseaux informatiques internationaux, le problème de la sécurité, lors de l'échange de données, est plus que jamais au goût du jour. Il ne se passe pas un jour sans que les médias vantent les mérites des "autoroutes de l'information" et du réseau Internet. Le développement exponentiel du réseau nécessite la mise au point de protocoles de sécurité sûrs, aussi bien pour contrôler l'identité d'un individu, que pour valider, et certifier, une quelconque transaction entre deux personnes.

Une étude menée aux Etats-Unis, a montré que le réseau Internet a provoqué une augmentation de 400% de l'espionnage étranger, et une propagation, sans précédent, de virus et autres chevaux de Troie. En 1992, il y aurait eu un million d'effractions "virtuelles", sans compter les centaines de milliers de mots de passe et autres codes d'accès volés chaque année.

Les journaux relatent de plus en plus souvent les "exploits" de pirates informatiques ayant réussi à s'infiltrer sur des serveurs plus ou moins sensibles.

A une époque où l'information constitue une arme véritable, et la plus terrible de toutes, la divulgation de données bien choisies ou de fausses informations, peut provoquer des catastrophes pour un particulier comme pour une entreprise. Le remède s'appelle cryptographie.

Considérons le problème P suivant: Soient H une matrice k x n quelconque de rang k (k<= n) à coefficients dans F_q (le corps fini à q éléments), i un élément de F_q^k et soit S={z de F_qⁿ, Hz^t=i}. Trouver un élément s de S possédant le plus petit nombre de composantes non-nulles.

En règle générale, ce problème est "difficile" (cf. Chap. ii). Si H ne possède pas de structures particulières, la seule solution consiste à parcourir les q^n-k éléments de l'ensemble S. Une telle recherche s'avère rapidement impraticable. A titre d'exemple, pour q=2, si on suppose que n=2k, alors il devient impossible de résoudre ce problème dès que k>50.

La théorie des codes permet de construire facilement des instances particulières du problème P, dont une solution peut être trouvée en temps polynomial (ceci sans poser de conditions sur la taille de la matrice H).

L a théorie de la complexité fournit une méthode pour analyser la complexité de calcul de différents algorithmes. Dans le domaine de la cryptographie, elle permet de déterminer le niveau de sécurité d'un protocole. La théorie de l'information nous apprend que tous les algorithmes cryptographiques peuvent être cassés (à une exception près). La théorie de la complexité nous indique si la seule solution pour assister au succès d'une attaque est la cryogénisation!

Les schémas d'identification

Dans de nombreuses applications (courrier électronique, échanges bancaires, ...), il peut s'avérer nécessaire que l'expéditeur s'assure de l'identité du destinataire avant de commencer une transaction. C'est le problème de l'identification.

Dans la terminologie usuelle, les deux intervenants sont respectivement appelés le vérifieur et le prouveur et sont représentés par Bob et Alice (ou Victor et Peggy).

Un schéma d'identification est un protocole cryptographique permettant à Alice de prouver ,en temps polynomial, son identité à Bob, sans que ce dernier puisse se faire passer pour Alice auprès d'une tierce personne.

De nos jours, les supports plastifiés,au format carte de crédit, sont de plus en plus employés comme moyen d'identification pour distinguer clients, membres ou adhérents. C'est pourquoi, il est supposé, lors de l'élaboration d'un schéma d'identification, que le prouveur dispose d'une faible puissance de calcul et d'une quantité limitée de mémoire. Ces contraintes ne s'appliquent pas au vérifieur.

Il est important de noter ici que l'hypothèse faite sur le prouveur est différente de celle utilisée dans la théorie générale développée par S. Goldwasser, S. Micali et C. Rackoff (cf. paragraphe suivant). En effet, ces derniers supposent que le prouveur possède une puissance illimitée. Or, dans le cadre d'une application pratique, le prouveur est souvent associé à un support mobile de type cartes à puces, sa puissance est donc limitée.

De même, en ce qui concerne le vérifieur, dans certains cas (la télévision cryptée par exemple), sa puissance de calcul est restreinte. Nous ne nous sommes pas placés dans cette optique, cependant on peut facilement montrer que pour les schémas que nous proposons, la complexité des calculs effectués est en O (k²)), k étant la dimension de la matrice utilisée.

Le problème de base concernant les méthodes d'identification actuelles (cartes à puces, mots de passe, numéros d'identification, ...) provient du fait que le prouveur établit son identité en révélant un secret s qu'il détient (pensez aux quatre chiffres de votre carte bleue !). Ainsi, il suffit qu'un adversaire, coopérant avec un vérifieur malhonnête, récupère cette quantité pour se faire passer pour Alice auprès d'un vérifieur honnête.

Performance des Schémas

D ans un cadre pratique, le prouveur peut être assimilé à un support portable de type carte à puces. Sa puissance de calcul, et sa capacité de stockage sont donc limitées. De ce fait, nous nous sommes particulièrement intéressés à la valeur de ces deux quantités. De plus, un dernier paramètre, non négligeable, est le nombre de bits échangés lors d'un processus d'identification; c'est le débit de transaction du schéma. En particulier, plus ce débit est important, et plus le coût de la communication entre le prouveur et le vérifieur sera important.

Les deux premières contraintes, mentionnées ci-dessus, ne s'appliquent pas au vérifieur qui, dans certains cas, peut être assimilé à un serveur possédant d'importants moyens de calculs.

Pour tous les schémas qui ont été proposés, les calculs s'effectuent sur le corps F₂ et n'utilisent, uniquement, que les opérateurs logiques xor et and. Si cela parait évident pour le schéma G-SD, il en est de même pour les schémas MR G-SD, CR G-SD et T-SD, puisque, d'après les propositions 5.5.1 et 5.2.5, du chapitre i, la multiplication de deux éléments du corps F₂, consiste en une série d'additions binaires.

Le schéma d'identification de S. Harari a été le premier protocole dont la sécurité dépendait de la difficulté de résolution du problème SD. Trois attaques possibles sont proposées. Les deux premières montrent, comment un fraudeur peut, dans 50% des cas, se faire passer pour Alice auprès de Bob. De nouveaux paramètres sont proposés afin de rétablir la sécurité du schéma. Cette modification augmente, d'un facteur 20, le débit de transaction et la complexité de calcul du schéma initial. Il était alors intéressant d'étudier s'il était possible d'utiliser une matrice de taille équivalente à celle des autres schémas SD, afin de diminuer la valeur de ces deux quantités.

La troisième attaque montre que le schéma n'est plus fiable si on réduit la taille de la matrice publique. Pour les valeurs initiales, suggérées par l'auteur, cette attaque permet, dans certains cas, à un vérifieur malhonnête d'obtenir, lors des transactions avec le prouveur, le secret de ce dernier. De plus, il apparaÎt clairement qu'une diminution de la taille de la matrice utilisée, augmente l'efficacité de cette attaque.

L' algorithme de Mc Eliece [McEl] proposé en 1978 est l'un des premiers systèmes cryptographiques à clé publique. Sa sécurité repose sur la difficulté du décodage d'un code linéaire binaire quelconque qui est conjecturé être un problème de complexité exponentielle. De nos jours aucune des attaques proposées ([CaCh1], [CaCh2], [LeBr], [Leo], [Ste1]) contre ce système n'est efficace pour les paramètres suggérés par Mc Eliece. L'idée principale de l'algorithme est d'utiliser une matrice génératrice d'un code de Goppa et de la "masquer" afin de la rendre indistinguable d'une matrice génératrice d'un code quelconque.

Le but initial de notre travail était de réaliser une étude sur les propriétés des codes de Goppa afin de découvrir des structures "cachées" dans le système Mc Eliece. En effet, les seules attaques existantes à ce jour sont valables pour n'importe quel type de code et ne tiennent donc pas compte de la structure du code utilisé.

Au cours de cette étude nous avons mis à jour une sous classe des codes de Goppa pour laquelle de nouvelles bornes sur la dimension et la distance minimale sont obtenues. Nous commencerons dans un premier temps par rappeler les résultats de base concernant les codes de Goppa classiques, certaines démonstrations ne sont pas données. Le lecteur pourra consulter [MaSl, ch. 12].

Conclusion

Des nouveaux schémas d'identification, dépendant de la difficulté de résolution du problème SD ont été proposés. L'un d'entre eux est,à ce jour, le plus performant des schémas SD. Plusieurs alternatives ont été suggérées afin d'améliorer ses paramètres. Pour cela, nous avons travaillé sur des sous-instances du problème général considéré.

Si de nouvelles cryptanalyses ne sont pas élaborées, pour ces instances particulières, alors ces schémas constituent une bonne alternative aux schémas classiques, dépendant d'un problème issue de la théorie des nombres.

Chacun d'entre eux possède ses avantages et ses inconvénients selon que l'on privilégie deux paramètres parmi les trois suivants: taille de la ROM, complexité de calcul, débit de transaction.

Tous les schémas basés sur le problème SD utilisent une fonction de hachage et un générateur de permutation aléatoire. Une amélioration consisterait à élaborer un nouveau schéma, n'utilisant pas ces deux objets. Ceci permettrait, entre autre, de mettre au point des systèmes interactifs de preuve, à divulgation nulle, ne dépendant pas du modèle de l'oracle aléatoire.

En ce qui concerne les codes de Goppa, de nombreuses questions sont encore sans réponse. Notamment, est-il possible de complètement caractériser les codes à poids pair ? Peut-on prouver que les bornes que nous avons proposées sont toujours atteintes lorsque g(z)=Tr_Fp^2s:Fp^s (z). Pour certains polynômes a(z) et b(z), est-il possible d'améliorer les bornes proposées ? En ce qui concerne la distance minimale, les bornes obtenues ne sont pas assez fines. Peut-on les améliorer ? Les résultats obtenus sur l'intersection de $\Gamma_{2,2} (1,z)$ et $\Gamma_{2,2} (1,z)^{\bot}$ doivent se généraliser à tout corps de caractéristique p quelconque. L'utilisation de certaines propriétés des codes de Reed et Muller doit permettre une nouvelle étude de ces deux codes.

Annexe A

. Quelques trinômes irréductibles sur F₂

Annexe B