Dans ce tp, on implémente un algorithme de chiffrement par Blocs basé sur un réseau de permutation-substitution (SPN).

Rappel de cours

SPN

Ces algorithmes utilisent en entrée une clé, et applique à chaque bloc plusieurs tours constitués de boîtes de substitutions (S-Box) et de boîtes de permutations (P-Box).

• Une S-Box substitue à un ensemble de bits un autre ensembe de bits (transormation bijective).
• Une P-Box est une permutation de bits. Elle prend la sortie d'une S-Box, permutte les bits, et les transmet à une S-box au tour d'après.
• A chaque tour, on combine le bloc avec la clé (ici un xor).

implantation

On prendra

• la taiile du bloc est 8 bits,
• le bloc est découpé en 2 sous-blocs de 4 bits chacun,
• la taille de la clef est 16 bits,
• la clef est décomposée en 2 sous-clefs de 8 bits chacun,
• le nombre de tours est égale à 2,
• les substitutions et les permutations sont les mêmes à chaque tour.

Remarques

On représentera dans le programme une substitution par un tableau d'entiers (unsigned char) de taille 16.

unisgned char s[]={14,3,2,10,12,11,15,9,0,4,7,13,1,8,6,5}

Ainsi, le bloc binaire 0011, qui vaut 3, sera remplacé par 1010 car s[3]=10.

On représentera une permutation par un tableau d'entiers (unisgned char) de taille 8.

unsigned char perm[8]={5,2,0,4,6,1,7,3};

Ainsi, le bit de poids faible (rang 0) est placé au rang 5.

Votre travail

1. Ecrivez les fonctions suivantes, qui implantent le spn décrit ci-dessus.

   #ifndef _SPN_H
   #define _SPN_H
    
   unsigned char do_perm(unsigned char w,unsigned char perm[8]);
   unsigned char do_subst(unsigned char w,unsigned char subst[16]);
    
   unsigned char encrypt(
   		unsigned char w, 
   		unsigned key,
   		unsigned char perm[8],
   		unsigned char subst[16]
   		);
    
   unsigned char decrypt(
   		unsigned char w, 
   		unsigned key,
   		unsigned char perm[8],
   		unsigned char subst[16]
   		);
    
   #endif

2. Ecrivez des programmes spn-encrypt-file.c , spn-decrypt-file.c qui implantent le SPN décrit ci-dessus. Les deux prennent sur la ligne de commande :

   • une clef (un entier non-négatif sur 16 bits),
   • un fichier qui défini une substitution,
   • un fichier qui défini une permutation,
   • "plain text" et "cipher text"

   Testez vos programmes sur un exemple à vous. Vérifiez avec les executables du répertoire

   /export/documents/is3+4/asr/Crypt/SPN-Test
   

3. L’exécutable /export/documents/is3+4/asr/Crypt/16btsef implante l’algorithme de cryptage ci-dessus avec la substitution

   {3,8,14,1,12,5,10,0,2,7,9,11,4,6,15,13}
   

   et la permutation

   {5,2,0,4,6,1,7,3}
   

   et une clef de 16 bits.

   • Développez une procédure qui craque cette clef par la force brute et qui prend un "temps raisonnable".
   • Trouvez la clef et décryptez le fichier /export/documents/is3+4/asr/Crypt/16bits-encrypted.dat