X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/blobdiff_plain/412f54fbed2c443f03aa09cc72f559221e63d83b..4da7584dffe58a5bbdcd406436a5b139ee4c13fd:/intro.tex diff --git a/intro.tex b/intro.tex index 3f51a08..c0b6e7d 100644 --- a/intro.tex +++ b/intro.tex @@ -4,241 +4,99 @@ chosen due to their unpredictable character and their sensitiveness to initial c 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, guaranteeing by doing so that generated numbers follow a uniform distribution. +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}. +the so-called DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or TestU01~\cite{LEcuyerS07} ones. -In its general understanding, the chaos notion is often reduced to the strong +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 all point -$x$ and all 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 +\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} -impose to the chaotic function two other properties called +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. -% -% 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,bcgr11:ip}, -% $\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip} et -% $\chi_{\textit{14Secrypt}}$ \cite{chgw14oip} où \textit{CI} signifie -% \emph{Chaotic Iterations}. -% -% Dans~\cite{bcgr11:ip} 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 -% $\Bool=\{0,1\}$ -% muni des lois \og +\fg{}, \og . \fg{} et \og $\overline{\bullet}$ \fg{} -% définies par les tableaux ci-dessous: - -% \begin{center} -% \begin{tabular}{|c|c|c|} -% \hline -% + & 0 & 1 \\ -% \hline -% 0 & 0 & 1 \\ -% \hline -% 1 & 1 & 1 \\ -% \hline -% \end{tabular}\qquad -% \begin{tabular}{|c|c|c|} -% \hline -% . & 0 & 1 \\ -% \hline -% 0 & 0 & 0 \\ -% \hline -% 1 & 0 & 1 \\ -% \hline -% \end{tabular}\qquad -% \begin{tabular}{|c|c|c|} -% \hline -% x & 0 & 1 \\ -% \hline -% $\overline{x}$ & 1 & 0 \\ -% \hline -% \end{tabular} -% \end{center} - - -% 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 -% $\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 , -% 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$. - -% 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 -% 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 -% 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. - - -% 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 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$. - -% \begin{figure}[hb] -% \begin{center} -% \subfloat[Fonction tente $f=\min\{x,\,1-x\}$]{ -% \begin{minipage}{0.45\textwidth} -% \begin{center} -% \includegraphics[height=3cm]{images/tente.png} -% \end{center} -% \end{minipage} -% \label{fig:iter:tent} -% } -% \subfloat[Fonction logistique $f(x) = \mu x (1 -x)$]{ -% \begin{minipage}{0.45\textwidth} -% \begin{center} -% \includegraphics[height=3cm]{images/logistique.png} -% \end{center} -% \end{minipage} -% \label{fig:iter:log} -% } -% \end{center} -% \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 -% 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 -% $\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$ -% sommets. -% 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$ -% 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. - -% 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 -% 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 -% section~\ref{sec:charac}. -% 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. -% - -%%% Local Variables: -%%% mode: latex -%%% TeX-master: "main" -%%% End: +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}. +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 ones 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. + + +However, it cannot be directly deduced +that $\chi_{\textit{14Secrypt}}$ is chaotic +since we do not output all the successive +values of iterating $F_f$. +This algorithm only displays a +subsequence $x^{b.n}$ of a whole chaotic sequence $x^{n}$ and +it is indeed definitively false that the chaos property is +preserved for any subsequence of a chaotic sequence. +This article presents conditions to preserve this property. + +An approach to generate a large class of chaotic functions has +been presented in~\cite{chgw14oip}. +It is basically fourfold: +first build a $\mathsf{N}$-cube, next remove an Hamiltonian cycle, further add self-loop +on each vertex and finally, translate this into a Boolean map. +We are then left to check whether this approach proposes maps with the required conditions +for the chaos. +The answer is indeed positive. The pseudorandom number generation can thus be seen as a +random walk in a $\mathsf{N}$-cube without a Hamiltonian cycle. + +In the PRNG context, there remains to find which subsequence +is theoretically and practically +sufficient to extract. +A uniform distribution is indeed awaited and this +cannot be obtained in a walk in the hypercube +with paths of short length $b$. +However, the higher +is $b$ the slower is the +algorithm to generate pseudorandom +numbers. +The time until the +corresponding Markov chain is close +to the uniform distribution is a metric +that should be theoretically and practically studied. +Finally, the ability of the approach to face classical +tests suite has to be evaluated. + + +%A upper bound of this time quadratic in the number of +%generated bits. + + +The remainder of this article is organized as follows. The next section is devoted to +preliminaries, basic notations, and terminologies regarding Boolean map 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. +This is the first major contribution. +Section~\ref{sec:SCCfunc} shows how to generate functions with required properties +making the PRNG chaotic. +The next section (Sect.~\ref{sec:hypercube}) defines the theoretical framework +to study the stopping-time, \textit{i.e.}, time until reaching +a uniform distribution. +This is the second major contribution. +The Section~\ref{sec:prng} gives practical results on evaluating the PRNG against the NIST suite. +This research work ends by a conclusion section, where the contribution is summarized and +intended future work is outlined.