X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/d69591c41135e899d27072006db6af016df62445..151dc81946eee7c7fb5fbc327ada099f2af6a2c3:/intro.tex?ds=inline diff --git a/intro.tex b/intro.tex index c0b6e7d..e66a6b4 100644 --- a/intro.tex +++ b/intro.tex @@ -1,102 +1,122 @@ -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. +The exploitation of chaotic systems to generate pseudorandom sequences +is a very topical issue~\cite{915396,915385,5376454}. Such systems are +fundamentally chosen because of 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 +Optimal parameters of such functions remain to be found so that +attractors are avoided,\textit{e.g.}. +By following this procedure, generated numbers will hopefully +follow a uniform distribution. In order to check the quality of the +produced outputs, PRNGs (Pseudo-Random Number +Generators) are usually tested 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. +In its general understanding, the notion of chaos 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 to be \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)$, is 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}. The functions mentioned 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}. -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. +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\}^{\mathsf{N}} +\rightarrow \{0,1\}^{\mathsf{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{DBLP:conf/secrypt/CouchotHGWB14} where \textit{CI} stands for +\emph{Chaotic Iterations}. We have firstly proven in~\cite{bcgr11:ip} +that, to establish the chaotic nature of +$\textit{CIPRNG}_f^1$ algorithm, 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 +as well. +However, it cannot be directly deduced that +$\chi_{\textit{14Secrypt}}$ is chaotic since we do not output all the +successive values of iterating $G_f$. This algorithm only displays a +subsequence $x^{b.n}$ of a whole chaotic sequence $x^{n}$ and it is +indeed incorrect to say that the chaos property is preserved for any +subsequence of a chaotic sequence. This article presents conditions +to preserve this property. -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. +Finding a Boolean function which provides a strongly connected +iteration graph having a doubly stochastic Markov matrix is however +not an easy task. +We have firstly proposed in~\cite{bcgr11:ip} a generate-and-test based +approach that solved this issue. However, this one was not efficient enough. +Thus, a second scheme has been further presented +in~\cite{DBLP:conf/secrypt/CouchotHGWB14} by remarking that +a $\mathsf{N}$-cube where an Hamiltonian cycle (or equivalently a Gray code) +has been removed is strongly connected and has +a doubly stochastic Markov matrix. -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. +However, the removed Hamiltonian cycle +has a great influence in the quality of the output. +For instance, if this one is not balanced (\textit{i.e.}, +the number of changes in different bits are completely different), +some bits would be hard to switch. +This article shows an effective algorithm that efficiently +implements the previous scheme and thus provides functions issued +from removing, in the $\mathsf{N}$-cube, a \emph{balanced} Hamiltonian cycle. +The length $b$ of the walk to reach a +distribution close to the uniform one would be dramatically long. +This article theoretically and practically +studies the length $b$ until the corresponding Markov +chain is close to the uniform distribution. +Finally, the ability of the approach to face classical tests +suite is 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. +This article, which +is an extension of~\cite{DBLP:conf/secrypt/CouchotHGWB14}, +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 proof of chaos of our most general PRNGs is +provided. This is the first major contribution. +Section~\ref{sec:SCCfunc} recalls a general scheme +to obtain functions with an expected behavior. Main theorems are recalled +to make the article self-sufficient. +The next section (Sect.~\ref{sec:hamilton}) presents an algorithm that +implements this scheme and proves that it always produces a solution. +This is the second major contribution. +Then, Section~\ref{sec:hypercube} defines the theoretical framework to study +the mixing-time, \textit{i.e.}, +the sufficient amont of time until reaching an uniform +distribution. It proves that this one is in the worst case quadratic in the number +of elements. Experiments show that the bound is in practice +significantly lower. This is the third major contribution. +Section~\ref{sec:prng} gives practical results on evaluating the PRNG +against the NIST suite. This research work ends with a conclusion +section, where the contribution is summarized and intended future work +is outlined. + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "main" +%%% ispell-dictionary: "american" +%%% mode: flyspell +%%% End: