UNIVERSITÉ MOHAMMED V – AGDAL

FACULTÉ DES SCIENCES

Rabat
N° d’ordre 2311

THÈSE DE DOCTORAT D’ETAT

Présentée par

OMARY FOUZIA

Spécialité : Informatique

Titre : Applications des algorithmes évolutionnistes

à la cryptographie

Soutenue le 20 juillet 2006

Devant le jury

Président :
Mr Abdelhak Mouradi PES et Directeur à l’Ecole Nationale des Systèmes
d’Information et d’Analyse des Systèmes.

Examinateurs :
Aboubakr Lbekkouri PES à la Faculté des Sciences de Rabat.
Safwan Benjelloun Ex. PES à la Faculté des Sciences de Rabat.
Mohammed Benkhalifa PES à la Faculté des Sciences de Rabat.
Abdelghani Bellaachia Professeur à l’Université de Georges Washington
aux Etats Unis.
Zouhair Guenoun PES à l’Ecole Mohammadia d’Ingénieurs de Rabat.

Faculté des Sciences, 4 Avenue Ibn Battouta B.P. 1014 RP, Rabat – Maroc
Tel +212 (0) 37 77 18 34/35/38, Fax : +212 (0) 37 77 42 61, [Link]
 RESUME

APPLICATIONS DES ALGORITHMES EVOLUTIONNISTES A

LA CRYPTOGRAPHIE

Cette thèse présente trois différents systèmes de chiffrement ayant tous le même outil de
base : les algorithmes évolutionnistes. Ce sont des systèmes symétriques générant leurs
propres clés (secrètes) de session. Le problème de chiffrement a été formalisé de la même
manière dans les trois systèmes. En fait, nous avons réussi à le ramener à un problème
d’optimisation combinatoire et fait appel aux algorithmes évolutionnistes pour le résoudre.

Dans le premier système, l’objectif principal est d’établir un échange des positions et des
fréquences d’apparition des différents caractères du message. Cet échange se fait par le biais
d’un algorithme évolutionniste dont nous avons défini les composantes de base adaptées à
notre problème.

Le deuxième système est une amélioration du premier, par la conception d’une nouvelle
méthode de chiffrement permettant de modifier les valeurs des fréquences d’apparition des
caractères du message. Cette méthode a l’avantage de réaliser un pré-chiffrement pour
notre algorithme évolutionniste. En fait, elle permet d’une part de générer une population
initiale plus intéressante et d’autre part d’augmenter davantage la résistance du premier
système.

Dans le troisième système une seconde amélioration du premier intervient au niveau de la

population finale. Il s’agit d’une nouvelle technique de chiffrement ayant pour but
d’équilibrer les fréquences d’apparition des caractères du texte chiffré par l’algorithme
évolutionniste. Cela renforcera davantage la résistance contre de redoutables attaques. Des
applications ont été faites pour les trois systèmes.

Mots clés : optimisation combinatoire, algorithmes évolutionnistes, cryptographie,

chiffrement, chiffrement symétrique, clé, cryptanalyse.
 DEDICACES

Mes chers Parents

Mes chers enfants

Mon cher mari

Mes chères sœurs

Mes chers frères

Et en particulier

A
 REMERCIEMENTS

Les travaux présentés dans ce mémoire ont été effectués au sein du laboratoire
d’Informatique de la faculté des Sciences de Rabat, du laboratoire de l’Ecole Hassania des
travaux publics de Casa et du laboratoire de mathématiques appliquées à Pas-de-Calais
(Université de Lille), sous la direction de Mr Aboubaker Lbekkouri, Professeur à la faculté
des Sciences de Rabat, pour qui je tiens à exprimer ma profonde gratitude pour son
soutien et son aide précieux.
Par la même occasion, j’aimerais témoigner à mon co-encadrant Mr Safwan Benjelloun,
ex Professeur à la faculté des Sciences de Rabat, ma grande reconnaissance pour sa
collaboration si bénéfique et si motivante le long de ce travail.
Sans oublier notre cher Professeur et rapporteur de thèse Mr Abdelghani Bellaachia, de
l’université de George Washington, qui a tant sacrifié son temps pour m’aider. Ses conseils
et ses commentaires m’ont tellement guidée durant ce long parcours.
Aussi, je présente mes vifs remerciements et ma grande considération à Mr Mohammed
Benkhalifa, Professeur à la faculté des Sciences de Rabat, qui a accepté avec enthousiasme
d’être rapporteur de cette thèse et de faire partie du jury.
Mr le Professeur Abdelhak Mouradi et Directeur de l’ENSIAS, a bien voulu examiner ce
travail et être membre du jury, qu’il trouvera ici l’expression de mon profond respect et
mon sincère estime.
Mes remerciements s’adressent aussi à Mr Zouhair Guenoun, Professeur à l’Ecole
Mohammadia d’Ingénieurs, qui m’a fait l’honneur de participer au jury.
Enfin, je ne manque pas de remercier :
Notre invité, Mr le Professeur Abdelaaziz Sadok, Doyen de la faculté des sciences de Ain-
Chok pour son soutien et son aide le long de ce travail.
Mr le Professeur Hassan Sadok, Directeur de recherche du Laboratoire de mathématiques
appliquées de Pas-de-Calais qui m’a bien reçue et m’a aidée à franchir pas mal d’obstacles.
 TABLE DES MATIÈRES

Chapitre 1 1

Introduction générale
Chapitre 2 5

Les algorithmes évolutionnistes

I Introduction.............................................................................................................................6
II Algorithmes génétiques........................................................................................................6
II.1 Définition et origine ......................................................................................................6
II.2 Corps d’un algorithme génétique..............................................................................7
II.2.1 Codage ..................................................................................................................8
II.2.2 Construction de la population initiale.............................................................9
II.2.3 Evaluation des individus.....................................................................................9
II.2.4 Sélection ...............................................................................................................9
II.2.5 Opérateurs génétiques.......................................................................................11
II.2.6 Critère d’arrêt......................................................................................................13
II.2.7 Convergence .......................................................................................................13
III Naissance des algorithmes évolutionnistes....................................................................15
III.1 Les algorithmes génétiques parallèles ...................................................................16
III.2 Extension vers les problèmes d’optimisation .....................................................16
III.3 Extension vers les problèmes d’ordonnancement.............................................16
III.3.1 Codage ..............................................................................................................16
III.3.2 Opérateurs génétiques adaptés....................................................................18
IV Recommandations ...............................................................................................................20
Chapitre 3 22

La cryptographie
I Introduction.............................................................................................................................23
II Définitions :............................................................................................................................23
III Cryptographie classique......................................................................................................24
III.1 Le code de César.........................................................................................................24
III.2 Le carré de Polybe.....................................................................................................25
III.3 Chiffrement de Delastelle ........................................................................................25
III.4 le chiffre des templiers (ou de PigPen)..................................................................26
Sommaire

III.5 Le Chiffrement par décalage ..................................................................................27

III.5.1 Arithmétique modulaire..................................................................................27
III.5.2 Application......................................................................................................27
III.6 Le chiffrement affine ................................................................................................28
III.7 Le chiffrement de Hill .............................................................................................29
III.8 Le chiffrement de Vigenère.....................................................................................31
III.9 Le chiffrement par transposition (par permutation)...........................................32
III.10 Le chiffrement par substitution............................................................................33
III.11 Systèmes à clés jetables...........................................................................................35
IV Cryptographie moderne.....................................................................................................35
IV.1 Cryptographie symétrique.........................................................................................35
IV.1.1 DES ...................................................................................................................36
IV.1.2 IDEA.................................................................................................................44
IV.1.3 AES.....................................................................................................................47
IV.2 Cryptographie asymétrique .......................................................................................48
IV.2.1 Schéma ElGamal..............................................................................................49
IV.2.2 RSA....................................................................................................................53
IV.3 Cryptographie Hybride.............................................................................................57
IV.4 Cryptographie Quantique..........................................................................................58
IV.4.1 Introduction ......................................................................................................58
IV.4.2 Bases théoriques ...............................................................................................58
IV.4.3 Description du protocole................................................................................60
IV.5 Cryptographie par courbe elliptique ......................................................................61
IV.5.1 Addition de deux points..................................................................................61
IV.5.2 Multiplication d'un point par un nombre entier.......................................63
IV.5.3 Echange de clés ...............................................................................................63
IV.5.4 Sécurité.............................................................................................................63
IV.5.5 Inconvénients...................................................................................................63
V La cryptanalyse.......................................................................................................................64
V.1 Cryptanalyse linéaire ...................................................................................................64
V.2 Cryptanalyse différentielle ........................................................................................65
V.3 L'attaque boomerang..................................................................................................67
V.3.1 Description ........................................................................................................67
V.3.2 Les différentes étapes.......................................................................................67
Chapitre 4 69

Chiffrement évolutionniste
I Introduction.............................................................................................................................71
II Motivation................................................................................................................................72
II.1 Position du problème.................................................................................................72
II.2 Description de l’algorithme......................................................................................72
Corps de l’AE................................................................................................................72
Premier concept : Choix de la population initiale ..................................................73
Deuxième concept : Sélection des meilleurs individus..........................................73

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat ii

Sommaire

II.3 Discussion ....................................................................................................................75

III Description du système de chiffrement SEC................................................................75
III.1 Formalisation du problème ....................................................................................76
III.2 Notre système de chiffrement ...............................................................................76
IV Déchiffrement ......................................................................................................................78
V Expérimentation...................................................................................................................79
V.1 Les messages modèles................................................................................................79
V.2 Résultats retenus.........................................................................................................83
V.3 Interprétation.............................................................................................................83
VI Extension de SEC à des blocs binaires...........................................................................83
VI.1 Motivation...................................................................................................................83
VII.2 Description de la méthode.....................................................................................84
VII Discussion ...........................................................................................................................87
VIII Conclusion........................................................................................................................88
Chapitre 5 89

Chiffrement avec fusion

I Introduction............................................................................................................................90
II Description du système ESEC-1.......................................................................................90
II.1 Formalisation du problème.......................................................................................90
II.2 Système de chiffrement..............................................................................................90
II.2.1 Première partie: la fusion.................................................................................90
II.2.2 Deuxième partie : usage de l’algorithme évolutionniste...........................93
III Déchiffrement ......................................................................................................................94
IV Expérimentation .................................................................................................................95
Les messages modèles.........................................................................................................95
V Discussion.............................................................................................................................100
VI Conclusion ..........................................................................................................................101
Chapitre 6 102

Chiffrement avec fragmentation

I Introduction...........................................................................................................................103
II Description du système ESEC-2.....................................................................................103
II.1 Premier chiffrement .................................................................................................103
II.2 Fragmentation des listes ..........................................................................................103
II.2.1 Description informelle....................................................................................103
II.2.2 Description formelle .......................................................................................104
III Déchiffrement..................................................................................................................106
III.1 Premier déchiffrement.............................................................................................107
III.2 Second déchiffrement..............................................................................................107
IV Discussion et conclusion..................................................................................................112

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat iii

Sommaire

Chapitre 7 113

Analyse et comparaison des Systèmes

IDEA, RSA, PGP et SEC
I Introduction...........................................................................................................................114
II Implémentation du système IDEA...................................................................................114
Autres Résultats Expérimentaux ..................................................................................115
III Implémentation de RSA.................................................................................................117
III.1 Présentation de l’interface de RSA........................................................................117
III.2 Autres Résultats expérimentaux ...........................................................................117
IV Implémentation du PGP ...................................................................................................118
IV.1 Présentation de l’interface de PGP .......................................................................119
IV.2 Résultats expérimentaux..........................................................................................119
V Implémentation de notre algorithme SEC ......................................................................120
V.1 Présentation de l’interface de SEC.........................................................................120
V.2 Résultats expérimentaux ..........................................................................................121
VI Comparaison et analyse .....................................................................................................121
VI.1 Comparaison entre les algorithmes modernes et l’algorithme
évolutionniste .....................................................................................................................121
VI.2 Discussions ...............................................................................................................122

Conclusion générale
I Limites de nos travaux .........................................................................................................123
II Perspectives ..........................................................................................................................124

Bibliographie

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat iv

Sommaire

TABLE DES ILLUSTRATIONS

Titre Page
Figure 2.1 : Un algorithme génétique ......................................................................................................8
Figure 2.2 : Croisement '1-point'...........................................................................................................12
Figure 2.3 : Croisement ‘2-points’........................................................................................................13
Table 3.1 : Le chiffrement de César.......................................................................................................25
Table 3.2 : La grille de Polybe.................................................................................................................25
Table 3.3 : Un chiffrement de Delastelle...........................................................................................26
Figure 3.1: Le chiffrement de PigPen....................................................................................................26
Table 3.4 : Un chiffrement par décalage ...............................................................................................27
Table 3.5 : Un chiffrement affine...........................................................................................................29
Table 3.6 : Un déchiffrement affine.......................................................................................................29
Table 3.7 : Un chiffrement de Hill.........................................................................................................30
Table 3.8 : Un déchiffrement de Hill.....................................................................................................31
Table 3.9 : Un chiffrement de Vigenère................................................................................................31
Figure 3.2 : Le cylindre de Scytale..........................................................................................................32
Figure 3.3 : Fréquences des lettres en Français. ..................................................................................34
Figure 3.4: Algorithme de chiffrement symétrique.............................................................................36
Table 3.10 : Les permutations CP1 et CP2 .........................................................................................38
Table 3.11 : La table des décalages à gauche LS.................................................................................38
Figure 3.5 : La diversification des clés en DES ...................................................................................39
Figure 3.6 : Enchaînement des opérations de chiffrement dans le système DES ........................41
Table 3.12 :La permutation initiale: PI et son inverse PI-1...............................................................42
Table 3.13 : les S-Boxes............................................................................................................................42
Figure 3.7 : Description de l’opération Dn=Gn-1 ⊕ F(Dn-1,Kn)..........................................................43
Figure 3.8 : Le chiffrement IDEA .........................................................................................................45
Table 3.15: Les sous clés de déchiffrement Ki'(r) générées à partir des sous clés Ki(r) ...................47
Table 3.16 : Difficulté du calcul de logarithme discret......................................................................50
Figure 4.1 Algorithme évolutionniste....................................................................................................73
Figure 4.2 : Le 1er message en clair ......................................................................................................79
Figure 4.3 : Le 1er message chiffré........................................................................................................79
Figure 4.4 : le 2ème message en clair......................................................................................................80
Figure 4.5 : Le 2ème message chiffré........................................................................................................80
Figure 4.6 : Résultats expérimentaux des messages 1et 2 ..................................................................80
Figure 4.7 : Le 3ème message en clair. ....................................................................................................81
Figure 4.8 : Le 3ème message chiffré........................................................................................................81
Figure 4.9 : Le 4 ème message en clair....................................................................................................82
Figure 4.10 : Le 4ème message chiffré ...................................................................................................82
Figure 4.11 : Résultats expérimentaux des messages 3 et 4...............................................................82
Table 4.1 : Tableau récapitulatif des résultats ......................................................................................83
Figure 5.1 Premier texte en clair............................................................................................................96
Figure 5.2 La forme cryptée du premier texte...................................................................................96
Figure 5.3 Le deuxième texte en clair..................................................................................................97
Figure 5.4 La forme cryptée du deuxième texte................................................................................97

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat v

Sommaire

Figure 5.5 Le troisième texte en clair ..................................................................................................98

Figure 5.6 La forme cryptée du troisième texte ................................................................................98
Figure 5.7 Le quatrième texte en clair ..................................................................................................99
Figure 5.8 La forme cryptée du quatrième texte ...............................................................................99
Figure 6.1: Schéma d’une clé-fragment...............................................................................................105
Figure 6.2 : L’algorithme du chiffrement par fragmentation ..........................................................106
Figure 6.3 : Le 1er message en clair......................................................................................................107
Figure 6.4 : Le chiffrement du 1er message après fragmentation des listes ................................108
Table 6.1 : La clé de fragmentation du 1er message.........................................................................108
Figure 6.5 : Le 2ème message en clair ...................................................................................................109
Figure 6.6 : Le chiffrement du 2ème message (après fragmentation des listes) ............................109
Table 6.2 : La clé de fragmentation du 2ème message.......................................................................110
Figure 6.7: Le 3ème message en clair ...................................................................................................110
Figure 6.8 : Le chiffrement du 3ème message (après fragmentation des listes) ...........................111
Table 6.3 : La clé de fragmentation du 3ème message ........................................................................111
Figure 6.9 : Le quatrième message en clair........................................................................................111
Figure 6.10 : Le chiffrement du 4ème message (après fragmentation des listes) ..........................112
Table 6.4 : La clé de fragmentation du 4ème message ........................................................................112
Figure 7.1 : Interface du IDEA dans le cas du chiffrement d’un texte ......................................114
Figure 7.2 : Interface du IDEA dans le cas de chiffrement d’une image..................................115
Table 7.1 : Résultats obtenue avec IDEA ..........................................................................................115
Figure 7.3 : Interface du RSA .............................................................................................................117
Table 7.2 : Résultats obtenue avec RSA..............................................................................................118
Figure 7.4 : Interface de PGP.............................................................................................................119
Table 7.3 : Résultats obtenue avec le PGP.........................................................................................119
Figure 7.5 : Interface des fichiers de SEC ........................................................................................120
Figure 7.6 : Interface des paramètres de l’AE de SEC .................................................................120
Table 7.4 : Résultats obtenue avec SEC..............................................................................................121
Table 7.5 : Temps de chiffrement et de déchiffrement....................................................................121
Figure7.7 : Représentation graphique du temps de chiffrement et de déchiffrement................122

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat vi

 Chapitre 1

INTRODUCTION GENERALE

La cryptologie, « science du secret » est l’une des sciences les plus antiques (plus de
3000 ans). Elle a été réservée pendant longtemps, aux milieux diplomatiques et
militaires. Grâce au développement de la société de l’information et l’évolution des
réseaux de communications sa démocratisation s’est installée et elle s’est imposée dans
tous les domaines. De nouvelles exigences se sont alors apparues : assurer la
confidentialité des messages ne suffit plus, il faut également assurer leur intégrité et
leur authenticité.

Dans la cryptologie, on distingue la cryptographie et la cryptanalyse. La première

définit et étudie les systèmes utilisés, alors que la seconde cherche à valider ou à casser
ces systèmes.

En dépit de son antiquité et de son importante évolution, de la cryptographie

classique (code de César et autres) à la cryptographie moderne (AES, RSA, PGP..) à
la cryptographie quantique, elle n’en est qu’à ses balbutiements. En fait, les meilleurs
systèmes de chiffrement sont comptés sur les bouts des doigts, nous pouvons en
citer quelques-uns :

DES, système de chiffrement symétrique, il chiffre par blocs en utilisant une

clé secrète ayant pour taille 64 bits. Cette taille si petite a favorisé son attaque
par recherche exhaustive.

IDEA, il est aussi un système de chiffrement symétrique (par blocs), sauf qu’il
dispose d’une clé secrète de taille plus grande soit ,128 bits .Il est aussi sujet
d’attaques (Chapitre3 §.IV).

AES, remplace actuellement le DES, grâce à la taille comparativement longue

de sa clé, allant jusqu’à 256 bits, il résiste toujours à la cryptanalyse

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat

Chap.1 Introduction générale

RSA, système de chiffrement asymétrique, basé sur l’arithmétique modulaire

et notamment sur le problème de factorisation. Il est actuellement loin d’être
sujet d’attaque ou de cryptanalyse. Mais l’avenir est incertain vu l’évolution
extrêmement rapide de la science et la technologie.

PGP, système hybride, combinant à la fois des algorithmes symétriques et

asymétriques. Il est pour le moment, le système le plus dominant.

Certes, concevoir et réaliser un nouveau système cryptographique plus sûr et

résistant ne serait que bénéfique pour cette science. C’est le but de notre contribution.
Pour ce, nous avons opté pour l’utilisation des algorithmes évolutionnistes (AE).

Pourquoi les algorithmes évolutionnistes ?

Les AE ont connu un grand succès dans la résolution des problèmes d’optimisation
et notamment les combinatoires qui sont en général NP-complets ou NP-difficiles.
Etant donné que nous avons pu ramener notre problème de chiffrement à un
problème d’optimisation combinatoire, l’appel aux AE est justifié. Ceci d’une part.
D’autre part, la majorité des processus dans les AE est aléatoire ce qui est un atout
pour la cryptographie. D’une manière générale, on utilise les algorithmes
évolutionnistes lorsque les méthodes d'optimisation classiques ne permettent pas
d'obtenir de bons résultats.

Nous rappelons que la méthode évolutionniste est une métaphore du principe de la

sélection naturelle et de la loi de survie du plus fort de Darwin. Elle utilise un
ensemble de solutions (ou population), la loi de sélection, et les opérateurs de
transformation qui sont, entre autres, le croisement et la mutation. Une solution au
problème est codée en terme de chromosome, appelé parfois aussi génotype. Les
chromosomes sont croisés entre eux ou mutés pour générer d'autres chromosomes.
Pour éviter la génération de solutions invalides, l'idée est d'incorporer dans les
opérateurs de croisement ou de mutations des contraintes ou des heuristiques.

D’une manière précise la contribution de notre travail, consiste en la conception et la

réalisation de systèmes de chiffrement symétriques ayant pour outil de base les AE.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 2

Chap.1 Introduction générale

Pour commencer, nous avons donné au problème de chiffrement une nouvelle

formalisation permettant de le ramener à un problème d’optimisation combinatoire.
En fait, nous avons représenté le message à chiffrer par un ensemble de listes
disjointes. Chaque liste est composée par les différentes positions dans le message du
caractère correspondant. L’objectif principal est de modifier au maximum les
fréquences d’apparition et les positions des caractères dans le message.

Dans un premier lieu, nous avons construit un système de chiffrement symétrique

basé sur les algorithmes évolutionnistes «symmetrical evolutionist-based ciphering »
nommé SEC, dont le but principal est d’établir un échange des fréquences
d’apparition entre les différents caractères du message ainsi que de leurs positions.
Cela se fait par le biais de l’AE que nous avons mis en œuvre. Nous notons que SEC
démarre avec des solutions potentielles générées aléatoirement en utilisant des
processus de la cryptographie classique. Des résultats expérimentaux nous ont prouvé
que pour une population initiale de taille 24 ou 30 de très bons résultats sont
obtenus. En travaillant sur la forme binaire du texte et en considérant des blocs de k
bits (k choisi aléatoirement) comme étant des caractères, nous obtenons une
extension de SEC. Cette dernière nous a permis d’éviter l’usage de la cryptographie
classique et par la suite renforcer la résistance aux attaques.

Des comparaisons avec d’autres systèmes connus et de même nature ont permis
d’évaluer notre système SEC.

Dans un deuxième lieu, nous avons défini une nouvelle méthode de chiffrement
intitulé « fusion ». Cette méthode consiste à regrouper un certain nombre de listes
dans une seule. La liste résultante est représentée par un seul caractère désigné
aléatoirement. Cette fusion peut être considérée comme un pré-chiffrement pour
SEC. Ainsi l’AE mis en œuvre débutera avec des solutions potentielles plus
intéressantes. L’avantage de cette méthode est qu’elle masque les fréquences réelles
des caractères ce qui mène à un nouveau système très résistant à la cryptanalyse par
étude des fréquences d’apparition des caractères. Nous désignons cette version
améliorée de SEC par ESEC-1 ( « enhancement of SEC »).

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 3

Chap.1 Introduction générale

Et enfin, nous avons élaboré une autre technique de chiffrement nommée

« fragmentation ». La fragmentation est un sur-chiffrement de SEC et s’applique au
texte chiffré issu de l’AE. Elle consiste à décomposer les listes de grande taille
formées par les positions des différents caractères d’un texte, en des sous listes de
même taille. Ces sous-listes seront représentées par des caractères différents choisis
aléatoirement. Cela renforcera davantage la résistance contre de redoutable
cryptanalyse et conduira à un troisième système plus sûr que nous nommons ESEC-2.

Présentation de notre document

Notre document comporte sept parties : une partie introductive au contexte du

problème, deux parties définissant et étudiant les domaines où porte notre
contribution, trois autres parties décrivant respectivement nos trois différents
systèmes de chiffrement et une partie conclusion. L’organisation ainsi faite facilite
l’accès à l’objet d’intérêt.

Ainsi le chapitre 1, situe le contexte de notre travail, cite en bref les différents
travaux existants et donne les grandes lignes de notre contribution.

Le Chapitre 2, définit et étudie des algorithmes évolutionnistes

Le Chapitre 3 est consacré à l’état de l’art de la cryptographie depuis la classique

jusqu’au quantique.

Les chapitres 4, 5 et 6 sont consacrés respectivement à la description de nos trois

systèmes de chiffrement : SEC, ESEC-1 et ESEC-2. Les résultats d’application de
chacun de ces systèmes sont donnés à la fin de chaque chapitre. Des comparaisons à
des systèmes de chiffrement très connus ont permis l’évaluation des nôtres.

Le chapitre 7 est consacré à des comparaisons sur le plan pratique avec les
algorithmes les plus dominants actuellement tels que IDEA, RSA, et PGP.

Nous achevons notre document par une conclusion générale, où nous faisons un
bilan de nos travaux effectués, ceux qui sont en cours et présentons les différentes
perspectives.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 4

 Chapitre 2

LES ALGORITHMES EVOLUTIONNISTES

I Introduction
II Algorithmes génétiques
II.1 Définition et origine
II.2 Corps d’un algorithme génétique
III Naissance des algorithmes évolutionnistes
III.1 Les algorithmes génétiques parallèles
III.2 Extension vers les problèmes d’optimisation
III.3 Extension vers les problèmes d’ordonnancement

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat

Chap.2 Les algorithmes évolutionnistes

I Introduction
Le succès des méthodes basées sur les algorithmes génétiques (AG) n’a cessé de
grandir depuis leur apparition, notamment dans le domaine de la recherche
opérationnelle et l’intelligence artificielle. Cependant, leurs applications à certains
problèmes comme les problèmes d’ordonnancement sont limités, par conséquent des
extensions ont été développés [MIC 92] ce qui a donné naissance aux algorithmes
évolutionnistes.

II Algorithmes génétiques
II.1 Définition et origine
Les algorithmes génétiques s’inspirent de l’évolution darwinienne des populations
biologiques, pour définir leurs mécanismes. Les principes de cette évolution sont tels
que, dans une population d’individus ce sont les plus forts, c’est à dire les mieux
adaptés au milieu, qui survivront et pourront donner une descendance ou une bonne
progéniture.

C’est en 1950 que les algorithmes génétiques ont vu le jour par des biologistes
utilisant des ordinateurs pour simuler l’évolution des organismes.

Vers 1960, John Holland et son équipe adaptaient ces algorithmes pour la
recherche de solutions à des problèmes d’optimisation [Hol 75], en développant une
analogie entre un individu dans une population et une solution d’un problème dans
un ensemble de solutions.

En effet, un individu dans une population est caractérisé par son empreinte
génétique autrement dit un ensemble de chromosomes issue de la recombinaison des
empreintes de ses deux parents, obtenue par croisement (en anglais : "Crossover") ou
modifiée par mutation. Le croisement correspond à la reproduction sexuée des
individus dans une population en respectant les phénomènes d’hérédité. Ainsi,
lorsque deux individus considérés comme assez forts s’accouplent, ils vont créer un
nouvel individu, membre de la génération suivante, qui aura lui-même de bonnes
chances d’être assez fort et de résister à la sélection naturelle, ce qui n’est pas le cas

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 6

Chap.2 Les algorithmes évolutionnistes

d’individus plus faibles. La mutation représente les modifications de l’empreinte

génétique qui peuvent se produire sur les individus d’une génération à l’autre et qui
évitent la dégénérescence de la population.

Par analogie, dans un AG, un individu ou une solution est caractérisé par une
structure de données qui représente son empreinte génétique. La force d’un individu,
encore appelée son "fitness", peut être mesurée par la valeur de la fonction
d’évaluation correspondante. Les opérateurs génétiques de croisement et de mutation
agissent sur les structures de données associées aux individus et permettent de
parcourir l’espace des solutions du problème. Le renouvellement de la population
c’est à dire de l’ensemble de solutions courantes, autrement dit la création d’une
nouvelle génération, est obtenu par itération de l’AG qui va créer de nouveaux
individus et en déduire d’autres, c’et équivalent au mécanisme de sélection naturelle.
L’exécution d’un tel algorithme doit contenir, à partir d’une population initiale, après
de nombreuses générations, à une population initiale où les individus sont tous très
forts, en d’autres termes, à un ensemble de meilleures solutions au problème
considéré.

En résumé, pour mettre en œuvre un AG, il est nécessaire de disposer :

- D’une représentation génétique du problème, c’est à dire d’un codage approprié

des solutions sous la forme de chromosomes.

- D’un moyen de créer la population initiale.

- D’une fonction d’évaluation ou fonction objective pour mesurer la force de

chaque chromosome.

- D’un mode de sélection des chromosomes à reproduire.

- D’opérateurs génétiques adaptés au problème.

- De valeurs pour les paramètres qu’utilisent l’algorithme : la taille de la population,

la probabilité d’appliquer tel ou tel opérateur.

II.2 Corps d’un algorithme génétique

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 7

 Chap.2 Les algorithmes évolutionnistes

Etape 0 : Définir un codage du problème

Etape 1 : Créer une population initiale P0 de q individus{X1, X2, …, Xq}

i := 0 ;

Etape 2 : Evaluation des individus.

Soit F la fonction d’évaluation. Calculer F(Xi) pour chaque individu Xi de Pi

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-Coisement : Appliquer l’opération de croisement aux paires sélectionnées

Mut 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 Pi+1

Répéter les étapes 2, 3 et 4 jusqu’à l’obtention du niveau de performance souhaité

Figure 2.1 : Un algorithme génétique

Nous détaillons dans les paragraphes suivants les cinq étapes de l’AG.
II.2.1 Codage
Le premier pas dans l’implantation des algorithmes génétiques est de créer une
population d’individus initiaux. Par analogie avec la biologie chaque individu de la
population est codé par un chromosome ou un génotype [HOL 75].

Une population est donc un ensemble de chromosomes. Chaque chromosome code

un point de l’espace de recherche. L’efficacité de l’algorithme génétique va donc
dépendre du choix du codage d’un chromosome. Il faut retenir que non seulement le
codage dépend de la nature de la solution mais aussi de la fonction à optimiser.

Dans le cas des AG, c’est le codage binaire qui est le plus utilisé. Le chromosome est
alors un vecteur dont les éléments ou les gènes appartiennent à {0,1}. Nous verrons
plus loin, dans le paragraphe 3, que dans l’extension des AG, d’autres types de codage
sont utilisés.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 8

Chap.2 Les algorithmes évolutionnistes

II.2.2 Construction de la population initiale

La population initiale est générée d’une manière aléatoire. Cependant, il est très
recommandé de disposer d’un mécanisme permettant de générer une population non
homogène qui servira de base pour les générations futures. Ce choix conditionne la
rapidité de la convergence vers l’optimum. Cela dit, dans le cas où l’on ne connaît
rien du problème à résoudre, il est essentiel que la population initiale soit répartie sur
l’espace de recherche.

II.2.3 Evaluation des individus

Evaluer un individu ou un chromosome consiste à calculer sa force. Cette évaluation
permettra aux individus les plus forts d’être retenus lors de la sélection. Le but de
l’AG est de maximiser la force des individus de la population. Soit C(x) la valeur du
critère à optimiser pour l’individu x. Si ce critère doit être maximisé, il peut servir
directement de mesure de la force. Dans le cas où l’on désire minimiser ce critère, il
est nécessaire de le complémenter pour se ramener à un cas de maximisation.
Goldberg [GOL 89] propose donc de calculer la force F(x) d’un individu x de la façon
suivante :

 Cmax −C(x ) Si C(x ) > 0


F(x )=
 0 Sinon

où Cmax peut être un coefficient fixé ou la plus grande valeur observée de C(x) soit
dans une population, soit depuis le début de l’algorithme.

Aucune condition n’est requise pour la fonction objective. Il suffit simplement que
cette fonction retourne des valeurs numériques comparables. La performance de
l’AG peut être sensible au choix de cette fonction.

II.2.4 Sélection
La sélection consiste à choisir les individus à partir desquels on va créer la génération
suivante. Comme dans la sélection naturelle, un caractère stochastique est introduit
dans la probabilité de sélection qui est souvent basée sur la fonction d’évaluation.
Les individus sélectionnés sont placés dans un bassin de reproduction dans lequel
auront lieu des opérations de croisement et de mutation. Plusieurs procédures de

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 9

Chap.2 Les algorithmes évolutionnistes

sélections existent. On peut citer la sélection proportionnelle basée sur le principe de

la roulette [GOL 89]. par rang de classement dans la population [DAV 91], par
tournoi et par élitisme.

Sélection de la roulette (Roulette Wheel Selection)

C’est la plus classique et la plus utilisée. Nous décrivons son processus ci-dessous :

On affecte à chaque individu xi une probabilité d’apparition p(xi), appelée encore force
relative :
On affecte à chaque individu Xi une probabilité d’apparition p(Xi) :

F(Xi )
p(Xi) = q

∑ F(X
k =1
k )

La sélection d’un individu se fait de la manière suivante.

i

Soit qi= la ∑ p( X
k =1
k ) probabilité d’apparition cumulée d’un individu Xi et soit r un

nombre aléatoire compris entre 0 et 1, l’individu retenu est:

X1 si q1 ≤ r Ou

Xi si qi-1<r ≤ qi pour 2 ≤ i ≤ q

q étant le nombre d’individu dans la population.

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é.

Sélection par rang de classement

Dans ce schéma de sélection, les individus d’une population sont classés dans une liste
selon l’ordre croissant de leur évaluation, ensuite la sélection est proportionnelle à leur
rang dans la liste de la population [DAV 91]. Cette méthode est utilisée pour une
fonction d’évaluation dont les valeurs sont très proches.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 10

Chap.2 Les algorithmes évolutionnistes

Le classement permet de calculer la nouvelle fonction d’évaluation basée sur le rang :

F = MAX - (rang - 1) * (MAX - MIN)/(q - 1) Avec q est la taille de la

population,

1.0 < MAX ≤ 2.0 et MIN=2 – MAX et rang ∈ {1, 2, 3, ..., q}

Avec cette nouvelle fonction d’évaluation, les meilleurs ont toujours plus de chance
d’être choisis, mais moins souvent que la roulette et les moins bons individus auront
plus de chance de participer au bassin de reproduction.

Sélection par tournoi

Sur une population de q chromosomes, on forme q paires de chromosomes. Dans les
paramètres de l’AG, on détermine une probabilité de victoire du plus fort. Cette
probabilité représente la chance qu’a le meilleur chromosome de chaque paire d’être
sélectionné. Cette probabilité doit être grande (entre 70% et 100%). A partir de q
paires, on détermine ainsi q individus pour la reproduction.

Sélection par Elitisme

A la création d’une nouvelle population, il y a de grandes chances que les meilleurs
chromosomes soient perdus après les opérations de croisement et de mutation. Pour
éviter cela, on utilise la méthode d’élitisme. Elle consiste à copier un ou plusieurs des
meilleurs chromosomes dans la nouvelle génération. Ensuite, on génère le reste de la
population selon l’algorithme de reproduction usuel . Cette méthode améliore
considérablement les algorithmes génétiques, car elle permet de ne pas perdre les
meilleurs solutions.

II.2.5 Opérateurs génétiques

Les parents sélectionnés sont introduits dans le bassin de reproduction où ils seront
de nouveaux choisis aléatoirement pour voir leurs chromosomes subir des
transformations par les opérateurs génétiques. Le croisement réalise une opération
binaire ou sexuée, et nécessite deux parents. La mutation est une opération unaire ou

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 11

Chap.2 Les algorithmes évolutionnistes

asexuée, utilisée pour introduire une faible variation dans la solution ou changer la
direction de la recherche.

a) Opérateur de croisement
Le croisement le plus simple fonctionne de la manière suivante. Soient deux
chromosomes X et Y devant subir le croisement, un nombre aléatoire entier p tiré
entre 1 et m, m étant le nombre de gènes d’un chromosome. Le nombre p indique la
position de coupure dans les chromosomes :

Figure 2.2 : Croisement '1-point'.

Ce processus est appliqué à chaque paire de chromosomes sélectionnés avec une

certaine probabilité Pcross. Les paires de chromosomes sont recopiées sans
modification dans la génération suivante avec la probabilité 1-Pcross. Ce croisement est
appelé croisement '1-point' car un seul point de coupe est effectué dans le
chromosome. Cette notion est généralisée au croisement 'k-points' où k points de
coupe sont effectués dans le chromosome, générant k+1 sous chromosomes qui sont
re-combinés pour créer deux chromosomes fils. Le premier chromosome fils est
alors la concaténation des sous- chromosomes de numéro pair du premier parent et
des sous-chromosomes de numéro impair du deuxième parent. Le deuxième fils est
obtenu de manière symétrique.

Reprenons les deux chromosomes X et Y auxquels on applique un croisement

'2_points' :

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 12

Chap.2 Les algorithmes évolutionnistes

Figure 2.3 : Croisement ‘2-points’

b) Opérateur de mutation
L’opérateur de mutation est appliqué, avec une certaine probabilité Pmut, aux individus
issus du croisement. La mutation la plus classique consiste à sélectionner
aléatoirement un gène du chromosome d’un individu et à modifier sa valeur.

II.2.6 Critère d’arrêt

Le critère d’arrêt peut être arbitraire, par exemple le nombre maximal de générations,
ou basé sur le critère de convergence décrit ci-dessous.

II.2.7 Convergence
J. Holland a défini des propriétés concernant la convergence des AG en introduisant la
notion de schéma [HOL 75].
Un schéma est un masque qui permet d’explorer les similitudes entre chromosomes. La
mise en œuvre de schémas nécessite d’ajouter à l’alphabet des gènes un symbole
supplémentaire * qui représente indifféremment 0 ou 1. Ainsi, un schéma 1*10
représente les chromosomes 1010 et 1110. D’une manière générale, un schéma
représentera 2r chromosomes, r étant le nombre de symboles * présents dans le schéma.
De même, un chromosome de longueur m est représenté par 2m schémas. Les schémas
sont caractérisés par leur ordre et leur longueur de définition.
L’ordre d’un schéma est le nombre de 0 et 1 contenus dans ce schéma. C’est aussi la
différence entre la longueur du chromosome et le nombre de symboles *.

La longueur de définition d’un schéma est la distance entre la première et la dernière

position fixe du chromosome ; une position fixe est un gène dont la valeur est
différente de *. Par exemple, pour le schéma ***001*110, la longueur de définition est

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 13

Chap.2 Les algorithmes évolutionnistes

10-4=6. Cette notion permet de calculer la probabilité de survie d’un chromosome après
un croisement.
Théorème des schémas [HOL 75] :
Dans un algorithme génétique, si le croisement est du type « un –point » et si la sélection
repose sur le principe de la roulette alors le nombre de chromosomes correspondant à
des schémas de longueur de définition courte, d’ordre faible et de force supérieure à la
moyenne augmente au cours des itérations.

En résumé, les travaux de Holland [HOL 75] montrent que, si les chances de
reproduction sont proportionnelles à la force (évaluation), les schémas de force au-
dessus de la moyenne auront tendances à apparaître plus fréquemment dans la prochaine
génération. Au contraire, les schémas de force en-dessous de la moyenne deviendront de
plus en plus rares. Par ailleurs, la longueur de définition d’un schéma est liée à la
position des génes dans le chromosome. La convergence d’un algorithme génétique
dépend donc des opérateurs génétiques mis en œuvre.
De leur côté K. Dejong [DEJ 75], et Greffenstette [GRE 86] ont proposé des mesures
statistiques permettant aussi de juger la convergence. Nous en citons deux :
Performance en-ligne
La performance en cours de la recherche est mesurée par la performance moyenne de
l'algorithme basée sur la fonction d’évaluation :
t =T
Performance-en-ligne(T) = 1 ∗∑ F ( t )
T t =1
Avec T, le nombre total des itérations jusqu'à l'itération t, F(t) est la valeur moyenne de
la fonction d’évaluation à la tième itération. Lors de l'exécution de l'AG, Performance-en-
ligne(T) converge de plus en plus vers une valeur stable (état stationnaire), et comme
Performamnce-en-ligne(T) converge, les solutions trouvées par l'algorithme deviennent de
plus en plus stables.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 14

Chap.2 Les algorithmes évolutionnistes

Performance hors-ligne
La mesure de performance hors-ligne, est similaire à celle en-ligne sachant que la
performance hors-ligne accorde plus l'importance aux meilleures performances
obtenues:
t =T
Performance-hors-ligne(T) = 1 ∗ ∑ F max ( t ) avec Fmax(t)=Sup(F(t)) et 1≤ t ≤ T
T t =1
Dans l'équation ci-dessus, ce qui change par rapport à la performance en-ligne est la
fonction Fmax(t), qui enregistre le meilleur fitness jusqu'à présent et ignore toute autre
évaluation.
Ces mesures de performance peuvent être utilisées comme critère d'arrêt. Puisque si
Performance-hors-ligne(T) converge vers une valeur stable durant l'évolution, la
chance d'obtenir une solution encore meilleure diminue fortement et l'on peut déjà
arrêter la simulation, car si meilleur signifie seulement une légère amélioration,
continuer l'algorithme serait une perte de temps.
Enfin, on a montré que la convergence peut-être observée directement en mesurant
comment les individus changent à chaque position de gène [BEA 93]. Un gène est dit
avoir convergé lorsque 95% de la population partage la même valeur et la population
est qualifiée d’avoir convergé si tous les gènes ont convergé.

III Naissance des algorithmes évolutionnistes

Les A G ainsi introduits, ont retenu l’attention de nombreux chercheurs et praticiens
de l’optimisation, en raison de leurs qualités particulières. Cependant, le codage
binaire des solutions constitue un frein majeur à l’utilisation des AG. En effet, ce type
de codage s’est révélé insuffisamment adapté à des problèmes d’optimisation avec des
variables réelles, à des problèmes nécessitant la représentation de permutations, ou
d’autres problèmes complexes. Des extensions des AG utilisant d’autres types de
codages et d’autres opérateurs génétiques, tout en conservant l’esprit des AG ont été
proposées. Cependant, il est difficile de trouver des frontières réelles entre les deux
types d’algorithmes si ce n’est que l’on peut considérer les AG comme une classe
particulière des AE.

Parmi les principales extensions des AG nous en citons :

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 15

Chap.2 Les algorithmes évolutionnistes

III.1 Les algorithmes génétiques parallèles

Dans cette classe d’algorithmes, on cherche à améliorer parallèlement chaque
individu par la méthode du Hill-Climbing , puis chaque individu s’accouple avec un
autre individu de son voisinage. Il n’y a donc plus de sélection comme dans les
algorithmes génétiques classiques. Les individus évoluent en parallèle, sans contrôle
central. Un exemple d’AG parallèle est décrit par Mühlenbein H. [MÜH 93a].

III.2 Extension vers les problèmes d’optimisation

Dans un AE, quand on est devant un problème à n variables réelles, on pourra le
représenter par un chromosome codé sous la forme d’un vecteur composé de n réels.
En fait, la représentation binaire a quelques inconvénients lorsqu’elle est appliquée à
des problèmes de plusieurs variables avec une grande précision numérique.

A titre d’exemple, pour un problème à 100 variables comprises dans un intervalle

réel [-500 , 500] et pour une précision requise de six chiffres après la virgule, la taille
du chromosome est 3000 [MIC 92]. Un tel chromosome engendre un espace de taille
101000. C.Z. Janikow et [Link] ont confirmé par des expérimentations que
le codage réel augmente la rapidité de l’algorithme et apporte la précision dans les
résultats ainsi ils ont montré que les résultats sont uniformes d’un essai à l’autre
[JAN 91].

Des opérateurs de croisement et de mutation adaptés à ce genre de codage ont été

proposés tels que : le croisement arithmétique [MIC 92] défini comme combinaison
linéaire de deux vecteurs ou chromosomes, la mutation uniforme [MÜH 93a] et non
uniforme [MIC 94].

III.3 Extension vers les problèmes d’ordonnancement

III.3.1 Codage
Dans le cas de problèmes d’ordonnancement, on utilise le codage de permutation
dans lequel les gènes d’un chromosome représentent des opérations et l’ordre des
gènes dans le chromosome indique la séquence de ces opérations. Dans ce cas le
croisement simple des AG n’est plus applicable car il risque de donner des solutions

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 16

Chap.2 Les algorithmes évolutionnistes

non admissibles. En fait, si on considère deux chromosomes possibles représentés par

les chromosomes :

C1 = A B C D et C2 = D A B C.

Supposons que le point de croisement est au centre des chromosomes, on obtient

alors deux chromosomes fils aberrants F1 = A B B C et F2 = D A D C, car une
même opération apparaît plusieurs fois. Ce problème nécessite d’améliorer le codage
des permutations et de concevoir des opérateurs génétiques qui préservent chaque
gène mais qui modifient leur ordre. Dans ce contexte un codage binaire pour les
permutations a été conçu de la manière suivante :

Etant donné une permutation de n éléments, on peut considérer la permutation

comme étant la suite des entiers 1, 2, … n, on obtient facilement une représentation
en binaire équivalente, il suffit de prendre la partie triangulaire supérieure stricte (sans
aucun terme de la diagonale) de la matrice de précédence associée M telle que :

Mij = 1 si et seulement si i est avant j dans la permutation et

Mii = 1 par convention.

Cette matrice M est transitive et antisymétrique. Elle a également la propriété de

n’avoir qu’une et une seule ligne comportant exactement k valeurs 1 pour k variant de
1 à n et qu’une et une seule colonne comportant exactement k valeurs 0 pour k
variant de 0 à n-1. Cette matrice est de taille n2.

Parmi les meilleurs exemples de problèmes où le codage de permutation a donné de

très bons résultats est le problème du voyageur du commerce en anglais "Travelling
Salesman problem" (TSP). Dans ce codage, chaque chromosome est une chaîne de
nombres.

Exemple :
Un vendeur doit distribuer ou livrer des marchandises à 9 villes. Il faut trouver un
ordre de parcours des villes permettant de réduire au minimum la distance parcourue.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 17

Chap.2 Les algorithmes évolutionnistes

C1= 1 5 3 2 6 4 7 9 8
C2= 8 5 6 7 2 3 1 4 9
C1 et C2 sont deux chromosomes distincts. Chacun d’eux indique l’ordre des villes
dans lesquelles le vendeur les visitera.

III.3.2 Opérateurs génétiques adaptés

Croisement
Des différents croisements ont été définis pour les types précédents de codage. A titre
d’exemples nous citons : le croisement de Nakano &Yamada [NAK 91], le croisement
simple binaire de permutation , le croisement uniforme de permutation [DJE 95] pour le
codage de permutation binaire et le croisement PMX conçu par Goldberg & Lingle
[GOL 85] pour résoudre le problème du voyageur de commerce. Nous en présentons
ci-dessous, trois autres types fréquemment utilisés.
- Croisement MPX (Maximal Préservative X) :
Ce croisement a été proposé par Mülhenbein [MÜH 93a] et [MÜH 93b] 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. Par un exemple nous
illustrons le fonctionnement.

Exemple :

Figure 2.4: Croisement MPX

La zone de croisement est comprise entre les positions 5 et 9 . La première étape

consiste à recopier la zone de croisement du parent 1 sur le fils 1. Ensuite, les gènes du
fils qui ne sont pas dans la zone de croisement sont complétés de la façon suivante: Le
ième gène du parent2 est recopié sur le ième gène du fils 1 si cette recopie respecte les

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 18

Chap.2 Les algorithmes évolutionnistes

contraintes(ne crée pas une tournée incohérente). Sinon, le ième gène du parent1 est
recopié sur le ième gène du fils 1 si cette recopie ne crée pas de doublons.. Si les deux cas
précédents ne peuvent pas s’appliquer, le ième gène du fils 1 reçoit un gène de la zone de
croisement du parent 2 qui respecte les contraintes(premier non pris).
Ce croisement est appliqué aux individus sélectionnés avec un taux bien précis. Le
meilleur taux est de l’ordre de 60% à 100% [MÜH 93b] .
-Croisement d’ordre à deux points OX
Ce croisement a d’abord été proposé par Davis [DAV 85], puis modifié par
Starkweather T. et al. [STA 91]. C’est un croisement à deux points. La zone interne du
parent 2 est utilisée pour le fils 1 et la zone interne du parent 1 est utilisée pour le fils 2.
Ensuite, en commençant par la troisième zone et en poursuivant par la première, les
valeurs manquantes de fils 1 sont copiés dans l’ordre du parent 1 (pour fils 2, on prend
l’ordre de parent 2).

Figure 2.5 : Croisement OX

-Croisement d’ordre à deux points linéaires ou croisement LOX
Il a été proposé par Falkenauer et Bouffouix [FAL 91] comme une amélioration du
croisement OX pour la résolution du problème d’ordonnancement de type « job-
shop ». Le début est similaire à OX, mais on termine autrement : en commençant par la
première zone et en poursuivant par la troisième, les valeurs manquantes de fils 1 sont
copiés dans l’ordre du parent 1 (pour fils 2, on prend l’ordre du parent 2).
Mutation
Les individus de la population issue du croisement vont ensuite subir un processus de
mutation avec une probabilité Pmut. Comme pour les croisements, de nombreuses
méthodes de mutation ont été développées dans la littérature du domaine. Nous
présentons ici le plus simple qui consiste à inverser les gènes de deux chromosomes
choisis aléatoirement. Cette méthode est illustrée sur la figure ci-dessous.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 19

Chap.2 Les algorithmes évolutionnistes

Figure 2.6 : Mutation d’un individu

IV Recommandations
Pour en finir, nous citons quelques recommandations concernant le choix des valeurs
des paramètres. En effet, d’après Grefenstette [GRE 86] les valeurs des paramètres
doivent être choisies avec les considérations suivantes :

• Taille de la population

Elle doit être judicieusement choisie en fonction de la taille du problème et du code.

- Trop faible : l’AE n’a pas assez d’échantillons de l’espace de recherche.

- Elevée : l’AE est plus informé. Une taille élevée prévient contre la convergence
prématurée.

- Trop élevée : le nombre élevé d’évaluations de la fonction objective par génération

ralentit la convergence.

• Taux de croisement

Plus le taux de croisement Pcros est élevé, plus il y aura de nouvelles structures qui
apparaissent dans la population.

- Trop élevé : les bons individus risquent de pas être cassés trop vite par rapport à
l’amélioration que peut apporter la sélection.

- Trop faible : la recherche risque de stagner.

Le taux habituel est choisi entre 60% et 100%.

• Taux de Mutation

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 20

Chap.2 Les algorithmes évolutionnistes

La mutation est un opérateur secondaire pour introduire la diversité dans la population.

Son taux d’application Pmut est choisi entre 0.1% et 5%.

- Trop élevé : le taux de mutation rend la recherche trop aléatoire ;

- Trop faible : la recherche risque de stagner.

Si la taille de la population est faible, un taux de croisement faible doit être combiné avec
un taux de mutation élevé. Mais sur cette étude de l’influence des paramètres,
Grefenstette suggère que la performance d’un AE dépend plus du codage et de la
fonction d’évaluation que de l’optimisation de ses paramètres [GRE 86].

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 21

 Chapitre 3

LA CRYPTOGRAPHIE

I Introduction
II Définitions
III Cryptographie classique
III.1 Le code de César
III.2 Le carré de Polybe
III.3 Chiffrement de Delastelle
III.4 le chiffre des templiers (ou de PigPen)
IIII.5 Le Chiffrement par décalage
III.6 Le chiffrement affine
III.7 Le chiffrement de Hill
III.8 Le chiffrement de Vigenère
III.9 Le chiffrement par transposition (par permutation)
III.10 Les faiblesses de la méthode de substitution
III.11 Systèmes à clés jetables
IV Cryptographie moderne
IV.1 Cryptographie symétrique
IV.1.1 DES
IV.1.2 IDEA
IV.1.3 AES
IV.2 Cryptographie asymétrique
IV.2.1 Schéma ElGamal
IV.2.2 RSA
IV.3 Cryptographie Hybride
IV.4 Cryptographie Quantique
IV.5 Cryptographie par courbe elliptique
V La cryptanalyse
V.1 Cryptanalyse linéaire
V.2 Cryptanalyse différentielle
V.3 L'attaque boomerang

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat

Chap.3 Cryptographie

I Introduction
L’idée de coder un message dans le but de le rendre intelligible à toute tierce personne
ne date pas d’aujourd’hui. Les « messages secrets » ont joué un rôle important dans
tous les conflits depuis que l’homme a appris à écrire et sont habituellement associés
aux guerres et aux agents secrets. Ce qui est nouveau, c’est le besoin quasi vital de
coder toute sorte d’information dans notre vie de tous les jours. En effet, les cartes
bancaires qui sont devenues nos proches compagnes, utilisent des systèmes de
chiffrement. Les transactions qui s’effectuent par lettre, par téléphone ou par contact
direct entre deux personnes se font de plus en plus par l’intermédiaire de réseaux de
communications électroniques. La généralisation de l’emploie des moyens modernes
de communication multiplie les possibilités d’indiscrétion et de falsification. Les
conséquences de telles falsifications peuvent être graves.

Ne pas protéger un message, c’est l’exposer à des problèmes tels que :

- Permettre à un concurrent de connaître les termes exacts d’un contrat signé

entre deux partenaires.
- Réception des messages sans être parfaitement sûr de leur provenance.
- Dévoiler un compte bancaire, à la réception d’un ordre de virement électronique
émis sous une fausse signature.
- L’interception de documents confidentiels et leur utilisation à mauvais fins.
Qu’est ce qu’un bon système de chiffrement ? C’est un système permettant de rendre
un message indéchiffrable par toute personne à laquelle il n’est pas destiné tout en
pouvant être facilement traduit par le destinataire officiel. Dans la mesure du possible,
ce système doit permettre de joindre une signature inviolable au message pour
permettre au destinataire de contrôler son authenticité.

II Définitions :
La cryptologie est une science mathématique qui comporte deux branches : la
cryptographie et la cryptanalyse [FLO 02].
La cryptographie classique est l'étude des méthodes permettant de transmettre des
données de manière confidentielle. Afin de protéger un message, on lui applique une

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 23

Chap.3 Cryptographie

transformation dépendante d’un paramètre appelé clé, afin de le rendre

incompréhensible ; c'est ce qu'on appelle le chiffrement, qui, à partir d'un texte en clair,
donne un texte chiffré ou cryptogramme. Inversement, le déchiffrement est l'action qui
permet de reconstruire le texte en clair à partir du texte chiffré.
La cryptographie moderne est la science de la sécurisation des données, elle nous permet
de stocker des informations sensibles ou de les transmettre à travers des réseaux non
sûrs (comme Internet).
La cryptanalyse, à l'inverse, est l'étude des procédés cryptographiques dans le but de
trouver des faiblesses, permettant de retrouver de texte en clair sans connaître la clef de
chiffrement [DUB 98]. Les cryptanalystes sont aussi appelés attaquants.

III Cryptographie classique

Dans la cryptographie classique, la méthode et la clé de chiffrement ainsi que celles de
déchiffrement sont connues par l’émetteur et le destinataire. L’émetteur et le destinataire
doivent se mettre préalablement d’accord sur la clé. Ce qui pose le problème de
l’échange des clés, par exemple, dans un réseau de N entités susceptibles de
communiquer secrètement, il faut distribuer CN2 = N(N −1)/ 2 clés.

La plupart des méthodes de chiffrement classiques reposent sur deux principes

essentiels: la substitution et la transposition [STI 03]. La substitution consiste à
remplacer certaines lettres par d'autres ou par des symboles. La transposition signifie
qu'on permute les lettres du message afin de le rendre inintelligible.
Au cours des siècles, de nombreux systèmes cryptographiques ont été mis au point, de
plus en plus perfectionnés et de plus en plus astucieux.
III.1 Le code de César
Le code de César est la méthode de cryptographie la plus ancienne communément
admise par l'histoire [BEC 90]. Il consiste à substituer chaque lettre de l’alphabet par
celle obtenue après un décalage des lettres. Par exemple, si on remplace A par D, on
remplace alors B par E, C par F, D par G, etc ...

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 24

Chap.3 Cryptographie

Texte
clair A B C D E F GH I J K L M N O P Q R S T U V W X Y Z
Texte
codé D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Table 3.1 : Le chiffrement de César

Il n'y a que 26 façons différentes de chiffrer un message avec le code de César. Donc,
il est très facile de le casser, en testant de façon exhaustive toutes les possibilités.

III.2 Le carré de Polybe

Polybe (150 av. JC) était un écrivain grec. C’est lui qui a inventé le premier chiffre de
substitution [SCH 96]. Le carré de Polybe est basé sur une grille comme celle-ci :

1 2 3 4 5
1 A B C D E
2 F G H IJ K
3 L M N O P
4 Q R S T U
5 V W X Y Z

Table 3.2 : La grille de Polybe

Chaque lettre est codée par 2 chiffres. Exemple : X=53. Les lettres I et J ne sont pas
différenciés. "BONJOUR" sera chiffré par "12343324344542"

III.3 Chiffrement de Delastelle

Le chiffre de Delastelle est un mélange de codage par substitution et par
transposition. On commence par découper le message en des blocs de 5 lettres, puis
on utilise le carré de Polybe. On écrit verticalement pour chaque lettre la position
dans le tableau. Par exemple, si on souhaite coder "OMARYFOUZ", on procède
comme suit :

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 25

Chap.3 Cryptographie

Le groupe des 5 premières lettres :

O M A R Y F O U Z
3 3 1 4 5 2 3 4 5 0
4 2 1 2 4 1 4 5 5 0

Table 3.3 : Un chiffrement de Delastelle

(Remarquons que les lettres vides sont remplacées par un double 00).
Ensuite, on effectue la transposition qui consiste à regrouper les chiffres deux par
deux, de la gauche vers la droite, puis du haut vers le bas. On obtient alors :
33145421242345014550. La dernière opération consiste à transformer le code
précédent en message littéral, en utilisant à nouveau le carré de Polybe. Toutefois, il
peut apparaître des nombres du type 00 01 02 10 20 etc... qu'on remplace par des
lettres spéciales ou des chiffres. Par exemple :

000 011 022 033 044 055 106 207 308 409 50%
On trouve ici finalement le message chiffré : "NDYFIHU1U%"

III.4 le chiffre des templiers (ou de PigPen)

Au lieu de remplacer chaque lettre par une autre, certains ont préféré remplacer les
lettres par des symboles pour diffuser leurs messages codés. C'est ainsi qu'ont procédé
les francs-maçons au XIXème siècle avec le chiffre de PigPen. Ils remplaçaient chaque
lettre par un symbole, selon la substitution suivante :

Figure 3.1: Le chiffrement de PigPen.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 26

Chap.3 Cryptographie

Par exemple, si nous souhaitons coder "UN BON CRYPTANALYSTE", on obtient:

III.5 Le Chiffrement par décalage

III.5.1 Arithmétique modulaire
Soient a, b et m des entiers avec m>0, on écrit a= b mod(m) « a est congru à b
modulo m » si m divise (b – a), cela équivalent aussi à : a et b ont même le reste de
division par m.

On définit alors l’arithmétique modulo m : l’anneau Z//mZ/ symbolise l’ensemble :

{0, 1, 2, …, m-1} muni des opérations addition (+) et multiplication ( . )

Par exemple : Dans Z//26Z/ , on calcule 11 x 13 = 143, on effectue une division

euclidienne : 143 = 5 x 26 + 13. Donc 11 . 13 = 13 mod(26).

On calcule 14 + 13 = 27 et puisque 27= 1x 26 + 1 alors 14 + 13 = 1 mod(26)

III.5.2 Application
Le chiffrement par décalage [STI 03] est basé sur l’arithmétique modulaire. On
l’utilise dans l’ensemble Z/ /26Z/ , car on a 26 lettres dans l’alphabet. Il est

représenté à l’aide de la fonction f définie par : f(x) = x + k mod(26).

Exemple : On applique la formule avec k=5 pour le texte «message secret» on a :

Texte en clair m e s S a g e s e c r e t
Nombre correspondant
12 4 18 18 0 6 4 18 4 2 17 4 19
à la lettre en clair
Nombre correspondant
17 9 23 23 5 11 9 23 9 7 22 9 24
à la lettre cryptée
Texte crypté r j x X f l j x j h w j y

Table 3.4 : Un chiffrement par décalage

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 27

Chap.3 Cryptographie

Remarquer que pour k = 3 on obtient le chiffrement de César

III.6 Le chiffrement affine

Ce chiffrement est réalisé à l’aide d’une fonction affine f(x) = ax + b mod (26).
On remarque que l’on retrouve le chiffrement par décalage dans le cas où a=1.

Pour que l’on puisse déchiffrer, il faut que l’opération inverse soit possible. C’est à
dire que l’équation : y =ax + b mod(26) ait une solution unique (cela revient à dire
que la fonction f doit être injective).

Théorème 1 :
L’équation y=a.x + b mod(26) admet une solution unique x ∈ Z//26Z/ pour tout

b ∈ Z//26Z/ si pgcd(a, 26) = 1.

On a donc 12 possibilités pour choisir a (1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25). Par
contre, b peut être quelconque. On a donc 12x26=312 clés possibles pour le
chiffrement affine. Ce nombre va augmenter si on utilise tous les caractères ASCII.

Le déchiffrement
Considérons maintenant la fonction f de chiffrement avec m= 26. On suppose que
pgcd(a, 26) = 1. L’équation y = a.x + b mod(26) admet alors une solution, pour la
déterminer il faut faire appel à la notion d’inverse modulaire définie par :

Soit a ∈ Z//26Z/ l’inverse de a est un élément a-1 ∈ Z//26Z/ tel que :

a.a-1= a-1.a=1 mod(26).

Dans Z/ /26Z/ , grâce à la table de multiplication on peut obtenir les inverses de tous

les nombres premiers avec 26 :

1-1=1, 3-1=9, 5-1=21, 7-1=15, 11-1=19, 17-1=23, 25-1=25.

En effet, on a les égalités suivantes modulo 26 :

3x9 = 27 =1, 5x21 = 105 = 4x26+1 = 1, …, 25x25 = 625 = 1

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 28

Chap.3 Cryptographie

y=a.x+b a.x = y –b a-1.a.x = a-1.(y-b) x = a-1.(y-b)

Par exemple : pour une clé de chiffrement a=7 et b=3 on a alors la fonction de
chiffrement : y= 7.x + 3 et la fonction de déchiffrement sera x= 7-1.(y-3) mod(26).

On note que 7-1 = 15 mod(26). D’où la formule finale : x= 15.y - 19 mod(26)

Application : sur le texte en clair "BONJOUR"

Lettre en clair B O N J O U R
Nombre x 1 14 13 9 14 20 17
Résultat y=7.x+3 10 23 16 14 10 13 18
Lettre chiffrée K X Q O X N S
Table 3.5 : Un chiffrement affine.

Ce qui donne le texte chiffré : "KXQOXNS"

Le déchiffrement sera à laide de la table :
Lettre chiffrée K X Q O X N S
Nombre y 10 23 16 14 10 13 18
Résultat x=15.y-19 1 14 13 9 14 20 17
Lettre en clair B O N J O U R
Table 3.6 : Un déchiffrement affine.

III.7 Le chiffrement de Hill

Le chiffrement de Hill, inventé en 1929 par Lester S. Hill, se rapproche beaucoup du
chiffrement affine. Il consiste à déterminer les caractères du texte chiffré par
combinaison linéaire de m caractères du texte en clair [STI 03].
Exemple : Avec m=2 le texte clair est décomposé en bloc de deux caractères x1 et x2. Le
texte chiffré sera alors composé de blocs y1 et y2. Un exemple de combinaison pourrait
être :
y1= 11.x1 +3.x2
y2= 8x1 +7.x2

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 29

Chap.3 Cryptographie

La clé de chiffrement sera alors une matrice carrée d’ordre 2 : 11 3 

 8 7
Dans le cas général, la clé est une matrice carrée d’ordre m. Dans notre exemple, nous
pouvons écrire de manière matricielle les deux équations :

 y1  11 3   x1 
 =  
 y2   8 7   
     x2 

 y1   k11 k12 . ....k1m   x1 

   
 y   k21 k22 ....k2m   x2 
 . 
et plus généralement :  .  =  . .
2
.  Ou bien Y = K.X
 .   
 .   .   
 ym     . 
   km1 km2 .......kmm   xm 
Le déchiffrement d’un message sera possible à condition que la matrice K soit inversible
et il sera réalisé à l’aide de la matrice inverse K-1 puisque :
Y = K.X ⇔ X = k-1.Y
Exemple :
11 3 
Avec la clé k =   le message "SECRET" sera chiffré en "CQVFXJ"
 8 7
 
Lettre en clair S E C R E T
X=(x1 x2) 18 4 2 17 4 19
Résultat Y=K.X 2 16 21 5 23 9
Lettre chiffrée C Q V F X J
Table 3.7 : Un chiffrement de Hill.

 7 23
Le déchiffrement se fait à l’aide de K-1 qui est égale à  .
18 11 
 
−1
11 3 a b   d −b 
en effet det K = = 77 - 24 = 53 = 1 mod(26) et   = 1 . .
8 7   det K  −c a 
c d   

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 30

Chap.3 Cryptographie

Lettre chiffrée C Q V F X J
Y=(y1 y2) 2 16 21 5 23 9
Résultat X=K-1.Y 18 4 2 17 4 19
Lettre obtenue S E C R E T
Table 3.8 : Un déchiffrement de Hill.

III.8 Le chiffrement de Vigenère

En 1586, Blaise de Vigenère a développé son Tracté des chiffres ou Secrètes manières
d'écrire, qui ressemble au chiffrement de César, à la différence près qu’il utilise un mot
clé au lieu d’un simple caractère [BEC 90].
Pour chiffrer un message, on choisit une clé qui sera un mot de longueur arbitraire. On
écrit ensuite cette clé sous le message à chiffrer, en la répétant aussi souvent que
nécessaire pour que sous chaque lettre du message à chiffrer, on trouve une lettre de la
clé. Pour chiffrer, on fait la somme modulo 26 de chaque caractère du message et du
caractère de la clé correspondant.
Exemple : On veut chiffrer le texte "CRYPTOGRAPHIE DE VIGENERE" avec la clé
"SECRET". On commence par écrire la clé sous le texte à chiffrer :
Texte C R Y P T O G R A P H I E D E V I G E N E R E
Clé S E C R E T S E C R E T S E C R E T S E C R E
Nbres 2 17 24 15 19 14 6 17 0 15 7 8 4 3 4 21 8 6 4 13 4 17 4
x1 x2 18 4 2 17 4 19 18 4 2 17 4 19 18 4 2 17 4 19 18 4 2 17 4
+Mod26 20 21 0 6 23 7 24 21 2 6 11 1 22 7 6 12 12 25 22 17 6 8 8
Texte U V A G X H Y V C G L B W H G M M Z W R O I I
Table 3.9 : Un chiffrement de Vigenère.

Bien que ce chiffrement soit beaucoup plus sûr que le chiffrement de César, il peut
encore être facilement cassé. En effet, lorsque les messages sont beaucoup plus longs
que la clé, il est possible de repérer la longueur de la clé et d’utiliser pour chaque
séquence de la longueur de la clé la méthode consistant à calculer la fréquence
d’apparition des lettres, permettant de déterminer un à un les caractères de la clé…

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 31

Chap.3 Cryptographie

Pour éviter ce problème, une solution consiste à utiliser une clé dont la taille est proche
de celle du texte afin de rendre impossible une étude statistique du texte chiffré. Ce type
de système de chiffrement est appelé système à clé jetable.
III.9 Le chiffrement par transposition (par permutation)
Matériellement : (Technique Assyrienne)
Cette technique de chiffrement est vraisemblablement la première preuve de l'utilisation
de moyens de chiffrement en Grèce dès 400 avant Jésus Christ pour dissimuler des
messages écrits sur des bandes de papyrus [FLO 02].

Figure 3.2 : Le cylindre de Scytale.

La technique consistait à:
- enrouler une bande de papyrus sur un cylindre appelé scytale

- écrire le texte longitudinalement sur la bandelette ainsi enroulée (le message dans
l'exemple ci-dessus est "OMARY FOUZIA ARRIVE")

Le message une fois déroulé n'est plus compréhensible (dans l’exemple ci-dessus
"OYU IM ZAVAFIREROAR ").

Il suffit au destinataire d'avoir un cylindre de même rayon pour pouvoir déchiffrer le

message. En réalité un casseur (il existait des casseurs à l'époque...) peut déchiffrer le
message en essayant des cylindres de diamètre successifs différents, ce qui revient à dire
que la méthode peut être cassée statistiquement (il suffit de prendre les caractères un à
un, éloignés d'une certaine distance).
Formellement : On fixe un entier m≠0 et une permutation de {1, 2 …m} qui seront la
clé de chiffrement, par exemple avec m=5 et la permutation
 
1 2 3 4 5
 
5 3 1 2 4


[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 32

Chap.3 Cryptographie

Le message "CRYPTOGRAPHIE CLASSIQUE" sera chiffré en

"TYCRPPROGACEHI ISLAS EQU". En effet, le texte en clair est décomposé en
blocs de cinq caractères chacun. Chaque bloc est transformé en en utilisant la
permutation ci-dessus. Par exemple CRYPT et OGRAP sont chiffrés respectivement
en TYCRP et PROGA et ainsi de suite. La clé de déchiffrement est le nombre 5 et la
permutation inverse :
1 2 3 4 5
 
 3 4 2 5 1
 
III.10 Chiffrement par substitution
III.10.1 La méthode de substitution
Le chiffrement par substitution consiste à remplacer dans un message une ou plusieurs
entités (généralement des lettres) par une ou plusieurs autres entités [MEN 97].
On distingue plusieurs types de cryptosystèmes par substitution :
• La substitution mono-alphabétique consiste à remplacer chaque lettre du
message par une autre lettre de l’alphabet. Comme le chiffrement par décalage.
• La substitution poly-alphabétique consiste à utiliser une suite de chiffres mono-
alphabétique réutilisée périodiquement. Comme exemple le chiffrement de
Vigenère.
• La substitution homophonique permet de faire correspondre à chaque lettre
du message en clair un ensemble possible d’autres caractères.
• La substitution de polygramme consiste à substituer un groupe de caractères
(polygramme) dans un message par un autre groupe de caractères.
- Au moyen d’une table (système de Playfair)
- Au moyen d’une transformation mathématique (système de Hill)
III.10.2 Les faiblesses de la méthode de substitution
Dans le chiffrement par substitution, la clé est simplement la permutation des 26 lettres
alphabétiques. Le nombre de clés est 26 ! Une recherche exhaustive de la clé est donc
impossible. Cependant, le chiffrement par substitution possède une grosse faiblesse
structurelle [GIR 01] : dans les langues, toutes les lettres n'ont pas la même fréquence
d'apparition. Dans un texte français, il y a presque toujours beaucoup plus de E que de
W. Or, le E est toujours remplacé par la même lettre et le W aussi. Donc, si dans votre
texte, la lettre qui apparaît le plus fréquemment est un L, il y a de fortes chances que ce
soit un E. En revanche, si il n'y a presque pas de D, on peut se dire que c'est

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 33

Chap.3 Cryptographie

probablement un W, ou un K, un X, etc ... Voici un exemple de l'analyse de la

fréquence d'apparition des différentes lettres dans une biographie :

Figure 3.3 : Fréquences des lettres en Français.

On voit clairement apparaître sur ce graphique plusieurs groupes de lettres qui ont la
même fréquence. Le E est de loin le plus fréquent. Il y a donc de fortes chances que la
lettre la plus fréquente du texte codé est en fait un E.
• Ensuite, les A, I, N, R, S, T.
• Puis les O, U, L, ...
Pour déterminer dans le deuxième groupe quelle lettre est un A, une méthode possible
est d'étudier les lettres qui apparaissent isolées (c'est-à-dire dans un mot à une seule lettre
du texte) : la lettre isolée la plus fréquente a de fortes chances d'être un A.
Ensuite, on étudie les groupes de 2 lettres. On peut étudier leur fréquence d'apparition
dans le texte, et comparer aux fréquences possibles du texte. Par exemple, les EN, NE,
TE, SE sont bien plus fréquents que les ST, NR, ...
Exemple commenté :
Afin de décoder un message chiffré. Son fonctionnement est très naïf. La lettre la plus
fréquente est assimilée à un E. La lettre la plus isolée est supposée être un A. On regarde
ensuite les mots de 2 lettres pour distinguer les lettres N, R, S, T, puis O, U, L.
Nous étudions par exemple le message suivant, chiffré par substitution mono
alphabétique :
TIXIV KYWXEZ PINIYRI-HMVMGLPIX IWX RI PI 13 JIZVMIV 1805 E HYVIR, YRI
ZMPPI H'EPPIQEKRI WMXYII E QM-GLIQMR IRXVI EEGLIR IX GSPSKRI. WSR

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 34

Chap.3 Cryptographie

TIVI C IXEMX VIGIZIYV HIW TSWXIW. HMVMGLPIX IWX YR IPIZI FVMPPERX,

UYM EGLIZI WIW IXYHIW WIGSRHEMVIW E 16 ERW.
Ce message a bien l'air totalement inintelligible. Une première étude nous donne:
METER FUSTAG LEYEUNE-DIRICVLET EST NE LE 13 HEGRIER 1805 A DUREN,
UNE GILLE D'ALLEPAFNE SITUEE A PI-CVEPIN ENTRE AACVEN ET
COLOFNE. SON MERE X ETAIT RECEGEUR DES MOSTES. DIRICVLET EST UN
ELEGE QRILLANT, BUI ACVEGE SES ETUDES SECONDAIRES A 16 ANS.
Certes, tout n'est pas parfait, mais on reconnaît quand même facilement de nombreux
mots, et il n'est plus très difficile de reconstituer le texte exact :
PETER GUSTAV LEJEUNE-DIRICHLET EST NE LE 13 FEVRIER 1805 A DUREN,
UNE VILLE D'ALLEMAGNE SITUEE A MI-CHEMIN ENTRE AACHEN ET
COLOGNE. SON PERE Y ETAIT RECEVEUR DES POSTES. DIRICHLET EST UN
ELEVE BRILLANT, QUI ACHEVE SES ETUDES SECONDAIRES A 16 ANS.
III.11 Systèmes à clés jetables
Pour éviter les attaques statiques il faut utiliser une substitution qui rend le texte chiffré
non analysable statiquement. D’où l’apparition des systèmes à clés jetables comme
solution [LAB 01]. Cela consiste à générer une clé qui est une suite binaire parfaitement
aléatoire (phénomène physique aléatoire : le bruit électromagnétique). Pour chiffrer un
message faire le ou exclusive (XOR) du message et de la clé.
Si chaque clé ne sert qu’une fois, le chiffre est incassable. Mais il y a l’inconvénient de la
taille de la clé et le problème de synchronisation (si l’on perd une seule donnée on ne
sait plus déchiffrer).

IV Cryptographie moderne
Si le but de la cryptographie classique est d’élaborer des méthodes permettant de
transmettre des données de manière confidentielle, la cryptographie moderne s’intéresse
en fait plus généralement aux problèmes de sécurité des communications. Le but est
d’offrir un certain nombre de services de sécurité comme la confidentialité, l’intégrité,
l’authentification des données transmises. La cryptographie moderne se compose de
deux grandes parties : La cryptographie symétrique et la cryptographie asymétrique.
IV.1 Cryptographie symétrique
Aussi appelée cryptographie conventionnelle ou à clé secrète.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 35

Chap.3 Cryptographie

Principe : sur la base d’une clé secrète, réaliser une transformation capable
respectivement de rendre illisible et de restituer une pièce d’information [MEN 97]. Il
existe de nombreux systèmes de chiffrement symétrique (DES, IDEA, AES, …). La
clé étant secrète, elle doit être échangée entre les intervenants par un canal confidentiel.
Dans les algorithmes symétriques, on distingue le chiffrement par bloc et le chiffrement
continu. Dans le premier, le message en clair est décomposé en blocs de même taille ;
chacun d’eux est chiffré individuellement et de la même manière. Pour le second,
chaque unité (lettre dans le cas d'un e-mail) du message en clair est chiffrée une par une
(exemples : substitution, chiffrement affine, masque jetable,…).

Clé secrète utilisée par Clé secrète utilisée par

l’expéditeur le destinataire

Texte chiffré
Algorithme de Algorithme de
chiffrement déchiffrement

Texte en clair Texte en clair

Figure 3.4: Algorithme de chiffrement symétrique

IV.1.1 DES
Le 15 mai 1973 le NBS (National Bureau of Standards, aujourd'hui appelé NIST
National Institute of Standards and Technology) a lancé un appel dans le Federal
Register (l'équivalent aux Etats-Unis du Journal Officiel en France) pour la création d'un
algorithme de chiffrement répondant aux critères suivants:

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 36

Chap.3 Cryptographie

- Ayant un haut niveau de sécurité lié à une clé de petite taille servant au chiffrement
et au déchiffrement
- Compréhensible
- Ne devant pas dépendre de la confidentialité de l'algorithme
- Adaptable et économique
- Efficace et exportable
Fin 1974, IBM propose Lucifer, qui, grâce à la NSA (National Security Agency), est
modifié le 23 novembre 1976 pour donner le DES (Data Encryption Standard). Le DES
a finalement été approuvé en 1978 par le NBS. Le DES fût normalisé par l'ANSI
(American National Standard Institute) sous le nom de ANSI X3.92, plus connu sous la
dénomination DEA (Data Encryption Algorithm) [MÜL 03].
C'est un système de chiffrement par blocs de 64 bits, dont 8 bits (un octet) servent de
test de parité (pour vérifier l'intégrité de la clé). Chaque bit de parité de la clef (1 tous les
8 bits) sert à tester un des octets de la clef par parité impaire, c'est-à-dire que chacun des
bits de parité est ajusté de façon à avoir un nombre impair de '1' dans l'octet à qui il
appartient. La clé a donc une longueur "utile" de 56 bits, ce qui signifie que seuls 56 bits
servent dans l'algorithme.
L'algorithme [MEN 97] consiste à faire des combinaisons, des substitutions et des
permutations entre le texte à chiffrer et la clé, en faisant en sorte que les opérations
puissent se faire dans les deux sens (pour le déchiffrement). On appelle code produit la
combinaison entre substitutions et permutations. La clé est codée sur 64 bits et formée
de 16 blocs de 4 bits, généralement notés k1 à k16. Etant donné que "seulement" 56 bits
servent réellement à chiffrer, il y a 256 (soit 7.2*1016) possibilités de clés différentes
a) La génération des clés partielles :
La clé initiale K0 de 64 bits subit, dans un premier temps, une première permutation CP1
(une réduction de 8 bits les bits de parité de chaque octet). La chaîne de caractères
résultante de 56 bits est alors divisée en 2 blocs de 28 bits (L0 et R0). Chacun d'eux subira
alors un décalage à gauche. Les deux nouveaux blocs (L1 et R1) seront alors concaténés
avant une nouvelle permutation CP2 (une autre réduction de 8 bits). On obtient alors
une clé partielle K1 de 48 bits.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 37

Chap.3 Cryptographie

On réitérera ces opérations 15 fois pour générer les 15 clés (K2, K3,..., K16). La différence
résidera dans l'incrémentation des paramètres des deux permutations.

57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 21 6 15 28 3 5 1 24 11 17 14
10 2 59 51 43 35 27 19 11 3 60 52 44 36 2 13 20 27 7 16 8 26 4 12 19 23
63 55 47 39 31 23 15 7 62 54 46 38 30 22 48 33 45 51 40 30 55 47 37 31 52 41
14 6 61 53 45 37 29 21 13 5 28 20 12 4 32 29 36 50 42 46 53 34 56 39 49 44

Table 3.10 : Les permutations CP1 et CP2

1 2 4 6 8 10 12 14 15 17 19 21 23 25 27 28

Table 3.11 : La table des décalages à gauche LS

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 38

Chap.3 Cryptographie

Clé initiale K0 de 64 bits

i =1

Permutation CP1

56 bits

28 bits 28 bits

Partie gauche Li-1 Partie droite Ri-1

Décalage à gauche LS[i]

28 bits 28 bits

Partie gauche Li Partie droite Ri

56 bits

Permutation CP2

Clé partielle Ki de 48 bits

i ← i+1

Non
i >16 ?

Figure 3.5 : La diversification des clés en DES

b) Le chiffrement :
Les grandes lignes de l'algorithme sont les suivantes:
- Fractionnement du texte en blocs de 64 bits (8 octets)
- Permutation initiale des blocs
- Découpage des blocs en deux parties: gauche et droite, nommées G et D

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 39

Chap.3 Cryptographie

- Etapes de permutation et de substitution répétées 16 fois (appelées rondes)

- Recollement des parties gauche et droite puis permutation initiale inverse
Dans un premier temps, chaque bit d'un bloc est soumis à la permutation initiale,
pouvant être représentée par la matrice de permutation initiale (notée PI)
Cette matrice de permutation indique, en parcourant la matrice de gauche à droite puis
de haut en bas, que le 58ème bit du bloc de texte de 64 bits se retrouve en première
position, le 50ème en seconde position et ainsi de suite.
Une fois la permutation initiale réalisée, le bloc de 64 bits est scindé en deux blocs de 32
bits, notés respectivement G et D (pour gauche et droite, la notation anglo-saxonne
étant L et R pour Left and Right). On note G0 et D0 l'état initial de ces deux blocs. Ces
derniers sont soumis à un ensemble de transformations itératives appelées rondes et
schématisées dans la figure 3.6. On note Gn et Dn les blocs obtenus à la nème ronde par
le biais de la fonction F schématisée dans la figure 3.7. Pour interpréter les opérations
de cette figure, nous disons que les 32 bits du bloc Dn sont étendus à 48 bits grâce à une
matrice appelée table d'expansion et notée E, dans laquelle les 48 bits sont mélangés et
16 d'entre eux sont dupliqués, aboutissant à E(Dn).

L'algorithme DES procède ensuite à un OU exclusif entre la clé partielle Kn+1 et E(Dn).
Le résultat est un bloc de 48 bits que nous appellerons D’n et auquel nous appliquons
les S-boxes. Il y a huit boites différentes . Elles sont représentées dans la table 5 par
des tableaux à 4 lignes ( indexées par 0, 1, 2, 3) et 16 colonnes (indexées de 0 à 15).

Soit B= b b b b b b un sous bloc de 6 bits de D’n , on calcule une chaîne de quatre

1 2 3 4 5 6

bits Sj(B) = C = c c c c . Les deux bits b b forment la représentation binaire de

1 2 3 4 1 6

l’indice d’une ligne h de Sj (0 ≤ h ≤ 3) et les quatre bits b b b b composent la

2 3 4 5

représentation binaire de l’indice d’une colonne k de Sj (0 ≤ k ≤ 15), C est alors la

représentation binaire sur quatre bits du terme Sj(h , k).

Le bloc obtenu D″n de longueur 32 bits est réordonnée suivant une permutation fixée P.
Le résultat est combinée avec Gn par Ou exclusif pour donner Dn+1 . Ainsi Gn+1 prend
la valeur de Dn.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 40

Chap.3 Cryptographie

Bloc en clair 64 bits

PI

G0 D0

K1

L1
G1 D1
R1

K2

L2
G15 D15
R2

K16

D16 G16

PI-1

Bloc chiffré 64 bits

Figure 3.6 : Enchaînement des opérations de

chiffrement dans le système DES

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 41

 Chap.3 Cryptographie

58 50 42 34 26 18 10 2 40 8 48 16 56 24 64 32
60 52 44 36 28 20 12 4 39 7 47 15 55 23 63 31
62 54 46 38 30 22 14 6 38 6 46 14 54 22 62 30
64 56 48 40 32 24 16 8 37 5 45 13 53 21 61 29
57 49 41 33 25 17 9 1 36 4 44 12 52 20 60 28
59 51 43 35 27 19 11 3 35 3 43 11 51 19 59 27
61 53 45 37 29 21 13 5 34 2 42 10 50 18 58 26
63 55 47 39 31 23 15 7 33 1 41 9 49 17 57 25

Table 3.12 :La permutation initiale: PI et son inverse PI-1

S1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 S2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 1 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 2 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 3 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
S3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 S4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 0 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
1 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 1 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
2 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 2 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
3 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 3 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
S5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 S6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 0 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
1 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 1 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
2 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 2 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
3 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 3 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
S7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 S8 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 0 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
2 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
3 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 3 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11

Table 3.13 : les S-Boxes

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 42

Chap.3 Cryptographie

32 1 2 3 4 5 16 7 20 21
4 5 6 7 8 9 29 12 28 17
8 9 10 11 12 13 1 15 23 26
12 13 14 15 16 17 5 18 31 10
16 17 18 19 20 21 2 8 24 14
20 21 22 23 24 25 32 27 3 9
24 25 26 27 28 29 19 13 30 6
28 29 30 31 32 1 22 11 4 25

Table 3.14 : La table d'expansion E et la permutation P

Dn-1 Kn
32bits 48bits

48bits

48bits

8x6 bits

S1 S2 S3 S4 S5 S6 S7 S8

8x4 bits

32bits
P

32bits F(Dn-1,Kn) = P(S(E(Dn-1) ⊕ Kn))

Gn-1

Dn

Figure 3.7 : Description de l’opération Dn=Gn-1 ⊕ F(Dn-1,Kn)

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 43

Chap.3 Cryptographie

c) Le déchiffrement :
Pour déchiffrer on utilise le même algorithme de chiffrement, mais cette fois-ci en
inversant l’ordre d’ application des clés, c’est à dire on commence par la clé K16 et on
termine avec la clé K1.
d) Le triple DES :
En 1990 Eli Biham et Adi Shamir [BIH 93] ont mis au point la cryptanalyse
différentielle. Elle permet de casser des versions restreintes de DES, dans lesquels on
diminue le nombre de tours de la boucle principale. On peut ainsi facilement casser un
DES à 8 ou à 10 tours. Le DES complet à 16 tours est resté hors de portée de cette
attaque. Ceci d’une part. D’autre part, l’ordinateur baptisé « DES cracker » contenant
1536 puces et pouvant chercher 88 milliards de clés par seconde, a réussi le concours
des laboratoires RSA, en trouvant une clé DES en 56 heures.

Cette méthode marche pour un nombre de rondes inférieur à 15, or l'algorithme Triple
DES (TDES) contient 16 rondes ce qui donne une solution à court terme. Le processus
du TDES consiste à enchaîner trois chiffrement DES à l'aide de deux clés de 56 bits (ce
qui équivalant à une clé de 112 bits) [FLO 02]. Le TDES permet d'augmenter
significativement la sécurité du DES, toutefois il a l'inconvénient majeur de demander
également plus de ressources pour le chiffrement et le déchiffrement.

IV.1.2 IDEA
IDEA est un système de chiffrement par blocs de 64 bits, avec une clé de 128 bits, qui
tourne sur 8 rondes [MEN 97]. Cet algorithme, utilisé par PGP, n'utilise que trois
opérations simples : le XOR notée ⊕ , l'addition modulo 216 notée [+] et la
multiplication modulo 216+1 notée ⊗ . Le principe est basé sur la difficulté d’inverser les
nombres dans un corps intègre abélien Z/ /pZ/ .

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 44

Chap.3 Cryptographie

Figure 3.8 : Le chiffrement IDEA

a) Génération des clés

Désignons par K la clé de 128 utilisée par IDEA. Nous présentons ci-dessous
l’algorithme permettant d’obtenir les 52 clés dérivées.

In put: Clé K de 128 bits.

Sortie : Les 52 clés de taille 16 bits Ki (r) pour les 8 rondes et la transformation finale.

(1) (1) (8) (8) (9) (9) (9) (9)

1. Ordonner les sous –clés K1 ,…, K6 …, K1 ,…, K6 et K1 , K2 , K3 , K4 .

2. Décomposer K en 8 blocs de 16 bits chacun ; affecter ces derniers aux premières 8

sous clés.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 45

Chap.3 Cryptographie

3. Répéter ce qui suit jusqu’à ce que toutes les 52 clés soient affectées :

Décaler d’une manière cyclique, vers la gauche, les 25 bits de la clé K; décomposer de
nouveau le résultat en 8 blocs ; affecter ces blocs aux huit prochaines sous clés.

b) Algorithme de chiffrement IDEA

Entée : Bloc de texte de 64 bits M=m1…m64 . Une clé K de 128 bits.

Sortie : Bloc chiffré Y=(Y1, Y2, Y3, Y4 )

1. Génération des 52 clés par l’algorithme ci-dessus.

2. (X1, X2, X3, X4) ← (m1…m16, m17…m32, m33…m48, m49…m64).

3. Pour r allant de 1 à 8 faire

(r) (r) (r) (r)

a) X1 ← X1 ⊗ K1 , X4 ← X4 ⊗ K4 , X2 ← X2[+] K2 , X3 ← X3[+] K3

(r) (r)
b) t0 ← K5 ⊗ (X1 ⊕ X3 ), t1 ← K6 ⊗ (t0[+](X2 ⊕ X4)), t2 ← t0[+]t1

c) X1 ← X1[+]t1, X4 ← X4 ⊕ t2, a ← X ⊕ t2, X2 ← X3 ⊕ t1, X3 ← a

(9)
4. Y1 ← X1 ⊗ K1 , Y4 ← X4 ⊗ K4(9), Y2 ← X3[+]K2(9),Y3 ← X2[+]K3(9)
(transformation de sortie)

c) Déchiffrement

On utilise l’algorithme de chiffrement de IDEA, mais cette fois-ci avec le texte chiffré Y
comme entrée et la même clé K. Le seul changement réside dans la génération des clés
dérivées. En fait, on utilise K pour générer les sous clés Ki (r) ; à partir de ces dernières,
d’autres clés Ki’ (r) sont obtenues dans la table 3.15 ; ensuite on utilise Ki’ (r) à la place des
(r)
Ki dans l’algorithme de chiffrement IDEA. Dans la table3.15, -Ki dénote l’opposé
modulo 216 de Ki , l’entier u=(216 -Ki)AND O × FFFF, 0 ≤ u ≤ 216-1. Ki-1 dénote l’inverse
multiplicative de Ki mod(216+1), se trouvant aussi dans {0, 1, …,216-1}, dérivant de

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 46

Chap.3 Cryptographie

l’extension de l’algorithme d’Euclide [Men 97] qui pour deux ,entiers a ≥ b ≥ 0 retourne
deux entiers x et y tels que : ax+by=pgcd(a,b). En utilisant a=216+1 et b=K ; le pgcd est
toujours égal à 1 (sauf pour Ki=0 étudié séparément ) et ainsi Ki-1 =y ou 216+1+y si y<0.
Quand Ki=0, cette entrée est appliquée à 216 et (216)-1=216 et alors (Ki)-1=0.

Ronde r K1'(r) K2'(r) K3'(r) K4'(r) K5'(r) K6'(r)

r=1 (K1(10-r))-1 -K2(10-r)
-K3(10-r) (10-r) -1
(K4 ) K5(9-r) K6(9-r)
2≤r≤8 (K1(10-r))-1 -K3(10-r) -K2(10-r) (K4(10-r))-1 K5(9-r) K6(9-r)
r=9 (K1(10-r))-1 -K2(10-r)
-K3(10-r) (10-r) -1
(K4 ) -- --
Table 3.15: Les sous clés de déchiffrement Ki'(r)
générées à partir des sous clés Ki(r)

IV.1.3 AES
Avec le temps, et les progrès de l'informatique, les 256 clés possibles du DES ne
représentent plus une barrière infranchissable. Il est désormais possible, avec des
moyens modestes, de percer les messages chiffrés par DES en un temps raisonnable. En
janvier 1997, le NIST (National Institute of Standards and Technologies) des Etats-Unis
lance un appel d'offres pour élaborer l'AES, Advanced Encryption System [BAY 03].
Le cahier des charges comportait les points suivants :

- Une grande sécurité.

- Une large portabilité : L'algorithme devant remplacer DES, est destiné à servir
aussi bien dans les cartes à puces, dans les processeurs 8 bits peu puissants, que
dans des processeurs spécialisés pour chiffrer des milliers de télécommunications
à la volée.

- La rapidité.

- Une lecture facile de l'algorithme, puisqu'il est destiné à être rendu public.

Techniquement, le chiffrement doit se faire par blocs de 128 bits, les clés comportant
128, 192 ou 256 bits.

Au 15 juin 1998, date de la fin des candidatures, 21 projets ont été déposés. Certains
sont l’œuvre d'entreprises (IBM), d'autres regroupent des universitaires (CNRS), les
derniers sont écrits par à peine quelques personnes. Pendant deux ans, les algorithmes

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 47

Chap.3 Cryptographie

ont été évalués par des experts, avec forum de discussion sur Internet, et organisation de
conférences. Le 2 octobre 2000, le NIST donne sa réponse : c'est le Rijndael qui est
choisi, un algorithme mis au point par 2 belges, Joan Daemen et Vincent Rijmen.

Le Rijndael procède par blocs de 128 bits, avec une clé de 128 bits également. Chaque
bloc subit une séquence de 5 transformations répétées 10 fois :

- Addition de la clé secrète (par un ou exclusif).

- Transformation non linéaire d'octets : les 128 bits sont répartis en 16 blocs de 8
bits (8 bits=un octet), eux même dispatchés dans un tableau 4×4. Chaque octet est
transformé par une fonction non linéaire S.
- Décalage de lignes : les 3 dernières lignes sont décalées cycliquement vers la
gauche : la 2ème ligne est décalée d'une colonne, la 3ème ligne de 2 colonnes, et la 4ème
ligne de 3 colonnes.
- Brouillage des colonnes : Chaque colonne est transformée par combinaisons
linéaires des différents éléments de la colonne (ce qui revient à multiplier la matrice
4×4 par une autre matrice 4×4). Les calculs sur les octets de 8 bits sont réalisés
dans le corps à 28 éléments.
- Addition de la clé de tour : A chaque tour, une clé de tour est générée à partir de la
clé secrète par un sous-algorithme (dit de cadencement). Cette clé de tour est
ajoutée par un ou exclusif au dernier bloc obtenu.
Pour une étude détaillée de l’AES , voir [STI 03].
IV.2 Cryptographie asymétrique
Les problèmes de distribution des clés sont résolus par la cryptographie à clé publique,
dont le concept fut inventé par Whitfield Diffie et Martin Helman en 1975 [LAB 01].
Elle repose sur un schéma asymétrique qui utilise une paire de clés pour le chiffrement :
une clé publique, qui chiffre les données, et une clé privée correspondante, qui sera
utilisée pour le déchiffrement. Vous publiez votre clé publique et vous gardez votre clé
privée secrète. Toute personne en possession d’une copie de la clé publique peut chiffrer
des informations que vous seul pourrez déchiffrer avec votre clé privée.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 48

Chap.3 Cryptographie

IV.2.1 Schéma ElGamal

a) Problème du logarithme discret
Même s’il n’est pas très utilisé en tant que système de chiffrement, le schéma ElGamal
est néanmoins à l’origine du standard de signature digitale DSS ( Digital Signature
Standard ) [MEN 97].
Il est basé sur le principe du chiffrement résiduel qui se résume ainsi :
Soient A et N deux nombres premiers entre eux et soit B tel que : AB = 1 mod(N).
Le cryptogramme d’un message élémentaire M tel que : 0 ≤ M ≤ N-1 est :
M' = AM mod(N)
On retrouve M en calculant M" = BM' mod(N) .
Dans cette méthode, N peut être connu par tous, A doit être connu par l’expéditeur et B
par le destinataire.
Connaissant N et A (resp. B) il est très facile de déterminer B (resp. A) par le calcul d’un
inverse modulaire.
Donc, pour que le chiffrement soit sûr il est nécessaire que A et B soient secrets.

L’intérêt du schéma ElGamal est de donner une méthode efficace permettant de rendre
A (et B) secrets pour celui qui ne possède pas la clef de déchiffrement, en se basant sur
la difficulté du calcul d’un logarithme discret.
En effet, il est impossible, dans un temps raisonnable, de déterminer dans certains cas la
valeur d’un logarithme discret.
Pour expliquer le problème du logarithme discret qui est à la base du schéma ElGamal.
Nous aurons besoin de quelques notions d’algèbre.
Notation :
▪ Z//nZ/ est l’ensemble des classes d’équivalence modulo n.

▪ En est l’ensemble des éléments inversibles de Z//nZ/ .

Définition : (Groupe cyclique)

Un groupe multiplicatif G est dit cyclique s’il existe un élément g de G (g est dit
générateur de G) engendrant G, c’est à dire pour tout élément a de G, il existe un entier
positif p tel que : a = gp.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 49

Chap.3 Cryptographie

Définition : (Fonction indicatrice d’Euler)

La fonction indicatrice d’Euler ϕ est la fonction définie de IN dans IN par :
ϕ(n) = cardinal ({p : réel tel que 0<p<n et p est premier avec n })
Propriétés :ϕ vérifie les propriétés suivantes :
▪ ϕ (n ) = ∑ ϕ (d )
dn

▪ ϕ (n) = n-1 si et seulement si n est un nombre premier

▪ Soit g un générateur de En supposé cyclique et x un élément de En il
existe s tel que : 0 ≤s ≤ ϕ( n ) vérifiant : x = gs mod(n)

Le problème du logarithme discret consiste en le calcul de s, connaissant x, g et n.

Ce problème est très difficile pour n bien choisi. En effet, le calcul de x = gs mod(n),
connaissant n, g et s est une chose facile et requiert au maximum 2log2(n) multiplications
modulaires. Par contre, pour x donné, le calcul de s tel que x = gs mod(n) connaissant
x, g et n est infaisable pour n très grand et bien choisi.
Pour illustrer la difficulté du problème, considérons le meilleur algorithme actuel du
calcul de logarithme discret. Cet algorithme est de l’ordre de

exp ( log( n ) log(log( n ))) . )

Si on dispose d’un ordinateur effectuant 106 opérations par seconde, le temps nécessaire
pour le calcul d’un logarithme discret modulo n est donné par le tableau suivant :

Nombre d’opérations pour le Temps pour le calcul de

Valeur de n
calcul d’un logarithme discret ce logarithme
10
10 4908 4x9x10-3 secondes
1030 2x68x107 27 secondes
70 12
10 2x69x10 31 jours
10100 2x34x1015 74 ans
150 19
10 3x25x10 107ans
10300 1x53x1023 4x86x1015 ans
Table 3.16 : Difficulté du calcul de logarithme discret

Dans le schéma d’ ElGamal, cryptosystème à clefs publiques, l’élément s est le secret

contenu dans la clef privée et les entiers n, g et x forment la clef publique.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 50

Chap.3 Cryptographie

Pour utiliser le schéma ElGamal, il faut tout d’abord construire des clefs de chiffrement,
c’est à dire déterminer les quatre éléments n, g, x, et s.

Nous nous intéressons dans un premier lieu au choix de n, afin que En soit un groupe
cyclique et afin d’assurer l’existence d’un générateur de En. A ce sujet, le théorème
suivant nous donne une condition suffisante.

Théorème 2 : En. est cyclique si n est un nombre premier

La démonstration du théorème ci-dessus se base sur le théorème suivant :

Théorème 3 : Les éléments inversibles de Z/ /nZ/ sont les images modulo n des

entiers premiers avec n, et il y en a ϕ(n).

Corollaire 1 : Le nombre de générateurs d’un groupe cyclique G d’ordre n est ϕ(n).

De plus, si x est un générateur de G, alors les autres générateurs de G sont
les xk, tels que pgcd(n,k)=1.
Intéressons-nous maintenant aux choix des autres paramètres g, x et s.
D’après les résultats ci-dessus, si n est premier alors En est un groupe cyclique à n-1
éléments. Donc, si g est un générateur de En , alors En = {1, g, g2, …, gn-2}.
Par suite, si x est un élément de En alors il existe un entier s dans {1, …, n-2} tel que :
x = gs mod(n)
b) Chiffrement et déchiffrement
Considérons comme message à chiffrer un nombre M compris entre 0 et n-1. Le
chiffrement s’effectue par : M’=AM mod(n)
1
Le déchiffrement se fait par : M" = M ' mod(n) , avec pgcd(A,n)=1.
A
Pour chiffrer, il faut déterminer un élément A, premier avec n, qui reste secret aux yeux
de tous sauf à ceux du destinataire du message.

Comme n est un nombre premier, tout nombre entier choisi dans {1, …, n-1} est
premier avec n.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 51

Chap.3 Cryptographie

Soit α un élément de En . Il existe k un nombre compris entre 2 et n-2 tel que :

α = gk mod(n) .

Posons A = xk mod(n) . A est bien un nombre premier avec n.

On chiffre alors le message M en calculant M’= [Link] mod(n).

On envoie M’ ainsi que α.

La sécurité du chiffrement est assurée par le fait que, α et la clef publique, personne ne

peut déterminer k, et donc ne peut déchiffrer en calculant : M" = 1k M' mod(n)

x

D’où la nécessité de connaître l’inverse de xk mod(n).

Montrons le rôle de la clé privée. On sait que : α = gk mod(n) et M’ = [Link] mod(n).

Donc αs = gks mod(n). De plus on a : xk = αs mod(n). D’où un inverse de xk mod(n) est

un inverse de αs modulo n. La connaissance de s, secret permet donc de
1
déterminer mod(n) .
xk

On peut donc déchiffrer en calculant M " = 1 s M 'mod( n ) et comme on a choisi M

α
compris entre 0 et n-1 on obtient M"=M.

c) Exemple d’application
Considérons le nombre premier n=181. Un générateur de Z//nZ/ est g=23.

Prenons s=7. Alors x=57 ( x=gs mod(n))

D’où la clef publique : ( 181 , 23 , 57 ) et la clef privée est : ( 181 , 7 )

Supposons que le message à chiffrer est une date de naissance : 071290.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 52

Chap.3 Cryptographie

Le chiffrement :

Comme n est de longueur 3 ; on décompose le message à des blocs de longueur 2 :

[ 07 12 90 ] qui correspondent aux nombres : 7, 12 et 90

Prenons un nombre k au hasard compris entre 2 et n-1, soit k=6.

Nous calculons α = gk = 236 =152 mod(181).

Ensuite, on chiffre les nombres en les multipliant par αs = gks = xk = 576 mod(181)

7 x 576 =146 mod(181)

12 x 576 = 121 mod(181)

90 x 576 = 93 mod(181)

Ce qui nous donne les éléments suivants : [ 146 121 093]

(On rajoute des 0 s’il est nécessaire, afin de n’avoir que des éléments de 3 chiffres)

On envoie alors le message chiffré : 146121093, ainsi que α = 152.

IV.2.2 RSA
Développé au MIT (Massachussets Institute of Technology) en 1977 par Ronald Rivest,
Adi Shamir et Leonard Adleman; le système RSA est à la fois sûr et à clef publique
[STI 03]. Il convient parfaitement pour le chiffrement des fichiers stockés dans les
mémoires de masse des ordinateurs personnels et il préserve la confidentialité des
messages électroniques.
Il possède une sécurité potentielle de travail largement plus grande que le système DES
(Data Encryption Standard, 1977) qui est pourtant utilisé par les organisations à
caractère fédéral, commercial ou privé pour sa rapidité.
Le RSA est un chiffrement exponentiel qui se résume ainsi :
Soient c et d deux entiers tels que :

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 53

Chap.3 Cryptographie

1 ≤ c , d ≤ ϕ(n)-1 avec pgcd(c ,ϕ(n)) =1 et cd = 1 mod(ϕ(n)).

Le cryptogramme de M est M’ = Mc mod(n).
En calculant M’d mod(n), on retrouve M.
Le RSA permet en outre d'établir une authenticité, c'est à dire qu'il gère le principe de
signature en utilisant seulement son algorithme de chiffrement.
Le chiffrement RSA apparaît dans la gestion des clés, c'est à dire qu'il permet de faire
transiter par Internet la clef IDEA qui sert à faire fonctionner le PGP.
On préfère utiliser des systèmes de chiffrement plus rapides (tels que les systèmes DES
ou IDEA) quand il s'agit de travailler sur des informations de longueur importante.
En effet, les inconvénients du RSA sont la quantité d'espace mémoire utilisée et la
lenteur de l'algorithme tant pour la génération des clés que pour le chiffrement d'un
message (1000 fois plus long que le DES).
a) Base mathématique de RSA
En plus des notions d’algèbre que nous avons vues au paragraphe ci-dessus, nous allons
voir d’autres notions d’algèbres qui sont à la base de la compréhension du système RSA.

Théorème 4 : (Petit théorème de Fermat)

Soit p un entier naturel premier et soit a un entier relatif non multiple de
p alors ap-1 = 1 mod(p).

En se basant sur ce théorème, nous pouvons démontrer les théorèmes et les corollaires
ci-dessous.
Théorème 5 : Soit a un entier non divisible par le nombre premier p et soit r et s deux
entiers tels que r = s mod(p-1) alors ar = as mod(p)

Corollaire 2 : Pour tout entier a et tout nombre premier p et avec r tel que :
r=1 mod(p-1) on a : ar =a mod(p)
En particulier, ap = a mod(p)
Corollaire 3 : Soit a un entier non divisible par les deux nombres premiers distincts
p et q et soient r et s deux entiers tels que : r=s mod((p-1)(q-1)) alors ar = as mod(pq). .
Le théorème suivant permet de construire et de démontrer l’algorithme RSA

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 54

Chap.3 Cryptographie

Théorème 6 : Soient p et q deux nombres premiers distincts, et a un entier quelconque.

Soit r un entier tel que r=1 mod((p-1)(q-1)) alors ar = a mod(pq).
b) Difficulté mathématique à la base du système RSA
Théorème 7 : (généralisation du théorème de Fermat par Euler)
Soit a et n deux entiers premiers entre eux alors aϕ(n) = 1 mod(n).
Propriété : ϕ(n)peut être calculé grâce à la formule suivante :
 
ϕ ( n ) = n   1 − 1  1 − 1
 
 ...  1 − 1
 
 p 1  p2   p m  
où p1, p2, …pm sont les facteurs premiers de n.
La propriété ci-dessus nous montre le rapport qui existe entre le calcul de ϕ(n) et les
facteurs premiers de n.
Donc, déterminer ϕ(n) revient à factoriser le nombre n. Or le problème de la
factorisation des très grands nombres est un problème difficile, voire impossible en un
temps raisonnable.
Dans le cas particulier où n = p.q avec p et q deux grands nombres premiers distincts,
nous pouvons déterminer ϕ(n) facilement.
En effet, nous savons que ϕ(p) = p-1 et ϕ(q) = q-1. De plus, comme p et q sont
premiers distincts alors p et q sont premiers entre eux alors on a :
ϕ(n) = ϕ(pq) = ϕ(p) ϕ(q) = (p-1)(q-1).
Mais si on ne connaît pas p et q alors il est difficile de factoriser n afin d’obtenir ϕ(n).
C’est sur cette difficulté mathématique que repose le système RSA.

c) Principe de chiffrement RSA

Choisissons deux nombres premiers p et q, n étant leur produit.
Calculons alors un nombre d tel que : pgcd (d , (p-1)(q-1) ) =1.
Cela nous permet de calculer facilement son inverse modulaire mod((p-1)(q-1))
Posons c, l’inverse de d mod((p-1)(q-1)). On a : cd =1 mod((p-1)(q-1))
Soit M, le nombre à chiffrer. Ce nombre doit être compris entre 0 et n-1.

▪ Pour chiffrer M, on utilise c et la formule suivante : M’ =Mc mod(n)

M’ est alors le nombre chiffré.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 55

Chap.3 Cryptographie

▪ Pour déchiffrer M’, on utilise d et le résultat du théorème 6 :

M’d = Mcd =M mod(n)
Car cd = 1 mod((p-1)(q-1)), c étant l’inverse modulaire de d.
M étant choisi dans l’intervalle [0,…,n-1], ainsi on obtient : Mcd = M

En résumé :
L’utilisateur B veut envoyer un message M à l’utilisateur A.
L’utilisateur A construit à partir de deux nombres premiers aléatoires p et q les nombres
n, d et c comme vu précédemment.

L’utilisateur A distribue alors sa clef publique (n,c) puisqu’on a vu qu’il est impossible de
trouver d, nécessaire au déchiffrement, par une méthode de calcul simple et rapide si on
ne possède pas les nombres p et q. Il conserve sa clef privée (d).
L’utilisateur B chiffre le message M en utilisant la clef publique (n,c) de l’utilisateur A. Il
transmet le message C ainsi obtenu.
Le destinateur, c’est à dire l’utilisateur A, peut alors déchiffrer ce message C en utilisant
sa clef privée (d).
L’algorithme est simple, la sécurité repose sur la taille du problème et la complexité de sa
solution. Tout le monde sait comment le résoudre, mais le temps nécessaire est plus
qu’irréaliste.
d) Exemple d’application
Considérons les deux nombres premiers :
P=11 et q=13. On calcule les clefs correspondantes :
Clef publique [143,53] Clef privée [77]
Supposons que le message à envoyer est une date de naissance : 071290
▪ Chiffrement :
Comme n est de longueur 3, il nous faut prendre des blocs de longueur 2 :
[ 07 , 12 , 90 ]
Pour le traitement, il s’agit du déchiffrement des nombres 7, 12 et 90.
On utilise pour cela, la clef publique [ 143, 53 ]
753 = 24 mod(143) ; 1253 =12 mod(143) ; 9053 =129 mod(143).
Ce qui nous donne : [ 24, 12 , 129 ]

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 56

Chap.3 Cryptographie

n étant de longueur 3, on rajoute des 0, si nécessaire, afin de n’avoir que des éléments de
3 chiffres [ 024 , 012 , 129 ]
On envoie alors le message 024012129
▪ Déchiffrement :
On reçoit le message précédent que l’on décompose en blocs de 3 chiffres (car n est de
longueur 3), ce qui donne [ 24 , 12 , 129 ]
On applique à chaque élément a du tableau la formule : a77 mod(143)
Afin de déchiffrer (en utilisant la clef privée [ 77 ].
On obtient ainsi le tableau suivant : [ 7, 12 , 90 ]
Il ne reste qu’à compléter chaque bloc par des 0, si nécessaire, afin d’avoir des éléments
de longueur n-1, c’est à dire 2. On obtient donc : [ 07 , 12 , 90 ].
Ce qui correspond bien à notre message original : 071290
IV.3 Cryptographie Hybride
Les algorithmes à clé publique (on parle aussi de chiffrement asymétrique) ont pourtant
un grave défaut : ils sont lents, beaucoup plus lents que leurs homologues symétriques.
Pour des applications où il faut échanger de nombreuses données, ils sont inutilisables
en pratique. On a alors recours à des cryptosystèmes hybrides. On échange des clés pour
un chiffrement symétrique grâce à la cryptographie à clé publique, ce qui permet de
sécuriser la communication de la clé. On utilise ensuite un algorithme de chiffrement
symétrique. Le célèbre PGP, décrit ci-dessous, fonctionne sur ce principe.
Le PGP (Pretty Good Privacy) est un algorithme de chiffrement à destination des
particuliers [PGP 98]. Il est surtout utilisé pour chiffrer des messages envoyés par
courrier électronique, même s'il peut aussi être utilisé pour chiffrer tous les fichiers. PGP
a été mis au point en 1991 par l'informaticien américain Philip Zimmermann, et ceci lui
valut divers problèmes avec la justice. D'une part, le PGP utilise l'algorithme RSA, qui
est breveté aux Etats-Unis. D'autre part, la NSA a tout fait pour tenter d'empêcher la
diffusion du PGP. La puissance de ce programme met en effet à la disposition de
chacun un moyen de cacher ses échanges électroniques qui résiste même aux assauts de
la plus puissante des agences de renseignements du monde. PGP s’appelle un système
hybride, il utilise le meilleur de la cryptographie symétrique (rapidité du chiffrement) et

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 57

Chap.3 Cryptographie

de la cryptographie asymétrique (sécurité de l'échange de clés). Il fonctionne suivant le

principe suivant :

1. Compression : le texte à envoyer est compressé. Cette étape permet de réduire le

temps de transmission des données, et améliore également la sécurité. En effet,
la compression détruit les modèles du texte (fréquences des lettres, mots
répétés). Et on sait que ces modèles sont souvent utilisés dans les analyses
cryptographiques.
2. Chiffrement du message : une clé de session aléatoire est générée, et le message
est chiffré par un algorithme symétrique à l'aide de cette clé. L'algorithme utilisé
a varié au cours du temps : il s'agissait au début d'IDEA, puis de CAST.
3. Chiffrement de la clé de session : la clé de session est chiffrée en utilisant la clé
publique du Destinataire (et l'algorithme RSA).
4. Envoi et réception du message : l'expéditeur envoie le couple message chiffré /
clé de session chiffrée au Destinataire. Celui-ci récupère d'abord la clé de session,
en utilisant sa clé privée, puis il déchiffre le message grâce à la clé de session.

IV.4 Cryptographie Quantique

IV.4.1 Introduction
Le chiffrement parfait existe: il s'agit du "One-Time Pad" de Vernam, dit aussi masque
jetable, utilisé notamment pour chiffrer le téléphone rouge entre Moscou et Washington
pendant la guerre froide. Le problème principal de ce protocole est le transport des clés:
celles- ci doivent être aussi grandes que le message, et la valise diplomatique n'est pas à la
portée du particulier. Les algorithmes à clé publique, développés auparavant, permettent
de résoudre ce problème mais rien ne stipule qu'ils sont inviolables. Le protocole utilisé
ici permet la création d'un canal d'échange de clé dont la sûreté repose sur des lois
physiques inviolables.

IV.4.2 Bases théoriques

a) Des clés espionnées
La physique classique (à notre échelle) permet la mesure de toutes les propriétés
physiques. L’information est codée à l'aide de propriétés physique mesurables d'un objet

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 58

Chap.3 Cryptographie

ou d'un signal (papier, bande magnétique, signal radio...), un espion pourrait mesurer ces
propriétés sans qu'il soit possible de s'en rendre compte.
Dans le monde quantique (à très petite échelle), cette possibilité disparaît. Les effets
quantiques se manifestent pour des objets microscopiques, comme les atomes ou les
photons ("particules" de lumière), où l'acte de mesurer n'est alors pas uniquement un
processus passif. Il est alors possible de concevoir un canal quantique - qui transporte
des signaux basés sur des phénomènes quantiques - où l'écoute même de ces signaux
perturbe irrémédiablement ces derniers, ce qui rend impossible de lire deux fois
l'information [GIR 01]. C'est une des conséquences du principe de Verner Heisenberg.

b) Photons et polarisation
La plus petite unité de la lumière, le photon, peut être assimilée à un minuscule champs
électrique oscillant. La direction de l'oscillation est la polarisation du photon. La lumière
naturelle est composé de photons dont les polarisations sont quelconques, cependant, en
faisant passer cette lumière dans un filtre polariseur, il est possible de ne garder que les
photons dont la polarisation est parallèle au filtre.
Nous sommes donc capables d'émettre des photons ayant une polarisation de 0°, 45°,
90°, et 135°. On peut détecter d'une façon certaine grâce à un cristal de calcite placé à 0°
la polarisation de photons polarisés à 0° ou 90°.
Si le photon possède une polarisation de 45° ou de 135° avec un cristal toujours à 0°, le
résultat sera aléatoire, il donnera 0° ou 90°. Maintenant, si le cristal est placé à 45°, il
permet de détecter de façon certaine les polarisations diagonales mais de manière
aléatoire les polarisations rectilignes (0° ou 90°). De plus, il est impossible de lire la
polarisation sans la modifier (principe d'incertitude de Heisenberg), on ne peut donc pas
effectuer plusieurs mesures sur un même photon, et donc connaître de façon certaine la
polarisation de n'importe quel photon. Voici les bases avec lesquelles nous allons
construire un protocole parfaitement sûr. Dans la suite, pour simplifier le
fonctionnement du cristal, on le considérera comme un filtre (et on le nommera ainsi)
laissant ou non passer le photon suivant sa polarité. d'un objet ou d'un signal sans que
ces propriétés ne soient perturbées.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 59

Chap.3 Cryptographie

IV.4.3 Description du protocole

Voici un exemple de protocole permettant de transmettre une clé composée de bits
d'Alice à Bob. Ils possèdent deux canaux: un quantique avec lequel ils peuvent échanger
des photons polarisés et un canal classique non sécurisé où ils peuvent discuter. Ils
conviennent que les photons polarisés à 0° ou 45° représentent 0, et ceux polarisés à 90°
ou 135° représentent 1. Alice émet, sur le canal quantique, une suite de photons
polarisés au hasard parmi 0°, 45°, 90° et 135°. A l'autre bout, Bob reçoit les photons et
mesure aléatoirement soit leur polarisation rectiligne (filtre placé à 0°), soit leur
polarisation diagonale (filtre placé à 45°). Si le photon traverse le filtre, Bob note 0, sinon
il note 1.
Bien sûr, certaines mesures de Bob (en moyenne, une sur deux) n'ont pas d'intérêt : il a
pu essayer de mesurer la polarisation rectiligne d'un photon polarisé à 45°, ce qui n'a pas
de sens et donne un résultat aléatoire (par exemple, le photon a été bloqué par le filtre,
Bob note donc 1 alors qu'Alice avait envoyé 0). Pour éliminer ces bits sans sens, il
indique à Alice, par le canal radio, quelle type de mesure (rectiligne ou diagonale) il a fait
pour chaque photon. Par le même canal radio, Alice lui indique quelles sont les mesures
correctes (photon polarisé à 0° ou 90° avec filtre rectiligne, photon à 45° ou 135° avec
filtre diagonal).
Il faut encore vérifier que ce protocole est sûr. Si caroline écoute le canal quantique, elle
peut faire la même chose que Bob, c'est à dire intercepter les photons en plaçant un filtre
polarisant tantôt rectiligne, tantôt diagonal. Pour que Bob ne se doute de rien, elle doit
remettre un photon polarisé. Elle va essayer d'envoyer le même photon qu'Alice, mais
comme elle a une chance sur deux d'avoir choisi le mauvais filtre, elle a une chance sur
deux de se tromper. Quand Bob reçoit le photon, s'il est mal polarisé par Caroline, il a
une chance sur deux d'avoir un résultat différent d'avec le photon original, et finalement,
pour chaque photon intercepté par Caroline, il y a une chance sur 4 que Bob reçoive une
information erronée.
Alice et Bob décident alors de "sacrifier" une partie de leur clé commune. Parmi tous les
bits qu'ils ont en commun, ils en choisissent quelques-uns au hasard, et les compare
publiquement par le canal radio : s'ils sont différents, ils ont une preuve qu'ils ont été

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 60

Chap.3 Cryptographie

écoutés, et ils oublient vite cette clé. En comparant suffisamment de bits, ils ont une
garantie presque absolue de ne pas avoir écouté.

IV.5 Cryptographie par courbe elliptique

Les spécialistes en cryptographie font de plus en plus appel à une technique qui
s'appuie sur des courbes elliptiques, proposée indépendamment par Victor Miller et
Neal Koblitz en 1985 [GIR 01]. La théorie des courbes elliptiques en général est un
domaine riche et a donné de nombreux résultats, dont la preuve du dernier théorème
de Fermat par Andrew Wiles.

Une courbe elliptique est un objet très simple mais qui a des propriétés tout à fait
surprenantes. Elles ont normalement la forme suivante:

y2+a1xy+a3y=x3+a2x2+a4x+a6

Pour leur usage en cryptographie, a1, a2 et a3 doivent être égaux à 0. Comme les
cryptographes ont l'habitude de renommer a4=a et a6=b, on obtient y2=x3+ax+b

Un exemple typique de courbe elliptique est donné sur la figure ci-dessous. Son
équation est y2=x3-5x2+3.

Figure 3.9 : la courbe elliptique d’équation y2=x3-5x2+3

IV.5.1 Addition de deux points
Prenons deux points A et B sur cette courbe. En général, la courbe passant par A et B
recoupe la courbe en un troisième point de coordonnées (x, y). Son symétrique (x, -y) est

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 61

Chap.3 Cryptographie

lui aussi sur la courbe et on le désigne par A+B pour signifier qu'il est construit à l'aide
de A et B. La chose surprenante est que cette opération "+" possède toutes les
propriétés de l'addition des nombres. C'est-à-dire que l'on peut faire tous les calculs de
type addition, soustraction et division avec un reste entier que nous faisons sur la droite
des nombres réels sur cet objet tordu que constitue une courbe elliptique. Il est possible,
comme l'ont démontré Miller et Koblitz, de coder avec cette opération bizarre au lieu de
travailler avec l'addition usuelle. Il en résulte une plus grande complexité des calculs qui
fait dire aux spécialistes que le chiffrement par la méthode des courbes elliptiques avec
une clef de 192 bits assure le même niveau de sécurité qu'une clef de 1024 bits pour la
méthode RSA. Il est donc probable que cette méthode sera de plus en plus utilisée pour
transmettre les clés.

Règles de l'addition

Soit la courbe elliptique cryptographique y2 = (x3 + ax + b) mod p. On reconnaît

l'équation déjà vue ci-dessus, sauf que l'on travaille modulo p. Le nombre p doit être un
nombre premier.
Lors des calculs, il arrive parfois que l'on doive faire une division par 0. Quand cela
arrive, le point résultat sera appelé "infini".
infini+infini = infini
(x1,y1) + infini = (x1,y1)
(x1,y1) + (x1,-y1) = infini
Si x1 x2, (x1,y1) + (x2,y2) = (x3,y3), avec
x3=(k2-x1-x2) mod p
y3 = (k(x1-x3)-y1) mod p
où k = (y2-y1) — (x2-x1)-1 mod p

Si y1 0, (x1,y1) + (x1,y1) = 2(x1,y1) = (x3,y3), avec

x3 = (k2-2x1) mod p
y3 = (k(x1-x3)-y1) mod p
où k = (3x12+a) — (2y1)-1 mod p

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 62

Chap.3 Cryptographie

On remarque que pour calculer k, on doit trouver l'inverse d'un nombre modulo p.
Pour trouver cet inverse, on utilise l'algorithme d'Euclide étendu.

IV.5.2 Multiplication d'un point par un nombre entier

On remplace la multiplication par une série d'additions. Prenons un exemple.

Soit la courbe y2 = (x3 + x + 2) mod 11.

Calculons d—P, avec d=3 et P=(4, 2). On peut vérifier que le point P appartient bien à

la courbe elliptique. On peut remplacer 3—P par P + P + P.

Calculons d'abord P+P. D'après la règle 5, P+P = (4, 2) + (4, 2) = (8, 4) = 2—P.

D'après la règle 4, 2—P + P = (8, 4) + (4, 2) = (2, 10) = 3—P.

IV.5.3 Echange de clés

Alice et Bob se mettent d'accord (publiquement) sur une courbe elliptique E(a,b,p),
c'est-à-dire qu'ils choisissent une courbe elliptique y2 = (x3+ax2+b) mod p. Ils se mettent
aussi d'accord, publiquement, sur un point P situé sur la courbe.
Secrètement, Alice choisit un entier dA, et Bob un entier dB. Alice envoie à Bob le point

dAP, et Bob envoie à Alice dBP. Chacun de son côté, ils sont capables de calculer

dA(dBP)=dB(dAP)=(dAdB)P, qui est un point de la courbe, et constitue leur clef secrète

commune.

IV.5.4 Sécurité
Si Eve a espionné leurs échanges, elle connaît E(a,b,p), P, dAP et dBP. Pour pouvoir
calculer dAdBP, il faut pouvoir calculer dA connaissant P et dAP. C'est ce que l'on appelle
résoudre le logarithme discret sur une courbe elliptique. Or, actuellement, si les nombres
sont suffisamment grands, on ne connaît pas de méthode efficace pour résoudre ce
problème en un temps raisonnable.
IV.5.5 Inconvénients
La théorie des fonctions elliptiques est complexe, et encore relativement récente. Il n'est
pas exclu que des trappes permettent de contourner le problème du logarithme discret.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 63

Chap.3 Cryptographie

La technologie de cryptographie par courbe elliptique a fait l'objet du dépôt de

nombreux brevets à travers le monde. Cela peut rendre son utilisation très coûteuse!

V La cryptanalyse
La cryptanalyse est l’étude des systèmes cryptographiques, notamment de leurs
faiblesses, dans le but de retrouver les messages clairs correspondants à des messages
chiffrés dont on n’est pas destinataire. En général, on part de l’hypothèse, connue sous
le nom de Kerckhoffs (fin du 19ième siècle), qui exprime que la méthode de chiffrement
utilisée doit « pouvoir tomber sans inconvénients aux mains de l’ennemi ». Autrement
dit, la sécurité d’un chiffrement doit reposer uniquement sur la protection de la clé.
Un cryptanalyste ou attaquant est donc une personne qui tente de déchiffrer des
messages, c’est-à-dire de retrouver des textes clairs à partir des textes chiffrés sans, à
priori, connaître la clé.
Selon les moyens dont dispose l’attaquant, on distingue plusieurs types d’attaques. Par
ordre de difficulté décroissante, nous en citons les modèles les plus courants :

Attaque sur texte chiffré seul (ciphertext-only) : le cryptanalyste possède des
exemplaires chiffrés des messages, il peut faire des hypothèses sur les messages
originaux qu'il ne possède pas. Le cryptanalyste est plus ardue de par le manque
d'informations à disposition.

Attaque à texte clair connu (known-plaintext attack) : le cryptanalyste possède des
messages ou des parties de messages en clair ainsi que les versions chiffrées
correspondantes. La cryptanalyse linéaire fait partie de cette catégorie.

Attaque à texte clair choisi (chosen-plaintext attack) : le cryptanalyste a la possibilité
d’obtenir la version chiffrée de messages clairs de son choix (en ayant accès à
une machine chiffrante ) . La cryptanalyse différentielle est un exemple d'attaque
à texte clair choisi.

Attaque à messages chiffrés choisis : Le cryptanalyste a temporairement
l’opportunité de déchiffrer les messages de son choix (en ayant par exemple
accès à une machine déchiffrante ). Il tente alors d’en profiter pour obtenir des
informations lui permettant de déchiffrer ensuite d’autres messages par ses
propres moyens.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 64

Chap.3 Cryptographie

Attaque en force brute ( ou recherche exhaustive de la clé) :Le cryptographe

essaie toutes les combinaisons de clés possibles jusqu'à l'obtention du texte clair.
Avec des ordinateurs de plus en plus performants et avec les méthodes de
calculs distribués (avec cette méthode et un grand nombre d'ordinateurs
travaillant ensemble, le DES a été cassé en 1999 en 22 heures seulement),
l'attaque en force brute restera toujours un moyen de casser des systèmes de
chiffrement (notamment symétriques, car pour les algorithmes asymétriques, le
problème n’est pas de trouver la bonne clé par attaque exhaustive, mais de
dériver la clé secrète à partir de la clé publique).
• Attaque à l’aide de l’analyse statistique (statistical analysis attak) : Le
cryptographe possède des informations sur les statistiques du message clair
(fréquences des lettres ou des séquences de lettres, voir les statistiques
d'utilisation des lettres dans le paragraphe. II.10.2)
V.1 Cryptanalyse linéaire
La cryptanalyse linéaire est une technique inventée par Mitsuru Matsui, chercheur chez
Mitsubishi. Elle date de 1993 et fut développée à l'origine pour casser l'algorithme de
chiffrement symétrique DES [BIH 93].

La cryptanalyse linéaire utilise une attaque à texte clair et consiste à modéliser

l'algorithme de chiffrement par une approximation linéaire, en le simplifiant. En
augmentant le nombre de couples disponibles (texte en clair, texte chiffré), on améliore
la précision de l'approximation et on peut deviner la clé [STI 95]. Tous les nouveaux
algorithmes de chiffrement doivent veiller à être résistants à ce type d'attaques. DES
n'était pas conçu pour empêcher ce genre de méthode, les tables de substitution (S-
Boxes) présentent en effet certaines propriétés linéaires alors qu'elles étaient justement
prévues pour ajouter une non-linéarité à DES.

L’attaque de DES nécessitait à l'origine 247 couples (tous chiffrés avec la même clé) que
l'attaquant a pu récupérer par un moyen ou un autre. Par la suite, Matsui améliore son
algorithme en 1994 et propose une solution avec 243 couples. La complexité avec une
bonne implémentation est toutefois inférieure et de l'ordre de 239 opérations DES.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 65

Chap.3 Cryptographie

Elle a par la suite été appliquée avec succès sur d’autres algorithmes. Les algorithmes
plus récents comme AES, IDEA et bien d'autres encore sont insensibles à une attaque
linéaire. La complexité de l'attaque est dans ces cas largement supérieure à celle d'une
recherche exhaustive.
V.2 Cryptanalyse différentielle
La cryptanalyse différentielle est une méthode générique de cryptanalyse qui peut être
appliquée aux algorithmes de chiffrement itératif par blocs, mais également aux
fonctions de hachage. Elle utilise une attaque à texte en clair choisi et se base sur
l’observation de l’évolution des différences entre deux textes lorsqu’ils sont chiffrés avec
la même clé. En analysant ces différences entre paires de textes, il est possible d’attribuer
des probabilités à chaque clé possible. A force d’analyser des paires de textes, on finit
soit par trouver la clé recherchée, soit par réduire suffisamment le nombre de clés
possibles pour pouvoir mener une attaque exhaustive rapide.
Origines de la cryptanalyse différentielle :
La découverte de la cryptanalyse différentielle est généralement attribuée à Eli Biham et
Adi Shamir à la fin des années 1980. Ces derniers publièrent un nombre d'attaques
contre divers algorithmes de chiffrement itératif par blocs et diverses fonctions de
hachage; ces articles comprenaient la présentation d'une faiblesse théorique dans
l'algorithme DES [BIH 93].

Il a été alors noté que DES était particulièrement résistant à cette attaque et en
particulier que de petites modifications dans ses paramètres l'affaiblissaient. Ce constat a
fait naître la rumeur que ses concepteurs (travaillant pour IBM) connaissaient déjà cette
méthode dans les années 1970. Effectivement, plusieurs personnes ayant participé à sa
conception ont depuis admis que la défense contre la cryptanalyse différentielle était
bien alors un des buts recherchés (Don Copperfield, 1994). Il semblerait que la NSA qui
contribua également à la conception de DES, avait même connaissance de cette
technique avant sa redécouverte par IBM. Et même La NSA exigea que le processus de
la conception soit tenu secret afin d'éviter la propagation de cette méthode. À l'intérieur
d'IBM, la cryptanalyse différentielle était connu sous le nom de T-attack, abréviation de
"Tickling attack", l'attaque par chatouillement car elle consistait à chatouiller les entrées
pour voir l'effet sur les sorties.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 66

Chap.3 Cryptographie

Alors que DES avait été conçu pour résister à la cryptanalyse différentielle, d'autres
algorithmes conçus à la même époque se sont révélés particulièrement vulnérables.
V.3 L'attaque boomerang
L'attaque boomerang est une version améliorée de la cryptanalyse différentielle, cette
méthode a été inventée par David Wagner en 1999. Elle consiste à attaquer les deux
moitiés d'un algorithme de chiffrement par bloc et part du principe que certaines
propriétés, après perturbations des entrées, ne se propagent pas à travers toute la
structure.

V.3.1 Description
On considère quatre messages en clair : P, P', Q et Q'. On dispose également des
versions chiffrées de ces messages : C, C', D et D'. On considère également un
algorithme de chiffrement symétrique E dont le chiffrement peut être décomposé en
deux parties.
La première moitié du chiffrement est représentée par E0 et E1 est la deuxième partie.
On définit deux caractéristiques différentielles ∆ → ∆* pour E0 et ν → ν* pour E1-1.
Cette notation signifie qu'une modification ∆ sur les entrées va entraîner une
modification ∆* sur les sorties après passage dans l'algorithme. Le but est d'obtenir des
caractéristiques qui vont satisfaire les données que nous avons.
On veut en premier que la paire (P,P') soit compatible avec la caractéristique de E0.
Ensuite, les paires (P,Q) ainsi que (P',Q') doivent satisfaire la caractéristique de E1-1.
Nous supposons ensuite que la paire (Q,Q') est configurée de telle manière à ce que la
caractéristique différentielle ∆* → ∆ soit respectée.
Si les paramètres sont corrects, la différence entre Q et Q' doit être égale à la différence
entre P et P' d'où le surnom de Boomerang.
V.3.2 Les différentes étapes
Nous avons donc un bloc P et un bloc P' avec une différence ∆ entre les deux. La
différence se traduit sous la forme d'un ou-exclusif du bloc P avec un vecteur, on obtient
alors P'. On calcule E0(P) et E0(P'). Ces deux résultats diffèrent de ∆*. On applique
ensuite E1 sur ces deux valeurs pour obtenir C et C' :
C = E1(E0(P)) et C' = E1(E0(P')).

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 67

Chap.3 Cryptographie

On génère ensuite D et D' à partir de C et C' grâce à un ou-exclusif avec ν :

D=C ν et D' = C’ ν
On déchiffre D et D' avec l'inverse de E1. On se trouve alors dans une couche
intermédiaire avec deux résultats qui varient de ∆* si les caractéristiques des différences
sont correctes. En déchiffrant avec E0, on trouve Q et Q'. Ceux-ci doivent présenter une
différence de ∆, la même qu'entre P et P'. La différence initialement imposée sur P et P'
est revenue entre Q et Q' comme un boomerang !
Grâce à cette approche, il est possible d'approcher successivement la clé en regardant si
les conditions décrites ci-dessus sont respectées avec un grand nombre de paires
claires/chiffrées.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 68

 Chapitre 4

CHIFFREMENT EVOLUTIONNISTE

I Introduction
II Motivation
II.1 Position du problème
II.2 Description de l’algorithme
II.3 Discussion
III Description du système de chiffrement SEC
III.1 Formalisation du problème
III.2 Notre système de chiffrement
IV Déchiffrement
V Expérimentation
V.1 Les messages modèles
V.2 Résultats retenus
V.3 Interprétation
VI Extension de SEC à des blocs binaires
VI.1 Motivation
VII.2 Description de la méthode
VII Discussion
VIII Conclusion

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat

Chap.4 Chiffrement évolutionniste

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 70

Chap.4 Chiffrement évolutionniste

I Introduction
L’optimisation combinatoire est un domaine vivant des Mathématiques Appliquées
s’appuyant principalement sur l’algorithmique et la Théorie de la Complexité qui s’est
développée en parallèle avec l’informatique. Il existe un tas de problèmes d’optimisation
combinatoire qui sont NP-complets tels que le Voyageur du Commerce (TSP), ou
problème d’ordonnancement. D’autres qui sont polynomiaux tels que les problèmes du
Flot maximal dans un graphe pondéré [LAC 03].
Nos contributions dans ce domaine, s’inscrivent dans le contexte de la cryptographie et
notamment le chiffrement.
Dans la première section de ce chapitre, nous présentons notre première approche pour
la conception et réalisation d’un système de chiffrement. Cette approche n’en est qu’à
ses balbutiements. Cependant, elle est à l’origine de la motivation pour la mise en œuvre
de notre premier système de chiffrement SEC. L’objectif principal de cette approche est
l’obtention d’un système de chiffrement symétrique dont la clé secrète est inattaquable
actuellement (≥240) bits). Cela se réalise par l’optimisation (maximisation) d’une
fonction d’évaluation concrétisant notre problème de chiffrement. La valeur de cette
fonction varie en fonction des transformations subies par les blocs d’un texte traduit en
binaire. Ces transformations se réalisent grâce aux opérateurs génétiques de l’AE que
nous avons adopté.
Dans la deuxième section, nous décrivons notre premier système de chiffrement SEC,
qui présente la résolution d’un problème d’optimisation cette fois-ci combinatoire
auquel a été ramené notre problème de chiffrement. En fait, nous avons représenté le
texte à chiffrer par un ensemble de listes disjointes. Chaque liste est composée par les
différentes positions dans le texte du caractère correspondant. L’objectif principal est
d’optimiser les fréquences d’apparition et modifier les positions des caractères dans le
message. Cela revient à déterminer une permutation des listes qui une fois affectées aux
différents caractères du texte assurent le résultat souhaité. Or, le nombre des
permutations d’un ensemble à n éléments est n! . Par conséquent, nous nous trouvons
devant un problème d’optimisation combinatoire (OC) exponentiel pour lequel la
résolution par AE est sollicitée.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 71

Chap.4 Chiffrement évolutionniste

II Motivation
II.1 Position du problème
Dans le but de concevoir un nouveau système de chiffrement basé sur un problème
d’optimisation combinatoire, nous avons essayé de trouver une formalisation du
problème de chiffrement menant à un tel système. Les grandes lignes tracées, dans cet
objectif sont les suivantes :
- Définir des nouvelles transformations dans le contexte du chiffrement.
- Ces transformations se basent sur des processus aléatoires.
- Le nombre de ces transformations est contrôlé par un critère basé sur la
convergence d’une fonction objective réelle. Cette convergence est équivalente à
une optimisation.
D’où l’émergence d’un problème d’optimisation pour lequel nous faisons appel aux AE
qui ont donné satisfaction dans la résolution de ce genre de problème.
Dans cette partie, nous présentons notre première approche de chiffrement, qui est
toujours à l’état embryonnaire. Cette approche consiste à décomposer le message clair
en un nombre fini de blocs de même taille qui constituent les individus (selon les AE),
auxquels nous appliquons les opérateurs génétiques servant d’outils pour les
transformations mentionnées ci-dessus. D’où la nécessité de franchir les premiers
obstacles, à savoir : la définition du codage et la construction de la fonction d’évaluation
adaptée. Nous allons décrire d’une manière détaillée les étapes essentielles de cette
approche.
II.2 Description de l’algorithme
Corps de l’AE

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 72

Chap.4 Chiffrement évolutionniste

Etape 0 : définir un codage du problème

Etape 1 : créer une population initiale P0 de q individus{X1, X2, …,Xq}
i:=0 ;
Répéter
Etape 2 : évaluation des individus.
Soit F la fonction d'évaluation.
Calculer F(Xi) pour chaque individu Xi de Pi
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 Pi+1
Jusqu’à : l’obtention du niveau de performance souhaité.
Répéter les étapes 2, 3 et 4 jusqu’à l’obtention du niveau de performance souhaité.

Figure 4.1 Algorithme évolutionniste

Notre algorithme s'inspire profondément des algorithmes génétiques, d'ailleurs il

possède le même squelette et évolue à l'aide des mêmes opérations. Cependant, deux
concepts diffèrent de ceux d'un algorithme génétique.

Premier concept : Choix de la population initiale

Dans un algorithme génétique, les individus de la population initiale sont des solutions
potentielles du problème. Par contre dans notre algorithme, la population initiale ne
contient qu'une seule solution, composée d’un nombre fini de blocs de même taille
constituant les individus de cette population ( nous précisons aussi que la concaténation
de tous ces individus donne la solution en question).

Deuxième concept : Sélection des meilleurs individus

Nous avons choisi une méthode adaptée à notre problème et nous l'avons nommée
pseudo-élitisme. Elle consiste à sélectionner les meilleurs individus en fonction de leur
valeur d'évaluation, sauf que les plus faibles ne vont pas être éliminés (en fait le nombre
d'individus dans la population restera le même durant tout l'algorithme).

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 73

Chap.4 Chiffrement évolutionniste

L’algorithme détaillé
Etape 0 : Nous traduisons le message à chiffrer M en binaire. Désignons par n sa taille.
Etape 1 : Création de la population initiale P0
Nous décomposons M en q blocs: M1, M2,…, Mq de même taille N tel que : n=q.N
(le choix de q respectera les normes des algorithmes génétiques).
Posons P0={ M1, M2, …, Mq }
Etape 2 : Evaluation des individus.
Pour faire la sélection, il faut d'abord définir la fonction d'évaluation.
Pour cela nous définissons une fonction caractéristique f sur l'ensemble {1, …, N}
des indices i d'un bloc B , considéré comme un vecteur de taille N, par:
Si la valeur initiale du ième bit a changé après l'application d'une opération Alors f(i)=1
Sinon f(i)= 0
Définition de la fonction d'évaluation F sur l'ensemble des individus par:
N
F(Bk)= ∑ f ( i ) ( 1 ≤ k ≤ q)
i =1

D'une manière intuitive, ce sont les individus ayant subi le plus de modifications
qui vont être sélectionnés. Car n'oublions pas que le but du chiffrement est
d'avoir le maximum d'individus modifiés.
Etape3: Sélection des meilleurs individus par le pseudo-elitisme défini plus haut:
Nous trions les individus en fonction de leur valeur d'évaluation. Et nous sélectionnons
les meilleurs selon les taux des opérateurs, fixés au départ.
Etape 4 : Application des opérateurs génétiques.
1-Croisement: Nous utilisons le croisement simple à un point. Cet opérateur est appliqué
aux individus sélectionnés dans l'étape 3. Le point de croisement est tiré au hasard.
Le taux de croisement pour lequel nous optons varie entre 75% et 90% [GRE 86] .
2-Mutation: Nous choisissons la mutation qui consiste à échanger deux gènes dans un
chromosome, autrement dit, elle est analogue à une transposition. Ces deux gènes sont
choisis au hasard. Cet opérateur sera appliqué aux individus issus du croisement. Le
meilleur taux est de l'ordre de 0,1% à 5% [GRE 86]. Plaçons la nouvelle progéniture
dans une nouvelle population en ajoutant ceux qui n'ont pas été sélectionnés pour
compléter la population dont la taille est fixe.
Répéter les étapes 2, 3, 4 jusqu'au critère d'arrêt défini ci-dessous.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 74

Chap.4 Chiffrement évolutionniste

Définir la condition d'arrêt

Nous savons que la fonction F est bornée (0 ≤ F(X) ≤ N). Donc F admet un minimum.
Théoriquement, l’algorithme s’arrête lorsque la fonction F converge vers 0 et c’est le
meilleur des cas; d'une manière intuitive, lorsque tous les blocs du message ont été
complètement modifiés. En général, la valeur de convergence est déterminée
expérimentalement et elle est proche de 0.
Détermination de la clé
Il s’agit de garder les traces des individus qui ont subi des opérations génétiques ainsi que
les points de croisement et de mutation correspondants.
Pour cela, nous procédons de la manière suivante :
- Chaque individu sera représenté par son rang dans la population.
- Les opérateurs seront codés par des entiers.
- Et nous établissons une liste de triplets dont les coordonnées indiquent
respectivement le rang de (ou des) l'individu ayant subi l'opération génétique, le
code de l'opérateur génétique appliqué, les points de croisements ou de mutation
correspondants. La liste sera incrémentée à chaque itération de l’algorithme.
II.3 Discussion
Dans l’algorithme décrit ci-dessus, la sélection des meilleurs individus ne s’accompagne
pas de l’élimination des faibles individus, ceci pour garder la trace de tous les blocs. Par
conséquent, certains blocs risquent de ne pas être modifiés donc non chiffrés.
D’autre part, la clé générée par cet algorithme est de taille très grande. En effet, elle est
fonction du nombre d’itérations et du nombre d’opérations effectuées sur les blocs au
cours de ces itérations. Donc, elle est fonction de la taille du texte. Des travaux sont en
cours pour améliorer cette approche.
En parallèle, nous avons déterminé une nouvelle formalisation du problème de
chiffrement, qui nous a permis d’aboutir à un autre système que nous estimons plus
important et qui sera décrit dans la deuxième partie de ce chapitre

III Description du système de chiffrement SEC

Soit M le message à chiffrer. M est une suite de n caractères. Ce message peut être
formé uniquement par des nombres, par exemple des codes bancaires d’un certain

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 75

Chap.4 Chiffrement évolutionniste

nombre de personnes, comme il peut être un mélange de nombres et de phrases

littéraires y compris la ponctuation.
III.1 Formalisation du problème
Soient c1, c2, …, cm les différents caractères de M. Désignons par Li (1 ≤ i ≤ m) la liste
des différentes positions du caractère ci dans M avant le chiffrement et par card(Li) le
nombre des occurrences de ci dans M .
Remarque : Li ∩ Lj = ∅ si i ≠ j, ∀ i,j ∈ {1, 2, …, m}.
L1, L2,…, Lm est une partition de l’ensemble {1, 2, …, n}.
Le message M peut être représenté par le vecteur ci-dessous :
(c1,L1) (c2,L2) … (cm,Lm)

Le but de notre travail est de modifier au maximum 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. Autrement dit, nous devons trouver une permutation σ de {1, 2, …, m} pour
laquelle la différence entre le cardinal de la nouvelle liste Lσ(i) affectée au caractère ci et
le cardinal de la liste initiale Li soit maximale. Là nous nous rendons compte que nous
sommes devant un problème d’optimisation combinatoire. Or les algorithmes
évolutionnistes sont très efficaces dans ce genre de problème, donc nous allons les
utiliser et notamment ceux appliqués aux problèmes de permutations [CAU 95]. Ces
algorithmes ont plusieurs versions, parmi lesquelles nous celle choisissons celle
présentée dans la figure 4.1 et qui est fréquemment utilisée.
III.2 Notre système de chiffrement
Etape 0 : Codage
Un individu (ou chromosome) est un vecteur de taille m.
Les gènes sont les listes Lp (1 ≤ i ≤ m).
i

Le ième gène Lp contient les nouvelles positions que prendra le caractère ci.
i

Etape 1 : Création de la population initiale P0 composée de q individus : X1, X2, …, Xq.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 76

Chap.4 Chiffrement évolutionniste

Nous désignons par Original-Ch le chromosome dont les gènes sont les listes
L1,L2,…,Lm (placés dans cet ordre) qui représentent le message avant l’application de
l’algorithme.
Nous appliquons à Original-Ch, des transformations simples et capables de modifier les
fréquences d’apparition des caractères. Par exemple, nous tirons au hasard q
permutations de {1,2,…,m} et l’appliquons afin d’obtenir une population initiale
constituée de q solutions potentielles .
i :=0.
Etape 2 : Evaluation des individus
Soit Xj un individu de Pi dont les gènes sont : Lj1,Lj2,…,Ljm.
Nous définissons la fonction d’évaluation F sur l’ensemble des individus Xj par :
m
F(Xj) = ∑
i =1
card(L ji )−card(Li)

Etape 3 : Sélection des meilleurs individus

Nous utilisons la méthode classique de la roulette [FLO 02] permettant de retenir les
individus les plus forts. Le processus est décrit dans II.2.1 du chapitre 2.
Nous introduisons une fonction de contrôle qui va éliminer les individus pour lesquels
seulement une minorité de gènes ont changé de valeurs 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
Croisement MPX (Maximal Préservative X)
Ce croisement (Voir II.2.3 du chapitre 2) est appliqué aux individus sélectionnés avec un
taux bien précis. D’après [ LAB 01] 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% [LAB 01].
Placer la nouvelle progéniture dans une nouvelle population Pi+1.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 77

Chap.4 Chiffrement évolutionniste

Répéter les étapes 2, 3 et 4 jusqu’à un critère d’arrêt.

Définir la condition d’arrêt :
La fonction F est bornée car 0 ≤ F(X) ≤ 2*m pour tout individu X

m m
∑i =1
card ( Lk i )− card ( Li ) ≤ ∑ (card ( L )+ card ( L )) ≤ 2*l
i =1
ki i

En fait : théoriquement et mathématiquement parlant, la fonction F admet un maximum

puisqu’elle est bornée. D’après certains résultats de recherche [KHA 88] la convergence
d’une fonction d’évaluation est assurée, mais peut être vers une valeur proche de Max,
déterminée expérimentalement. En fait, cela se confirme dans les expériences et les
travaux pratiques que nous avons entamés et que nous interpréterons par la suite.
Dernière phase de notre 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.

IV Déchiffrement
Le déchiffrement du message chiffré M’ se fait en deux étapes :
Dans la première étape, nous allons représenter le texte chiffré, par un vecteur de listes
comme nous l’avons fait pour le message en clair. Désignons alors par c’1, c’2, …, c’m les
différents caractères de M’ et par L’1, L’2 , …, L’m leurs listes respectives de positions dans
M’. Grâce à la clé génétique, les caractères vont retrouver leurs listes de positions
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 : Clef(1) = p1 , Clef(2) = p2 , …, Clef(i) = 1 , …, Clef(m) = pm où
Le caractère c’p va être associé à la liste L1’
1

Le caractère c’p va être associé à la liste L2’ ….Le caractère c’p va être associé à la liste
2 m

L’m.
Ainsi, nous obtenons le message M.
Dans la deuxième étape, nous procédons au déchiffrement de M pour obtenir M0. Or,
le passage de M0 à M se fait par le biais d’opérations ou fonctions simples de la

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 78

Chap.4 Chiffrement évolutionniste

cryptographie par exemple substitution simple, décalage, chiffrement affine… et dont la

clé est secrète et symétrique.

V Expérimentation
Nous avons appliqué notre algorithme sur des messages de différentes tailles ; mais nous
n’avons retenu que quatre modèles comme des exemples. Et pour chacun d’eux, nous
avons fait l’application pour des différentes tailles de populations nous 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.
V.1 Les messages modèles
Nous citerons ci-dessous les quatre messages modèles, et donnerons les opérations
utilisées pour brouiller le message et la clé de session générée par notre algorithme
évolutionniste Le brouillage utilisé pour les quatre messages ci-dessous est un
chiffrement affine défini par : F(x) = ax+b où a= -1 , b = 255. Et x est le code ASCII du
caractère du message initial.
Message 1 : Taille=1026

Travelling salesman problem (TSP) is an NP-complete problem, implying that there is no known algorithm to solve it exactly
in better than O(an) time (for n cities). In fact, there are (n-1)!/2 possible combinations, so to try every one requires factorial
time with the problem size. Just to remind, there are cities and given distances between them. Travelling salesman has to
visit all of them, but he does not want to travel very much. The task is to find a sequence of cities to minimize travelled
distance. In other words, find a minimal Hamiltonian tour in a complete graph of n nodes. A method was implemented for
a 6-city problem. The optimal tour found for the 6 cities was: 1- 2 - 5 - 4 - 6 - 3 - 1 which has distance 9.242640 [Link]
processor times for the 5 and 6 city runs were below the timer resolution. The time for each combination can be estimated as
2e-07 seconds. The number of combinations for the 29 cities problem is 8.84e30. This gives a time estimate of 1.77e24
seconds, or 5.60e16 years.

Figure 4.2 : Le 1er message en clair

ŤĚŜ╔ÎČČ═ÄźŹ×ŜČÎ×ëŜÄŹÜĚôľČÎëŹĹŤś▀═׏ŜÄŹĺ▀ĆÉôëÜČÎŁÎŹÜĚôľČÎëůŹ═ëÜČ╦═ÄźŹŁ┼ŜŁŹŁ┼ÎĚÎŹ═׏
ÄôŹ╚Äô╠ÄŹŜČźôĚ═Ł┼돣ôŹ×ôČ╔ÎŹ═ŁŹÎĂŜÉŁČ╦Ź═ÄŹľÎŁŁÎĚŹŁ┼ŜÄŹ╩ĹŜÄŁ═ëΏŤôĚŹÄŹÉ═Ł═Î×î㏻
ÄŹ¤ŜÉŁůŹŁ┼ÎĚÎŹŜĚÎŹĹÄĆÍî▒ĎťŹÜô××═ľČÎŹÉôëľ═ÄŜŁ═ôÄ×ůŹ×ôŹŁôŹŁĚ╦ŹÎ╔ÎĚ╦ŹôÄÎŹĚÎıË═ĚÎ׏¤ŜÉŁôĚ
═ŜČŹŁ═ëÎŹ╠═Ł┼ŹŹŁ┼ÎŹÜĚôľČÎëŹ×═ćÎ㏌ËףŹŁôŹĚÎë═ÄöůŹŁ┼ÎĚÎŹŜĚÎŹŹÉ═Ł═Î׏ŜÄöŹź═╔ÎÄŹö═ףŜÄÉÎ
׏ľÎŁ╠ÎÎÄŹŁ┼Îë㏍ĚŜ╔ÎČČ═ÄźŹ×ŜČÎ×ÎŹŁŜ×╚Ź═׏ŁôŹ¤═ÄöŹŜŹ×ÎıËÎÄÉÎŹô¤ŹÉ═Ł═Î׏ŁôŹë═Ä═ë═ćÎŹŁĚŜ
╔ÎČČÎöŹö═ףŜÄÉÎ㏻ďôŁ┼ÎĚŹ╠ôĚö×ůŹ¤═ÄöŹŜŹë═Ä═ëŜČŹłŜë═ČŁôÄ═ŜÄŹŹŁôËĚŹ═ÄŹŜŹÉôëÜČÎŁÎŹźĚŜÜ
┼Źô¤ŹÄŹÄôöÎ×㏏çŹëÎŁ┼ôöŹ╠Ŝ׏═ëÜČÎëÎÄŁÎöŹ¤ôĚŹŜŹ░ĆÉ═Ł╦ŹÜĚôľČÎë㏍┼ÎŹôÜŁ═ëŜČŹŁôËĚŹ¤ôËÄöŹ
¤ôĚŹŁ┼ÎŹ░ŹÉ═Ł═Î׏╠Ŝ×ÖŹÍĆŹťŹĆŹðŹĆŹÂŹĆŹ░ŹĆŹ╬ŹĆŹÍŹ╠┼═É┼Ź┼Ŝ׏ö═ףŜÄÉÎŹŮăťÂť░ÂñŹËÄ═Ł
×ăŤ┼ÎŹÜĚôÉÎ××ôĚŹŁ═ëÎ׏¤ôĚŹŁ┼ÎŹðŹŜÄöŹ░ŹÉ═Ł╦ŹĚËÄ׏╠ÎĚÎŹľÎČô╠ŹŁ┼ÎŹŁ═ëÎĚŹĚÎ×ôČËŁ═ôÄ㏏Ť┼
ÎŹŁ═ëÎŹ¤ôĚŹÎŜÉ┼ŹÉôëľ═ÄŜŁ═ôÄŹÉŜÄŹľÎŹÎף═ëŜŁÎöŹŜ׏ťÎĆñİŹ×ÎÉôÄö×㏏Ť┼ÎŹÄËëľÎĚŹô¤ŹÉôëľ═ÄŜŁ═ô
Ä׏¤ôĚŹŁ┼ÎŹťŮŹÉ═Ł═Î׏ÜĚôľČÎëŹ═׏ÁăÁÂÎ╬ñ㏍┼═׏ź═╔Î׏ŜŹŁ═ëÎŹÎף═ëŜŁÎŹô¤ŹÍăİİ͏×ÎÉôÄö
×ůŹôĚŹðă░ñÎÍ░Ź╦ÎŜĚ×ăŹ

Figure 4.3 : Le 1er message chiffré

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 79

Chap.4 Chiffrement évolutionniste

La clé: 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 4 5 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49 50 6 7 51 23 52 0 1 2 3 25 29 24 27 28 30 26 31

Message2 Taille: 684

Astronauts In August 1983 Guion Bluford became the first African American to go into space,
while serving on a mission aboard the Challenger space shuttle. Bluford said that the blastoff
of the shuttle was like riding in a high-speed elevator through a bonfire. He also recognized
that, "From a black perspective, my flight on the shuttle represented another step forward.
"Astronaut Mae Jemison became the first African American woman to travel in space when
she flew on the space shuttle Endeavor in a September 1992 mission. After her space flight,
Jemison resigned from NASA and established the Jemison Group, a company that researches,
develops, and markets advanced technologies.

Figure 4.4 : le 2ème message en clair

║öłČć╣ĂăłöŜ╣î║ăıăöłîŹÉĹ×îİăÂć╣î▀śă╬ćČ▓îð╠ĎĂĚ╠îłů╠î╬ÂČöłî║╬ČÂĎĂ╣î║Ě
╠ČÂĎĂ╣îłćîıćîÂ╣łćîöÁĂĎ╠▒î═ůÂś╠îö╠ČŞÂ╣ıîć╣îĂîĚÂööÂć╣îĂðćĂČ▓îłů╠îľůĂśś
╠╣ı╠ČîöÁĂĎ╠îöůăłłś╠śî▀śă╬ćČ▓îöĂÂ▓îłůĂłîłů╠îðśĂöłć╬╬îć╬îłů╠îöůăłłś╠î═Ă
öîśÂô╠îČÂ▓Â╣ıîÂ╣îĂîůÂıůÖöÁ╠╠▓î╠ś╠ŞĂłćČîłůČćăıůîĂîðć╣╬ÂČ╠śîŤ╠îĂśöćîČ╠
Ďćı╣ÂŁ╠▓îłůĂł▒îÜťČćĚîĂîðśĂĎôîÁ╠ČöÁ╠ϳª╠▒îĚĺî╬śÂıůłîć╣îłů╠îöůăłłś╠îČ
╠ÁČ╠ö╠╣ł╠▓îĂ╣ćłů╠Čîöł╠Áî╬ćČ═ĂČ▓śÜ║öłČć╣ĂăłîŚĂ╠îĆ╠ĚÂöć╣îð╠ĎĂĚ╠îł
ů╠î╬ÂČöłî║╬ČÂĎĂ╣î║Ě╠ČÂĎĂ╣î═ćĚĂ╣îłćîłČĂŞ╠śîÂ╣îöÁĂĎ╠î═ů╠╣îöů╠î╬ś╠═îć
╣îłů╠îöÁĂĎ╠îöůăłłś╠îË╣▓╠ĂŞćČîÂ╣îĂîł╠Áł╠Ěð╠ČîŹÉÉëîĚÂööÂć╣śî║╬ł╠Čîů╠Čî
öÁĂĎ╠î╬śÂıůł▒îĆ╠ĚÂöć╣îČ╠öÂı╣╠▓î╬ČćĚî╝║ł║îĂ╣▓î╠öłĂðśÂöů╠▓îłů╠îĆ╠ĚÂ
öć╣îİČćăÁ▒îĂîĎćĚÁĂ╣ĺîłůĂłîČ╠ö╠ĂČĎů╠ö▒î▓╠Ş╠śćÁö▒îĂ╣▓îĚĂČô╠łöîĂ▓ŞĂ╣
Ď╠▓îł╠Ďů╣ćśćıÂ╠öśî

Figure 4.5 : Le 2ème message chiffré.

La clé: 8 9 10 11 12 13 14 15 16 17 18 19 6 7 22 29 30 31 32 33 34 35 36 37 38
39 40 41 42 43 44 21 1 23 24 25 2 5 4 20 26 0 3 28 27
Message1 -(1026) Message2 -(684)

1800 1200

1600
1000
1400

1200
800
1000 Itérations

800 600
Evaluation
moyenne
600
400
400

200 200

0
16 24 30 32 0
T aille de population 16 24 30 32

Figure 4.6 : Résultats expérimentaux des messages 1et 2

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 80

Chap.4 Chiffrement évolutionniste

Message 3 Taille: 1149

Abraham Lincoln, the 16th president of the United States, guided his country through the most
devastating experience in its national history--the CIVIL WAR. He is considered by many
historians to have been the greatest American president. Abraham Lincoln was born Sunday,
February 12, 1809, in a log cabin near Hodgenville, Kentucky. He was the son of Thomas and
Nancy Hanks Lincoln, Thomas Lincoln was a. Abraham had gone to school briefly in
Kentucky and did so again in Indiana. He attended school with his older sister... Both of
Abraham's parents were members of a Baptist congregation which had separated from another
church due to opposition to slavery. When Abraham was 7, the family moved to southern
Indiana As Abraham grew up, he loved to read and preferred learning to working in the fields.
This led to a difficult relationship with his father who was just the opposite. Abraham was
constantly borrowing books from the neighbors. Lincoln's declining interest in politics was
renewed by the passage of the Kansas-Nebraska Act in 1854. In 1860 he furthered his national
reputation with a successful speech at the Cooper Institute in New York.

Figure 4.7 : Le 3ème message en clair.

ě╚Ľ╩Ü╩╬╔ł╣═ă¤Ă═┤╔öÜŜ╔ŁŹöÜ╔׼ŜŚ╣ĺŜ═ö╔¤▀╔öÜŜ╔│═╣öŜĺ╔ľö╩öŜŚ┤╔Ĺť╣ĺŜĺ╔Ü╣Ś╔㤝
═öĽÉ╔öÜĽ¤ťĹÜöÜŜ╔╬¤Śö╔ĺŜô╩Śö╩ö╣═Ĺ╔Ŝź×ŜĽ╣Ŝ═ăŜ╔╣═╔╣öŚ╔═╩ö╣¤═╩Ă╔Ü╣Śö¤ĽÉ▒▒ö
ÜŜ╔śĆîĆł╔ŤěÖ¬╔ČŜ╔╣Ś╔ă¤═Ś╣ĺŜĽŜĺ╔╚É╔╬╩═É╔Ü╣Śö¤Ľ╣╩═Ś╔ö¤╔Ü╩ôŜ╔╚ŜŜ═╔öÜŜ╔ĹĽŜ╩
öŜŚö╔ě╬ŜĽ╣ă╩═╔׼ŜŚ╣ĺŜ═ö¬ě╚Ľ╩Ü╩╬╔ł╣═ă¤Ă═╔ś╩Ś╔╚¤Ľ═╔ľť═ĺ╩É┤╔İŜ╚Ľť╩ĽÉ╔Łć┤╔Ł
ëçĎ┤╔╣═╔╩╔äĹ╔ă╩╚╣═╔═Ŝ╩Ľ╔ȤĺĹŜ═ô╣ĂĂŜ┤╔╝Ŝ═öťăÂɬ╔ČŜ╔ś╩Ś╔öÜŜ╔Ś¤═╔¤▀╔ęܤ
╬╩Ś╔╩═ĺ╔Ę╩═ăÉ╔Č╩═ÂŚ╔ł╣═ă¤Ă═┤╔ęܤ╬╩Ś╔ł╣═ă¤Ă═╔ś╩Ś╔╩¬╔ě╚Ľ╩Ü╩╬╔Ü╩ĺ╔Ť═Ŝ╔
ö¤╔Śăܤ¤Ă╔╚Ľ╣Ŝ▀ĂÉ╔╣═╔╝Ŝ═öťăÂÉ╔╩═ĺ╔ĺ╣ĺ╔Ś¤╔╩Ĺ╩╣═╔╣═╔Ć═ĺ╣╩═╩¬╔ČŜ╔╩ööŜ═ĺŜĺ
╔Śăܤ¤Ă╔ś╣öÜ╔Ü╣Ś╔¤ĂĺŜĽ╔Ś╣ŚöŜĽ¬¬¬╔ş¤öÜ╔¤▀╔ě╚Ľ╩Ü╩╬ðŚ╔×╩ĽŜ═öŚ╔śŜĽŜ╔╬Ŝ╬╚ŜĽŚ
╔¤▀╔╩╔ş╩×ö╣Śö╔ă¤═ĹĽŜĹ╩ö╣¤═╔śÜ╣ăÜ╔Ü╩ĺ╔ŚŜ×╩Ľ╩öŜĺ╔▀Ľ¤╬╔╩═¤öÜŜĽ╔ăÜťĽăÜ╔ĺťŜ╔ö
¤╔¤×פŚ╣ö╣¤═╔ö¤╔ŚĂ╩ôŜĽÉ¬╔ŤÜŜ═╔ě╚Ľ╩Ü╩╬╔ś╩Ś╔Ě┤╔öÜŜ╔▀╩╬╣ĂÉ╔╬¤ôŜĺ╔ö¤╔Ś¤ťöÜ
ŜĽ═╔Ć═ĺ╣╩═╩ěŚ╔ě╚Ľ╩Ü╩╬╔ĹĽŜś╔ť×┤╔ÜŜ╔äôŜĺ╔ö¤╔ĽŜ╩ĺ╔╩═ĺ╔׼Ŝ▀ŜĽĽŜĺ╔ĂŜ╩Ľ═╣═Ĺ╔
ö¤╔ś¤ĽÂ╣═Ĺ╔╣═╔öÜŜ╔▀╣ŜĂ匬╔ęÜ╣Ś╔ĂŜĺ╔ö¤╔╩╔ĺ╣▀▀╣ăťĂö╔ĽŜĂ╩ö╣¤═ŚÜ╣×╔ś╣öÜ╔Ü
╣Ś╔▀╩öÜŜĽ╔śÜ¤╔ś╩Ś╔ËťŚö╔öÜŜ╔¤×פŚ╣öŜ¬╔ě╚Ľ╩Ü╩╬╔ś╩Ś╔ă¤═Śö╩═öĂÉ╔╚¤ĽĽ¤ś╣═Ĺ╔
╚¤¤ÂŚ╔▀Ľ¤╬╔öÜŜ╔═Ŝ╣ĹÜ╚¤ĽŚ¬ł╣═ă¤Ă═ðŚ╔ĺŜăĂ╣═╣═Ĺ╔╣═öŜĽŜŚö╔╣═╔פĂ╣ö╣ăŚ╔ś╩Ś╔
ĽŜ═ŜśŜĺ╔╚É╔öÜŜ╔×╩ŚŚ╩ĹŜ╔¤▀╔öÜŜ╔╝╩═Ś╩Ś▒ĘŜ╚Ľ╩ŚÂ╩╔ěăö╔╣═╔Łëı╦¬╔Ć═╔ŁëŹç╔ÜŜ╔
▀ťĽöÜŜĽŜĺ╔Ü╣Ś╔═╩ö╣¤═╩Ă╔ĽŜםö╩ö╣¤═╔ś╣öÜ╔╩╔ŚťăăŜŚŚ▀ťĂ╔Ś×ŜŜăÜ╔╩ö╔öÜŜ╔ś¤¤×ŜĽ
╔Ć═Śö╣öťöŜ╔╣═╔ĘŜś╔Ž¤ĽÂ¬

Figure 4.8 : Le 3ème message chiffré.

La clé: 15 16 17 18 19 20 21 22 23 24 25 26 27 50 51 4 5 6 31 32 33 34 35 36 37
38 39 40 41 42 43 44 45 46 47 48 49 7 8 9 10 11 12 13 14 28 29 30 0 1 2 3 52 53

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 81

Chap.4 Chiffrement évolutionniste

Message 4 Taille: 803

By encryption, we mean a process of converting information to a disguised form in

order to send it across a potentially unsafe channel. The reverse process is called
decryption. Using strong encryption techniques, sensitive, valuable information can be
protected against organized criminals, malicious hackers, or spies from a foreign
military power, for example. Indeed, cryptography used to be almost exclusively a tool
for the military. However, in moving into an information society, the value of
cryptography in everyday life in such areas as privacy, trust, electronic payments, and
access control has become evident. In this way, the field of cryptography has
broadened from classical encryption techniques into areas such as authentication, data
integrity, and non-repudiation of data transfer.

Figure 4.9 : Le 4 ème message en clair.

ôŚðźÄŁĎŚůöśćÄ▀ðÜźðĹźťÄðťðůĎ棟ŹŹðćĆðŁćÄıźĎöśÄľðśÄĆćĎĹťöśćÄðöćðťðÉśŹ
ľÂśŹźÉðĆćĎĹðśÄðćĎÉźĎðöćðŹźÄÉðśöðťŁĎ描ðťðůćöźÄöśťĚĚŚðÂÄŹťĆźðŁ¬ťÄÄźĚ
çðˬźðĎźıźĎŹźðůĎ棟ŹŹðśŹðŁťĚĚźÉðÉźŁĎŚůöśćÄçðłŹśÄľðŹöĎćÄľðźÄŁĎŚůöśćÄð
öźŁ¬ÄśĺÂźŹ▀ðŹźÄŹśöśıź▀ðıťĚÂť×ĚźðśÄĆćĎĹťöśćÄðŁťÄðןðůĎćöźŁöźÉðťľťśÄŹöð
ćĎľťÄśîźÉðŁĎśĹśÄťĚŹ▀ðŝ̜ŁśćÂŹð¬ťŁÖźĎŹ▀ðćĎðŹůśźŹðĆĎćĹðťðĆćĎźśľÄðĹś
ĚśöťĎŚðůćÜźĎ▀ðĆćĎðźëťĹůĚźçðśÄÉźźÉ▀ðŁĎŚůöćľĎťů¬ŚðÂŹźÉðöćðןðťĚĹćŹöðźëŁĚ
ÂŹśıźĚŚðťðöććĚðĆćĎðö¬źðŜ̜öťĎŚçðŤćÜźıźĎ▀ðśÄðĹćıśÄľðśÄöćðťÄðśÄĆćĎĹť
öśćÄðŹćŁśźöŚ▀ðö¬źðıťĚÂźðćĆðŁĎŚůöćľĎťů¬ŚðśÄðźıźĎŚÉťŚð̜ƟðśÄðŹÂŁ¬ðťĎź
ťŹðťŹðůĎśıťŁŚ▀ðöĎÂŹö▀ðźĚźŁöĎćÄśŁðůťŚĹźÄöŹ▀ðťÄÉðťŁŁźŹŹðŁćÄöĎćĚð¬ťŹð×
źŁćĹźðźıśÉźÄöçðśÄðö¬śŹðÜťŚ▀ðö¬źðĆśźĚÉðćĆðŁĎŚůöćľĎťů¬Śð¬ťŹð×ĎćťÉźÄźÉðĆ
ĎćĹðŁĚťŹŹśŁťĚðźÄŁĎŚůöśćÄðöźŁ¬ÄśĺÂźŹðśÄöćðťĎźťŹðŹÂŁ¬ðťŹðťÂö¬źÄöśŁťöść
Ä▀ðÉťöťðśÄöźľĎśöŚ▀ðťÄÉðÄćÄİĎźůÂÉśťöśćÄðćĆðÉťöťðöϝďƟĎçð

Figure 4.10 : Le 4ème message chiffré

La clé: 9 10 11 12 13 14 15 16 17 18 19 24 25 26 27 28 29 30 31 32 33 0 1 2 3
22 4 5 7 8 23 20 21 6

Message3- ( 1149)
Message4-( 803)
1800
1400
1600

1400 1200
1200 1000
1000 Itérations
800
800
600 Evaluation
600
moyenne
400 400
200 200
0
16 24 30 32 0
Taille de population 16 24 30 32

Figure 4.11 : Résultats expérimentaux des messages 3 et 4

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 82
Chap.4 Chiffrement évolutionniste

V.2 Résultats retenus

Taille -Population
16 24 30 32
Message1 Nbre de générations 35 58 71 64
1026 car. Valeur de CV 1288 1394 1638 1354
Message2 Nbre de générations 26 58 46 53
684 car. Valeur de CV 1068 1100 982 1002
Nbre de générations 44 58 111 53
Message3
1149 car. Valeur de CV 1458 1622 1512 1444

Message4 Nbre de générations 34 51 38 130

803 car. Valeur de CV 886 1096 1088 1160

Table 4.1 : Tableau récapitulatif des résultats

V.3 Interprétation
Pour la plus part 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 ( message2 et message 3 dans figure1). Dans certains cas, les
tailles 30 et 32 ont donné aussi de bons résultats, mais le nombre de générations dans ce
cas été doublé ce qui est coûteux du point de vue temps. Nous conseillons alors de
prendre 24 comme taille de la population.

VI Extension de SEC à des blocs binaires

VI.1 Motivation
Dans le but d’éviter les méthodes de la cryptographie classique, sujets d’attaques de la
cryptanalyse, nous avons élaboré une nouvelle technique de chiffrement. Cette méthode
consiste à modifier les caractères d’un texte et par la suite leurs fréquences d’apparition
en partant de leur codage en binaire.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 83

Chap.4 Chiffrement évolutionniste

VII.2 Description de la méthode

Partons d’un codage binaire des caractères du texte à chiffrer et fixons un entier k (k>1).
Nous pouvons considérer alors le texte comme un ensemble de blocs de k bits,
nommés k-blocs. Et nous établissons les listes respectives des occurrences (ou
positions) des différents k-blocs dans le texte. Ensuite, nous appliquons l’AE utilisé par
SEC aux listes obtenues pour aboutir à un texte chiffré en binaire. Et enfin, nous
convertissons le texte chiffré binaire en caractères selon le codage utilisé.

Exemple :

Supposons que le Message à chiffrer est constitué des deux lignes qui suivent:

Deux types de technique se distinguent englobant toutes les méthodes de chiffrement

modernes connues.

Le message en binaire correspondant est :

0100010001100101011101010111100000100000011101000111100101110000011001010
1110011001000000110010001100101001000000111010001100101011000110110100001
1011100110100101110001011101010110010101110011001000000111001101100101001
0000001100100011010010111001101110100011010010110111001100111011101010110
0101011011100111010000100000011001010110111001100111011011000110111101100
0100110000101101110011101000010000001110100011011110111010101110100011001
0101110011001000000110110001100101011100110010000001101101000101110111010
0011010000110111101100100011001010111001100100000011001000110010100100000
0110001101101000011010010110011001100110011100100110010101101101011001010
1100101011011100111010000100000011011010110111101100100011001010111001001
1011100110010101110011001000000110001101101111011011100110111001110101011
001010111001100100000001000000

 En décomposant le message à des blocs de 10 bits on obtient 63 blocs différents.

Blocs avec leurs listes de positions :

0100010001: {1}

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 84

Chap.4 Chiffrement évolutionniste

1001010111: {2}
0101011110: {3}
0000100000: {4,32,40}
0111010001: {5,41}
1110010111: {6}
0000011001: {7,23}
0101110011: {8,48}
0010000001: {9,49,69}
1001000110: {10,54}
0101001000: {11}
0001110100: {12}
0110010101: {13,33,81}
1000110110: {14}
1000011011: {15}
1001101001: {16}
0111000101: {17}
1101010110: {18}
0101011100: {19,55,75}
1100100000: {20,56,76}
0111001101: {21,25}
1001010010: {22,58}
0001101001: {24}
1101000110: {26}
1001011011: {27}
1001100111: {28}
0111010101: {29}
1001010110: {30,66}
1110011101: {31,39}
1011100110: {34,74}
0111011011: {35}
0001101111: {36}
0110001001: {37}
1000010110: {38}
1011110111: {42}
0101011101: {43}
0001100101: {44,72}
0111001100: {45}
1000000110: {46}
1100011001: {47}
1011010001: {50}
0111011101: {51}
0001101000: {52}
0110111101: {53}
0110010001: {57}
0000011000: {59}
1101101000: {60}
0110100101: {61}

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 85

Chap.4 Chiffrement évolutionniste

1001100110: {62}
0110011100: {63}
1001100101: {64}
0110110101: {65}
0101011011: {67}
1001110100: {68}
1011010110: {70}
1111011001: {71}
0111001001: {73}
0110001101: {77}
1011110110: {78}
1110011011: {79}
1001110101: {80}
1100110010: {82}
0000001000: {83,84}

Après 48 itérations on obtient :

La clé de chiffrement
23 21 22 17 18 19 20 16 11 12 13 14 15 46 47 49 55 56 57 1 2 24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39 40 41 42 43 44 45 3 4 5 6 7 8 9 10 50 51 48 59 58 61 60 54 53
52 62 0

Message chiffré en binaire

0000001000110010000001110011010110111101011001000100000110001101101000011
0100101100110011001100111001001100101001000000110010001100101001000000111
0100011001010101011100110000100000011101000111100101110000011001100101011
1110110100001010111100000011001010001000110010100100001101001110100011010
0101101110011001110110111101100100011001110101011001010110111001110110111
0011001110110111001100111011011110101100100010001101111011000100110000101
1010111101110101011101000110010101101001011001100110011100110010000001101
1000110011011010001011001110001110100011110010111011101110110010101110001
1010001000110110100001101110011101001001101001011011010101010110111001011
0111001110101111001101110011001101011110110011100010110000101101101010110
0111010101011101000111100101110101011100111101100110110101100110001101100
1000110011100100111001100101100110010

Message code en hexadécimal

02320735BD64418DA1A59999C99481919481D1955CC207479706657DA15E0651194
869D1A5B99DBD919D595B9DB99DB99DBD6446F62616BDD5D195A5999CC81B
19B459C74797776571A23686E749A5B556E5B9D79B99AF671616D59D574797573D
9B598D919C9CCB32

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 86

Chap.4 Chiffrement évolutionniste

Commentaires :
Comme nous le remarquons dans l’exemple, les caractères du texte en clair sont
complètement modifiés ainsi que leurs fréquences. Par conséquent, il n’est guère
possible de faire une cryptanalyse par étude des fréquences des caractères.
Pour en conclure :

- Cette méthode est une généralisation de SEC. En effet, pour k=8, c’est exactement le
système SEC décrit auparavant.
- Elle augmente la résistance de notre système. Donc, elle mérite d’être étudiée analysée
plus profondément, et expérimentée pour les différentes valeurs de k. Dans ce but, des
travaux sont en cours de réalisation.

VII Discussion
Nous allons comparer notre algorithme avec l’un des algorithmes 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 notre 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 afin qu’il le soit). En outre,
notre clé est de session, et 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 types.
Autre point important à évoquer, on peut penser à une cryptanalyse par l’étude de
fréquences d’apparition des caractères dans le message. Or, nous rappelons que nos
messages ne sont pas exclusivement des messages littéraux sans ponctuation, dont
l’attaque par étude des fréquences d’apparition des lettres dans un texte écrit en une
langue naturelle est applicable en se basant sur des études en linguistique, mais peuvent
contenir tous les caractères de ponctuation, des nombres etc. Et puisqu’il n’y a aucune
étude exacte sur ces derniers donc des attaques de ce type ne sont pas satisfaisantes.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 87

Chap.4 Chiffrement évolutionniste

D’autant plus, l’utilisation d’un brouillage initial ou l’extension de SEC à des blocs
binaires, le cryptanalyste ne peut avoir une idée préalable sur les caractères du message.

VIII Conclusion
Notre travail a apporté deux contributions simultanées. La première est l’élargissement
de l’espace d’application des algorithmes évolutionnistes ; en fait, leurs applications dans
le domaine cryptographique sont jusqu’à maintenant très limitées. Cependant, leur
efficacité a été prouvée en cryptanalyse. En effet, ils ont été utilisés pour casser le
fameux algorithme de chiffrement asymétrique « Knapsack cipher » basé sur le
problème du sac à dos. La deuxième contribution est la conception d’une nouvelle
formalisation du problème de chiffrement et l’innovation d’un algorithme de
chiffrement évolutionniste. Ce dernier bénéficie de tous les avantages des algorithmes
évolutionnistes (simplicité des opérations, performance…) et possède des qualités qu’on
a 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. Et
même, la plus part des cryptologues pensent que tous les algorithmes de chiffrement
sont cassables à long terme, mais l’essentiel c’est de concevoir son système de
chiffrement de telle manière que la durée de vie souhaitée pour le texte chiffré doit être
inférieure à celle mise par le cryptanalyste pour casser ce système.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 88

 Chapitre 5

CHIFFREMENT AVEC FUSION

I Introduction
II Description du système
II.1 Formalisation du problème
II.2 Système de chiffrement
III Déchiffrement
IV Expérimentation
V Discussion
VI Conclusion

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat

Chap5. Chiffrement avec fusion

I Introduction
Le système de chiffrement présenté dans ce chapitre est une version améliorée de SEC
« enhancement of SEC » et intitulé ESEC-1. Ayant pour objectif la modification au
maximum des fréquences d’apparition des caractères du texte en clair T, afin de rendre
délicate la cryptanalyse statistique, nous avons conçu une nouvelle méthode de
chiffrement nommée « fusion ». Cette dernière constitue une étape préparatoire pour
l’application de l’algorithme évolutionniste. Elle permet en fait de générer une
population initiale plus intéressante. Ensuite, par le biais de la clé générée par notre
algorithme, nous illustrons le processus de chiffrement et déchiffrement. En dernier lieu
nous présentons nos différentes applications tout en les interprétant et par une
discussion évaluative nous montrons les avantages de notre système en comparaison
avec d’autres.

II Description du système ESEC-1

II.1 Formalisation du problème
Soit T le texte à chiffrer, T est une suite de n caractères désignés par t1, t2, …, tn .
Désignons par Li (1 ≤ i ≤ n) la liste des différentes positions du caractère ti dans T avant
le chiffrement et par card(Li) le nombre des occurrences de ti dans T .
Remarque : Li ∩ Lj est vide, ∀ i,j ∈ [1,k].
L1, L2,…, Ln est une partition de l’ensemble {1, 2, …, n}.
Le message M peut être représenté par le vecteur ci-dessous :

(t1,L1) (t2,L2) … (tn,Ln)

Le but de notre travail est de modifier au maximum les fréquences d’apparition des
caractères dans le texte T et d’établir le plus de désordre dans leurs positions. Cela est
décrit dans le paragraphe 2.3 ci-dessous.
II.2 Système de chiffrement
II.2.1 Première partie: la fusion
Le message M avant la fusion peut être représenté par le vecteur ci-dessous :

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 90

Chap5. Chiffrement avec fusion

(t1,L1) (t2,L2) … (tn,Ln)

Où les listes L1, L2, …, Ln constituent une partition de l’ensemble {1, 2, …, l }et sont
triées en fonction de leurs tailles dans l’ordre décroissant. Nous les partageons en trois
sous ensembles de tailles voisines de [n/3](partie entière de n/3), nommés
respectivement : EL, Em, Ep.
Désignons respectivement par NL, Nm et Np les cardinaux de EL, Em et Ep.

Le processus de fusion est récursif et décrit par l’algorithme suivant :

Désignons par Lm et Lp les plus petits éléments respectifs de Em, Ep, et par Sk la taille de
la clé désirable.

- Si la fusion de ces deux listes amène à une clé de taille non souhaitable la fusion
ne sera appliquée que dans Ep comme suit :

 Tirons au hasard un certain nombre de listes Lp1, Lp2,…, Lpf dans Ep.

 Fusionner les listes ci dessus revient à :

Remplacer les caractères tp1, tp2, …, tpf correspondants à ces listes par un
caractère cf tiré au hasard et ne représentant aucune autre liste.

Ajouter à la clé de fusion le triplet :

([tp1, tp2, …, tpf ] ; [Lp1, Lp2, …, Lpf] ; cf)

Ep ← Ep-{ Lp , Lp ..., Lp }.
1 2 f

 Répéter le processus de la fusion sur Ep jusqu’à atteindre la taille de la clé

désirée.

- Sinon la fusion sera appliquée récursivement sur Em U Ep comme suit :

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 91

Chap5. Chiffrement avec fusion

 Désignons d’abord les listes qui vont être fusionnées. Ces listes se
composent de Lp1, Lm1,…, Lpf, Lmf tels que f est pris au hasard dans
{1,2,…, min(Nm,Np)}, Lp1, Lp2,…, Lpf sont choisies dans Ep dans l’ordre
croissant de leur taille, en alternance avec Lm1, Lm2,…, Lmf prises dans Em
dans le même ordre, tout en tenant compte de la contrainte « ne pas
dépasser la taille souhaitable de la clé ».

r ←1; E←Ø

répéter
E ← E U Lp ULm
r r
Si taille de E ≤ Sk alors r ←r+1

f←r
 Fusionner les listes ci-dessus revient à :

remplacer les caractères tp1, tm1, tp2, tm2, …, tpf , tmf correspondants à ces
listes par un seul caractère cf tiré au hasard et qui n’est pas déjà pris.

Ajouter à la clé de fusion le triplet :

([tp1, tm1, tp2, tm2, …, tpf , tmf] ; [Lp1, Lm1,…, Lpf, Lmf] ; cf)

 Em ← Em - { Lm1 ..., Lmf } ; Ep ← Ep - { Lp1 ..., Lpf }

 Répéter le processus de la fusion sur :Ep et Em

Jusqu’à atteindre la taille de la clé désirée Sk.

- Si nous désignons par Fo le nombre de fusions appliquées alors La clé générée

représentative de ces opérations est un ensemble de FO triplets de la forme :

([ti1, ti2, … tipi], [Li1, Li2, … Lip ], ci) où :

i

ci est le remplaçant des caractères ti1, ti2, …, tip dont les listes de positions
i

respectives dans le texte en clair sont : Li1, Li2, …, Lip .

i

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 92

Chap5. Chiffrement avec fusion

Ainsi, le nombre de caractères (donc aussi de listes) se réduit après « fusion ». Et

nous désignons par :

(cf1,Lf1) (cf2,Lf2) … (cfm,Lfm)

II.2.2 Deuxième partie : usage de l’algorithme évolutionniste

Le but de l’application de l’ algorithme évolutionniste est de changer itérativement la
répartition des listes sur les différents caractères de Tf de telle manière que la différence
entre le cardinal de la nouvelle liste Li’ affectée au caractère ci et le cardinal de la liste
initiale Li soit maximale. Là nous nous rendons compte que nous sommes devant un
problème d’optimisation combinatoire. Or les algorithmes évolutionnistes sont très
efficaces dans ce genre de problème, donc nous allons les utiliser et notamment ceux
appliqués aux problèmes de permutations. Ces algorithmes ont plusieurs versions, la
plus utilisée est celle décrite ci-dessous.
a) Squelette de l’algorithme (voir Chapitre 2 §.II.2)
b) L’algorithme évolutionniste
Etape 0 : Codage
Un individu (ou chromosome) est un vecteur de taille m. Les gènes sont les listes Lp
i

(1 ≤ i ≤ m). Le i ème
gène Lp contient les nouvelles positions que prendra le caractère cfi.
i

Etape 1 : Création de la population initiale P0 composée de q individus : X1, X2, …, Xq.

Nous désignons par Ch-Initial le chromosome dont les gènes sont les listes
Lj , Lj , …, Lj (placés dans cet ordre) qui représentent le texte avant l’application de
1 2 m

l’algorithme.
Nous appliquons q permutations sur Ch-Initial afin d’obtenir une population initiale
constituée de q solutions potentielles du problème.
i :=0.
Etape 2 : Evaluation des individus
Soit Xj un individu de Pi dont les gènes sont : Lj , Lj , …, Lj .
1 2 m

Nous définissons la fonction d’évaluation F sur l’ensemble des individus Xj par :

m
F(Xj) = ∑ card(L )−card(L )
i =1
ji i

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 93

Chap5. Chiffrement avec fusion

Etape 3 : Sélection des meilleurs individus

Nous utilisons la méthode classique de la roulette (voir chapitre 2)

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

Croisement MPX (Maximal Préservative X) : (voir chapitre 2)
Ce croisement est appliqué aux individus sélectionnés avec un taux bien précis, le
meilleur taux est de l’ordre de 60% à 100% [GRE 86].
Mutation de transposition :
Cet opérateur est appliqué aux individus issus du croisement avec un taux adapté, de
préférence de 0.1% à 5% [GRE 86].
Placer la nouvelle progéniture dans une nouvelle population Pi+1.
Répéter les étapes 2, 3 et 4 jusqu’à un critère d’arrêt.
Définir la condition d’arrêt :
La fonction F est bornée car 0 ≤ F(X) ≤ 2*m pour tout individu X
En fait :
m m
∑i =1
card ( Lk i ) − card ( Li ) ≤ ∑ (card ( Lk i ) + card ( Li ))
i =1

m m
≤∑card(Lki )+∑card(Li)≤2*l
i =1 i =1

Théoriquement et mathématiquement parlant, la fonction F admet un maximum

puisqu’elle est bornée. D’après certains résultats de recherche [MÜH 93a], la
convergence d’une fonction d’évaluation est assurée mais peut être vers une valeur
proche de Max, déterminée expérimentalement. En fait, cela se confirme dans les
applications pratiques que nous avons entamés et que nous interpréterons par la suite.
Dernière phase de notre algorithme :
Désignons par Ch-Final la solution finale donnée par notre algorithme évolutionniste. A
partir de Ch-Initial et Ch-Final, nous construisons notre clé symétrique. Cette clé sera
appelée clé- génétique.

III Déchiffrement
Evidemment, nous commençons par le déchiffrement de la deuxième partie du
système.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 94

Chap5. Chiffrement avec fusion

Représentons le texte chiffré T’ par un vecteur de listes comme nous l’avons fait pour le
texte en clair. Désignons alors par c’1, c’2, …, c’m les différents caractères de T’ et par L’1,
L’2…, L’m leurs listes respectives de positions dans T’. Grâce à la clé génétique, les
caractères vont retrouver leurs listes de positions 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 :
Clef(1)=p1 , Clef(2)=p2 , …, Clef(i)=1 , …, Clef(m)=pm où
Le caractère c’p va être associé à la liste L1’.
1

Le caractère c’p va être associé à la liste L2’.

2

Le caractère c’p va être associé à la liste L’m.

m

Ainsi, nous obtenons le texte Tf..

Quand au déchiffrement de la première partie, grâce à la clé de la fusion qui est claire et
directe, nous pouvons immédiatement re-décomposer les listes fusionnées Lfi en les sous
listes d’origine et associer à chacune de ces dernières son caractère correspondant. Ainsi
nous obtenons le texte T.
Enfin, nous procédons au déchiffrement de T pour obtenir T0. Or, le passage de T0 à T
se fait par le biais d’opérations ou fonctions simples de la cryptographie (par exemple
substitution simple, décalage, chiffrement affine…) et dont la clé est secrète et
symétrique et de taille négligeable par rapport à la clé de fusion et à la clé- génétique.

IV Expérimentation
Nous avons appliqué notre algorithme sur des messages de différentes tailles ; mais nous
n’avons retenu que quatre exemples typiques. Et pour chacun d’eux, nous avons fait
l’application pour des différentes tailles de populations (nous 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.
Les messages modèles
Le brouillage utilisé pour les quatre messages ci-dessous est un chiffrement affine défini
par F(x)=ax+b où a=-1 , b=255 et x est le code ASCII du caractère du message
initial.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 95

Chap5. Chiffrement avec fusion

Message 1 : Taille=1026

Travelling salesman problem (TSP) is an NP-complete problem,

implying that there is no known algorithm to solve it exactly in
better than O(an) time (for n cities). In fact, there are (n-
1)!/2 possible combinations, so to try every one requires
factorial time with the problem size. Just to remind, there are
cities and given distances between them. Travelling salesman has
to visit all of them, but he does not want to travel very much.
The task is to find a sequence of cities to minimize travelled
distance. In other words, find a minimal Hamiltonian tour in a
complete graph of n nodes. A method was implemented for a 6-city
problem. The optimal tour found for the 6 cities was: 1- 2 - 5 -
4 - 6 - 3 - 1 which has distance 9.242640 units. The processor
times for the 5 and 6 city runs were below the timer resolution.
The time for each combination can be estimated as 2e-07 seconds.
The number of combinations for the 29 cities problem is 8.84e30.
This gives a time estimate of 1.77e24 seconds, or 5.60e16 years.

Figure 5.1 Premier texte en clair.

ðŮÖñ══ÄİÖůÁŮ═ñÁ ╔Ůİů╩ð╦╩═ñ ╔ůÖÖ╩ ╠╠ůůÄÁůŮİů╩ ╠╠Ă╦ ╔╩═ñ¤ñů╩ð╦╩═ñ ╔╠ůÄ ╔╩

═ ╚ÄİÖů¤ ă٤ů¤ ăñðñůÄÁůİ╦ů ╠İ╦ ╚İůŮ═Ö╦ðĤ ă╔ů¤╦ůÁ╦═ÖñůĤůñ ╠Ůä═ ╚ůÄİů╩ñ¤
Ö
ñðů Ůİů ╠ Ůİ ╠ůů ñů ╦ðůİůĂ ñ ╠Ěů ╠İů ŮĂ ╠ů ñðñůŮðñů İ ╠╚╠Ŝ ┼ů
╩¤╦ ¤╩ă═ñůĂ╦Ö ╩ İ٤Ä╦╔İ Ö╠ůŤ ╦ů ╦ůÄ¤Ä ð ůñÁ ñð ů İŤñůðñź ¤ ¤ Źăðñ ů ŮĂ ╦Öð Ů═ůÉ
╔╩ Ä ╩¤Ä ůÁ ÁĚů¤ Ź ¤ů ╚ ůÖ ╚İ╦ ╠ů Ä Á Ť ¤ Ä ¤Ä ╔
╦ ðñ ╔Ä ô ¤ ăñðñůŮðñůůĂĤÄñÁůŮİôůÖ
ÁÁÄ ůů
ñů ╚ ñů ð╦ ═ñ ñ
İ
ñ ů
Ĥ ă ¤ ă
ŮİĂ ╩ ╔ İ
ÁÄ× ÜĚ
ñ ů ñ ññ ů ñ ů ð ñ══ ů ═ñ
Á¤ Ů
¤ İ Ů Ůİ Ů
ů ů ╦ů Ů
ů ══
ÄÖ ůôÄÁ¤ ╠ů╩ŹÁů ¤ ╚
ůů ╦ Ť ¤ ăñ ╔ ñů ╦ñ ůݤ╦ă ů╔╚ŮİÖ ůÖ╦ů ðÄŮÖñ═Áů ñðÁ ╔╚ůů ăŹĂÁĚů¤ ñů Ů ╠ů
ÖÄÁĤ
¤ ŹăİĂô ÁůĂ ¤
ů ╦ů İ ůŮů ñź ñ ñů ñ ů¤╦ů¤ ݤ Ö ñůÖðŮ ñ══╔ñ ůă Ö ăŮİäñĚÁů ╠İÄÁ ů
¤ ŤÄ ô Á╠ů İ ůŮů╦ Ťİ Ä¤Ä Ů ůľÁ٤ ╔ÄİÄŮİ ╔Ä×
ůů ¤Ź ů Ö İůŮů ╩
ôĂôÄÁ¤ Ů╩
╦¤ ăñðů ╚╦ð ═ ═ ╦ ╦ ð ╦ ═ ñ ñů ð
ů╦ ůİůİ╦ ñôÁĚůůŤĹÄůôñ ╦╔ÄůÄ╚Ů╔ ů ╩═╔ñÄ ñ¤İ ñÄ ů ╦ð¤ůŮů▀Ä╠Ă ╚ů╩ð╔╦╩═ñ¤ ĚůÖ ñůă
Ť ╔ ¤ă ô Á Ä ╔ ╔ ¤ ô Ť ╔ Öă
╦╩¤Ä ╔Ů═ů¤╦ Źðů Ť╦ Źİôů Ť╦ðů¤ ăñů▀ůĂĤÄñÁů ╚ŮÁîů ╚╠ů┼ů ╠ůĺů ╠ůĆů ╠ů▀ů ╠ů»ů ╠ů ╚
ô Á Ĥ
ů╚ Ă ů ůŮ ŮİĂ ñůťĚ┼Ć┼▀Ćı ů Źİ Ě ╩ Ă
ñů ð╦ ñ ╦ðů ñ ů ╦ðů ñůĺů
Ůİ ăůÄ▀ůăĂ ă Á╚ůðôÄÁ¤
Źİ ů ╚ñðñů╩ñ═╦ ╚ů ñůĤÁñðůðñ Öă ¤Ä ╔ Á Ť ¤ă
╦═ Ź¤Ä╦İĚůůÖ ăñů¤Ä ╔ñů Ť╦ðůñŮ
ÁÁ
Ă ůĂ╦ ╩ İŮ ╦İůĂŮİů╩ñůñ
ô Ĥ Á ¤ ă ¤Ä ╔
Ů ñ ůŮ ů┼ñ ╠ıćů ñĂ╦İ Ěůů ñůİŹ ╩ñðů╦ ů
Á
Ă╦ă ╩ İŮ╔ Ä İ¤Äů ðů ñů┼ ťůÁ¤Ä Ă ╔ ñ¤ ůô╩ðÁ╩ ñ ů ůŚ Öă ╔
╦ ═ ╔ ÄÁ Ě ŚĆñ» ıĚůÖ ăÄÁůÖÄÖñÁůŮů¤
Á ôÁ Ť
╔ Ä ¤Ä╦ Ť╦ ¤ă
Ů ñů ů Ě ććñ┼Ćů ñĂ╦İ ╠ů╦ðůĺĚ▀ıñ ╚▀ů ╚ñŮð Ěů
Á Ä¤Ä Á
ñůñ
Ä╔ Á¤Ä ╔ ¤ ╦ Ť ╚ Á ôÁ Á

Figure 5.2 La forme cryptée du premier texte

La clé de la fusion :
({ë, ś, Î} ;{4 111 230 327 358 382 429 433 501 969,10 70 97 325 364 581 967, 29 141 152 187 865} ; ź)
({Ł, Č, ▒};{24 57 128 201 208 276 341 402 641 802 852 904 914 945, 31, 42}; Ć )
({ł, ╬} ;{ 92 263 344 418 527 609 687 717 797 806 , 190 692 715 992 1017,} ; ć )
({Í , Ď, Ë, ö, ç, ░, Â}; {33 144 165 191 , 44 189 632 693 697 701 705 709 713 883, 61 175 217 301 400 532
1007 , 89 452, 118,140, 168 518}; »)

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 96

Chap5. Chiffrement avec fusion

La deuxième clé :
22 23 24 25 26 27 28 29 30 31 32 20 33 34 35 36 37 0 1 2 3 4 5 6 7 8
17 18 19 9 21 10 11 12 13 14 15 16

Message 2 : Taille=684
Astronauts: In August 1983 Guion Bluford became the first African
American to go into space, while serving on a mission aboard the
Challenger space shuttle. Bluford said that the blastoff of the
shuttle was like riding in a high-speed elevator through a
bonfire. He also recognized that, "From a black perspective, my
flight on the shuttle represented another step forward.
"Astronaut Mae Jemison became the first African American woman to
travel in space when she flew on the space shuttle Endeavor in a
September 1992 mission. After her space flight, Jemison resigned
from NASA and established the Jemison Group, a company that
researches, develops, and markets advanced technologies.

Figure 5.3 Le deuxième texte en clair

ťĺŚ ĚůťŚĺťĚśťť═ ťĺŚśťťť═ ś═ ťł Ěś═ ćť▓ ╣ ś═ Čů ║ śŚ▒ ś▓ ł 匜ť▓ łČůĚśť

║ öłČĎůĚśŚ ś═ śłĚ Ś śĺ▓ůČ ćś╣▒ łĎć śĺ ╣ĎöłĚ═ śÁĚśůÁś ║łĺĺ łĎ öů═ Ďůö╣ö śŚ▒Á ś═
Á Ěś
▒ůćć Ď Ď Ď Ď
═Áö śĺ ůČÁ śĺ ťŚŚćÁČś═ ćť Ďö śĺů ł śŚ ůŚśŚ Á ś═ ćůĺŚĎ▓▓ śĎ▓ śŚ▒Á śĺ▒
▓ ▒ ▓ ╣ ╣ ▒ ▒
Áö Ě Á Á Áö
ťŚŚć ╣ůĺśćłŹ ś ł╣ łĚ═ śłĚśů ś▒ ł═▒ ĺ▓ ╣ ś ć ╣ůŚ śŚ▒ ť═▒ śů ś═ Ě▓ ł Č
Á ś
śĹ śůćĺ ś Č ═ÁĚöł▀ ╣ śŚ▒ůŚćśŜ Á ▓
║Éśů ś═ÁÁćůČŹś Á ĺ▓ĎöČ Śł╣ö Ďćś ║ľś▓ ćĎł ▒ ŚöÁ
═ ś Ě
Á
śŚ▒ śĺ▒ ťŚŚć ś ▓ ĺ Ě Ś ╣ śůĚ Ś▒ śĺŚ ▓ ś▓ ╣ů ╣ČÁ ŜťĺŚÁ ĚůťŚśıů ś Ď║ł
Á Ď öÁ Ď Á îö Ď Áö
Ď Áö Á Ďö ö öĎ
ĺ Ěś ═Á Á Ś▒Á ś▓ łö 匜ť▓ö łČůĚśť║Áö łČůĚś╣ Ď ║ůĚśŚĎśŚöů╣Á 朳̜ĺ▓ůČÁ ś╣▒
Á Čů ║ śÁ öÁ öÁ Á Á Á ×Á
Ď
Ěśĺ▒ ś▓ ć ╣ ś ĚśŚ▒ śĺ▓ůČ śĺ▒ ťŚŚć ś Ě╣ ů╣ śłĚśů ś ▓ Ś ║═ śťťť ś ║łĺ
ĺł ĚČś
Á Á ť▓ ŚÁ ś▒Ď śĺ▓ÁůČ ś▓Áćł ▒ Śćś Á ║ôłĺ Ěś Á Ďö ĺł═Ě ╣ ś▓ÖÁ ║Áś ťÁöťśůĚ╣ Ťś ĺŚů
Ď ═ Ď öĎ Ü Ö
═ ćłĺ Á Ś Á ×Á ║łĺĎ ═ö Ďť ć ů Ď ║ ů ľ Ś ůŚśöÁ ĺÁůöČ▒Á ĺćś╣Á╣Á ćĎ▓ ĺćśů
▒ ╣ ś ▒ ś Ěś ▓ ś śČ ▓ Ě ś ▒
Áö Áö Á ×Á öÁ Á Á
Ě╣ ś ║ů Ź Śĺśů╣╣ůĚČ ╣ śŚ Č▒Ě ć ═ ł ĺČś
ö Á Á Á Ď Ď Á

Figure 5.4 La forme cryptée du deuxième texte

La clé de la fusion :

({İ, Â, ╬, Ă, ă} ; {8 15 17 27 34 149 158 196 247 333 380 483 609, 11, 21 513, 22 514 515, 23} ; Ŝ)
({╠,Ş, ś, Ł,╝} ; {24, 26 606, 32 156, 40 120 178 253 295 395 509 586, 130} ; ś)
({ ł , ë} ; {92 202 367 429 454 466, 101 237 310 441 494 642 664}; Ť)
({Ć }; {86 142 229 301 305 341 362 449 476 505 538 610 618 646 }; )
({Ë} ; {90 285 312 549 611 638 ť648} ; ô)
ð
({ } ;{154 260 371 525 683} ; )

La deuxième clé
21 22 24 17 18 19 25 20 7 23 26 27 28 29 0 1 2 3 4 5 6 9 12 10 11 13
15 14 8 16

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 97

Chap5. Chiffrement avec fusion

Message 3 : Taille=1149

Abraham Lincoln, the 16th president of the United States, guided

his country through the most devastating experience in its
national history--the CIVIL WAR. He is considered by many
historians to have been the greatest American president. Abraham
Lincoln was born Sunday, February 12, 1809, in a log cabin near
Hodgenville, Kentucky. He was the son of Thomas and Nancy Hanks
Lincoln, Thomas Lincoln was a. Abraham had gone to school
briefly in Kentucky and did so again in Indiana. He attended
school with his older sister... Both of Abraham's parents were
members of a Baptist congregation which had separated from
another church due to opposition to slavery. When Abraham was 7,
the family moved to southern Indiana As Abraham grew up, he
loved to read and preferred learning to working in the fields.
This led to a difficult relationship with his father who was
just the opposite. Abraham was constantly borrowing books from
the neighbors. Lincoln's declining interest in politics was
renewed by the passage of the Kansas-Nebraska Act in 1854. In
Figure his
1860 he furthered 5.5 Lenational
troisième texte en clair with a successful
reputation
speech at the Cooper Institute in New York.

Figure 5.5 Le troisième texte en clair

śśİşðşĚłĚ╣═ă¤Ă═öł╦ð╚łĚă╦ðłöİ╚Ľ╣╩╚═╦ł¤Žł╦ð╚łĚ═╣╦╚╩łĂ╦ş╦╚ĽöłËı╣╩╚╩ł
ð╣Ľłă¤ı═╦İŽł╦ðݤıËð╦ð╚łĚ¤Ľ╦ł╩╚ËşĽ╦ş╦╣═Ëł╚ăö╚İ╣╚═ă╚ł╣═ł╣╦Ľł═ş╦╣¤
═şĂłð╣Ľ╦¤İŽöö╦ð╚łĂËËËĚłıśôźł▒╚ł╣Ľłă¤═Ľ╣╩╚İ╚╩łśŽłĚş═Žłð╣Ľ╦¤İ╣ş═Ľł╦¤
łðşË╚łś╚╚═ł╦ð╚łËİ╚ş╦╚Ľ╦łśĚ╚İ╣ăş═łöİ╚Ľ╣╩╚═╦źśśİşðşĚłĚ╣═ă¤Ă═łŜşĽłś¤İ═ł
Ăı═╩şŽöłŹ╚śİışİŽłĚ×öłĚŚś┤öł╣═łşłĂ¤Ëłăşś╣═ł═╚şİł▒¤╩Ë╚═Ë╣ĂĂ╚öłě╚═╦ıă原ł
▒╚łŜşĽł╦ð╚łĽ¤═ł¤Žł▀ð¤ĚşĽłş═╩łľş═㎳▒ş═弳Ě╣═ă¤Ă═öł▀ð¤ĚşĽłĚ╣═ă¤Ă═łŜşĽłşźł
śśİşðşĚłðş╩łË¤═╚ł╦¤łĽăð¤¤Ăłśİ╣╚ŽĂŽł╣═łě╚═╦ıă厳ş═╩ł╩╣╩łĽ¤łşËş╣═ł╣═łË═
╩╣ş═şźł▒╚łş╦╦╚═╩╚╩łĽăð¤¤ĂłŜ╣╦ðłð╣Ľł¤Ă╩╚İłĽ╣Ľ╦╚İźźźłĹ¤╦ðł¤ŽłśśİşðşĚť
Ľłöşİ╚═╦ĽłŜ╚İ╚łĚ╚Ěś╚İĽł¤ŽłşłĹşö╦╣Ľ╦łă¤═Ëİ╚Ëş╦╣¤═łŜð╣ăðłðş╩łĽ╚öşİş╦╚
╩łŽİ¤Ěłş═¤╦ð╚İłăðıİăðł╩ı╚ł╦¤ł¤öö¤Ľ╣╦╣¤═ł╦¤łĽĂşË╚İŽźłıð╚═łśśİşðşĚłŜşĽ
łÉöł╦ð╚łŽşĚ╣ĂŽłĚ¤Ë╚╩ł╦¤łĽ¤ı╦ð╚İ═łË═╩╣ş═şśĽłśśİşðşĚłËİ╚Ŝłıööłð╚łĂ¤Ë╚╩
ł╦¤łİ╚ş╩łş═╩łöİ╚Ž╚İİ╚╩łĂ╚şİ═╣═Ëł╦¤łŜ¤İĺ╣═Ëł╣═ł╦ð╚łŽ╣╚Ă╩Ľźł▀ð╣ĽłĂ╚
╩ł╦¤łşł╩╣ŽŽ╣ăıĂ╦łİ╚Ăş╦╣¤═Ľð╣öłŜ╣╦ðłð╣ĽłŽş╦ð╚İłŜð¤łŜşĽłÜıĽ╦ł╦ð╚ł¤öö¤
Ľ╣╦╚źłśśİşðşĚłŜşĽłă¤═Ľ╦ş═╦ĂŽłś¤İݤŜ╣═Ëłś¤¤ĺĽłŽİ¤Ěł╦ð╚ł═╚╣Ëðś¤İĽźĚ╣═ă
¤Ă═ťĽł╩╚ăĂ╣═╣═Ëł╣═╦╚İ╚Ľ╦ł╣═łö¤Ă╣╦╣㼳ŜşĽłİ╚═╚Ŝ╚╩łśŽł╦ð╚łöşĽĽşË╚ł¤Žł
╦ð╚łěş═ĽşĽöľ╚śİşĽĺşłśă╦ł╣═łĚŚîŤźłË═łĚŚăśłð╚łŽıİ╦ð╚İ╚╩łð╣Ľł═ş╦╣¤═şĂłİ╚öı
╦ş╦╣¤═łŜ╣╦ðłşłĽıăă╚ĽĽŽıĂłĽö╚╚ăðłş╦ł╦ð╚łĂ¤¤ö╚İłË═Ľ╦╣╦ı╦╚ł╣═łľ╚ŜłÖ¤İĺź

Figure 5.6 La forme cryptée du troisième texte

La clé de la fusion :
({Ł} ; {2 174 201 239 258 273 301 406 432 534 559 666 720 883 905
Ŝ
915 935 993 1024} ; ) ĺ
({ │, ╬, ¬} ;{9 150 246 374 390 940, 22 280 284 1038 1047, 44}; )

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 98

Chap5. Chiffrement avec fusion

ť
({ ╔, ç} ;{23 1049, 107} ; ) ś
Ć ę};{96 198 316 654 693 741,147 149 472 709 1044 1128, 148}; )
({ë,Â,
({ , Ď} ;{27 108 228 543 571 602 638 639 733 757 837 873 874 972
Č 1000 1080 1108 1124, 140 141 1021} ; Ë)
({ ć, ╝};{51 263, 146 1121};ô)
({ };{76 139 175 İ180 268 278 330 366 438 450 657 689 903 994}; Ö)
({Ę} ;{152,660}; )

La deuxième clé
22 23 24 25 29 30 31 32 33 34 19 17 18 35 36 37 38 0 1 2 3 4 5 6 7 8
9 10 27 11 20 21 26 28 13 14 15 12 16

Message 4 : Taille=805
Cryptographic knapsacks are based on the Subset Problem: Given
a finite set W={w1, ..., wn} of positive integers and a positive
integer C, does there exist a subset W'of W such that the sum of
all elements in W' is equal to C? The relationship with
encryption is straightforward. Let the message space be the
set of binary strings b1,...,bn as
C= b1w1 + ... + bnwn In practice arithmetic is carried out in
some finite field and various sophistications are used to
construct the knapsack set(e.g. arithmetic may be modulo some
prime p and the knapsack elements are chosen in such a way to
enable the receiver to easily decrypt the message). If the
subsets of W are arranged to have unique sums then this
encryption is reversible and so, given a sum S, there will be a
unique plaintext message.

Figure 5.7 Le quatrième texte en clair

Ś ťŚě ľ ďťźě ě ť ďěŚ └ď ě └ťď źď ľ └ďľ └ď Ś └Źľďďďľ └źď

ç ççÂÍ └ ç └Ä │Ź Źı
ěď ź ď ď ď │ Î ď Źź▀ď× Îď Í Â └ďď╝×Î
çÎ śśś
ź └ťÂ └Ś
ďěźťďěď Ä │ └
ç Í××
ď ╝źÄ └ť ďť │╝ď Éľ └Ś └ďďÉ └Ĺ ďěď
ÄÂ└ŚďÎ Â └ Í╝ çÍÎÄÂÄ └ Ź│ ďÄ Źď └ď Źď │
ľďÎ ľě ď ľçÍÎÄÂÄ
Ä Â └ └ŹçÉ
ďě ď Â ÄÎÂ Î ╝
└ź ď źď Ź ď ď └ ě ď ď ďďİ ľ └ďŚ └ ě
Í Î ×Î Â îÍ╝ Î╝ │
ź ľ ď Ź ľď └ź
   Î╝ Ś Í╝
×× × ŚěÂÎ
źď ď ťľ Ś 쌝 ďďďĺ └ ďď ľ └ď └ ěť └ďď ě └ďď └ď ľ └ď └│ďççÂ
Ä îŹ ÄÎ ś Ü╝ × ÂÍ çŁ Ź × ÂÄÍ Î Äç ÄÂ
ď
ÄÍ ÄΠΠŚ Ä Â╝Í │ źď× Śě Π└ďěŚ Â Í╝
źěŚ ď źť ď ı śśś źďě ď ď ıŹıď ďÎÎśśśď ďÎ矏źď
ľŹ └ çďÎÂďÄ쌌
×Ä Î ×└ťďÉ
ďÉ× źď Î Źç└ď│ × ź └╬ ╬ × ěŚ
ď └ ťďěźťď Ë ç │ÂÄ ľ│
ď ÄÂ
ě
ÂÄ │ ÄÎ└ │ └ťď Í╝Â Ä Ś ÎÍ ľ╝└Ä Ä ╝
ź ďěŚ ď Ä
ď ź ď ďťźě ě ťď └ ð └śťśďěŚ ľŹ └ ď Źě │ď
Ä × │ ÄÍ╝ Î ÎÍç ÄÎÂÄ
└ď ŹÎ ť ď╝Î Ź └ďÂÍŚ Ź│Í└ďÎÂ
ÂÄÍ ╝ │ ¾ └ďťźě çÎ
ďěźťď ě ťď│ └Î └ÂŹ └ź ďěŚ └ďÄ ľ ÂÄ └źď│ źďç
Í Ź╝×Í ÎÍ └źěç Ä└ ľç└ └ └ └Śďď çÎ └│ │ ś╝ď
× ľďěď
ě ď ď ď ďŚ ď ě ďť Ś ď ľ └ď Ź └ ěť
× └ ÂÎ ÍÎ Ä└Î
│ ď ľ └ďç ÂÍ └ ď××ď ŹďďěŚÂ │ Ä │
└ď쌌쟝 └ťď ďľ └ └ď ź
ÂÍ ÎÄ×ç │ └ďď
çç  Ź ď ľ └źď ľ ď
ÎÎ é
╝ ÂŚ Î╝×Î
Ë└ź
ďŚÍ└╝ └Ś
źď ÂÎ └ďěźťď ďťÂÍ └źďěď │ ╝ ŹďľÄÜ╝ ľÎ└Ś
ď ╝ └ďÎ ŹÂ ď Â└ďěď ÄÎ
ź │ ÄÎ │
└ď ě ź └Ĺ ď Ź └ ěť └ś
ççÂÄÍ ÎÄ×× ÎÍÉ Ä │ Î╝ É Â Ä×× × ╝
ÄÜ╝ ç× Ä Â Â ÎÎ

Figure 5.8 La forme cryptée du quatrième texte

La clé de la fusion :

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 99

Chap5. Chiffrement avec fusion

ć Ć
{{ , ,»};{3 258 331 519 593 627 633 720, 4 10 18
98 123 247 259 306 378 448 491 536 542 555 634 721 787, 49}; {╝}}
{{ö , Ť } ;{ 15 22 488 495ś 552 559 , 33 119 143 282 407 432 436 469
526Č546┼ 629 683 743} ;{ }} Ś
{{ , , } ;{ 42 761, 56 ,60};{ }}
{{ ô } ;{ 53 198 199 202 223 238 431 528 562 602 626 738 772
773 788} ;{Ł}} ť
{{ ë , ┬ } ;{ 62 104 129 438 614 690 732 751, 80 355};{ İ}}
{{ Ö, ä } ;{ 68 96 172 195 276 324 421 428 652 667, 81};{ }} ĺ
{{ Ę , ł } ;{79 169 174 213 669, 82 91 249 279 359 372 591 770};{ }}

La deuxième clé :
14 15 16 17 18 13 1 6 4 19 20 21 22 23 24 25 26 27 28 29 0 5 7 12 10 8 9 2 11 3

V Discussion
Pour qualifier notre système ESEC-1, nous allons le comparer à des systèmes de
chiffrement symétriques très connus. Prenons par exemple IDEA. Il est considéré par
les spécialistes comme l’un des meilleurs cryptosystèmes à clé privée. Il est utilisé par le
PGP pour le chiffrement de données.

La longueur de sa clé est 128 bits (mieux que le DES qui est de 64 bits). Notre système
possède deux clés. La première est celle de la « fusion » dont la taille sera fixée à une
valeur raisonnable et incassable de nos jours ( nous évitons la taille proche de la taille du
texte pour ne pas avoir le même inconvénient que le chiffre de Vernam [LAB 01] où la
clé est de la taille du message à envoyer). La deuxième, est générée par l’algorithme
évolutionniste, et au moins de l’ordre de 30*8 =240 bits (elle peut même aller jusqu’à
256*8), car nous pouvons toujours supposer que le nombre de caractères différents dans
le texte est au moins 30 (sinon nous pouvons lui en rajouter afin qu’il le soit) ; taille
encore plus importante puisqu’elle résiste mieux à la cryptanalyse par recherche
exhaustive. Cela dit, les deux clés sont de session et purement aléatoires alors que celle
de IDEA ne l’est pas.

IDEA chiffre par blocs (opère sur le texte en clair par groupes de bits appelés blocs) ; ce
qui est un atout pour la cryptanalyse différentielle. Le nôtre chiffre autrement (agit sur
tout le texte en clair à la fois), donc il est d’une part à l’abri d’une telle cryptanalyse,
d’autre part il est moins coûteux. Cependant, la seule cryptanalyse redoutable dans notre
cas est celle basée sur l’étude des fréquences d’apparition des lettres dans un texte. Or,
grâce à la fusion les vraies fréquences des caractères ne sont plus reconnues, par

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 100

Chap5. Chiffrement avec fusion

conséquent le cryptanalyste ne peut se baser sur de fausses statistiques, d’autant plus

qu’il ne possède ni clé fixe, ni table fixe indiquant les différentes substitutions possibles
des caractères comme par exemple dans le cas du chiffrement poly alphabétique de
Vigenère [STI 03] (en fait, ce dernier a été cassé à cause de la longueur de son mot-clé).
Pour en finir, la force de cette fusion réside dans le fait que les listes fusionnées sont
aléatoires, le caractère remplaçant aussi, et la taille de la clé maîtrisable.

VI Conclusion
Par ce travail nous avons atteint deux objectifs. Le premier est l’introduction d’une
nouvelle méthode de chiffrement « fusion » dont le majeur avantage est le renforcement
du système contre les attaques les plus redoutables, quant aux autres avantages, ils sont
mentionnés dans la discussion ci-dessous. Le deuxième est l’exploitation des algorithmes
évolutionnistes pour la conception et la réalisation d’un chiffrement bénéficiant de
toutes les qualités des A.E (simplicité des opérations génétiques, performance,…). Nous
avons évalué ce travail en le comparant à d’autres systèmes de même nature.

Malgré les qualités dont dispose notre système (résistance aux attaques, génération
aléatoire de ses propres clés, taille intéressantes des clés….) nous ne pouvons, comme le
pensent la plus part des cryptologues, dire qu’il est sûr (seul le chiffre de Vernam ou
masque jetable l’est, d’après Shanon [SHA 49]). Donc là, un long trajet reste à parcourir
par les mathématiciens cryptologues.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 101

t
 Chapitre 6

CHIFFREMENT AVEC FRAGMENTATION

I Introduction
II Description de l’algorithme
II.1 Premier chiffrement
II.2 Fragmentation des listes
III Déchiffrement
III.1 Premier déchiffrement
III.2 Second déchiffrement
IV Discussion et conclusion

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat

Chap.6 Chiffrement avec fragmentation

I Introduction
Dans ce chapitre, nous présentons un nouveau système de chiffrement basé sur SEC,
désigné par ESEC-2. Ce système consiste, en premier lieu, à modifier les fréquences
d’apparition des caractères du texte à chiffrer et en second lieu, à établir un équilibre
entre ces dernières.
Ainsi, dans la première partie de notre système de chiffrement nous faisons appel à SEC,
notre premier algorithme de chiffrement, tel qu’il a été donné au chapitre 4, nous
l’appliquons à un message M pour aboutir à un message M’. Ensuite, nous procédons à
la « fragmentation » des listes des positions des caractères de M’ qui sont de grandes
tailles et désignons de nouveaux caractères pour les associer respectivement aux
positions figurant dans les fragments de liste. Cela permet d’avoir des listes de tailles
très voisines dont il est encore plus difficile de faire la cryptanalyse par étude des
fréquences de caractères. Cette fragmentation est en fait un sur-chiffrement de SEC.
II Description du système ESEC-2
II.1 Premier chiffrement
Etant donné un message M formé à partir de n caractères c1, c2, …, cn. Nous
définissons les listes : L1, L2, …, Ln des différentes positions de chacun des caractères ci,
1 ≤ i ≤ n.
La première partie du système de chiffrement consiste à répartir, d’une manière itérative,
les listes sur les différents caractères de M, de telle sorte que la différence entre le
cardinal de la nouvelle liste L'i associée au caractère ci et le cardinal de sa liste initiale
Li soit maximale. Nous obtenons ainsi un message chiffré M’.
Pour plus de détails, nous renvoyons le lecteur au chapitre 4.

II.2 Fragmentation des listes

II.2.1 Description informelle
Le message M’ obtenu dans la première partie est constitué des mêmes caractères c1, …,
cn de M auxquels sont associées les listes L’1, …, L’n. Ces listes sont, en général, de tailles
différentes. Le but de la deuxième partie de notre système est de transformer le message
M’ en un message M’’ dont les listes associées à ses caractères sont presque de même

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 103

Chap.6 Chiffrement avec fragmentation

taille, ceci en décomposant les listes de grandes tailles en d’autres listes, lesquelles sont
associées à de nouveaux caractères.
II.2.2 Description formelle
Soient L’1, …, L’n les listes des différentes positions associées aux caractères c1, …, cn du
message M’ obtenu à partir du premier chiffrement.
 n 
 ∑ card ( L 'i ) 
Soit l= E  i =1 
 n 
 
 
Parmi les listes ci-dessus, nous pouvons distinguer celles de grandes tailles ( leur taille est
supérieur à la taille moyenne l )
Soit L’j une liste de grande taille associée au caractère cj (card(L' j )>l) .

card ( L ' j ) 
Posons n j = E   + 1
 l
Nous allons fragmenter la liste L’j en nj+1 listes L’j , L’j , …, L’j et L’j de tailles égales
1 2 nj nj+1

exceptée L’j dont la taille est soit nulle soit plus petite que celle des L’j (1≤ k≤ nj).
nj+1 k
’
En effet, si le résultat de la division euclidienne de card(L ) par nj est : j

card(L’j) = nj *q + r alors q sera la taille des listes L’j , L’j , …, L’j et r sera celle de L’j .
1 2 nj nj+1

La première liste L’j sera associée au caractère c j tandis que les autres listes sont
1

associées à de nouveaux caractères cj , cj , …, cj

2 3 nj+1
’ ’ ’
Donc L’j = L’j U L U …U L U Lj j j
1 2 nj nj+1

La décomposition de L' j en L’j , L’j , …, L’j et L’j est effectuée comme suit :
1 2 nj nj+1

Si L’j = {p1, p2, …, pmj} alors

L’j1 ={p1, pnj+1, p2nj+1, …}
L'j2={p2, pnj+2, p2nj+2, …}
…… …………
Ljnj = {pnj, p2nj, p3nj, …}
L’j est constitué des r derniers éléments de L’j.
nj+1

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 104

Chap.6 Chiffrement avec fragmentation

Le caractère associé à la liste ayant subi une fragmentation est enregistré avec les
nouveaux caractères dans une liste appelée clé-fragment

Figure 6.1: Schéma d’une clé-fragment

La liste ci-dessus constituera une clé secrète qui va être utilisée lors du déchiffrement.
D’une manière formelle, l’algorithme de chiffrement par fragmentation est le suivant :

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 105

Chap.6 Chiffrement avec fragmentation

Début
Données : Message M’ obtenu à partir de l’algorithme 1 de chiffrement
Résultats : Message chiffré M’’
Méthode :
Déterminer les listes des positions L'1,L'2 ,...,L'n associées aux caractères c1, …, cn
du message M’
 n 
∑ card(L'i) 
Soit l = E i =1 
 n 
 
Où E[x] est la partie entière de x, i.e le plus grand entier inférieur ou égal à x.

Pour j :=1 à n faire

Si card (L’j) > l alors /* L' j est une liste de grande taille */
card(L' j ) 
Soient n j = E  +1 et m j =card(L' j )
 l
/* fragmentation de L’j */
Soient nj listes L’j 1, L’j 2, …., L’j nj initialement vides qui sont associées
respectivement à des nouveaux caractères cj1, cj2, …,cjnj
/* Répartition de L’j sur L’j 1, L’j 2, …., L’j nj */
Supposons que L’j = {p1, p2, …, pmj}
Pour k :=1 à mj faire
d :=k mod(nj)
/* d est le reste de la division entière de k par nj */
Mettre pk dans la liste L’jd
Fin pour
Enregistrer (cj,[cj1, cj2, …,cjnj]) dans clé-fragment
Fin pour
Fin
Figure 6.2 : L’algorithme du chiffrement par fragmentation

III Déchiffrement
Le déchiffrement est effectué en deux étapes essentielles :
Première étape : déchiffrement par l’utilisation de clé-fragment qui à partir du message
chiffré M’’ permet de trouver le message M’.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 106

Chap.6 Chiffrement avec fragmentation

Deuxième étape : déchiffrement par l’utilisation de la clé génétique qui à partir du

message M’ permet de retrouver le message d’origine M.
III.1 Premier déchiffrement
Pour chaque élément (cj,[cj1, cj2, …,cjnj]) de clé-fragment nous remplaçons dans M’’
toutes les occurrences des caractères cj1, cj2, …,cjnj par le caractère cj.
III.2 Second déchiffrement
Cette étape est traitée d’une manière détaillée au chapitre 4, qui se résume par la
construction des listes de positions associées aux différents caractères de M’. Ensuite
utiliser la clé génétique pour retrouver les vraies positions des caractères.

Exemples

Message 1 :
Abraham Lincoln, the 16th president of the United States, guided
his country throughthe most devastating experience in its
national history--the CIVIL WAR. He is considered by many
historians to have been the greatest American [Link]
Lincoln was born Sunday, February 12, 1809, in a log cabin near
Hodgenville, Kentucky. He was the son of Thomas and Nancy Hanks
Lincoln, Thomas Lincoln was a. Abraham had gone to school briefly
in Kentucky and did so again in Indiana. He attended school with
his older sister... Both of Abraham's parents were members of a
Baptist congregation which had separated from another church due
to opposition to slavery. When Abraham was 7, the family moved to
southern IndianaAs Abraham grew up, he loved to read and
preferred learning to working in the fields. This led to a
difficult relationship with his father who was just the opposite.
Abraham was constantly borrowing books from the
[Link]'s declining interest in politics was renewed by
the passage of the Kansas-Nebraska Act in 1854. In 1860 he
furthered his national reputation with a successful speech at the
Cooper Institute in New York.

Figure 6.3 : Le 1er message en clair

Le nombre d’itérations est: 44

L’évaluation moyenne est: 1440
La moyenne des cardinaux des listes est: 21

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 107

Chap.6 Chiffrement avec fragmentation

La clé génétique est :

11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 52 53 33 34 35 36 37 38 39 40 41 42
43 44 45 46 47 48 49 50 51 0 1 2 27 28 8 9 10 29 3 4 5 6 7 30 31 32

wFF2NB''jj9KkA&r[7*B]m
QqƒL{\h=9n‰?X†c…ŠaBPo‚39!>^lQE?a)r@,t|9n>n7B9[`zttK‹e]7qB2t,,B*ˆƒ''A
iX7n8D)ŠaN=&,…!0LL{3\‰KkP|‚^79G@7(?=†&EZb739iz‹eTTTaB[54Y4j]pwsdƒf!X
|)…`J‰Gi9nh2hPFe^'D‚e@*=9ia{39NKi7†[q(8ˆ]F !&ƒŠaBX,‹\ENˆGQ…w' h|9D‰P
L{!hi9n‚?dwF‹2*('^j=9`zA&@UE)i7JA‰[lt‚KDer]S\F{ttNeƒmgrXmuyvr…39P(^Z
b,@7EF|&K7ˆDN[f†>, ‚889Z!r]xxhKt`-
edƒf\XUUN…7qˆP7i&^Jc@CCB'()i7‰K[ID‚Kk]ffNKGƒj=&`†A‰rXC*z'(N…j3‚KkZbP
UE)^Dd@wF{2q(''7B>[,,& ]Q†ƒG`*zJAXF‹|!cZe…7‰Pxx‚?ttke^DNK@>=9n7i[7N(
3&]|‰ƒ4‚>nENDdXf\…7Naˆ&Kn>P)`q†zA^U=Qa@*3Gi7Zbnh[7|)?a{ddd]VVŠqƒ†cXw
F‹(NB'WG…LDN2‰KaPUˆ{ ^'!'FF‹)@zcc7[V(LQa9?]7k‚,,2,EŠ=9AƒU*3`qX7B>…7i
LLN(N hPc‹†'^E&zQ*!h@7qt{`kB7tt[?J]7LL†)|Ša9‰ƒ7aXGiD8\‹ed…p*ˆ‚PwFF2q
('^UEN@Rrr7aB[cD'=Ze]''8!hƒ?†X)ztŠ*B{2…4&>39N(wGPwF‹EqD'^,,2U@tLrr7B
[7b8 h]7aƒ{!hNX(‚K…L‹2c\h{ˆ>PZ E‹2K&,^Q†@UzA2-
‰,,7‚[?*!]c39hbndƒCq|)XZ\>…ŠJPD^7n9c=9ktb@{ˆZbN39AKiBLL7U9*[q=9]c(Ša
B‹ƒU*†XUE)….tGiPQq!^zLLJA3?ad@wFFDNB''7()[`k&GŠE‰Kae]F†{‹zU|‚,ƒFJA--
Xcc2'…Q*\P7Kh9qFz{)dj=&KkZ‰WG^> `k3‚|9K@7&?!‹2hia7‰[LLZ39|9k]UDGƒ72‚
ˆU hXFe…QaBPLLN)(,,^†c@?*\h7ENKDNTIˆF{2N-([w`Š]7&ƒmuH1dX4‰…mu
yPq ^ct‹2aBh2>@*=Gi7EQ3zADN[{\Lt?aN|J&]UU9qƒ(X7tt`ˆ)GctZ…7i !hkPEQ^?
*B@55†L\‹24‰)Š=9tQˆ[3‚]I Uƒ6zA2d

Figure 6.4 : Le chiffrement du 1er message après fragmentation des listes

Caractère associé à la liste fragmentée remplaçants

A † z J
b Z
a Q ? Š
h \ ˆ !
i ) G
n >
2 { ‹
9 = 3 |
K & ‰ ‚
k `
N ( E D
B * q
7 [ ] ƒ X … P ^ @
Table 6.1 : La clé de fragmentation du 1er message

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 108

Chap.6 Chiffrement avec fragmentation

Message2 :

Travelling salesman problem (TSP) is an NP-complete problem,

implying that there is no known algorithm to solve it exactly in
better than O(an) time (for n cities). In fact, there are (n-
1)!/2 possible combinations, so to try every one requires
factorial time with the problem size. Just to remind, there are
cities and given distances between them. Travelling salesman has
to visit all of them, but he does not want to travel very
much. The task is to find a sequence of cities to minimize
travelled distance. In other words, find a minimal Hamiltonian
tour in a complete graph of n nodes. A method was implemented
for a 6-city problem. The optimal tour found for the 6 cities
was: 1- 2 - 5 - 4 - 6 - 3 - 1 which has distance 9.242640 units.
The processor times for the 5 and 6 city runs were below the
timer resolution. The time for each combination can be
estimated as 2e-07 seconds. The number of combinations for the
29 cities problem is 8.84e30. This gives a time estimate of
1.77e24 seconds, or 5.60e16 years.

Figure 6.5 : Le 2ème message en clair

Le nombre d’iterations est:32

L’évaluation moyenne est: 1534
La moyenne des cardinaux des listes est: 19

La clé génétique est :

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 51 32 33 34 35 36 37 38 39 40 41 42
43 44 45 46 47 48 49 50 2 3 4 1 52 0 6 7 26 27 28 29 5 30 31 8 9

ddzqqu‰3H778B23FT_[EaVze‰#‡+ldingLYŒR*8€}
nssmvaa3uƒ aG‹e‰>‡oˆUHaa3{H7]$pB"\=Z(uzu8HE['+6€A::L_‰7ŠVŒHp(Y$‹*F'v3#}U"
„552=‰bˆ{[]eƒu$>G\"ZB€A8l_2AE+=pHrLl99vY[*8ŒHU Rg0}P€ 992$oˆ"p#V„]BGƒ\llA)
gN-
cc8ŠvF{ee3E8m‡ee[_=Œ'€Ro+8TL8pY$pz*8u Vb}‹vA G„t,UHzFˆ992"'V{B‰]=pH>\:ŒHZ
(E$p(+aGzee3‡LRUy#0Yh,,"*=Š}8zu{[ko 8ZƒV>ˆ_Gz]\8mHŒ FT8€kE7Uq#u+k{R"B[&„u
Leƒ=:>u€Y8p ‡0*ddzq#‰33H7}FT‰„RTB[ Z_2ˆ$‹]qŒFU"\82‰3E'9+=pƒ‡oLe,,YZ>*kkv
u}€Š$ :B2Aˆ=‹]8V_q u\q#GbbE8,,m0+dZ„L$p26Y{F*"'}99[k BˆRƒt,>€&m]89\8Œ=U uT8
pE‡{HAHŒy#+$pzq„‰33kLkUF"p[&>0YP€*‹=p(V}:'GkRo 9{HAˆB]‡r[ŒH_‰\ww2UH3p
€{B2AE$Š,,+8[L_Y8mva‰ "#*7Vz2Z}'9 €ˆ8Ak„u0]\xx8ƒ=p(kE:BF+ŒHaa3‡r[A kL9‹GY
_*Os&U$b}aaze‰#u0 dZ„ˆ8v"{‡r2]=Š,V\9‹,€kk8'GE8pƒ+OL8mHŒ>RY:B2f*)s}c sˆ.]s\II8
EO+sL1Ys*)}:ZU&m Z_Fˆk{R"p2Am]!0cIcOI/\,[AHp0dd u8az&#FRŠVE8ŒH„u+9‹GL$Zƒ
Y.*B€k}O 8U"bˆ8z,A]:>Vz\e ‰'::8p#E8{‡„G+8zRTv3$pH[0LYdZ>*"ŒHr}9‹V _&mˆ8
m‡eU€A2{Hv]&B[\e#u8uTpH_$ƒkE82+c>s/SLRTum€kk0Y*dZ }8A‡e#G ‹9ˆ&'veŒ[B"UH
€F]9Šv\=p„u8!E8{HpHR+aV‹e‰>‡LŒHYJ0JIIu/0*dZUF}7{q R _ˆ$pH#]„u"Œ‡r2ƒ\'9980S
S>cIEFTumvARo+ŠGL.0O/ )OYb#B2z0*

Figure 6.6 : Le chiffrement du 2ème message (après fragmentation des listes)

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 109

Chap.6 Chiffrement avec fragmentation

Caractère associé à la liste fragmentée remplaçants

T F R
R ‡
V Š ‹ '
M &
P $ " =
( Z
2 B _
U # „ ƒ >
Z V G
H ΠU {
A [ €
3 ‰
8 E + L Y * } ˆ ] \
Table 6.2 : La clé de fragmentation du 2ème message

Message 3:

Cryptographic knapsacks are based on the Subset Problem: Given a finite set W={w1, ..., wn} of
positive integers and a positive integer C, does there exist a subsetW'of W such thatthe sum of
all elements in W' is equal to C? The relationship with encryption is straightforward. Let the
message space be the set of binary strings b1,...,bn as C= b1w1 + ... + bnwn In practice
arithmetic is carried out in some finite field and various sophistications are used to construct the
knapsack set(e.g. arithmetic may be modulo some prime p and the knapsack elements are chosen
in such a way to enable the receiver to easily decrypt the message)...

Figure 6.7: Le 3ème message en clair

Le nombre d’itération est:28

L’évaluation moyenne est: 886
La moyenne des cardinaux des listes est : 14

La clé génétique est :

11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 30 31 32 33 34 35 36 37 38 39 40 41 42
43 44 0 5 6 26 27 7 29 1 2 3 28 4 8 9 10

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 110

Chap.6 Chiffrement avec fragmentation

ww??T+,jq<TI()rrOxT|Dr@KCxqtoO8~gXF/[20;Œaho9V\Aijq1cˆ
kZJCnQsstK|&.‹(y(~XC;t+}L'ebdŒCBSSAe/uZF.J<T1Q2‹sVtKC(\ˆ,,tq&CxgXO[CT9Q^‹s~ŒC
(y+,VjAwdZgg1tp2+ItqtK;PQ@\&|X8ho9V^}lF.[}ŒChh)AC+I2\0ˆZ@h JC..OccKCc~
; ^8&‹(y}l[C(ŒVmh|cAC+Zw:JCGGIKjqcc2Q(1y0‹<&ee(+I~ D)??^QF1y‹@Œ8p+Ox(02..1q
|jgBAZJv;\+K^+I&
ˆ9ppx,t[@<Ox)ŒAo;ZC0VJ8ˆ2+[Link]/|x?&9\j‹ ,,pobddBSSooyCxŒwLAobebZfJBSBSfKo/e
&WWyCTqD^+()t|jQ(+I~2‹DŒC(AC)xjQ;gZC1\J‹/y9F
VK..(Q^ˆ&.‹(cgXOxg[s|xq(1hp@F<0Q8p‹D)2+(19AOj~Zhh;gJ\F1C)1@^+qD)+2+I&rr|xTpx)X
9ˆ\==t,B[OjQ^0 ~t‹DŒ |?Ao;Z Fghcc1CF Vt<Tq(ˆKCTCxgX2+Itr O<@|x)Œ~c;
Vt\8ACjˆZD0I1ptJQ yChh)IO&e|?X^F[~tyxc;ŒC0VACqD)‹s~jZJ2+1;O@p(?KgVt)??\&^+IX
t9|,~{{BS
Figure 6.8 : Le chiffrement du 3ème message (après fragmentation des listes)

Caractère associé à la liste fragmentée remplaçants

C K & X [ ΠA Z J
Y /
P @ 8 9
T ~ ; V ˆ
S B
1 F
X O |
Q j
T <
+ 2 \ ^
I 0
( Q ‹
) D
Table 6.3 : La clé de fragmentation du 3ème message

Message 4:

By encryption, we mean a process of converting information to a disguised form in order to

send it across a potentially unsafe channel. The reverse process is called decryption. Using
strong encryption techniques, sensitive, valuable information can be protected against organized
criminals, malicious hackers, or spies from a foreign military power, for example. Indeed,
cryptography used to be almost exclusively a tool for the military. However, in moving into an
information society, the value of cryptography in everyday life in such areas as privacy, trust,
Le nombre
electronic payments, d’Iteration
and access est:38
control has become evident. In this way, the field of
cryptography L’évaluation
has broadenedmoyenne est: 976encryption techniques into areas such as
from classical
authentication, La
datamoyenne desnon-repudiation
integrity, and cardinaux desoflistes est 23
data transfer.

Figure 6.9 : Le quatrième message en clair

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 111

Chap.6 Chiffrement avec fragmentation

La clé génétique est :

9 10 11 12 13 14 15 16 5 6 7 22 23 24 25 26 27 28 29 30 31 32 33 8 20 18 19 4 21 0 1 2 3
17

kxxIHbtxoo.B0Dej'n[HMŒE o/8!‰HG„ZppIty--H()0UDNMp8yi<[Link]'I.ŒI q) BU
TNGjq„p8/nn I0DZ&q[H'(.ŒI‰Mq )4„E!/8GrrIDo [Link]'T0GEpjŒI, <M b[
zw m,‰„&i-jHi[HI/i!‰GrDIG'ItzzzHŒqj!&x o4)80w aarMU„[Link][0b/ xo(. BM
D4‰!,,bsTTHr'Gj0brB.-[ Œ-EzT<fz‰ )Mp8&nn(NZy„It0bIf Hooi4j!t[q'< U Uc M
G(Œ 8/UE cbv‰q I&Nnn0< zzr„nnz)!NZTGrIEcg gHirDI/' GoojHŒ p& 8n <„p
Zy[) UM bINzz4./x Dooe‰& 'p8yŒIHEnozjw uub[‰ q „!/xoo.U &<o,xxI GrH D(.'fj
ŒIzn8y4 [ddzTG)-‰zx„EcI.yzDp8y'(,,HnNzz4</xw lZej-[& „)0bIn-NMU DIBb.'I0
Œ)M pZyiE(NBy Ir!t‰4x „I.,H-<zTjDZp'I/xo(.U&io,xŒ)0 [-‰HxqEx„zNpp HIM
DGT!,' </jHcŒEG o&)-<cx „[Link]. [z‰!(/8ybBDooxnnH4G 'EM qŒ< !tjHG !Z
[Link]„,,crI[ Htn ‰DI--qj0(w'uMŒ4,)G eEx „I.[HIN‰zq DZp'!tx o(.U/<o, xŒ,,c f&8E
qqHjq „ppinnIz<Grr!tzD[0b/xo 4)BM'I‰!,,bsTTHŒI0(8 E& j<c„GTT,,IcDET4,[M
b.!<(NZyb'qq4E ŒI0b‰UUi(x <Mq„Ib0h/iHTqNB4.8M bIpDqEc.'(&icb pjHwŒ

Figure 6.10 : Le chiffrement du 4ème message (après fragmentation des listes)

Caractère associé à la liste fragmentée remplaçants

B ) N
Y 8 Z
C E <
R G
T !
I / &
. ( 4
B 0 M
I D ' Œ „
H j [ ‰
Table 6.4 : La clé de fragmentation du 4ème message

IV Discussion et conclusion
Le système de chiffrement ESEC-2 que nous avons détaillé, bénéficie, en plus des
avantages du système SEC, d’une force considérable de défense contre les attaques qui
se basent sur les études des fréquences d’apparition des caractères dans un texte. En
effet, avec l’utilisation de SEC, des échanges de fréquences d’apparition des caractères
sont établies aléatoirement . Et par la fragmentation des listes, les valeurs des
fréquences sont complètement modifiées. D’autant plus, les caractères représentants les
listes fragmentées sont tirés au hasard et changent d’une session à l’autre.
Enfin, cette méthode est avantageuse par rapport à la « fusion » décrite au chapitre 5.
En effet, la clé de fragmentation ne contient pas les positions des caractères ajoutés.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 112

 Chapitre 7

ANALYSE ET COMPARAISON DES

SYSTEMES IDEA, RSA, PGP ET SEC

I Introduction
II Implémentation de l’IDEA
III Implémentation de RSA
IV Implémentation de PGP
V Implémentation de notre algorithme SEC
VI Comparaison et analyse

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat

Chap. 7 Analyse & Comparaison …

I Introduction

Dans le but d’achever l’évaluation de notre travail, nous allons présenter dans ce
chapitre les différentes comparaisons de nos systèmes de chiffrement SEC aux
systèmes les plus dominants actuellement IDEA, RSA et PGP. Ces comparaisons se
basent sur les temps de chiffrement et du déchiffrement. Pour ce, le langage de
programmation utilisé est Delphi, sous l’environnement Windows.

Dans la deuxième partie de ce chapitre nous exposons les résultats relatifs au système
IDEA. Quant à la troisième partie, elle est consacrée à ceux du système RSA. Les
résultats concernant PGP sont présentés dans la quatrième partie, et ceux concernant
notre système SEC sont présentés dans la cinquième partie. Enfin par des comparaisons
évaluatives, nous achevons ce chapitre.

II Implémentation du système IDEA

Figure 7.1 : Interface du IDEA dans le cas du chiffrement d’un texte

Commentaire :

Les temps de chiffrement et déchiffrement sont très voisins dans le cas d’un texte

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 114

Chap. 7 Analyse & Comparaison …

Figure 7.2 : Interface du IDEA dans le cas de chiffrement d’une image

Commentaire : Dans le cas des images, le temps de déchiffrement augmente

légèrement par rapport à celui du chiffrement.

Autres Résultats Expérimentaux

• Texte :

Nous allons chiffrer le texte suivant : « there is only one God and Mohamed his
prophet ». avec les clés : ‘n_lagraa_b_kamel’ , ’n_lagraa_lakhdar’ et
‘o_lakhda_b_kamel ’.

Clé secrète Texte crypté

n_lagraa_b_kamel u {e Z æƦ,þº ÖÃC [¦—êþ Ðä[¦åM U/ §Ñâ ”W×Õ¹ÊJ«ûI «ôSf
n_lagraa_lakhdar ðÊ÷ù‡”%õ¢œÀ¦ÄD]õ“sIî -i ºlºóV9
M%Õ (^
©žUÜ.H 8ïI É#w^B
o_lakhda_b_kamel ÀîgÜ4jã‾†I" †CGxöñúÉÈÇ ¤Y çb_ïѹpM ^&~{zâ€Ù~x%
ðªv öІ>

Table 7.1 : Résultats obtenus avec IDEA

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 115

Chap. 7 Analyse & Comparaison …

Nous remarquons que le changement de clé donne des résultats

différents, par contre le temps de chiffrement reste constant.

• Image :

Nous allons chiffrer l’image BMP 244.188 avec la clé « cryptage_image_1» .

Image en claire Image crypté

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 116

Chap. 7 Analyse & Comparaison …

III Implémentation de RSA

III.1 Présentation de l’interface de RSA

Figure 7.3 : Interface du RSA

III.2 Autres Résultats expérimentaux

Nous allons chiffrer le même texte « employé avec IDEA « there is only one God and
Mohamed his prophet ». Dans chaque essai on utilise un couple ( privée/ publique )
différent :

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 117

Chap. 7 Analyse & Comparaison …

Les Nbrs Clé Clé groupa Tps

Texte crypté
premier privée Publique ge d’exe
049301040277068002770843054703
960843125007391271106308431250
073902770843090812501199084302
580739119908431013125001040258
P = 1 0 3 N=1339 046302771199084301040547039608
D = 5 5 1 1 5 ms
q = 1 3 E = 3 1 1 431266068012501266010402770493
084308430843084308430843000000
00000000000000

125297103175330655465075295003
439671224695007759203747940444
P= 1087 N=1479407 367114810910723751219521051763
D= 263743 2 7 ms
q=1361 E=369247 613604131475350070889306952390
550315116284700892051117956024
9765
104391230013963270620604073620
087056168511456340440849465526
P =104327 N=1417908257 085024887904183708470460259670
D=265835689 3 10 ms 018254469204364683551178963961
q=13591 E=354447589
023791672901206759770893980837

Table 7.2 : Résultats obtenus avec RSA

IV Implémentation du PGP

Le PGP est un système de chiffrement hybride clé publique combinant les avantages de

IDEA et RSA. IDEA est 1000 fois plus rapide que RSA alors qu’il est pratiquement

impossible de percer la clé secrète de RSA. Toutes les procédures utilisées par l’IDEA

et le RSA sont exploitées par le PGP.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 118

Chap. 7 Analyse & Comparaison …

IV.1 Présentation de l’interface de PGP

Figure 7.4 : Interface de PGP

IV.2 Résultats expérimentaux

L’exemple suivant montre le contenu du fichier chiffré par PGP. On a repris le même
message utilisé par IDEA et RSA.

Clé
Clé privée clé de session Message crypté
publique

pgp0108133301070104010013330114009501071333
N=1339 113901010108009509770053' ø?R cëw†KÁ§ ®Jÿ&)Ø
D=307 Lakhdar_kamel_25
E=307 Gb<l
°9ç ~(ÎAÝ9Xêx-^Œu´ÓÕ¼¼/

Table 7.3 : Résultats obtenus avec le PGP

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 119

Chap. 7 Analyse & Comparaison …

On remarque que le message chiffré commence par les trois lettres ‘pgp’ indiquant que
ce dernier a été chiffré par PGP, ensuite on trouve les chiffres représentants la clé de
session, suivis par les données cryptées.

V Implémentation de notre algorithme SEC

V.1 Présentation de l’interface de SEC

Figure 7.5 : Interface des fichiers de SEC

Figure 7.6 : Interface des paramètres de l’AE de SEC

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 120

Chap. 7 Analyse & Comparaison …

V.2 Résultats expérimentaux

L’exemple suivant montre le chiffrement du texte précédent avec SEC.

Paramètres AG
clé de session Texte chiffré
size pop nbrgen

AE ytsrmlihgeda pon
10 5 ytsrmlihgeda adeghilmnoprstyolr
ponadeghilmnoprsty yipydehnyderymdsytesygdltgrsylipya
dalrol
Table 7.4 : Résultats obtenus avec SEC

Le fichier contenant le message chiffré débute par ‘AE’ indiquant que ce dernier est
chiffré à l’aide des AE ensuite la clé de session suivie du texte chiffré.

VI Comparaison et analyse
VI.1 Comparaison entre les algorithmes modernes et l’algorithme évolutionniste

Le tableau de la figure 7.10 donne les temps de chiffrement et déchiffrement des

différents algorithmes pour un texte de taille 16 ko.

Les paramètres utilisés pour chaque algorithme sont::

IDEA : On n’a aucun paramètre influant sur le temps du calcul.

RSA : Les paramètres qui influent sur le temps du calcul sont les valeurs des nombres
premiers p et q (le tps augmente suivant la valeur de p et q).

On a pris q = 103 et p = 13.

SEC : Les paramètres qui influent sur le temps du calcul sont le nombre de génération
et la taille de la population. On a choisi taillepop =10 et nbrgene=10.

IDEA RSA SEC

tps de cryptage 30 ms 330 ms 200 ms
tps de décryptage 40 ms 390 ms 20 ms
Table 7.5 : Temps de chiffrement et de déchiffrement

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 121

Chap. 7 Analyse & Comparaison …

450
400
350
300
250
tps de
200 cryptage
150
100 tps de
50
decryptage
0
IDEA RSA SEC

Figure7.7 : Représentation graphique du temps de chiffrement et

de déchiffrement

VI.2 Discussions
On a vu que :

a. IDEA a un temps de chiffrement et de déchiffrement très petits par rapport aux

deux autres algorithmes mais l’inconvénient des algorithmes symétriques est
comment faire circuler la clef privée de manière sûre et confidentielle. C’est un
algorithme performant et difficile à casser.

b. RSA est très lent en chiffrement et déchiffrement comparativement aux autres

algorithmes. On peut considérer ceci comme un inconvénient. Mais c’est un
algorithme robuste, sa clef privée est difficile à casser.

c. SEC a un temps de chiffrement moyen comparativement aux temps de

chiffrement de IDEA et RSA et un temps de déchiffrement plus petit par rapport
au temps de déchiffrement des deux autres systèmes.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 122

 CONCLUSION GENERALE

Par le biais de cette thèse, nous avons pu réaliser un travail d’innovation consistant à
définir un système de chiffrement basé sur un problème d’optimisation combinatoire.
Notre outil de base est : les algorithmes évolutionnistes. Le premier obstacle franchis
pour la réalisation de ce travail, était la formalisation du problème de chiffrement de
façon à le ramener à un problème d’optimisation combinatoire. Le deuxième obstacle
franchis était l’établissement des éléments de base de l’algorithme évolutionniste à
savoir : codage des chromosomes, définition de la fonction d’évaluation, choix des
opérateurs génétiques. Enfin, la génération de la clé de session du chiffrement par
l’algorithme évolutionniste en était l’ultime.
Ainsi, après la construction d’un premier système de chiffrement évolutionniste dont
des applications sur différents messages ont été réalisées, illustrant le bon
fonctionnement de ce système, deux améliorations ont été élaborées dont le but d’avoir
un chiffrement plus sûr. Ce qui a permis l’obtention de deux autres systèmes de
chiffrements distincts plus résistants que le premier. Des discussions évaluatives ont eu
lieu, à la fin de chaque chapitre décrivant l’un des trois systèmes, permettant ainsi
d’illustrer les avantages et les qualités de nos systèmes comparativement aux autres
existants actuellement. Cependant, montrer qu’un système de chiffrement est sûr n’est
pas une tâche facile. Nous rejoignons nos collègues cryptologues en disant que tous les
systèmes de chiffrement sont cassables à long terme ( excepté le masque jetable d’après
Shanon), mais l’essentiel c’est que la durée de vie souhaitée pour le texte chiffré soit
inférieure à celle mise par le cryptanayste désirant casser ce système.

I Limites de nos travaux

- Dans le but de ne pas avoir une clé finale symétrique dépassant les normes, nous nous
limitons dans le brouillage initial à un nombre très réduit d’opérations de chiffrement
classique

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat

Conclusion

-Certes, la nouvelle technique de chiffrement « fusion » augmente considérablement la

résistance de notre système, cependant elle présente l’inconvénient d’augmenter la taille
de la clé secrète. Nous ne pouvons donc pas fusionner autant de listes que nous voulons.
En fait, nous risquons d’avoir une taille de clé aussi longue que le message. Donc nous
avons intérêt à limiter le nombre de fusion.
-Quand à la fragmentation elle possède l’avantage d’avoir une clé de taille très petite
comparativement à celle de la fusion. Toutefois, le choix des caractères remplaçants reste
limité lorsque le texte en clair se compose d’un très grand nombre de caractères
différents
-Le trafique des clés secrètes a toujours assez limité l’utilisation des algorithmes
symétriques, des efforts restent à fournir pour laisser la porte grande ouverte à ce genre
de systèmes qui sont plus rapides que les autres types de systèmes.

II Perspectives
Dans le but de délimiter les champs de nos travaux, nous envisageons de nouvelles
perspectives :

-Dans une prochaine publication, nous présenterons notre nouvelle technique de

chiffrement (voir [Link]), qui permet d’éviter l’usage de la cryptographie classique
dans le brouillage initiale. Cette méthode permet d’avoir un ensemble de solutions
potentielles plus intéressant et donne un chiffrement plus performant.
-La combine des deux méthodes « fusion » et « fragmentation » renforcera
incontestablement la résistance de notre système, pourvu de trouver des techniques pour
réduire les tailles des clés. Des travaux de recherches dans ce sens sont en cours de
réalisation par notre équipe.
-Concevoir un opérateur de mutation des gènes permettant de modifier mutuellement
(ou bilatéralement) les contenus de listes.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 124

 BIBLIOGRAPHIE

[BAY 03] Bayart F. La cryptographie [DEJ 75] Dejong K ., An Analysis of

éxpliquée. 2003. the Behaviour of a class of genetic
[Link] Adaptive Systems. Doctorat
/moderne/aes.php3 dissertation, Dept. of Computer
[BEA 93] Beasley D., Bull D.R. and and Communication Sciences,
Martin R.R., An overview of Genetic University of Michigan, Ann
Algorithms: Part1, Fundamentals. Arbor, 1975.
Techn. Report of [Link] [DJE 95] Djerid L. Portmann M.C.
Cardiff, UK , University and Villon P., Performance Analysis
Computing,15(4), 1993, pp.58- of Previous and New Proposed Cross-
69. Over Genetic Operators Designed for
[BEC 90] Beckett B., Introduction aux Permutation Scheduling Problems.
méthodes de la cryptologie. Edition International Conference on
Masson 1990. Industrian Engineering and
[BIH 93] Biham E. and Shamir A., Production Management,
Differential Cryptanalysis of the Data Marrakech, April 4-7, 1995.
Encryption Standard. Springer- [DUB 98] Dubertret G. Initiation à la
Verlag, 1993. cryptographie. Edition Vuibert,
[CAU 95] Christophe Caux- Henri 1998.
Pierreval- Marie-Claude [FAL 91] Falkenauer E. and
Portmann. Les algorithmes génétiques Bouffouix S., A Genetic Algorithm
et leur application aux problèmes for job Shop. Proceedings of the
d’ordonnancement. APII. Volume IEEE international Conference
29-N° 4-5/ 1995, pp 409-443. on Robotics and Automation,
[CLA 91] John A Clark. Invited [Link] 824-829.
Paper . Nature-Inspired [FLO 02] Florin G. et Natkin S.,
Cryptography: Past, Present and les techniques de la cryptographie.
Future. Department of computer CNAM 2002.
Science, university of York, York, [GIR 01] Giry D. et Durand S.
YO10 5DD, UK, 1991. Travaux d’études et de recheche
Email: jac@[Link] Cryptographie. Octobre 2001.
[DAV 85] Davis L., Job-Shop [Link]
Scheduling with genetic algorithm. eb_Ter
Proc. Ist Int,. Conf on Genetic [GOL 85] Goldberg D.E, and Lingle
Algorithms and their R., Alleles, Loci, and the TSP.
applications, Lawrence Erlbaum, Proceedings of the First
Hillsdale, NJ, 1985, pp 136-140. International Conference on
[DAV 91] L. Davis , The genetic Genetic Algorithms, 1985, pp
Algorithm Handbook. Ed. New- 154-159.
York: Van Nostrand Reinhold,
ch.17, 1991.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat

Bibliographie

[GOL 89] Goldberg D.E, Genetic [MIC 92] Michalewicz Z., Genetic
Algorithms in Search, Optimisation Algorithms +Data= Evolution
& Machine Learning. Addison- Program. Springer- Verglas, 1992.
Wesley Publishing Company, [MIC 94] Michalewicz Z., Evolutionary
Inc,1989. Computation techniques for non linear
[GRE 86] Grefenstette J.J, Programming. International
Optimization of Control Parameters Transactions on Operational
for Genetic Algorithms. IEEE Research, 1(2), 1994, pp 223-240.
Trans. On SMC, Vol. 16, n°1, [MÜH 93a] Mühlenbein H.,
Jan/Feb. 1986, pp. 122-128. Evolutionary Algorithms: Theory and
[HOL 75] Holland J.H., Adaptation in applications. (Wiley) 1993.
Natural and Artificial Systems. [MÜH 93b] Mühlenbein H., and
Cambridge, Mass: MIT press, Schlierkamp-Voosen D.
1975. Predictive Models for the Breeder
[JAN 91] Janikow C.Z, and Genetic Algorithm-I, Continuous
Michalewicz Z., An experimental Parameter Optimisation.
Comparison of Binary and Floating Evolutionary Computation (1),
Point representation in Genetic 1993. pp 25-49.
Algorithms. Proceedings of the [MÜL 03] Didier Müller, Ars
Fourth International Conference Cryptographica. 2003.
on Genetic Algorithms, 1991,pp [Link]
31-36. [Link]/crypto/
[KHA 88] Khan Phang C., [NAK 91] Nakano R., and Yamadat,
Algorithmes heuristiques et Conventional Genetic Algorithm for
évolutionnistes. Thèse de doctorat Job Shop Problems. Proc. Fourth
université de Lille. (Octobre Int. [Link] Genetic
1988). Algorithms, ed. Morgan
[LAB 01] Labouret G. (2001). Kaufman, San Mateo , California,
Introduction à la cryptographie. 1991, pp 474-479.
[Link] [PGP 98] PGP. (1998). Personal
ours/crypto/[Link] Privacy pour windows 2000, XP, et
[LAC 03] Lacomme P., Prins C. et NT. Traduction française:
Sevaux M., Algorithmes de graphes. [Link]-cryptologie, NAI.
collection algorithmes, Ed. [SHA 48] Claude Shannon, A
Eyrolles, Paris, 2003. Mathematical theory of
[MEI 93] Meier W., On the Security of Communication. Bell System
the IDEA Block Cipher. Advances Technical Journal, July 1948., p.
in Cryptology EUROCRYPT 379; Oct. 1948, p.623
93, Proceedings, Springer - [SHA 49] Claude Shannon.
Verlag, 1994, pp. 371-385. (1949). Communication Theory of
[MEN 97] Menezes A.J., Oorschot Secrecy Systems. Bell Systems
P.C. van et Vanstone S.A., Technical Journal
Handbook of Applied Cryptography. [SCH 96] B. Schneier, Cryptographie
(CRC Press, 1997). appliquée. Seconde édition (John
Wiley & Sons, 1996).

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 126

Bibliographie

[STA 91] Starkweather T. , Mc [STI 03] Douglas Stinson, D.

Daniel S., Mathias K, Whittley C, Cryptographie Théorie et pratique.
and Whittley D, A Comparison of Traduction de Serge Vaudenay,
Genetic Sequencing Operators. Proc. Gildas Avoine et Pascal Junod.
Fourth Int. Conf. On genetic (2ième édition). Paris Vuibert
Algorithms ed. Morgan Informatique, 2003.
Kaufman, San Mateo, California,
1991, pp 69-76.

[Link] / Thèse en Informatique / 2006 / Faculté des Sciences Rabat 127