Le blog de lilxam

J’ai décidé sur ce blog de vous faire part de plusieurs de mes projets, même les plus petits alors voici un petit article en attendant un prochain plus conséquent et/ou plus intéressant.
J’en profite pour dire que mon packer avance mais je me vois confronté à la complexité du format PE donc il faudra attendre un peu avant la prochaine partie. Je vous laisse alors de la lecture.

Un peu de cryptographie, de temps en temps ça ne fait pas de mal =).
Petit flash-back en 1918. Les français sont menacés d’une offensive par les allemands qui percerait jusqu’à Paris. Cinq points d’attaques sont redoutés par l’armée française. Elle n’a pas le droit à l’erreur. Les allemands utilisent un cryptage pour se communiquer, le chiffre ADFGVX. C’est alors que Georges-Jean Painvin fait apparition et parvient à casser ce cryptage. Tentons de faire la même chose et mettons au point un programme permettant de déchiffrer tous ces messages allemands.

Voyons comment la routine de cryptage fonctionne. Je n’ai pas envie de tout expliquer, alors je vous donne un extrait tout droit venu de BibM@th, un super site concernant les mathématiques et la cryptographie.

Ce chiffre est constitué d’une substitution de type carré de Polybe, suivie d’une transposition. Pour réaliser la substitution, les 26 lettres de l’alphabet et les 10 chiffres sont rangés dans un tableau 6×6, aux extrémités desquelles on a ajouté les lettres ADFGVX.

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

Chaque lettre est codé par le couple de lettres qui correspond à sa ligne et à sa colonne. Ainsi, R est codé DF, et le message RENFORT COMPIEGNE 16H10 devient :
DFAXV VFAFD DFGFD DFDFG VAGDA XGGVV AXXAV FDVXA DX
On choisit ensuite, pour faire la transposition, une clé qui est un mot courant, par exemple DEMAIN. On écrit le texte intermédiaire sous ce mot, puis on réordonne les colonnes par ordre alphabétique croissant :

D	E	M	A	I	N
D	F	A	X	V	V
F	A	F	D	D	F
G	F	D	D	F	G
V	A	G	D	A	X
G	G	V	V	A	X
X	A	V	F	D	V
X	A	D	X

A	D	E	I	M	N
X	D	F	V	A	V
D	F	A	D	F	F
D	G	F	F	D	G
D	V	A	A	G	X
V	G	G	A	V	X
F	X	A	D	V	V
X	X	A	D

Il ne reste plus qu’à relire le tableau de haut en bas, et de gauche à droite:
XDFVA VDFAD FFDGF FDGDV AAGXV GGAVX FXADV VXXAD

Vous avait également une explication et un applet Java sur apprendre en ligne pour faire vos tests. Je retiens votre attention sur ce site tout simplement génial dans le domaine de la cryptographie mais pas seulement, les mathématiques et d’autres domaines y sont étudiés.

Bref revenons à nos moutons.
Si vous avez ben compris le système, vous avez aussi compris que la difficulté du décryptage et causée par la transposition. En effet si on arrive à réorganiser la grille et donc à obtenir la première grille (la verte) une simple analyse de fréquence sur les couples de lettres et on retrouve rapidement le message original.
Seulement nous avons pas la clef pour réorganiser cette grille. Donc nous ne savons pas combien de colonnes comporte la grilles, et dans quel ordre sont rangées ces colonnes.

L’attaque

L’attaque va en fait consister à tester toutes les permutations des colonnes de la grille possibles avec un nombre de colonnes allant de 2 à 9 par exemple (nous ne connaissons pas la taille de la clef). Au delà ça commence à faire beaucoup. Ensuite on analyse la fréquence de chaque couple de lettre et on calcule l’IC (Indice de coïncidence). La permutation qui nous donne un IC le plus proche de celui de notre langue (pour nous français : 0.074) s’avère probablement être la bonne.

Coder un programme faisant tout cela n’est pas simple. Pour ce qui est des permutations j’ai utilisé la récursivité. Pour le reste un peu d’algorithmique et de bonnes idées et le tour est joué.
Je vous propose mon code, largement optimisable mais qui fonctionne assez bien :

#include
#include
#include 
 
#define MAX_LENGHT 5112
 
void Permute(unsigned char *charset, unsigned short counter, unsigned char *res);
void GetPermutation();
void Check(unsigned char *res);
double GetIC(unsigned char *szCryptogramme);
 
unsigned char szCryptogramme[MAX_LENGHT] = {0x00};
unsigned char szCryptogrammeR[MAX_LENGHT] = {0x00};
unsigned char szCryptogrammeP[MAX_LENGHT] = {0x00};
 
unsigned char lettres[36+1][2+1];
unsigned short frequences[36+1];
unsigned short NbLettres = 0;
 
double ICmax = 0;
double CurrentIC = 0;
 
int main()
{
    FILE *pFile = NULL;
 
    unsigned int time = 0;
 
    pFile = fopen("cryptogramme.txt", "r");
 
    if(pFile == NULL)
    {
             printf("\nAucun cryptogramme trouvé\n");
             system("pause");
             return 0x0;
    }
 
    fgets(&szCryptogramme, MAX_LENGHT, pFile);
 
    printf("\n\nCryptogramme de départ : %s", szCryptogramme);
 
    time = GetTickCount();
 
    GetPermutation(szCryptogramme);
 
    time = GetTickCount() - time;
    time /= 1000;
 
    printf("\n\nTermine. Effectue en %ld secondes.\nUne sauvegarde se trouve dans log.txt", time);
    system("pause");
    return 0x0;
}
void Check(unsigned char *szKey)
{
     unsigned short wKeyLen = 0;
     unsigned short indice = 0;
     unsigned short indice2 = 0;
     unsigned int c = 0;
 
     size_t i;
 
     wKeyLen = strlen(szKey);
 
     /* On permute les colonnes */
     for(i = 0; i < wKeyLen; i++)
     {
           c=0;
           indice = ((szKey[i]-0x30));
           indice2 = i;
           while(indice < strlen(szCryptogramme))            {                         c++;                                                      szCryptogrammeP[indice2] = szCryptogrammeR[indice];                         indice = ((szKey[i]-0x30) + wKeyLen*c);                         indice2 = i + wKeyLen*c;            }      }            /*On calcule l'ic*/      CurrentIC = GetIC(szCryptogrammeP);            if(CurrentIC > ICmax)
     {
                  FILE *log = NULL;
                  log = fopen("log.txt", "w+");
 
                  /* On enregistre */
                  if(log != NULL)
                  {
                          fprintf(log, "\n\n\nNouvel IC : %f", CurrentIC);
                          fprintf(log, "\nCle : %s (taille : %ld)", szKey, wKeyLen);
                          fprintf(log, "\nNombre de lettres : %ld", NbLettres);
                          fprintf(log, "\nBigramme : %s\n\n", szCryptogrammeP);
 
                          fprintf(log, "\nLettres : \n");
                          for(i = 0; i <= NbLettres; i++)                                 fprintf(log, "\n%s -> frequence : %ld", lettres[i], frequences[i]);
 
                          fclose(log);
                  }
 
                  system("cls");
                  printf("\n\n\nNouvel IC : %f", CurrentIC);
                  printf("\nCle : %s (taille : %ld)", szKey, wKeyLen);
                  printf("\nNombre de lettres : %ld", NbLettres);
                  printf("\nBigramme : %s\n\n", szCryptogrammeP);
 
                  printf("\nLettres : \n");
                  for(i = 0; i < NbLettres; i++)                         printf("\n%s -> frequence : %ld", lettres[i], frequences[i]);
 
                  ICmax = CurrentIC;
 
     }
 
     //system("pause");
     return;
 
}
double GetIC(unsigned char *szCryptogramme)
{
         unsigned short founded = 0;
         unsigned short len = 0;
 
         double IC = 0;
 
         size_t i, j;
 
         memset(&lettres, 0x00, sizeof(lettres));
         memset(&frequences, 0x00, sizeof(frequences));
         NbLettres = 0;
 
         len = strlen(szCryptogramme);
 
         /*Determination de la fréquence de chaque lettres*/
         for(i = 0; i < len; i+=2)
         {
               founded = 0;
 
               for(j = 0; j < 36; j++)
               {
 
                     if(szCryptogramme[i] == lettres[j][0] && szCryptogramme[i+1] == lettres[j][1])
                     {
                                          frequences[j]++;
                                          founded = 1;
                                          break;
                     }
               }
               if(founded == 0)
               {
                          for(j = 0; j < 36; j++)
                          {
                                if(lettres[j][0] == 0x00)
                                {
                                                 lettres[j][0] = szCryptogramme[i];
                                                 lettres[j][1] = szCryptogramme[i+1];
 
                                                 frequences[j]++;
                                                 break;
                                }
                          }
               }
         }
 
         /*Comptage du nombre de lettres */
         for(j = 0; j < 36; j++)
         {
               if(frequences[j] != 0x0)
                                NbLettres++;
         }
 
         /*Calcul de l'IC*/
         len /= 2;
 
         for(j = 0; j < NbLettres; j++)
         {
               IC += (double)(frequences[j]*(frequences[j]-1))/(len*(len-1));
         }
 
         return IC;
}
void GetPermutation()
{
     unsigned short wKeyLen;
     unsigned int dwSize = 0;
 
     unsigned char charset[10+1] = "0123456789";
     unsigned char wKeyPermutted[9+1] = {0x00};
 
     size_t i, j, k, l;
 
     l = 0;
     for(wKeyLen = 2; wKeyLen <= 9; wKeyLen++) /* Test avec des clefs de 2 à 9 caractères */
     {
 
                printf("\nTest avec une clef de %ld charactères...", wKeyLen);
                charset[wKeyLen] = 0x00;
 
                /* On remet le tableau en colonnes */
                dwSize = strlen(szCryptogramme)/wKeyLen;
 
                for( j = 0; j < dwSize; j++)
                {
                     for(k = 0; k < wKeyLen; k++)
                     {
                           szCryptogrammeR[j*wKeyLen+k] = szCryptogramme[j+k*dwSize];
                     }
                }
 
                /* On permutte la clef et on check */
                Permute(charset, wKeyLen, wKeyPermutted);
 
                for(j = 0; j <= 9; j++)                       charset[j] = 0x30+j;                }            return; } void Permute(unsigned char *charset, unsigned short counter, unsigned char *res) {      size_t i;      char tmp[1+1] = {0x0};                 if(counter > 0)
     {
 
         counter -=1;
         for(i = 0; i < strlen(charset); i++)
         {
               if(charset[i] != 0xFF)
               {
                    res[counter] = charset[i];
                    charset[i] = 0xFF; /* Pour éviter d'avoir deux fois le même caractère
                                          dans la clef */
 
                    //Sleep(500);
 
                    Permute(charset, counter, res); /* On utilise la récursivité pour faire le BF */
                    charset[i] = res[counter];
               }
 
         }
     }
     else
     {
         Check(res); /* On check avec la nouvelle clef */
     }
     return;
}

Une petite démonstration avec un poème de Baudelaire :

L’Horloge

Horloge! dieu sinistre, effrayant, impassible,
Dont le doigt nous menace et nous dit: “Souviens-toi!
Les vibrantes Douleurs dans ton coeur plein d’effroi
Se planteront bientôt comme dans une cible;

Le Plaisir vaporeux fuira vers l’horizon
Ainsi qu’une sylphide au fond de la coulisse;
Chaque instant te dévore un morceau du délice
A chaque homme accordé pour toute sa saison.

Trois mille six cents fois par heure, la Seconde
Chuchote: Souviens-toi! – Rapide, avec sa voix
D’insecte, Maintenant dit: Je suis Autrefois,
Et j’ai pompé ta vie avec ma trompe immonde!

Remember! Souviens-toi! prodigue! Esto memor!
(Mon gosier de métal parle toutes les langues.)
Les minutes, mortel folâtre, sont des gangues
Qu’il ne faut pas lâcher sans en extraire l’or!

Souviens-toi que le Temps est un joueur avide
Qui gagne sans tricher, à tout coup! c’est la loi.
Le jour décroît; la nuit augmente; souviens-toi!
Le gouffre a toujours soif; la clepsydre se vide.

Tantôt sonnera l’heure où le divin Hasard,
Où l’auguste Vertu, ton épouse encor vierge,
Où le Repentir même (oh! la dernière auberge!),
Où tout te dira Meurs, vieux lâche! il est trop tard!”

Charles Baudelaire

On le crypte avec la clef VERTU. On obtient

GXFGDXXVAFDADFFGXDDXGAFAXXADFVFVAFFVAXVFFVDFXXFXGXDXAG
FVFDDDFVFVDDDGFFAADAAXDGDAFFGXXGAFGVDAFFDFFXFDDADDDFXV
AAFVFVAXAXFVFFFXAFGFADGFFVDFDXDVVVFFVADFDVXAXXDVFDVDAV
FFFAADFAAXDVDXDFDVDVVFFVXFDFFFFDDXFVXDGXDVDVGXDVDVDAFA
GVFVXXFGAVFGXGDXDGDXGFFVXFFVDFXXFVFVGXFFVXAXFAFVFVAAFA
FFFFFXDVAFFVFADAXXXAFVXXXFDXFXDVDVGFAFFAFVFVFAAFDAAXDV
DXADFFDFDDDAFDXFDFAGAFDDFFXFGDFVAXGDXVVFFFXXVGFFFAFVVV
VFDFDVVFVXFFVXFDFDDXVDFFDVVDVVADFAXDXVXFDDXFAVVAFAFFVG
XAFVFFFXVVDAVFAXVAVXAFVVFFVFVDAFVGVAGDDDADADVDFAXDFAVA
VFAXXDVFAVAFADVAFFFAFDFFVVADFFFFDDFFXGFFFFDAFDFDGAAXVD
VXXDDAAAVXDDDVFDVFGDDFFDFFFDFFFFVGDDXXXVVGVDVAVVFVXXFD
AXXDDAVDDXDVVFXXVFXXFDGDVAGDVGVXXADFFFDVFFVXFDVGFFADAG
ADDDVADVFVXGVDVAXFXFVFVDVFAXXFFDADGVXDGFXAFVXFVFFFVXVX
GAFFGFAFVVVGXXVVFAGVAFVDDAFXAFXVXDDFFVDFDXFFXXDDAFAFFV
FVXXFADGDVGAXVVXVFVADVVXAVGVAXFXFVDVXAAXAFFVAGXVFVGAGF
AGDFFDXXFAAVFFDGGGDFAVFDFFXFVAXVDGDFFGDVDFAVAAFFFVXFFV
FAFFXFADAVFVFFAVDAXAADFFFAFAADFVDDDAAXFGFXDDDADXXXDFAV
FDXFFVXFADXXDAFFVVFXDVGAFFGVXFVDFVFAAXFGDDDVFAFXAVFFVF
XFVDFAAFGAGADXFXAVDDXXDDAXFXFVFFFVAGAVDVFDXXDGFADXVFDV
FFDXFXFVVXAXFXADDVVVDXFVFDFVADFXDVVVXXAXAXDFXFDXAGVFAD
VXFFVGDVDFFGAFVAXFVFVVFAAAXFVXDFVXVFVVAAVAFXAFVGDDDADA
DXFVFGVGFDGDGFFDVFXVXAVDVVVFXXFFFXGGFXXFXDXFVFVAFVVVDF
AXVFDXFXDFDGFXXXFAGFVXAXGADXXDDAGXXAXAFXDDXDXXAXFFVFVX
GDFAXADFVDXDDDXFFVAAVFVFVFAFFDDFFGAFVXXFVXXFDDVFXXDDFF
FFXGDFADFXVFFDXFFVAGVFGDVXVDFDFFVFDAVFDFAXFFVFVDVVDFVF
AAXFVFADDFVXFGVAVDXXFFAVFVXFVAGXVGXXXDDVVDADVFVDVFDDVX
XDVDVFDDXDXAVGVGDDDDGDFFVFVXVFADXFVDFAXDXADDFAVFVXXVFD
ADAXDFFVAGXVXDAGXXFFAFVAVGFDFFAFVFADFXVAVDFXXAVXFFXGXG
FVGFFGFDAVVFVAVVVADVVAVVXDVXAFFFADAFGFAFFFAFFDVXAVAAFV
XGVFVVGFAAXFXAVAFAGAVFFVXVFXVXDDFDFAGFVADFDDDVXDDDVAFF
XXVDADXFAAVDVFVFVGVVVGDVVDDGVDAFFFVXFVFFFAXFVDXAVDVAFF
VGVAFFADFAGAXDXFADAFVADFFDVXAGVFXDVFFVAGAGVFAFFAFGFXFA
VFDFVFVDVXFVFXFFDADFGFVAXDVGVDFDAGVVVFXDAFVDVDFFADVFAF
VVVXVDFD

Maintenant on teste notre programme et voilà le résultat :

Nouvel IC : 0.069723
Cle : 40123 (taille : 5)
Nombre de lettres : 25
Bigramme :

VGGVAFXDVGAFXFVDGVAFXDVGAFXFVDVXFAVDVFFXFAXVFAFXDFXDVD
VDAGAGXDFFDAFFXVDFFADDGAFFFXFXFADVVGVDVXAFXVDFVGVDVXAF
FAXFDFXVAFVFFXDDVDXVFFAAVDVDDFXVAFVFFXVXFADFFXAFVFXAFA
VDXVFXDFAFFAVGVDFXXAFADVXDFFXVDFVDFXVXAFVFVGVDVFXDFXVX
FFXVFXDFAFXVAAAFVDVFXDGAVGVDFAXVVXVDAGAGXDAFFAFXVDGAVG
FFXVDFVDXDAFXVDFDVFAVDXVDFDFAAAFDDDDVDVXFFXVFXVFXVVDAA
FADVVGVDVGVDGAVGFFFAFXFAXDXAFFGAAFXDVDVFGXAGVFFAXDFFXA
VDXDFXVGGVAFXDFAXGAFXVFFFAXVFXFAGGVFVFXVVDFXDAVGGAGVFA
VXVDFFVFAGAFXVVXVXVDVGFFAAAFVFVGFAFXFXVDAAGVFFGGVFVDFA
XVFXDFFFXVDFDFVDVXXAAFXDVDVFXVDDAFXDAAVDFFVFVXVFVXVGFA
AAVDFFAAGVFFGGVFVDGVAFDDDDVDFFAAAAAFXDVXGAAFVFXDDFAFVF
DFVDFXFFFXFFFAFXAFXVDFXDAFFAFXDDFAVGVGVDFXFAGXAAVDXVDF
FXAGAFFAFXGAFFXDGVVDVFXDVDVGFFFXVDAAAFXVVXVDAAGVVFAAGV
AFDFVDFXAFVFXAFAVDXVFXDFAFFAXDFFGAFAVXVDFFXAVDAAFXFFXA
AFFAGXVXFAXVFXVDAADFVDDDFFFAXVDFVDXVFFXVDFVXFADFAXVDFX
VFFAFXFFVFDFXDVDAGAFFAFXVDDFAXFFFAGAAFDDGADFFFXAFAVDFF
XAVDAADDFFDFXDAFDDGAVDFADDDDAFXVVXVDXDVDDDVDDDDVVDXDFX
AFVFXAFAVDXVFXDFAFFAGAXDAFVXFAXFVFVDVDFXDFAFDDVDDDAFXD
DDAFXVXFAFFXFAVDXDVXVDDDDFFFVGGAFFXDVGVDDFAFVFDFVDFXVG
VDFXVGFFXVXFVFVDFXVGVDFXDDFAXVVFDFVDFXDDAFXDDFVDVGAGAF
VGDFXDVDFXAFXVDFVXVDFXXFFFXVXFVFVDFXGGVFFAVGXVVDAGFFVF
DFGAFFFXVGAAGVVDXDFXFFXVFXVDXVVDGXDFXDFFFAXDVDVGAFXDFX
AFVFXAFAVDXVFXDFAFFAGGVFVDVGVDDFVDDDGAFXVDFXDFVFXVAXAF
VFVDVFXDFFXAFAVXVDGGVFFAXFFFXFXVVDFXFFXVFXDFXDFAAAGVVD
XDDFAFVFDFAAAFVFGAAAVDFXDFVGFFVGAFFAVGVDAXAFVFXDVXAAXD
AFDFVGFFXVVFFADFFFVFXFDDVDXVDFVDFXAFVFXAFAVDXVFXDFAFFA
VGVDXFAFVFAGAGXDVDFFDFAFVFAXAFVFXDFXFXAFFAAGVGFFAAVGVD
GAFXDAVXXDVDFXVDXAFAVXVDDFFFXVDFDFFXAFXVXVVDXDFFVGGVVD
VFXDVDAFVGVDVXFAXAFAXVGVFFFXFFXDVXAFVGFFVFXFVFFXDFVDXA
VDXDDFVFDFAFXVGAAFVFFXVDVDXVAAAFXDXAFAVDXDXFVDAFVGVDXD
VDGAVDXVDFFAXDDDDDVDAFGVVGFFVXVDXDXVFAXDVDFFVFDVVDXDXF
VDAFDFAFVFDFDFVDVXFAXDFFDDVDVFXDFXXAFAVDVFGXVGAAGVVDFA
VGVDFXDFDFXDAFGADFFFXDVXAAGVFFXDVGVDFXDVFFVFVXVDVGFFFA
XDVDXXXXDD

Lettres :

VG -> frequence : 47
GV -> frequence : 17
AF -> frequence : 76
XD -> frequence : 61
XF -> frequence : 15
VD -> frequence : 128
VX -> frequence : 33
FA -> frequence : 68
VF -> frequence : 59
FX -> frequence : 71
XV -> frequence : 56
DF -> frequence : 66
AG -> frequence : 13
FF -> frequence : 62
DA -> frequence : 3
DD -> frequence : 28
GA -> frequence : 21
DV -> frequence : 7
AA -> frequence : 27
XA -> frequence : 19
GX -> frequence : 5
XG -> frequence : 1
GG -> frequence : 6
AX -> frequence : 5
XX -> frequence : 2
-> frequence : 0

Une simple analyse de fréquence et on retrouve alors notre joli poème =).

Voilà c’est tout ce dont je voulais vous faire part. Je sais ce n’est rien d’extraordinaire mais on ne sait jamais, peutêtre que ça intéressera quelqu’un. Du moins j’ai trouvé très intéressant de faire ce programme.

Voici le code + binaire :
ADFGVX