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.
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.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.
UTFK et que le décalage est S=6, quel était le message d'origine? (Utiliser les majuscules.)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 statistiques 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.) |
