X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/860ecbe3a673a4ac258e24e6c0284a56e3427b6e..a12a11a39f112c043de69e8694f29b32b8c7dbc5:/prng_gpu.tex diff --git a/prng_gpu.tex b/prng_gpu.tex index 34ec700..a32d94a 100644 --- a/prng_gpu.tex +++ b/prng_gpu.tex @@ -11,6 +11,11 @@ \usepackage[ruled,vlined]{algorithm2e} \usepackage{listings} \usepackage[standard]{ntheorem} +\usepackage{algorithmic} +\usepackage{slashbox} +\usepackage{ctable} +\usepackage{tabularx} +\usepackage{multirow} % Pour mathds : les ensembles IR, IN, etc. \usepackage{dsfont} @@ -35,6 +40,9 @@ \newcommand{\alert}[1]{\begin{color}{blue}\textit{#1}\end{color}} + +\newcommand{\PCH}[1]{\begin{color}{blue}#1\end{color}} + \title{Efficient and Cryptographically Secure Generation of Chaotic Pseudorandom Numbers on GPU} \begin{document} @@ -85,7 +93,13 @@ On the other side, speed is not the main requirement in cryptography: the great need is to define \emph{secure} generators able to withstand malicious attacks. Roughly speaking, an attacker should not be able in practice to make the distinction between numbers obtained with the secure generator and a true random -sequence. +sequence. \begin{color}{red} Or, in an equivalent formulation, he or she should not be +able (in practice) to predict the next bit of the generator, having the knowledge of all the +binary digits that have been already released. ``Being able in practice'' refers here +to the possibility to achieve this attack in polynomial time, and to the exponential growth +of the difficulty of this challenge when the size of the parameters of the PRNG increases. +\end{color} + Finally, a small part of the community working in this domain focuses on a third requirement, that is to define chaotic generators. The main idea is to take benefits from a chaotic dynamical system to obtain a @@ -119,10 +133,19 @@ statistical perfection refers to the ability to pass the whole {\it BigCrush} battery of tests, which is widely considered as the most stringent statistical evaluation of a sequence claimed as random. This battery can be found in the well-known TestU01 package~\cite{LEcuyerS07}. +\begin{color}{red} +More precisely, each time we performed a test on a PRNG, we ran it +twice in order to observe if all $p-$values are inside [0.01, 0.99]. In +fact, we observed that few $p-$values (less than ten) are sometimes +outside this interval but inside [0.001, 0.999], so that is why a +second run allows us to confirm that the values outside are not for +the same test. With this approach all our PRNGs pass the {\it + BigCrush} successfully and all $p-$values are at least once inside +[0.01, 0.99]. +\end{color} Chaos, for its part, refers to the well-established definition of a chaotic dynamical system proposed by Devaney~\cite{Devaney}. - In a previous work~\cite{bgw09:ip,guyeux10} we have proposed a post-treatment on PRNGs making them behave as a chaotic dynamical system. Such a post-treatment leads to a new category of PRNGs. We have shown that proofs of Devaney's chaos can be established for this @@ -146,14 +169,38 @@ property. Last, but not least, we propose a rewriting of the Blum-Goldwasser asymmetric key encryption protocol by using the proposed method. + +\PCH{ +{\bf Main contributions.} In this paper a new PRNG using chaotic iteration +is defined. From a theoretical point of view, it is proved that it has fine +topological chaotic properties and that it is cryptographically secured (when +the based PRNG is also cryptographically secured). From a practical point of +view, experiments point out a very good statistical behavior. Optimized +original implementation of this PRNG are also proposed and experimented. +Pseudo-random numbers are generated at a rate of 20GSamples/s which is faster +than in~\cite{conf/fpga/ThomasHL09,Marsaglia2003} (and with a better +statistical behavior). Experiments are also provided using BBS as the based +random generator. The generation speed is significantly weaker but, as far +as we know, it is the first cryptographically secured PRNG proposed on GPU. +Note too that an original qualitative comparison between topological chaotic +properties and statistical test is also proposed. +} + + + The remainder of this paper is organized as follows. In Section~\ref{section:related works} we review some GPU implementations of PRNGs. Section~\ref{section:BASIC RECALLS} gives some basic recalls on the well-known Devaney's formulation of chaos, and on an iteration process called ``chaotic iterations'' on which the post-treatment is based. The proposed PRNG and its proof of chaos are given in Section~\ref{sec:pseudorandom}. -Section~\ref{sec:efficient PRNG} presents an efficient -implementation of this chaotic PRNG on a CPU, whereas Section~\ref{sec:efficient PRNG +\begin{color}{red} +Section~\ref{The generation of pseudorandom sequence} illustrates the statistical +improvement related to the chaotic iteration based post-treatment, for +our previously released PRNGs and a new efficient +implementation on CPU. +\end{color} + Section~\ref{sec:efficient PRNG gpu} describes and evaluates theoretically the GPU implementation. Such generators are experimented in Section~\ref{sec:experiments}. @@ -162,7 +209,8 @@ generator is cryptographically secure, then it is the case too for the generator provided by the post-treatment. Such a proof leads to the proposition of a cryptographically secure and chaotic generator on GPU based on the famous Blum Blum Shub -in Section~\ref{sec:CSGPU}, and to an improvement of the +in Section~\ref{sec:CSGPU}, \begin{color}{red} to a practical +security evaluation in Section~\ref{sec:Practicak evaluation}, \end{color} and to an improvement of the Blum-Goldwasser protocol in Sect.~\ref{Blum-Goldwasser}. This research work ends by a conclusion section, in which the contribution is summarized and intended future work is presented. @@ -170,7 +218,7 @@ summarized and intended future work is presented. -\section{Related works on GPU based PRNGs} +\section{Related work on GPU based PRNGs} \label{section:related works} Numerous research works on defining GPU based PRNGs have already been proposed in the @@ -229,7 +277,7 @@ with basic notions on topology (see for instance~\cite{Devaney}). \subsection{Devaney's Chaotic Dynamical Systems} - +\label{subsec:Devaney} In the sequel $S^{n}$ denotes the $n^{th}$ term of a sequence $S$ and $V_{i}$ denotes the $i^{th}$ component of a vector $V$. $f^{k}=f\circ ...\circ f$ is for the $k^{th}$ composition of a function $f$. Finally, the following @@ -416,7 +464,7 @@ the metric space $(\mathcal{X},d)$. \end{proposition} The chaotic property of $G_f$ has been firstly established for the vectorial -Boolean negation $f(x_1,\hdots, x_\mathsf{N}) = (\overline{x_1},\hdots, \overline{x_\mathsf{N}})$ \cite{guyeux10}. To obtain a characterization, we have secondly +Boolean negation $f_0(x_1,\hdots, x_\mathsf{N}) = (\overline{x_1},\hdots, \overline{x_\mathsf{N}})$ \cite{guyeux10}. To obtain a characterization, we have secondly introduced the notion of asynchronous iteration graph recalled bellow. Let $f$ be a map from $\mathds{B}^\mathsf{N}$ to itself. The @@ -473,33 +521,58 @@ Let us finally remark that the vectorial negation satisfies the hypotheses of bo We have proposed in~\cite{bgw09:ip} a new family of generators that receives two PRNGs as inputs. These two generators are mixed with chaotic iterations, -leading thus to a new PRNG that improves the statistical properties of each -generator taken alone. Furthermore, our generator -possesses various chaos properties that none of the generators used as input +leading thus to a new PRNG that +\begin{color}{red} +should improve the statistical properties of each +generator taken alone. +Furthermore, the generator obtained by this way possesses various chaos properties that none of the generators used as input present. + \begin{algorithm}[h!] \begin{small} \KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ ($n$ bits)} \KwOut{a configuration $x$ ($n$ bits)} $x\leftarrow x^0$\; -$k\leftarrow b + \textit{XORshift}(b)$\; +$k\leftarrow b + PRNG_1(b)$\; \For{$i=0,\dots,k$} { -$s\leftarrow{\textit{XORshift}(n)}$\; +$s\leftarrow{PRNG_2(n)}$\; $x\leftarrow{F_f(s,x)}$\; } return $x$\; \end{small} -\caption{PRNG with chaotic functions} +\caption{An arbitrary round of $Old~ CI~ PRNG_f(PRNG_1,PRNG_2)$} \label{CI Algorithm} \end{algorithm} +This generator is synthesized in Algorithm~\ref{CI Algorithm}. +It takes as input: a Boolean function $f$ satisfying Theorem~\ref{Th:Caractérisation des IC chaotiques}; +an integer $b$, ensuring that the number of executed iterations +between two outputs is at least $b$ +and at most $2b+1$; and an initial configuration $x^0$. +It returns the new generated configuration $x$. Internally, it embeds two +inputted generators $PRNG_i(k), i=1,2$, + which must return integers +uniformly distributed +into $\llbracket 1 ; k \rrbracket$. +For instance, these PRNGs can be the \textit{XORshift}~\cite{Marsaglia2003}, +being a category of very fast PRNGs designed by George Marsaglia +that repeatedly uses the transform of exclusive or (XOR, $\oplus$) on a number +with a bit shifted version of it. Such a PRNG, which has a period of +$2^{32}-1=4.29\times10^9$, is summed up in Algorithm~\ref{XORshift}. +This XORshift, or any other reasonable PRNG, is used +in our own generator to compute both the number of iterations between two +outputs (provided by $PRNG_1$) and the strategy elements ($PRNG_2$). + +%This former generator has successively passed various batteries of statistical tests, as the NIST~\cite{bcgr11:ip}, DieHARD~\cite{Marsaglia1996}, and TestU01~\cite{LEcuyerS07} ones. + + \begin{algorithm}[h!] \begin{small} \KwIn{the internal configuration $z$ (a 32-bit word)} @@ -515,31 +588,94 @@ return $y$\; \end{algorithm} +\subsection{A ``New CI PRNG''} + +In order to make the Old CI PRNG usable in practice, we have proposed +an adapted version of the chaotic iteration based generator in~\cite{bg10:ip}. +In this ``New CI PRNG'', we prevent from changing twice a given +bit between two outputs. +This new generator is designed by the following process. + +First of all, some chaotic iterations have to be done to generate a sequence +$\left(x^n\right)_{n\in\mathds{N}} \in \left(\mathds{B}^{32}\right)^\mathds{N}$ +of Boolean vectors, which are the successive states of the iterated system. +Some of these vectors will be randomly extracted and our pseudorandom bit +flow will be constituted by their components. Such chaotic iterations are +realized as follows. Initial state $x^0 \in \mathds{B}^{32}$ is a Boolean +vector taken as a seed and chaotic strategy $\left(S^n\right)_{n\in\mathds{N}}\in +\llbracket 1, 32 \rrbracket^\mathds{N}$ is +an \emph{irregular decimation} of $PRNG_2$ sequence, as described in +Algorithm~\ref{Chaotic iteration1}. + +Then, at each iteration, only the $S^n$-th component of state $x^n$ is +updated, as follows: $x_i^n = x_i^{n-1}$ if $i \neq S^n$, else $x_i^n = \overline{x_i^{n-1}}$. +Such a procedure is equivalent to achieve chaotic iterations with +the Boolean vectorial negation $f_0$ and some well-chosen strategies. +Finally, some $x^n$ are selected +by a sequence $m^n$ as the pseudorandom bit sequence of our generator. +$(m^n)_{n \in \mathds{N}} \in \mathcal{M}^\mathds{N}$ is computed from $PRNG_1$, where $\mathcal{M}\subset \mathds{N}^*$ is a finite nonempty set of integers. + +The basic design procedure of the New CI generator is summarized in Algorithm~\ref{Chaotic iteration1}. +The internal state is $x$, the output state is $r$. $a$ and $b$ are those computed by the two input +PRNGs. Lastly, the value $g(a)$ is an integer defined as in Eq.~\ref{Formula}. +This function must be chosen such that the outputs of the resulted PRNG are uniform in $\llbracket 0, 2^\mathsf{N}-1 \rrbracket$. Function of \eqref{Formula} achieves this +goal (other candidates and more information can be found in ~\cite{bg10:ip}). +\begin{equation} +\label{Formula} +m^n = g(y^n)= +\left\{ +\begin{array}{l} +0 \text{ if }0 \leqslant{y^n}<{C^0_{32}},\\ +1 \text{ if }{C^0_{32}} \leqslant{y^n}<\sum_{i=0}^1{C^i_{32}},\\ +2 \text{ if }\sum_{i=0}^1{C^i_{32}} \leqslant{y^n}<\sum_{i=0}^2{C^i_{32}},\\ +\vdots~~~~~ ~~\vdots~~~ ~~~~\\ +N \text{ if }\sum_{i=0}^{N-1}{C^i_{32}}\leqslant{y^n}<1.\\ +\end{array} +\right. +\end{equation} - -This generator is synthesized in Algorithm~\ref{CI Algorithm}. -It takes as input: a Boolean function $f$ satisfying Theorem~\ref{Th:Caractérisation des IC chaotiques}; -an integer $b$, ensuring that the number of executed iterations is at least $b$ -and at most $2b+1$; and an initial configuration $x^0$. -It returns the new generated configuration $x$. Internally, it embeds two -\textit{XORshift}$(k)$ PRNGs~\cite{Marsaglia2003} that return integers -uniformly distributed -into $\llbracket 1 ; k \rrbracket$. -\textit{XORshift} is a category of very fast PRNGs designed by George Marsaglia, -which repeatedly uses the transform of exclusive or (XOR, $\oplus$) on a number -with a bit shifted version of it. This PRNG, which has a period of -$2^{32}-1=4.29\times10^9$, is summed up in Algorithm~\ref{XORshift}. It is used -in our PRNG to compute the strategy length and the strategy elements. - -This former generator has successively passed various batteries of statistical tests, as the NIST~\cite{bcgr11:ip}, DieHARD~\cite{Marsaglia1996}, and TestU01~\cite{LEcuyerS07} ones. +\begin{algorithm} +\textbf{Input:} the internal state $x$ (32 bits)\\ +\textbf{Output:} a state $r$ of 32 bits +\begin{algorithmic}[1] +\FOR{$i=0,\dots,N$} +{ +\STATE$d_i\leftarrow{0}$\; +} +\ENDFOR +\STATE$a\leftarrow{PRNG_1()}$\; +\STATE$k\leftarrow{g(a)}$\; +\WHILE{$i=0,\dots,k$} + +\STATE$b\leftarrow{PRNG_2()~mod~\mathsf{N}}$\; +\STATE$S\leftarrow{b}$\; + \IF{$d_S=0$} + { +\STATE $x_S\leftarrow{ \overline{x_S}}$\; +\STATE $d_S\leftarrow{1}$\; + + } + \ELSIF{$d_S=1$} + { +\STATE $k\leftarrow{ k+1}$\; + }\ENDIF +\ENDWHILE\\ +\STATE $r\leftarrow{x}$\; +\STATE return $r$\; +\medskip +\caption{An arbitrary round of the new CI generator} +\label{Chaotic iteration1} +\end{algorithmic} +\end{algorithm} +\end{color} \subsection{Improving the Speed of the Former Generator} -Instead of updating only one cell at each iteration, we can try to choose a -subset of components and to update them together. Such an attempt leads -to a kind of merger of the two sequences used in Algorithm -\ref{CI Algorithm}. When the updating function is the vectorial negation, +Instead of updating only one cell at each iteration,\begin{color}{red} we now propose to choose a +subset of components and to update them together, for speed improvements. Such a proposition leads\end{color} +to a kind of merger of the two sequences used in Algorithms +\ref{CI Algorithm} and \ref{Chaotic iteration1}. When the updating function is the vectorial negation, this algorithm can be rewritten as follows: \begin{equation} @@ -580,9 +716,12 @@ than the ones presented in Definition \ref{Def:chaotic iterations} because, inst we select a subset of components to change. -Obviously, replacing Algorithm~\ref{CI Algorithm} by +Obviously, replacing the previous CI PRNG Algorithms by Equation~\ref{equation Oplus}, which is possible when the iteration function is -the vectorial negation, leads to a speed improvement. However, proofs +the vectorial negation, leads to a speed improvement +(the resulting generator will be referred as ``Xor CI PRNG'' +in what follows). +However, proofs of chaos obtained in~\cite{bg10:ij} have been established only for chaotic iterations of the form presented in Definition \ref{Def:chaotic iterations}. The question is now to determine whether the @@ -761,6 +900,8 @@ the distance between $(S^n,E^n)$ and $(S,E)$ is strictly less than $% In conclusion, %%RAPH : ici j'ai rajouté une ligne +%%TOF : ici j'ai rajouté un commentaire +%%TOF : ici aussi $ \forall \varepsilon >0,$ $\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N} ,$ $\forall n\geqslant N_{0},$ @@ -835,21 +976,345 @@ have $d((S,E),(\tilde S,E))<\epsilon$. \end{proof} +\begin{color}{red} +\section{Statistical Improvements Using Chaotic Iterations} + +\label{The generation of pseudorandom sequence} + + +Let us now explain why we are reasonable grounds to believe that chaos +can improve statistical properties. +We will show in this section that chaotic properties as defined in the +mathematical theory of chaos are related to some statistical tests that can be found +in the NIST battery. Furthermore, we will check that, when mixing defective PRNGs with +chaotic iterations, the new generator presents better statistical properties +(this section summarizes and extends the work of~\cite{bfg12a:ip}). + -\section{Efficient PRNG based on Chaotic Iterations} -\label{sec:efficient PRNG} -Based on the proof presented in the previous section, it is now possible to -improve the speed of the generator formerly presented in~\cite{bgw09:ip,guyeux10}. -The first idea is to consider -that the provided strategy is a pseudorandom Boolean vector obtained by a -given PRNG. -An iteration of the system is simply the bitwise exclusive or between -the last computed state and the current strategy. -Topological properties of disorder exhibited by chaotic -iterations can be inherited by the inputted generator, we hope by doing so to -obtain some statistical improvements while preserving speed. +\subsection{Qualitative relations between topological properties and statistical tests} + + +There are various relations between topological properties that describe an unpredictable behavior for a discrete +dynamical system on the one +hand, and statistical tests to check the randomness of a numerical sequence +on the other hand. These two mathematical disciplines follow a similar +objective in case of a recurrent sequence (to characterize an intrinsically complicated behavior for a +recurrent sequence), with two different but complementary approaches. +It is true that the following illustrative links give only qualitative arguments, +and proofs should be provided later to make such arguments irrefutable. However +they give a first understanding of the reason why we think that chaotic properties should tend +to improve the statistical quality of PRNGs. +% +Let us now list some of these relations between topological properties defined in the mathematical +theory of chaos and tests embedded into the NIST battery. %Such relations need to be further +%investigated, but they presently give a first illustration of a trend to search similar properties in the +%two following fields: mathematical chaos and statistics. + + +\begin{itemize} + \item \textbf{Regularity}. As stated in Section~\ref{subsec:Devaney}, a chaotic dynamical system must +have an element of regularity. Depending on the chosen definition of chaos, this element can be the existence of +a dense orbit, the density of periodic points, etc. The key idea is that a dynamical system with no periodicity +is not as chaotic as a system having periodic orbits: in the first situation, we can predict something and gain a +knowledge about the behavior of the system, that is, it never enters into a loop. A similar importance for periodicity is emphasized in +the two following NIST tests~\cite{Nist10}: + \begin{itemize} + \item \textbf{Non-overlapping Template Matching Test}. Detect generators that produce too many occurrences of a given non-periodic (aperiodic) pattern. + \item \textbf{Discrete Fourier Transform (Spectral) Test}. Detect periodic features (i.e., repetitive patterns that are near each other) in the tested sequence that would indicate a deviation from the assumption of randomness. + \end{itemize} + +\item \textbf{Transitivity}. This topological property introduced previously states that the dynamical system is intrinsically complicated: it cannot be simplified into +two subsystems that do not interact, as we can find in any neighborhood of any point another point whose orbit visits the whole phase space. +This focus on the places visited by orbits of the dynamical system takes various nonequivalent formulations in the mathematical theory +of chaos, namely: transitivity, strong transitivity, total transitivity, topological mixing, and so on~\cite{bg10:ij}. A similar attention +is brought on states visited during a random walk in the two tests below~\cite{Nist10}: + \begin{itemize} + \item \textbf{Random Excursions Variant Test}. Detect deviations from the expected number of visits to various states in the random walk. + \item \textbf{Random Excursions Test}. Determine if the number of visits to a particular state within a cycle deviates from what one would expect for a random sequence. + \end{itemize} + +\item \textbf{Chaos according to Li and Yorke}. Two points of the phase space $(x,y)$ define a couple of Li-Yorke when $\limsup_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))>0$ et $\liminf_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))=0$, meaning that their orbits always oscillates as the iterations pass. When a system is compact and contains an uncountable set of such points, it is claimed as chaotic according +to Li-Yorke~\cite{Li75,Ruette2001}. A similar property is regarded in the following NIST test~\cite{Nist10}. + \begin{itemize} + \item \textbf{Runs Test}. To determine whether the number of runs of ones and zeros of various lengths is as expected for a random sequence. In particular, this test determines whether the oscillation between such zeros and ones is too fast or too slow. + \end{itemize} + \item \textbf{Topological entropy}. The desire to formulate an equivalency of the thermodynamics entropy +has emerged both in the topological and statistical fields. Another time, a similar objective has led to two different +rewritten of an entropy based disorder: the famous Shannon definition of entropy is approximated in the statistical approach, +whereas topological entropy is defined as follows. +$x,y \in \mathcal{X}$ are $\varepsilon-$\emph{separated in time $n$} if there exists $k \leqslant n$ such that $d\left(f^{(k)}(x),f^{(k)}(y)\right)>\varepsilon$. Then $(n,\varepsilon)-$separated sets are sets of points that are all $\varepsilon-$separated in time $n$, which +leads to the definition of $s_n(\varepsilon,Y)$, being the maximal cardinality of all $(n,\varepsilon)-$separated sets. Using these notations, +the topological entropy is defined as follows: $$h_{top}(\mathcal{X},f) = \displaystyle{\lim_{\varepsilon \rightarrow 0} \Big[ \limsup_{n \rightarrow +\infty} \dfrac{1}{n} \log s_n(\varepsilon,\mathcal{X})\Big]}.$$ +This value measures the average exponential growth of the number of distinguishable orbit segments. +In this sense, it measures complexity of the topological dynamical system, whereas +the Shannon approach is in mind when defining the following test~\cite{Nist10}: + \begin{itemize} +\item \textbf{Approximate Entropy Test}. Compare the frequency of overlapping blocks of two consecutive/adjacent lengths ($m$ and $m+1$) against the expected result for a random sequence. + \end{itemize} + + \item \textbf{Non-linearity, complexity}. Finally, let us remark that non-linearity and complexity are +not only sought in general to obtain chaos, but they are also required for randomness, as illustrated by the two tests below~\cite{Nist10}. + \begin{itemize} +\item \textbf{Binary Matrix Rank Test}. Check for linear dependence among fixed length substrings of the original sequence. +\item \textbf{Linear Complexity Test}. Determine whether or not the sequence is complex enough to be considered random. + \end{itemize} +\end{itemize} + +We have proven in our previous works~\cite{guyeux12:bc} that chaotic iterations satisfying Theorem~\ref{Th:Caractérisation des IC chaotiques} are, among other +things, strongly transitive, topologically mixing, chaotic as defined by Li and Yorke, +and that they have a topological entropy and an exponent of Lyapunov both equal to $ln(\mathsf{N})$, +where $\mathsf{N}$ is the size of the iterated vector. +These topological properties make that we are ground to believe that a generator based on chaotic +iterations will probably be able to pass all the existing statistical batteries for pseudorandomness like +the NIST one. The following subsections, in which we prove that defective generators have their +statistical properties improved by chaotic iterations, show that such an assumption is true. + +\subsection{Details of some Existing Generators} + +The list of defective PRNGs we will use +as inputs for the statistical tests to come is introduced here. + +Firstly, the simple linear congruency generators (LCGs) will be used. +They are defined by the following recurrence: +\begin{equation} +x^n = (ax^{n-1} + c)~mod~m, +\label{LCG} +\end{equation} +where $a$, $c$, and $x^0$ must be, among other things, non-negative and less than +$m$~\cite{LEcuyerS07}. In what follows, 2LCGs and 3LCGs refer as two (resp. three) +combinations of such LCGs. For further details, see~\cite{bfg12a:ip,combined_lcg}. + +Secondly, the multiple recursive generators (MRGs) will be used, which +are based on a linear recurrence of order +$k$, modulo $m$~\cite{LEcuyerS07}: +\begin{equation} +x^n = (a^1x^{n-1}+~...~+a^kx^{n-k})~mod~m . +\label{MRG} +\end{equation} +Combination of two MRGs (referred as 2MRGs) is also used in these experiments. + +Generators based on linear recurrences with carry will be regarded too. +This family of generators includes the add-with-carry (AWC) generator, based on the recurrence: +\begin{equation} +\label{AWC} +\begin{array}{l} +x^n = (x^{n-r} + x^{n-s} + c^{n-1})~mod~m, \\ +c^n= (x^{n-r} + x^{n-s} + c^{n-1}) / m, \end{array}\end{equation} +the SWB generator, having the recurrence: +\begin{equation} +\label{SWB} +\begin{array}{l} +x^n = (x^{n-r} - x^{n-s} - c^{n-1})~mod~m, \\ +c^n=\left\{ +\begin{array}{l} +1 ~~~~~\text{if}~ (x^{i-r} - x^{i-s} - c^{i-1})<0\\ +0 ~~~~~\text{else},\end{array} \right. \end{array}\end{equation} +and the SWC generator designed by R. Couture, which is based on the following recurrence: +\begin{equation} +\label{SWC} +\begin{array}{l} +x^n = (a^1x^{n-1} \oplus ~...~ \oplus a^rx^{n-r} \oplus c^{n-1}) ~ mod ~ 2^w, \\ +c^n = (a^1x^{n-1} \oplus ~...~ \oplus a^rx^{n-r} \oplus c^{n-1}) ~ / ~ 2^w. \end{array}\end{equation} + +Then the generalized feedback shift register (GFSR) generator has been implemented, that is: +\begin{equation} +x^n = x^{n-r} \oplus x^{n-k} . +\label{GFSR} +\end{equation} + + +Finally, the nonlinear inversive (INV) generator~\cite{LEcuyerS07} has been studied, which is: + +\begin{equation} +\label{INV} +\begin{array}{l} +x^n=\left\{ +\begin{array}{ll} +(a^1 + a^2 / z^{n-1})~mod~m & \text{if}~ z^{n-1} \neq 0 \\ +a^1 & \text{if}~ z^{n-1} = 0 .\end{array} \right. \end{array}\end{equation} + + + +\begin{table} +\renewcommand{\arraystretch}{1.3} +\caption{TestU01 Statistical Test} +\label{TestU011} +\centering + \begin{tabular}{lccccc} + \toprule +Test name &Tests& Logistic & XORshift & ISAAC\\ +Rabbit & 38 &21 &14 &0 \\ +Alphabit & 17 &16 &9 &0 \\ +Pseudo DieHARD &126 &0 &2 &0 \\ +FIPS\_140\_2 &16 &0 &0 &0 \\ +SmallCrush &15 &4 &5 &0 \\ +Crush &144 &95 &57 &0 \\ +Big Crush &160 &125 &55 &0 \\ \hline +Failures & &261 &146 &0 \\ +\bottomrule + \end{tabular} +\end{table} + + + +\begin{table} +\renewcommand{\arraystretch}{1.3} +\caption{TestU01 Statistical Test for Old CI algorithms ($\mathsf{N}=4$)} +\label{TestU01 for Old CI} +\centering + \begin{tabular}{lcccc} + \toprule +\multirow{3}*{Test name} & \multicolumn{4}{c}{Old CI}\\ +&Logistic& XORshift& ISAAC&ISAAC \\ +&+& +& + & + \\ +&Logistic& XORshift& XORshift&ISAAC \\ \cmidrule(r){2-5} +Rabbit &7 &2 &0 &0 \\ +Alphabit & 3 &0 &0 &0 \\ +DieHARD &0 &0 &0 &0 \\ +FIPS\_140\_2 &0 &0 &0 &0 \\ +SmallCrush &2 &0 &0 &0 \\ +Crush &47 &4 &0 &0 \\ +Big Crush &79 &3 &0 &0 \\ \hline +Failures &138 &9 &0 &0 \\ +\bottomrule + \end{tabular} +\end{table} + + + + + +\subsection{Statistical tests} +\label{Security analysis} + +Three batteries of tests are reputed and usually used +to evaluate the statistical properties of newly designed pseudorandom +number generators. These batteries are named DieHard~\cite{Marsaglia1996}, +the NIST suite~\cite{ANDREW2008}, and the most stringent one called +TestU01~\cite{LEcuyerS07}, which encompasses the two other batteries. + + + +\label{Results and discussion} +\begin{table*} +\renewcommand{\arraystretch}{1.3} +\caption{NIST and DieHARD tests suite passing rates for PRNGs without CI} +\label{NIST and DieHARD tests suite passing rate the for PRNGs without CI} +\centering + \begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|} + \hline\hline +Types of PRNGs & \multicolumn{2}{c|}{Linear PRNGs} & \multicolumn{4}{c|}{Lagged PRNGs} & \multicolumn{1}{c|}{ICG PRNGs} & \multicolumn{3}{c|}{Mixed PRNGs}\\ \hline +\backslashbox{\textbf{$Tests$}} {\textbf{$PRNG$}} & LCG& MRG& AWC & SWB & SWC & GFSR & INV & LCG2& LCG3& MRG2 \\ \hline +NIST & 11/15 & 14/15 &\textbf{15/15} & \textbf{15/15} & 14/15 & 14/15 & 14/15 & 14/15& 14/15& 14/15 \\ \hline +DieHARD & 16/18 & 16/18 & 15/18 & 16/18 & \textbf{18/18} & 16/18 & 16/18 & 16/18& 16/18& 16/18\\ \hline +\end{tabular} +\end{table*} + +Table~\ref{NIST and DieHARD tests suite passing rate the for PRNGs without CI} shows the +results on the two firsts batteries recalled above, indicating that all the PRNGs presented +in the previous section +cannot pass all these tests. In other words, the statistical quality of these PRNGs cannot +fulfill the up-to-date standards presented previously. We have shown in~\cite{bfg12a:ip} that the use of chaotic +iterations can solve this issue. +%More precisely, to +%illustrate the effects of chaotic iterations on these defective PRNGs, experiments have been divided in three parts~\cite{bfg12a:ip}: +%\begin{enumerate} +% \item \textbf{Single CIPRNG}: The PRNGs involved in CI computing are of the same category. +% \item \textbf{Mixed CIPRNG}: Two different types of PRNGs are mixed during the chaotic iterations process. +% \item \textbf{Multiple CIPRNG}: The generator is obtained by repeating the composition of the iteration function as follows: $x^0\in \mathds{B}^{\mathsf{N}}$, and $\forall n\in \mathds{N}^{\ast },\forall i\in \llbracket1;\mathsf{N}\rrbracket, x_i^n=$ +%\begin{equation} +%\begin{array}{l} +%\left\{ +%\begin{array}{l} +%x_i^{n-1}~~~~~\text{if}~S^n\neq i \\ +%\forall j\in \llbracket1;\mathsf{m}\rrbracket,f^m(x^{n-1})_{S^{nm+j}}~\text{if}~S^{nm+j}=i.\end{array} \right. \end{array} +%\end{equation} +%$m$ is called the \emph{functional power}. +%\end{enumerate} +% +The obtained results are reproduced in Table +\ref{NIST and DieHARD tests suite passing rate the for single CIPRNGs}. +The scores written in boldface indicate that all the tests have been passed successfully, whereas an +asterisk ``*'' means that the considered passing rate has been improved. +The improvements are obvious for both the ``Old CI'' and ``New CI'' generators. +Concerning the ``Xor CI PRNG'', the score is less spectacular: a large speed improvement makes that statistics + are not as good as for the two other versions of these CIPRNGs. +However 8 tests have been improved (with no deflation for the other results). + + +\begin{table*} +\renewcommand{\arraystretch}{1.3} +\caption{NIST and DieHARD tests suite passing rates for PRNGs with CI} +\label{NIST and DieHARD tests suite passing rate the for single CIPRNGs} +\centering + \begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|c|c|} + \hline +Types of PRNGs & \multicolumn{2}{c|}{Linear PRNGs} & \multicolumn{4}{c|}{Lagged PRNGs} & \multicolumn{1}{c|}{ICG PRNGs} & \multicolumn{3}{c|}{Mixed PRNGs}\\ \hline +\backslashbox{\textbf{$Tests$}} {\textbf{$Single~CIPRNG$}} & LCG & MRG & AWC & SWB & SWC & GFSR & INV& LCG2 & LCG3& MRG2 \\ \hline\hline +Old CIPRNG\\ \hline \hline +NIST & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} \\ \hline +DieHARD & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} * \\ \hline +New CIPRNG\\ \hline \hline +NIST & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} \\ \hline +DieHARD & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} *\\ \hline +Xor CIPRNG\\ \hline\hline +NIST & 14/15*& \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & 14/15 & \textbf{15/15} * & 14/15& \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} \\ \hline +DieHARD & 16/18 & 16/18 & 17/18* & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & 16/18 & 16/18 & 16/18& 16/18\\ \hline +\end{tabular} +\end{table*} + + +We have then investigate in~\cite{bfg12a:ip} if it is possible to improve +the statistical behavior of the Xor CI version by combining more than one +$\oplus$ operation. Results are summarized in Table~\ref{threshold}, illustrating +the progressive increasing effects of chaotic iterations, when giving time to chaos to get settled in. +Thus rapid and perfect PRNGs, regarding the NIST and DieHARD batteries, can be obtained +using chaotic iterations on defective generators. + +\begin{table*} +\renewcommand{\arraystretch}{1.3} +\caption{Number of $\oplus$ operations to pass the whole NIST and DieHARD batteries} +\label{threshold} +\centering + \begin{tabular}{|l||c|c|c|c|c|c|c|c|} + \hline +Inputted $PRNG$ & LCG & MRG & SWC & GFSR & INV& LCG2 & LCG3 & MRG2 \\ \hline\hline +Threshold value $m$& 19 & 7 & 2& 1 & 11& 9& 3& 4\\ \hline\hline +\end{tabular} +\end{table*} + +Finally, the TestU01 battery has been launched on three well-known generators +(a logistic map, a simple XORshift, and the cryptographically secure ISAAC, +see Table~\ref{TestU011}). These results can be compared with +Table~\ref{TestU01 for Old CI}, which gives the scores obtained by the +Old CI PRNG that has received these generators. +The obvious improvement speaks for itself, and together with the other +results recalled in this section, it reinforces the opinion that a strong +correlation between topological properties and statistical behavior exists. + + +Next subsection will now give a concrete original implementation of the Xor CI PRNG, the +fastest generator in the chaotic iteration based family. In the remainder, +this generator will be simply referred as CIPRNG, or ``the proposed PRNG'', if this statement does not +raise ambiguity. +\end{color} + +\subsection{First Efficient Implementation of a PRNG based on Chaotic Iterations} +\label{sec:efficient PRNG} +% +%Based on the proof presented in the previous section, it is now possible to +%improve the speed of the generator formerly presented in~\cite{bgw09:ip,guyeux10}. +%The first idea is to consider +%that the provided strategy is a pseudorandom Boolean vector obtained by a +%given PRNG. +%An iteration of the system is simply the bitwise exclusive or between +%the last computed state and the current strategy. +%Topological properties of disorder exhibited by chaotic +%iterations can be inherited by the inputted generator, we hope by doing so to +%obtain some statistical improvements while preserving speed. +% %%RAPH : j'ai viré tout ca %% Let us give an example using 16-bits numbers, to clearly understand how the bitwise xor operations %% are @@ -881,7 +1346,7 @@ obtain some statistical improvements while preserving speed. -\lstset{language=C,caption={C code of the sequential PRNG based on chaotic iterations},label=algo:seqCIPRNG} +\lstset{language=C,caption={C code of the sequential PRNG based on chaotic iterations},label={algo:seqCIPRNG}} \begin{small} \begin{lstlisting} @@ -915,7 +1380,13 @@ works with 32-bits, we use the command \texttt{(unsigned int)}, that selects the Thus producing a pseudorandom number needs 6 xor operations with 6 32-bits numbers that are provided by 3 64-bits PRNGs. This version successfully passes the -stringent BigCrush battery of tests~\cite{LEcuyerS07}. +stringent BigCrush battery of tests~\cite{LEcuyerS07}. +\begin{color}{red}At this point, we thus +have defined an efficient and statistically unbiased generator. Its speed is +directly related to the use of linear operations, but for the same reason, +this fast generator cannot be proven as secure. +\end{color} + \section{Efficient PRNGs based on Chaotic Iterations on GPU} \label{sec:efficient PRNG gpu} @@ -1151,7 +1622,16 @@ as it is shown in the next sections. \section{Security Analysis} \label{sec:security analysis} - +\PCH{This section is dedicated to the analysis of the security of the + proposed PRNGs from a theoretical point of view. The standard definition + of {\it indistinguishability} used is the classical one as defined for + instance in~\cite[chapter~3]{Goldreich}. It is important to emphasize that + this property shows that predicting the future results of the PRNG's + cannot be done in a reasonable time compared to the generation time. This + is a relative notion between breaking time and the sizes of the + keys/seeds. Of course, if small keys or seeds are chosen, the system can + be broken in practice. But it also means that if the keys/seeds are large + enough, the system is secured.} In this section the concatenation of two strings $u$ and $v$ is classically denoted by $uv$. @@ -1391,6 +1871,7 @@ secure. \begin{color}{red} \subsection{Practical Security Evaluation} +\label{sec:Practicak evaluation} Suppose now that the PRNG will work during $M=100$ time units, and that during this period,