Jadis, la cryptographie, la science du secret, a �t� strictement r�serv�e aux milieux diplomatiques et militaires pendant plus de 3000 ans. Mais avec le d�veloppement de l?informatique et l?�volution des r�seaux de communications, elle s?est impos�e dans tous les domaines. Cependant, les vrais algorithmes de chiffrement sont peu nombreux, citons-en quelques exemples�:

DES (Florin et Natkin, 2002), algorithme sym�trique, mis au point en 1973, dont la cl� secr�te est de 64 bits. Une recherche exhaustive de la cl� (1998) a permis aux crypto-analyseurs de casser ce fameux algorithme.

AES (Stinson, 2003), d�velopp� en 1997, a remplac� le DES. Il est sym�trique et peut supporter des cl�s de longueurs �gales � 128, 192 et 256 bits.

IDEA (Florin et Natkin, 2002), algorithme sym�trique, assez r�cent, avec une cl� de 128 bits.

RSA (Labouret, 2001), mis au point en 1970, est asym�trique et se base sur l?arithm�tique modulaire pour d�finir sa cl� publique et sa cl� priv�e. Cet algorithme r�siste toujours � la cryptanalyse.

Le PGP (Menezes, Oorschot et al., 1996) et (Manuel PGP 1998), mis au point en 1992, est une combinaison des meilleures fonctionnalit�s de la cryptographie asym�trique et de la cryptographie conventionnelle. PGP est un syst�me hybride, il est actuellement, le crypto-syst�me dominant.

Parall�lement, les domaines d?application des algorithmes �volutionnistes n?ont cess� de s?�largir gr�ce � leur grande efficacit� (rapidit�, simplicit� de leurs op�rateurs?). Ceci nous a incit�s � concevoir et � r�aliser un syst�me de chiffrement fond� sur les techniques des algorithmes �volutionnistes.

Cet article est structur� comme suit�: dans la section 2, nous avons ramen� le probl�me de chiffrement d?un message M � un probl�me d?optimisation. Ensuite, nous avons d�fini un codage adapt� du probl�me, permettant ainsi une r�solution qui s?inspire de celle du probl�me de voyageur du commerce (Caux, Pierreval et al. 1995) (en anglais TSP). Puis, nous avons construit notre algorithme en d�finissant la fonction d?�valuation ad�quate, en pr�cisant la nature des individus aptes � la s�lection et en choisissant les op�rateurs g�n�tiques adapt�s � ce probl�me. Le processus de d�chiffrement est d�taill� dans la section 3 et les r�sultats exp�rimentaux des diff�rents exemples trait�s sont pr�sent�s dans la section 4. Dans la section 5, nous pr�sentons les avantages de notre algorithme en comparaison avec des algorithmes importants du domaine de la cryptographie, avant de conclure en section 6.

Soit M₀ le message � chiffrer. M₀ est une suite de l caract�res. Ces derniers appartiennent � l?ensemble des 256 caract�res du code ASCII .

Il est � noter que ce message peut �tre form� uniquement par des nombres (par exemple des codes bancaires d?un certain nombre de personnes), comme il peut �tre un m�lange de nombres et de phrases litt�raires y compris la ponctuation, etc.

Nous appliquons d?abord � M₀ un brouillage. Ce dernier peut �tre effectu� par combinaison de plusieurs m�thodes simples comme les substitutions, les permutations, le chiffrement affin�, etc. Cela n�cessite une cl� secr�te sym�trique. Le message brouill� sera d�sign� par M.

Soient c₁,c₂,?,c_m les diff�rents caract�res de M (l<=m<=256). D�signons par L_i (1<=i<=m) la liste des diff�rentes positions du caract�re c_i dans M avant le chiffrement et par card(L_i) le nombre des occurrences de c_i dans M.

L₁, L₂,?, L_m est une partition de l?ensemble {1, 2, ?, m}.

Le message M peut �tre repr�sent� par le vecteur ci-dessous�:

Le but de notre travail est de modifier le plus possible les fr�quences d?apparition des caract�res dans le message M et d?�tablir le plus de d�sordre dans leurs positions. Pour cela, nous changeons it�rativement la r�partition des listes sur les diff�rents caract�res de M de telle mani�re que la diff�rence entre le cardinal de la nouvelle liste L?_i affect�e au caract�re c_i et le cardinal de la liste initiale L_i soit maximale. Il s?agit ainsi d?un probl�me d?optimisation. Or, les algorithmes �volutionnistes sont tr�s efficaces pour la r�solution de ce genre de probl�me. Nous avons choisi de les utiliser, notamment ceux appliqu�s aux probl�mes de permutations (Caux, Pierreval et al. 1995). Ces algorithmes se pr�sentent sous plusieurs versions, la plus utilis�e est celle d�crite en section 2.2.

• Etape 0 : D�finir un codage du probl�me

• Etape 1 : Cr�er une population initiale P₀ de q individus{X₁, X₂, ?,X_q}
  i := 0

• Etape 2 : Evaluation des individus

• Soit F la fonction d?�valuation. Calculer F(X_i) pour chaque individu X_i de P_i

• Etape 3 : S�lection
  S�lectionner les meilleurs individus (au sens de F) et les grouper par paire.

• Etape 4 : Application des op�rateurs g�n�tiques
  1-Croisement�: Appliquer l?op�ration de croisement aux paires s�lectionn�es
  2-Mutation�: Appliquer la mutation aux individus issus du croisement

• Ranger les nouveaux individus obtenus de 1 et 2, dans une nouvelle g�n�ration P_i+1

• R�p�ter les �tapes 2, 3 et 4 jusqu?� l?obtention du degr� de performance souhait�.

Notre syst�me de chiffrement est d�compos� en quatre �tapes�:

• codage,

• cr�ation de la population initiale P_0�;

• �valuation des individus,

• s�lection des meilleurs individus,

• applications des op�rateurs g�n�tiques.

Nous les commentons dans ce qui suit.

Etape 0�: Codage

Un individu (ou chromosome) est un vecteur de taille m. Les g�nes sont les listes L_pi (1<=i<=m). Le i^e g�ne L_pi contient les nouvelles positions que prendra le caract�re c_i.

Etape 1�: Cr�ation de la population initiale

La population initiale P₀ est compos�e de q individus�(X₁,X₂,?,X_q). Nous d�signons par ��Original-Ch�� le chromosome dont les g�nes sont les listes L₁,L₂,?,L_m (plac�s dans cet ordre) repr�sentant le message avant l?application de l?algorithme.

Nous appliquons q permutations sur ��Original-Ch�� afin d?obtenir une population initiale constitu�e de q solutions potentielles au probl�me. i�:=0.

Etape 2�: Evaluation des individus

Soit X_j un individu de P_i dont les g�nes sont L_j1,L_j2,?,L_jm.

Nous d�finissons la fonction d?�valuation F sur l?ensemble des individus X_j par�:

Etape 3�: S�lection des meilleurs individus

Nous utilisons la m�thode classique de la roulette (Florin et Natkin, 2002) permettant de retenir les individus les�plus forts. Le processus utilis� est rappel� dans ce qui suit :

A chaque individu X_i est affect� une probabilit� d?apparition ou force relative p(X_i) calcul� selon [2].

La probabilit� d?apparition cumul�e d?un individu X_{i �}not�e q_i est calcul�e selon [3].

Soit r un nombre al�atoire compris entre 0 et 1, l?individu s�lectionn� est donn� en [4].

Ce processus est r�p�t� q fois. Avec ce principe, un individu fort peut �tre s�lectionn� plusieurs fois. Par contre, un individu faible a moins de chance d?�tre s�lectionn�.

Nous introduisons ensuite une fonction de contr�le qui �limine les individus pour lesquels seulement une minorit� de g�nes ont chang� de valeur par rapport au chromosome initial�Original-Ch. Puisque nous nous sommes ramen�s � un probl�me de permutations avec contraintes, nous appliquons alors les op�rateurs g�n�tiques adapt�s � ce genre de probl�me.

Etape 4�: Applications des op�rateurs g�n�tiques

Cette �tape est effectu�e gr�ce au croisement MPX�et la mutation de transposition�que nous d�crivons ci-dessous.

Croisement MPX�(Maximal Preservative X)�

Ce croisement a �t� propos� par (M�hlenbein et Schlierkamp-Voosen, 1993) pour le probl�me du voyageur de commerce. L?id�e de cet op�rateur est d?ins�rer une partie du chromosome d?un parent dans le chromosome de l?autre parent de telle fa�on que le croisement r�sultant soit le plus proche possible de ses parents. C?est un croisement � deux points. Les deux fils sont obtenus de mani�re sym�trique. Nous en illustrons le fonctionnement par l?exemple ci-dessous.

La zone de croisement est comprise entre les positions 5 et 9. La premi�re �tape consiste � recopier la zone de croisement du parent1 sur le fils1. Ensuite, les g�nes du fils1 qui ne sont pas dans la zone de croisement sont compl�t�s comme suit.

Le i^� g�ne du parent2 est recopi� sur le i^� g�ne du fils1 si cette copie respecte les contraintes (ne cr�e pas une tourn�e incoh�rente). Dans le cas contraire, le i^� g�ne du parent1 est recopi� sur le i^� g�ne du fils1 si cette copie ne cr�e pas de doublons. Si les deux cas pr�c�dents ne peuvent pas s?appliquer, le i^� g�ne du fils1 re�oit un g�ne de la zone de croisement du parent2 qui respecte les contraintes (premier non pris).

Ce croisement est appliqu� aux individus s�lectionn�s avec un taux bien pr�cis. D?apr�s (Labouret, 2001) le meilleur taux est de l?ordre de 60% � 100%.

Mutation de transposition�

Nous choisissons la mutation qui consiste � permuter al�atoirement deux g�nes d?un chromosome. Cet op�rateur est appliqu� aux individus issus du croisement avec un taux adapt�, de pr�f�rence de 0,1% � 5% (Labouret, 2001). Le processus est d�crit dans ce qui suit.

• Placer la nouvelle prog�niture dans une nouvelle population P_i+1.

• R�p�ter les �tapes 2, 3 et 4 jusqu?� un crit�re d?arr�t.

• D�finir la condition d?arr�t exprim�e � l?aide de la fonction F (cf. [1]). Cette fonction F est born�e car 0 <= F(X) <= 2*l pour tout individu X, en fait�:
  [5]
  Th�oriquement, la fonction F admet un maximum puisqu?elle est born�e. D?apr�s Khan Phang (Khan Phang, 1988), la convergence d?une fonction d?�valuation est assur�e. Elle peut �tre vers une valeur proche de Max, d�termin�e exp�rimentalement. En fait, les exp�riences que nous avons entam�es et que nous interpr�terons par la suite nous ont permis de confirmer ce r�sultat.

• Derni�re phase de l?algorithme�: d�signons par ��Final-Ch�� la solution finale donn�e par notre algorithme �volutionniste. A partir de ��Original-Ch�� et ��Final-Ch��, nous construisons notre cl� sym�trique. Cette cl� sera appel�e cl� g�n�tique.

Le d�chiffrement du message chiffr� M? se fait en deux �tapes�:

Etape 1

Dans cette �tape, nous repr�sentons le texte chiffr�, par un vecteur de listes comme nous l?avons fait pour le message en clair. D�signons par c?₁, c?₂, ?, c?_m les diff�rents caract�res de M? et par L?₁, L?₂?, L?_m leurs listes respectives de position dans M?. Gr�ce � la cl� g�n�tique, les caract�res vont retrouver leurs listes de position correspondantes dans le message en clair. En effet, la cl� est une permutation de {1,2,?,m} que nous pouvons repr�senter par un vecteur not� ��Clef��, de taille m telle que�:

Ainsi, nous obtenons le message M.

Etape 2

Dans cette seconde �tape, nous proc�dons au d�chiffrement de M pour obtenir M₀. Le passage de M₀ � M se fait par le biais d?op�rations ou fonctions simples de la cryptographie (substitution simple, d�calage, chiffrement affin�?) et dont la cl� est secr�te et sym�trique.

Nous avons appliqu� notre algorithme sur des messages de diff�rentes tailles. Nous n?avons retenu que quatre exemples mod�les. Pour chacun, nous avons ex�cut� l?application pour diff�rentes tailles de population et nous en avons retenu les meilleures. Puis dans un tableau r�capitulatif, nous avons enregistr� les r�sultats importants, � savoir�: valeur de la convergence de la fonction d?�valuation, nombre de g�n�rations atteint lors de cette convergence.

Le brouillage utilis� pour les quatre messages ci-dessous est�un chiffrement affin�d�fini par F(x)= ax + b o� a = -1, b = 255 et x = code ASCII du caract�re du message initial.

Pour la plupart des exemples trait�s dans nos exp�riences, nous constatons que les meilleures valeurs de l?optimum (valeur de convergence) sont atteintes pour une population de taille 24 (message 2 et message 3 dans figure1). Dans certains cas, les tailles 30 et 32 ont donn� de bons r�sultats, mais le nombre de g�n�rations dans ce cas a doubl�, ce qui se traduit par un co�t suppl�mentaire en terme de temps. Nous conseillons donc de choisir 24 comme taille de la population.

Nous citerons, dans la section 5, �les quatre messages mod�les et expliciterons les op�rations utilis�es pour brouiller le message et la cl� de session g�n�r�e par notre algorithme �volutionniste.

Nous comparons notre algorithme avec l?un des algorithmes sym�triques les plus connus, le DES.

En g�n�ral, les algorithmes sym�triques les plus connus (DES, IDEA, AES) font des chiffrements par blocs. Le n�tre chiffre le message tout entier en une seule prise, ce qui est moins co�teux.

Le DES a une cl� de 64 bits (mais ne sont utilis�s que les 56 bits). Cette taille si petite a favoris� son attaque par une recherche exhaustive de la cl� (ou attaque par force brute). Dans notre algorithme, nous pouvons toujours supposer que le message contient plus de 30 caract�res diff�rents, donc la taille de la cl� est au moins �gale � 240 bits, taille r�sistante actuellement aux attaques. Dans le cas o� le texte contient moins de vingt diff�rents caract�res nous pouvons le compl�ter par d?autres. En outre, notre cl� est une cl� de session (variable d?un message � l?autre) et est g�n�r�e par notre propre algorithme. Par contre, celle du DES ne l?est pas. Or, les cl�s de session sont plus r�sistantes aux attaques que les autres.

Autre point important � �voquer, on peut penser � une crypto-analyse par l?�tude des fr�quences d?apparition des caract�res dans le message. Ce genre d?attaque s?appuie sur des �tudes en linguistique d�terminant les fr�quences d?apparition des lettres d?un texte �crit dans une langue naturelle. Or, rappelons que nos messages ne sont pas exclusivement des messages litt�raux sans ponctuation,�ils peuvent contenir tous les caract�res possibles du code ASCII. Puisqu?il n?y a aucune �tude des fr�quences de tous les caract�res du code ASCII, une attaque de ce genre est � rejeter, d?autant plus que le brouillage initial que nous avons effectu� rend l?attaque plus difficile puisque le crypto-analyste ne peut avoir une id�e pr�alable sur les types des caract�res du message.

Notre travail a apport� deux contributions simultan�es. La premi�re est l?�largissement de l?espace d?application des algorithmes �volutionnistes. Ces derniers n?ont prouv� leur efficacit� qu?en crypto-analyse. En fait, l?unique et le meilleur algorithme de chiffrement asym�trique ��Knapsack cipher�� (Muller, 2003), inspir� de la r�solution du probl�me du sac � dos, a �t� attaqu� en utilisant les algorithmes g�n�tiques. La deuxi�me contribution est la conception d?une nouvelle formalisation du probl�me de chiffrement par l?innovation d?un algorithme de chiffrement �volutionniste. Ce dernier b�n�ficie de tous les avantages des algorithmes �volutionnistes (faible co�t, simplicit� des op�rations, performance?) et poss�de des qualit�s que nous avons mentionn�es dans la discussion ci-dessus. Toutefois, montrer qu?un syst�me de chiffrement est s�r reste une t�che tr�s d�licate (except� le syst�me � masque jetable). La plupart des crypto-analystes pensent m�me que tous les algorithmes de chiffrement sont cassables � long terme,�mais l?essentiel est de concevoir son syst�me de chiffrement de telle mani�re que la dur�e de vie souhait�e pour le texte chiffr� soit inf�rieure � celle mise par le crypto-analyste pour casser ce syst�me.