5 Le développement, la popularité d’Internet et son rôle récent dans la vie de tous les jours conduisent au besoin de protéger nos données et notre vie privée dans notre monde devenu numérique. Un tel développement conduit à de nouveaux problèmes, cruciaux, de sécurité. Ces problèmes sont, par exemple, issus de nouvelles activités parties par Internet, telles que le vote électronique (e-Voting), la vidéo à la demande (VoD), et la gestion des droits d’auteur à l’ère du numériques ~\cite{ Zhu200675}. Les nombres pseudo-aléatoires (PRNGs : Pseudorandom number generators) jouent un rôle important dans toutes ces nouvelles technologies, car ils sont omniprésents dans les cryptosystèmes et les algorithmes de dissimulation d'information modernes.
8 Les PRNGs sont définis à partir de suites récurrentes (déterministes) définies sur un ensemble fini ‘d'état’, ayant fréquemment une structure d’anneau ou de corps, ces suites éétaient couplées avec une fonction, dont le rôle et d’envoyer chaque état sur une valeur de sortie. Cette valeur est souvent soit un nombre réel dans l'intervalle $ [0 ;1] $ , soit un entier inférieur au égal à une borne fixée ~\cite{ LEcuyer08}.
9 En fait, la suite générée n'est pas vraiment aléatoire, vu qu’elle est complètement déterminée par un ensemble relativement petit de valeurs initiales, constituant l’espace d'états du PRNG.
10 Comparé aux approches matérielles, ces PRNGs sont plus faciles à générer et reproductibles, mais sont finalement moins proche d’un aléas pur que les nombres génères par des sources matérielles. Les PRNGs sont souvent basées sur des opérations logiques telles que le ou exclusifs bit à bit (bitwise exclusive or :XOR) ou le décalage circulaire de vecteurs de bits.
11 Cependant le niveau de sécurité de certains PRNGs de ce type s’est révélé être en deçà des standards actuels.
14 Récemment, certains chercheurs ont exploré la possibilité d'utiliser des systèmes dynamiques chaotiques pour en faire des PRNGs ~\cite{Falcioni2005, Cecen2009, PO2004}.
15 Ces tentatives se basent sur l'hypothèse que les systèmes chaotiques numériques peuvent renforcer la sécurité d’algorithmes cryptographiques, car le comportement de tels systèmes dynamiques est très voisin de celui d’une source de bruit physique ~\cite{ Schuster1984}.
16 Leur sensibilité aux conditions initiale et de leur spectre comprenant toutes fréquences en font des outils intéressants dans l’écriture de générateurs pseudo-aléatoires cryptographiquement sûrs. En particulier, la dynamique imprévisible, semblable à du hazard, des systèmes chaotiques, couplée à leur déterminisme et à la simplicité, conduisent à l’idée de leur utilisation en tant que PRNGs.
19 On trouve deux grandes familles de réalisation dans la cryptographie par chaos, la première matière de concevoir de tels cryptosystèmes consiste à réaliser des circuits analogiques, en utilisant des techniques basées sur la synchronisation du chaos ~\cite{ PhysRevLett.64.821}. La seconde approche consiste à réaliser ces cryptosystèmes chaotiques à partir de circuits numériques ou d’ordinateurs, elle ne dépend pas de la technique de synchronisation évoquée ci-dessus. D’une manière générale, les cryptosystèmes chaotiques basés sur la synchronisation sont conçus pour établir des communications sécurisées sur canal de bruit; ils ne peuvent pas être directement étendus à la réalisation de chiffrement numérique. Le problème avec cette approche est qu’un certain nombre d’études cryptanalyse ont conduit à la découverte de failles de sécurité dans la plupart des cryptosystèmes chaotiques de cette espèce. Plus précisément, la plupart du temps il est possible d'extraire de l‘informations sur les paramètres sécurisé fournis au cryptosystèmes, en analysant le flux de données cryptographiques ~\cite{BethLaMa94}. C’est pourquoi, cette approche a tendance à être écartée du champ d’études de la cryptographe conventionnelle, quand bien même la synchronisation du chaos continue à être activement étudiée afin de sécurité les communications analogiques un haut débit et un niveau relativement faible de sécurité. Comme ce document a trait à des recherches se situant à l’interface des systèmes chaotiques et de la cryptographie conventionnelle, nous nous intéresseront uniquement à la seconde approche évoquée ci-dessus, c’est à-dire au chaos numérique et à ses applications cryptographiques.
22 Cependant, même si les systèmes chaotiques présentent un comportement assimilable à du hazard, on ne peut pas pour autant en déduire que leurs versions discrétisé fournissent des systèmes cryptographiquement sûrs (voir par exemple ~\cite{HabutsuNSM91, Biham91cryptanalysisof}). En effet, les fonctions chaotiques discrétisées n’héritent pas forcinrent intégralement du comportement complexe des fonctions chaotiques continues, et cette dégradation est susceptible de soulever de nombreux problèmes de sécurité. C’est pourquoi il est primordial du bien évaluer la complexité de la fonction binaire issue de la source chaotique originelle, lorsque l’on souhaite l’utiliser à des fins cryptographiques. De plus, un certain nombre de PRNG basis sur le chaos ont des problèmes de reproductibilité du flux de données, du fait d’une représentation différente des nombres à virgule flottante suivant le générateur considère (voir, par ex.,~\cite{Matthews:1984}).
25 Les systèmes dynamiques chaotiques sont habituellement continus, c’est-à-dire définis sur la droite réelle. Le passage des nombres réels aux nombres entiers peut conduire à une perte du caractère, c’est pourquoi cette conversion doit s’appuyer sur un cadre théorique rigoureux.
28 Dans ce document, nous présentons de nouveau générateurs de bits pseudo-aléatoires et chaotique. Ils peuvent évidemment aussi être utilisé pour produire des nombre uniformément distribués dans [0 ;1]. En effet, les bits produits peuvent être groupés $n$ par $n$, pour ainsi obtenir la partie décimale de $x\in [0 ;1] $ représentée en base 2. Ces générateurs sont basés sur les ‘’itérations chaotiques’’, des systèmes dynamiques discrets satisfaisant la définition de chaos proposée par Devaney~\cite{guyeux09}. Un cadre rigoureux est introduit dans lequel des propriétés topologiques de chaos, possédées par ces générateurs, sont rappelées.
31 Notre objectif, lors de la construction de ces générateurs, a été de tirer profit de l’apparent aléa de fonctions chaotiques réelles tout en possédant un niveau de sécurité élevé.
32 Plus précisément, notre générateur provient d’un système chaotiques itérant sur un espace d’entiers, et non sur un intervalle réel.
34 On montre qu’un PRNG est qualité par des preuves théoriques et validations expérimentales. De nombreux tests statistiques se trouvent dans la littérature. Leur but commun est de vérifier empiriquement la qualité statistique d'une suite donnée. Les batteries de tests les plus importants et les plus réputées, pour l’évaluation de PRNG, sont TestU01 ~\cite{Lecuyer2009}, NIST (National Institute of Standards and Technology, institut de standardisation du gouvernement des Etats-Unis d’Amérique) et DieHARD~\cite{ANDREW2008, Marsaglia1996}. Nous avons aussi recours à des tests de comparaison en fonction des paramètres fournis ~\cite{Menezes1997}. Pour diverses raisons, un générateur peut être aléatoire pour l’une de ces batteries et ne pas l’être pour une autre. C’est pourquoi réussir le plus grand nombre de ces tests est important pour augmenter la confiance que l’en peut accorder à un générateur donnée ~\cite{Turan2008}.
37 \section{Travaux en relation}
39 Random number generators (RNGs) are essential in statistical studies in several fields. They may be based on physical noise sources or on mathematical algorithms, but in both cases truly random numbers may not be obtained because of data acquisition
40 systems in the first case or because machine precision in the second case~\cite{Gonzalez2005281,Guler2011}. In spite of the fact that the existence (or not) of truly random number generators (RNG) remains an open question, the random number is replaced by value, pseudo-random numbers, provided by deterministic algorithms whose properties mimic those of a truly random sequence~\cite{DeMicco20083373,Knuth1998}.
42 Pseudo Random Number Generators (PRNGs) are widely used in science and technology, it is a critical component in modern cryptographic systems, communication systems, statistical simulation systems and any scientific area incorporating Monte Carlo methods~\cite{Vadim2011692,Marchi20093328,citeulike:867581,thecolourblue:1046} and many others. By the way, the Monte Carlo method appeared on the scientific scene in the late 1940s, for problems involving particle scattering in nuclear physics~\cite{Dyadkin1997258}. In the present era, there are few scientific fields that do not use random number. One of the most important applications of PRNGs is in cryptography to generate cryptographic keys, and to randomly initialize certain variables in cryptographic protocols.
44 Moreover, the idea o f applying chaos theory to randomness has produced important works very recently ~\cite{james1995,Gonzalez1999109,Ergun2007235,Zhou20093442,Gonzalez2002259,Behnia20113455}. Chaos theory has been established since 1970s by many different research areas, such as physics, mathematics, engineering, and biology, etc. ~\cite{Hao1993}. Since 1990s, many researchers have noticed that there exists the close relationship between chaos and cryptography ~\cite{Brown1996,Fridrich98symmetricciphers,Zaher20113721,Wong200367,Roland2001429,MS199850}; many properties of chaotic systems have their corresponding counterparts in traditional cryptosystems. Chaotic systems have several significant features favorable to secure communications, such as ergodicity, sensitivity to initial condition, control parameters and random like behaviour, which can be connected with some
45 conventional cryptographic properties of good ciphers, such as confusion/diffusion. With all these advantages scientists
46 expected to introduce new and powerful tools of chaotic cryptography. Cryptography is the art of achieving security by
47 encoding messages to make them non-readable. Nowaday, some efficient techniques for encoding based on discrete time chaotic systems are presented in ~\cite{Djema2009,Belmouhoub2005}. A good random number generation improves the cryptographic security ~\cite{Behnia2008408}.
49 Several test suites are readily available to researchers in academia and industry who wish to analyze their newly developed PRNG. Some general purpose test suites are Diehard by George Marsaglia ~\cite{Marsaglia1996}, the National Institute of Standards and Technology Statistical Test Suite ~\cite{ANDREW2008}, and Comparative test parameters~\cite{Menezes1997}. Systematic tests of pseudorandom number generators have received much attention. Finally, The TestU01 testsuite by L'Ecuyer and Simard ~\cite{Lecuyer2009} appears to define the current state of the art in the field.
50 \section{Résume de nos contributions}
51 Il a été étable dans ~\cite{guyeux09, guyeux10} que les itérations chaotiques (IC), un outil servant à l’obtention d’algorithmes itératifs rapide, satisfait la propriété de chaos topologique telle qu'elle a été définie par Devaney ~\cite{ Dev89}.
52 Nous avons alors construit notre PRNG en combinant ces itérations chaotiques avec deux générateurs basés sur la suite de logistique~\cite{wang2009}.
53 Le PRNG obtenu s’est a avoir présenter de meilleures propriétés statistiques que chaque composant pris séparément.
54 De plus de nombreuses propriétés de chaos différents ont été établis.
55 L'avantage de posséder de telles dynamiques chaotiques réside, pour les PRNGs, dans le fait que le générateur résultant est imprévisible.
56 Ces propriétés chaotiques, hérité de itérations chaotiques, ne sont possédés par aucun des deux générateurs fournis en entrée.
57 Nous avons montré que, en plus d'être chaotique, notre prévenir générateur peut passer la batterie de tests du NIST, qui est largement considérée être une batterie complète et difficile à passer : les générateur le passant peuvent servir à des applications cryptographiques ~\cite{ ANDREW2008}.
60 Dans les articles ~\cite{guyeuxTaiwan10, bgw10:ip}, nous avons amélioré la rapidité de a premier PRNG en n’utilisant plus les suites logistiques. Les deux PRNG fournis aux itérations chaotiques ont été : deux XORshifts dans \cite{ guyeuxTaiwan10}, et ISAAC avec XORshift au \cite {bgw10:ip}.
61 Nous avons de plus montré que, non seulement ces générateurs passent le NIST, mais en plus la version avec deux XORshift passe DIEHARD~\cite{guyeuxTaiwan10}, et celle avec ISAAC passer TestU01 \cite{bgw10:ip}.
64 Dans les extensions ~\cite{wbg10:ip, bfgw11:ij} de l’article~\cite{wang2009}, nous avons une nouvelle fois amélioré la vitesse, la sécurité et approfondis l'évaluation du générateur et précédent. D’autre part, l’application à le dissimulation d’information (tatouage numérique et stéganographie), précédemment proposée, a elle aussi été approfondie. Les propriétés chaotiques, les tests statistiques et diverse analyse de la sécurité tendent à montrer que notre générateur améliore les caractéristiques des PRNGs fournis en entrée, et pourrait donc, dans une certaine mesure, permettre de faire fau à un plus grand nombre d’attaque que les générateurs en entrée, si l’on se place dans un contexte cryptographique.
67 Dans les articles évoques ci-dessus, seule la négation vectorielle avait été envisagée pour fonction d’itération des itérations chaotiques. Il nous a semblé judicieux de nous demander si cette fonction a pouvait être avantageusement remplacée par d’autres fonctions d’itération. Ainsi, dans ~\cite{bcgw11:ip}, nous avons proposé une méthode, utilisant des graphes orientés fortement connectés, permette de sélectionner de bonnes fonctions d’itérations à mettre dans les itérations chaotique de notre générateur. L'approche proposée dans cet article résout le problème de la sélection des bonnes fonctions en produisant une classe de fonctions telles que les itérations chaotiques sont effectivement du chaos selon Devaney, et telles que le générateur associé passe avec succès les tests statistiques
70 Enfin, nous avons utilisé le négation vectorielle comme un prototype, et expliquer comment modifier cette fonction sans perdre les bonnes propriétés du générateur associé~\cite{bfgw11:ip}. Nous avons finalement fournis les résultats de simulation et une analyse de sécurité des générateur associé, afin d’évaluer le caractère aléatoire de cette nouvelle famille de générateurs.
73 \section{Objectifs de le thèse}
74 During my research studies, the quantization effects on the dynamics of the chaotic maps have been investigated. It is noticed that most of the maps will experience the problems such as short periodic cycle length, high correlation of data, and the problem of the existence of fixed points will become significant. Therefore, a new scheme based on chaotic iterations is proposed. It is found that the statistical properties of a sequence can be greatly improved by applying this newly designed chaotic iterations function. This hence can also serve as the major building block for the design of chaos-based random number generators.
76 \section{Organisation du manuscrit}
78 The organization of this thesis is as follows.
80 In Chapter 2, serving as the background of this thesis, the fundamental views and definitions of random number are summarized, and an overview of the classification and explanation of different types of RNGs are provided. We present the definitions that will be used in this thesis. The use of chaos for random number generators will be summarized. Some techniques to generate random number, based on chaos, will be revisited.
82 In Chapter 3, beginning with an brief review of the combinatorial objects used in the design of CIs PRNG and a theoretical proof of chaotic iterations, it outlines two novel approaches for generating random number sequences based on chaotic iterations techniques. The design of CIs for random number generators will be summarized. Some typical examples of chaos-based random number generators are described.
86 In Chapter 4, a detailed study is undergone, how a PRNG can be tested is described and the details of Diehard, NIST, comparative test parameters and TestU01 statistical test suites are presented. A comparative study on the quality of two novel approaches for CIs PRNGs and the associated random number generators are reported. The approach for combining two generators based on chaotic iterations would give better properties than the individual components alone. The comparison of the speed and statistical tests results allow us to consider that our new CIs generator has better pseudo-random characteristics
89 in Chapter 5. The performance of these newly designed PRNG based on chaotic iterations will be analyzed and compared with some common PRNGs. Finally, the criteria, such as uniformity, correlations, sequence patterns and complexity, and so on, which are commonly used to verify the randomness of a sequence, are also introduced.
91 In Chapter 6, In prior literature, the iterate function is just the vectorial boolean negation.
92 In this Chapter, we propose a method using Graph with strongly connected components as a selection criterion for chaotic iterate function.
93 In order to face the challenge of using the proposed chaotic iterate functions in PRNG, these PRNGs are subjected to the NIST statistical batteries of tests.
96 In Chapter 7, a potential use of above PRNGs in some Internet security field is presented, namely in information hiding. Such generators can strongly improve the confidence put in any information hiding scheme and in cryptography in general: due to their properties of unpredictability, the possibilities offered to an attacker to achieve his goal are drastically reduced in that context.
99 We conclude this thesis in Chapter 8 by summarizing the significance of our work and discussing the possible future work in this area.
102 \section{Abréviations}
103 \begin{tabular}{ll}\toprule
104 \textbf{Abbreviation}& \textbf{Definition}\\\hline
105 \textbf{RNGs}& Générateurs de nombres aléatoires \\
106 &(Random Number Generators)\\
107 \textbf{TRNGs}& Générateurs de nombres réellement aléatoires \\
108 &(True Random Number Generators)\\
109 \textbf{PRNG}& Générateurs de nombres pseudo-aléatoires \\
110 &(Pseudo Random Number Generator)\\
111 \textbf{CSPRNG}&Cryptographiquement sûr Générateur nombre pseudo-aléatoire \\
112 &(Cryptographically Secure Pseudo Random Number Generator)\\
113 \textbf{NIST}& Institut National des Standards and Technology \\
114 &(National Institute of Standards and Technology,USA)\\
115 \textbf{VOD}& Vidéo à la Demande \\
116 &(Video on Demand)\\\bottomrule
122 \section{ Notations mathématiques }
123 \begin{tabular}{@{}c@{}@{}l@{}}
124 \textbf{Symbol} &\textbf{Meaning}\\
125 $\llbracket 1;\mathsf{N} \rrbracket$ & $\rightarrow\{1,2,\hdots,N\}$ \\
126 $S^{n}$ & $\rightarrow$ $n$-ième terme d’une suite $S=(S^{1},S^{2},\hdots)$ \\
127 $v_{i}$ & $\rightarrow$ the $i$-ième coordonnée d’un vecteur : $v=(v_{1},v_{2},\hdots, v_n)$\\
128 $f^{k}$ & $\rightarrow$ $k$-ième composition d’une fonction $f$ \\
129 $\emph{strategy}$~ & $\rightarrow$ toute suite dont les éléments appartiennent à$%
130 \llbracket 1;\mathsf{N} \rrbracket $ \\
131 $mod$ & $\rightarrow$ le modulo (reste d’une division euclidienne)\\
132 $\mathbb{S}$ & $\rightarrow$ ensemble de toutes les stratégies.\\
133 $\mathbf{C}_n^k$ & $\rightarrow$ le coefficient binomial ${n \choose k} = \frac{n!}{k!(n-k)!}$\\
134 $\oplus$ & $\rightarrow$ ou exclusif bit à bit \\
135 %& $\begin{array}{r@{\;}l}\ f^{k}=\underbrace{f\circ ...\circ f} \\ \ k\ \text{times}\end{array}$\\
136 $+$ & $\rightarrow$ addition d’entiers \\
137 $\ll \text{and} \gg$ & $\rightarrow$ opérateurs de décalage habitude \\
138 $(\mathcal{X}, \text{d})$ & $\rightarrow$ un espace métrique \\
139 $\lfloor x \rfloor$ & $\rightarrow$ la partie entière de $x$ \\
140 $n!$ & $\rightarrow$ le factoriel $n!=n\times(n-1)\times\dots\times1$\\
141 $\mathds{N}^{\ast }$ & $\rightarrow$ l'ensemble des entiers naturels non nul \{1,2,3,...\}
