1 \chapter{Notions générales}
2 \label{Notions générales}
5 Ce chapitre, faisant office de fondations pour cette thèse, introduit la terminologie et les notations utilisés dans le domaine des générateurs de nombres pseudo-aléatoires.
8 Une suite aléatoire de bits peut s’interpréter comme le résultat de lancers d’une pièce équilibrée (non-biaisée). On assimiler "Pile" à "0" et "face" à "1", et l’on suppose que chaque lancer a une probabilité $1/2$ exactement de produire un "0", et parcellement pour "1". On suppose de plus que les lancers sont indépendants les uns des autres: le résultat n’importe quel précédent lancer n’affecte pas les lancers à venir. La pièce sans biais et équitable est alors l’image d’un générateur aléatoire de bits parfait, puisque les " 0 " et "1" seront aléatoirement distribués. Tous les éléments de la suite sont générés indépendamment les uns des autres, et la valeur de l'élément suivant dans la suite ne peut être prédite à partir de la suite des nombres déjà obtenus, et ce quelle que soit la grandeur de cette suite~\cite{Deborah1998,Kallenberg1986}. Cependant, clairement, l'utilisation de pièces non biaisées à des fins cryptographiques est impraticable en pratique. Quai qu’il en soit, la sortie hypothétique d'un tel générateur idéal de suites réellement aléatoire sert de critère de comparaison (benchmark) pour l'évaluation des générateurs de nombres aléatoires et pseudo aléatoires~\cite{ANDREW2008}.
10 \section{Différents types de générateurs de nombres aléatoires (RNG)}
11 Un RNG est un composant informatique ou physique, assemblé pour produire une suite de nombres ou de symboles qui semble aléatoires~\cite{William2007}.
14 Générer une bonne suite aléatoires est une tâche difficile. On peut bien évidemment obtenir une telle suite à partir d’un lancer de clés ou d’une pièce de monnaie, un tel procède mécanique n’est, on l’a dit, pas pratique. Il y a quelques temps de cela, les nombres aléatoires étaient générés à partir et tabulées en utilisant par exemple les procèdes mécaniques évoqués ci-dessus. Ces tables prêtes à l'emploi peuvent encore se trouver sur le web ou sur des CDs de données dédiés.
17 Cependant, du fait des besoins liés à Internet et aux problèmes de sécurité soulevés par cette approche, ces tables~\cite{Tippett1927} ne permettent plus de satisfaire les besoins en nombres aléatoires. C’est pourquoi de nouveaux types de RNG ont été introduits, notamment depuis l’apparition de l’informatique.
20 Les RNG sont traditionnellement regroupés en deux classes, suivant leur source d’aléas: les générateurs de nombres vraiment aléatoires et les générateurs de nombres pseudo aléatoires.
21 \subsection{ Les générateurs de nombres vraiment aléatoires (TRNGs)}
22 Un TRNG est un générateur produisant des bits statistiquement indépendants et sans biais. Ils s’agit de RNG non déterministes. En informatique, un TRNG est un appareil produisant des nombres aléatoires à partir d'un processus physique~\cite{Pashley2010184}. De tels composants se basent souvent sur des phénomènes microscopiques génèrent un signal de bas niveau, un bruit statistiquement aléatoire. Les phénomènes peuvent être un "bruit thermal" utilisant les capteurs de température de l’ordinateur, peuvent utiliser l’effet photoélectrique ou tout autre phénomène quantique~\cite{Guler2011,WT198429,Danger2009,JarosawAdam2011}. En théorie, ces processus sont complètement imprévisible s; en pratique, une telle assertion se vérifie à l’aide de batteries tests statistiques. Un tel générateur quantique de type physique, consiste typiquement en un transducteur qui convertir un certains aspects d’un phénomène physique en un signal électrique. Ce transducteur est relié à un amplificateur et d'autres composant électroniques, dont le but est de porter la sortie du transducteur de l’échelle microscopique à l’échelle macroscopique. Enfin, un convertisseur analogique vers numérique permet de transformer a signal analogique en une suite de nombres, souvent de simples bits. On obtient ainsi une suite de bits en reproduisant le procédé tant que nécessaire.
25 \subsection{ Les générateurs de nombres pseudo-aléatoires (PRNGs)}
26 Un PRNG, appelé aussi générateur déterministes de bits aléatoires (DRBG : Deterministic Random Bit Generator ) ~\cite{Barker05recommendationfor} est un algorithme générant une suite de nombres qui approximent les propriétés des nombres aléatoires. La suite n'est pas réellement aléatoire dans le sens où elle est complètement déterminée par un ensemble de valeurs initiales relativement petit, appelé l’état du PRNG. S’il est vrai que des suites proches d’un aléa pur peuvent être obtenues avec des générateurs physiques, cela ne signifie pas pour autant que les générateurs pseudo-aléatoires sont inutiles. Leur importance se matérialise lors de simulations, par exemple de systèmes physiques en utilisant la méthode de Monte Carlo. Ils sont de plus primordiaux en cryptographie et en génération procédurale~\cite{Tan20091618,StDenis200691}. Des classes bien connue de tels algorithmes sont les générateurs congruentiels linéaires~\cite{Knuth1998_1}, les Lagged Fibonacci générateurs~\cite{Knuth1998_2}, linéaire feedback shift registre~\cite{tagkey2009407}, feedback with carry shift registers~\cite{Klapper1994}, and generalised feedback shift registers~\cite{Linardatos2002157,Klapper199961,Mykkeltveit1979202,Unjeng198461}. Le Blum Blum Shub~\cite{DBLP1986}, le Fortuna~\cite{DBLP2003}, et le Mersenne Twister~\cite{Matsumoto1998} sont par exemple des instances récentes de ces classes d’algorithmes.
29 \section{ PRNGs cryptographiquement sûrs }
30 Un PRNG pouvant être utilisé en cryptographie est appelé un PRNG cryptographiquement sûr (CSPRNG). Une propriété importante que doit satisfaire un CSPRNG est qu’un adversaire, ne connaissant pas la graine, n'a qu'un avantage négligeable de pouvoir distinguer la séquence produite par le générateur d'une séquence réellement aléatoire. En d'autres termes, tandis que l’en se demande à un PRNG que de passer certains tests statistiques, un CSPRNG doit passer tous les tests statistiques ayant un temps d’ exécuter polynomial par rapport à la taille de la graine. Bien qu’une telle propriété ne peut pas être prouvée~\cite{Miller2010}, on peut cependant s’en approcher en réduisant ce problème pour un générateur à un problème NP-difficile tel que la factorisation des entiers. En général, des années d’étude sont requises avant de pouvoir certifier qu’un algorithme donné est un CSPRNG.
33 Donnons maintenant quelques classes de CSPRNGs:
36 \item les chiffrements par flot (Stream ciphers).
37 \item les chiffrements par bloc fonctionnant en mode counter ou output feedback mode.
38 \item certains PRNGs produit expressément pour être cryptographiquement sûr, tels que la fonction CryptGenRandom de Microsoft, l'algorithme Yarrow (embarqué dans le Mac OS X et dans FreeBSD), et Fortuna.
39 \item la combinaison de PRNGs telle que le PRNG résultant ne possède plus aucune trace de non-aléas.
40 \item des PRNG spécialement conçus à partir de problèmes mathématiques difficiles, tels que les algorithmes Micali-Schnorr et Blum Blum Shub. Ces algorithmes sont livrés avec des preuves de sécurité rigoureuses. En contre partie, ces CSPRNGs sont lents, voire inutilisables pour un certain nombre d’applications.
44 Le chiffrement par flot est technique cryptographique qui chiffre les bits individuellement, en utilisant une transformation qui change au cours du temps. A contrario dans un chiffrement par blocs, le clair-texte est découpé en blocs, et chaque bloc de bits est chiffré d’un coup, en simultané, la même transformation s’appliquant chacun des blocs.
47 Dans certaines applications spécifiques, les chiffrements par flots sont plus appropriés que les chiffrements par bloc ~\cite{Preneel03nessied20, Robshaw95streamciphers}:
49 \item Les chiffrements par flots sont généralement plus rapides que le chiffrements par bloc, surtout quand ces premiers sont produits au niveau matériel.
50 \item Les chiffrements par flots ont une complexité matérielle plus faible, et nécessitent moins de mémoire, et ce que ce soit au niveau hardware ou software.
51 \item Les chiffrements par flots opèrent sur le clair-texte caractère par caractère, et ainsi aucun tampon n.est nécessaire, il n’y a pas besoin d'accumuler un bloc complet du clair-texte (contrairement au chiffrement par bloc).
52 \item Les chiffrements par flots synchrones n'ont pas de propagation d’erreur~\cite{springerlink1994}.
55 \section{Le chiffrement par flot}
56 Un chiffrement par flot génère le flux de sortie (cryptogramme) à partir d’un état interne. Cet état est mis à jour, essentiellement de deux manières différentes. Dans le premier cas de figure, l’état change indépendamment du clair-texte ou du cryptogramme. On parle alors de chiffrement par flot synchrone. Par contre, dans le cas des chiffrements par flot auto-synchronisant, l’état est mis à jour à partir des derniers bits du cryptogramme calculès.
59 \subsection{Les masque jetable( One-Time Pad, ou chiffrement Vernam)}
60 Le chiffrement de Vernam est un chiffrement par flot dans lequel on applique le XORshift entre chaque bit du clair-texte et le bit correspondant d’un flux de données aléatoire ou pseudo-aléatoire, appelé le keystream, ayant la même faille que le clair-texte. Si le keystream est réellement aléatoire et utilisé une seule fois, il s’agit alors du masque jetable (One-Time Pad)
63 Shannon a montré~\cite{Shannon-OTP} que le masque jetable fournit une sécurité parfaite. Cela veut dire que l'entropie conditionnelle du message $M$ connaissant le cryptogramme $ C $, est la même que l'entropie du message d'origine : $H(M|C) = H(M)$. Shannon a aussi montré que le masque jetable est optimale : la condition précédente ne peut être obtenue avec une clé de taille plus petite que le message $M$.
66 Le problème avec le masque jetable est que l’on doit avoir une clé de la faille du message, ce qui dans la plupart des cas est impossible en pratique~\cite{PhysRevA2004}. Les deux schémas suivants tentent de produire un keystream à l’allure aléatoire à partir d’une petite clé. Par allure aléatoire, il faut comprendre que l’on ne doit pas pouvoir faire la distinction entre le keystream et une suite aléatoire, en une complexité inférieure à celle intervenant quand on tente toutes les clés possibles.
69 \subsection{ chiffrements par flots synchrones}
70 Dans un chiffrement par flot synchrone, le flux de nombres pseudo-aléatoires est produit indépendamment du clair-texte et du cryptogramme, puis est ensuite combiné soit au clair-texte à chiffrer, soit au cryptogramme à déchiffrer~\cite{cusick2004stream}.
73 Dans un chiffrement par flot synchrone, l'expéditeur et le récepteur doivent être exactement synchronisés pour que le déchiffrement puisse se faire sans encombre. Si des chiffres sont ajoutés ou enlevés du message pendant la transmission, alors la synchronisation sera perdue. Pour la restaurer, on peut effectuer différentes tentatives de déchiffrement à partir de keystream décalés jusqu’à obtenir un message intelligible. Une autre approche consiste à introduire des marqueurs dans le cryptogramme, comme autant de repères permettant une resynchronisation.
76 Si, cependant, un chiffre est corrompu durant la transmission, sans qu’il y ait décalage, alors seul un bit du clair-texte aura été affecté et l'erreur ne se propagera pas à d'autres parties du message. Cette propriété est utile quand le taux d'erreur de transmission est élevé ; mais dans ce cas les erreurs ont moins de chance d’être détectée. De plus, à cause de cette propriété, les chiffrements par flot synchrones sont fragiles face aux attaques actives : si un adversaire peut changer un bit dans le cryptogramme, alors il pourrait être en mesure de faire des changements prévisibles au niveau du clair-texte. En effet, changer un bit dans le cryptogramme entraîne le changement du bit du clair-texte situé au même endroit. provoque le même bit pour être retourné dans le texte clair~\cite{Wu2008,Daemen1994}.
79 \subsection{ chiffrements par flot auto-synchronisants}
80 Une autre approche utilise un certain nombre des $N$ derniers chiffres du cryptogramme pour calculer le keystream. De tels schémas sont aussi appelés chiffrements par flot asynchrones, ‘’cryptogramme autokey’’ (CTAK). L'idée de l’auto-synchronisation a été brevetée en 1946~\cite{schneier1996}. Elle a l'avantage que le récepteur peut auto-matiquement se synchroniser avec le générateur keystream après avoir reçu $N$ chiffres du cryptogramme, rendant ainsi facile la resynchronisation en cas d’ajout ou de perte de chiffres lors de la transmission. Des erreurs portant sur un chiffre seul seront limités dans leurs protée, affectant seulement au plus $N$ chiffres du clair-texte.
83 Un exemple de chiffrement par flot auto-synchronisation est un chiffrement par bloc en mode Cipher Feedback (CFB)~\cite{Meyer100035}.
85 \section{ Générateurs de nombres aléatoires basés sur le chaos }
86 Depuis les années 70, l'utilisation de dynamiques chaotiques pour la génération de suites aléatoires et les applications cryptographiques a soulevé beaucoup d'intérêt. De nombreux ponts entre la théorie du chaos et la cryptographie ont été établis ces deux dernières décennies qui ont conduit à de nombreux travaux de recherche~\cite{STMAZ01769371}.
89 Les dynamiques chaotiques sont habituellement étudiées dans deux différents domaines. Dans le domaine des temps continus, dans lequel ces dynamiques sont produites à partir de systèmes chaotiques issus d’équations différentielles. Dans le domaine des temps discrets, dans lequel une fonction chaotique est utilisée dans une relation de récurrence.
92 Le chaos fait référence à un certain nombre de propriétés distinctes, incluant la sensibilité aux conditions initiales, l’ergodicité et le spectre large bande, contribuant toutes au caractère imprévisible et semblant aléatoire du système considéré. Assimiler ces propriétés, ou du moins les relier, à une forme d’aléas en affirmant que les générateur basés sur du chaos, sont de bons générateurs aléatoires, même à la controverse. Toutefois il est indéniable qu’un certain nombre de ces générateurs ont été proposés dans dévases applications, notamment dans la sécurisation de communications, et avec un certain succès.
95 Il est dorénavant commun d'utiliser des fonctions chaotiques pour la génération de nombres pseudo-aléatoires. Et du fait de la Grâce à la construction récente de circuits électroniques pour la réalisation des systèmes chaotiques, il est aussi dorénavant possible de générer la suite de bits en observant de telle dynamique, apportant ainsi une méthode complémentaire pour la génération matérielle d’aléas.
98 \section{ Chaos continu dans les ordinateurs}
99 Au cours les deux dernières décennies, l'utilisation de systèmes chaotiques pour concevoir de nouveaux cryptosystèmes, des PRNG, voire des fonctions de hachage, est devenu de plus en plus fréquentes. D’une manière générale, la théorie du chaos sur des espaces continu est utilisée dans le but d’analyser les performances des systèmes considèrés.
102 Cependant, quand des systèmes chaotiques sont mis en œuvre dans des ordinateurs ayant une précision finie, il est naturel de se demander si la dynamique désirée présente dans le système continu est préservée sur la machine. En fait la plupart des propriétés de chaos n’ont de sens que quand les systèmes dynamiques évoluent sur la droite réelle, et ces propriétés peuvent perdre tout leur sens, ou tout le moins devenir ambiguës, quand l'espace sur lequel on itère est fortement quantifié, ou lorsque l’on travaille à précision finie (en d'autres termes, la dynamique chaotique d’un systèmes continu se dégrade lorsque l’en effectue des calculs à précision finie).
105 Les erreurs de quantification, qui sont introduites à chaque itération d’un système chaotique numérique, produiront des pseudo orbites qui s’éloigneront des orbites réelles d’une manière complexe et incontrôlé. Du fait de la sensibilité aux conditions initiales des systèmes chaotiques, même des changements élémentaires introduits par l'arithmétique des ordinateurs peuvent définitivement changer les structures des pseudo orbites.
108 Même si ces erreurs de quantification sont complètement déterministes quand l'arithmétique et sa précision sont fixes, il est techniquement impossible de connaître et de traiter toutes les erreurs intervenant dans les itérations numériques. Des modèles de perturbation aléatoire ont bien été proposés pour représenter les erreurs de quantification dans les systèmes chaotique numériques, mais ils ne peuvent pas prévoir exactement la dynamique réelle de systèmes dynamiques numériques étudiées, et ces modèles ont de ce fait été critiqué pour leur manque de réalité.
111 Quand des systèmes chaotiques sont mis en œuvre sur des machines à précision finie, leurs propriétés dynamiques seront profondément différentes des propriétés des systèmes à valeurs continues. Des dégradations vont apparaître, telles que l’apparition de cycles de petite longueur et des distributions decayed. Ce phénomène a été rapporté et analysé dans diverses situations~\cite{Binder1986,Wheeler1989,Palmore1990,Blank1997,Li2005}.
114 Par conclure, un système chaotique continu peut perdre ses propriétés quand on le porte sur ordinateur. C’est pourquoi, à notre sens, le meilleur moyen de concevoir un générateur de nombres pseudo-aléatoires chaotiques consiste à utiliser les itérations chaotiques.
116 \section{ Chaos pour des systèmes dynamiques discrets}
117 On considère espace métrique $(\mathcal{X},d)$ et une fonction continue $f:\mathcal{X}\longrightarrow \mathcal{X}$. Soit le systèmes dynamiques:
119 x^0 \in \mathcal{X} \textrm{ and } \forall n \in \mathds{N}^*, x^n=f(x^{n-1}),
123 La définition suivante d’un comportement chaotique, formulée par Devaney~\cite{Dev89}, est largement accepté:
126 Un système dynamique de la forme ~\ref{Devaney} est dit chaotique s’il vérifie les propriétés suivantes :
128 \item Transitivité topologique:
131 \forall U,V \textrm{ ouverts de } \mathcal{X}, ~\exists k>0, f^k(U) \cap V \neq \varnothing
133 Intuitivement, une fonction topologiquement transitive est telle que deux points aussi proches que l’om veut peuvent finir par se retrouver en des lieux complètement différents. D’autre part, le système dynamique est intrinsèquement compliqué et ne peut être décomposé en deux ouverts disjoints invariants sous les itérations de $f$. Enfin, signalons que si le système possède une orbite dense, alors il est clairement transitif.
134 \item Densité de points périodiques dans $\mathcal{X}$:
135 Soit $P=\{p\in \mathcal{X}|\exists n \in \mathds{N}^{\ast}:f^n(p)=p\}$ l'ensemble des points périodiques de $f$. Alors $P$ est dense dans $\mathcal{X}$:
137 \overline{P}=\mathcal{X}
139 Intuitivement, cette densité signifie que chaque point de l’espace est proche autant que l’on veut de points périodiques. Les systèmes transitifs ne présentant pas cette propriété peuvent ne pas être sensibles à la condition initiale, ce qui justifie en partie cette introduction d’un élément de régularité dans une définition de chaos.
140 \item Sensibilité à la condition initiale:
141 $\exists \varepsilon>0,$ $\forall x \in \mathcal{X},$ $\forall \delta >0,$ $\exists y \in \mathcal{X},$ $\exists n \in \mathbb{N},$ $d(x,y)<\delta$ and $d\left(f^n(x),f^n(y)\right) \geqslant \varepsilon.$
142 Un système donc sensible aux conditions initiales, si il existe des points arbitrairement proches de $x$ qui s’éloignent à terme d’au moins $\varepsilon$ de $x$. Tous les points voisins de $x$ ne s’éloigneront pas forcément de $\varepsilon$: il faut qu’il s’en trouve au moins un dans chaque voisinage de $x$. Si une fonction possède cette dépendance aux conditions initiales, alors pour toutes les applications pratiques, la dynamique de la fonction défie tous les calculs numériques. De petites erreurs au cours du calcul, introduites par exemple du fait des erreurs d’arrondi, peuvent devenir non négligeables au cours des itérations. Le résultat du calcul numérique d'une orbite peut n’avoir aucune ressemblance avec l'orbite originale.
146 Quand le système $(\mathcal{X}, f)$ est chaotique, on peut dire, en citant Devaney: `` il est imprévisible du fait de la dépendance aux conditions initiales. Il ne peut pas être cassé ou décomposé en deux sous-systèmes qui n'interagissent pas du fait de la transitivité topologique. Et en dépit de a comportement aléatoire, on a cependant un élément de régularité. `` Des comportements fondamentalements différents sont possibles et ils interviennent de manière imprévisible.
149 \section{ Les itérations chaotiques}
150 \label{ Les itérations chaotiques }
153 \label{Chaotic iterations}
154 L’ensemble $\mathds{B}$ désignant $\{0,1\}$, soit $f:\mathds{B}^{\mathsf{N}%
155 }\longrightarrow \mathds{B}^{\mathsf{N}}$ une ``fonction d’itération'' et $S\in \mathbb{S}
156 $ une stratégie chaotique. Les \emph{ itérations chaotiques } sont définies par~\cite{Robert1986}:
159 \left\{\begin{array}{l}
160 x^0\in \mathds{B}^{\mathsf{N}}, \\
161 \forall n\in \mathds{N}^{\ast },\forall i\in \llbracket1;\mathsf{N}\rrbracket%
165 x_i^{n-1} & \text{if}~S^n\neq i \\
166 f(x^{n-1})_{S^n} & \text{if}~S^n=i.
173 En d'autres termes, à la $n$-ième itérée, seule la $S^{n}$-ième cellule est mise à jour. Signalons que l’on peut fournir une définition plus générale, soit en considérant que $S^{n}$ est un sous-ensemble de $\llbracket 1;\mathsf{N} \rrbracket$, soit en remplaçant $f(x^{n-1})_{S^{n}}$ par $f(x^{k})_{S^{n}}$, où$k < n$, pour décrire par exemple des retards à la transmission des celleles ~\cite{Bahi2000}. Pour la définition générale de telles itérations chaotiques, on pourra se rapporter à~\cite{Robert1986}.
174 Les itérations chaotiques engendrent un ensemble de vecteurs de bits. Elles sont définies par un état initial $x^{0}$, une fonction d'itération $f$, et une stratégie chaotique $ S $.
176 Le paragraphe suivant donne l’aperçu preuve que itérations chaotiques de satisfaire la propriété de chaotique topologique par Devaney. Ainsi, ils peuvent être utilisés pour définir un nouveaux générateurs de nombres pseudo-aléatoires.
