Accéder au contenu principal

Ynlqdwmnvqrbk - 1

Une des fonctions cryptographiques les plus élémentaires, c’est la fonction ROT13. L’idée, très simplement, consiste à remplacer chaque lettre du mot que vous souhaitez crypter par la treizième lettre suivante dans l’ordre alphabétique : a, première lettre, est remplacée par n, treize plus unième lettre ; b est remplacé par o etc. sachant, naturellement, qu’à partir de n, on revient au début de l’alphabet.

Par exemple, si nous souhaitons encoder le mot « test », on commence par déterminer le rang de chaque lettre dans l’alphabet (20, 5, 19, 20) auquel on rajoute 13 modulo 26 (soit 7, 18, 6, 7) et on remplace ce résultat par les lettres correspondantes de l’alphabet ; ce qui nous donne « grfg ».

Évidemment, cette rotation de treize places est un cas particulier. Jules César, qui fût un grand utilisateur de cette méthode pour chiffrer ses messages, était susceptible d’appliquer à peu près n’importe quelle rotation de 1 à 25 [1] de telle sorte que, en fonction de la clé choisie, « test » pouvait devenir « uftu » (rot1), « vguv » (rot2), « sdrs » (rot25) etc.

On peut très facilement reproduire l’algorithme de Caius Iulius — par exemple, voici ce que ça peut donner une fois codé sous R :

rot = function(x, n) {
   a <- strsplit(x, "")[[1]]
   v <- match(a, letters) + n
   b <- rep(NA, length(v))
   for(i in 1:length(v)) {
      r <- v[i] - floor(v[i]/26) * 26
      if(r == 0) r <- v[i]
      b[i] <- r
   }
   res <- paste(letters[b], collapse = "")
   return(res)
}

De telle sorte que :

> rot("test", 13)
[1] "grfg"

Et bien sûr :

> rot(rot("test", 13), 13)
[1] "test"

Nous avons donc un algorithme (la rotation alphabétique) et une clé (le facteur de rotation) : c’est la base de la cryptographie.

Seulement voilà : le chiffre de César est extrêmement facile à casser et ce, d’autant plus qu’un des principes fondamentaux de la cryptographie – le principe de Kerckhoffs — stipule que votre adversaire, celui qui va tenter de casser votre code, sait quel algorithme vous utilisez. En l’occurrence, il sait que vous utilisez le chiffre de César et il ne lui reste donc qu’à deviner avec quelle clé.

Une manière très simple et imparable de décoder votre message consiste tout bêtement à essayer toutes les clés possibles — de 1 à 25 — et à voir celle qui renvoie quelque chose qui a un sens. C’est ce que l’on appelle une attaque par la force brute.

Par exemple, si le message à décoder est « dpncpe » et si dico est une liste de tous les mots possibles [2], on peut écrire l’algorithme suivant (toujours sous R) :

msg <- "dpncpe"
res <- NULL
for(i in 1:25) {
   ans <- rot(msg, i)
   ix <- dico == ans
   if(any(ix)) {
      res <- c(res, dico[ix])
   }
}

Ce qui, en moins d’une seconde, nous donne :

> res
[1] "secret"

En l’occurrence, notre algorithme de décodage n’a aucun doute ; il n’y a qu’une seule possibilité : « dpncpe » signifie « secret » avec un facteur de rotation de 11. Code cassé.

Puisque votre adversaire connaît l’algorithme, le seul moyen de sécuriser vos messages c’est de faire en sorte qu’il ne puisse pas — du moins pas dans un délai raisonnable — deviner votre clé. En d’autres termes, vingt-cinq clés possibles, c’est beaucoup trop peu ; il va falloir faire mieux.

Un moyen de faire ça consiste à utiliser une clé de vingt-six chiffres de un à vingt-six qui indiquent à votre algorithme comment permuter chaque lettre de l’alphabet. Par exemple, la clé suivante (key) signifie qu’il faut remplacer a par la vingt-sixième lettre de l’alphabet (donc z), que b doit être remplacé par la neuvième lettre de l’alphabet (i), que c devient b etc.

key <- c(26, 9, 2, 20, 10, 17, 13, 6, 4, 21, 5, 25, 7, 18, 11, 12, 16, 8, 19, 23, 14, 1, 15, 22, 3, 24)

Ça n’a peut-être l’air de rien mais le nombre de permutations possibles de notre alphabet [3] s’élève tout de même à 26! — factorielle de 26 — soit environ 4.10^26 (4 suivi de 26 zéros) clés possibles. Pour la force brute, ça va commencer à être un peu plus sportif.

Voici à quoi ressemble l’algorithme :

algo = function(x, key, code) {
   a <- strsplit(x, "")[[1]]
   if(code) {
      b <- match(a, letters[key])
   } else {
      b <- key[match(a, letters)]
   }
   res <- paste(letters[b], collapse = "")
   return(res)
}

L’argument code est un booléen de telle sorte que si code = TRUE, l’algorithme encode x et si code = FALSE, il sait qu’il doit décoder x. Avec notre clé, on obtient :

> algo("secret", key = key, code = TRUE)
[1] "skynkd"

Et inversement :

> algo("skynkd", key = key, code = FALSE)
[1] "secret"

La force de ce système de cryptage réside non seulement dans le nombre de clé possibles (26!) mais aussi dans le fait que plusieurs combinaisons sont possibles. Pour bien voir ce point, raisonnons un peu : que sait l’adversaire de notre mot secret ?

D’abord, puisqu’il connait l’algorithme, il sait que le nombre de lettres n’a pas varié. Si dans « skynkd » il y en a six, c’est que dans le mot en clair il y en a six aussi. Ce simple fait réduit son champ de recherche à 3 148 mots (avec mon dictionnaire). Par ailleurs, il sait que toutes les lettres qui composent mon mot sont différentes les unes des autres à l'exception de la deuxième et la cinquième qui sont identiques. Ce qui nous laisse 146 possibilités. Par exemple, « toison » fonctionne — auquel cas s = t, k = o, y = i, n = s et d = n — mais « enfant » fonctionne également — s = e, k = n, y = f, n = a et d = t.

C’est-à-dire qu’à l’instar du chiffre de Vernam, si vous n’avez pas la bonne clé, il est théoriquement impossible de savoir avec certitude ce que signifie « skynkd ». Vous avez 146 possibilités — « toison », « enfant », « caviar », « fumeur », « mouton »… et bien-sûr « secret » — mais aucun moyen de savoir laquelle est la bonne.

Là où ça va se compliquer, c’est si vous rallongez votre message. Parce qu’en multipliant les caractères, vous allez donner une nouvelle arme à votre adversaire, une arme extrêmement puissante : les probabilités.

---
[1] Je prends quelques libertés avec la réalité historique : l’alphabet latin classique ne comportait que 23 lettres puisque, d’une part, les romains de l’époque impériale ne distinguaient ni le V du U ni le I du le J et que, d’autre part, le W n’existait pas. Notez, puisque nous y sommes, qu’à l’époque archaïque, le G, le X et le Y n’existaient pas non plus.
[2] En l’occurrence j’utilise un dictionnaire de 22 740 mots français trouvé sur internet.
[3] Et je vous passe les majuscules, les lettres accentuées et les signes de ponctuation…

Commentaires

  1. Le Diable probablement02/02/2014 21:31

    Pour aller plus loin, et pour ceux qui ont le temps, je recommande ceci :

    https://www.coursera.org/course/crypto

    Dispensé par une pointure internationale de la cryptographie, gratuit, etc. Profitez-en avant que ce soit interdit. :)

    RépondreSupprimer

Enregistrer un commentaire

Posts les plus consultés de ce blog

Brandolini’s law

Over the last few weeks, this picture has been circulating on the Internet. According to RationalWiki, that sentence must be attributed to Alberto Brandolini, an Italian independent software development consultant [1]. I’ve checked with Alberto and, unless someone else claims paternity of this absolutely brilliant statement, it seems that he actually is the original author. Here is what seems to be the very first appearance of what must, from now on, be known as the Brandolini’s law (or, as Alberto suggests, the Bullshit Asymmetry Principle):The bullshit asimmetry: the amount of energy needed to refute bullshit is an order of magnitude bigger than to produce it.— ziobrando (@ziobrando) 11 Janvier 2013To be sure, a number of people have made similar statements. Ironically, it seems that the “a lie can travel halfway around the world while the truth is still putting on its shoes” quote isn’t from Mark Twain but a slightly modified version of Charles Spurgeon’s “a lie will go round the w…

Les prix « avant l’euro »

(J’ai l’intention de compléter cet article au fur et à mesure. Si vous avez des prix à proposer (avec des sources crédibles), n’hésitez pas à le me suggérer dans les commentaires.)L’euro a été introduit en deux temps. La première étape a eu lieu le 1er janvier 1999 à minuit, quand le taux de change irrévocable des différentes monnaies nationales par rapport à l’euro a été fixé définitivement — soit, pour ce qui nous concerne, 1 euro = 6.55957 francs. La seconde étape, l’introduction des pièces et billets en euro, s’est étalée sur un mois et demi : du 1er janvier 2002 au 17 février 2002 ; date à laquelle les espèces en franc ont été privées du cours légal [1] — c’est-à-dire qu’il était interdit de les utiliser ou de les accepter en règlement d’une transaction.SalairesÀ compter du 1er juillet 2000, le SMIC horaire brut était fixé à 42.02 francs soit, pour avec une durée légale du travail de 39 heures par semaine (169 heures par mois), 7 101.38 francs bruts par mois. Le 1er juillet 2001,…

Comment j’ai déprogrammé l’obsolescence

C’est arrivé ce matin. Notre lave-vaisselle familial, que nous avions programmé pour tourner la nuit dernière, n’avait pas fonctionné. Mon épouse, étonnée par cette inhabituelle défaillance, a essayé de le relancer : rien à faire, le bestiau ne fonctionnait plus. Dépités, nous convînmes donc, ma dulcinée et moi-même, qu’il était temps de lui trouver un remplaçant. Cette fois ci, nous disions nous pas plus tard que ce matin, nous n’achèterons pas la première camelote venue à 300 euros : rendez-vous fût pris en début de soirée pour faire l’acquisition d’une bête de course qui, nous l’espérions, durerait vingt ans, comme celle de belle-maman.Dans les entrailles de la bêteMais la journée avançant, cette histoire ne sortait pas de ma tête. Le lave-vaisselle en question, nous l’avions tout de même acheté il y a à peine plus de trois ans : ce n’est pas Dieu possible que ce machin, même s’il ne nous avait objectivement pas coûté grand-chose, nous lâche aussi vite. Si ça se trouve, me disais-j…