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