{"id":4691,"date":"2012-06-21T17:44:16","date_gmt":"2012-06-21T21:44:16","guid":{"rendered":"http:\/\/cscircles.cemc.uwaterloo.ca\/?page_id=4691"},"modified":"2018-02-05T02:50:41","modified_gmt":"2018-02-05T07:50:41","slug":"15c-fr","status":"publish","type":"page","link":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/15c-fr\/","title":{"rendered":"15C: L'ANLNCCN MN BJUJMN BNLANCN de C\u00e9sar"},"content":{"rendered":"<!-- Please retain this notice and add more notes if you create a new version.<br \/>\nMain French translator: Brice Canvel, brice.canvel@gmail.com<br \/>\nOriginal lesson author: David Pritchard, daveagp@gmail.com<br \/>\nLicense: http:\/\/creativecommons.org\/licenses\/by-nc-sa\/3.0\/<br \/>\nFor the full site, visit http:\/\/cscircles.ca-->\n<p><em>Les exercices 15A, 15B et 15C peuvent \u00eatre fait dans n'importe quel ordre.<\/em><\/p>\n<p>La cryptographie est l'art et la science de cacher le sens de l'information de fa\u00e7on que seulement certaines personnes puissent la voir. Dans cette le\u00e7on nous introduisons une des m\u00e9thodes de cryptographie les plus simple, le <strong><a href=\"http:\/\/fr.wikipedia.org\/wiki\/Chiffrement_par_d%C3%A9calage\">Chiffre de C\u00e9sar<\/a> <\/strong> et vous allez \u00e9crire un programme pour le casser! Vous allez r\u00e9aliser vous-m\u00eame tous les aspects de la solution (contrairement \u00e0 la le\u00e7on 15A ou nous avons divis\u00e9 le probl\u00e8me en sous-parties pour vous).<\/p>\n<p>Le chiffre de C\u00e9sar fonctionne en rempla\u00e7ant une lettre de l'alphabet par une autre lettre. Plus exactement, lorsque vous voulez chiffrer du texte, vous choisissez une <strong>valeur de d\u00e9calage<\/strong><em> S<\/em>, qui est un nombre entre 0 et 25. Vous remplacez ensuite chaque lettre dans le texte par une lettre qui est <em>S<\/em> positions plus loin dans l'alphabet, en revenant au d\u00e9but de l'alphabet apr\u00e8s avoir atteint la lettre Z \u00e0 la fin de l'alphabet.<\/p>\n<h2>Exemple<\/h2>\n<p>Supposons que nous voulions coder le message secret<\/p>\n<p style=\"text-align: center;\"><code>RETROUVEZ MOI A HUIT HEURES PRES DU ZOO<\/code><\/p>\n<p>en utilisant la valeur de d\u00e9calage <em>S<\/em>=2. La r\u00e8gle de chiffrement dit que chaque lettre est remplac\u00e9e par celle qui est plac\u00e9e 2 positions plus loin dans l'alphabet. Par exemple, comme l'alphabet est ABCDEFGHIJKLMNOPQ<strong>R<\/strong>S<strong>T<\/strong>..., la pr\u00e9mi\u00e8re lettre <code>R<\/code> sera remplac\u00e9e par la lettre <code>T<\/code>. Poursuivant, le <code>E<\/code> est remplac\u00e9 par <code>G<\/code>, le <code>T<\/code> est remplac\u00e9 par <code>V<\/code>, et cetera. Pour chiffrer la lettre <code>Z<\/code>, on doit retourner au d\u00e9but: apr\u00e8s <code>Z<\/code> on a <code>A<\/code>, puis <code>B<\/code>, donc <code>Z<\/code> est remplac\u00e9 par <code>B<\/code>. De m\u00eame <code>Y<\/code> serait remplac\u00e9 par <code>A<\/code>. Donc la version chiffr\u00e9e de notre message est:<\/p>\n<p style=\"text-align: center;\"><code>TGVTQWXGB OQK C JWKV JGWTGU RTGU FW BQQ<\/code><\/p>\n<p>Si un espion voyait ce message, il ne serait pas du tout \u00e9vident pour lui de voir ce qu'il cache.<\/p>\n<div class='pybox modeNeutral' id='pybox0'>\n<img title='You have not yet completed this problem.' src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Short Answer Exercise: <\/span><span class='title'>Codeur Espion<\/span><\/div>Quel est le r\u00e9sultat de chiffrer <code>CODEUR ESPION<\/code>\u00a0avec la valeur de d\u00e9calage <em>S<\/em>=5? (Utilisez les majuscules.) Vous pouvez \u00e9crire un programme dans la <a href=\"\/console-fr\/\">console<\/a> pour faire cette op\u00e9ration, si vous voulez \u2014 cela vous sera peut \u00eatre utile plus tard.<br><label for=\"pyShortAnswer0\">Your answer: <\/label><input type=\"text\" onkeypress=\"{if (event.keyCode==13) pbShortCheck(0)}\" id=\"pyShortAnswer0\"><div class=\"pyboxbuttons\"><input type=\"hidden\" name=\"type\" value=\"trimmableString\"\/><input type=\"hidden\" name=\"correct\" value=\"HTIJZW JXUNTS\"\/><input type=\"hidden\" name=\"slug\" value=\"15c.encode\"\/><input type=\"hidden\" name=\"lang\" value=\"\"\/><input type='submit' style='margin:5px;' value='Check answer' onClick = 'pbShortCheck(0)'\/><\/div><div class=\"pbresults\" id=\"pyShortResults0\"><\/div><div class=\"epilogue\">Correct!<\/div><\/div>\n<h2>D\u00e9coder<\/h2>\n<p>Une fois que votre ami obtient le message, s'il connait la valeur de d\u00e9calage <em>S<\/em> alors il est facile pour lui de dechiffrer le message: chaque lettre est remplac\u00e9e par celle qui se trouve <em>S<\/em> positions <em>avant<\/em> dans l'alphabet. Par exemple, il prendrait le <code>L<\/code>, regarderait deux positions avant dans l'alphabet et trouverait <code>J<\/code>, qui est la premi\u00e8re lettre de notre message secret. Ici encore, il faut traiter l'alphabet de cyclique, <code>Z<\/code> est avant <code>A<\/code>.<\/p>\n<p><div class='pybox modeNeutral' id='pybox1'>\n<img title='You have not yet completed this problem.' src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Short Answer Exercise: <\/span><span class='title'>D\u00e9codeur Espion<\/span><\/div>Si le message chiffr\u00e9 est <code>UTFK<\/code>\u00a0et que le d\u00e9calage est\u00a0<em>S<\/em>=6, quel \u00e9tait le message d'origine? (Utiliser les majuscules.)<br><label for=\"pyShortAnswer1\">Your answer: <\/label><input type=\"text\" onkeypress=\"{if (event.keyCode==13) pbShortCheck(1)}\" id=\"pyShortAnswer1\"><div class=\"pyboxbuttons\"><input type=\"hidden\" name=\"type\" value=\"trimmableString\"\/><input type=\"hidden\" name=\"correct\" value=\"ONZE\"\/><input type=\"hidden\" name=\"slug\" value=\"15c.decode\"\/><input type=\"hidden\" name=\"lang\" value=\"\"\/><input type='submit' style='margin:5px;' value='Check answer' onClick = 'pbShortCheck(1)'\/><\/div><div class=\"pbresults\" id=\"pyShortResults1\"><\/div><div class=\"epilogue\">Correct!<\/div><\/div>\n<h2>Travailler pour les m\u00e9chants<\/h2>\n<p>Vous avez \u00e9t\u00e9 engag\u00e9 par un espion espion pour d\u00e9chiffrer un message chiffr\u00e9 avec le Chiffre de C\u00e9sar. Malheureusement, l'espion ne conna\u00eet pas la valeur de <em>S<\/em>. Nous allons utiliser les statistiques pour \u00e9crire un programme qui a une bonne chance de trouver automatiquement la valeur correct de <em>S<\/em>.<\/p>\n<p>Notre m\u00e9thode utilisera la m\u00e9thode <strong>d'analyse des fr\u00e9quences des lettres<\/strong>. En fran\u00e7ais, certaines lettres sont tr\u00e8s courantes (comme le E) et d'autres tr\u00e8s rares (comme le K). Voici une table de fr\u00e9quence d\u00e9riv\u00e9e en calculant l'occurence des lettres dans un long texte.<\/p>\n<table class=\"minyspace\" style=\"text-align: center;\">\n<tbody>\n<tr>\n<th>A<\/th>\n<th>B<\/th>\n<th>C<\/th>\n<th>D<\/th>\n<th>E<\/th>\n<th>F<\/th>\n<th>G<\/th>\n<th>H<\/th>\n<th>I<\/th>\n<\/tr>\n<tr>\n<td>.0812<\/td>\n<td>.0090<\/td>\n<td>.0334<\/td>\n<td>.0367<\/td>\n<td>.1713<\/td>\n<td>.0107<\/td>\n<td>.0087<\/td>\n<td>.0074<\/td>\n<td>.0758<\/td>\n<\/tr>\n<tr>\n<th>J<\/th>\n<th>K<\/th>\n<th>L<\/th>\n<th>M<\/th>\n<th>N<\/th>\n<th>O<\/th>\n<th>P<\/th>\n<th>Q<\/th>\n<th>R<\/th>\n<\/tr>\n<tr>\n<td>.0054<\/td>\n<td>.0005<\/td>\n<td>.0545<\/td>\n<td>.0297<\/td>\n<td>.0709<\/td>\n<td>.0541<\/td>\n<td>.0302<\/td>\n<td>.0136<\/td>\n<td>.0655<\/td>\n<\/tr>\n<tr>\n<th>S<\/th>\n<th>T<\/th>\n<th>U<\/th>\n<th>V<\/th>\n<th>W<\/th>\n<th>X<\/th>\n<th>Y<\/th>\n<th>Z<\/th>\n<th><\/th>\n<\/tr>\n<tr>\n<td>.0795<\/td>\n<td>.0724<\/td>\n<td>.0637<\/td>\n<td>.0163<\/td>\n<td>.0011<\/td>\n<td>.0039<\/td>\n<td>.0031<\/td>\n<td>.0014<\/td>\n<td><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Par exemple, la fr\u00e9quence de L, .0545=5,45%, signifie qu'en moyenne dans un texte en fran\u00e7ais, 5,45% des lettres sont des L.<\/p>\n<p>Appelons <strong>justesse<\/strong> d'une lettre sa valeur dans le tableau ci-dessus. Pour notre m\u00e9thode statistique, d\u00e9finissons la <em>justesse d'une phrase<\/em> comme \u00e9tant \u00e9gale \u00e0 la somme de la justesse de chacune de ses lettres. Par exemple, la justesse de la cha\u00eene <code>TERRE<\/code> est<\/p>\n<p style=\"text-align: center;\">justesse(\"<code>TERRE<\/code>\") = .0724 + .1713 + .0655 + .0655 + .1713 = .5460<\/p>\n<p>L'id\u00e9e dans l'analyse de fr\u00e9quence est que les cha\u00eenes avec la plus grande justesse sont plus \u00e0 m\u00eame de repr\u00e9senter un texte fran\u00e7ais. Par exemple, si l'espion voit le message chiffr\u00e9 \"<code>VGTTG<\/code>\", il peut repr\u00e9senter le text d'origine \"<code>TERRE<\/code>\" avec d\u00e9calage\u00a0<em>S<\/em>=2, ou \"<code>UFSSF<\/code>\" avec <em>S<\/em>=1. Mais la justesse de \"<code>UFSSF<\/code>\" est<\/p>\n<p style=\"text-align: center;\">justesse(\"<code>UFSSF<\/code>\") = .0637 + .0107 + .0795 + .0795 + .0107 = .2441<\/p>\n<p>et comme .2441 &lt; .5460, votre programme devrait conclure que <code>TERRE<\/code> a plus de chance d'\u00eatre le message correct que <code>UFSSF<\/code>.<\/p>\n<p><table class='pywarn'><tr><td class='pywarnleft'><img src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/files\/warning.png'\/><\/td><td class='pywarnright'><span> Mesurer les cha\u00eene par leur <em>justesse<\/em> n'est pas parfais. Disons que le message secret \u00e9tait\u00a0<code>KAYAK<\/code>\u00a0et que la valeur de d\u00e9calage \u00e9tait\u00a0<em>S<\/em>=10, de telle fa\u00e7on que le message chiffr\u00e9 soit <code>UKIKU<\/code>. Quand vous indiquez <code>UKIKU<\/code>\u00a0\u00e0 votre programme solveur, il va essayer <em>S<\/em>=10, donnant <code>KAYAK<\/code> comme possibitli\u00e9 avec justesse .1665, mais le meilleur est\u00a0<em>S<\/em>=16, qui donnne\u00a0<code>EUSUE<\/code>\u00a0avec une justesse \u00e9gale \u00e0 .5495 comme \u00e9tant la meilleure r\u00e9ponse devin\u00e9e. Et votre programme va afficher le mot <code>EUSUE<\/code> qui n'est pas fran\u00e7ais. (Une analyse de fr\u00e9quence de ce type fonctionne mieux si le message secret est plus long.) <\/span><\/td><\/table><\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform2\" method=\"POST\">\n<div class='pybox modeNeutral ' id='pybox2'>\n<img title='You have not yet completed this problem.' src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>D\u00e9cryptage automatique<\/span><\/div>\n<div>Ecrivez un programme qui lit une ligne d'entr\u00e9e, le message chiffr\u00e9, compos\u00e9 uniquement de lettre majuscules et d'espaces. Votre programme doit essayer de d\u00e9coder le messagee en utilisant les 26 valeurs possibles du d\u00e9calage <em>S<\/em>; de ces 26 possibilit\u00e9, il affichera celle avec la plus grande justesse.<\/div>\n<p>Pour vous aider, nous avons pr\u00e9-d\u00e9fini la variable <code>justesseLettres<\/code>\u00a0pour vous, une liste de longueur 26 qui est \u00e9gale aux valeurs de la table de fr\u00e9quences ci-dessus,<\/p>\n<pre>justesseLettres = [.0812, .0090, .0334, .0367, .1713,...<\/pre>\n<div><a class=\"hintlink\"  id=\"hintlink3\">Cliquez ici pour des conseils g\u00e9n\u00e9raux.<\/a><div class=\"helpOuter\" style=\"display: none;\"><div class=\"helpInner\"><div style=\"text-align: center\">You need to create an account and log in to ask a question.<\/div><\/div><\/div><div class='pyboxTextwrap pyboxCodewrap RW resizy'  style='height: 526px;'><textarea wrap='off' name='usercode2' id='usercode2'  cols=10 rows=20   class='pyboxCode RW'>\n# tester la constante donn\u00e9e ... vous pouvez supprimer cette ligne\nprint(justesseLettres)\n# delete this comment and enter your code here\n<\/textarea><\/div>\n<div id='pbhistory2' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput2\">Enter testing statements like <code>print(myfunction(\"test argument\"))<\/code> below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<input type='hidden' id='defaultCode2' value='# tester la constante donn\\u00e9e ... vous pouvez supprimer cette ligne\\nprint(justesseLettres)\\n'><\/input>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit2' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch2\" value=\"Input Switch\" onclick=\"pbInputSwitch(2,'Y')\" ><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(2)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(2,'Y')\" ><\/td>\n<\/tr><\/table><select id='pbSelect2' class='selectmore'><option name='more'>More actions...<\/option>\n<option name='history' data-pbonclick=\"historyClick(2,'15c.autodecrypt')\" >History<\/option>\n<option name='default' data-pbonclick=\"pbSetText(2,descape($('#defaultCode2').val()))\" >Reset code to default<\/option>\n<option name='help' data-pbonclick=\"helpClick(2);\" >Help<\/option>\n<\/select><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"\"\/><input type=\"hidden\" id=\"inputInUse2\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"2\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"5babc8f432902c560ad83224ab2dc80c\"\/>\n<div id='pbresults2' class='pbresults avoidline'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>jQuery(function(){pbToggleCodeMirror(2);});pbInputSwitch(2,\"Y\");<\/script>\n<\/div>\n<p><table class='pywarn'><tr><td class='pywarnleft'><img src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/files\/warning.png'\/><\/td><td class='pywarnright'><span> La solution ci-dessus est appel\u00e9e <em>force brute<\/em> car on essaye les 26 solutions possibles. Vous auriez m\u00eame pu faire ce travail \u00e0 la main! Les protocoles cryptographiques modernes, par contre, sont d\u00e9velopp\u00e9s pour les solutions de force brute ne fonctionnent pas m\u00eame si vous utilisez des ordinateurs tr\u00e8s rapides pour essayer toutes les solutions. <\/span><\/td><\/table><\/p>\n<p>Si vous vouliez rendre ce syst\u00e8me d'auto-d\u00e9chiffrement plus efficace, vous pourriez faire attention \u00e0 d'autres aspects statistiques de la langue fran\u00e7aise, par exemple \"quelles lettres sont le plus \u00e0 m\u00eame d'\u00eatre en paire\" ou \"quelles lettres ont le plus de chance d'\u00eatre au d\u00e9but d'un mot\". C'est aussi utile pour de plus g\u00e9n\u00e9raux <a href=\"http:\/\/fr.wikipedia.org\/wiki\/Chiffrement_par_substitution\">chiffres de substitution<\/a>, o\u00f9 des lettres sont remplac\u00e9es par des lettres mais pas de mani\u00e8re cyclique. Pour ces m\u00e9thodes de chiffrement, la force brute ne fonctionne pas puisqu'il y a 26*25*...*1\u00a0chiffres de substitution possibles, ce qui est \u00e0 peu pr\u00e8s \u00e9gal \u00e0 4 * 10<sup>26<\/sup>.<\/p>\n<p>Vous avez compl\u00e9t\u00e9 cette le\u00e7on! Soyez libre d'envoyer des messages chiffr\u00e9s \u00e0 vos amis.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Les exercices 15A, 15B et 15C peuvent \u00eatre fait dans n'importe quel ordre. La cryptographie est l'art et la science de cacher le sens de l'information de fa\u00e7on que seulement certaines personnes puissent la voir. Dans cette le\u00e7on nous introduisons &hellip; <a href=\"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/15c-fr\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-4691","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/pages\/4691","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/comments?post=4691"}],"version-history":[{"count":31,"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/pages\/4691\/revisions"}],"predecessor-version":[{"id":10727,"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/pages\/4691\/revisions\/10727"}],"wp:attachment":[{"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/media?parent=4691"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}