Mot clés: chiffrement évolutionniste, ACEO, parallélisation, optimisation, extension, modèle en îlots, sous population.
Résumé. Ce papier présente une tentative d’extension de l’Algorithme de Chiffrement Evolutionnaire basé Occurrences (ACEO) permettant le chiffrement de messages regroupant la majorité des caractères du code ASCII. Pour pouvoir traiter des messages écrits suivant d’autres langues que celles adoptées par l’ACEO, telle que la langue chinoise, l’hébreu, …, nous avons pensé à augmenter l’espace de recherche par les caractères de ces langues. Cette augmentation va entrainer un allongement du temps de calcul. Pour éviter cela, la solution la plus prometteuse sera de faire une parallélisation de cet algorithme en utilisant le modèle en îlots. Ce modèle repose sur la division de la population en petites sous populations évoluant chacune sur un processeur suivant un schéma fonctionnel et en envoyant ses meilleurs individus soit vers une population voisine, soit dans un pool commun. Une étape dite de migration est ensuite appliquée sur les sous populations, où chacune d’entre elles reçoit des individus soit envoyés par ses populations voisines soit péchées dans le pool central. L’intérêt de cette méthode de parallélisation, est que chaque sous population évolue selon des paramètres différents, c’est pour cela qu’il doit y avoir des bon paramètres pour produire des meilleures solutions à chaque moment de l’évaluation.
Pendant longtemps la science des secrets était utilisée seulement dans certains domaines plus au moins très sensibles, mais depuis l’avancement considérable des technologies actuelles en matière de traitement de données, de puissance de calcul et de réseaux de télécommunication, elle est devenu, une tâche critique dans un nombre important d’applications telles que l’historique médical, la sécurité sur internet, la sécurité des réseaux…etc.
Par conséquence, la conception d’algorithmes de chiffrement puissants est devenue
plus compliquée, néanmoins il existe des algorithmes de chiffrement qui ont résisté à
plusieurs attaques comme : le RSA qui fait parti du groupe asymétrique, l’AES et
l’IDEA qui font partie du group symétrique et le PGP [
Une nouvelle approche est apparue dans la conception des algorithmes de
chiffrement, c’est l’utilisation des algorithmes évolutionnaires inspiré de la théorie de
l’évolution naturelle [
L’article est organisé comme suit : une description de quelques algorithmes de chiffrements évolutionnaire, une description de l’extension de l’ACEO nommée ACEO2, une comparaison entre les différents algorithmes évolutionnaire de chiffrement présentés et une discussion.
2.1
Le SEC est un algorithme de chiffrement évolutionnaire. Dans l’opération de
chiffrement il encode un texte M0 constitué de 256 caractères de code ASCII, par
l’application d’un ensemble de transformations (substitution, permutation et
chiffrement affiné) pour obtenir un texte M. Son principe consiste à construire des
listes Li contenant les différentes positions des caractères Ci, puis il joue sur l’ordre de
ces listes pour obtenir un désordre maximal à condition de ne pas modifier le contenu
des listes. Dans le SEC un individu est un vecteur de taille m et ses gènes sont
représentés par les listes Li ; ensuite, le SEC enchaine le processus évolutionnaire
(évaluation, sélection, opérateur de croisement et de mutation). Enfin, une clé dite
« clé génétique » est générée [
Pour l’opération de déchiffrement, le SEC et grâce à la clé génétique il trouvera les
listes des positions des différents caractères puis le texte M sera récupéré. La dernière
étape dans l’opération de déchiffrement est l’application des fonctions inverses à
celles utilisées pour l’encodage. On obtiendra ainsi le message initial M0 [
La méthode de chiffrement utilisée par l’algorithme SEC peut être appliquée sur n’importe quel ensemble d’entités (caractères, bloc de caractère, bloc de bits etc...). Pour assurer une protection contre les attaques basées sur l’étude des fréquences des caractères du texte à chiffrer, on coupe ce dernier en blocs de bits après l’application d’une opération de codage binaire et puis on applique l’algorithme évolutionnaire. Le codage adopté par SEC-EX consiste à : conversion du texte T en binaire, choix aléatoire d’un entier k, coupage du texte T en bloc B1, B2,..., Bm de taille k (si le dernier bloc contient moins de k bits, on le complète avec des bits 0). Nommons Li la liste des différentes positions du bloc Bi dans T et par Ch-intial le vecteur des gènes Li (1≤i≤m).
L’application de l’algorithme SEC sur les listes des blocs Li permet le changement de
la distribution des listes des différents blocs Bi de T. considérons Ch-final la solution
finale obtenue par l’application de cet algorithme. Le texte chiffré est obtenu par
l’association de chaque bloc Bi à une liste Li’ de Ch-final. Le couple k et les
permutations qui transforme Ch-initial vers Ch-final constitue la clé secrète [
Dans l’ACEO une transformation du message en clair M0 vers un schéma particulier est faite en calculant le nombre d’occurrence, Oi, dans M0 des 149 caractères admissibles. Ces 149 nombres d’occurrence représentent les différents gènes et leur ensemble constitue un individu ACEO. Il est à noter que les caractères qui ne figurent pas dans M0 auront des occurrences nulles. Ainsi, la somme des 149 valeurs de gènes égale la longueur du message M0.
Pour augmenter la complexité de la tâche des cryptanalyses, ACEO applique m
perturbations [
ACEO utilise OX « Order Cross-over » comme opérateur de croisement. Il
consiste à générer des descendants en trois phases avec un taux de 60% à 100% [
Le processus de chiffrement permet de générer une clé dite clé de session et qui
varie d’un message à un autre [
Dans l’ACEO2 nous présentons une proposition d’extension de l’algorithme de chiffrement évolutionnaire ACEO pour pouvoir d’un coté traiter des messages qui utilisent d’autres langues. D’un autre coté, pour augmenter la confusion, en compliquant ainsi la tâche des cryptanalystes, l’augmentation de l’espace de recherche semble être une solution adéquate. Mais dans ce cas on risque d’avoir une augmentation considérable du temps de calcul. Donc, on propose l’utilisation du modèle en Îlots comme solution pour pouvoir paralléliser le processus de chiffrement évolutionnaire.
Dans l’opération de codage, on calcule le nombre d’occurrence Oi pour chaque
caractère Ci du texte à chiffrer, puis on met ces derniers dans une table (TCAR) [
Oi
Gène i O1
O2
O3 …… .…………
Oi+1
O207 Gène1 Gène 207
Après l’opération du codage, une population initiale est crée par l’application de
plusieurs perturbations sur le résultat du codage. Ce dernier change d’une
instanciation du problème à une autre [
207 F(Ii)= O ji O j 0
j 1 Avec Ii= [O1, O2, …, O207] et Oji est le Jème gène d ième individu,
Et pour éviter le problème de convergence prématurée on a adopté une sélection aléatoire. 3.3
Pour trouver plus de solutions optimisées dans une courte durée de calcul, la parallèlisation semble une solution indispensable du fait qu’elle réduit le temps de traitement nécessaire pour trouver des solutions acceptables. Ceci est assuré par l’implémentation des AEs sur des architectures parallèles.
Dans la théorie d’équilibre d’évolution proposée par Sewall Wright [
Il exist plusieurs modèles pour implémenter une parallèlisation d’un AE.
L’ACEO2 utilise le modèle en îlots présentant des caractéristiques importante du fait
que : la population est divisée en petites sous populations. Les figures (2 et 3)
montrent les deux scénarios choisis par l’ACEO2, et l’introduction d’un opérateur de
migration [
Dans le modèle de parallélisation adopté (modèle en ilôts), chaque sous population évolue indépendamment des autres. Une étape dite de migration est rattachée au processus. Elle consiste à envoyer les meilleurs individus vers une sous population voisine ou bien vers un pool commun ce qui donne lieu à des coûts relatifs de communications pendant la migration.
Cette conception peut être implémentée même si des machines parallèles ne sont pas disponibles. On peut faire une simulation avec un réseau de station de travail ou avec une seule machine.
Sous Population
Sous Population
Sous Population
Sous
Population
Fig. 2. Structure de connexions pour 4 sous-populations
Sous Population
Sous Population
Sous Population
Sous Population
Sous Population
Sous Population
Sous Population
Sous Population
Sous Population
Sous
Population
Les différents algorithmes de chiffrement présentés dans cet article font partie de la
classe symétrique. Leurs caractères aléatoires et le codage n’utilisent que des
informations peu utiles , en plus du fait que le texte chiffré peut contenir des
caractères qui ne figurent pas dans le texte en clair ; toutes ces caractéristiques
rendent cette nouvelle classe, dite évolutionniste, très puissante contre plusieurs types
d’attaques. Ces algorithmes utilisent, aussi, une clé de session générée pendant le
processus de chiffrement, cette clé est fortement dépendante du message à chiffrer.
Dans le SEC par exemple, le message à chiffrer contient au moins 30 caractères
différents ce qui nous ramène à une clé de 240 bits, le même principe est suivi par le
SEC-EX. Dans l’ACEO, une clé est de taille égale à 1192 bits vu que le message à
chiffrer peut contenir 149 caractères différents. Ceci le rend plus dur contre les
attaques exhaustives, mais cela rend le processus de chiffrement plus coûteux en
temps de calcul. Pour pallier à ce problème, l’ACEO2 applique le modèle de
parallèlisation en îlots (voir 3.3) qui a prouvé son efficacité avec plusieurs problèmes
[
Ce travail présente une conception d’une extension d’un algorithme de chiffrement évolutionnaire qui a prouvé sa réussite par rapport à d’autres algorithmes appartenant à la même classe. Cette conception est basée sur l’enrichissement de l’espace de recherche et l’application d’un modèle efficace pour paralléliser des processus évolutionnaires.