From ddb01e4b5bfe53afe6dba0b77f3d5322ac38c81f Mon Sep 17 00:00:00 2001 From: guyeux Date: Thu, 14 Jun 2012 11:27:03 +0200 Subject: [PATCH] blabla --- mabase.bib | 9 +++++++ prng_gpu.tex | 72 ++++++++++++++++------------------------------------ 2 files changed, 31 insertions(+), 50 deletions(-) diff --git a/mabase.bib b/mabase.bib index 6b41f33..30ad80e 100644 --- a/mabase.bib +++ b/mabase.bib @@ -30,6 +30,15 @@ note = {To appear}, } +@UNPUBLISHED{ANDREW2008, + author = {NIST Special Publication 800-22 rev. 1}, + title = {A Statistical Test Suite for Random and Pseudorandom Number Generators + for Cryptographic Applications}, + year = {August 2008}, + owner = {qianxue}, + timestamp = {2009.01.22} +} + @Article{combined_lcg, title = "Efficient and portable combined random number generators", journal = "Communications of the ACM", diff --git a/prng_gpu.tex b/prng_gpu.tex index 468b218..3228083 100644 --- a/prng_gpu.tex +++ b/prng_gpu.tex @@ -943,7 +943,8 @@ chaotic iterations, the result presents better statistical properties The list of defective PRNGs we will use as inputs for the statistical tests to come is introduced here. -Firstly, the simple linear congruency generator (LCGs) is defined by the following recurrence: +Firstly, the simple linear congruency generator (LCGs) will be used. +It is defined by the following recurrence: \begin{equation} x^n = (ax^{n-1} + c)~mod~m \label{LCG} @@ -952,16 +953,17 @@ where $a$, $c$, and $x^0$ must be, among other things, non-negative and less tha $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) is based on a linear recurrence of order +Secondly, the multiple recursive generators (MRGs) will be used too, 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 be used in this paper. +Combination of two MRGs (referred as 2MRGs) is also used in these experimentations. -Thirdly, generators based on linear recurrences with carry will be regarded too in experimentations. -This includes the add-with-carry (AWC) generator, based on the recurrence: +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} @@ -1007,49 +1009,14 @@ a^1 & \text{if}~ z^{n-1} = 0 .\end{array} \right. \end{array}\end{equation} \subsection{Statistical tests} \label{Security analysis} -Considering the properties of binary random sequences, various statistical tests can be designed -to evaluate the assertion that the sequence is generated by a perfectly random source. We have -performed some statistical tests for the CIPRNGs proposed here. These tests include NIST -suite~\cite{ANDREW2008} and DieHARD battery of tests~\cite{DieHARD}. For completeness and -for reference, we give in the following subsection a brief description of each of the -aforementioned tests. +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. -\subsubsection{NIST statistical tests suite} - -Among the numerous standard tests for pseudo-randomness, a convincing way to show the randomness of the produced sequences is to confront them to the NIST (National Institute of Standards and Technology) statistical tests, being an up-to-date tests suite proposed by the Information Technology Laboratory (ITL). A new version of the Statistical tests suite has been released in August 11, 2010. - -The NIST tests suite SP 800-22 is a statistical package consisting of 15 tests. They were developed to test the randomness of binary sequences produced by hardware or software based cryptographic pseudorandom number generators. These tests focus on a variety of different types of non-randomness that could exist in a sequence. - -For each statistical test, a set of $P-values$ (corresponding to the set of sequences) is produced. -The interpretation of empirical results can be conducted in various ways. -In this paper, the examination of the distribution of P-values to check for uniformity ($ P-value_{T}$) is used. -The distribution of $P-values$ is examined to ensure uniformity. -If $P-value_{T} \geqslant 0.0001$, then the sequences can be considered to be uniformly distributed. - -In our experiments, 100 sequences (s = 100), each with 1,000,000-bit long, are generated and tested. If the $P-value_{T}$ of any test is smaller than 0.0001, the sequences are considered to be not good enough and the generating algorithm is not suitable for usage. - - - - - -\subsubsection{DieHARD battery of tests} -The DieHARD battery of tests has been the most sophisticated standard for over a decade. Because of the stringent requirements in the DieHARD tests suite, a generator passing this battery of -tests can be considered good as a rule of thumb. - -The DieHARD battery of tests consists of 18 different independent statistical tests. This collection - of tests is based on assessing the randomness of bits comprising 32-bit integers obtained from -a random number generator. Each test requires $2^{23}$ 32-bit integers in order to run the full set -of tests. Most of the tests in DieHARD return a $P-value$, which should be uniform on $[0,1)$ if the input file -contains truly independent random bits. These $P-values$ are obtained by -$P=F(X)$, where $F$ is the assumed distribution of the sample random variable $X$ (often normal). -But that assumed $F$ is just an asymptotic approximation, for which the fit will be worst -in the tails. Thus occasional $P-values$ near 0 or 1, such as 0.0012 or 0.9983, can occur. -An individual test is considered to be failed if the $P-value$ approaches 1 closely, for example $P>0.9999$. - - -\subsection{Results and discussion} \label{Results and discussion} \begin{table*} \renewcommand{\arraystretch}{1.3} @@ -1065,16 +1032,21 @@ DieHARD & 16/18 & 16/18 & 15/18 & 16/18 & \textbf{18/18} & 16/18 & 16/18 & 16/18 \end{tabular} \end{table*} -Table~\ref{NIST and DieHARD tests suite passing rate the for PRNGs without CI} shows the results on the batteries recalled above, indicating that almost all the PRNGs cannot pass all their tests. In other words, the statistical quality of these PRNGs cannot fulfill the up-to-date standards presented previously. We will show that the CIPRNG can solve this issue. - -To illustrate the effects of this CIPRNG in detail, experiments will be divided in three parts: +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,$ + \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} -x_i^n=\left\{ +\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} -- 2.39.5