La cryptographie

À quoi ça sert ?

Qui ne s'est jamais amusé à envoyer des messages secrets ? Ou à essayer de déchiffrer ceux qu'on trouve dans les pages de jeux de certains magazines ? La cryptographie, ça sert exactement à ça : écrire des messages de manière à ce que seul leur légitime destinataire puisse les lire.

Mais qu'est-ce qu'un message ? Pour pouvoir travailler, il faut savoir de quoi on parle. On peut définir un message ainsi : suite finie d'éléments pris dans un ensemble fini ayant une signification. Ici, notre «ensemble fini» sera par exemple l'ensemble des mots du dictionnaire, ou plus simplement l'ensemble des caractères d'imprimerie. Nous pouvons donc commencer.

La première idée

Le code de Jules César

Pour envoyer des ordres confidentiels à ses généraux, Jules César utilisait une méthode très simple : il remplaçait dans son texte tous les A par des D, les B par des E, les C par des F, les D par des G, ... les V par des Y, les W par des Z, les X par des A, les Y par des B et les Z par des C, c'est-à dire qu'il décalait l'alphabet de trois lettres.

C'est la méthode la plus simple : remplacer chaque lettre par une autre, ou un chiffre, ou un dessin, de manière à ce que deux lettres s'écrivend différemment.

Les défauts de cette méthode

Mais cette méthode a de nombreux défauts : si un des généraux avait trahi Jules César, il aurait eu à trouver un nouveau code. Ça n'aurait pas été insurmontable, il y en a 620448401733239439360000 du même type, mais il faudrait envoyer un courier de confiance à chaque autre général.

Mais le gros défaut de cette méthode est son manque de fiabilité : dès que le message dépasse deux lignes, on peut percer ce type de code sans trop de difficulté, par des raisonnements du style : « « ws » est un mot qui revient souvent, c'est donc probablement « le » ou « la »... ».

Comment y remédier

La solution est de compliquer le code. Par exemple en ne travaillant plus sur les lettres seulement, mais aussi la ponctuation et les espaces... mais ça ne résiste pas bien longtemps non plus. Ou en travaillant avec les mots entiers. Mais alors le code ne tient plus dans la poche ou dans la tête. Une astuce est d'associer non plus un mais plusieurs symboles à chaque lettre (ou signe), et de les utiliser indifféremment l'un de l'autre. On peut aussi utiliser une correspondance pour les lettres paires, et une autre pour les impaires.

On peut multiplier les astuces, il n'en demeure pas moins qu'il faut une astuce par correspondant, faute de quoi une trahison est très ennuyeuse.

La notion de clef

Le carré Vignère

Examinons cette table :

Soient les mots ORDINATEUR et DECHIFFRER. Regardons l'intersection lettre par lettre dans le tableau : RVFPVFYVYI. Avec ORDINATEUR et RVFPVFYVYI, on peut retrouver DECHIFFRER. Avec DECHIFFRER et RVFPVFYVYI, on peut retrouver ORDINATEUR. Si maintenant nous convenons d'utiliser le mot ORDINATEUR, nous pouvons nous transmettre un message en toute simplicité à condition qu'il ne dépasse pas 10 lettres. Mais nous pouvons utiliser le mot ORDINATEURORDINATEURORDI pour coder un message de 24 lettres. ORDINATEUR s'appelle dans ce cas une clef : c'est lui qui nous ouvre la porte du message.

Cette méthode est-elle tout à fait sûre ? Pas en l'état : il suffit d'essayer tous les mots du dictionnaire, et on finit par trouver. Mais rien n'oblige à prendre un mot du dictionnaire : il vaut mieux prendre des lettres au hasard. Dans ce cas, si la clef est longue, il devient difficile de trouver : tester toutes les clefs de 10 lettres, en en essayant un milliard par seconde prendrait 40 heures, et avec 1 lettres, il faudrait plus de 50 000 ans. Mais ça ne veut rien dire, il existe peut-être une méthode efficace. Non! Pour une simple raison : quoi que vous vouliez me faire dire, il existe une clef qui me le fasse dire (à condition que la taille des mots concorde, évidemment). Pour celà, il faut que la clef soit aussi longue que le message. Donc si vous pouvez échanger avec quelqu'un un CD-ROM plein de lettres prises au hasard, vous pourriez échanger 2 pages chacun par jour pendant 68 ans, et ce de manière totalement secrète, à condition de garder le CD précieusement.

Généralisons

Globalement, une clef, c'est un petit peu d'information qui contient la description d'une méthode de codage. Par exemple, la clef du code de César était 3. Ceci ne veut rien dire : une clef correspond à une méthode - on dit un algorithme : on a une fonction coder(clef,texte) telle que pour toute clef, la fonction texte -> coder(clef,texte) soit injective (f est injective si x<>y => f(x)<>f(y)). Il faut en outre que l'inverse soit facile à calculer, et que sans la clef ce soit impossible.

On voit bien que ce sont des mathématiques. Alors soyons efficaces, parlons de nombres : A=0, B=1, ..., ou bien utilisons le code ASCII : ' '=32, 'A'=65, 'a'=97... peu importe, ce qui compte, c'est que notre message n'est plus qu'une suite de nombres entre 0 et n-1.

Alors on peut immaginer de nombreuses méthode. Donnons-en quelques unes : (notons qu'on peut saucissonner le message en paquets de taille constante, quitte à lui ajouter quelques espaces à la fin)

• clef=(k0...ki), texte=(t0...ti), coder(clef,texte)=(t0+k0...ti+ki) (c'est à peu de choses près le carré Vignère.
• coder(clef,texte)=le membre de droite d'équations linéaires dont les coefficients sont la clef.
• ...

Voyons les deux premiers : ils ont le même défaut : le résultat est plus gros que la clef. Dans le premier cas, on peut ruser : si la clef est aussi une suite de nombres entre 1 et n-1, quand le résultat dépasse n, on enlève n. Quand on fait la soustraction, si on trouve un résultat négatif, on ajoute n.

Le pire, c'est que ça marche aussi dans le second cas : si on décrète n=0, c'est à dire qu'on enlève ou ajoute n tant que le résultat n'est pas entre 0 et n-1, alors l'addition, la soustraction, la multiplication et la division par un nombre n'ayant pas de diviseur commun avec n marchent comme d'habitude.

Les codes à clef publique

L'idée de base

Le problème, avec les méthode que j'ai énoncées, c'est qu'il faut pouvoir se passer la clef en toute confidentialité : il faut donc une clef par couple de correspondants, et chacune exige une communication sécurisée. Ce qui serait vraiment bien, c'est que tout le monde puisse m'écrire, mais que je sois le seul à pouvoir lire.

Ceci est impossible, pour la simple raison qu'il suffit d'essayer de m'écrire tous les messages possibles, et de voir lequel sera transmis de la même façon. Mais essayer tous les messages prend du temps. Beaucoup de temps, plusieurs siècles. Il faut donc une méthode plus efficace. A priori, la méthode est ouverte : pas question de faire tourner l'algorithme en boîte noire, un bon hacker peut sans problème analyser cette boîte.

Donc étant donné un algorithme dont on sait qu'il possède un algorithme inverse simple (celui que j'utilise), n'est-il pas toujours facile de trouver cet inverse simplement ? Réponse : non. En tout cas, pour ce que je vais évoquer, personne ne connaît de méthode rapide, pas plus qu'on n'est capable de démontrer qu'il n'y en a pas. Si des vocations se créent...

La méthode des empilements

Etant donnés n nombres (entiers, toujours), et la somme d'une partie de ces nombres, comment retrouver lesquels ? Dans certains cas, c'est facile. par exemple, si chaque nombre est plus grand que la somme de ceux qui sont plus petits (on met le plus grand possible, et on recommence), ou si chaque nombre est divisible par un nombre premier p un nombre distinct de fois (on écrit en base p). Mais en général, c'est dur.

La technique de cryptage est donc la suivante : choisir une suite (an) de nombres permettant de résoudre le problème simplement, choisir une fonction f ayant certaines propriétés :

• f a une inverse
• f est «compliquée»
• pour tout x et y f(x+y)=f
(x)+f(y)

Alors il faut publier la famille (f(an)). Celui qui veut envoyer un message le code en binaire, le découpe en paquets de n chiffres, et pour chaque paquet, fait la somme des nombres corespondant à des 1. Il envoie les sommes.

À l'arrivée, il faut appliquer l'inverse de f au message, puis résoudre simplement le problème pour comprendre le message.

Il faut trouver une fonction f qui convient. On remarque que k=1+1+...+1, donc que f(k)=f(1)+...+f(1)=k.f(1). Donc f sera toujours trop simple. Dommage. Mais si on applique le truc de tout-à-l'heure, c'est-à-dire décrèter p=0 pour un certain p. On a vu que l'addition et la multiplication marchent bien, et dans ce cas, si on garde p secret, f n'est plus simple du tout. Attention : il faut bien choisir p. Il ne doit rien avoir en commun avec les (an), et ne doit pas interférer avec le truc de résolution. Il suffit donc de prendre un nombre premier plus grand que la somme de tous les (an).

Cette méthode a des défauts : elle n'est pas très fiable, et la clef est énorme.

Les méthodes utilisées en pratique

En pratique, les méthodes employées reposent sur le même principe de base, mais aves des méthodes reposant sur des bases un peu plus compliquées. Je ne suis pas spécialiste de cryptographie, ni introduit dans les hautes sphères des services secrets mondiaux, mais je sais néanmoins qu'une des méthodes les plus employées repose sur l'algorithme dit «RSA» (pour Rivest, Shamir, Adleman). Vous trouverez ici un texte, qui devrait être accessible à un élève de fin de terminale S qui s'en donne la peine, qui en explique les principe et démontre le fonctionnement (mais pas la solidité, qui reste encore conjecturée)  : ccm_rsa.ps.