X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/236f25b2f3a081b11c71bedad6d044d695ce2cca..8dfce25f59a57787b53e1ba55971a5c4f8d5993f:/intro.tex?ds=inline diff --git a/intro.tex b/intro.tex index 10463ea..e66a6b4 100644 --- a/intro.tex +++ b/intro.tex @@ -1,28 +1,29 @@ The exploitation of chaotic systems to generate pseudorandom sequences -is a hot topic~\cite{915396,915385,5376454}. Such systems are -fundamentally chosen due to their unpredictable character and their +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 It -thus remains to find optimal parameters in such functions so that -attractors are avoided, hoping by doing so that the generated numbers +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, it is usual to test the PRNGs (Pseudo-Random Number -Generators) with statistical batteries like the so-called +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 +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 \emph{strongly sensitive to the initial conditions} if +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)$, are larger than $\epsilon$. However, +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}. Functions evoked above have been studied according +\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 @@ -35,11 +36,11 @@ 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} means +\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 algorithm -$\textit{CIPRNG}_f^1$, it is necessary and sufficient that the +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 @@ -47,13 +48,13 @@ 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. +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 not correct that the chaos property is preserved for any +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. @@ -62,7 +63,7 @@ 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 solves this issue. However, this one was not efficient enough. +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) @@ -71,12 +72,12 @@ a doubly stochastic Markov matrix. However, the removed Hamiltonian cycle has a great influence in the quality of the output. -For instance, if this one one is not balanced (\textit{i.e.}, +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 provides thus functions issued -from removing in the $\mathsf{N}$-cube a \emph{balanced} Hamiltonian cycle. +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. @@ -88,27 +89,28 @@ suite is evaluated. - -The remainder of this article is organized as follows. The next +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 proofs of chaos of our most general PRNGs 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 awaited behavior. Main theorems are recalled -to make the document self-content. +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 it always produces a solution. -This is the second major contribution -The later section -(Sect.~\ref{sec:hypercube}) defines the theoretical framework to study -the mixing-time, \textit{i.e.}, time until reaching a uniform -distribution. It proves that this one is at worth quadratic in the number -of elements. Experiments show that the bound is practically largely much -lower. This is the third major contribution. The +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 by a conclusion +against the NIST suite. This research work ends with a conclusion section, where the contribution is summarized and intended future work is outlined.