X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/blobdiff_plain/c8b7da5a49ee32f19091be950c39633b20b344e3..e4f6e60e4d2af88e0e16f2d680cf4fe3725ea1fc:/intro.tex diff --git a/intro.tex b/intro.tex index 6460412..569c493 100644 --- a/intro.tex +++ b/intro.tex @@ -1,65 +1,56 @@ -L'exploitation de \og systèmes chaotiques\fg{} pour générer des séquences -pseudo-aléatoires est un sujet actif de recherche~\cite{915396,915385,5376454}. -Ces systèmes sont choisis principalement -en raison de leur imprévisibilité et de leur sensibilité aux conditions initiales. - -Souvent les travaux se limitent à itérer une fonction paramétrée -\emph{chaotique} comme la fonction logistique~\cite{915396,915385}, ou encore -celle du chat d'Arnold~\cite{5376454}\ldots Il reste à trouver les paramètres -optimaux permettant d'éviter les attracteurs de telles fonctions et garantissant -que les séquences de nombres produits suivent une loi de distribution uniforme. -Pour vérifier la qualité des sorties produites il est usuel de soumettre les -PRNG (Pseudo-Random Number Generator) à des tests statistiques tels -DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10} et TestU01~\cite{LEcuyerS07}. - -Dans son acception vulgarisée, -la notion de chaos est souvent réduite à celle de forte sensibilité -aux conditions initiales (le fameux \og \emph{effet papillon}\fg{}): -une fonction continue $k$ définie sur un espace métrique -est dite \emph{fortement sensible aux conditions initiales} si pour tout -point $x$ et pour toute valeur positive $\epsilon$ -il est possible de trouver un point $y$, arbitrairement proche -de $x$, et un entier $t$ tels que la distance entre les -$t^{\textrm{ièmes}}$ itérés de $x$ et de $y$ --- notés $k^t(x)$ et $k^t(y)$ --- est supérieure à $\epsilon$. -Cependant, dans sa définition du chaos, -Devaney~\cite{Devaney} impose à la fonction chaotique deux autres propriétés -appelées \emph{transitivité} et \emph{régularité}, -Les fonctions citées plus haut ont été étudiées -au regard de ces propriétés et ont été prouvées comme chaotiques sur $\R$. -Cependant, rien ne garantit que ces propriétés sont préservées sur les nombres -flottants qui est le domaine d'interprétation des nombres réels de $\R$. - -Pour éviter cette perte de chaos, nous avons présenté des PRNGs qui itèrent des -fonctions continues $G_f$ sur un domaine discret $\{ 1, \ldots, n \}^{\Nats} -\times \{0,1\}^n$ où $f$ est une fonction booléenne (\textit{i.e.}, $f : -\{0,1\}^n \rightarrow \{0,1\}^n$). Ces générateurs sont -$\textit{CIPRNG}_f^1(u)$ \cite{guyeuxTaiwan10,bcgr11ip}, -$\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip} et -$\chi_{\textit{14Secrypt}}$ \cite{chgw14oip} où \textit{CI} signifie +The exploitation of chaotic systems to generate pseudorandom sequences is +an hot topic~\cite{915396,915385,5376454}. Such systems are fundamentally +chosen due to their unpredictable character and their sensitiveness to initial conditions. +In most cases, these generators simply consist in iterating a chaotic function like +the logistic map~\cite{915396,915385} or the Arnold's one~\cite{5376454}\ldots +It thus remains to find optimal parameters in such functions so that attractors are +avoided, hoping by doing so that the generated numbers follow a uniform distribution. +In order to check the quality of the produced outputs, it is usual to test the +PRNGs (Pseudo-Random Number Generators) with statistical batteries like +the so-called DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or TestU01~\cite{LEcuyerS07} ones. + +In its general understanding, chaos notion is often reduced to the strong +sensitiveness to the initial conditions (the well known ``butterfly effect''): +a continuous function $k$ defined on a metrical space is said +\emph{strongly sensitive to the initial conditions} if for each point +$x$ and each positive value $\epsilon$, it is possible to find another +point $y$ as close as possible to $x$, and an integer $t$ such that the distance +between the $t$-th iterates of $x$ and $y$, denoted by $k^t(x)$ and $k^t(y)$, +are larger than $\epsilon$. However, in his definition of chaos, Devaney~\cite{Devaney} +imposes to the chaotic function two other properties called +\emph{transitivity} and \emph{regularity}. Functions evoked above have +been studied according to these properties, and they have been proven as chaotic on $\R$. +But nothing guarantees that such properties are preserved when iterating the functions +on floating point numbers, which is the domain of interpretation of real numbers $\R$ on +machines. + +To avoid this lack of chaos, we have previously presented some PRNGs that iterate +continuous functions $G_f$ on a discrete domain $\{ 1, \ldots, n \}^{\Nats} + \times \{0,1\}^n$, where $f$ is a Boolean function (\textit{i.e.}, $f : + \{0,1\}^n \rightarrow \{0,1\}^n$). These generators are +$\textit{CIPRNG}_f^1(u)$ \cite{guyeuxTaiwan10,bcgr11:ip}, +$\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip} and +$\chi_{\textit{14Secrypt}}$ \cite{chgw14oip} where \textit{CI} means \emph{Chaotic Iterations}. - -Dans~\cite{bcgr11ip} nous avons tout d'abord prouvé que pour établir la nature -chaotique de l'algorithme $\textit{CIPRNG}_f^1$, il est nécessaire et suffisant -que le graphe des itérations asynchrones soit fortement connexe. Nous avons -ensuite prouvé que pour que la sortie de cet algorithme suive une loi de -distribution uniforme, il est nécessaire et suffisant que la matrice de Markov -associée à ce graphe soit doublement stochastique. Nous avons enfin établi des -conditions suffisantes pour garantir la première propriété de connexité. Parmi -les fonctions générées, on ne retenait ensuite que celles qui vérifiait la -seconde propriété. Dans~\cite{chgw14oip}, nous avons proposé une démarche -algorithmique permettant d'obtenir directement un graphe d'itérations fortement -connexe et dont la matrice de Markov est doublement stochastique. Le travail -présenté ici généralise ce dernier article en changeant le domaine d'itération, -et donc de métrique. L'algorithme obtenu possède les même propriétés théoriques -mais un temps de mélange plus réduit. - -% Pour décrire un peu plus précisément le principe de -% la génération pseudo-aléatoire, considérons l'espace booléen +We have firstly proven in~\cite{bcgr11:ip} that, to establish the chaotic nature +of algorithm $\textit{CIPRNG}_f^1$, it is necessary and sufficient that the +asynchronous iterations are strongly connected. We then have proven that it is necessary +and sufficient that the Markov matrix associated to this graph is doubly stochastic, +in order to have a uniform distribution of the outputs. We have finally established +sufficient conditions to guarantee the first property of connectivity. Among the +generated functions, we thus have considered for further investigations only the one that +satisfy the second property too. In~\cite{chgw14oip}, we have proposed an algorithmic +method allowing to directly obtain a strongly connected iteration graph having a doubly +stochastic Markov matrix. The research work presented here generalizes this latter article +by updating the iteration domain and the metric. The obtained algorithm owns the same +theoretical properties but with a reduced mixing time. + +% +% Pour décrire un peu plus précisément le principe de +% la génération pseudo-aléatoire, considérons l'espace booléen % $\Bool=\{0,1\}$ % muni des lois \og +\fg{}, \og . \fg{} et \og $\overline{\bullet}$ \fg{} -% définies par les tableaux ci-dessous: +% définies par les tableaux ci-dessous: % \begin{center} % \begin{tabular}{|c|c|c|} @@ -90,64 +81,64 @@ mais un temps de m % \end{center} -% La fonction itérée est -% une fonction $f$ de $\Bool^n$ dans lui-même qui à +% La fonction itérée est +% une fonction $f$ de $\Bool^n$ dans lui-même qui à % un mot binaire $x = (x_1,\ldots,x_n)$ % associe le mot $(f_1(x),\ldots, f_n(x))$. -% Un exemple de fonction de $\Bool^n$ dans lui-même -% est la fonction négation -% définie par +% Un exemple de fonction de $\Bool^n$ dans lui-même +% est la fonction négation +% définie par % $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$. -% Le principe itératif, basé sur le mode opératoire dit \emph{asynchrone}, est le -% suivant: à chaque itération $t$, on choisit un indice $i$ entre $1$ et $n$, et -% le mot $x^t = (x_1^t,\ldots,x_n^t)$ est remplacé par $x^{t+1} = (x_1^t,\ldots , +% Le principe itératif, basé sur le mode opératoire dit \emph{asynchrone}, est le +% suivant: à chaque itération $t$, on choisit un indice $i$ entre $1$ et $n$, et +% le mot $x^t = (x_1^t,\ldots,x_n^t)$ est remplacé par $x^{t+1} = (x_1^t,\ldots , % x_{i-1}^t, f_i(x^t), x_{i+1}^t,\ldots, x_n^t)$. -% Au bout d'un nombre $N$ d'itérations, si la fonction (notée $G_f$ dans ce -% document) que l'on peut associer à l'algorithme décrit ci-dessus a de \og -% \emph{bonnes}\fg{} propriétés chaotiques, le mot $x^N$ doit être \og \emph{très -% différent}\fg{} de $x^0$ de façon à sembler ne plus dépendre de $x_0$. En -% effet, pour un générateur aléatoire, il faut que la structure de $x^N$ semble -% être due au hasard; pour une application cryptographique, il faut qu'il soit -% matériellement impossible (dans les conditions techniques actuelles) de -% retrouver $x^0$ à partir de $x^N$. +% Au bout d'un nombre $N$ d'itérations, si la fonction (notée $G_f$ dans ce +% document) que l'on peut associer à l'algorithme décrit ci-dessus a de \og +% \emph{bonnes}\fg{} propriétés chaotiques, le mot $x^N$ doit être \og \emph{très +% différent}\fg{} de $x^0$ de façon à sembler ne plus dépendre de $x_0$. En +% effet, pour un générateur aléatoire, il faut que la structure de $x^N$ semble +% être due au hasard; pour une application cryptographique, il faut qu'il soit +% matériellement impossible (dans les conditions techniques actuelles) de +% retrouver $x^0$ à partir de $x^N$. % Tous les mots de $\Bool^n$ peuvent constituer les $2^n$ sommets d'un % \gls{graphoriente} (cf. glossaire) dans lequel un arc relie deux sommets $x$ et -% $x'$ s'il existe une itération de l'algorithme de génération qui permet de -% passer directement de $x$ à $x'$. Ce graphe est appelé le \emph{graphe d'itérations} et +% $x'$ s'il existe une itération de l'algorithme de génération qui permet de +% passer directement de $x$ à $x'$. Ce graphe est appelé le \emph{graphe d'itérations} et % nous montrons ici que si l'on a un \gls{graphfortementconnexe} (cf. glossaire), % alors la fonction $G_f$ est transitive, donc chaotique. -% Enfin, un bon générateur aléatoire se doit de +% Enfin, un bon générateur aléatoire se doit de % fournir des nombres selon une \gls{distributionuniforme} (cf. glossaire). -% La dernière partie de cet article donne, -% dans le cas où le graphe d'itérations est fortement connexe, -% une condition nécessaire et suffisante pour que -% cette propriété soit satisfaite. +% La dernière partie de cet article donne, +% dans le cas où le graphe d'itérations est fortement connexe, +% une condition nécessaire et suffisante pour que +% cette propriété soit satisfaite. -% Le chaos a été appliqué à des domaines variés en +% Le chaos a été appliqué à des domaines variés en % informatique, comme les fonctions de hachage, -% la stéganographie, la génération de nombres pseudo -% aléatoires\ldots -% Toutes ces applications exploitent les propriétés définissant des -% fonctions chaotiques et énoncées par Devaney, telles que la -% transitivité, la régularité et la sensibilité aux conditions initiales. - - -% Les systèmes dynamiques \emph{chaotiques} sont des processus itératifs -% définis par une fonction chaotique $f$ d'un domaine $E$ dans lui-même. -% En démarrant d'un état quelconque $x$ du sytème, -% nommé par la suite \emph{configuration}, -% le système construit la séquence $x$, $f(x)$, $f^2(x)$, $f^3(x)$, \dots -% où $f^k(x)$ est le $k^{\textrm{ème}}$ itéré de $f$ en $x$. +% la stéganographie, la génération de nombres pseudo +% aléatoires\ldots +% Toutes ces applications exploitent les propriétés définissant des +% fonctions chaotiques et énoncées par Devaney, telles que la +% transitivité, la régularité et la sensibilité aux conditions initiales. + + +% Les systèmes dynamiques \emph{chaotiques} sont des processus itératifs +% définis par une fonction chaotique $f$ d'un domaine $E$ dans lui-même. +% En démarrant d'un état quelconque $x$ du sytème, +% nommé par la suite \emph{configuration}, +% le système construit la séquence $x$, $f(x)$, $f^2(x)$, $f^3(x)$, \dots +% où $f^k(x)$ est le $k^{\textrm{ème}}$ itéré de $f$ en $x$. % La plupart des applications informatiques dite \og chaotiques \fg{} -% sont basées sur des processus itératifs de la forme $x^{n+1} = f(x^n)$ -% où $f$ est la fonction \emph{tente} avec $x^0 = 0,4001$ (donnée à la figure~\ref{fig:iter:tent}) -% ou la fonction \emph{logistique} avec $\mu = 3,45$ et $x^0 = 0,1$ (donnée à la figure~\ref{fig:iter:log}) -% connues pour être chaotiques dans $\R$. +% sont basées sur des processus itératifs de la forme $x^{n+1} = f(x^n)$ +% où $f$ est la fonction \emph{tente} avec $x^0 = 0,4001$ (donnée à la figure~\ref{fig:iter:tent}) +% ou la fonction \emph{logistique} avec $\mu = 3,45$ et $x^0 = 0,1$ (donnée à la figure~\ref{fig:iter:log}) +% connues pour être chaotiques dans $\R$. % \begin{figure}[hb] % \begin{center} @@ -168,81 +159,91 @@ mais un temps de m % \label{fig:iter:log} % } % \end{center} -% \caption{Systèmes itératifs basés sur des fonctions chaotiques dans $\R$ \label{fig:iter}} +% \caption{Systèmes itératifs basés sur des fonctions chaotiques dans $\R$ \label{fig:iter}} % \end{figure} -% Cependant il n'a pas été établi que des fonctions prouvées -% comme étant chaotiques sur $\R$ le restent sur les nombres à virgule flottante, -% qui est le domaine d'interprétation informatique des réels. -% On souhaite ainsi éviter une éventuelle perte des propriétés de chaos -% lors de l'exécution des programmes implémentant ces fonctions. -% Ce document présente pour cela l'alternative suivante: -% à partir d'une fonction booléenne, $f: \Bool^n \rightarrow \Bool^n$, -% où $\Bool$ est le domaine des booléens $\{0,1\}$, on +% Cependant il n'a pas été établi que des fonctions prouvées +% comme étant chaotiques sur $\R$ le restent sur les nombres à virgule flottante, +% qui est le domaine d'interprétation informatique des réels. +% On souhaite ainsi éviter une éventuelle perte des propriétés de chaos +% lors de l'exécution des programmes implémentant ces fonctions. +% Ce document présente pour cela l'alternative suivante: +% à partir d'une fonction booléenne, $f: \Bool^n \rightarrow \Bool^n$, +% où $\Bool$ est le domaine des booléens $\{0,1\}$, on % construit une fonction $G_f : \llbracket 1 ; n \rrbracket^{\Nats} \times \Bool^n$, -% où $\llbracket 1 ; n \rrbracket$ est l'ensemble des entiers -% $\{1, 2, \hdots, n\}$ et on itère celle-ci. -% Comme $f$ est discrète, $G_f$ l'est aussi et les résultats théoriques -% obtenus sur $G_f$, notamment sa chaoticité, sont maintenus durant -% l'implémentation. -% Un exemple de fonction booléenne de $\Bool^n$ dans lui-même est la fonction négation -% définie par +% où $\llbracket 1 ; n \rrbracket$ est l'ensemble des entiers +% $\{1, 2, \hdots, n\}$ et on itère celle-ci. +% Comme $f$ est discrète, $G_f$ l'est aussi et les résultats théoriques +% obtenus sur $G_f$, notamment sa chaoticité, sont maintenus durant +% l'implémentation. +% Un exemple de fonction booléenne de $\Bool^n$ dans lui-même est la fonction négation +% définie par % $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$. -% De plus, plutôt que de trouver des exemples de telles fonctions $f$, et de prouver -% (\textit{a posteriori}) la chaoticité de $G_f$, on peut penser à caractériser -% les fonctions engendrant systématiquement des fonctions chaotiques. -% Ce document présente une telle caractérisation -% qui s'exprime sur le graphe des itérations asynchrones -% de la fonction booléenne $f$, qui est, intuitivement, le graphe -% de toutes les itérations possibles de la fonction. -% Cette situation se réduit en un problème portant sur des graphes à $2^n$ +% De plus, plutôt que de trouver des exemples de telles fonctions $f$, et de prouver +% (\textit{a posteriori}) la chaoticité de $G_f$, on peut penser à caractériser +% les fonctions engendrant systématiquement des fonctions chaotiques. +% Ce document présente une telle caractérisation +% qui s'exprime sur le graphe des itérations asynchrones +% de la fonction booléenne $f$, qui est, intuitivement, le graphe +% de toutes les itérations possibles de la fonction. +% Cette situation se réduit en un problème portant sur des graphes à $2^n$ % sommets. -% Ainsi pour étendre l'applicabilité de cette caractérisation, on s'intéresse +% Ainsi pour étendre l'applicabilité de cette caractérisation, on s'intéresse % au graphe des interactions de $f$, qui, intuitivement, -% représente les dépendances entre les $f_i$, $1\le i \le n$ et les $i$ -% et qui ne contient que $n$ sommets (et qui est à comparer aux $2^n$ +% représente les dépendances entre les $f_i$, $1\le i \le n$ et les $i$ +% et qui ne contient que $n$ sommets (et qui est à comparer aux $2^n$ % sommets. -% Sur ce graphe on exprime des conditions garantissant la chaoticité de la fonction $G_f$. -% Ainsi, toutes les fonctions $G_f$ engendrées à partir d'un graphe -% d'interactions de $f$ aux propriétés \textit{ad hoc} seront chaotiques. +% Sur ce graphe on exprime des conditions garantissant la chaoticité de la fonction $G_f$. +% Ainsi, toutes les fonctions $G_f$ engendrées à partir d'un graphe +% d'interactions de $f$ aux propriétés \textit{ad hoc} seront chaotiques. -% Se pose enfin l'applicabilité des fonctions $G_f$ à la génération -% de nombres pseudo aléatoires, l'aléa étant intuitivement +% Se pose enfin l'applicabilité des fonctions $G_f$ à la génération +% de nombres pseudo aléatoires, l'aléa étant intuitivement % une notion proche de celle du chaos. -% Pour aborder cette classe de problèmes, on remarque que l'on doit au moins -% garantir que l'ensemble des valeurs retournées par l'algorithme suit -% une loi uniforme, propriété qui n'est pas imposée d'un point de vue topologique. -% Ce document montre que cette contrainte peut s'exprimer à nouveau sur le graphe des itérations asynchrones de $f$ -% et qu'on peut ainsi filtrer les bons candidats à la génération de nombres pseudo aléatoires. -% Cette idée est validée après évaluation -% des générateurs de nombres pseudo aléatoires +% Pour aborder cette classe de problèmes, on remarque que l'on doit au moins +% garantir que l'ensemble des valeurs retournées par l'algorithme suit +% une loi uniforme, propriété qui n'est pas imposée d'un point de vue topologique. +% Ce document montre que cette contrainte peut s'exprimer à nouveau sur le graphe des itérations asynchrones de $f$ +% et qu'on peut ainsi filtrer les bons candidats à la génération de nombres pseudo aléatoires. +% Cette idée est validée après évaluation +% des générateurs de nombres pseudo aléatoires % sur une batterie de tests. -% Le reste de ce document est organisé comme suit. -% La section~\ref{section:chaos} présente ce qu'est un système dynamique discret booléen itérant une fonction $f$. -% La chaoticité de la fonction engendrée $G_f$ est caractérisée en +The remainder of this article is organized as follows. The next section is devoted to +preliminaries, basic notations, and terminologies regarding asynchronous iterations. +Then, in Section~\ref{sec:proofOfChaos}, Devaney's definition of chaos is recalled +while the proofs of chaos of our most general PRNGs is provided. Section~\ref{sec:SCCfunc} shows how to generate functions and a number of iterations such that the iteration graph is strongly connected, making the +PRNG chaotic. The next section focuses on examples of such graphs obtained by modifying the +hypercube, while Section~\ref{sec:prng} establishes the link between the theoretical study and +pseudorandom number generation. +This research work ends by a conclusion section, where the contribution is summarized and +intended future work is outlined. + +% Le reste de ce document est organisé comme suit. +% La section~\ref{section:chaos} présente ce qu'est un système dynamique discret booléen itérant une fonction $f$. +% La chaoticité de la fonction engendrée $G_f$ est caractérisée en % section~\ref{sec:charac}. -% Des conditions suffisantes pour obtenir cette chaoticité sont présentées en +% Des conditions suffisantes pour obtenir cette chaoticité sont présentées en % section~\ref{sec:sccg}. -% L'application à la génération de nombres pseudo aléatoires est formalisée, -% les fonctions dont l'image est uniformément distribuée sur le domaine sont -% caractérisées et les générateurs sont évalués en section~\ref{sec:prng}. - -Dans la section suivante, nous rappelons les notions élémentaires sur les -systèmes booléens. La section~\ref{section:caracterisation} présente les -définitions théoriques liées au chaos. Ensuite, une application de ces résultats -à la génération de nombres pseudo-aléatoires est proposée en -section~\ref{section:genpa} ainsi qu'une méthode permettant d'obtenir des -matrices d'itérations doublement stochastiques en -section~\ref{section:genmat}. Enfin, en section~\ref{section:expes} la qualité -du PRNG obtenu est éprouvée avec les tests standards du domaine. - +% L'application à la génération de nombres pseudo aléatoires est formalisée, +% les fonctions dont l'image est uniformément distribuée sur le domaine sont +% caractérisées et les générateurs sont évalués en section~\ref{sec:prng}. + +% Dans la section suivante, nous rappelons les notions élémentaires sur les +% systèmes booléens. La section~\ref{section:caracterisation} présente les +% définitions théoriques liées au chaos. Ensuite, une application de ces résultats +% à la génération de nombres pseudo-aléatoires est proposée en +% section~\ref{section:genpa} ainsi qu'une méthode permettant d'obtenir des +% matrices d'itérations doublement stochastiques en +% section~\ref{section:genmat}. Enfin, en section~\ref{section:expes} la qualité +% du PRNG obtenu est éprouvée avec les tests standards du domaine. +% %%% Local Variables: %%% mode: latex