Sans décoder ?

“Le Nombre imaginaire” ou les mathématiques comme terrain de jeu où l’imagination seule fixe les limites.

En ces temps joyeux de hacking présidentiel et de logiciels rançonneurs, il n’est pas sans intérêt de se demander ce que peuvent apporter les maths en termes de sécurité informatique. La réponse est : beaucoup. Mais au-delà de la complexité assez affolante des algorithmes en jeu, il existe quelques principes de bon sens peu connus et pourtant fort éclairants, qui si nous les appliquions tous pourraient nous aider à gagner un peu de confiance en ces systèmes dont nous dépendons tellement et dont nous ignorons trop.

Qu’il s’agisse du mot de passe de notre banque en ligne ou de documents professionnels confidentiels, nous avons tous besoin de protéger des secrets. Parfois ces secrets doivent être partagés avec des tiers de confiance, tout en étant protégés des regards indiscrets. C’est ici qu’entre en jeu le message codé, dont l’humanité a fait usage depuis qu’il y a des guerres, depuis qu’il y a des chefs.

En cryptographie, pour des raisons que j’ignore, les gentils s’appellent traditionnellement Alice et Bob, et le méchant est une méchante nommée Eve (je préfère ne pas trop réfléchir à la psyché du premier à avoir utilisé ces noms). Alice veut partager un secret avec Bob tout en le protégeant du regard indiscret d’Eve.

Il existe pour cela un grand nombre de protocoles modernes dont certains défrisent. La cryptographie quantique, par exemple, permet de s’assurer avec une certitude absolue que si Eve intercepte le message d’Alice, cette dernière ainsi que Bob le sauront immédiatement et pourront interrompre leur échange (ou, pourquoi pas, joyeusement le continuer pour désinformer Eve).

Toutefois cette technique, à base de photons intriquées circulant sur des fibres optiques, n’est pas à la portée de toutes les bourses ; nous allons devoir nous contenter de choses plus simples.

Alice peut encoder son message à l’aide d’une clé connue d’elle et de Bob seuls ; si Eve intercepte le message elle n’en sera guère avancée. Holà, me direz-vous : n’ai-je pas entendu dire que tout code peut être craqué en y mettant les moyens ? Depuis l’équipe d’Alan Turing cassant le code Enigma jusqu’aux indiscrétions actuelles de la NSA, il n’y a aucune méthode de codage réellement sûre ?

C‘est presque vrai mais pas exactement, comme on le sait depuis les travaux de Claude Shannon, père de la théorie de l’information. C’est justement là que les choses deviennent très intéressantes. Voici un message, par exemple, que ni vous ni personne ne pourrez jamais décoder, quels que soient les moyens que vous y mettiez :

I4|HB??0dgq>1asta<g »D\pb5t*7uERvH%is2uvLrKS3-

En revanche, et pour vous montrer que je ne triche pas, voici un autre message codé qui, lui, ne résisterait guère à un crypto-analyste averti :

nV85^;&F24@F*E=BB;QH>*O94G;B>.Ba]RhWYOLB`]-bV

Vous noterez au passage que ces deux messages codés ont la même longueur. La différence de qualité entre les deux ne saute peut-être pas aux yeux, mais elle est pourtant essentielle.

J’ai pourtant appliqué le même principe de cryptage, très simple, aux deux messages. Je me suis donné une clé – une suite de caractères. Je peux coder chaque caractère de mon message en clair avec un nombre calculé par mon ordinateur (entre 0 et 255, en l’occurrence, mais je ne me sers que des nombres entre 32 et 125 pour avoir un caractère imprimable, donc je décale tout vers le bas de 32 positions et je me retrouve avec un nombre entre 0 et 93 pour coder chaque caractère). J’ai ajouté au nombre qui correspond au premier caractère de mon message le nombre correspondant au premier caractère de ma clé, enlevé 93 si ça dépassait, puis retrouvé le caractère correspondant à ce nouveau nombre, que j’ai insérée dans mon message codé. J’ai opéré de même pour la deuxième lettre et ainsi de suite, en reprenant ma clé au début si elle était trop courte. Si ma clé n’avait qu’une lettre, on retrouverait le fameux code de Jules César, dans lequel chaque lettre est décalée d’un rang constant ; mais j’ai tout de même fait un peu mieux que ça.

Si Alice, ou Bob ou qui que ce soit connaissent ma clé, que je peux leur révéler séparément en secret, ils peuvent facilement retrouver le message d’origine. Mais qu’en est-il d’Eve ? Eh bien, elle ne devrait pas avoir trop de mal à déchiffrer mon deuxième message sans connaître la clé ; mais pour ce qui concerne le premier : même pas en rêve.

Comment Eve chercherait-elle à attaquer mon deuxième message codé ? Tout d’abord en faisant des hypothèses et en utilisant le contexte.  J’écris cette chronique en français, mon message a des chances d’être écrit en cette langue. Par ailleurs j’ai benoîtement révélé ma méthode de codage, ce qui est tout de même un vrai cadeau.

Eve sait comment attaquer un code de Jules César. Elle peut chercher si une lettre apparaît souvent ; il y a des chances que cette lettre code le E, lettre la plus fréquente en français. Si elle voit beaucoup de F dans le message codé, par exemple, elle peut essayer de voir ce que cela donne quand on déplace toutes les lettres d’un rang vers le bas : si elle obtient un message en clair, bingo ! Si ça ne marche pas, elle pourra supposer que mes F représentent des S, et déplacer les lettres en conséquence. De toute façon, dans le pire des cas, elle pourra tout simplement essayer les 93 décalages possibles et elle finira par tomber sur le bon.

Bon, il se trouve que j’ai fait un peu mieux que Jules César, donc Eve va devoir travailler un peu plus. Elle fera des hypothèses quant à la longueur de ma clé. Après avoir travaillé en vain sur l’hypothèse d’une clé de deux lettres, elle s’intéressera à la possibilité que ma clé ait trois caractères. Elle pourra ici encore procéder à une étude statistique et remarquer, par exemple, que si l’on considère la suite d’un caractère sur trois à partir de la première, la lettre B apparaît quatre fois sur quinze. Cela veut dire que, pour cette série, B code un caractère relativement fréquent en français. De même, quand on regarde un caractère sur trois à partir du troisième, on observe que le point-virgule apparaît trois fois. Eve pourra donc essayer différentes combinaisons de codes associant le B dans un cas, et le point-virgule dans l’autre, à l’une des lettres les plus fréquentes du français (« esantirulop ») ou à un signe de ponctuation fréquent (l’espace blanc en premier lieu). Lors de ces essais, en associant le B de la première série à l’espace blanc et le point-virgule de la deuxième à la lettre r, elle verra apparaître ceci (où je remplace une lettre non encore décodée par un point d’interrogation) :

L?op?ra?io? e?t ?ré?ue?po?r ?e ?70?17?à ?7h?0

Voilà qui commence à fleurer bon la grille de mots croisés à moitié résolue. Pas de syllabe ni de caractère bizarre, la première lettre en majuscule, une suite de chiffres qui évoquent une date de cette année, un « à » et un « h » qui pourraient bien spécifier une heure… Eve trouvera le message en clair, comme vous, en comblant les trous qui restent – n’oubliez pas que chaque point d’interrogation représente un caractère décalé d’une constante par rapport à celui qui lui correspond dans le message codé.

Parfait, bravo Eve. Mais pourquoi, alors, ne pourrait-elle pas appliquer les mêmes techniques à mon premier message? La clé en est sans doute plus longue, mais le principe reste le même. Il faudra peut-être tester un nombre très important de combinaisons, mais si Eve travaille à la NSA, cela ne devrait pas soulever de problème, si ?

Eh bien, si. Car il se trouve que pour mon premier message, j’ai utilisé une clé tirée au hasard, de la même longueur que le message. Chaque caractère a donc été codée en le décalant d’un nombre potentiellement différent de celui utilisé pour les tous les autres. Ceci a deux conséquences.

La première, c’est que le nombre de combinaisons à tester devient monstrueusement astronomique. C’est un nombre qui s’écrit avec 88 zéros. Si la puissance cumulée de tous les ordinateurs du monde pouvait en traiter mille milliards de milliards de milliards par seconde (nous n’en sommes pas encore là), et si on allouait ces ressources au problème pendant le prochain milliard d’années, on n’en effleurerait même pas la surface.

Très bien, me direz-vous : mais comment exclure qu’un jour apparaisse un super-super ordinateur quantique, qui utilise des copies de lui-même dans une infinité d’univers parallèles et leur fasse tester toutes les combinaisons possibles en parallèle ?  A change de revanche pour toutes les NSA de tous ces univers qui pourront demander le même service à la nôtre – entre services secrets on se donne des coups de main. Ils pourraient alors bien casser mon code ?

Eh bien, non, même pas dans ce cas. Pour la raison toute simple suivante : casser un code, c’est trouver le message en clair qui, crypté avec la clé que l’on détermine au passage, devient le message codé soumis à l’analyse. Encore faut-il qu’il n’y en ait qu’un !

Si la clé est courte, la probabilité que deux messages en clair différents (quoique de même longueur) puissent donner le même message codé en utilisant deux clés différentes est infinitésimale. C’est pourquoi, en décodant mon deuxième message, Eve n’a eu aucun doute sur le fait d’avoir retrouvé mon message en clair ainsi que la clé (« BOF », en l’occurrence) que j’avais utilisée pour le crypter.

En revanche, la clé aléatoire utilisée pour mon premier message codé a la longueur du message lui-même. Il existe alors un grand nombre de messages en clair de la même longueur qui donneraient exactement le même message codé, en utilisant une autre clé. En fait, donnez-moi n’importe quelle phrase de 45 signes de long, et je me fais fort de trouver facilement une clé qui le cryptera en produisant exactement le même message codé.

En énumérant les clés possibles, Eve va donc effectivement retrouver mon message en clair.  Mais elle va aussi en trouver bien d’autres ! Elle va, de fait, énumérer toutes les phrases de 45 signes existant en français. Par exemple :

L’opération est prévue pour le 110519 à 10h23

L’opération est prévue pour le 270917 à 17h30

L’opération a été annulée pour cause de grève

Chacun son univers et le continuum ira mieux !

Eve, laisse tomber. Tu n’y arriveras jamais !!

Si j’étais Eve, je suivrais ce dernier conseil. Mon message est définitivement indéchiffrable par Eve pour la bonne et simple raison qu’il a autant de probabilité que n’importe quel autre d’apparaître, compte tenu des informations dont Eve dispose. On dit que son entropie est maximale. La malheureuse Eve n’aura jamais le moyen de faire le tri, contrairement à Bob qui dispose de ma clé.

Si cette méthode est aussi inviolable que ça, comment se fait-il alors qu’elle ne soit pas utilisée partout ? C’est qu’il y a un hic : Pour le déchiffrer, Bob (et lui seul) doit connaître ma clé ; et pour que notre raisonnement ci-dessus soit valable cette clé ne peut servir qu’une fois, pour un seul message (sinon, on pourrait considérer deux messages utilisant la même clé comme un seul utilisant une clé plus courte que lui, donc vulnérable à l’analyse). Mais si, chaque fois que j’envoie un message à Bob, je dois lui fournir auparavant une clé secrète de la même longueur par un canal inviolable, alors pour autant qu’un tel canal existe j’aurais plus vite fait de l’utiliser pour remettre directement à Bob le message en clair au lieu de la clé !

Yannick Cras
Le nombre imaginaire