II. Présentation du système de McEliece

Chiffre de McEliece Sommaire I. Historique de la cryptographie 2 II. Présentation du système de McEliece 2
1. Posons le problème 2
2. Construction des paramètres du code 3
3. Le chiffrement 5
4. Le déchiffrement 5 III. Sûreté du système de McEliece 7
5. Une première attaque 7
6. Une méthode probabiliste 8
7. En conclusion 10 Annexes 11
1. Nombre moyen de tirages avant de trouver une matrice
inversible 11
2. Construction des corps finis 11
3. Trouver ( un élément primitif 13
4. Trouver P un polynôme irréductible 14
5. Calcul explicite dans un corps fini 16
6. Complexité de la méthode du pivot de Gauss 17
7. Détermination de k colonnes indépendantes 19
8. Primalité et factorisation 21
9. Quelques procédures écrites sous Maple 22
10. Démonstration des théorèmes 24
11. La loi française sur la cryptographie 26 Bibliographie 27 La cryptographie peut être décrite par l'image suivante : Bob veut
envoyer un message secret (en général « Bonjour ») à Alice mais pour cela
il doit utiliser un canal public. Seulement, Oscar espionne et écoute tous
les échanges qui se font par l'intermédiaire de ce canal. L'idée naturelle
est donc de chiffrer le message afin que seul Alice puisse le déchiffrer.
Formellement, on peut résumer tout cela par le schéma suivant : [pic] Les clés que nous voyons apparaître sur le schéma sont des paramètres
« personnels » que l'on prend en compte lors des étapes de chiffrement et
de déchiffrement et qui permettent d'apporter une diversité quasiment
infinie.
Nous allons dans ce mémoire présenter principalement un système de
chiffrement particulier proposé par McEliece. Nous expliquons dans un
premier temps son fonctionnement et nous testons par la suite (ce qui est
indispensable pour tout système cryptographique) la sécurité qu'il fournit.
Nous nous sommes efforcés par ailleurs d'étudier en Annexes les problèmes
pratiques que l'on rencontre avec McEliece et également de présenter
quelques procédures.
Signalons finalement que, dans un souci de clarté, nous avons adopté
le code suivant : les théorèmes sont annoncés par un trait bleu en marge et
sont démontrés en Annexes, les exemples sont annoncés par un trait rouge en
marge et les quelques démonstrations isolées sont annoncées par un trait
vert en marge. Historique de la cryptographie Les systèmes cryptographiques sont utilisés depuis très longtemps et
répondaient à l'origine à des besoins militaires. On sait par exemple que
Jules César utilisait le chiffre suivant : chaque lettre du message à
transmettre était remplacée par celle qui la suivait dans l'alphabet. Par
exemple, le mot BONJOUR était codé par CPOKPVS. L'utilisation de clés est
également apparue rapidement et le chiffrement de Jules César a alors fait
place au chiffrement de Vigenère. Toutefois tous ces systèmes utilisaient
une clé privée, c'est-à-dire que la clé de chiffrement et la clé de
déchiffrement étaient en réalité identiques. Ceci présente un défaut
important : avant de pouvoir discuter en toute sécurité, Bob et Alice
devaient s'être mis d'accord sur la clé commune, et cela en utilisant
forcément un canal public. Oscar pouvait alors intercepter facilement le
renseignement et puis déchiffrer tous les messages par la suite.
La grande révolution de la cryptographie moderne a été l'introduction
des systèmes à clé publique, par Diffie et Hellman, pour lesquels la clé de
chiffrement et la clé de déchiffrement ne sont pas identiques. Ainsi, Alice
peut informer Bob publiquement (en pratique par l'intermédiaire d'un
annuaire ou d'un serveur de clés) de la clé de chiffrement sans pour autant
compromettre la sécurité du chiffre. Bien sûr, il y a un revers à la
médaille : comme il existe forcément un lien entre les clés de chiffrement
et de déchiffrement, pour que ces méthodes puissent être utilisées, il doit
être calculatoirement difficile de reformer la clé de déchiffrement à
partir celle de chiffrement, alors que l'opération inverse doit être aisée.
De tels problèmes trouvent généralement leur solution dans les
mathématiques et notamment en arithmétique, par exemple pour RSA.
Cette nouvelle idée a apporté de nouvelles perspectives à la
cryptographie et très vite de nombreux systèmes cryptographiques à clé
publique sont nés. Cependant, très souvent dans la précipitation, les
systèmes créés se sont avérés peu efficaces soit parce que trop compliqués
à mettre en ?uvre, soit parce que n'offrant pas assez de sécurité. Le
système de McEliece est l'un d'entre eux et, comme nous allons le voir,
illustre bien cette période hésitante et révolutionnaire. Présentation du système de McEliece Dans tout ce qui suit F2 désigne l'ensemble {0,1} que l'on munit
d'une structure de corps.
Attention ! Pour écrire les messages qui seront représentés par des
vecteurs en ligne et non en colonne, nous allons transposer toutes les
matrices. Posons le problème Donnons-nous un entier n strictement positif et posons E=F2n. E est
alors un espace vectoriel sur F2 que l'on peut munir de la norme suivante
que l'on appelle le poids :
[pic]
La distance définie par cette norme est appelée distance de Hamming. Soit maintenant F un sous-espace vectoriel de E de dimension k. On
appelle distance minimale de F la quantité suivante : [pic] i) On a alors la propriété suivante :
Si x' est un élément de E, alors il existe au plus un couple
(x,e) vérifiant[pic]
S'il existe, le vecteur e est alors appelé le vecteur d'erreur.
Et réciproquement si pour tout x' élément de E, il existe au
plus un couple (x,e) vérifiant [pic] où t est un entier, alors la distance
minimale de F est strictement supérieure à (2t). Le problème est alors le suivant : Si on se donne x', existe-t-il un
couple solution et s'il existe, comment peut-on le trouver ?
Ce problème est en général difficile mais il se trouve que si F a une
structure particulière (que nous qualifierons de sympathique), alors on
peut trouver des algorithmes efficaces pour répondre à la question. C'est
sur cette remarque que repose le principe du système de McEliece.
Avant d'exposer celui-ci, nous allons remarquer que l'on peut trouver
une application linéaire de F2k dans E, qui réalise une bijection de F2k
dans F. Appelons alors G la matrice canonique de cette application. La
donnée de G entraîne bien évidemment celle de F (on dit que F est le code
engendré par G), c'est-à-dire au lieu de se donner un sous-espace vectoriel
de E de dimension k, on peut se donner une matrice de taille (k,n)
(Attention, on transpose !) à coefficients dans F2; c'est ce que nous
ferrons par la suite.
Exposons donc maintenant le principe du système de McEliece. Alice
choisit une matrice sympathique G de taille (k,n), une matrice inversible S
de taille (k,k) et une matrice de permutation P de taille (n,n), calcule
ensuite le produit G'=SGP. Elle rend ensuite publique la matrice G' et le
nombre maximal d'erreurs, que l'on notera t, qu'elle sait corriger avec un
algorithme simple.
Bob veut alors envoyer le message m à Alice. Pour cela, il calcule le
produit de m par G' auquel il ajoute un vecteur d'erreur de poids
convenable (inférieur ou égal au nombre publié). Il envoie alors à Alice le
vecteur calculé que l'on appellera x'. Mathématiquement cela s'écrit[pic].
Lorsque Alice reçoit x', elle calcule[pic]. Comme G est une matrice
sympathique, elle peut facilement éliminer le vecteur d'erreur et donc
retrouver [pic]. Connaissant S et G, elle retrouve ensuite le message
original m.
Oscar, quant à lui, est confronté au problème difficile puisqu'il ne
connaît que G' (qui n'est pas une matrice sympathique), ainsi il ne peut
pas a priori éliminer l'erreur et retrouver le message. Construction des paramètres du code Bien que pratiquement, la construction des paramètres doive
obligatoirement débuter par la construction de G, nous présentons ici un
ordre différent gradué par la difficulté que revêt chaque construction.
Notons également que nous utiliserons ici un code sympathique de la
classe BCH, alors que McEliece avait suggéré un code sympathique de la
classe de Goppa. Ceci ne change en rien l'état d'esprit du système de
chiffrement. Construction de la matrice S Il s'agit ici de construire une matrice de taille (k,k) inversible et
aléatoire. La première idée consiste à générer une première matrice
aléatoire. On regarde ensuite si elle est inversible (par la méthode du
pivot de Gauss qui est rapide lorsque les coefficients sont dans F2 - voir
Annexe 6). Si c'est le cas, on a trouvé une matrice S convenable, sinon on
réitère le procédé jusqu'à réussite. Toutefois, pour que cette méthode soit
raisonnable, il faut s'assurer que le nombre de matrices que l'on va
générer ne soit pas trop grand même pour des valeurs de k élevées.
On montre (voir Annexe 1) que le nombre moyen de matrices à générer
n'excède pas quatre. Ainsi cette méthode est satisfaisante.
La procédure 1 présentée en Annexes renvoie une matrice inversible et
son inverse. Construction de la matrice P Construire