🚀 go-pugleaf

Vincent Burel schrieb:
> "Falk Tannh�user" <tannhauser86549spam@free.fr> wrote in message
> news:4a66b6b5$0$414$426a34cc@news.free.fr...
>> J'ai enfin trouv� 2-3 heures � consacrer au challenge (bon, je ne suis pas
> un casseur de code chevronn� apr�s tout...)
[...]
>> Avec une cl� de longueur 21, l'analyse fr�quentielle devient possible,
>> sachant que les caract�res ' ' et 'e' sont les plus
>> fr�quents en fran�ais. Bizarrement, les trois premiers caract�res du
>> fichier ont �t� encod�s diff�remment.
>> Pour ne pas �tre compl�tement hors sujet : std::map convient tr�s bien
>> pour compter les caract�res :-)
> Combien de temps cela prend de faire un tel d�codage ?
> vous avez des outils sp�cifiques ou bien a t'il fallu programmer qqc de
> sp�cial ?

GCC et Emacs sont suffisants comme outils :-) Un petit programme comme celui-ci fait l'affaire :
____________________________________________________________________________________
#include <fstream>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <iterator>

struct cmp_second
{
   template<typename T>
   bool operator()(T const& a, T const& b) const { return a.second < b.second; }
};

template<typename KeyT, typename MappedT>
void print_sorted_by_second(std::map<KeyT, MappedT> const& m)
{
   typedef std::vector<std::pair<KeyT, MappedT> > VecT;
   VecT v(m.begin(), m.end());
   std::sort(v.begin(), v.end(), cmp_second());
   for(typename VecT::const_iterator it = v.begin(); it != v.end(); ++it)
     std::cout << ' ' << std::hex << std::setfill('0') << std::setw(2) << +it->first
               << '-' << std::dec << std::setfill(' ') << it->second;
}

int main()
{
   std::ifstream in("SimpleAsciiText.bin", std::ios::binary);
   std::vector<unsigned char> data(std::istreambuf_iterator<char>(in),
                                   (std::istreambuf_iterator<char>()));

   // Find global character statistics and key length
   std::map<unsigned char, unsigned> stat;
   for(std::vector<unsigned char>::const_iterator it = data.begin(); it != data.end(); ++it)
   {
     ++stat[*it];
     std::cout << (*it >> 7 & 1); // Print bit 7
   }
   std::cout << "\nFound " << data.size() << " chars, " << stat.size() << " different chars.\n";

   // Find character statistics per key byte
   unsigned const key_length = 21; // Value found during preceding step
   std::vector<std::map<unsigned char, unsigned> > key_stat(key_length);
   for(unsigned i = 0; i < data.size(); ++i)
     ++key_stat[i % key_length][data[i]];
   for(unsigned i = 0; i < key_length; ++i)
   {
     std::cout << std::setw(2) << i << ": ";
     print_sorted_by_second(key_stat[i]);
     std::cout << '\n';
   }

   // Find key bytes and plaintext
   unsigned char const key[key_length] =
   { // To be completed
     0x89 ^ ' ', 0x97 ^ 'e'
   };
   for(unsigned i = 0; i < data.size(); ++i)
   {
     std::cout << char(data[i] ^ key[i % key_length]);
     if(i % key_length == key_length - 1)
       std::cout << '\n';
   }
   return 0;
}
____________________________________________________________________________________

En regardant le bit 7 des caract�res du fichier crypt�, on s'aper�oit qu'il y a des fortes r�gularit�s ; les irr�gularit�s sont 
d�s � la pr�sence des caract�res accentu�s (relativement rares) dans le texte clair. Si on ex�cute le programme dans une fen�tre 
Emacs, on peut faire varier la largeur de la fen�tre � la souris pour reconna�tre la r�gularit� du dessin des 0 et 1 et ainsi 
d�duire que la longueur de la cl� est de 21.
Ceci veut dire que dans un fichier de 1040 caract�res, respectivement 49 ou 50 caract�res ont �t� encod�s avec le m�me octet de 
la cl�. Maintenant il suffit de faire des statistiques de caract�res pour chacun des 21 octets de la cl�.
Pour le premier octet, on voit que les valeurs 0x89 et 0xCC sont les plus fr�quentes (10 respectivement 8 apparitions) et comme 
par hasard, 0x89^0xCC == 0x45 == 0x20^0x65 == ' ' ^ 'e'  - il est donc hautement probable que ces 2 valeurs correspondent � la 
lettre 'e' et � l'espace (voir aussi <http://fr.wikipedia.org/wiki/Fr%C3%A9quence_d%27apparition_des_lettres_en_fran%C3%A7ais>) 
et il ne reste qu'� essayer de d�crypter avec les 2 valeurs (0x89 ^ ' ') et (0x89 ^ 'e') pour le premier octet de la cl� pour 
voir laquelle est la bonne.
C'est pareil pour le deuxi�me octet et les valeurs 0x97 et 0xD2, puis pour les 19 octets restants �a fonctionne de fa�on similaire.
On aurait probablement pu automatiser davantage cette derni�re phase du d�cryptage, mais l'approche "semi-manuelle" avec mise � 
jour successive et recompilation du programme marche suffisamment bien dans le cas pr�sent.

Falk