Version:0.9 StartHTML:0000000105 EndHTML:0000091588 StartFragment:0000000152 EndFragment:0000091554 
TP n°2 de Cryptographie
 
 
PRESENTATION GENERALE DE L’ALGORITHME
DATA ENCRYPTION STANDARD
 
 
 
 
 
LUP SQT – Novembre 2004
 
 
 
 
 
Julien VEHENT
 
 
 
 
PRESENTATION 
 

En 1977, le Bureau Fédéral des Standards des États-Unis (US Fédéral Bureau of Standards) a approuvé un algorithme cryptographique conçu par la firme IBM pour la sécurité des données. Le Standard de Codage des Données (DES, Data Encryption Standard) a été approuvé uniquement pour des documents non classés secret-défense. Depuis lors, le DES a été largement adopté dans l'industrie du matériel cryptographique (processeur de cryptage), mais également dans l’industrie du logiciel où l'algorithme peut être implanté en un nombre limité de lignes de codes.

 

DES est un algorithme de cryptage rapide lorsqu’il est implanté matériellement. Aujourd’hui, il peut être cassé en un minimum de temps avec des moyens appropriés, comme le montre le résultat du dernier DES challenge animé par RSA Security.

 

On voit en effet que le groupe « Electronix Frontier Foundation » à cassé le code en 22 heures et 15 minutes en janvier 1999. DES n’est donc plus un système de cryptographie à toute épreuve, c’est pourquoi il a été remplacé par Advanced Encryption Standard en 2001.

 

La derniére spécification de DES est la Federal Information Processing Standards Publication n° 46-3 (FIPS46-3) datée du 25 octobre 1999. Il est peu probable de voir évoluer DES à l’avenir, étant donné son remplacement par AES.

 

 

Voici un extrait d’article qui retrace le parcours de DES :

« Dans les laboratoires secrets du gouvernement, lors de la Seconde Guerre mondiale, la cryptographie est entrée dans l’ère de l’informatique et a intégré les mathématiques. Toutefois, aucun professeur n’enseignant cette discipline et aucune conférence n’y étant consacrée, toutes les recherches américaines en la matière étaient menées à la National Security Agency (NSA).

A cette époque où l’internet n'était qu’une simple curiosité, la cryptographie n’était même pas une branche reconnue des mathématiques. C’est alors que le DES a fait son apparition.

Pour le début des années 1970, l’idée était révolutionnaire. Le NBS réclamait un standard de chiffrement gratuit. Comme le Bureau souhaitait que ce standard ne soit pas militaire, il s’est adressé au public pour la création d’algorithmes de chiffrement. Le NBS n’a reçu qu’un seul candidat sérieux: DES, provenant de recherches des laboratoires d’IBM. En 1976, celui-ci est devenu l’algorithme de chiffrement officiel du gouvernement américain pour les communications "sensibles mais non classées secrètes". Celles-ci incluaient par exemple des informations d’ordre personnel, financier et logistique. […] Lorsque IBM l’a proposé comme standard, personne ne disposait du savoir-faire pour l’analyser, excepté la NSA. Elle a apporté deux changements au DES: elle a adapté l’algorithme et réduit de plus de moitié la longueur de la clé.[…]

Les modifications apportés par la NSA ont provoqué un tollé parmi les rares personnes à y prêter attention. Elles furent choquées à la fois par "l'emprise invisible" de la NSA (les changements n’ont pas été rendus publics et aucune explication n’a été donnée quant à la forme finale de l’algorithme), et par la longueur réduite de la clé.

Toutefois, ce tollé s’est accompagné de recherche scientifique. Il n’est pas exagéré d'affirmer que la publication du DES a donné naissance à la cryptographie en tant que discipline académique moderne. Les premiers cryptographes universitaires ont commencé leur carrière en essayant de casser le DES ou, du moins, en essayant de comprendre les modifications apportées par la NSA.

Quasiment tous les algorithmes de chiffrement (en particulier ceux utilisés par la cryptographie "à clé publique" [utilisé par le fameux PGP]) peuvent retracer leurs origines jusqu'au DES »

 

Passons maintenant à l’analyse de l’algorithme DES :

 

 

TRAITEMENT DU TEXTE CLAIR

DES crypte des blocks de texte de 64 bits avec une clé de 56 bits. Cette derniére est réduite à deux parties de 24bits, soit 48 bits, pour le traitement dans l’algorithme.

La figure ci-dessous permet de visualiser le travail effectué sur le block de texte clair de 64 bits.

 

I)                  Le texte clair est permuté, c'est-à-dire que l’ordre des bits est réagencé selon une table définie dans le code. Le résultat est séparé en deux parties, que nous nommerons Gauche et Droite, de 32 bits.

---ENTREE DANS LES ITERATIONS, AU NOMBRE DE 16---

II)               La partie de droite est stockée pour devenir la partie de gauche de l’itération suivante.

 

III)            La partie de droite est expansée à 48 bits grâce à une table définie dans le code qui repète certains bits.

 

IV)             La partie de droite et la clé effectuent un XOR.

 

V)                Le block de 48 bits en sortie du XOR est envoyé dans les S-Box. Le fonctionnement des S-Box sera détaillé plus tard.

 

VI)             Le block de 32 bits en sortie des S-Box est permuté, le principe est le même que pour la permutation initiale mais la table change.

 

VII)          Ce dernier effectue un XOR avec la partie de gauche et le résultat deviens la partie de droite de l’itération suivante, qui commence juste après cette étape.

 
 
            A la fin de la 16éme itération, les deux parties sont concaténées et le block de 64bits obtenus est permutés avant d’être sorti du 
programme.
 
            En ce qui concerne le déchiffrage :
Si on considére l’entrée du 16éme étage de déchiffrage. On sais que G16 = D15 et que D16 = G16 XOR f(R15,K15).
Selon les propriétés de l’algorithme, on démontre que la sortie du 1er étage de décryptage est égale au 32bits inversé de l’entrée du 16éme étage de cryptage.
 
 
            LA PERMUTATION INITIALE
 
                        static int table_DES_IP[64] = {
                       39,  7, 47, 15, 55, 23, 63, 31,
                       38,  6, 46, 14, 54, 22, 62, 30,
                       37,  5, 45, 13, 53, 21, 61, 29,
                       36,  4, 44, 12, 52, 20, 60, 28,
                       35,  3, 43, 11, 51, 19, 59, 27,
                       34,  2, 42, 10, 50, 18, 58, 26,
                       33,  1, 41,  9, 49, 17, 57, 25,
                       32,  0, 40,  8, 48, 16, 56, 24
                       };
 
La séquence en entrée est un block de 64 bits. Lors de la permutation initiale, les bits sont réagencés en suivant la table ci-dessus. 
C’est-à-dire que le bits numéro 39 passe en premiére position, suivi du bits numéro 7, puis du bits numéro 47, etc…..
 
            La FIPS46-3 définit une table de permutation différente de celle utilisée dans le code source ici étudiée, mais le principe est 
exactement le même.
 
            Après cette permutation, le block est séparé en deux block de 32 bits. Par rapport au block initial, les block « D » et « G » seront 
donc les bits suivant :
 
            G :        39,  7, 47, 15, 55, 23, 63, 31,                       D :        35,  3, 43, 11, 51, 19, 59, 27,
               38,  6, 46, 14, 54, 22, 62, 30,                              34,  2, 42, 10, 50, 18, 58, 26,
               37,  5, 45, 13, 53, 21, 61, 29,                              33,  1, 41,  9, 49, 17, 57, 25,
               36,  4, 44, 12, 52, 20, 60, 28,                              32,  0, 40,  8, 48, 16, 56, 24
 
 
 
        L’EXPANSION DE 32 à 48 BITS
 
            Le block D est expansé à 48 bits être de même taille que la clé. Cette expansion est réalisée en en répétant certains bits de l’ancien 
block dans le nouveau block.
 
 
static int table_DES_E[48] = {
    31,  0,  1,  2,  3,  4,  3,  4,
     5,  6,  7,  8,  7,  8,  9, 10,
    11, 12, 11, 12, 13, 14, 15, 16,
    15, 16, 17, 18, 19, 20, 19, 20,
    21, 22, 23, 24, 23, 24, 25, 26,
    27, 28, 27, 28, 29, 30, 31,  0
};
 
            Dans le tableau ci-dessus, les chiffres en rouges sont les chiffres répétés. Ils sont au nombre de 16 pour passer de 32 à 48 bits. 
            Cette table n’est pas celle de la FIPS46-3 mais le principe est le même.
 
 
            LES S-BOX
 
            Les S-Box sont aux nombres de 8. Chacune d’elle acceptent un nombre sur 6 bits en entrée, ce qui signifie que l’on traite un nombre 
de 48 bits (8*6). 
 
Ce nombre binaire est décomposé. Les bits respectivement plus fort et plus faible sont utilisées pour repérer une ligne, les 4 bits 
centraux repèrent un colonne. 
On obtient une coordonnée dans un tableau.
 
Ces tableaux contiennent des nombres sur 4 bits (entre 0 et 15) qui seront les valeurs en sortie des S-Box.
 
Ex :       101101
 
 
            Les bits en rouges sont la référence de ligne, soit 11 ou, en entier, le nombre 3.
            Les bits en bleu sont la référence de colonne, soit 0110 ou, en entier, le nombre 6.
 
            Maintenant considérons la table suivante, définie dans le code source de DES :
 
            /* table S[0] */
00..........{.13,  1,  2, 15,  8, 13,  4,  8,  6, 10, 15,  3, 11,  7,  1,  4,
01...........10, 12,  9,  5,  3,  6, 14, 11,  5,  0,  0, 14, 12,  9,  7,  2,
10...........7,  2, 11,  1,  4, 14,  1,  7,  9,  4, 12, 10, 14,  8,  2, 13,
11-------> 0, 15,  6, 12, 10,  9, 13,  0, 15,  3,  3,  5,  5,  6,  8, 11  },
..............................................||             
..............................................||
............................................0110
 
        On recherche dans la table la ligne correspondant à nos coordonnées. On tombe ici sur le chiffre 13 soit 1101 en binaire.
 
            Chaque S-Box possédent un tableau qui lui est propre. Ici, les tableaux ne sont pas ceux de la FIPS 46-3.
 
 
 

TRAITEMENT DE LA CLE

La clé, d’une longueur de 56 bits, est tout d’abord permutée (permutation de choix 1) via une table, comme pour le texte clair. Elle est ensuite séparée en deux blocks de 28 bits. Ces blocks subissent un « Left Shift » c'est-à-dire un décalage des bits à gauche. Dans notre code source, le décalage est de 1 ou 2 bits suivant le round dans lequel on se trouve.

Ces deux parties « Shiftées » sont stockées pour servir à l’itération suivante (oû elles subiront encore un « Left Shift »).

Dans l’itération en cours, Les deux blocks sont concaténées pour effectuer une permutation de choix 2. Lors de cette permutation, la taille du block est réduite de 56 à 48 bits

static int table_DES_PC2[48] = {
    24, 27, 20,  6, 14, 10,  3, 22,
     0, 17,  7, 12,  8, 23, 11,  5,
    16, 26,  1,  9, 19, 25,  4, 15,
    54, 43, 36, 29, 49, 40, 48, 30,
    52, 44, 37, 33, 46, 35, 50, 41,
    28, 53, 51, 55, 32, 45, 39, 42
};
 
Pour effectuer cette réduction, certains bits sont tout simplement supprimés. Ainsi, dans le tableau ci-dessus, les bits 
{2 ; 13 ; 18 ; 21 ; 31 ; 34 ; 38 ; 47 } sont supprimés.
 
Le résultat de cette fonction effectue un XOR avec le block de texte clair de 48 bits (étape IV).
 
 
 
 
 

CODE SOURCE

Le code source ci-dessous reprend les points vu ci-dessus. Les opérations d’une itération de cryptage sont contenu dans une boucle « for » qui va de 0 à 15, soit 16 itérations. 

 
 
 
 
 
/*****************************************************************************
 * des.c                                                                     *
 *                 Software Model of ASIC DES Implementation                 *
 *                                                                           *
 *   Written 1995-8 by Cryptography Research (http://www.cryptography.com)   *
 *   Original version by Paul Kocher. Placed in the public domain in 1998.   *
 *  THIS IS UNSUPPORTED FREE SOFTWARE. USE AND DISTRIBUTE AT YOUR OWN RISK.  *
 *                                                                           *
 *  IMPORTANT: U.S. LAW MAY REGULATE THE USE AND/OR EXPORT OF THIS PROGRAM.  *
 *                                                                           *
 *****************************************************************************
 *
 ******************************************************************************
 *Notes pour l'implémentation                                                 *
 *                                                                            *
 *     Cette implémentation de DES adhére aux spécifications de la "FEDERAL   *
 *  INFORMATION PROCESSING STANDARDS PUBLICATION" numéro 46-3 et produit des  *
 *     sorties standards. L'opération interne de l'algorithme est légèrement  *
 *    différentes de la FIPS46. Par exemple, les Sbox ont étaient réarrangées *
 *  pour simplifier l'implémentation et de nombreuses permutations ont étaient*
 *  modifiées.                                                                *
*****************************************************************************/
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "des.h"
 
 
static void ComputeRoundKey(bool roundKey[56], bool key[56]);
static void RotateRoundKeyLeft(bool roundKey[56]);
static void RotateRoundKeyRight(bool roundKey[56]);
static void ComputeIP(bool L[32], bool R[32], bool inBlk[64]);
static void ComputeFP(bool outBlk[64], bool L[32], bool R[32]);
static void ComputeF(bool fout[32], bool R[32], bool roundKey[56]);
static void ComputeP(bool output[32], bool input[32]);
static void ComputeS_Lookup(int k, bool output[4], bool input[6]);
static void ComputePC2(bool subkey[48], bool roundKey[56]);
static void ComputeExpansionE(bool expandedBlock[48], bool R[32]);
static void DumpBin(char *str, bool *b, int bits);
static void Exchange_L_and_R(bool L[32], bool R[32]);
 
static int EnableDumpBin = 0;
 
 
 
/**********************************************************************/
/*                                                                    */
/*                            DES TABLES                              */
/*                                                                    */
/**********************************************************************/
 
 
/*
 *  IP: Output bit table_DES_IP[i] equals input bit i.
 *
 *  Permutation initiale: les bits du block de texte clair
 *  sont réarrangés selon la table ci-dessous
 */
static int table_DES_IP[64] = {
    39,  7, 47, 15, 55, 23, 63, 31,
    38,  6, 46, 14, 54, 22, 62, 30,
    37,  5, 45, 13, 53, 21, 61, 29,
    36,  4, 44, 12, 52, 20, 60, 28,
    35,  3, 43, 11, 51, 19, 59, 27,
    34,  2, 42, 10, 50, 18, 58, 26,
    33,  1, 41,  9, 49, 17, 57, 25,
    32,  0, 40,  8, 48, 16, 56, 24
};
 
 
/*
 *  FP: Output bit table_DES_FP[i] equals input bit i.
 *
 *  Permutation Finale: Le block de 64 bits en sorties
 *  des 16 itérations est réarrangé comme ci-dessous
 */
static int table_DES_FP[64] = {
    57, 49, 41, 33, 25, 17,  9,  1,
    59, 51, 43, 35, 27, 19, 11,  3,
    61, 53, 45, 37, 29, 21, 13,  5,
    63, 55, 47, 39, 31, 23, 15,  7,
    56, 48, 40, 32, 24, 16,  8,  0,
    58, 50, 42, 34, 26, 18, 10,  2,
    60, 52, 44, 36, 28, 20, 12,  4,
    62, 54, 46, 38, 30, 22, 14,  6
};
 
 
/*
 *  PC1: Permutation choice 1, used to pre-process the key
 *
 *  Permutation des bits sur la clé de 56 bits
 */
static int table_DES_PC1[56] = {
    27, 19, 11, 31, 39, 47, 55,
    26, 18, 10, 30, 38, 46, 54,
    25, 17,  9, 29, 37, 45, 53,
    24, 16,  8, 28, 36, 44, 52,
    23, 15,  7,  3, 35, 43, 51,
    22, 14,  6,  2, 34, 42, 50,
    21, 13,  5,  1, 33, 41, 49,
    20, 12,  4,  0, 32, 40, 48
};
 
 
/*
 *  PC2: Map 56-bit round key to a 48-bit subkey
 *
 *  Substitution de la clé de 56 bits par une clé de 48
 *  bits. Les bits qui ne sont pas dans la table ne
 *  sont pas utilisés
 */
static int table_DES_PC2[48] = {
    24, 27, 20,  6, 14, 10,  3, 22,
     0, 17,  7, 12,  8, 23, 11,  5,
    16, 26,  1,  9, 19, 25,  4, 15,
    54, 43, 36, 29, 49, 40, 48, 30,
    52, 44, 37, 33, 46, 35, 50, 41,
    28, 53, 51, 55, 32, 45, 39, 42
};
 
 
/*
 *  E: Expand 32-bit R to 48 bits.
 *
 *  Expansion de la partie droite du texte clair 
 *  de 32 bits à 48 bits.
 *  Les bits sont utilisés plusieurs fois pour
 *  arriver à  48 bits.
 */
 
static int table_DES_E[48] = {
    31,  0,  1,  2,  3,  4,  3,  4,
     5,  6,  7,  8,  7,  8,  9, 10,
    11, 12, 11, 12, 13, 14, 15, 16,
    15, 16, 17, 18, 19, 20, 19, 20,
    21, 22, 23, 24, 23, 24, 25, 26,
    27, 28, 27, 28, 29, 30, 31,  0
};
 
 
/*
 *  P: Permutation of S table outputs
 *
 *  Permutation en sortie des S-Box
 */
static int table_DES_P[32] = {
    11, 17,  5, 27, 25, 10, 20,  0,
    13, 21,  3, 28, 29,  7, 18, 24,
    31, 22, 12,  6, 26,  2, 16,  8,
    14, 30,  4, 19,  1,  9, 15, 23
};
 
 
/*
 *  S Tables: Introduce nonlinearity and avalanche
 *
 *  Définition des S-Box.  Au nombre de 8, Elles permettent
 *  de faire correspondre une sortie sur 32 bits à 
 *  une entrée sur 48 bits.
 *  
 */
static int table_DES_S[8][64] = {
 
    /* table S[0] */
        {   13,  1,  2, 15,  8, 13,  4,  8,  6, 10, 15,  3, 11,  7,  1,  4,
            10, 12,  9,  5,  3,  6, 14, 11,  5,  0,  0, 14, 12,  9,  7,  2,
             7,  2, 11,  1,  4, 14,  1,  7,  9,  4, 12, 10, 14,  8,  2, 13,
             0, 15,  6, 12, 10,  9, 13,  0, 15,  3,  3,  5,  5,  6,  8, 11  },
 
    /* table S[1] */
        {    4, 13, 11,  0,  2, 11, 14,  7, 15,  4,  0,  9,  8,  1, 13, 10,
             3, 14, 12,  3,  9,  5,  7, 12,  5,  2, 10, 15,  6,  8,  1,  6,
             1,  6,  4, 11, 11, 13, 13,  8, 12,  1,  3,  4,  7, 10, 14,  7,
            10,  9, 15,  5,  6,  0,  8, 15,  0, 14,  5,  2,  9,  3,  2, 12  },
 
    /* table S[2] */
        {   12, 10,  1, 15, 10,  4, 15,  2,  9,  7,  2, 12,  6,  9,  8,  5,
             0,  6, 13,  1,  3, 13,  4, 14, 14,  0,  7, 11,  5,  3, 11,  8,
             9,  4, 14,  3, 15,  2,  5, 12,  2,  9,  8,  5, 12, 15,  3, 10,
             7, 11,  0, 14,  4,  1, 10,  7,  1,  6, 13,  0, 11,  8,  6, 13  },
 
    /* table S[3] */
        {    2, 14, 12, 11,  4,  2,  1, 12,  7,  4, 10,  7, 11, 13,  6,  1,
             8,  5,  5,  0,  3, 15, 15, 10, 13,  3,  0,  9, 14,  8,  9,  6,
             4, 11,  2,  8,  1, 12, 11,  7, 10,  1, 13, 14,  7,  2,  8, 13,
            15,  6,  9, 15, 12,  0,  5,  9,  6, 10,  3,  4,  0,  5, 14,  3  },
 
    /* table S[4] */
        {    7, 13, 13,  8, 14, 11,  3,  5,  0,  6,  6, 15,  9,  0, 10,  3,
             1,  4,  2,  7,  8,  2,  5, 12, 11,  1, 12, 10,  4, 14, 15,  9,
            10,  3,  6, 15,  9,  0,  0,  6, 12, 10, 11,  1,  7, 13, 13,  8,
            15,  9,  1,  4,  3,  5, 14, 11,  5, 12,  2,  7,  8,  2,  4, 14  },
 
    /* table S[5] */
        {   10, 13,  0,  7,  9,  0, 14,  9,  6,  3,  3,  4, 15,  6,  5, 10,
             1,  2, 13,  8, 12,  5,  7, 14, 11, 12,  4, 11,  2, 15,  8,  1,
            13,  1,  6, 10,  4, 13,  9,  0,  8,  6, 15,  9,  3,  8,  0,  7,
            11,  4,  1, 15,  2, 14, 12,  3,  5, 11, 10,  5, 14,  2,  7, 12  },
 
    /* table S[6] */
        {   15,  3,  1, 13,  8,  4, 14,  7,  6, 15, 11,  2,  3,  8,  4, 14,
             9, 12,  7,  0,  2,  1, 13, 10, 12,  6,  0,  9,  5, 11, 10,  5,
             0, 13, 14,  8,  7, 10, 11,  1, 10,  3,  4, 15, 13,  4,  1,  2,
             5, 11,  8,  6, 12,  7,  6, 12,  9,  0,  3,  5,  2, 14, 15,  9  },
 
    /* table S[7] */
        {   14,  0,  4, 15, 13,  7,  1,  4,  2, 14, 15,  2, 11, 13,  8,  1,
             3, 10, 10,  6,  6, 12, 12, 11,  5,  9,  9,  5,  0,  3,  7,  8,
             4, 15,  1, 12, 14,  8,  8,  2, 13,  4,  6,  9,  2,  1, 11,  7,
            15,  5, 12, 11,  9,  3,  7, 14,  3, 10, 10,  0,  5,  6,  0, 13  }
};
 
 
 
 
/**********************************************************************/
/*                                                                    */
/*                             DES CODE                               */
/*                                                                    */
/**********************************************************************/
 
/*=============================================================================================
                                     ---EncryptDES---
                                   Fonction de Cryptage
                Cette fonction crypte des blocks de 64bits en utilisant DES
  =============================================================================================*/
 
void EncryptDES(bool key[56], bool outBlk[64], bool inBlk[64], int verbose) {
  int i,round;
  bool R[32], L[32], fout[32];
  bool roundKey[56];
 
  EnableDumpBin = verbose;                       /* Flag de débogage sur On/Off */
  DumpBin("input(left)", inBlk+32, 32);
  DumpBin("input(right)", inBlk, 32);
  DumpBin("raw key(left )", key+28, 28);
  DumpBin("raw key(right)", key, 28);
 
  /*Réalise la permutation de choix 1 sur la clé*/
  ComputeRoundKey(roundKey, key);
 
  DumpBin("roundKey(L)", roundKey+28, 28);
  DumpBin("roundKey(R)", roundKey, 28);
 
  /*Réalise la permutation initiale sur le block de texte clair de 64 bits et sépare le résultat
        en deux parties Left et Right  */
  ComputeIP(L,R,inBlk);
 
  DumpBin("after IP(L)", L, 32);
  DumpBin("after IP(R)", R, 32);
 
  /* Boucle for qui parcours les 16 rounds */
  for (round = 0; round < 16; round++) {
    if (verbose)
      printf("-------------- BEGIN ENCRYPT ROUND %d -------------\n", round);
    DumpBin("round start(L)", L, 32);
    DumpBin("round start(R)", R, 32);
 
    /* Chaque partie de la clé est décalé de 1 ou 2 bits (dépend du round) à  gauche */
    RotateRoundKeyLeft(roundKey);
    if (round != 0 && round != 1 && round != 8 && round != 15)
      RotateRoundKeyLeft(roundKey);
    DumpBin("roundKey(L)", roundKey+28, 28);
    DumpBin("roundKey(R)", roundKey, 28);
 
    /* Entrée dans l'itération */
    ComputeF(fout, R, roundKey);
    DumpBin("f(R,key)", fout, 32);
    for (i = 0; i < 32; i++)
      L[i] ^= fout[i];
    DumpBin("L^f(R,key)", L, 32);
        
        /*Fonction d'échange de Left et Right*/
    Exchange_L_and_R(L,R);
 
    DumpBin("round end(L)", L, 32);
    DumpBin("round end(R)", R, 32);
    if (verbose)
      printf("--------------- END ROUND %d --------------\n", round);
  }
  /*Fin des 16 rounds*/
  
  /*Fonction d'échange de Left et Right*/
  Exchange_L_and_R(L,R);
 
  /* Concaténation de Left et Right et exécution de la permutation finale */
  ComputeFP(outBlk,L,R);
  DumpBin("FP out( left)", outBlk+32, 32);
  DumpBin("FP out(right)", outBlk, 32);
}
 
/* FIN DE LA FONCTION DE CRYPTAGE DES*/
 
/*=============================================================================================
                                     ---DecryptDES---
                                  Fonction de décryptage
               Cette fonction décrypte des blocks de 64bits en utilisant DES
  =============================================================================================*/
 
void DecryptDES(bool key[56], bool outBlk[64], bool inBlk[64], int verbose) {
  int i,round;
  bool R[32], L[32], fout[32];
  bool roundKey[56];
 
  EnableDumpBin = verbose;                      /* Flag de débogage sur On/Off */
  DumpBin("input(left)", inBlk+32, 32);
  DumpBin("input(right)", inBlk, 32);
  DumpBin("raw key(left )", key+28, 28);
  DumpBin("raw key(right)", key, 28);
 
  /*Réalise la permutation de choix 1 sur la clé*/
  ComputeRoundKey(roundKey, key);
 
  DumpBin("roundKey(L)", roundKey+28, 28);
  DumpBin("roundKey(R)", roundKey, 28);
 
  /*Réalise la permutation initiale sur le block de texte clair de 64 bits et sépare le résultat
        en deux parties Left et Right  */
  ComputeIP(L,R,inBlk);
 
  DumpBin("after IP(L)", L, 32);
  DumpBin("after IP(R)", R, 32);
 
  /*Boucle for qui parcours les 16 rounds */
  for (round = 0; round < 16; round++) {
    if (verbose)
      printf("-------------- BEGIN DECRYPT ROUND %d -------------\n", round);
    DumpBin("round start(L)", L, 32);
    DumpBin("round start(R)", R, 32);
 
    /*Execute la fonction computeF et effectue un XOR entre la sortie et Left*/
    ComputeF(fout, R, roundKey);
    DumpBin("f(R,key)", fout, 32);
    for (i = 0; i < 32; i++)
      L[i] ^= fout[i];
    DumpBin("L^f(R,key)", L, 32);
 
    Exchange_L_and_R(L,R);
 
    /*Chaque partie de la clé est décalé de 1 ou 2 bits (dépend du round) à  gauche */
    DumpBin("roundKey(L)", roundKey+28, 28);
    DumpBin("roundKey(R)", roundKey, 28);
    RotateRoundKeyRight(roundKey);
    if (round != 0 && round != 7 && round != 14 && round != 15)
      RotateRoundKeyRight(roundKey);
 
    DumpBin("round end(L)", L, 32);
    DumpBin("round end(R)", R, 32);
    if (verbose)
      printf("--------------- END ROUND %d --------------\n", round);
  }
  /*Fin des 16 rounds*/
  
  /*Fonction d'échange de Left et Right*/
  Exchange_L_and_R(L,R);
 
  /* Concaténation de Left et Right et exécution de la permutation finale */
  ComputeFP(outBlk,L,R);
  DumpBin("FP out( left)", outBlk+32, 32);
  DumpBin("FP out(right)", outBlk, 32);
}
/* FIN DE LA FONCTION DE DECRYPTAGE DES*/
 
/*=============================================================================================
                                     DEFINITION DES FONCTIONS
  =============================================================================================*/
 
 
 
/*
 *  ComputeRoundKey: Execute la permutation de choix 1 sur la clé et stocke le résultat dans roundkey
 */
static void ComputeRoundKey(bool roundKey[56], bool key[56]) {
  int i;
 
  for (i = 0; i < 56; i++)
    roundKey[table_DES_PC1[i]] = key[i];
}
 
/*--------------------------------------------------------------------------------------------------*/
 
/*
 *  RotateRoundKeyLeft: rotation de chaque partie (de28bits) de la clé de 1 bits à gauche
 */
static void RotateRoundKeyLeft(bool roundKey[56]) {
  bool temp1, temp2;
  int i;
 
  temp1 = roundKey[27];
  temp2 = roundKey[55];
  for (i = 27; i >= 1; i--) {
    roundKey[i] = roundKey[i-1];
    roundKey[i+28] = roundKey[i+28-1];
  }
  roundKey[ 0] = temp1;
  roundKey[28] = temp2;
}
 
/*--------------------------------------------------------------------------------------------------*/
 
/*
 *  RotateRoundKeyRight: rotation de chaque partie (de28bits) de la clé de 1 bits à  gauche
 */
static void RotateRoundKeyRight(bool roundKey[56]) {
  bool temp1, temp2;
  int i;
 
  temp1 = roundKey[0];
  temp2 = roundKey[28];
  for (i = 0; i < 27; i++) {
    roundKey[i] = roundKey[i+1];
    roundKey[i+28] = roundKey[i+28+1];
  }
  roundKey[27] = temp1;
  roundKey[55] = temp2;
}
 
/*--------------------------------------------------------------------------------------------------*/
 
/*
 *  ComputeIP: Réalise la permutation initiale et découpe le block de 64 bits
 *       en deux parties de 32 bits Left et Right
 */
static void ComputeIP(bool L[32], bool R[32], bool inBlk[64]) {
  bool output[64];
  int i;
 
  /* Permutation
   */
  for (i = 63; i >= 0; i--)
    output[table_DES_IP[i]] = inBlk[i];
 
  /* Découpage entre Left et Right:   Les bits 63 à  32 vont à  gauche, les bits 31 à  0 à  droite.
   */
  for (i = 63; i >= 0; i--) {
    if (i >= 32)
      L[i-32] = output[i];
    else
      R[i] = output[i];
  }
}
 
/*--------------------------------------------------------------------------------------------------*/
 
/*
 *  ComputeFP: Concaténation de Left et Right et execution de la permutation finale
 */
static void ComputeFP(bool outBlk[64], bool L[32], bool R[32]) {
  bool input[64];
  int i;
 
  /* Concaténation de Left et Right dans une entrée de 64 bits
   */
  for (i = 63; i >= 0; i--)
    input[i] = (i >= 32) ? L[i - 32] : R[i];
 
  /* Permutation
   */
  for (i = 63; i >= 0; i--)
    outBlk[table_DES_FP[i]] = input[i];
}
 
/*--------------------------------------------------------------------------------------------------*/
 
/*
 *  ComputeF: Execution du cryptage DES et stockage du résultat dans fout
* Cette fonction est le traitement qui à  lieu dans UNE SEULE itération
*/
/* ----------------------DEBUT DE LA FONCTION COMPUTE F --------------------------------*/
 
static void ComputeF(bool fout[32], bool R[32], bool roundKey[56]) {
  bool expandedBlock[48], subkey[48], sout[32];
  int i,k;
 
  /* Expansion de Right en 48 bits via la fonction "ComputeExpansionE"*/
  ComputeExpansionE(expandedBlock, R);
  DumpBin("expanded E", expandedBlock, 48);
 
  /* Conversion de la clé de 56bits en sous-clé de 48 bits */
  ComputePC2(subkey, roundKey);
  DumpBin("subkey", subkey, 48);
 
  /* XOR de 48bits entre la  sous-clé et le texte expansé*/
  for (i = 0; i < 48; i++)
    expandedBlock[i] ^= subkey[i];
 
  /* Le résultat du XOR est divisé en 8 partie de 6 bits qui sont traités dans les S-Box
               Les 8 S-Box ressortent chacun 4 bits qui forment un block de 32bits                            */
  for (k = 0; k < 8; k++)
    ComputeS_Lookup(k, sout+4*k, expandedBlock+6*k);
 
  /* Appel de la fonction de permutation "ComputeP" ci-dessous */
  ComputeP(fout, sout);
}
/* ----------------------FIN DE LA FONCTION COMPUTE F --------------------------------*/
 
/*--------------------------------------------------------------------------------------------------*/
 
/*
 *  ComputeP: Réalise une permutation en sortie des S-Box via le tableau "table_DES_P[32]"
 */
static void ComputeP(bool output[32], bool input[32]) {
  int i;
 
  for (i = 0; i < 32; i++)
    output[table_DES_P[i]] = input[i];
}
 
/*--------------------------------------------------------------------------------------------------*/
 
/*
 *  Fonction S-Box
 * Cette fonction définie le traitement effectuée sur les block de 6 bits
 * Elle renvoie des block de 4 bits, soit un entier entre 0 et 15
 */
static void ComputeS_Lookup(int k, bool output[4], bool input[6]) {
  int inputValue, outputValue;
 
  /* conversion des block en entrée en entier */
  inputValue = input[0] + 2*input[1] + 4*input[2] + 8*input[3] +
          16*input[4] + 32*input[5];
 
  /* Recherche la valeur dans la S-Box numéro "k" - k de 0 à 7 */
  outputValue = table_DES_S[k][inputValue];
 
  /* Conversion du résultat en forme binaire */
  output[0] = (outputValue & 1) ? 1 : 0;
  output[1] = (outputValue & 2) ? 1 : 0;
  output[2] = (outputValue & 4) ? 1 : 0;
  output[3] = (outputValue & 8) ? 1 : 0;
}
 
/*--------------------------------------------------------------------------------------------------*/
 
/*
 *  ComputePC2: Permutation de choix 2- conversion d'une clé de 56 bits en 48 bits
 */
static void ComputePC2(bool subkey[48], bool roundKey[56]) {
  int i;
 
  for (i = 0; i < 48; i++)
    subkey[i] = roundKey[table_DES_PC2[i]];
}
 
/*--------------------------------------------------------------------------------------------------*/
 
/*
 *  ComputeExpansionE: Expansion du bloc de bits de 32 bits en 48 bits
 *  via le tableau "table_DES_E[48]"
 */
static void ComputeExpansionE(bool expandedBlock[48], bool R[32]) {
  int i;
 
  for (i = 0; i < 48; i++)
    expandedBlock[i] = R[table_DES_E[i]];
}
 
/*--------------------------------------------------------------------------------------------------*/
 
/*
 *  Exchange_L_and_R:  Echange entre les block Right et Left
 */
static void Exchange_L_and_R(bool L[32], bool R[32]) {
  int i;
 
  for (i = 0; i < 32; i++)
    L[i] ^= R[i] ^= L[i] ^= R[i];                 /* Echange de L[i] et R[i] */
}
 
/*--------------------------------------------------------------------------------------------------*/
 
/*
 *  DumpBin: Renvoie les valeurs intermédiaires si enableDumpBin est activé.
 */
static void DumpBin(char *str, bool *b, int bits) {
  int i;
/*Contrôle d'erreur d'appel*/
  if ((bits % 4)!=0 || bits>48) {
    printf("Bad call to DumpBin (bits > 48 or bit len not a multiple of 4\n");
    exit(1);
  }
 
/*Si DumpBin est activé*/
  if (EnableDumpBin) {
    for (i = strlen(str); i < 14; i++)
      printf(" ");
    printf("%s: ", str);
    for (i = bits-1; i >= 0; i--)
      printf("%d", b[i]);
    printf(" ");
    for (i = bits; i < 48; i++)
      printf(" ");
    printf("(");
    for (i = bits-4; i >= 0; i-=4)
      printf("%X", b[i]+2*b[i+1]+4*b[i+2]+8*b[i+3]);
    printf(")\n");
  }
}
/*-------------------------------------------FIN----------------------------------------------------*/