1 The exploitation of chaotic systems to generate pseudorandom sequences is
2 an hot topic~\cite{915396,915385,5376454}. Such systems are fundamentally
3 chosen due to their unpredictable character and their sensitiveness to initial conditions.
4 In most cases, these generators simply consist in iterating a chaotic function like
5 the logistic map~\cite{915396,915385} or the Arnold's one~\cite{5376454}\ldots
6 It thus remains to find optimal parameters in such functions so that attractors are
7 avoided, guaranteeing by doing so that generated numbers follow a uniform distribution.
8 In order to check the quality of the produced outputs, it is usual to test the
9 PRNGs (Pseudo-Random Number Generators) with statistical batteries like
10 the so-called DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or TestU01~\cite{LEcuyerS07}.
12 In its general understanding, the chaos notion is often reduced to the strong
13 sensitiveness to the initial conditions (the well known ``butterfly effect''):
14 a continuous function $k$ defined on a metrical space is said
15 \emph{strongly sensitive to the initial conditions} if for all point
16 $x$ and all positive value $\epsilon$, it is possible to find another
17 point $y$, as close as possible to $x$, and an integer $t$ such that the distance
18 between the $t$-th iterates of $x$ and $y$, denoted by $k^t(x)$ and $k^t(y)$,
19 are larger than $\epsilon$. However, in his definition of chaos, Devaney~\cite{Devaney}
20 impose to the chaotic function two other properties called
21 \emph{transitivity} and \emph{regularity}. Functions evoked above have
22 been studied according to these properties, and they have been proven as chaotic on $\R$.
23 But nothing guarantees that such properties are preserved when iterating the functions
24 on floating point numbers, which is the domain of interpretation of real numbers $\R$ on
27 To avoid this lack of chaos, we have previously presented some PRNGs that iterate
28 continuous functions $G_f$ on a discrete domain $\{ 1, \ldots, n \}^{\Nats}
29 \times \{0,1\}^n$, where $f$ is a Boolean function (\textit{i.e.}, $f :
30 \{0,1\}^n \rightarrow \{0,1\}^n$). These generators are
31 $\textit{CIPRNG}_f^1(u)$ \cite{guyeuxTaiwan10,bcgr11:ip},
32 $\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip} and
33 $\chi_{\textit{14Secrypt}}$ \cite{chgw14oip} where \textit{CI} means
34 \emph{Chaotic Iterations}.
35 We have firstly proven in~\cite{bcgr11:ip} that, to establish the chaotic nature
36 of algorithm $\textit{CIPRNG}_f^1$, it is necessary and sufficient that the
37 asynchronous iterations are strongly connected. We then have proven that it is necessary
38 and sufficient that the Markov matrix associated to this graph is doubly stochastic,
39 in order to have a uniform distribution of the outputs. We have finally established
40 sufficient conditions to guarantee the first property of connectivity. Among the
41 generated functions, we thus considered for further investigations only the one that
42 satisfy the second property too. In~\cite{chgw14oip}, we have proposed an algorithmic
43 method allowing to directly obtain a strongly connected iteration graph having a doubly
44 stochastic Markov matrix. The research work presented here generalizes this latter article
45 by updating the iteration domain and the metric. The obtained algorithm owns the same
46 theoretical properties but with a reduced mixing time.
49 % Pour décrire un peu plus précisément le principe de
50 % la génération pseudo-aléatoire, considérons l'espace booléen
52 % muni des lois \og +\fg{}, \og . \fg{} et \og $\overline{\bullet}$ \fg{}
53 % définies par les tableaux ci-dessous:
56 % \begin{tabular}{|c|c|c|}
65 % \begin{tabular}{|c|c|c|}
74 % \begin{tabular}{|c|c|c|}
78 % $\overline{x}$ & 1 & 0 \\
84 % La fonction itérée est
85 % une fonction $f$ de $\Bool^n$ dans lui-même qui à
86 % un mot binaire $x = (x_1,\ldots,x_n)$
87 % associe le mot $(f_1(x),\ldots, f_n(x))$.
88 % Un exemple de fonction de $\Bool^n$ dans lui-même
89 % est la fonction négation
91 % $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$.
93 % Le principe itératif, basé sur le mode opératoire dit \emph{asynchrone}, est le
94 % suivant: à chaque itération $t$, on choisit un indice $i$ entre $1$ et $n$, et
95 % le mot $x^t = (x_1^t,\ldots,x_n^t)$ est remplacé par $x^{t+1} = (x_1^t,\ldots ,
96 % x_{i-1}^t, f_i(x^t), x_{i+1}^t,\ldots, x_n^t)$.
98 % Au bout d'un nombre $N$ d'itérations, si la fonction (notée $G_f$ dans ce
99 % document) que l'on peut associer à l'algorithme décrit ci-dessus a de \og
100 % \emph{bonnes}\fg{} propriétés chaotiques, le mot $x^N$ doit être \og \emph{très
101 % différent}\fg{} de $x^0$ de façon à sembler ne plus dépendre de $x_0$. En
102 % effet, pour un générateur aléatoire, il faut que la structure de $x^N$ semble
103 % être due au hasard; pour une application cryptographique, il faut qu'il soit
104 % matériellement impossible (dans les conditions techniques actuelles) de
105 % retrouver $x^0$ à partir de $x^N$.
107 % Tous les mots de $\Bool^n$ peuvent constituer les $2^n$ sommets d'un
108 % \gls{graphoriente} (cf. glossaire) dans lequel un arc relie deux sommets $x$ et
109 % $x'$ s'il existe une itération de l'algorithme de génération qui permet de
110 % passer directement de $x$ à $x'$. Ce graphe est appelé le \emph{graphe d'itérations} et
111 % nous montrons ici que si l'on a un \gls{graphfortementconnexe} (cf. glossaire),
112 % alors la fonction $G_f$ est transitive, donc chaotique.
114 % Enfin, un bon générateur aléatoire se doit de
115 % fournir des nombres selon une \gls{distributionuniforme} (cf. glossaire).
116 % La dernière partie de cet article donne,
117 % dans le cas où le graphe d'itérations est fortement connexe,
118 % une condition nécessaire et suffisante pour que
119 % cette propriété soit satisfaite.
122 % Le chaos a été appliqué à des domaines variés en
123 % informatique, comme les fonctions de hachage,
124 % la stéganographie, la génération de nombres pseudo
126 % Toutes ces applications exploitent les propriétés définissant des
127 % fonctions chaotiques et énoncées par Devaney, telles que la
128 % transitivité, la régularité et la sensibilité aux conditions initiales.
131 % Les systèmes dynamiques \emph{chaotiques} sont des processus itératifs
132 % définis par une fonction chaotique $f$ d'un domaine $E$ dans lui-même.
133 % En démarrant d'un état quelconque $x$ du sytème,
134 % nommé par la suite \emph{configuration},
135 % le système construit la séquence $x$, $f(x)$, $f^2(x)$, $f^3(x)$, \dots
136 % où $f^k(x)$ est le $k^{\textrm{ème}}$ itéré de $f$ en $x$.
137 % La plupart des applications informatiques dite \og chaotiques \fg{}
138 % sont basées sur des processus itératifs de la forme $x^{n+1} = f(x^n)$
139 % où $f$ est la fonction \emph{tente} avec $x^0 = 0,4001$ (donnée à la figure~\ref{fig:iter:tent})
140 % ou la fonction \emph{logistique} avec $\mu = 3,45$ et $x^0 = 0,1$ (donnée à la figure~\ref{fig:iter:log})
141 % connues pour être chaotiques dans $\R$.
145 % \subfloat[Fonction tente $f=\min\{x,\,1-x\}$]{
146 % \begin{minipage}{0.45\textwidth}
148 % \includegraphics[height=3cm]{images/tente.png}
151 % \label{fig:iter:tent}
153 % \subfloat[Fonction logistique $f(x) = \mu x (1 -x)$]{
154 % \begin{minipage}{0.45\textwidth}
156 % \includegraphics[height=3cm]{images/logistique.png}
159 % \label{fig:iter:log}
162 % \caption{Systèmes itératifs basés sur des fonctions chaotiques dans $\R$ \label{fig:iter}}
166 % Cependant il n'a pas été établi que des fonctions prouvées
167 % comme étant chaotiques sur $\R$ le restent sur les nombres à virgule flottante,
168 % qui est le domaine d'interprétation informatique des réels.
169 % On souhaite ainsi éviter une éventuelle perte des propriétés de chaos
170 % lors de l'exécution des programmes implémentant ces fonctions.
171 % Ce document présente pour cela l'alternative suivante:
172 % à partir d'une fonction booléenne, $f: \Bool^n \rightarrow \Bool^n$,
173 % où $\Bool$ est le domaine des booléens $\{0,1\}$, on
174 % construit une fonction $G_f : \llbracket 1 ; n \rrbracket^{\Nats} \times \Bool^n$,
175 % où $\llbracket 1 ; n \rrbracket$ est l'ensemble des entiers
176 % $\{1, 2, \hdots, n\}$ et on itère celle-ci.
177 % Comme $f$ est discrète, $G_f$ l'est aussi et les résultats théoriques
178 % obtenus sur $G_f$, notamment sa chaoticité, sont maintenus durant
180 % Un exemple de fonction booléenne de $\Bool^n$ dans lui-même est la fonction négation
182 % $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$.
187 % De plus, plutôt que de trouver des exemples de telles fonctions $f$, et de prouver
188 % (\textit{a posteriori}) la chaoticité de $G_f$, on peut penser à caractériser
189 % les fonctions engendrant systématiquement des fonctions chaotiques.
190 % Ce document présente une telle caractérisation
191 % qui s'exprime sur le graphe des itérations asynchrones
192 % de la fonction booléenne $f$, qui est, intuitivement, le graphe
193 % de toutes les itérations possibles de la fonction.
194 % Cette situation se réduit en un problème portant sur des graphes à $2^n$
196 % Ainsi pour étendre l'applicabilité de cette caractérisation, on s'intéresse
197 % au graphe des interactions de $f$, qui, intuitivement,
198 % représente les dépendances entre les $f_i$, $1\le i \le n$ et les $i$
199 % et qui ne contient que $n$ sommets (et qui est à comparer aux $2^n$
201 % Sur ce graphe on exprime des conditions garantissant la chaoticité de la fonction $G_f$.
202 % Ainsi, toutes les fonctions $G_f$ engendrées à partir d'un graphe
203 % d'interactions de $f$ aux propriétés \textit{ad hoc} seront chaotiques.
205 % Se pose enfin l'applicabilité des fonctions $G_f$ à la génération
206 % de nombres pseudo aléatoires, l'aléa étant intuitivement
207 % une notion proche de celle du chaos.
208 % Pour aborder cette classe de problèmes, on remarque que l'on doit au moins
209 % garantir que l'ensemble des valeurs retournées par l'algorithme suit
210 % une loi uniforme, propriété qui n'est pas imposée d'un point de vue topologique.
211 % Ce document montre que cette contrainte peut s'exprimer à nouveau sur le graphe des itérations asynchrones de $f$
212 % et qu'on peut ainsi filtrer les bons candidats à la génération de nombres pseudo aléatoires.
213 % Cette idée est validée après évaluation
214 % des générateurs de nombres pseudo aléatoires
215 % sur une batterie de tests.
218 % Le reste de ce document est organisé comme suit.
219 % La section~\ref{section:chaos} présente ce qu'est un système dynamique discret booléen itérant une fonction $f$.
220 % La chaoticité de la fonction engendrée $G_f$ est caractérisée en
221 % section~\ref{sec:charac}.
222 % Des conditions suffisantes pour obtenir cette chaoticité sont présentées en
223 % section~\ref{sec:sccg}.
224 % L'application à la génération de nombres pseudo aléatoires est formalisée,
225 % les fonctions dont l'image est uniformément distribuée sur le domaine sont
226 % caractérisées et les générateurs sont évalués en section~\ref{sec:prng}.
228 % Dans la section suivante, nous rappelons les notions élémentaires sur les
229 % systèmes booléens. La section~\ref{section:caracterisation} présente les
230 % définitions théoriques liées au chaos. Ensuite, une application de ces résultats
231 % à la génération de nombres pseudo-aléatoires est proposée en
232 % section~\ref{section:genpa} ainsi qu'une méthode permettant d'obtenir des
233 % matrices d'itérations doublement stochastiques en
234 % section~\ref{section:genmat}. Enfin, en section~\ref{section:expes} la qualité
235 % du PRNG obtenu est éprouvée avec les tests standards du domaine.
240 %%% TeX-master: "main"
