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