X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/cc4c6aa868df1972b090ffcce36c865b8bf53644..9879779d913285ee14baad568f69be401dfd0fb3:/prng_gpu.tex diff --git a/prng_gpu.tex b/prng_gpu.tex index bc40b2d..0c9f9c7 100644 --- a/prng_gpu.tex +++ b/prng_gpu.tex @@ -13,6 +13,9 @@ \usepackage[standard]{ntheorem} \usepackage{algorithmic} \usepackage{slashbox} +\usepackage{ctable} +\usepackage{tabularx} +\usepackage{multirow} % Pour mathds : les ensembles IR, IN, etc. \usepackage{dsfont} @@ -87,7 +90,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 @@ -121,10 +130,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 @@ -154,8 +172,13 @@ The remainder of this paper is organized as follows. In Section~\ref{section:re 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}. @@ -164,7 +187,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. @@ -172,7 +196,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 @@ -477,7 +501,7 @@ 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 \begin{color}{red} -should improves the statistical properties of each +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. @@ -553,7 +577,7 @@ 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 pseudo-random bit +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 @@ -566,14 +590,14 @@ updated, as follows: $x_i^n = x_i^{n-1}$ if $i \neq S^n$, else $x_i^n = \overlin 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 pseudo-random bit sequence of our generator. +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 is required to make the outputs uniform in $\llbracket 0, 2^\mathsf{N}-1 \rrbracket$ -(the reader is referred to~\cite{bg10:ip} for more information). +This function must be chosen such that the outputs of the resulted PRNG is 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} @@ -599,8 +623,7 @@ N \text{ if }\sum_{i=0}^{N-1}{C^i_{32}}\leqslant{y^n}<1.\\ } \ENDFOR \STATE$a\leftarrow{PRNG_1()}$\; -\STATE$m\leftarrow{g(a)}$\; -\STATE$k\leftarrow{m}$\; +\STATE$k\leftarrow{g(a)}$\; \WHILE{$i=0,\dots,k$} \STATE$b\leftarrow{PRNG_2()~mod~\mathsf{N}}$\; @@ -640,7 +663,7 @@ x^0 \in \llbracket 0, 2^\mathsf{N}-1 \rrbracket, S \in \llbracket 0, 2^\mathsf{N \forall n \in \mathds{N}^*, x^n = x^{n-1} \oplus S^n, \end{array} \right. -\label{equation Oplus0} +\label{equation Oplus} \end{equation} where $\oplus$ is for the bitwise exclusive or between two integers. This rewriting can be understood as follows. The $n-$th term $S^n$ of the @@ -650,7 +673,7 @@ as an integer having $\mathsf{N}$ bits too). More precisely, the $k-$th component of this state (a binary digit) changes if and only if the $k-$th digit in the binary decomposition of $S^n$ is 1. -The single basic component presented in Eq.~\ref{equation Oplus0} is of +The single basic component presented in Eq.~\ref{equation Oplus} is of ordinary use as a good elementary brick in various PRNGs. It corresponds to the following discrete dynamical system in chaotic iterations: @@ -672,7 +695,7 @@ we select a subset of components to change. Obviously, replacing the previous CI PRNG Algorithms by -Equation~\ref{equation Oplus0}, which is possible when the iteration function is +Equation~\ref{equation Oplus}, which is possible when the iteration function is the vectorial negation, leads to a speed improvement (the resulting generator will be referred as ``Xor CI PRNG'' in what follows). @@ -932,7 +955,7 @@ have $d((S,E),(\tilde S,E))<\epsilon$. \begin{color}{red} \section{Statistical Improvements Using Chaotic Iterations} -\label{The generation of pseudo-random sequence} +\label{The generation of pseudorandom sequence} Let us now explain why we are reasonable grounds to believe that chaos @@ -1007,6 +1030,53 @@ 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} @@ -1106,25 +1176,32 @@ Threshold value $m$& 19 & 7 & 2& 1 & 11& 9& 3& 4\\ \hline\hline \end{tabular} \end{table*} +Finally, the TestU01 battery as 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. + + Next subsection gives a concrete implementation of this Xor CI PRNG, which will new be simply called CIPRNG, or ``the proposed PRNG'', if this statement does not raise ambiguity. \end{color} -\subsection{Efficient PRNG based on Chaotic Iterations} +\subsection{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. - +% +%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 @@ -1156,7 +1233,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} @@ -1666,6 +1743,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,