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