Le chaos dans la cryptographie

Après une longue absence, je reviens pour vous parler d’un sujet récent, la cryptographie chaotique.

En effet, la cryptographie actuelle, en particulier RSA et DES souffrent de la monté de la puissance de calculs des ordinateurs, et l’arrivée de l’ordinateur quantique pourrait bien sonner le glas de ces algorithmes. Pour remédier, et surtout trouver un remplacent, 2 pistes intéressent les chercheurs actuellement :

- La cryptographie Quantique ( Que je n’aborderais pas ici )

-La cryptographie Chaotique ( Qui est le sujet principal de cet article )

La cryptographie chaotique repose sur l’utilisation, comme son nom ne l’indique pas, du chaos. Mais on parle ici du chaos au sens physique du terme, décrit par la théorie du chaos, s’intéressant à des systèmes déterministes mais avec une forte sensibilité aux conditions initiales.
Le jeu de billard en est un exemple. En effet, il est aisément concevable que l’on ne pourra pas renvoyer une bille exactement d’où elle vient, il faudrait qu’elle soit renvoyée avec exactement la même force, le même angle. En supposant que ces deux conditions soient remplies, il n’est pas dit que les bandes du billard réagissent de manière identique. Les conditions initiales vont donc jouer un rôle déterminant dans l’évolution de la bille.

L’étude de cette théorie est relativement récente, et a intéressé/intéresse les militaires, ne permettant à la recherche civile de ne s’y intéresser que récemment…

Le principe de la cryptographie chaotique est de noyer le message à transmettre dans un chaos et de l’envoyer à un récepteur qui connait les caractéristiques du générateur de chaos, qui pourra donc soustraire le chaos au signal reçu et ainsi en extraire le message.

Des implémentations physiques sont à l’étude, comme l’explique cet article de tout-pour-la-science et l’illustre le projet OCCULT .

Je vais dans cet article vous présenter la méthode générale ( numérique ), puis les améliorations possible grâce à la méthode de Baptista ( pas le catcheur hein :) ) et de Wang. Je présenterais ensuite quelques attaques de cryptanalyse et comment le chiffrement chaotique y répond. Il faut être bien conscient que c’est une lutte dans le temps, et que les deux camps font des avancer à des vitesses impressionnantes ( grâce notamment aux avancés récentes de la théorie des nombres ). Les réponses actuelles seront donc peut-être dépassé d’ici à quelques années. Peut-être, voir même très surement.


Prenons la suite défini par la relation de récurrence Xn+1 = Xn * k * (1 – Xn), avec X0 dans [0,1].

Prenons par exemple X0 = 0,2 et k = 2. La suite a cette allure :

courbeK2Mais si l’on prend k=3.6 :

courbeK36Et l’on aperçoit ici un comportement chaotique. Nous allons donc prendre cette suite comme base de notre chiffre.

Fixons ses conditions initales : X0 = 0.4362719749372

k = 3.78

Ces conditions initiales vont représenter le secret dont aura besoin la machine qui va décrypter le message.

On va ensuite définir un alphabet qui va faire correspondre nos différentes lettres à des nombres. Je vais pour cela prendre la table ASCII.

On se restreint ensuite à un intervale, ici Xmin = 0.2 et Xmax = 0.8, l’intervalle est [0.2,0.8] .

On subdivise cette intervalle en 256 intervalles différents ( correspondant aux nombre de caractères différents que l’on code ). On appellera ces intervalles S0, S1, … avec Si = [Xmin + E*i,Xmin + E*(i+1)[ et E = (Xmax - Xmin)/256 . On se défini aussi un N0 = 96 arbitraire et un Nmax = 256² = 65536

Le principe est alors le suivant :

On souhaite coder le message "Code". Ce qui correspond à 67 111 100 101 . On fait ensuite correspondre chaque intervalle Si au caractère représenté par le nombre i. Ainsi, S65 représente A.

Maintenant, on itère notre suite au moins N0 fois, et jusqu'à ce qu'on ai Xn qui appartient à S67 . Dans notre cas, on va avoir n = 406 et Xn = 0,358579557009 . On va choisir ce Xn comme étant notre nouveau X0' .

Et on itère notre suite au moins N0 fois avec cette nouvelle condition initiale, jusqu'à ce que l'on ai Xn' qui appartient à 111. On obtient n' = 563. Et on recommence l'opération pour 100 et 101.

On obtient ainsi notre message codé. Pour le décoder, il suffit de faire le travail en sens inverse : On commence par itéré 406 fois pour obtenir l'intervalle, donc le Si, donc le i et donc le caractère correspondant, puis on recommence en prenant le X406 comme X0' et en itérant 563 fois, ...

La méthode est donc simple et avec un grand niveau de sécurité, ne présentant aucun raccourci et ne dépendant que de la clé de départ ( X0 et k ).De plus, les caractères qui se répètent ne sont pas codés de la même manière ( pas d'analyse fréquentielle à priori possible ).

Un de problème est que le message "Code" sera toujours codé de la même façon avec une même clé.

On introduit donc 2 ajouts, la méthode de Baptista et la méthode de Wang. La méthode de Baptista consiste à choisir un l dans [0,1[ et à généré à chaque fois que l'intervalle Si désiré est atteint,un nombre K pseudo aléatoire. Si K > l, on s'arrête, sinon on continue à itérer jusqu'à retomber de nouveau dans l'intervalle Si. On recommence alors l'opération.

Bien entendu, plus l est grand, plus le temps de calcul est important. Il devient déraisonnable à partir de 0.95 environ. Un bon choix est l = 0.8, car la courbe du temps nécéssaire pour coder en fonction de l est linéaire jusqu'à 0.8 . Elle devient ensuite exponentielle.

Un avantage de cette méthode est qu'elle est assez facile à implémenter et que le décrypteur n'a pas à être changé.

La méthode Wang, elle, consiste à choisir à chaque caractère un R pseudo-aléatoire dans [0,Rmax], puis de faire R itérations avant de prendre le nouveau X0′. Donc si il faut 406 itérations pour atteindre S67, on va en faire R2 de plus, et démarré avec X0′ = X(67 + R2) . On transmettra ensuite R1 +406, R2 + 563, …

La méthode reste viable pour Rmax < 60000. Elle présente les mêmes avantages que la méthode Baptista.

Parlons maintenant des attaques sur cet algorithme. La première, la plus connue surement, le Brute Force, c’est à dire tester toutes les possibilités pour la clé, et faire derrière une analyse pour vérifier si le texte est intelligible. Cette méthode à très peu de chance d’aboutir en un temps raisonnable pour la cryptographie chaotique, grâce en particulier à la sensibilité aux conditions initiales ( modifier X0 de 0.00000000000000001 suffit à complètement changé le code en sortie !).

Une deuxième attaque envisageable est une Memory attack, qui va consister à prendre les lettres les plus répandus, et à créer une base de donnée qui va recenser les divers codes possibles, avec leur correspondance pour la clé. Une telle base permet d’obtenir des taux de réussite pouvant aller jusqu’à 60% en considérant les lettres « e », »t », »a », »o », »i », »n », »s », »r » , puisque dépendante (la réussite) de la première lettre.

Une bonne manière de s’en prémunir est de faire en sorte que la base devienne énorme, grâce à une méthode comme celle de Baptista, ou encore de modifier l’alphabet pour coder directement des doublets de lettres au lieu de lettre simple ( alphabet de 256*256 caractères ), ce qui ralenti les calculs mais permet d’augmenter la sécurité.

Une étude de 2007 [SETIT 07] à montré que la méthode de Baptista, même avec un coefficient de 0.99, reste vulnérable à une attaque de texte clair choisi ( décrite dans le document ) si le message est suffisamment long, comme c’est le cas par exemple pour une image. Mais la possibilité réelle de cette attaque reste limité. Néanmoins, l’auteur propose l’amélioration suivante : l’introduction d’une fonction f(X) discrète, qui donnera une valeur pseudo-aléatoire qui pourra être rajouter au code de sortie.

D’autre amélioration sont à l’étude, et paraissent les unes après les autres.Et comme la puissance d’un outil de chiffrement dépend aussi de sa vitesse de d’encryption ou encore de la facilité de son implémentation, beaucoup de domaine sont concernés. On pourra citer par exemple l’idée de passer d’un code de bloc de 8 bits à un bloc de 4 bits, ce qui peut permettre d’aller jusqu’à 12 fois plus rapidement dans l’encryption d’un fichier texte. On pourra aussi citer les différentes tentatives d’implémentations, comme le projet déjà cité OCCULT, et la possible industrialisation du procédé grâce au projet INTOCCULT.

En somme, je pense qu’il va être intéressant de suivre les actualités sur ce sujet, et la bataille que vont se livrer, que se livre déjà même, les cryptanalystes et les cryptologues :).

Pour vos tests personnels, je vous mets un bout de code python qui simule le chiffrement et le déchiffrement par la méthode générale ainsi que par la méthode Baptista. Je vous conseille d’observer à quel point le système est sensible aux conditions initiales, c’est édifiant !

#! usr/bin/python
import string,math,random
#Conditions initiales :
X0 = 0.358579557009
k = 3.78
N0,Nmax = 96,256*256
n = 0.8

eps,Xmin,Xmax = 0.6/(256), 0.2, 0.8
Message= "Hello World!"

def crypt(entre,baptista = False):
 global X0,k,N0,Nmax,eps,Xmin,Xmax,n
 sortie,X1 = "",X0

 for j in range(0,len(entre)):
 if(baptista):
 r,i = 0,0
 while(r<=n):
 X1 = k*X1*(1-X1)
 i += 1
 while(((X1< Xmin + ord(entre[j])*eps ) or (X1>= Xmin + (ord(entre[j]) + 1)*eps)) or i<N0):
 X1 = k*X1*(1-X1)
 i += 1
 r = random.random()
 sortie += str(i) + ' '
 else:
 i=0
 while(i<Nmax and ((X1< Xmin + ord(entre[j])*eps ) or (X1>= Xmin + (ord(entre[j]) + 1)*eps)) or i<N0):
 X1 = k*X1*(1-X1)
 i += 1
 sortie += str(i) + ' '
 return sortie

def decrypt(entree):
 global X0,k,N0,Nmax,eps,Xmin,Xmax
 sortie,X1,entre = "",X0,entree.split(' ')

 for j in range(0,len(entre)-1):
 for i in xrange(int(entre[j])):
 X1 = k*X1*(1-X1)
 sortie += chr(int(math.floor((X1-0.2)/eps)))
 return sortie

encrypt =  crypt(Message,True)
print encrypt, decrypt(encrypt)
Bibliographie/Webographie :
http://www.hkstar.com/~hmk409/research/ces/research/200107/project.htm
SETIT2007 : Analyse De Sécurité d’une Nouvelle Méthode De
Cryptage Chaotique
Nada REBHI, Mohamed Amine BEN FARAH, Abdennaceur KACHOURI &
Mounir SAMET
Tout pour la sciencehttp://www.tout-pour-la-science.com/2284/S%E9curisation+de+l%27information+:+le+cryptage+par+le+chaos.html
Illustrastion Verhlust Henon
Spyworld-actu : http://www.spyworld-actu.com/spip.php?article1214

6 réflexions au sujet de « Le chaos dans la cryptographie »

  1. Ping : “Nouveaux” types de cryptographie | Veille technologique en TIC par les étudiants de l'option informatique à Centrale Nantes

  2. tres bn explication
    mé je voudrais savoir s il y a une article comme celle ci pour la transformation de gAUSS basé sur Baptista é merci :)

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Vous pouvez utiliser ces balises et attributs HTML : <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>