(Février 2016) Décryptez les secrets les mieux gardés !

Offre valable sous réserve d’utilisation d’un chiffrement antérieur au XVIIe siècle. Voir conditions en magasin.

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Pour ceux qui prennent peur devant un texte long

Chaque partie de ce défi, identifiée par un titre, peut être réalisée séparément. Il n’est absolument pas besoin de tout lire (ni de tout faire) d’un seul coup. Alors ne partez pas tout de suite. :D

Pour ce Défi de Clem de février, on revient vers de la cryptographie, mais promis, ce sera plus simple que la dernière fois. Le but de ce défi va être de réaliser un programme capable de décrypter1 automatiquement un texte rendu illisible par l’utilisation de certains chiffrements simples. Semi-automatiquement serait plus exact : un tel programme peut se tromper, et il faut toujours un œil humain pour vérifier le résultat obtenu et, éventuellement, remettre la recherche sur les rails.

Nous allons procéder en trois étapes, permettant d’introduire des outils de décryptage au fur et à mesure, et de présenter trois systèmes de chiffrement, pour ceux qui ne les connaissent pas encore.

Tout au long de ce défi, gardez à l’esprit que, du fait des méthodes de décryptage employées, le programme sera d’autant plus efficace que le message fourni en entrée sera long.

Étape 0 : pré-traiter un message

Il est d’usage, dans les systèmes de chiffrement les plus basiques, de simplifier le message à chiffrer en enlevant toutes les espaces et les ponctuations, en remplaçant les caractères spéciaux par leurs versions sans diacritiques (p. ex. ç > c, œ > oe, ê > e, etc.) et en mettant toutes les lettres en majuscule, ou en minuscule, selon ce que vous préférez.

Cette étape 0 consiste donc à écrire une fonction qui prenne un message écrit en français courant (on n’utilisera que du français dans ce défi) et en fasse un message traitable par les fonctions de chiffrement. Dans l’idéal la fonction sera paramétrable, permettant de choisir une sortie en minuscules ou majuscules, de conserver les espaces d’origine ou de les enlever totalement, ou de redécouper le message toutes les $n$ lettres.

Par exemple, le texte que j’écris en ce moment même, avec les options « majuscules » et « découpage toutes les cinq lettres », doit donner le résultat suivant.
PAREX EMPLE LETEX TEQUE JECRI SENCE MOMEN TMEME AVECL ESOPT IONSM AJUSC ULESE TDECO UPAGE TOUTE SLESC INQLE TTRES DOITD ONNER LERES ULTAT SUIVA NT

Étape 1 : chiffre de César

Le chiffre de César est ce que l’on appelle un chiffrement par substitution simple : chaque lettre du message en clair (c’est-à-dire, le message que l’on va chiffrer) sera remplacée par une et une seule autre lettre ; en outre, deux lettres de l’alphabet de départ ne peuvent pas être remplacées par la même lettre de l’alphabet d’arrivée.

Plus précisément, le chiffre de César se contente de décaler les lettres du message en clair d’un certain nombre de rangs dans l’alphabet. Par exemple, le chiffre de César « classique » décale de trois lettres : A devient D, B devient E, C devient F, etc. Et pour déchiffrer, on procède simplement dans l’autre sens : on décale chaque lettre du même nombre de rangs dans l’autre sens.

Commencez donc par écrire une fonction qui prend un texte et un décalage, et permet de chiffrer / déchiffrer le texte avec le chiffre de César utilisant ce décalage.

Avec un décalage de 12, le message « Rends à César ce qui est à moi ! » doit devenir DQZPEMOQEMDOQCGUQEFMYAU.

Comment l’attaquer ?

L’avantage du chiffre de César (du point de vue de l’attaquant, bien sûr), c’est qu’il n’y a que 25 décalages possibles à essayer et à vérifier, ce qui est donc très rapide. Et c’est précisément ainsi que va fonctionner votre première fonction de décryptage : il s’agira de décaler le message de un rang, puis de deux, puis de trois, etc. et de laisser l’utilisateur trouver lui-même quelle combinaison est la bonne.

Cette méthode a l’avantage de fonctionner quelle que soit la longueur du message, mais elle demande encore une trop grande participation de l’utilisateur. Pour mieux automatiser le processus, on va utiliser une forme simplifiée d’analyse des fréquences.

Vous l’avez sans doute déjà remarqué, toutes les lettres n’apparaissent pas aussi souvent dans un texte : on trouve beaucoup plus de T que de J, par exemple. Eh bien, en français, c’est le E qui truste la première place, et de très loin : en moyenne, 17,26 % des lettres d’un texte en français sont des E. En deuxième et troisième places arrivent le A avec 8,4 % et le S avec 8,08 % : une domination incontestable, vous disais-je.

Ce que vous devez faire, c’est compter combien de fois apparaît chaque lettre du message à décrypter : celle qui apparaît en première position a de très fortes chances d’être un E dans le texte en clair, ce qui vous permet de déduire le décalage qui a été utilisé. Allez ! Au travail !

En guise d’exercice, essayez de retrouver quel message se cache derrière le cryptogramme suivant.
SYKMA OTTGB GOZPG SGOYK AJKHU TNKAX GBKIY KYINB XKYOR RKYVK XJGOZ ZUAZK YJKRG SSKLG UTATH KGASG ZOTKR RKYIG YYGOK TZRKA XIUXJ KYKTG RRGOK TZJGT YRGSU TZGMT KKZRN GAZRK RUAVR KYSGT MKGOZ TORKY IGXKY YKYJK RKAXS GZXKT ORGVK AXJAR UAVXO KTTKR KYXKZ KTGOZ IZGOZ VGXGZ ORJKY INBXK YOTJV KTJGT ZKYBU ARGTZ ZUAZV XODRK MXGTJ GOXKZ RGROH KXZ

Il s’agissait du tout début de La chèvre de M. Seguin.

M. Seguin n’avait jamais eu de bonheur avec ses chèvres.

Il les perdait toutes de la même façon : un beau matin, elles cassaient leur corde, s’en allaient dans la montagne, et là-haut le loup les mangeait. Ni les caresses de leur maître, ni la peur du loup, rien ne les retenait. C’était, paraît-il, des chèvres indépendantes, voulant à tout prix le grand air et la liberté.

Pistes d’amélioration
Le ROT13 est un cas particulier du chiffre de César, celui où le décalage est de 13 : la même fonction permet alors de chiffrer et déchiffrer le message. Vous pouvez, si vous le désirez, ajouter une fonction spécifique pour ce chiffrement-là.

Sur un texte court, l’analyse fréquentielle peut donner de mauvais résultats. Vous pouvez proposer plusieurs résultats possibles, par ordre de probabilité : d’abord, la lettre la plus fréquente du cryptogramme correspond à un E, puis c’est la deuxième plus fréquente, puis la troisième. S’il faut aller plus loin, c’est que vous n’avez pas de chance, ou qu’un petit malin a décidé de chiffrer La Disparition de Georges Perec.

(Niveau avancé) Il est possible d’aller encore plus loin pour limiter le besoin de recourir à une vérification humaine. Une fois que vous avez déterminé quelle lettre correspond à un E et décrypté le message en fonction de cela, vous pouvez utiliser un dictionnaire pour chercher des mots de sept ou huit lettres dans le texte ainsi décrypté : si vous n’en trouvez aucun, c’est mauvais signe, et vous pouvez passer à la deuxième solution la plus probable.

Étape 2 : substitution simple

Je vais répéter ici la définition d’un chiffrement par substitution simple : chaque lettre du message en clair sera remplacée par une et une seule autre lettre ; en outre, deux lettres de l’alphabet de départ ne peuvent pas être remplacées par la même lettre de l’alphabet d’arrivée.

La différence avec le chiffre de César, c’est qu’il n’y a aucune espèce de logique dans la manière d’échanger les lettres. On peut décider, par exemple, que A devient K, B devient W, C reste C, D devient A, E devient J, etc. On constitue ainsi un alphabet désordonné qui devient la clé de notre message : ici, il s’agirait de KWCAJ…

Pour chiffrer un message, on prend chaque lettre du message en clair et on la remplace par son équivalent dans l’alphabet desordonné. Pour déchiffrer le message, on procède dans l’autre sens. Vous pouvez dès à présent coder ces deux fonctions.

Avec l’alphabet désordonné GHSUKNMLTCQXVZJIDORYABWPEF, le message « La réforme, oui. La chienlit, non ! » doit devenir XGOKN JOVKJ ATXGS LTKZX TYZJZ.

Il n’est cependant pas très pratique de générer (et surtout, de retenir !) un alphabet désordonné parfaitement aléatoire. Il existe donc deux techniques pour générer un alphabet désordonné à partir d’une clé.

  • L’alphabet désordonné commence par la clé, nettoyée bien sûr de ses doublons, puis les autres lettres de l’alphabet suivent leur ordre habituel.
  • On procède de même, mais en répartissant les lettres sur cinq ou six colonnes, puis on prend les lettres colonne par colonne.

Vous pouvez donc ajouter à votre code la possibilité de générer des alphabets désordonnés à partir d’une clé.

Avec la clé DISMOITOUTBILOUTE, la première méthode donne l’alphabet désordonné DISMOTUBLEACFGHJKNPQRVWXYZ. La seconde méthode, elle, avec un tableau de cinq colonnes, donne le résultat suivant.

1 2 3 4 5
D I S M O
T U B L E
A C F G H
J K N P Q
R V W X Y
Z

Ce qui donne l’alphabet désordonné DTAJRZIUCKVSBFNWMLGPXOEHQY.

Comment l’attaquer ?

La seule technique viable consiste à généraliser l’analyse des fréquences. Il faut compter combien de fois apparaît chaque lettre dans le cryptogramme, et donc quel pourcentage de l’ensemble des lettres elle représente, et comparer avec la répartition fréquentielle des lettres en français pour tenter une correspondance entre alphabet désordonné et alphabet ordinaire.

Pour cela, vous aurez besoin de ladite répartition fréquentielle du français, que je vous donne directement sous une forme utilisable informatiquement, parce que je suis gentil.

1
2
3
4
5
(0.084,0.0106,0.0303,0.0418,0.1726,
0.0112,0.0127,0.0092,0.0734,0.0031,
0.0005,0.0601,0.0296,0.0713,0.0526,
0.0301,0.0099,0.0655,0.0808,0.0707,
0.0574,0.0132,0.0004,0.0045,0.0030,0.0012)

Cependant, si vous testez votre fonction de décryptage, vous verrez que même avec un texte de plus de huit mille caractères, le résultat obtenu par cette seule méthode est assez illisible. Il vous faudra donc ajouter deux possibilités de post-traitement, afin de rendre la fonction plus utilisable.

Tout d’abord, il faudra que l’utilisateur puisse signaler au programme où il s’est trompé. Supposez par exemple que le programme aboutisse au résultat « JEIUSITOUJOURILA » : il faudrait pouvoir lui dire « En fait, tu as inversé le S et le I dans ton décryptage, essaye encore. ». Je vous laisse décider quelle forme cela peut prendre.

Ensuite, il serait même encore mieux que le programme propose de lui-même ce genre de corrections. En effet, si vous regardez attentivement les fréquences, à part le E qui est tout seul en première place, les autres sont assez susceptibles de changer de place si le texte en clair ne respecte pas strictement la répartition fréquentielle.

Par exemple, C (3,03 %), P (3,01 %) et M (2,96 %) qui ont un score très proche, et assez nettement séparé de leurs plus proches voisins D (4,18 %) et V (1,32 %), ont de fortes chances de se retrouver mélangés. Il pourrait être assez intéressant que le programme propose plusieurs versions alternatives du décryptage, où ces trois lettres arriveraient dans un ordre différent. Et bien évidemment, faire de même avec d’autres lettres susceptibles d’être inversées. À vous de voir comment rendre cette amélioration progressive du rendu la plus ergonomique possible.

En guise d’exercice, essayez de retrouver quel message se cache derrière le cryptogramme suivant. Gardez bien à l’esprit, cependant, qu’il est à peu près impossible d’arriver à un résultat parfait du premier coup, donc ne vous inquiétez pas si votre programme ne donne pas un retour optimal.
IMGPB MUMBB RRIRG APBMB SGRIR ONHAP PMGQR RQDMS IAQRB SAQLM AEBRD RGQQM ABBMG QIRPR PJHAG QRPUM OABBM GQRPS GJMPP MVRMP MBSDA RNRMQ NMURN PBRLR SABBM VRDHN QRBIS GVNMG ISJMP IMGPB RPJNH LHGIR SNPIR BMUMB BRRHS BMBSD ARNRG RJMNU ARGQJ MPPRD RSURG QIRPL HNDRP KSAGR PHGQJ MPIRP QAGRR PMRQN RUSRP LHAPH GGMGQ RBMUR VRQMQ AHGNR OHSUN ROCMK SRURN PMGQH SBMUA VGRUA RNVRD MBRLA KSRRQ BRPJB MGQRP VNADJ MGQRP NMDJR GQJMN DABRP JARNN RPIRP JMBMA PRGNS AGRPR GBMOM GQRQN HAQRD RGQIR POHBH GGRPE NAPRR PRQIR QNMGV RPDHG HBAQC RPPHS BRUMG QBRPI MBBRP IRDMN ENRJH PRRPJ MNIRP DMAGP HSEBA RRPRQ IMGPB RPMNE NRPKS AJHSP PRGQV AVMGQ RPKSR PIMGP IRPOH SNPIR BMENR RPEHG IAPPR GQIRJ RQAQP PAGVR PQMGI APKSM BBMGQ RQURG MGQJM NBRPO NYJQR PJNHL HGIRP PRGQH NQABB RGQIR PPRNJ RGQPU RGADR SXRQI RPRQN RPPKS MDRSX PMGPG HDADD RGPRP PHGQB RPJAR NNRPK SAIHN DRGQP HSPBR POHSU NRBAQ PIRDH SPPRL NHAIR RQCSD AIRRQ JSAPP MGQPP HGQBR PDSNP IHGQR BBRPP HGQQH DERRP JHSNB RQRNG AQRBR SNPEM QAPPR SNPBR PMUMA RGQRN AVRPR QMBMU RNAQR ABPPR NURGQ RGOHN RGHEB RDRGQ OMNOR PQMSI RPPHS PIRSX KSRBR ONMJM SIVNA PMLMA QPMIR DRSNR QHSQM SLHGI IRBMU MBBRR PRQNH SURBM NAUAR NRQCH DIHGQ BRPRM SXPHG QUAPK SRSPR PRQNR DJBAR PIRLR SABBR PIRPH SNORP OMOCR RPRBB RFMAB BAQRQ URNPI RPVNH QQRPP HSQRN NMAGR PRBBR PROHS BRPAE ARGKS RBRIR DHGIR BMUMB BRRGR PMAQJ MPJHS NKSHA PRPRM SXPHG QNHSV RPGAM KSRBP BARSX RBBRP PHGQB ARRPB RVRGA RKSAC MGQRB RPNMY HGPIR BMBSG RJMNB MMSIR DHGIR BMUMB BRRIA PMGQF RPSAP UARSX RQQNR PHSEB ARSXI APDHA BRPMO QRPBM JJMNR GORRQ BRGHD IRORS XKSAH GQOHG PQNSA QORPO CHPRP IRJAR NNRRQ BRIRD HGNRJ HGIAQ FRPSA PDRDH ANRRQ FRPSA PURNP RIMGP BRPQN MIAQA HGPIS JMPPR DMAPD HAMSP PAFRP SAPUA RSXOR PRQNR PRQMA RGQOH DDRBR PRMSX IRBMN AUARN RQCHD HGGRJ HSUMA QBRPO HDJNR GINRI RBRSN PMOQR PFRGR DRPHS UARGP JMPOM NABPG RXAPQ RNRGQ KSRIM GPBAG PQMGQ IRBRS NMJJM NRGOR FRDRP HSUAR GPUMV SRDRG QRBBR RQMAQ JMNRA BBRMO RBBRI RPJRQ AQPPA GVRPI MGPBR PMNEN RPIRB RSNGH DFRDR PHSUA RGPOB MANRD RGQOM NABNA DRMUR OORBS AIRBM NAUAR NRORP RQNRP ICARN PMJJR BMARG QCHDD RMBHN PBRVR GARPR GUHBM IRGHS URMSU RNPBR DAGOR ONHAP PMGQI RBMBS GRRQB RIRDH GNRVM NIMMQ QRGQA URDRG QSGJR QAQPA GVRIM GPSGM NENRK SAJHS PPMAQ IMGPS GROHS NIRBM ENRR

Il s’agissait du court texte Mémoire écrit par H. P. Lovecraft, dans la traduction donnée par Wikisource. L’alphabet désordonné est généré à partir de la clé « MemoireLovecraft », par la méthode horizontale.

Pistes d’amélioration
Pour poser les premiers jalons d’un décryptage sur ce type de chiffrements, on peut employer la méthode des mots probables : vous faites l’hypothèse qu’un certain mot se trouve dans le texte (par exemple, « attaque », « bataillon » ou « soldats » dans un texte d’origine militaire), et vous essayez de trouver des suites de lettres dans le cryptogramme qui pourraient correspondre à ce mot. Par exemple, pour « attaque », vous chercheriez une suite de sept lettres, la première et la quatrième étant identiques, la deuxième et la troisième aussi, mais les autres étant toutes différentes. En combinant cela et l’analyse fréquentielle, on peut arriver assez vite à de bons résultats.

Il est également possible de compter combien de fois apparaît chaque combinaison de deux ou trois lettres, et de comparer là encore avec la répartition attendue en français. Cela peut lever certaines ambiguïtés. Par exemple, on a vu que C, P et M ont, prises individuellement, une fréquence d’apparition très proche. En revanche, ME est nettement plus courant que CE, lui-même nettement plus courant que PE. De même, malgré la fréquence assez faible du D, c’est lui qui a le plus de chance d’apparaître entre deux E.

(Niveau avancé) À l’aide d’un dictionnaire, vous pouvez vérifier si tel ou tel échange de lettres (ou combinaison de plusieurs échanges) donne de meilleurs résultats, en faisant apparaître des mots significatifs dans le texte décrypté.

(Niveau avancé) À l’aide d’un dictionnaire, vous pouvez tenter de trouver l’éventuelle clé à l’origine de l’alphabet désordonné, et tester si tel ou tel échange de lettres améliore les résultats de cette recherche de clé.

Étape 3 : chiffre de Vigenère

Le chiffre de Vigenère est une variante subtile du chiffre de César. On commence par choisir une clé, puis la première lettre de la clé détermine le décalage à appliquer à la première lettre du message, la deuxième lettre de la clé détermine le décalage à appliquer à la deuxième lettre du message, etc. Évidemment, quand on arrive au bout de la clé, on recommence au début de celle-ci, et ainsi de suite jusqu’à ce que le message soit entièrement chiffré.

Avec la clé VIGENERE, le texte « Pourquoi est-ce qu’un corbeau ressemble à un bureau ? » doit devenir KWAVD YFMZA ZGRUL YIKUV OIRYM MYWRQ SPZIA ROYII VC.

En effet, la première lettre de la clé (V) est la 22e de l’alphabet, et indique donc un décalage de 21 rangs pour la première lettre du message. I est la 9e lettre de l’alphabet, d’où 8 rangs de décalage pour la deuxième lettre. G est la 7e, donc 6 rangs. Etc.

Pour déchiffrer, on procède bien évidemment en sens inverse. Avec cela, vous avez toutes les informations en main pour écrire les fonctions de chiffrement et déchiffrement pour Vigenère. Vous pouvez bien sûr réutiliser la fonction du chiffre de César déjà codée, puisque le chiffre de Vigenère se sert explicitement de ce dernier.

Comment l’attaquer ?

La différence avec le chiffre de César est subtile, et pourtant, elle fait une grande différence : la méthode de l’analyse de fréquences ne fonctionne plus ! Ou plus exactement, plus toute seule. En effet, avant de pouvoir procéder à une analyse fréquentielle, il faut déterminer la longueur de la clé utilisée. Pour cela, deux méthodes existent.

La première consiste à chercher des suites de trois lettres ou plus (plus c’est long, plus c’est bon) qui apparaissent plusieurs fois dans le cryptogramme. Il y a de très fortes chances que ces lettres correspondent aux mêmes lettres du texte en clair, chiffrées par les mêmes lettres de la clé. Par conséquent, la distance (en lettres) entre la première lettre de la première occurrence et la première lettre de la seconde occurrence est très vraisemblablement un multiple de la longueur de la clé.

En relevant toutes les occurrences de suites de lettres qui apparaissent plusieurs fois, et en calculant la distance entre ces occurrences d’une même suite de lettres, on peut alors rechercher le diviseur commun à toutes ces distances : il s’agit de la longueur de la clé, avec une très forte probabilité.

La seconde méthode est plus mathématique. Elle utilise ce que l’on appelle l’indice de coïncidence des lettres du cryptogramme. Pour calculer l’indice de coïncidence, il faut compter le nombre de A que renferme le cryptogramme (qu’on appelle $n_1$), le nombre de B ($n_2$), le nombre de C ($n_3$), etc. jusqu’à Z ($n_{26}$), et on appelle $n$ le nombre total de lettres que compte le cryptogramme. L’indice de coïncidence $IC$ est alors obtenu par la formule suivante.

$$IC \ = \ \sum_{i=1}^{26} \frac{n_i(n_i-1)}{n(n-1)}$$

Dans un texte parfaitement aléatoire, cet indice de coïncidence est aux alentours de $0,038$. Pour un texte en français, en revanche, il est censé être aux alentours de $0,074$. En pratique, cependant, même avec un texte de plus de 1500 caractères, on peut encore avoir des indices assez nettement différents, comme $0,08$.

Pour obtenir la longueur de la clé par cette méthode, vous allez commencer par calculer l’indice de coïncidence de l’ensemble du cryptogramme (on va l’appeler $IC_1$). Puis vous allez diviser le cryptogramme en deux sous-textes, le premier contenant la 1re, la 3e, la 5e, etc. lettre, et le second contenant la 2e, la 4e, la 6e, etc. lettre ; vous calculez alors l’indice de coïncidence de chacun de ces sous-textes, et vous en faites la moyenne ($IC_2$). Vous répétez le procédé avec trois sous-textes, contenant chacun une lettre toutes les trois lettres, puis avec quatre sous-textes, etc.

Lorsque vous atteignez un indice de coïncidence moyen très proche de celui du français ($0,074$), vous avez trouvé la longueur de votre clé ! Du moins, ça, c’est la théorie. Comme je l’ai dit, dans la pratique, l’indice de coïncidence peut être assez éloigné de $0,074$, même avec la bonne longueur de clé. En outre, les longueurs de clé ayant un diviseur commun avec la longueur réelle (par exemple, 6 pour une longueur réelle de 8) peuvent faire de bons scores, et les diviseurs de la longueur réelle des scores encore meilleurs (par exemple, 4 pour 8).

Comment être sûr de trouver la bonne, alors ? Sauf mauvaise surprise, la bonne longueur de clé aura un indice de coïncidence supérieur à l’indice théorique, tandis que les autres « bons scores » s’en approcheront plutôt par le bas.

Une fois que vous avez déterminé la longueur de la clé, vous divisez le cryptogramme en autant de sous-textes, comme on l’a fait précédemment pour calculer l’indice de coïncidence, et vous appliquez à chacun la même méthode de décryptage que pour le chiffre de César. Finalement, une fois qu’on a la bonne longueur de clé, c’est pas si difficile ! :D

En guise d’exercice, essayez de retrouver quel message se cache derrière le cryptogramme suivant. Notez qu’au début du texte se trouve une date écrite en chiffres, qui a été supprimée, pour des raisons de commodité.
VVZCW RHSMK BJGOE UQQIL KJDLP FHGMV TCIHJ VHFMZ MVRYO AQQSG XERUO TOSMV FVGNS EGVCM XIRYD EWOCK ERIHF MDHCV KVPCF NQCOM XCZYQ OXFFV ILPFJ CHQFR BISUV QXSFE HLGHP UVOXI XJGCP NVSNH NVBIV SUSGV KTWIO SLQCU XJOMZ MSONY BVZYE EVWLU XCICG ALFYT HEBUJ TUSMF NJIHF FRFGV TTQYT SLPFV WVDIV RYIYU XCOJQ AUSCC WVFOE IWWIE JLWUD CRAJR ZESXP RGWHR BISWF SHHOU XJIHF PHFCF WVUFP RLSOJ XUSHP TUSUE VZSHO EOWNK XIONV RHSRG EZEOF LHQUI TTHYS EGSWV MFIPS AJSUL LJWSU RRIPV KRHIO POIMU TWTCS MDHCF GJEOF DHRCJ VLGMJ OQGCC XJHXF SWWHV TLULB NGDOS EZQUD EOICU NDCCO STICJ TZHMJ NWSLV LJSLF NFCLV TLLWI OVSMU NGOMT EQCHG TIQYR UHZFV LJCHU LHDUJ LVAUJ SSOLT XHIYM LHGMF GKPYM LHGYK BEHYS EVGUE MVGWF SWOFZ GKSHU IRBXV VVDOC LLQKL XECOT AYCHJ FLZNJ POWYC XJQCU AWWIE LECOT AXFCF GJRYT IUSFV LUCHO EURUE LCSNF XWSJI HMSHD AOCHR NIOCU PXOCE LZACF UAUIL MVFFF SYSLJ ZIOWJ EXLXV UVFHB RGRYM XEHUE OXFIL WVZUD OPHYJ LVRYE IHZYJ MPZYG EUAYV MVBYS GLEOV WVDYJ RHQUI WVBUM EWGOI MFINU AQHXR KKWZJ CHGXV FVHLF OXRYJ MPZYE OQHFR MIOXV CWWIE GVDYV TJOLU XIZUN OLBXI XKFUD EPOCJ VVJIM UPSYE XLHYU EGSGV LLFYN EQHAI HJGCF TGSJC NJHIV THIHV IRFNJ EGIWY TIAYE EFSNK XCOHH UHOOI TZHYD HDDJV TTSOY QXWHV ERQIO NDWMJ XEHJB SSCOI EVGUV TUSMV LGSLP NVEOL GVOHU HRZIX BVDLP VHBWR EVOPF CWFUU NTHCP NQSMV YVFUQ AVHLF ICCHH THAJJ TKHYO DUSIE MICOW EUOXR BCZYV RVRYJ KVBPP IVOOO MVLNF SGOHJ EVGHP THGKL BRQWP MSOAE XEHFF VRZOD XTSNU EGSLE BVFYQ AUHCV WVBIU RHHLR ORWFD OPDLV GURYT NRHYJ UZPFJ OJFUG AZEOF SHHXV LRRXJ TLCHJ GFIMB VRBMM HLZOF TUSOK BCSUD EXLKL BJWHU EUSMJ XEHUM ASCYJ BVRYT TUCOS TUCOS SHBFV NIRIO NDBNE HEDUT UQSVZ UCWIH RDDBZ XTCGQ LHHYD TZGXF SLAJC XJBIU EVEOZ EVILQ EUAYK MICHU DHHOU BVFJM UVOZF GUZYT SXXYK LHIYO OXGNI TZHIO SQCOJ LRJIO SOSMJ XIJCD EVEOV IVINS EQRLV NEUOJ DHRYT XXSHS EPSGV KVROJ TDRYD HUSMU EVDLF IFFNJ OQGIE OFIXS AEWYE GVDUT CKSLT AVFXB NVQYC BMFYD ETIYE HLGHB VRBMG TJJIV LXMGV MKFYV NHVCJ MFWLF CRAJC XKSXF LDBWZ XEBYM IWHYI TKILF PUCPV GTOFF NRIMR OFBMW OXZOJ BDDFF MHBNV VIWLF LKWMK HZFYE EOOJF XJWYE EVHLF NSOXP UUGYE GFIMF NWSHR GKOOY POIMX KRBXT NRAMV GTVIJ SLGMR GKZYT POIMZ GKSLF SVOHK LFIFF SSZOJ VRFUD THFCJ MZEOF SGIHV IVFCP DHWFE RJSLB DRBWH NVGNJ OQBCU XXOOD EOAZR BUWNO IGSJV BICFO IGSZF EHIYU DHFID TEGHJ DHHUE MUOOU RHGKL BDSLJ THFUZ XEHFI OQBYL KUSNS EQCGD XJDIV RWCOJ VVIRM ARBNI HLJYS AGSMI XEGYJ GQSGV GKGXB NVZYC BMFYU OXXIL KJDLF CLSOO WVRCF ZYWYJ XKCYV VUSMU XJHLP UEOXF NIGCM NHLCJ MVAUM HHILV NJSGF NWRYK KRROD TLCHW KRBWB IVSKL XUSFB PUSGZ XISYE IWWIE JLWYT TYWYZ ECWYO OXGFR OFBMD OQGNR FDSHU CRBML EKSJP UUIHV IRFNJ EGSHF MISNS AYOCC EFIPS AJSXV YRILJ EORIE MCOJM UVULR GUSJB RWWYV LKRUJ LOSOI LVFLP NHSHF NJOYU EPCCE LLHCM EFSFZ OISLF PRBXR BKWFB UQPYJ HZBCM NRIMC TJSGC LHWFE HLGUT EPPFV JLWFF TDWNK XDDME EIOCI XJCLU IUZUG HVGCF DHGNI HLPUE OXFMU XJBYD RRDIC XJGWJ EQHCW BHIYT QXSMF GKHLP PVCOM XEHHP SUSPL XJBIT CRZFV VKWIO SHHHF LUWMT EUHUK BFBMQ OXFFR IICXV IUSUL ZIOHE JRILC XKIXF DHGNI HLPUE OXFMR IICZJ THROU XMSFP PSSGV GKRYT EWIXV LICGB NHGJC NJWYV RVSXZ MZCHT OQHJR KLRUV TUSMJ HEHYO PUSJR KRHCP NFSLK TZBYT PDFNZ XJRYM HLGNF BISFJ TWSLR BISIO THHYK KRWNF EVOZF GUQYT OQHFV LISMV LWONJ WVQYT DLJYI LKFUW AXLKL XECOT AYCHJ OFIFV RHGOD XIOJS EVHIL MCSMU RRIVR WFILT NRBNG TJSWS IWDIL KHIYM EXFML OISME EYWYE GVBNE EVGOA XKGXF TKSMV LUSXP CWCLR MFIXF DLGWL LJWIO SDQUU XDWKV EVWFJ HEHYD RLHJF NIZYQ UEZCT IFILV NJFUE WGIVM IFCOC XJTYN MHGXZ GKSFM IJSHT XVHXF CXFZF KDOCF NWZUD TACLJ THSNF NISAO ALHFV VLZNF DHZUG HVGCF MDZAI XCOXJ FISLV GTSXF SWSGG LVHXF SPILJ VVDOC LLQHV WFWNQ AVOPF BIQIN POSNV FVBNE IVDUI NUIGP IQGHF NJBYM EFFIP HEGJB SHBNF NKQUT NRIME HLGWP MSOLV KZCHT VRZIE MZSLT AXBUU OVFMB IUSXL MICVB RFZOJ HEJYS RDDFL LCCCO QXSWV LDCNT DHGCX GVBNV NHAUE BVFYE EFFCI XHICD OQGCJ MVOXF RRINV KCSMQ RRTUE XJSNB RHGYI OVFFB PRSMZ XRIRT EXZMZ GZHCF SDEOF BLBAS AQRNI HLPUE OXFAZ KRINE EECLE XCVLF PRBXZ MLBDP UUDUI ERRYD LDFUK BFBMV IYOHK XHICT EUHXV WVPOU AXBYU XJSMD HDBMF GJXYG EUOCJ LZXUW ALGUJ LVNXF TDZYE MLBYD HDBMF GESNU EDGMV STZUJ RHDIL KHIYN OQDYK BKTCM SOOWF FGFCU CHGNC TGSHT EHEOZ GFIMB SRIPV GKUOJ DHRUE LCOLF DDQNZ HERYD EWFUM TZZHP UVZUL KZCHT VRIFL TJGYA COOCI XKOMT ECGCD ICSJP UUEOZ EWINB LDDII MVSXF TRINC XDCHE EBOPF GJBIV SUSOJ LZBIV SDJCF GJZCO THBNZ HERYE EGWYI VVJIM UPSUE HKFYW IHIRD TZHLF CDACC EVQBB BDBYR NECOT NHDIL OFBMM EGSXZ XIOOK OXFXY NZEOB SDAYD HZFYW EQSLV X

Il s’agissait de l’avant-propos de l’ouvrage Les Troubadours, leurs vies, leurs œuvres, leur influence de Joseph Anglade et la clé utilisée était TROUBADOUR.

Pistes d’amélioration
Il est possible d’améliorer légèrement le choix du décalage à opérer pour décrypter un (sous-)texte utilisant le chiffre de César. Plutôt que de se fonder uniquement sur la fréquence maximale et d’en déduire qu’il s’agit d’un E, vous pouvez calculer la somme des écarts entre la fréquence qu’aurait chaque lettre dans le texte décrypté pour un décalage donné, et la fréquence attendue en français : le décalage ayant le plus faible écart cumulé sera certainement le décalage voulu.

(Niveau avancé) À l’aide d’un dictionnaire, vous pouvez vérifier si la clé obtenue après l’analyse fréquentielle de tous les sous-textes est un mot ayant du sens : si c’est le cas, il s’agit très certainement de la bonne clé.

(Niveau expert) Que faire si la clé fait la longueur du texte, ou a minima une longueur telle qu’il n’est pas possible de faire une analyse fréquentielle sur les sous-textes ? Cette question restera ouverte, à vous de proposer d’éventuelles solutions. Il est bien entendu que ce point est du pur bonus, et que le défi sera considéré comme réussi à 100 % même si vous n’y répondez pas.

En guise de conclusion

Améliorer encore un peu plus ?
Et si votre programme était capable de décider par lui-même lequel de ces trois systèmes de chiffrement a été utilisé ? Le chiffre de Vigenère est facile à isoler : l’indice de coïncidence du texte complet sera très mauvais. Pour ce qui est de distinguer efficacement une substitution simple d’un chiffre de César, je vous laisse trouver la solution par vous-mêmes…

Voilà, c’est tout pour ce défi. Comme vous le voyez, il y a plein de petites étapes, que vous pouvez réaliser séparément : par exemple, rien ne vous oblige à coder les fonctions de chiffrement / déchiffrement pour coder les fonctions de décryptage, et vice-versa.

J’ai donné quelques exemples pour tester vos fonctions de décryptage. Je vous invite chaleureusement à proposer vos propres cryptogrammes sur lesquels les autres pourront plancher. Et maintenant, amusez-vous bien !

Candidat Langage Étendue
Emeric Perl 6 Chiffrement et déchiffrement César
Folaefolc Python Étape 0, décryptage César
Garfield Python Étape 0
Ge0 Python 2 Décryptage Vigenère
LudoBike C++ Décryptage César
Matouche Python 3 Décryptage César
SpaceFox Java Décryptage Vigenère
Taurre C Étape 0, chiffrement César
yoch Python Décryptage substitution simple

  1. Petit point vocabulaire : on parle de déchiffrer un message quand on sait comment procéder, et qu’on connaît la clé, mais de décrypter quand le message ne nous est pas destiné et qu’on essaye de le lire quand même. 

Édité par Dominus Carnufex

#JeSuisGrimur #OnVautMieuxQueÇa

+14 -2

Désolé, je sais que c'est pas le but de celui qui joue à Prem's, mais j'avais déjà fait ce genre de truc y a quelques années et je m'étais éclaté.

@nohar si jamais tu passes par là… Pas taper stp. :D

Python 2 :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#!/usr/bin/python
# -*- coding: utf-8 -*-
import math
import sys
import urllib2

def get_probable_key(cipher, key_len):
    i = 0
    vigenere_key = ''
    while i < key_len:
        subcipher = sub_string(cipher, i, key_len)
        vigenere_key += frequency_cryptanalysis(subcipher)
        i += 1
    return vigenere_key


def vigenere_uncipher(ciphered, key):
    out_string = ''
    if ciphered != '' and key != '':
        a = ord('a')
        z = ord('z')
        A = ord('A')
        Z = ord('Z')

        ord_key = []
        i = 0
        len_key = len(key)
        while i < len_key:
            ord_key.append(ord(key[i]) - A)
            i += 1

        i = 0
        l = len(ciphered)

        j = 0
        while i < l:
            ch_cipher = ord(ciphered[i])
            if ch_cipher >= a and ch_cipher <= z:  # lowercase
                ch_cipher -= ord_key[j % len_key]
                if ch_cipher < a:
                    ch_cipher += 26
                j += 1
            elif ch_cipher >= A and ch_cipher <= Z: # uppercase
                ch_cipher -= ord_key[j % len_key]
                if ch_cipher < A:
                    ch_cipher += 26
                j += 1
            out_string += chr(ch_cipher)

            i += 1

    return out_string


def get_probable_key_length(cipher):
    french_ic = 0.074
    min_diff = 1
    gap = 0.01
    key_len = 2

    keys_lengthes = []

    number_of_acceptable_ic = 0
    max_number_of_acceptable_ic = 0
    i = 2
    while i <= 10:
        ics = coincident_index_with_step(cipher, i)
        number_of_acceptable_ic = 0
        for ic in ics:
            if math.fabs(float(ic) - french_ic) < gap:
                number_of_acceptable_ic += 1

        if math.fabs(float(ic) - french_ic) < gap:
            max_number_of_acceptable_ic = number_of_acceptable_ic
            key_len = i

            addit = 1

            if addit:
                keys_lengthes.append(key_len)
                key_len = i

        i += 1
    return key_len


def coincident_index(cipher):
    tot_ic = 0.0

    ch = ord('A')
    i = 0
    n = len(cipher)
    while i < 26:
        ni = cipher.count(chr(ch))
        ic = float(ni * (ni - 1)) / (n * (n - 1))
        tot_ic += ic

        i += 1
        ch += 1
    return tot_ic


def coincident_index_count(
    cipher,
    letter,
    start,
    step,
    ):
    c = 0
    d = 0
    i = start
    l = len(cipher)

    while i < l:
        if cipher[i] == letter:
            c += 1
        d += 1
        i += step
    return (c, d)


def frequency_cryptanalysis(cipher):
    occs = {}
    i = 0
    l = len(cipher)
    while i < l:
        if occs.has_key(cipher[i]):
            occs[cipher[i]] += 1
        else:
            occs[cipher[i]] = 1
        i += 1
    letter = ''
    max = -1
    for key in occs.keys():
        if occs[key] > max:
            max = occs[key]
            letter = key

    E = ord('E')
    ciphered_letter = ord(letter)

    diff = ciphered_letter - E
    if diff < 0:
        diff += 26
    return chr(ord('A') + diff)


def sub_string(cipher, start, step):
    out = ''
    i = start
    l = len(cipher)
    while i < l:
        out += cipher[i]
        i += step
    return out


def coincident_index_with_step(cipher, step):
    indexes = []
    start = 0
    while start < step:

        ch = ord('A')
        i = 0
        tot_ic = 0.0
        while i < 26:
            (ni, n) = coincident_index_count(cipher, chr(ch), start,
                    step)
            if n != 0 and n - 1 != 0:
                ic = float(ni * (ni - 1)) / (n * (n - 1))
                tot_ic += ic

            i += 1
            ch += 1
        indexes.append(tot_ic)
        start += 1
    return indexes


def avg(l):
    sum = 0
    for i in l:
        sum += i
    return sum / len(l)


cipher = 'YOUR CIPHER'  # TODO: Fill this var with relevant data
cipher_tmp = cipher.replace(' ', '')
key_len = get_probable_key_length(cipher_tmp)
probable_key = get_probable_key(cipher_tmp, key_len)
txt_plain = vigenere_uncipher(cipher, probable_key)
print txt_plain

Édité par Ge0

+1 -0
Staff

@nohar si jamais tu passes par là… Pas taper stp. :D

1
2
3
4
         This is Bill.
 o       Bill respects the PEP-08 and doesn't name his variables 'l'.
/|\      Bill is smart.
/ \      Be like Bill.

Édité par nohar

I was a llama before it was cool

+24 -0

Pour ceux que ça intéresse, j'ai lu Histoire des codes secrets de Simon Singh il y a quelques années, j'ai beaucoup aimé. Je recommande chaudement, d'autant plus que l'ouvrage présente d'autres chiffrements comme Enigma, ADFGVX, RSA, l'échange de clés Diffie-Hellman…

+2 -0

@nohar si jamais tu passes par là… Pas taper stp. :D

1
2
3
4
         This is Bill.
 o       Bill respects the PEP-08 and doesn't name his variables 'l'.
/|\      Bill is smart.
/ \      Be like Bill.

nohar

C'était pas très relevant comme intervention, même si ça fait sens. :)

Image utilisateur

+2 -0
Staff

Déchiffrement de Vigenère (donc de César)

Un petit test en Java, qui déchiffre du Vigenère (donc du César) :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
package info.kisai.vigenere;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Locale;
import java.util.Map;

/**
 * Déchiffrement d'un code de Vigenère. Code sous WTFPL - http://www.wtfpl.net
 * Created by spacefox on 01/02/16.
 */
public class Vigenere {

    private static final char[] ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
    private static final int ALPHABET_SIZE = ALPHABET.length;
    private static final char MOST_FREQUENT_LETTER = 'E';

    // Je suppose que l'index de coïncidence va dépasser cette valeur. Si non, le cas n'est pas géré…
    private static final double INDEX_THRESHOLD = 0.070;


    public String unCypher(String in) {
        String cleanIn = in.replace(" ", "").toUpperCase(Locale.FRANCE);

        int step = 0;
        List<String> subCyphers;    // On garde la liste des sous-chaînes, elle re-sert ensuite
        do {
            step++;
            subCyphers = splitCypher(cleanIn, step);
        } while (computeMeanIndexOfCoincidence(subCyphers) < INDEX_THRESHOLD);

        List<String> subUnCyphered = new ArrayList<>(step);
        for (String subCypher : subCyphers) {
            Character mostFrequent = mostFrequent(computeFrequencies(subCypher));
            Character keyLetter = toLetter(mostFrequent - MOST_FREQUENT_LETTER);
            subUnCyphered.add(unCaesar(subCypher, keyLetter));
        }

        return concatenate(subUnCyphered, cleanIn.length());
    }

    private List<String> splitCypher(String cleanIn, final int step) {
        List<String> subCyphers = new ArrayList<String>(step) {{
            for (int i = 0; i < step; i++) {
                add("");
            }
        }};
        for (int i = 0; i < cleanIn.length(); i++) {
            subCyphers.set(i % step, subCyphers.get(i % step) + cleanIn.charAt(i));
        }
        return subCyphers;
    }

    private float computeMeanIndexOfCoincidence(List<String> subCyphers) {
        float sumIndexes = 0;
        for (String subCypher : subCyphers) {
            sumIndexes += computeIndexOfCoincidence(subCypher);
        }
        return sumIndexes / subCyphers.size();
    }

    private float computeIndexOfCoincidence(String s) {
        final Map<Character, Float> frequencies = computeFrequencies(s);
        float ic = 0;
        float n = s.length();
        for (Float nq : frequencies.values()) {
            ic += (nq * (nq - 1)) / (n * (n - 1));
        }
        return ic;
    }

    private Map<Character, Float> computeFrequencies(String s) {
        final Map<Character, Float> frequencies = new HashMap<Character, Float>() {{
            for (char c = 'A'; c <= 'Z'; c++) {
                put(c, 0f);
            }
        }};
        for (char c : s.toCharArray()) {
            if ('A' <= c && c <= 'Z') {
                frequencies.put(c, frequencies.get(c) + 1);
            }
        }
        return frequencies;
    }

    private Character mostFrequent(Map<Character, Float> frequencies) {
        float maxFrequency = Float.MIN_VALUE;
        Character out = null;
        for (Map.Entry<Character, Float> entry : frequencies.entrySet()) {
            if (entry.getValue() > maxFrequency) {
                out = entry.getKey();
                maxFrequency = entry.getValue();
            }
        }
        return out;
    }

    private Character toLetter(int i) {
        return ALPHABET[i % ALPHABET_SIZE];
    }

    private String unCaesar(String subCypher, Character key) {
        StringBuilder sb = new StringBuilder();
        for (char c : subCypher.toCharArray()) {
            // On ajoute ALPHABET_SIZE pour éviter de se prendre le chou avec les nombres négatifs
            sb.append(toLetter(c - key + ALPHABET_SIZE));
        }
        return sb.toString();
    }

    private String concatenate(List<String> subUnCyphered, int length) {
        char[] out = new char[length];
        int steps = subUnCyphered.size();
        for (int step = 0; step < steps; step++) {
            char[] chars = subUnCyphered.get(step).toCharArray();
            for (int i = 0; i < chars.length; i++) {
                out[i * steps + step] = chars[i];
            }
        }
        return new String(out);
    }
}

Bon, que peut-on en dire :

  1. Il n'y a aucun contrôle d'entrée : on donne de la merde au programme, il plante. En même temps, j'ai grave la flemme de m'occuper de ça.
  2. La combine avec le seuil de l'index de coïncidence fonctionne, elle permet de trouver des clés arbitrairement longues, mais :
    • S'il est trop bas, le programme peut s'arrêter sur une mauvaise clé.
    • S'il est trop haut, le programme ne trouvera jamais la clé.
    • Une solution serait de limiter la boucle à une longueur « raisonnable » (quelques pourcents de la longueur du message) et de prendre la valeur d'index de coïncidence la plus élevée.
    • Une autre solution serait sans doute de calculer toutes longueurs, et de tenter la plus proche de la fréquence théorique. Sur un texte de cette longueur, ce programme fait ça en moins de 2 secondes.
    • On pourrait aussi prendre plusieurs valeurs crédibles et faire des essais avec un dictionnaire.
  3. C'est clairement pas optimisé, que ce soit en temps CPU, en mémoire ou en lisibilité. Mais ça fait le job dans un temps raisonnable (instantané sur l'exemple), donc bon…
  4. Le programme ne donne pas la clé de décodage. Parce qu'on s'en fout en fait, on en a jamais besoin. On peut la récupérer en concaténant les différentes keyLetter ligne 36.

Quant au reste je n'ai pas testé les cas aux limites, mais ça devrait faire le boulot, modulo les points ci-dessus.

Je pense que le code reste clair, s'il ne l'est pas, n'hésitez pas à poser des questions !

La question niveau expert

En fait c'est une question piège. En considérant qu'on a une clé de la longueur du texte :

  1. La clé n'est jamais réutilisée (un seul message chiffré avec cette clé). On se retrouve dans le cas du chiffre de Vernam, aussi appelé « Masque jetable », et qui est mathématiquement sûr… tant qu'on arrive à respecter les moult conditions d'utilisations.
  2. Soit on a plusieurs messages chiffrés par la même clé. On a alors diverses solutions pour retrouver la clé et donc le message d'origine, détaillées dans les articles ci-dessus.

PS : je note que mon code est plus court que celui en Python proposé ci-dessus :-°

Édité par SpaceFox

Pour l'étape 2 (substitution simple), voici une solution inspirée par ce papier.

La méthode s'apparente à un recuit simulé, les solutions ne sont donc pas forcément les mêmes à chaque fois, et le texte décrypté n'est généralement pas parfait (mais il est possible de finir manuellement).

Mon code (j'ai pris "les misérables" comme corpus d'apprentissage) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import random
from string import ascii_uppercase as charset
from collections import defaultdict, Counter
from math import fsum, log, exp
import unicodedata


msg = "IMGPB MUMBB RRIRG APBMB SGRIR ONHAP PMGQR RQDMS IAQRB SAQLM AEBRD RGQQM ABBMG QIRPR PJHAG QRPUM OABBM GQRPS GJMPP MVRMP MBSDA RNRMQ NMURN PBRLR SABBM VRDHN QRBIS GVNMG ISJMP IMGPB RPJNH LHGIR SNPIR BMUMB BRRHS BMBSD ARNRG RJMNU ARGQJ MPPRD RSURG QIRPL HNDRP KSAGR PHGQJ MPIRP QAGRR PMRQN RUSRP LHAPH GGMGQ RBMUR VRQMQ AHGNR OHSUN ROCMK SRURN PMGQH SBMUA VGRUA RNVRD MBRLA KSRRQ BRPJB MGQRP VNADJ MGQRP NMDJR GQJMN DABRP JARNN RPIRP JMBMA PRGNS AGRPR GBMOM GQRQN HAQRD RGQIR POHBH GGRPE NAPRR PRQIR QNMGV RPDHG HBAQC RPPHS BRUMG QBRPI MBBRP IRDMN ENRJH PRRPJ MNIRP DMAGP HSEBA RRPRQ IMGPB RPMNE NRPKS AJHSP PRGQV AVMGQ RPKSR PIMGP IRPOH SNPIR BMENR RPEHG IAPPR GQIRJ RQAQP PAGVR PQMGI APKSM BBMGQ RQURG MGQJM NBRPO NYJQR PJNHL HGIRP PRGQH NQABB RGQIR PPRNJ RGQPU RGADR SXRQI RPRQN RPPKS MDRSX PMGPG HDADD RGPRP PHGQB RPJAR NNRPK SAIHN DRGQP HSPBR POHSU NRBAQ PIRDH SPPRL NHAIR RQCSD AIRRQ JSAPP MGQPP HGQBR PDSNP IHGQR BBRPP HGQQH DERRP JHSNB RQRNG AQRBR SNPEM QAPPR SNPBR PMUMA RGQRN AVRPR QMBMU RNAQR ABPPR NURGQ RGOHN RGHEB RDRGQ OMNOR PQMSI RPPHS PIRSX KSRBR ONMJM SIVNA PMLMA QPMIR DRSNR QHSQM SLHGI IRBMU MBBRR PRQNH SURBM NAUAR NRQCH DIHGQ BRPRM SXPHG QUAPK SRSPR PRQNR DJBAR PIRLR SABBR PIRPH SNORP OMOCR RPRBB RFMAB BAQRQ URNPI RPVNH QQRPP HSQRN NMAGR PRBBR PROHS BRPAE ARGKS RBRIR DHGIR BMUMB BRRGR PMAQJ MPJHS NKSHA PRPRM SXPHG QNHSV RPGAM KSRBP BARSX RBBRP PHGQB ARRPB RVRGA RKSAC MGQRB RPNMY HGPIR BMBSG RJMNB MMSIR DHGIR BMUMB BRRIA PMGQF RPSAP UARSX RQQNR PHSEB ARSXI APDHA BRPMO QRPBM JJMNR GORRQ BRGHD IRORS XKSAH GQOHG PQNSA QORPO CHPRP IRJAR NNRRQ BRIRD HGNRJ HGIAQ FRPSA PDRDH ANRRQ FRPSA PURNP RIMGP BRPQN MIAQA HGPIS JMPPR DMAPD HAMSP PAFRP SAPUA RSXOR PRQNR PRQMA RGQOH DDRBR PRMSX IRBMN AUARN RQCHD HGGRJ HSUMA QBRPO HDJNR GINRI RBRSN PMOQR PFRGR DRPHS UARGP JMPOM NABPG RXAPQ RNRGQ KSRIM GPBAG PQMGQ IRBRS NMJJM NRGOR FRDRP HSUAR GPUMV SRDRG QRBBR RQMAQ JMNRA BBRMO RBBRI RPJRQ AQPPA GVRPI MGPBR PMNEN RPIRB RSNGH DFRDR PHSUA RGPOB MANRD RGQOM NABNA DRMUR OORBS AIRBM NAUAR NRORP RQNRP ICARN PMJJR BMARG QCHDD RMBHN PBRVR GARPR GUHBM IRGHS URMSU RNPBR DAGOR ONHAP PMGQI RBMBS GRRQB RIRDH GNRVM NIMMQ QRGQA URDRG QSGJR QAQPA GVRIM GPSGM NENRK SAJHS PPMAQ IMGPS GROHS NIRBM ENRR"
s = msg.replace(' ', '')

with open('les-miserables', 'r', encoding='utf8') as fp:
    txt = fp.read()

txt = unicodedata.normalize('NFKD', txt).upper()
#.encode('ASCII', 'ignore').decode()

counter = Counter((txt[i], txt[i+1]) for i in range(len(txt) - 1))
counter = {(a,b): v for (a, b), v in counter.items() if a in charset and b in charset}

X = defaultdict(dict)
for (a,b), v in counter.items():
    X[a][b] = v

M = defaultdict(lambda: 1e-8)
for a, d in X.items():
    total = sum(d.values())
    for b, v in d.items():
        M[a,b] = float(v) / total

def make_code():
    cipher = list(charset)
    random.shuffle(cipher)
    return dict(zip(charset, cipher))

def decode(s, code):
    return ''.join(code.get(c, c) for c in s)

def plausibility(f, s):
    s2 = decode(s, f)
    return fsum(log(M[s2[i], s2[i+1]]) for i in range(len(s2)-1))

def transform(f):
    _f = f.copy()
    (k1, v1), (k2, v2) = random.sample(_f.items(), 2)
    _f[k1] = v2
    _f[k2] = v1
    return _f


if __name__ == '__main__':
    f = make_code()
    pl = plausibility(f, s)
    i = 0
    while True:
        _f = transform(f)
        _pl = plausibility(_f, s)
        if _pl > pl or random.random() < exp(_pl - pl):
            f, pl = _f, _pl
        if i % 250 == 0:
            print(pl, _pl)
            print(i, decode(s, f))
            inp = input('continuer ?')
            if inp and inp[0].upper() != 'Y':
                break
        i += 1

Le texte décrypté :

Édité par yoch

+0 -0

Yop' !

Je viens de faire la partie 0 et la partie 1 (qui était assez simple au premier abord, mais une fois dans le code je me suis rendu compte que c'était pas vraiment a piece of cake xD)

Voici ma sortie :

1
2
3
4
5
6
7
$ je suis un message extremement crypte et tape a la main alors j n ai pas pu mettre d accents  ni de signes de ponctuation merci de le prendre en compte  inserer smiler souriant ici
JESUI SUNME SSAGE EXTRE MEMEN TCRYP TEETT APEAL AMAIN ALORS JNAIP ASPUM ETTRE DACCE NTSNI DESIG NESDE PONCT UATIO NMERC IDELE PREND REENC OMPTE INSER ERSMI LERSO URIAN TICI
- - - - - - - - - -
BWKMA KMFEW KKSYW WPLJW EWEWF LUJQH LWWLL SHWSD SESAF SDGJK BFSAH SKHME WLLJW VSUUW FLKFA VWKAY FWKVW HGFUL MSLAG FEWJU AVWDW HJWFV JWWFU GEHLW AFKWJ WJKEA DWJKG MJASF LAUA
TOCES CEXWO CCKQO OHDBO WOWOX DMBIZ DOODD KZOKV KWKSX KVYBC TXKSZ KCZEW ODDBO NKMMO XDCXS NOCSQ XOCNO ZYXMD EKDSY XWOBM SNOVO ZBOXN BOOXM YWZDO SXCOB OBCWS VOBCY EBSKX DSMS
JESUI SUNME SSAGE EXTRE MEMEN TCRYP TEETT APEAL AMAIN ALORS JNAIP ASPUM ETTRE DACCE NTSNI DESIG NESDE PONCT UATIO NMERC IDELE PREND REENC OMPTE INSER ERSMI LERSO URIAN TICI
QLZBP ZBUTL ZZHNL LEAYL TLTLU AJYFW ALLAA HWLHS HTHPU HSVYZ QUHPW HZWBT LAAYL KHJJL UAZUP KLZPN ULZKL WVUJA BHAPV UTLYJ PKLSL WYLUK YLLUJ VTWAL PUZLY LYZTP SLYZV BYPHU APJP

Et mon code :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import string


#exo 1
def split_in_five(text: str) -> str:
    text = ''.join(_.upper() for _ in text if _.upper() in string.ascii_uppercase)
    text = ''.join(text[_] if _ % 5 or not _ else " {}".format(text[_]) for _ in range(len(text)))
    return text

#exo 2
def find_the_right_cesar_cippher(text: str) -> list:
    head, tail = ord('A'), ord('Z')
    possibilities = [[chr((ord(c) + _) % 26 + head) for c in text if c != " "] for _ in range(1, 26)]
    percentages_per_possibility = {}

    for possibility in possibilities:
        length = len(possibility)
        letters = {}
        for char in possibility:
            letters[char] = 1 if char not in letters.keys() else letters[char] + 1
        percentages = {letter: count / length for letter, count in letters.items()}
        percentages_per_possibility[''.join(possibility)] = percentages

    true_possibilities = {}
    percentages_per_letter = {
        'E': (0.1695, 0.1745),
        'A': (0.0815, 0.0865),
        'S': (0.0815, 0.0865)
    }

    for possibility, percentages in percentages_per_possibility.items():
        true_possibilities[possibility] = {}
        for letter, probability in percentages_per_letter.items():
            if letter in percentages.keys():
                if probability[0] <= percentages[letter] <= probability[1]:
                    true_possibilities[possibility][letter] = True
                else:
                    true_possibilities[possibility][letter] = False

    return_values = []
    for possibility, letters_percents in true_possibilities.items():
        if len(percentages_per_letter) - 1 <= len(letters_percents) <= len(percentages_per_letter):
            okey = False
            for letter, boolean in letters_percents.items():
                if boolean:
                    okey = True
            if okey:
                return_values.append(split_in_five(possibility))
    
    return return_values


if __name__ == '__main__':
    text = input("$ ")
    print(split_in_five(text))
    print("- " * 10)
    print("\n".join(find_the_right_cesar_cippher(split_in_five(text))))

Edit : je me rend compte d'un truc assez intéressant pour tromper les algorithmes de déchiffrement automatique : les sorties que j'obtiens contiennent certes la bonne phrase, mais en propose d'autres avec A, E et S dans les "bonnes proportions". je me demande ce que ça ferait si on balançait un texte dans les bonnes proportions comme ceux ci dans un algo de déchiffrement (ce qui afficherait sûrement seulement la "phrase" de début)

Édité par Cithoran

Ma chaine YouTube ! | Seventh, un micro langage communautaire ! | Mon projet : Unamed (en pleine reprogrammation en C++11/SFML2.4) | Mon tuto sur Pygame !

+0 -0
Staff

Salut,

Une petite version en C pour l'étape 1.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <locale.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <wchar.h>
#include <wctype.h>

#define NORM_KEEP_SPACE   1
#define NORM_LOWER    2

static void chomp(wchar_t *);
static void ws_replace_special(wchar_t *);
static int cesar(char *, unsigned);
static char *normalize(wchar_t *, int, unsigned);


static void
chomp(wchar_t *ws)
{
  while (*ws != L'\n' && *ws != L'\0')
      ++ws;

  *ws = L'\0';
}


static void
ws_replace_special(wchar_t *ws)
{
  size_t i;

  for (i = 0; ws[i] != L'\0'; ++i) {
      switch (ws[i]) {
      case L'à':
      case L'â':
      case L'À':
          ws[i] = 'a';
          break;
      case L'é':
      case L'ê':
      case L'è':
      case L'ë':
      case L'É':
      case L'Ê':
      case L'È':
          ws[i] = 'e';
          break;
      case L'î':
      case L'ï':
          ws[i] = 'i';
          break;
      case L'ô':
          ws[i] = 'o';
          break;
      case L'û':
      case L'ù':
          ws[i] = 'u';
          break;
      case L'ç':
      case L'Ç':
          ws[i] = 'c';
          break;
      default:
          if (iswpunct(ws[i]))
              ws[i] = L' ';
          break;
      }
  }
}


static int
cesar(char *s, unsigned n)
{
  static char lo[] = "abcdefghijklmnopqrstuvwxyz";
  static char up[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  char *ch;

  assert(s != NULL);

  if (islower(*s))
      ch = lo;
  else
      ch = up;

  for (; *s != '\0'; ++s) {
      char *t;

      if (*s == ' ')
          continue;

      t = strchr(ch, *s);

      if (t == NULL) {
          fprintf(stderr, "Mauvais format d'entrée (%c)\n", *s);
          return -1;
      }

      *s = ch[((unsigned)(t - ch) + n) % sizeof lo];
  }

  return 0;
}


static char *
normalize(wchar_t *ws, int mode, unsigned word_size)
{
  char *ret;
  char *dst;
  wchar_t *src;
  size_t len;
  size_t i;

  assert(ws != NULL);
  ws_replace_special(ws);
  len = wcslen(ws);

  if (!(mode & NORM_KEEP_SPACE)) {
      assert(word_size != 0);
      ret = malloc(len + (len / word_size + 1) + 1);
  } else
      ret = malloc(len + 1);

  if (ret == NULL) {
      fprintf(stderr, "malloc: %s\n", strerror(errno));
      return NULL;
  }

  dst = ret;
  src = ws;
  i = 0;

  while (*src != L'\0') {
      if (mode & NORM_KEEP_SPACE) {
          if (*src == L' ' && *(src + 1) == L' ') {
              ++src;
              continue;
          }
      } else if (*src == L' ') {
          ++src;
          continue;
      } else if (i == word_size) {
          *dst++ = ' ';
          i = 0;
          continue;
      }

      if (mode & NORM_LOWER)
          *dst++ = tolower(*src++);
      else
          *dst++ = toupper(*src++);

      ++i;    
  }

  *dst = '\0';
  return ret;
}


int
main(void)
{
  char *s;
  wchar_t ws[255];
  unsigned n;
  int ret = EXIT_FAILURE;

  setlocale(LC_CTYPE, "");

  wprintf(L"Veuillez entrer une phrase à chiffrer : ");
  fflush(stdin);

  if (fgetws(ws, 255, stdin) == NULL) {
      fprintf(stderr, "fgetws: %s\n", strerror(errno));
      goto end;
  }

  chomp(ws);
  s = normalize(ws, 0, 5);

  if (s == NULL) {
      fprintf(stderr, "Impossible de normaliser le texte\n");
      goto end;
  }

  wprintf(L"Veuillez entrer le décalage à appliquer : ");
  fflush(stdin);

  if (wscanf(L"%u", &n) != 1) {
      fprintf(stderr, "Veuillez entrer un nombre\n");
      goto free_s;
  }

  if (cesar(s, n) != 0) {
      fprintf(stderr, "Impossible de chiffrer la phrase entrée\n");
      goto free_s;
  }

  wprintf(L"%s\n", s);
  ret = EXIT_SUCCESS;
free_s:
  free(s);
end:
  return ret;
}

+0 -0

Bon je me suis un peu amusé aujourd'hui à faire l'étape 0 et 1.

Pas de difficulté particulière pour l'étape 0 (que j'ai fait plus sérieusement que les autres à ce que je vois, j'aime perdre mon temps…)

Du coup j'ai fait tout un bidule avec un découpage en plusieurs classes, possibilité de charger un fichier de de phrases à crypter, gestion d'un fichier de langue pour l'affichage etc etc… je me suis senti un peu tout con en voyant que tout le monde s'était concentré sur la partie algo. Déformation professionnel je pense. Je vais donc pas le copier coller ici, il est un peu trop long.

Ensuite pour déchiffrer un code crypté en césar, j'ai fait une analyse de fréquence par lettre et une analyse de fréquence par digrammes (j'ai récupéré les fréquences ici : wiki : analyse fréquentielle

Pour chaque décalage du message d'origine, je génère les tableaux de fréquence de lettre et de digramme, et à la fin je calcule le classement pour chaque analyse. Le gagnant sera le décalage dont la somme des classements est la plus faible. Pour mon algo, je dois forcer un pré-traitement du texte :

  • suppression des espace et des caractères spéciaux

  • tout en minuscule

Sinon ça fonctionne pas :)

Pour mon programme je propose un traitement à la main (on donne le texte à décrypter et on choisit le paramétrage de pré-traitement), ce qui, pour l'exemple du sujet, donne la sortie console suivante:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|----------------------------------------|
|------------CHOIX D'EXECUTION-----------|
|----------------------------------------|
- A la main : 0
- Automatique : 1
0
|----------------------------------------|
|---------EXECUTION MANUELLE-------------|
|----------------------------------------|
Entrer la phrase à déchiffrer :
SYKMA OTTGB GOZPG SGOYK AJKHU TNKAX GBKIY KYINB XKYOR RKYVK XJGOZ ZUAZK YJKRG SS
KLG UTATH KGASG ZOTKR RKYIG YYGOK TZRKA XIUXJ KYKTG RRGOK TZJGT YRGSU TZGMT KKZR
N GAZRK RUAVR KYSGT MKGOZ TORKY IGXKY YKYJK RKAXS GZXKT ORGVK AXJAR UAVXO KTTKR
KYXKZ KTGOZ IZ
|----------------------------------------|
|---------------PARAMETRAGE--------------|
|----------------------------------------|
Choisissez un paramétrage à appliquer
- Fin du paramétrage : 1
- Suppression des espaces : 2
- Suppression de la ponctuation : 3
- Gestion de la casse : 4
- Recouper le message : 5
2
Choisissez un paramétrage à appliquer
- Fin du paramétrage : 1
- Suppression de la ponctuation : 3
- Gestion de la casse : 4
- Recouper le message : 5
3
Choisissez un paramétrage à appliquer
- Fin du paramétrage : 1
- Gestion de la casse : 4
- Recouper le message : 5
4
Choisissez un paramétrage à appliquer
- Fin du paramétrage : 1
- Recouper le message : 5
1
Entrer votre choix pour la casse :
- sortie du message en majuscule : 0
- sortie du message en minuscule : 1
1

|----------------------------------------|
|-------RESULTAT POST TRAITEMENT---------|
|----------------------------------------|
Votre phrase :
SYKMA OTTGB GOZPG SGOYK AJKHU TNKAX GBKIY KYINB XKYOR RKYVK XJGOZ ZUAZK YJKRG SS
KLG UTATH KGASG ZOTKR RKYIG YYGOK TZRKA XIUXJ KYKTG RRGOK TZJGT YRGSU TZGMT KKZR
N GAZRK RUAVR KYSGT MKGOZ TORKY IGXKY YKYJK RKAXS GZXKT ORGVK AXJAR UAVXO KTTKR
KYXKZ KTGOZ IZ
Avec les paramètrages suivants:
1 - Suppression des espaces
2 - Suppression de la ponctuation
3 - Gestion de la casse
Donne le résultat post traitement suivant :
sykmaottgbgozpgsgoykajkhutnkaxgbkiykyinbxkyorrkyvkxjgozzuazkyjkrgssklgutathkgasg
zotkrrkyigyygoktzrkaxiuxjkyktgrrgoktzjgtyrgsutzgmtkkzrngazrkruavrkysgtmkgoztorky
igxkyykyjkrkaxsgzxktorgvkaxjaruavxokttkrkyxkzktgoziz

|----------------------------------------|
|--------------DECHIFFRAGE---------------|
|----------------------------------------|
Message décrypté :
mseguinnavaitjamaiseudebonheuravecseschvresillesperdaittoutesdelammefaonunbeauma
tinellescassaientleurcordesenallaientdanslamontagneetlhautlelouplesmangeaitniles
caressesdeleurmatrenilapeurduloupriennelesretenaitct
Décalage pour le décryptage:
20
Fin de l'éxécution

Ensuite j'ai fait une partie plus automatique, avec un fichier de phrase en entrée: chaque phrase est chiffrée puis l'algo de déchiffrage tente de retrouver le décalage. Les statistiques de réussite et d'échec s'affichent en sortie.

Du coup j'ai analysé deux fichiers :

  • l'un avec la partie "Origine" de la fiche wiki de césar : lien

  • l'autre avec une dizaine de phrases sans lettre E.

Résultat pour le 1er fichier:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
|----------------------------------------|
|------------CHOIX D'EXECUTION-----------|
|----------------------------------------|
- A la main : 0
- Automatique : 1
1
|----------------------------------------|
|---------EXECUTION AUTOMATIQUE----------|
|----------------------------------------|
Nombre de ligne : 17
Nombre de succès: 17
Nombre d'échec : 0
Fin de l'éxécution

Et les résultats pour le deuxième fichier:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
|----------------------------------------|
|------------CHOIX D'EXECUTION-----------|
|----------------------------------------|
- A la main : 0
- Automatique : 1
1
|----------------------------------------|
|---------EXECUTION AUTOMATIQUE----------|
|----------------------------------------|
Nombre de ligne : 11
Nombre de succès: 1
Nombre d'échec : 10
Fin de l'éxécution

Donc pour le premier autant ça se passe très bien (la phrase la plus courte doit faire 25 caractères sans espace), autant pour le second c'est la débandade. Bon évidemment des phrases sans E, ça a pas été évident à trouver, et c'est des phrases assez courtes en générale (ça varie de 15 à 90 caractères). C'était vraiment pour tester à fond l'algo et clairement il est pas assez solide.

Il faudrait que je rajoute du coup l'analyse avec un dictionnaire. Si j'ai la motivation je m'attaquerais à ca.

+0 -0

premier script avec python, j'en ai profiter pour test. Je vous prie donc de ne pas m'assassiner si vous voyez une horreur !

étape 0 :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# cipher ==> string chiffré
# decipher ==> string déchiffré
# myString ==> string chiffré ou déchiffré


def goToCrypt(myCrypt):
    return "lol"

def etapeZero(deCipher, startPos, pas):
    i = startPos
    z = 0
    tabString = []
    myResult = ''


    deCipher = deCipher.replace(' ', '')
    deCipher = deCipher.replace('ê', 'e')
    deCipher = deCipher.replace("'", '')
    deCipher = deCipher.replace('é', 'e')
    deCipher = deCipher.replace('«', '')
    deCipher = deCipher.replace('»', '')
    deCipher = deCipher.replace(',', '')
    deCipher = deCipher.replace('.', '')

    deCipher = deCipher.upper()




    myLength = len(deCipher)

    print("longueur de chaine", myLength)

    if myLength == 0:
            print('erreur longeur String ==> 0')


    while i < myLength:

        tabString.append(deCipher[i:i + 5])

        myResult += tabString[z]
        myResult += ' '


        i += pas
        z += 1

    return myResult



deCipher = input("Entrez la phrase à chiffrer : ")
cipher = etapeZero(deCipher, 0, 5)
print(cipher)

Édité par Garfield

+0 -0

Étape 1

J'avais un petit peu de temps ce soir, je me suis dit que c'était l'occasion pour participer (enfin) aux défis de Clem'. Voici donc ma version (sans doute pas ultra-optimisée) du décodage du chiffrage César en Python 3, en jouant sur les minuscules et les majuscules pour faciliter le décodage :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
alphabet = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ') #utile pour la suite

#Fonction qui cherche la lettre la plus présente (sans doute E)
def search_e (cryptogram) :
    max = 0
    for letter in alphabet :
        count = cryptogram.count(letter)
        if count > max :
            max = count
            probably_e = letter
    return probably_e

#Fonction de décodage (qui joue sur MAJ/minuscules).
def decode (cryptogram, gap) :
    cryptogram = cryptogram.upper().replace(' ', '')
    translation = cryptogram
    for rank in range(26) :
        new_rank = rank - gap
        if new_rank > 25 :
            new_rank = new_rank - 26
        translation = translation.replace(alphabet[rank], alphabet[new_rank].lower())
    return translation.upper()



cryptogram = input()
probably_e = search_e(cryptogram)

#Cas le plus probable
gap = alphabet.index(probably_e) - 4
print ('\nSi ', probably_e, ' vaut E :')
translation = decode(cryptogram, gap)
print(translation)

#Cas moins probable
gap = alphabet.index(probably_e)
print ('\nSi ', probably_e, ' vaut A :')
translation = decode(cryptogram, gap)
print(translation)

Ce qui donne :

Si K vaut E : MSEGUINNAVAITJAMAISEUDEBONHEURAVECSESCHVRESILLESPERDAITTOUTESDELAMMEFAONUNBEAUMATINELLESCASSAIENTLEURCORDESENALLAIENTDANSLAMONTAGNEETLHAUTLELOUPLESMANGEAITNILESCARESSESDELEURMATRENILAPEURDULOUPRIENNELESRETENAITCTAITPARATILDESCHVRESINDPENDANTESVOULANTTOUTPRIXLEGRANDAIRETLALIBERT

Si K vaut A : IOACQEJJWRWEPFWIWEOAQZAXKJDAQNWRAYOAOYDRNAOEHHAOLANZWEPPKQPAOZAHWIIABWKJQJXAWQIWPEJAHHAOYWOOWEAJPHAQNYKNZAOAJWHHWEAJPZWJOHWIKJPWCJAAPHDWQPHAHKQLHAOIWJCAWEPJEHAOYWNAOOAOZAHAQNIWPNAJEHWLAQNZQHKQLNEAJJAHAONAPAJWEPYPWEPLWNWPEHZAOYDRNAOEJZLAJZWJPAORKQHWJPPKQPLNETHACNWJZWENAPHWHEXANP

Édité par Matouche

Étudiant à l'HEAJ de Namur. Envie de découvrir Sass ? Voilà, voilà…

+0 -0

Voici un petit script un Perl (j'utilise le nouveau Perl, Perl 6). Malheureusement, je n'ai pas eu le temps de plus m'amuser avec, il n'est donc absolument pas complet. J'essaierais de l'améliorer/le compléter à l'occasion. Il s'utilise de la sorte :

1
$ script [mode] [indice] [nom du fichier]

Par exemple, pour chiffrer grâce à décalage de 16 lettres le contenu d'un fichier message.txt :

1
$ script enc 16 message.txt

Avec un fichier texte contenant le message suivant, j'obtiens le résultat ci-dessous.

1
Zeste de Savoir, un petit pas pour l'homme, un grand pas pour la connaissance !
1
2
$ perl6 script.p6 enc 16 message.txt
PUIJUTUIQLEYHKDFUJYJFQIFEKHBXECCUKDWHQDTFQIFEKHBQSEDDQYIIQDSU

Bien évidemment, ça fonctionne dans l'autre sens avec le mode pour déchiffrement, dec. Ci-dessous, vous pourrez retrouver mon code. Encore une fois, je compte bien l'améliorer dès que possible.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
use v6;

my @alphabet = 'A' .. 'Z';

multi sub MAIN(Str $mode, Int $n, Str $filename) {
  given $mode {
    when 'enc' {
      my $message = prepare(slurp($filename));
      my $encrypt = encrypt($n, $message);
      say $encrypt;
    }
    when 'dec' {
      my $message = slurp($filename);
      my $decrypt = decrypt($n, $message);
      say $decrypt;
    }
    default {
      die 'Invalid !';
    }
  }
}

multi sub prepare(Str $message) {
  return $message.subst(/<-:L>+/,'',:g).uc;
}

multi sub encrypt($key where 1..25, $message) {
  $message.trans(@alphabet Z=> @alphabet.rotate($key));
}

multi sub decrypt($key where 1..25, $message) {
  $message.trans(@alphabet.rotate($key) Z=> @alphabet);
}

Le code est ultra basqiue. Les erreurs ne sont absolument pas gérées : par exemple, si l'indice de décalage \$n est supérieur à 25, ça plante. Si le nom du fichier \$filename est incorrect, ça plante. Bref, plein d'améliorations à apporter ! ;)

Édité par Emeric

+2 -0

J'ai fini d'implémenter l'étape 1 en C++, l'étape 0 n'est pas fonctionnel, mais je pense quand même continuer sur l'étape 2. Le code est sur github avec un CMakeLists si certains veulent l'essayer :)

« La Nature est un livre écrit en langage mathématique », Galilée

+0 -0

Voici mon code en Objective-c

Etape 0:

Fichier NSString+Crypt.h :

1
2
3
4
5
6
#import <Foundation/Foundation.h>

@interface NSString (Crypt)
- (NSString *)prepareCrypt;

@end

Fichier NSString+Crypt.m

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#import "NSString+Crypt.h"

@implementation NSString (Crypt)
- (NSString *)prepareCrypt{
    NSString *res;
    //Enlève les accentes et autres conneries
    res = [[self componentsSeparatedByCharactersInSet:[[NSCharacterSet letterCharacterSet] invertedSet]] componentsJoinedByString:@""];
    //Met en masjuscule
    res = [res uppercaseString];
    
    //Enlève les espaces
    res = [res stringByReplacingOccurrencesOfString:@" " withString:@""];
    
    NSMutableString *mutableString = [res mutableCopy];
    
    for (int i = 0; i < mutableString.length; i++){
        if (i % 6 == 0 && i > 0){
            [mutableString insertString:@" " atIndex:i];
        }
    }
    
    return [mutableString copy];
    
}
@end

Etape 1:

CorrectTextFrench.h

1
2
3
4
5
6
import <Foundation/Foundation.h>

@interface CorrectTextFrench : NSObject
- (BOOL)correctTextFrench:(NSString *)text;
- (int)frequencesOfNSString:(NSString *)c in:(NSString *)s;
@end

CorrectTextFrench.m

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#import "CorrectTextFrench.h"

@implementation CorrectTextFrench
- (BOOL)correctTextFrench:(NSString *)text{
    text = [text lowercaseString];
    
    NSString *bestCharFrequences;
    int bestFrequences = 0;
    int currentFrequent = 0;
    
    for (int i = 0; i < 26; i++){
        NSString *search = [NSString stringWithFormat:@"%c", 97 + i];
        currentFrequent = [self frequencesOfNSString:search in:text];
        
        if (currentFrequent > bestFrequences){
            bestCharFrequences = search;
            bestFrequences = currentFrequent;
        }
    }
    
    if ([bestCharFrequences isEqualToString:@"e"] || [bestCharFrequences isEqualToString:@"s"] || [bestCharFrequences isEqualToString:@"a"]){
        return YES;
    }else{
        return NO;
    }
     

}

- (int)frequencesOfNSString:(NSString *)c in:(NSString *)s{
    int f = 0;
    for (int i = 0; i < s.length; i++){
        if ([[NSString stringWithFormat:@"%c", [s characterAtIndex:i]] isEqualToString:c]){
            f++;
        }
    }
    return f;
}
@end

CaesarCrypt.h

1
2
3
4
5
6
7
8
#import <Foundation/Foundation.h>
#import "NSString+Crypt.h"
#import "CorrectTextFrench.h"
@interface CaesarCrypt : NSObject
- (NSString *)cryptString:(NSString *)text withRotation:(int)r;
- (NSString *)decryptString:(NSString *)decrypt withRotation:(int)r;
- (NSArray *)decryptString:(NSString *)decryptText;
@end

CaesarCrypt.m

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#import "CaesarCrypt.h"

@implementation CaesarCrypt
- (NSString *)cryptString:(NSString *)text withRotation:(int)r{
    text = [text prepareCrypt];
    
    const char *utf8 = [text cStringUsingEncoding:NSUTF8StringEncoding];
    size_t len = strlen(utf8) + 1;
    
    char t[len];
    memcpy(t, utf8, len);
    
    for (int i = 0; i  < text.length; i++){
        if (t[i] == ' '){
            continue;
        }
        if ((t[i] + r) > 'Z'){
            t[i] = 64 + ((t[i] + r) - 'Z');
        }else if ((t[i] + r) < 'A'){
            t[i] = 91 - ('A' - (t[i] + r));
        }else{
           t[i] += r;
        }
        
    }
    
    return [NSString stringWithFormat:@"%s", t];
}

- (NSString *)decryptString:(NSString *)decrypt withRotation:(int)r{
    return [self cryptString:decrypt withRotation:r];
}
- (NSArray *)decryptString:(NSString *)decryptText{
    CorrectTextFrench *c = [[CorrectTextFrench alloc] init];
    NSMutableArray *pos = [NSMutableArray array];
    for (int i = 0; i <= 25; i++){
        NSString *string = [self cryptString:decryptText withRotation:i];
        if ([c correctTextFrench:string]){
            [pos addObject:[self cryptString:decryptText withRotation:i]];
        }
        
    }
    
    return [pos copy];
}
@end

Et pour le test :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
    NSString *s = @"J'aimes les poules";
    CaesarCrypt *crytp = [[CaesarCrypt alloc] init];
    NSString *sd = [crytp cryptString:s withRotation:8];
    NSArray *p = [crytp decryptString:sd];
    NSLog(@"Crypt : %@", sd); // RIQUMA TMAXW CTMA
    NSLog(@"Decrypt : %@", [crytp decryptString:sd withRotation:-8]); //JAIMES LESPO ULES
    NSLog(@"Decrypt sans clé : %@", p); //"RIQUMA TMAXW CTMA"
                                        //"VMUYQE XQEBA GXQE"
                                        //"FWEIAO HAOLK QHAO"
                                        //"JAIMES LESPO ULES" <-- C'est le bon message ;)
+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte