Python et la cryptographie
(et un peu de piratage aussi)

Un sytème mécanique de chiffrement. Crédit: Adam Foster, Flickr.

Un système mécanique de chiffrement. Crédit: Adam Foster, Flickr.

Ce tutoriel est tiré d’une présentation que j’ai faite pour un meetup de Hacks/Hackers Montréal. Devenez membre si vous habitez dans la région!

Depuis la nuit des temps, que ce soit en temps de guerre, lors de tractations politiques ou dans le monde des affaires, des hommes et des femmes ont tenté de garder pour eux certaines informations ayant le potentiel de leur donner un avantage.

Plus récemment, les révélations d’Edward Snowden ont aussi rappelé l’importance pour tous de protéger ses données personnelles.

Dans cet article, je vous explique ce qu’est la cryptographie, à partir d’exemples concrets. Nous allons recréer ensemble les algorithmes qui permettaient à Jules César, aux nobles de la Renaissance ou encore aux soldats de la Guerre de Sécession de protéger leurs secrets.

Mais puisque qu’aucun système n’est infaillible (et parce que c’est toujours amusant de déjouer les règles établies), je vais aussi vous montrer comment « pirater » ces anciens algorithmes, que plus personne n’utilise j’espère!

Pour rédiger cet article, je me suis principalement inspiré de l’excellent Hacking Secret Ciphers with Python, écrit par Al Sweigart. Un incontournable de 442 pages, que j’ai dévoré et que je conseille fortement. Si vous n’êtes pas très à l’aise avec Python, je vous suggère d’aller jeter un coup d’oeil à mon tutoriel Vos premiers pas en programmation!

I Décoder les secrets de Jules César

Jules César au musée du Louvre. Crédit: Nicolas Coustou, Wikimedia Commons.

Jules César au musée du Louvre. Crédit: Nicolas Coustou, Wikimedia Commons.

La cryptographie ne date pas d’hier. Jules César, le célèbre empereur romain, rendait illisibles ses messages au cas où ils tomberaient entre les mains de ses ennemis.  Sa technique était très simple: il utilisait le chiffrement par décalage. Et, vous allez le voir, cette technique est particulièrement facile à pirater.

Imaginons que ce bon vieux Jules souhaite envoyer le message suivant à un de ses généraux:

  • « Ce soir, on attaque les Gaulois! »

Jules César, qui apparement aimait utiliser le chiffre 3 comme clé de chiffrement, procède alors comme suit:

  • La première lettre du message est « C ». Il s’agit de la troisième lettre de l’alphabet. 3 + 3 = 6. « F » est la sixième lettre de l’alphabet. « C » est donc remplacé par « F ».
  • La deuxième lettre du message est « E ». Il s’agit de la cinquième lettre de l’alphabet. 5 + 3 = 8. « H » est la huitième lettre de l’alphabet. « E » est donc remplacé par « H ».
  • Et ainsi de suite…

Au final, le message crypté donne:

  • « FH VRLU, RQ DWWDTXH OHV JDXORLV! »

Par la suite, le général, une fois le message reçu, procède à l’inverse pour le déchiffrer.

  • « F » est la sixième lettre de l’alphabet. 6 – 3 = 3. « F » remplace donc « C ».
  • « H » est la huitième lettre de l’alphabet. 8 – 3 = 5. « H » remplace donc « E ».
  • Etc…

Rien de bien compliqué donc!

Crypter et décrypter à la Jules

Voici comment crypter les messages à la Jules César en Python. Mes commentaires sont en gris, à partir de la ligne 4.

Si vous lancez le script ci-dessus dans votre terminal, vous verrez donc ceci.

ceasar_crypt

Pour décrypter les messages, le code est essentiellement le même, sauf qu’on remplace le message original par le message crypté. Aussi, on soustraie la clé au lieu de l’additionner.

Une fois lancé dans votre terminal, vous devriez voir votre message en clair!

caesar_decrypt

Pirater Jules!

Jules César se disait sans doute qu’à moins de connaître sa méthode, personne ne pourrait déchiffrer ses messages. Et le taux d’analphabétisme du Ier siècle av. JC devait sans doute jouer en sa faveur.

Le problème, c’est que sa méthode simpliste peut facilement être découverte (avec par exemple une analyse fréquentielle des caractères ou un gros sac d’or à l’intention d’un général véreux). Et une fois la méthode trouvée, son dernier rempart était sa clé.

Or, dans un alphabet de 26 lettres, Jules César n’avait que 26 choix de décalage. C’est bien peu! Et de nos jours, tester ces 26 possibilités est un jeu d’enfant avec un script en Python!

Pour ce faire, la stratégie est la suivante:

  • Tester toutes les possibilités de clés.
  • Vérifier si des mots intelligibles se trouvent dans le message décrypté.

Si une des clés produit des mots français, alors on saura qu’il s’agit de la clé secrète!

Mais comment distingue-t-on le français du charabia, me direz-vous? Avec un dictionnaire bien sûr! Rendez-vous à l’adresse suivante et téléchargez la liste de mots gracieusement rendue publique par le chercheur Christophe Pallier. Nous allons demander à notre notre ordinateur de comparer le résultat de chaque déchiffrage avec les 300 000+ mots de cette liste.

Voici à quoi un tel script ressemblerait. Notez que dans notre cas, nous avons non pas 26 lettres, mais 38, puisque j’ai ajouté les caractères spéciaux.

Une fois le script lancé, votre ordinateur va tester en quelques secondes l’ensemble des possibilités, en plus de comparer les résultats avec plus de 300 000 mots. Pas mal, non? Au final, vous devriez avoir un résultat similaire à ça:

caesar_hack

Maintenant que la clé secrète est entre vos mains, vous pouvez décrypter le message secret de Jules César et courir prévenir Vercingétorix! 🙂

 

II Les Spartiates, ces petits cachotiers

Un soldat spartiate. Crédit: Benutzer Ticinese, Wikimédia.

Un soldat spartiate. Crédit: Benutzer Ticinese, Wikimédia.

Vous m’excuserez de ne pas suivre un ordre chronologique, mais j’ai choisis de partir du plus simple vers le plus compliqué. Et bien que les Spartiates aient vécu avant Jules César, ils avaient mis au point un système de cryptographie qui s’avèrera bien plus efficace que le sien: le chiffrement par transposition.

Les Grecs utilisaient une scytale (voir image ci-dessous) pour coder leurs messages. La technique était aussi simple qu’astucieuse. L’expéditeur enroulait une lanière de cuir autour d’un bâton et écrivait son message dans le sens de la longueur. Une fois la lanière déroulée, le message devenait illisible puisque les lettres se retrouvaient alors dans le désordre.

La lanière était alors transmise au destinataire, qui l’enroulait à son tour autour d’un bâton avec exactement la même circonférence que celle de l’expéditeur. Et les lettres alors parfaitement alignées révélaient leur message!

Plutôt malin non?

Une scytale. Crédit: Wikimédia.

Une scytale. Crédit: Wikimédia.

En gros, cette méthode revient à utiliser une clé X et revenir à la ligne à chaque X nombre de caractères. Par exemple, avec le message « Il fait beau aujourd’hui, je vais aller marcher » et une clé de 8, on peut représenter le tout dans Excel comme suit:

transposition_excel

Puisque nous avons choisi la clé 8, nous avons 8 colonnes et notre message crypté serait les lettres de la colonne 1 (« IBOJAR »), suivies des lettres de la colonne 2 (« LEUELC »), etc…

Au final, notre message crypté serait « IBOJARLEUELC AR LHFUDVEEA  ARRIAHI TUUSM JI A ». Totalement incompréhensible!

Cette technique possède plusieurs avantages. Tout d’abord, une analyse fréquentielle des lettres ne fonctionnerait pas pour décrypter les messages des Spartiates. Certaines lettres apparaissent plus souvent que d’autres en français, ce qui permet de décoder certains messages cryptés, mais ce n’est pas le cas ici. Puisque les lettres ne sont pas remplacées par un autre caractère, elles auront toutes une fréquence normale.

Et, comparé à l’algorithme de Jules César, il y a beaucoup plus de possibilités de clés! Techniquement, plus un message est long, plus il y a de clés possibles!

Par exemple, imaginons que Léonidas, roi des Spartes et opposant héroïque aux Perses lors de la bataille des Thermopyles, souhaite envoyer le message le suivant au chef de sa cité:

  • « Nous sommes encerclés. À trois cents hoplites contre plusieurs milliers, nous ne tiendrons plus longtemps. J’ai parlé aux hommes. Pas question de se rendre. Nous nous batterons jusqu’à la mort. À défaut de pouvoir les arrêter, nous pouvons au moins les ralentir et vous donner le temps de fortifier la cité. Nous nous retrouverons dans l’autre monde. Adieu! »

Ce message contient 357 caractères. Il y a donc 357/2 => 178 clés possibles! César peut aller se rhabiller!

Malheureusement pour les Spartiates, un bon petit script en Python peut facilement pirater leurs messages secrets!

Crypter et décrypter comme un Spartiate

Commençons par le script en Python pour chiffrer vos messages à la Léonidas.

Une fois lancé, ce script devrait vous donner ça:

crypted_transposition

Et voici le script pour le décrypter. La grande différence, c’est que l’on inverse les lignes et les colonnes.

Et voilà le résultat!

decrypt_transpo

Hacker les spartiates!

La technique de chiffrement de Jules César étant très simple, l’empereur se devait de la garder secrète pour protéger ses secrets. Pour les Spartiates, c’était différent et bien plus sécuritaire. Même si les ennemis connaissaient la technique de cryptage, tant qu’ils n’avaient la bonne taille de bâton (qui équivaut à la clé), décrypter le message était ardu.

À l’époque de la Grèce Antique, tester manuellement 178 possibilités de clés aurait pris un temps fou. Mais aujourd’hui, ça ne prend que quelque secondes à un ordinateur et c’est pourquoi j’espère que plus personne n’utilise cet algorithme aujourd’hui!

En somme, le concept est simple. Nous allons reprendre le script de décryptage, sauf que nous allons tester toutes les clés possibles cette fois-ci, tout en vérifiant si des mots en français ont été déchiffrés grâce à notre dictionnaire, comme nous l’avions fait pour l’algorithme de Jules César.

Et voilà le résultat une fois que le script a fini son oeuvre!

hack_transposi

Ah! Imaginez à quel point vous pourriez changer le cours de l’Histoire s’il était possible de retourner dans le temps avec un ordinateur portable bien rechargé! Tous les secrets militaires des Grecs seraient dans votre poche!

 

III Le chiffre indéchiffrable
de Blaise de Vigenère

Blaise de Vigenère (1523-1596), diplomate français. Crédit: Wikimédia.

Blaise de Vigenère (1523-1596), diplomate français. Crédit: Wikimédia.

À la fin du Moyen-Âge, en France, le diplomate français Blaise de Vigenère (qui avait de toute évidence un intérêt pour les mathématiques) met au point un algorithme que personne ne réussira à briser pendant plus de 250 ans!

De Vigenère a présenté sa méthode (probablement fortement inspirée du travail du cryptanalyste italien Giovan Battista Bellaso) devant la cour d’Henri III en 1586. L’algorithme se révèle particulièrement coriace pour les scientifiques et savants de l’époque qui tentent de le déchiffrer, ce qui lui vaudra le surnom de chiffre indéchiffrable.

Ce n’est finalement qu’en 1854 qu’un premier mathématicien, le londonien Charles Babbage, en viendra à bout. En parallèle, l’officier prussien à la retraite Friedrich Wilhelm Kasiski réussit aussi ce tour de force et publie une méthode complète pour rendre le système caduque en 1863.

Mais le système, même une fois compromis, a continué à être utilisé, notamment par les soldats de la Confédération, lors de la guerre de Sécession (1861-1865).

Les soldats de la Confédération utilisaient ce genre de disque pour crypter leurs messages à l'aide de la technique de Vigenère. Crédit: Wikimédia.

Les soldats de la Confédération utilisaient ce genre de disque pour crypter leurs messages à l’aide de la technique de Vigenère. Crédit: Wikimédia.

La méthode de Vigenère consistait à choisir une clé et à s’en servir pour crypter le message lui-même. Par exemple, imaginons la situation suivante:

  • Message: Le chiffre indéchiffrable
  • Clé: python

Voici comment nous nous y prendrions pour crypter notre message dans Excel. Les deux premières lignes représentent notre alphabet avec le chiffre correspondant à chaque lettre (en Python, on commence toujours nos listes par 0).

Nous avons ensuite la ligne de notre message, avec le numéro de chaque lettre, puis notre clé, qui se répète pour couvrir tout le message, et avec encore une fois le chiffre correspondant à chaque lettre.

Pour crypter notre message, il suffit de faire la somme des chiffres correspondant à la lettre en clair et à la lettre de notre clé. Par exemple, la première lettre du message est « L », qui est associé à 11. La lettre correspondante pour notre clé est « P », qui est le numéro « 15 ». 11 + 15 = 26. Nous n’avons pas de lettre 26, donc nous retournons au début, ce qui nous donne la lettre « A »!

vigenere_excel

La grande force de cette technique réside dans le fait qu’une lettre peut servir à en crypter plusieurs autres. Par exemple, le « Y » de notre clé « PYTHON » sert à crypter « E », « R », « C » et « A ». À l’inverse, les lettres cryptées peuvent aussi renvoyer à plusieurs lettres en clair. Dans le message crypté, « A » renvoie tant « L » qu’à « C » et « H ».

De plus, avec six lettres, il existe 26^6 = 308 915 776 clés possibles! Et si on avait fait un petit effort supplémentaire avec une clé de 10 lettres, on aurait eu le choix entre 141 167 095 653 376 combinaisons différentes!  Pas étonnant que les mathématiciens se soient cassés les dents pendant près de trois siècles sur cet algorithme. Il y a beaucoup trop de possibilités pour toutes les tester, même avec un ordinateur!

Pendant plus 250 ans, nombreux sont ceux qui ont cru que De Vigenère avait conçu un algorithme parfait, mais cela revenait à sous-estimer le merveilleux pouvoir de l’ingéniosité humaine et des mathématiques, comme nous allons le voir!

Crypter à la façon De Vigenère

Imaginons que Blaise de Vigenère, de retour de la Cour, décide d’envoyer le message suivant à Henri III, pour éviter de se faire oublier par le roi. Il a évidemment crypté le message avec la clé Louise, qui correspond au prénom de la reine.

  • Votre altesse Henri III, roi de France et de tous les Français, j’espère que vous avez trouvé amusant de déchiffrer le message suivant. Il a été secrètement chiffré avec la technique que je vous ai montrée lors de mon dernier passage à la Cour. Il pourrait vous être d’une grande utilité pour vos correspondances, lorsque la plus grande discrétion est nécessaire! Votre éternellement fidèle Blaise de Vigenère.

Voici le code en Python pour encrypter le tout. Mes commentaires commencent à la ligne 4. Vous remarquerez que je travaille avec un alphabet sans caractère spéciaux. C’est pour simplifier. Mais n’hésitez pas à vous compliquez la vie si le coeur vous en dit!

Une fois lancé dans votre terminal, vous devriez avoir un résultat identique à ceci:

vigenere_crypt

Une fois reçu, Henri III (ou plus probablement un de ses domestiques) aurait dû déchiffrer le tout à la main. Heureusement, aujourd’hui, nous avons Python! Voici le code pour décrypter le message. Je n’ai commenté que les passages qui diffèrent.

Voici ce que ça donne un fois dans le terminal. Tout est lisible de nouveau!

vigenere_decrypt

Hacker Vigenère!

Impossible de tester toutes les possibilités de clés, il y en a beaucoup trop. Par conséquent, pour pirater l’algorithme de Vigenère, il faut trouver un moyen d’écarter certaines possibilités de clés pour en isoler seulement un nombre restreint, que l’on pourra alors tester.

La première question que l’on doit se poser pour le pirater est la suivante: Quelles sont les longueurs probables de la clé?

En 1863, l’officier prussien à la retraite, Friedrich Wilhelm Kasiski, trouva une façon très élégante d’en avoir une petite idée et cette technique porte aujourd’hui son nom. Il s’est rendu compte que l’algorithme créait des répétitions dans le texte crypté. Par exemple, dans notre message pour Henri III:

  • GCNZW EWHYAKI SSHZA MTW, LWA HP TLIFGP SN LW XZIM TWW QFUVÇSMD, X’YAHÈVP EOM NSFG UDWD EFICNÉ EXIMIFX OS XÉKZMQTLMJ PP AYAKERS MCAZLBN. QD E ÉEÉ GYKJÈXPAYVL GSWZNJÉ EGSW TS XPQBVAUFS KCW NP JICK ET AIVLVÉP ZIZK HP AIV VICBCMJ TLGMIYI À WO WWMV. TZ JWMVCOCB NSFG ÊNZW H’FBY OJEYRY CLMWWNÉ XGYC JIA USCFYAHSYRUVUID, ZIZKUFS FI HPFG AZSROS XQKGCÉHCWF IDH HÉKWWDOCZW! ZZHLM ÉLICBYTDIXSHB XMOÈZY JDETGY LW ZTUYVÈJI.

Kasiski s’est rendu compte que si on comptait le nombre de caractères entre chacune des répétitions, et qu’on cherchait les facteurs communs de ces « distances », les facteurs communs correspondaient à des longueurs possibles de la clé.

La raison est simple: plus le texte est long, plus il y a de chances que les mêmes lettres de la clé se retrouvent alignés avec les mêmes lettres du texte à crypter. Par conséquent, des répétitions apparaissent dans le message secret.

Donc, nul besoin d’essayer toutes les longueurs de clés imaginables. La méthode de Kasiski permet d’éliminer des millions, voire des milliards de possibilités!

Si on sait que la clé a de fortes chances d’être composée de 6 caractères (« Louise », par exemple), alors on sait que les lettres en position 1, 7, 13, 19, 25, etc., ont toute été cryptées avec la première lettre de la clé (« L » dans notre cas). Même chose pour les lettres en position 2, 8, 14, 20, 26, et ainsi de suite. J’ai coloré en bleu les lettres qui aurait été codées avec le premier caractère d’une clé d’une longueur de 6, pour le début de notre texte crypté.

GCNZW EWHYAKI SSHZA MTW, LWA HP TLIFGP SN LW XZIM TWW QFUVÇSMD…

Par la suite, on regroupe ces lettres en bleu. Puisqu’on sait qu’il n’y a que 26 possibles lettres qui les cryptent, on peut tester ces possibilités une à une et procéder à une analyse fréquentielle.

En français, on sait que les lettres les plus utilisées sont E (14%), S (8%), A (7%), I (7%) et T (7%). Par conséquent, lorsqu’on teste les 26 lettres de l’alphabet qui ont pu servir à crypter le message, on peut vérifier si le résultat de notre test est proche d’une répartition normale. Si c’est le cas, on saura que la lettre testée à de bonnes chances d’être dans la clé!

Après avoir testé et compilé les résultats pour toutes les premières lettres, toutes les deuxièmes, troisièmes, quatrièmes, cinquième et sixième lettres, on devrait avoir une bonne idée des lettres qui ont le plus de chances de se retrouver dans la clé.

Il nous restera donc plus qu’à tester toutes les combinaisons possibles pour les lettres suspectées, pour une clé de 6 caractères.

Dans notre cas, lorsqu’on sait que la clé est de 6 caractères, il existe 26^6 = 308 915 776 clés possibles. Toutefois, avec cette méthode et notre script en Python, nous sommes capables de trouver la clé en… 81 tentatives!

Vous ne me croyez pas? Voici le script complet. Faites le test vous-même! 🙂

Mes explications en commentaire sont assez brèves ici. Ce code est directement inspiré de celui de Hacking Secret Ciphers with Python, écrit par Al Sweigart. Je vous suggère d’aller y jeter un coup d’oeil si vous voulez plus de détails. Mes principales modifications sont d’avoir rendu le programme bilingue, pour qu’il déchiffre tant les messages secrets en français qu’en anglais. Aussi, l’exemple de Al Sweigart est un ensemble de cinq scripts qui fonctionnent ensemble. J’ai tout rassemblé en un seul et unique script.

Et voilà ce que ça donne dans le terminal!

vigenere_hack

Conclusion

Évidemment, ces algorithmes sont aussi vieux que célèbres et plus personne n’est censé les utiliser. De nos jours, les algorithmes de chiffrages sont bien plus compliqués et bien plus sécuritaires. J’encourage d’ailleurs tout un chacun à protéger ses données personnelles. Mais prenez garde et restez à l’affût, car personne n’est à l’abri d’une faille de sécurité…! 🙂

2 commentaires sur “Python et la cryptographie
(et un peu de piratage aussi)

  1. antoine

    bonjour, j’ai essayé votre code de cryptage à la Jules César et j’ai modifier les premières lignes:
    message = « Ce soir, on attaque les Gaulois! »
    message = message.decode(« utf-8 »).upper()

    Afin de pouvoir demander a l’utilisateur d’entrer lui meme sa phrase a crypter, j’ai donc utilisé la fonction input:
    message=raw_input(« Entrez votre message à coder »)
    message=message.decode(« utf-8 »).upper()

    alors déjà l’accent sur le « à » me donne une erreur, alors que mon fichier alors que quand je mets des accents dans message= »Ce soir lé gaulois » par exemple tout va bien, de plus, lorsqu’il me demande de rentrer ma phrase, les accents ne fonctionnent pas non plus, j’aimerai donc savoir si vous pouviez m’aider a comprendre comment demander a l’utilisateur de rentrer sa phrase et que celle ci fonctionne avec les accents. Merci 🙂

    Répondre

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *