15C: L'ANLNCCN MN BJUJMN BNLANCN de César

Les exercices 15A, 15B et 15C peuvent être fait dans n'importe quel ordre.

La cryptographie est l'art et la science de cacher le sens de l'information de façon que seulement certaines personnes puissent la voir. Dans cette leçon nous introduisons une des méthodes de cryptographie les plus simple, le Chiffre de César et vous allez écrire un programme pour le casser! Vous allez réaliser vous-même tous les aspects de la solution (contrairement à la leçon 15A ou nous avons divisé le problème en sous-parties pour vous).

Le chiffre de César fonctionne en remplaçant une lettre de l'alphabet par une autre lettre. Plus exactement, lorsque vous voulez chiffrer du texte, vous choisissez une valeur de décalage S, qui est un nombre entre 0 et 25. Vous remplacez ensuite chaque lettre dans le texte par une lettre qui est S positions plus loin dans l'alphabet, en revenant au début de l'alphabet après avoir atteint la lettre Z à la fin de l'alphabet.

Exemple

Supposons que nous voulions coder le message secret

RETROUVEZ MOI A HUIT HEURES PRES DU ZOO

en utilisant la valeur de décalage S=2. La règle de chiffrement dit que chaque lettre est remplacée par celle qui est placée 2 positions plus loin dans l'alphabet. Par exemple, comme l'alphabet est ABCDEFGHIJKLMNOPQRST..., la prémière lettre R sera remplacée par la lettre T. Poursuivant, le E est remplacé par G, le T est remplacé par V, et cetera. Pour chiffrer la lettre Z, on doit retourner au début: après Z on a A, puis B, donc Z est remplacé par B. De même Y serait remplacé par A. Donc la version chiffrée de notre message est:

TGVTQWXGB OQK C JWKV JGWTGU RTGU FW BQQ

Si un espion voyait ce message, il ne serait pas du tout évident pour lui de voir ce qu'il cache.

Exercice à réponse courte : Codeur Espion
Quel est le résultat de chiffrer CODEUR ESPION avec la valeur de décalage S=5? (Utilisez les majuscules.) Vous pouvez écrire un programme dans la console pour faire cette opération, si vous voulez — cela vous sera peut être utile plus tard.
Correct !

Décoder

Une fois que votre ami obtient le message, s'il connait la valeur de décalage S alors il est facile pour lui de dechiffrer le message: chaque lettre est remplacée par celle qui se trouve S positions avant dans l'alphabet. Par exemple, il prendrait le L, regarderait deux positions avant dans l'alphabet et trouverait J, qui est la première lettre de notre message secret. Ici encore, il faut traiter l'alphabet de cyclique, Z est avant A.

Exercice à réponse courte : Décodeur Espion
Si le message chiffré est UTFK et que le décalage est S=6, quel était le message d'origine? (Utiliser les majuscules.)
Correct !

Travailler pour les méchants

Vous avez été engagé par un espion espion pour déchiffrer un message chiffré avec le Chiffre de César. Malheureusement, l'espion ne connaît pas la valeur de S. Nous allons utiliser les statistiqes pour écrire un programme qui a une bonne chance de trouver automatiquement la valeur correct de S.

Notre méthode utilisera la méthode d'analyse des fréquences des lettres. En français, certaines lettres sont très courantes (comme le E) et d'autres très rares (comme le K). Voici une table de fréquence dérivée en calculant l'occurence des lettres dans un long texte.

A B C D E F G H I
.0812 .0090 .0334 .0367 .1713 .0107 .0087 .0074 .0758
J K L M N O P Q R
.0054 .0005 .0545 .0297 .0709 .0541 .0302 .0136 .0655
S T U V W X Y Z
.0795 .0724 .0637 .0163 .0011 .0039 .0031 .0014

Par exemple, la fréquence de L, .0545=5,45%, signifie qu'en moyenne dans un texte en français, 5,45% des lettres sont des L.

Appelons justesse d'une lettre sa valeur dans le tableau ci-dessus. Pour notre méthode statistique, définissons la justesse d'une phrase comme étant égale à la somme de la justesse de chacune de ses lettres. Par exemple, la justesse de la chaîne TERRE est

justesse("TERRE") = .0724 + .1713 + .0655 + .0655 + .1713 = .5460

L'idée dans l'analyse de fréquence est que les chaînes avec la plus grande justesse sont plus à même de représenter un texte français. Par exemple, si l'espion voit le message chiffré "VGTTG", il peut représenter le text d'origine "TERRE" avec décalage S=2, ou "UFSSF" avec S=1. Mais la justesse de "UFSSF" est

justesse("UFSSF") = .0637 + .0107 + .0795 + .0795 + .0107 = .2441

et comme .2441 < .5460, votre programme devrait conclure que TERRE a plus de chance d'être le message correct que UFSSF.

Mesurer les chaîne par leur justesse n'est pas parfais. Disons que le message secret était KAYAK et que la valeur de décalage était S=10, de telle façon que le message chiffré soit UKIKU. Quand vous indiquez UKIKU à votre programme solveur, il va essayer S=10, donnant KAYAK comme possibitlié avec justesse .1665, mais le meilleur est S=16, qui donnne EUSUE avec une justesse égale à .5495 comme étant la meilleure réponse devinée. Et votre programme va afficher le mot EUSUE qui n'est pas français. (Une analyse de fréquence de ce type fonctionne mieux si le message secret est plus long.)

Exercice de code : Décryptage automatique
Ecrivez un programme qui lit une ligne d'entrée, le message chiffré, composé uniquement de lettre majuscules et d'espaces. Votre programme doit essayer de décoder le messagee en utilisant les 26 valeurs possibles du décalage S; de ces 26 possibilité, il affichera celle avec la plus grande justesse.

Pour vous aider, nous avons pré-défini la variable justesseLettres pour vous, une liste de longueur 26 qui est égale aux valeurs de la table de fréquences ci-dessus,

justesseLettres = [.0812, .0090, .0334, .0367, .1713,...
Cliquez ici pour des conseils généraux.
Entrez instructions de test comme print(mafonction("argument de test")) ci-dessous.

La solution ci-dessus est appelée force brute car on essaye les 26 solutions possibles. Vous auriez même pu faire ce travail à la main! Les protocoles cryptographiques modernes, par contre, sont développés pour les solutions de force brute ne fonctionnent pas même si vous utilisez des ordinateurs très rapides pour essayer toutes les solutions.

Si vous vouliez rendre ce système d'auto-déchiffrement plus efficace, vous pourriez faire attention à d'autres aspects statistiques de la langue française, par exemple "quelles lettres sont le plus à même d'être en paire" ou "quelles lettres ont le plus de chance d'être au début d'un mot". C'est aussi utile pour de plus généraux chiffres de substitution, où des lettres sont remplacées par des lettres mais pas de manière cyclique. Pour ces méthodes de chiffrement, la force brute ne fonctionne pas puisqu'il y a 26*25*...*1 chiffres de substitution possibles, ce qui est à peu près égal à 4 * 1026.

Vous avez commplété cette leçon! Soyez libre d'envoyer des messages chiffrés à vos amis.