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
28 % Pour éviter cette perte de chaos, nous avons présenté des PRNGs qui itèrent des
29 % fonctions continues $G_f$ sur un domaine discret $\{ 1, \ldots, n \}^{\Nats}
30 % \times \{0,1\}^n$ où $f$ est une fonction booléenne (\textit{i.e.}, $f :
31 % \{0,1\}^n \rightarrow \{0,1\}^n$). Ces générateurs sont
32 % $\textit{CIPRNG}_f^1(u)$ \cite{guyeuxTaiwan10,bcgr11:ip},
33 % $\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip} et
34 % $\chi_{\textit{14Secrypt}}$ \cite{chgw14oip} où \textit{CI} signifie
35 % \emph{Chaotic Iterations}.
37 % Dans~\cite{bcgr11:ip} nous avons tout d'abord prouvé que pour établir la nature
38 % chaotique de l'algorithme $\textit{CIPRNG}_f^1$, il est nécessaire et suffisant
39 % que le graphe des itérations asynchrones soit fortement connexe. Nous avons
40 % ensuite prouvé que pour que la sortie de cet algorithme suive une loi de
41 % distribution uniforme, il est nécessaire et suffisant que la matrice de Markov
42 % associée à ce graphe soit doublement stochastique. Nous avons enfin établi des
43 % conditions suffisantes pour garantir la première propriété de connexité. Parmi
44 % les fonctions générées, on ne retenait ensuite que celles qui vérifiait la
45 % seconde propriété. Dans~\cite{chgw14oip}, nous avons proposé une démarche
46 % algorithmique permettant d'obtenir directement un graphe d'itérations fortement
47 % connexe et dont la matrice de Markov est doublement stochastique. Le travail
48 % présenté ici généralise ce dernier article en changeant le domaine d'itération,
49 % et donc de métrique. L'algorithme obtenu possède les même propriétés théoriques
50 % mais un temps de mélange plus réduit.
52 % Pour décrire un peu plus précisément le principe de
53 % la génération pseudo-aléatoire, considérons l'espace booléen
55 % muni des lois \og +\fg{}, \og . \fg{} et \og $\overline{\bullet}$ \fg{}
56 % définies par les tableaux ci-dessous:
59 % \begin{tabular}{|c|c|c|}
68 % \begin{tabular}{|c|c|c|}
77 % \begin{tabular}{|c|c|c|}
81 % $\overline{x}$ & 1 & 0 \\
87 % La fonction itérée est
88 % une fonction $f$ de $\Bool^n$ dans lui-même qui à
89 % un mot binaire $x = (x_1,\ldots,x_n)$
90 % associe le mot $(f_1(x),\ldots, f_n(x))$.
91 % Un exemple de fonction de $\Bool^n$ dans lui-même
92 % est la fonction négation
94 % $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$.
96 % Le principe itératif, basé sur le mode opératoire dit \emph{asynchrone}, est le
97 % suivant: à chaque itération $t$, on choisit un indice $i$ entre $1$ et $n$, et
98 % le mot $x^t = (x_1^t,\ldots,x_n^t)$ est remplacé par $x^{t+1} = (x_1^t,\ldots ,
99 % x_{i-1}^t, f_i(x^t), x_{i+1}^t,\ldots, x_n^t)$.
101 % Au bout d'un nombre $N$ d'itérations, si la fonction (notée $G_f$ dans ce
102 % document) que l'on peut associer à l'algorithme décrit ci-dessus a de \og
103 % \emph{bonnes}\fg{} propriétés chaotiques, le mot $x^N$ doit être \og \emph{très
104 % différent}\fg{} de $x^0$ de façon à sembler ne plus dépendre de $x_0$. En
105 % effet, pour un générateur aléatoire, il faut que la structure de $x^N$ semble
106 % être due au hasard; pour une application cryptographique, il faut qu'il soit
107 % matériellement impossible (dans les conditions techniques actuelles) de
108 % retrouver $x^0$ à partir de $x^N$.
110 % Tous les mots de $\Bool^n$ peuvent constituer les $2^n$ sommets d'un
111 % \gls{graphoriente} (cf. glossaire) dans lequel un arc relie deux sommets $x$ et
112 % $x'$ s'il existe une itération de l'algorithme de génération qui permet de
113 % passer directement de $x$ à $x'$. Ce graphe est appelé le \emph{graphe d'itérations} et
114 % nous montrons ici que si l'on a un \gls{graphfortementconnexe} (cf. glossaire),
115 % alors la fonction $G_f$ est transitive, donc chaotique.
117 % Enfin, un bon générateur aléatoire se doit de
118 % fournir des nombres selon une \gls{distributionuniforme} (cf. glossaire).
119 % La dernière partie de cet article donne,
120 % dans le cas où le graphe d'itérations est fortement connexe,
121 % une condition nécessaire et suffisante pour que
122 % cette propriété soit satisfaite.
125 % Le chaos a été appliqué à des domaines variés en
126 % informatique, comme les fonctions de hachage,
127 % la stéganographie, la génération de nombres pseudo
129 % Toutes ces applications exploitent les propriétés définissant des
130 % fonctions chaotiques et énoncées par Devaney, telles que la
131 % transitivité, la régularité et la sensibilité aux conditions initiales.
134 % Les systèmes dynamiques \emph{chaotiques} sont des processus itératifs
135 % définis par une fonction chaotique $f$ d'un domaine $E$ dans lui-même.
136 % En démarrant d'un état quelconque $x$ du sytème,
137 % nommé par la suite \emph{configuration},
138 % le système construit la séquence $x$, $f(x)$, $f^2(x)$, $f^3(x)$, \dots
139 % où $f^k(x)$ est le $k^{\textrm{ème}}$ itéré de $f$ en $x$.
140 % La plupart des applications informatiques dite \og chaotiques \fg{}
141 % sont basées sur des processus itératifs de la forme $x^{n+1} = f(x^n)$
142 % où $f$ est la fonction \emph{tente} avec $x^0 = 0,4001$ (donnée à la figure~\ref{fig:iter:tent})
143 % ou la fonction \emph{logistique} avec $\mu = 3,45$ et $x^0 = 0,1$ (donnée à la figure~\ref{fig:iter:log})
144 % connues pour être chaotiques dans $\R$.
148 % \subfloat[Fonction tente $f=\min\{x,\,1-x\}$]{
149 % \begin{minipage}{0.45\textwidth}
151 % \includegraphics[height=3cm]{images/tente.png}
154 % \label{fig:iter:tent}
156 % \subfloat[Fonction logistique $f(x) = \mu x (1 -x)$]{
157 % \begin{minipage}{0.45\textwidth}
159 % \includegraphics[height=3cm]{images/logistique.png}
162 % \label{fig:iter:log}
165 % \caption{Systèmes itératifs basés sur des fonctions chaotiques dans $\R$ \label{fig:iter}}
169 % Cependant il n'a pas été établi que des fonctions prouvées
170 % comme étant chaotiques sur $\R$ le restent sur les nombres à virgule flottante,
171 % qui est le domaine d'interprétation informatique des réels.
172 % On souhaite ainsi éviter une éventuelle perte des propriétés de chaos
173 % lors de l'exécution des programmes implémentant ces fonctions.
174 % Ce document présente pour cela l'alternative suivante:
175 % à partir d'une fonction booléenne, $f: \Bool^n \rightarrow \Bool^n$,
176 % où $\Bool$ est le domaine des booléens $\{0,1\}$, on
177 % construit une fonction $G_f : \llbracket 1 ; n \rrbracket^{\Nats} \times \Bool^n$,
178 % où $\llbracket 1 ; n \rrbracket$ est l'ensemble des entiers
179 % $\{1, 2, \hdots, n\}$ et on itère celle-ci.
180 % Comme $f$ est discrète, $G_f$ l'est aussi et les résultats théoriques
181 % obtenus sur $G_f$, notamment sa chaoticité, sont maintenus durant
183 % Un exemple de fonction booléenne de $\Bool^n$ dans lui-même est la fonction négation
185 % $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$.
190 % De plus, plutôt que de trouver des exemples de telles fonctions $f$, et de prouver
191 % (\textit{a posteriori}) la chaoticité de $G_f$, on peut penser à caractériser
192 % les fonctions engendrant systématiquement des fonctions chaotiques.
193 % Ce document présente une telle caractérisation
194 % qui s'exprime sur le graphe des itérations asynchrones
195 % de la fonction booléenne $f$, qui est, intuitivement, le graphe
196 % de toutes les itérations possibles de la fonction.
197 % Cette situation se réduit en un problème portant sur des graphes à $2^n$
199 % Ainsi pour étendre l'applicabilité de cette caractérisation, on s'intéresse
200 % au graphe des interactions de $f$, qui, intuitivement,
201 % représente les dépendances entre les $f_i$, $1\le i \le n$ et les $i$
202 % et qui ne contient que $n$ sommets (et qui est à comparer aux $2^n$
204 % Sur ce graphe on exprime des conditions garantissant la chaoticité de la fonction $G_f$.
205 % Ainsi, toutes les fonctions $G_f$ engendrées à partir d'un graphe
206 % d'interactions de $f$ aux propriétés \textit{ad hoc} seront chaotiques.
208 % Se pose enfin l'applicabilité des fonctions $G_f$ à la génération
209 % de nombres pseudo aléatoires, l'aléa étant intuitivement
210 % une notion proche de celle du chaos.
211 % Pour aborder cette classe de problèmes, on remarque que l'on doit au moins
212 % garantir que l'ensemble des valeurs retournées par l'algorithme suit
213 % une loi uniforme, propriété qui n'est pas imposée d'un point de vue topologique.
214 % Ce document montre que cette contrainte peut s'exprimer à nouveau sur le graphe des itérations asynchrones de $f$
215 % et qu'on peut ainsi filtrer les bons candidats à la génération de nombres pseudo aléatoires.
216 % Cette idée est validée après évaluation
217 % des générateurs de nombres pseudo aléatoires
218 % sur une batterie de tests.
221 % Le reste de ce document est organisé comme suit.
222 % La section~\ref{section:chaos} présente ce qu'est un système dynamique discret booléen itérant une fonction $f$.
223 % La chaoticité de la fonction engendrée $G_f$ est caractérisée en
224 % section~\ref{sec:charac}.
225 % Des conditions suffisantes pour obtenir cette chaoticité sont présentées en
226 % section~\ref{sec:sccg}.
227 % L'application à la génération de nombres pseudo aléatoires est formalisée,
228 % les fonctions dont l'image est uniformément distribuée sur le domaine sont
229 % caractérisées et les générateurs sont évalués en section~\ref{sec:prng}.
231 % Dans la section suivante, nous rappelons les notions élémentaires sur les
232 % systèmes booléens. La section~\ref{section:caracterisation} présente les
233 % définitions théoriques liées au chaos. Ensuite, une application de ces résultats
234 % à la génération de nombres pseudo-aléatoires est proposée en
235 % section~\ref{section:genpa} ainsi qu'une méthode permettant d'obtenir des
236 % matrices d'itérations doublement stochastiques en
237 % section~\ref{section:genmat}. Enfin, en section~\ref{section:expes} la qualité
238 % du PRNG obtenu est éprouvée avec les tests standards du domaine.
243 %%% TeX-master: "main"
