Chaos Crypto-Système basé sur l'Attracteur de Hénon-Lozi A. ALI-PACHA1, N. HADJ-SAID1, A. M’HAMED2, A. BELGHORAF1 1 Université des Sciences et de la Technologie d’Oran USTO BP 1505 El M’Naouer Oran 31036 ALGERIE Phone / Fax : 213 / 041- 46 26 85 2 Institut National des Télécommunications, Evry France E.Mail : alipacha@yahoo.com Résume: constitue l’un des outils les plus performants permettant d’assurer la quasi-totalité des services de La cryptologie, véritable science régissant le codage sécurité. de l'information, a connu une réelle explosion avec le développement des systèmes informatiques, passant La cryptologie est à la fois une science, un art et un d'une ère artisanale et confidentielle à des systèmes de champ d’innovation et de recherche. Deux très hautes technologies nécessitant une importante alternatives ont alors été développées durant les puissance de calcul. Elle a connu un plus large essor dernières années : la cryptographie quantique et la encore avec l'arrivée des systèmes de cryptographie chaotique. communications modernes (Internet, etc...) où il y a La première résout de manière radicale le problème de une nécessité absolue de protéger les données la confidentialité puisque par principe, elle offre une échangées des individus. clé incassable (lié au principe d’incertitude Depuis quelques années, les chercheurs s'intéressent à d’Heisenberg), mais son débit est très limité (de la possibilité d'utiliser des signaux chaotiques dans les l’ordre de quelques dizaines de kbits/s) et son coût de systèmes de transmission de données, en particulier mise en uvre reste très élevé. pour transmettre des quantités importantes La cryptographie par chaos, quant à elle, a déjà donné d’informations sécurisées. L'intérêt d'utiliser des la preuve de sa faisabilité et de sa puissance de signaux chaotiques réside dans deux propriétés du chiffrage (supérieur à 1 Gbits/s). Le chiffrement d’un chaos : message par le chaos s’effectue donc en superposant à Un signal chaotique est un signal à large spectre et l’information initiale un signal chaotique. On envoie permet donc de transmettre des signaux très variés, par la suite le message noyé dans le chaos à un d'autre part, un signal chaotique est obtenu à partir récepteur qui lui connaît les caractéristiques du d'un système déterministe, il est donc possible de le générateur de chaos. Il ne reste alors plus au reconstituer en se plaçant dans les mêmes conditions destinataire qu’à soustraire le chaos de son message que celles qui ont contribué à le créer et, ainsi, de pour retrouver l’information, autrement dit son récupérer l'information de départ. principe de fonctionnement est le même que celui du Dans cette communication on essaye de mettre chiffrement continue (stream cipher). certains concepts de la théorie du chaos à la disposition du chiffrement continue en particulier 2. Théorie du Chaos l’attracteur de Hénon-Lozi, des données (textes et images fixes) seront cryptées pour valider le Il n’est pas rare d’entendre quelqu’un qualifier une chiffrement. situation de chaotique. Cette qualification porte par nature l’idée que cette situation relève du désordre ou Mots Clés: Cryptographies; Chiffrement Continue, de la plus grande confusion. Les phénomènes dans Chaos; attracteur, Générateur, Hénon Lozi lesquels on ne pouvait déceler à priori aucune logique 1. Introduction ont progressivement été regroupés sous le terme de "chaos" [5, 6, 7]. Assurer un échange d’informations rapide, fiable et authentique, tel fut parmi les préoccupations majeures Il n’existe pas de définition rigoureuse du chaos mais de l’humanité depuis bien plusieurs dizaines, voire par chaos, il faut admettre la notion de "phénomène même des centaines d’années. Cet aspect devient de imprévisible et erratique". Cependant, depuis une plus en plus accentuer avec l’apparition du réseau. vingtaine d’années, on attribue le terme chaos à des L’échange quasi instantané de milliers d’octets "comportements erratiques qui sont liés à des pouvant contenir différents types d’informations, systèmes simples pouvant être régis par un petit parfois cruciales, rend la protection de la nombre de variables entre lesquelles les relations communication et de l’échange d’informations d’une décrivant leur évolution peuvent être écrites. Ces importance capitale. systèmes sont donc déterministes bien La confidentialité du message, son intégrité et son qu’imprévisibles. authenticité, constitue généralement les La théorie du chaos, déjà entrevue par Jacques caractéristiques fondamentales d’une communication Hadamard et Henri Poincaré au début du XXe siècle, a sûre. La technique de cryptage ou de chiffrement, été définie à partir des années 1960 par de nombreux à temps discret : scientifiques. Xn+1 = T(Xn, Λ) où On appelle chaotiques des phénomènes complexes, dépendant de plusieurs paramètres et caractérisés par Xn ∈ IRp (p >1), n est un entier naturel, une extrême sensibilité aux conditions initiales : par X0 est la condition initiale et Λ le vecteur de exemple, les volutes décrites par la fumée d'une paramètres de la récurrence. Le débat entre modèle cigarette, ou la trajectoire d'un ballon qui se dégonfle. discret et modèle continu n’est pas aussi anodin qu’on Ces courbes ne sont pas déterminées, modélisées par pourrait le croire. Dans le cas continu (équations des systèmes d'équations linéaires ni par les lois de la différentielles), il faut un minimum de 3 équations mécanique classique; pourtant, elles ne sont pas autonomes pour faire apparaître un comportement nécessairement aléatoires, relevant du seul calcul des chaotique. Par contre, un modèle discret peut générer probabilités : elles sont liées au chaos dit déterministe. du chaos à partir d’une seule équation. Dans la suite L'imprédictibilité est présente dans de tels systèmes, de cette communication nous ne considérerons que qui n'en sont pas moins munis d'un ordre sous-jacent. les systèmes à temps discrets : attracteur de Hénon- Les signaux chaotiques peuvent être obtenus à partir Lozi. de circuits non linéaires où interviennent des paramètres. 2.2 Attracteur Géométriquement, ces phénomènes dynamiques sont Si l’on observe l’ensemble des différents états représentés dans un espace dont la dimension, qui peut successifs de l’espace d’état, on peut observer être supérieure à celle de l'espace à trois dimensions, l’émergence d’une trajectoire dans cet espace. Cette dépend du nombre de paramètres choisis pour les trajectoire est également appelée orbite du système. Il décrire. À chaque instant, l'état du phénomène est est à noter que si les variables d’état prennent des représenté par un point dans cet espace appelé espace valeurs réelles, l’orbite d’un système dynamique à des phases. L'évolution du système est décrite par la temps continu sera une courbe alors que l’orbite d’un trajectoire de ce point. Pour les phénomènes les plus système dynamique discret sera représentée par une simples, ce point est attiré vers un point d'équilibre ou série de points. une courbe limite, près desquels il repasse périodiquement. Les mathématiciens appellent ces L’attracteur est une limite vers laquelle semblent courbes limites des attracteurs étranges. convergé les orbites du système. On peut définir un attracteur comme un ensemble compact de l’espace 2.1 Système Dynamique Non Linéaire d’état vers lequel toutes les trajectoires environnantes Un système dynamique consiste en un espace de convergent c’est à dire que l’attracteur décrit en fait phase abstrait ou un espace d’état dont les une situation de régime telle qu’elle peut apparaître coordonnées décrivent l’état dynamique du système à après disparition des phénomènes transitoires. Le n’importe quel moment et dont une règle dynamique bassin d’attraction est alors l’ensemble des points spécifie la tendance future immédiate de toutes les initiaux dont les trajectoires convergent vers variables d’état composant le système, donnée par la l’attracteur : attracteur étrange. valeur présente de ces mêmes variables d’état. Une des découvertes les plus spectaculaires des Mathématiquement, un système dynamique est décrit dernières années a été celle des attracteurs étranges, par un problème où seules sont données les valeurs de ces objets géométriques issus de l'évolution de départ des variables d’état. Il peut avoir une systèmes chaotiques. Dans le plan, ils sont formés composante de temps "discrète" ou "continue". d'une suite infinie de points : x0, x1, x2, x3 ... , xn , ... Une classe importante de phénomènes naturels peut être décrite par un ensemble de p équations Qui dépendent de xo la valeur initiale. Au fur et à différentielles ordinaires du premier ordre du type: mesure que le nombre de points augmente, une image se forme dans le plan et devient de plus en plus nette d X i (t ) = Fi ( X j (t ), Λ ) Avec (figure 3). Cette image n'est pas une courbe ni une dt surface, c'est en fait un objet intermédiaire constitué X∈IRp, p≥1eti, j =1,..,p. de points avec entre eux des espaces inoccupés. L'objet est qualifié d'étrange en raison de sa structure pointilliste et de sa nature fractale. Une valeur p représente la dimension du système. La fonction F différente de xo conduit à une toute autre suite qui dépend des variables du système et du vecteur de après une courte phase, dessine la même image. paramètres Λ qui conditionne le comportement du • D'où qu'on parte, on se retrouve toujours sur système. Si F ne dépend pas explicitement du temps, l'attracteur, c'est le côté prévisible de mais seulement de X, le système est dit autonome. l'évolution. Mais on peut également rendre compte de l’évolution d’un système dynamique au moyen d’une application • Où se retrouve-t-on exactement sur l'attracteur? Il est impossible de répondre à la question, c'est le côté imprévisible de l'évolution. On appelle attracteur cette forme (figure 3) qui apparaît de façon répétitive, indépendamment des conditions initiales ou des trajectoires. Les attracteurs étranges constituent ce que l’on appelle le chaos. Les trajectoires dans l’attracteur étranges ne doivent pas se couper. Cette propriété est très intéressante et sera exploitée dans le cadre de la cryptographie. Il est à noter qu’un attracteur chaotique n’occupe pas forcément un volume fini de l’espace d’état. Figure 1: xn+1 = x(n+1) = 1+y(n) a * |(x(n))| 2.3 Sensibilité aux Conditions initiales La sensibilité aux conditions initiales (S.C.I) est une caractéristique fondamentale des systèmes dynamiques. Il faut entendre ici qu’un système réagira de façon totalement différente selon la condition initiale. Ceci a notamment comme conséquence le fait qu’un système chaotique, même si toutes ses imprévisible car sensible à d’infimes perturbations initiales. Attracteurs étranges et chaos ont permis de mieux comprendre des phénomènes comme l'apparition de la turbulence en hydrodynamique, les perturbations Figure 2:: yn+1 = y(n+1) = b * x(n) orbitales dans le système solaire, et la météorologie, qui permet de bien illustrer la dépendance sensitive des conditions initiales, comme l'a fait Edward Lorenz dans sa célèbre remarque que «le battement des ailes d'un papillon aura pour effet après quelque temps de changer complètement l'état de l'atmosphère terrestre». 3. L’Attracteur de Hénon Lozi L’attracteur est défini par le système d’équations suivant, ou a et b sont des constantes : = bX(n+1) = 1 + Y(n) – a * X(n)  Y(n+1) = b* X(n) Figure 3. : L’attracteur de Hénon Lozi 4. Chiffrement continue Si on programme ces formules avec Matlab on aura Le système de chiffrement continue consiste à le graphe de la figure 3 avec 50.000 points avec les valeurs suivantes a = 1.7; b = 0.5 on aura ce graphe : produire [10] une suite chiffrante qui est le résultat de l’addition bit à bit du texte clair à la suite pseudo aléatoire (appelé codon). L’un des exemples les plus connus de chiffrement à flot est le système A5 utilisé N X (n) Y (n) N X (n) Y (n) par GSM, l’algorithme est utilisé pour chiffrer la 0 0 0 8 -0,198 0,2719 communication entre le mobile et la borne reliée au 1 1 0 9 0,936 -0,099 réseau. C’est un système relativement simple pour 2 -0,7 0,5 10 -0,689 0,468 protéger raisonnablement la communication sur le 3 0,31 -0,35 11 0,297 -0,345 trajet aérien. 4 0,123 0,155 12 0,153 0,148 Les algorithmes de chiffrement en continu 0,946 0,062 0,888 0,076 convertissent la donnée à chiffré 1 bit à la fois. La 5 13 réalisation la plus simple d’un algorithme de 6 -0,546 0,473 14 -0,434 0,444 chiffrement en continu est illustrée par la figure 4. 7 0,544 -0,273 15 0,706 -0,217 Tableau 1 : valeurs X,Y, 4.2 Champs formant la clé de chiffrement Dans ce qui suit on remplace le générateur RDRL par l’attracteur chaotique. Le choix de la clé de chiffrement, dans ce cas par exemple, doit être suivant : 1. le choix d’attracteur, Figure 4 Chiffrement continu 2. le travail suivant l’axes X/Y/Z , 3. le pas d’échantillonnage, et Ce type de générateur engendre un flux de bits 4. l’état initiale X0 , Y0 et Z0 . (appelons les codons) K1, K2, K3, …, Ki. Ce flux est combiné par ou exclusif avec le flux de bits du texte Nous avons crypté et décrypté nos données [7], avec en clair m1, m2, m3, …, mi pour produire le flux de la clé de chiffrement par défaut suivant : bits de donnée chiffré. • Attracteur : Hénon Lozi c i= m i⊕ k i (1) • Pas : 1 Du coté du déchiffrement, les bits de donnée • Axe : X chiffré sont combiné par ou exclusif avec un flux • On fait varier les valeurs initiales X0 et Y0. identique de codons pour retrouver les bits du texte en 5. Résultats et Interprétation : clair : Nous allons utiliser l’attracteur de Hénon Lozi pour m i = c i⊕ k i = (m i⊕ k i)⊕ k i = m i (2) crypter nos données. Le principe du chiffrement continu sera utilisé, les valeurs de X (tableau 2) 4.1 Générateur Pseudo aléatoire : RDRL seront converti en binaires pour être combiné avec les Le chiffrement à flot [3, 9] qui existe actuellement n-bits de données a crypté (figure 5). est généré par un générateur pseudo-aléatoire RDRL (Registre à Décalage à Rétroaction Linéaire) qui produit une suite de longueur connue, de zéros et de uns logiques. Il est dit aléatoire car cette suite est arbitraire. Cependant, lorsque la suite arrive à son terme, le générateur ne s'arrête pas de fonctionner. La séquence déjà transmise est à nouveau reproduite (générateur périodique). D'où le qualificatif de pseudo-aléatoire. Le principal intérêt de l’étude des Générateurs Pseudo-Aléatoires de Suites Crypto- graphiquement Surs GPASCS est qu’ils sont parfaits ⊕ pour le chiffrement en continu. Leur construction se fait en tenant compte de: Figure 5a: Courbe de l’image en claire 1. Longue période, 2. Pas de répétitions, 3. Complexité linéaire locale 4. Critères de non linéarité pour des fonctions booléennes. La clé de chiffrement est la même que celle du déchiffrement (chiffrement symétrique).l’état t initial du registre est la clé de chiffrement. Dans certain cas, la cryptanalyse peut se baser sur la répétitivité du signal transmis car les algorithmes de cryptage sont Figure 5b: Courbe de données des suites de nombres pseudo aléatoires. Il est alors possible de reconstruire la clé à partir du signal crypté. Pour éviter ce type de faille, il faut donc que la clé ait une dimension suffisamment complexe pour que même à long terme, on ne puisse pas remonter au code. Le principe serait alors de se servir d’un bruit aléatoire évoluant dans le temps dont on connaît les caractéristiques en guise de clé. Figure 5c: Courbe de l’image cryptée N° X X Décimal x normalise Arrondi r 0 0 17,583 18 1 0 17,583 18 2 1 18,583 19 3 -6,4833 11,1 11 4 9,27 26,853 27 5 2,6958 20,279 20 6 -15,285 2,2974 2 7 9,3106 26,893 27 (X0= 2, Y0= 2.5 ) 8 11,515 29,098 29 9 -12,044 5,5386 6 10 -0,11417 17,469 17 11 20,82 38,403 38 12 -3,7106 13,872 14 13 -11,168 6,4144 6 14 14,942 32,525 33 15 11,685 29,268 29 16 -17,583 0 0 17 0,73095 18,314 18 (X0= 0.02, Y0=0.02 ) 18 11,028 28,611 29 5.2 Texte 19 -3,7169 13,866 14 20 16,207 16 Le principe utilisé pour le cryptage d’image est utilisé -1,3754 dans le cryptage du texte, l’attracteur c’est l’attracteur 21 12,81 30,393 30 de Hénon Lozi avec un pas de 0.005. 22 -0,58418 16,999 17 23 -3,9149 13,668 14 Chiffrement Clé par défaut avec 24 10,282 27,865 28 25 0,57087 18,154 18 Texte en claire : X0 = 1, Y0 = X 0 = 0.2, Y0 = 26 -16,88 0,70333 1 1 2.5 27 11,722 29,304 29 la cryptologie a • t>DSjaznj ~m4hcwfm`}e 28 14,258 31,841 32 connu une rapide ~zuu2r?KO| tgq(a!k{`z|!ufp 29 -12,444 5,1389 5 évolution à notre |z - 30 -2,7808 14,802 15 époque surtout en s|x;cuasyw `jcepo1/9 dcx 31 21,877 39,46 39 ce qui concerne ces % • dyv{. *|abjj Tableau 2 : des Valeurs de X utilisé pour le cryptage deux facteurs / uibkivsp/ 1àcadlu0ya• g "ctyp`/÷lq dfy4)! 5.1 Image lkk%pxh qe2np(qt`4n|gr {|fj 20~u uk{k3jw|8rkgr 2de.`fI |||s 3jrifk`k| ~o~`!mua L{fk/|l`pkk om Le besoin de Nd"bdsmio! Od"bgsnhl communications fe!bnomtoh ee"cnlouohbct sécurisées a donné ccthn hno naissance à une or"sëctsksè r!sëctshrègs!`! nouvelle science dr!cenolé!n enlné!lahsraob Emir Abdelkader mosquée que nous appelons `iqs`oae!?!t g á!tod cryptologie.. od"nnutem lotwdmm On voit que si on change les valeurs des conditions mgrchdlcd! d!qcheobg initiales le résultat est changé, il est clair que le choix ptd"nour!cp ptd!omus des valeurs initiales sont importantes comme dans re `qremnor!aryq exemples, les images chiffrées ci-dessous sont mnls!bsyrtn unnoghd. brouillées. mnfke/ [02] http://math.cmaisonneuve.qc.ca/alevesque chaos_fract/Galerie/Galerie.html On voit que si on change les valeurs des conditions initiales le résultat est changé. [03] S. H. Strogatz, Nonlinear Systems and Chaos, Perseus publishing 1994. 6. Conclusion : [04] L’utilisation du chaos dans les télécommunications http://www.astrosurf.com/cieldaunis/chaos/resum est étudiée depuis plusieurs années. Le chaos est ons.html obtenu à partir de systèmes non linéaires; il [ 05] J. GLEICK ‘chaos theory’, Albin Michel 1989. correspond à un comportement borné, de ces systèmes, ce qui le fait apparaître comme du bruit [06 pseudo aléatoire. Il peut donc être utilisé pour ] A. Ali-Pacha A, N. Hadj-Said, B. Belmekki, A. masquer ou mélanger les informations dans une Belghoraf, «Chaotic Behaviour for the Secrete transmission sécurisée. key of Cryptographic System», Revue Elsevier L’originalité de cette communication repose sur la Science : Chaos, Solitons & Fractals, Volume prise en compte des propriétés de signaux chaotiques 23/5 pp. 1549-1552. Available online October issue soit d’équations différentielles soit de 2004. récurrences discrètes non linéaire. Nous avons pris comme exemple l’attracteur de [07] A. Ali-Pacha, N. Hadj-Said, A. M”Hamed, A. Hénon Lozi dans le cas des équations discrètes non Belghoraf, «Lorenz’s Attractor Applied to the linéaires, les résultats de chiffrement sont Stream Cipher (Ali-Pacha Generator)», Revue satisfaisants. La sécurité de ce principe réside dans Elsevier Science : Chaos, Solitons & Fractals, l’impossibilité de connaître la clé secrète du ce Volume 33/5 pp.1762-1766. Available online système chaotique crypto système qui est fonction du August 2007. nom de l’attracteur utilisé en plus de l’état initiale et [08] ] http://just.loic.free.fr/chaos/ de pas d’échantillonnage. Aussi, il faut noter que les attaques utilise contre se [09] type d’algorithmes sont les mêmes que celles utilise http://math.cmaisonneuve.qc.ca/alevesque/chaos_ pour le chiffrement continue sauf que dans notre cas, fract/chaos/chaos.html nous avons ajouté d’autres contraintes aux [10] B. Schneier,'' Applied Cryptography-Protocols, cryptanalyses. Algorithms and Source Code in C'', John Wiley & Bibliographies : Sounds, Inc, New York, Second Edition, 1996. [01]http://www.astrosurf.com/luxorion/chaos-inerte- vivant.htm