X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/c069ead2bda7032833d2d7f3d0851906ec4d22f0..8dfce25f59a57787b53e1ba55971a5c4f8d5993f:/prng.tex?ds=inline diff --git a/prng.tex b/prng.tex index ae733d9..2d1d7f2 100644 --- a/prng.tex +++ b/prng.tex @@ -1,12 +1,12 @@ -Let us finally present the pseudorandom number generator $\chi_{\textit{15Rairo}}$, +Let us finally present the pseudorandom number generator $\chi_{\textit{16HamG}}$, which is based on random walks in $\Gamma_{\{b\}}(f)$. More precisely, let be given a Boolean map $f:\Bool^{\mathsf{N}} \rightarrow -\Bool^\mathsf{N}$, +\Bool^{\mathsf{N}}$, a PRNG \textit{Random}, an integer $b$ that corresponds to an iteration number (\textit{i.e.}, the length of the walk), and an initial configuration $x^0$. Starting from $x^0$, the algorithm repeats $b$ times -a random choice of which edge to follow, and traverses this edge +a random choice of which edge to follow, and crosses this edge provided it is allowed to do so, \textit{i.e.}, when $\textit{Random}(1)$ is not null. The final configuration is thus outputted. @@ -16,19 +16,19 @@ This PRNG is formalized in Algorithm~\ref{CI Algorithm:2}. \begin{algorithm}[ht] %\begin{scriptsize} -\KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ ($n$ bits)} -\KwOut{a configuration $x$ ($n$ bits)} +\KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ ($\mathsf{N}$ bits)} +\KwOut{a configuration $x$ ($\mathsf{N}$ bits)} $x\leftarrow x^0$\; \For{$i=0,\dots,b-1$} { \If{$\textit{Random}(1) \neq 0$}{ -$s\leftarrow{\textit{Random}(n)}$\; -$x\leftarrow{F_f(s,x)}$\; +$s^0\leftarrow{\textit{Random}(\mathsf{N})}$\; +$x\leftarrow{F_f(x,s^0)}$\; } } return $x$\; %\end{scriptsize} -\caption{Pseudo Code of the $\chi_{\textit{15Rairo}}$ PRNG} +\caption{Pseudo Code of the $\chi_{\textit{16HamG}}$ PRNG} \label{CI Algorithm:2} \end{algorithm} @@ -46,8 +46,8 @@ Sect.~\ref{sec:hypercube}. Notice that the chaos property of $G_f$ given in Sect.\ref{sec:proofOfChaos} -only requires that the graph $\Gamma_{\{b\}}(f)$ is strongly connected. -Since the $\chi_{\textit{15Rairo}}$ algorithm +only requires the graph $\Gamma_{\{b\}}(f)$ to be strongly connected. +Since the $\chi_{\textit{16HamG}}$ algorithm only adds probability constraints on existing edges, it preserves this property. @@ -61,7 +61,7 @@ whose Markov Matrix (issued from Eq.~(\ref{eq:Markov:rairo})) has the smallest practical mixing time. Such functions are given in Table~\ref{table:nc}. -In this table, let us consider for instance +In this table, let us consider, for instance, the function $\textcircled{a}$ from $\Bool^4$ to $\Bool^4$ defined by the following images : $[13, 10, 9, 14, 3, 11, 1, 12, 15, 4, 7, 5, 2, 6, 0, 8]$. @@ -69,142 +69,110 @@ In other words, the image of $3~(0011)$ by $\textcircled{a}$ is $14~(1110)$: it is obtained as the binary value of the fourth element in the second list (namely~14). -In this table the column -that is labeled with $b$ (respectively by $E[\tau]$) +In this table the column that is labeled with $b$ %(respectively by $E[\tau]$) gives the practical mixing time -where the deviation to the standard distribution is lesser than $10^{-6}$ -(resp. the theoretical upper bound of stopping time as described in -Sect.~\ref{sec:hypercube}). +where the deviation to the standard distribution is inferior than $10^{-6}$. +%(resp. the theoretical upper bound of stopping time as described in Sect.~\ref{sec:hypercube}). \begin{table*}[t] \begin{center} \begin{scriptsize} -\begin{tabular}{|c|c|c|c|c|} +\begin{tabular}{|c|c|c|c|} \hline Function $f$ & $f(x)$, for $x$ in $(0,1,2,\hdots,2^n-1)$ & $\mathsf{N}$ & $b$ -&$E[\tau]$\\ +\\ \hline %%%%% n= 4 -$\textcircled{a}$&[13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]&4&64&154\\ +$\textcircled{a}$&[13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]&4&64\\ \hline %%%%% n= 5 $\textcircled{b}$& -[29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, & 5 & 78 & 236\\ +[29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, & 5 & 78 \\ & 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4] -&&&\\ +&&\\ %%%%% n= 6 \hline & [55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33, 49, -&&&\\ +&&\\ & 15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1, 40, 63, -&&&\\ +&&\\ $\textcircled{c}$& 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, -&6&88&335\\ +&6&88\\ & 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32] -&&&\\ +&&\\ %%%%% n= 7 \hline & -[111, 94, 93, 116, 122, 90, 125, 88, 115, 126, 119, 84, 123, 98, -&&&\\ -& - 81, 120, 109, 106, 105, 110, 99, 107, 104, 72, 71, 118, 117, - &&&\\ -& -96, 103, 102, 113, 64, 79, 86, 95, 124, 83, 91, 121, 24, 85, 22, -&&&\\ -$\textcircled{d}$& -69, 20, 19, 114, 17, 112, 77, 76, 13, 108, 74, 10, 9, 73, 67, 66, -&7 & 99&450\\ - -& - 101, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59, 56, 48, 53, 38, -&&&\\ -& - 37, 60, 55, 58, 33, 49, 63, 44, 47, 40, 42, 46, 45, 41, 35, 34, -&&&\\ -& -39, 52, 43, 50, 32, 36, 29, 28, 61, 92, 26, 18, 89, 25, 87, 30, -&&&\\ -& -23, 4, 27, 2, 16, 80, 31, 78, 15, 14, 3, 11, 8, 12, 5, 70, 21, -&&&\\ -& -68, 7, 6, 65, 1] -&&&\\ +[111, 124, 93, 120, 122, 114, 89, 121, 87, 126, 125, 84, 123, 82, +&&\\ +&112, 80, 79, 106, 105, 110, 75, 107, 73, 108, 119, 100, 117, 116, +&&\\ +&103, 102, 101, 97, 31, 86, 95, 94, 83, 26, 88, 24, 71, 118, 69, +&&\\ +&68, 115, 90, 113, 16, 15, 76, 109, 72, 74, 10, 9, 104, 7, 6, 65, +&&\\ +$\textcircled{d}$ &70, 99, 98, 64, 96, 127, 54, 53, 62, 51, 59, 56, 60, 39, 52, 37, &7 &99\\ +&36, 55, 58, 57, 49, 63, 44, 47, 40, 42, 46, 45, 41, 35, 34, 33, +&&\\ +&38, 43, 50, 32, 48, 29, 28, 61, 92, 91, 18, 17, 25, 19, 30, 85, +&&\\ +&22, 27, 2, 81, 0, 13, 78, 77, 14, 3, 11, 8, 12, 23, 4, 21, 20, +&&\\ +&67, 66, 5, 1] +&&\\ %%%%%n=8 \hline & -[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180, 227, -&&&\\ -& -178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168, 229, 166, -&&&\\ -& -165, 244, 163, 242, 241, 192, 215, 220, 205, 216, 218, 222, 221, -&&&\\ -& -208, 213, 210, 212, 214, 219, 211, 217, 209, 239, 202, 207, 140, -&&&\\ -& -139, 234, 193, 204, 135, 196, 199, 132, 194, 130, 225, 200, 159, -&&&\\ -& -62, 185, 252, 59, 250, 169, 56, 191, 246, 245, 52, 243, 50, 176, -&&&\\ -& -48, 173, 238, 189, 44, 235, 42, 137, 184, 231, 38, 37, 228, 35, -&&&\\ -& -226, 177, 224, 151, 156, 141, 152, 154, 158, 157, 144, 149, 146, -&&&\\ -& -148, 150, 155, 147, 153, 145, 175, 206, 143, 136, 11, 142, 129, -&&&\\ -$\textcircled{e}$& -8, 7, 198, 197, 4, 195, 2, 161, 160, 255, 124, 109, 108, 122, -&8&110&582\\ -& - 126, 125, 112, 117, 114, 116, 100, 123, 98, 97, 113, 79, 106, -&&&\\ -& - 111, 110, 99, 74, 121, 120, 71, 118, 103, 101, 115, 66, 65, -&&&\\ -& -104, 127, 90, 89, 94, 83, 91, 81, 92, 95, 84, 87, 85, 82, 86, -&&&\\ -& -80, 88, 77, 76, 93, 72, 107, 78, 105, 64, 69, 102, 68, 70, 75, -&&&\\ -& -67, 73, 96, 55, 58, 45, 188, 51, 186, 61, 40, 119, 182, 181, -&&&\\ -& -53, 179, 54, 33, 49, 15, 174, 47, 60, 171, 46, 57, 32, 167, 6, -&&&\\ -& - 36, 164, 43, 162, 1, 0, 63, 26, 25, 30, 19, 27, 17, 28, 31, -&&&\\ -& -20, 23, 21, 18, 22, 16, 24, 13, 10, 29, 14, 3, 138, 41, 12, -&&&\\ -& -39, 134, 133, 5, 131, 34, 9, 128] -&&&\\ +[223, 238, 249, 254, 243, 251, 233, 252, 183, 244, 229, 245, 227, +&&\\ +&246, 240, 176, 175, 174, 253, 204, 203, 170, 169, 248, 247, 226, +&&\\ +&228, 164, 163, 162, 161, 192, 215, 220, 205, 216, 155, 222, 221, +&&\\ +&208, 213, 150, 212, 214, 219, 211, 145, 209, 239, 202, 207, 140, +&&\\ +&195, 234, 193, 136, 231, 230, 199, 197, 131, 198, 225, 200, 63, +&&\\ +&188, 173, 184, 186, 250, 57, 168, 191, 178, 180, 52, 187, 242, +&&\\ +&241, 48, 143, 46, 237, 236, 235, 138, 185, 232, 135, 38, 181, 165, +&&\\ +&35, 166, 33, 224, 31, 30, 153, 158, 147, 218, 217, 156, 159, 148, +&&\\ +$\textcircled{e}$&151, 149, 19, 210, 144, 152, 141, 206, 13, 12, 171, 10, 201, 128, +&8&109\\ +&133, 130, 132, 196, 3, 194, 137, 0, 255, 124, 109, 120, 122, 106, +&&\\ +&125, 104, 103, 114, 116, 118, 123, 98, 97, 113, 79, 126, 111, 110, +&&\\ +&99, 74, 121, 72, 71, 70, 117, 101, 115, 102, 65, 112, 127, 90, 89, +&&\\ +&94, 83, 91, 81, 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, +&&\\ +&108, 107, 78, 105, 64, 69, 66, 68, 100, 75, 67, 73, 96, 55, 190, +&&\\ +&189, 62, 51, 59, 41, 60, 119, 182, 37, 53, 179, 54, 177, 32, 45, +&&\\ +&44, 61, 172, 11, 58, 9, 56, 167, 34, 36, 4, 43, 50, 49, 160, 23, +&&\\ +&28, 157, 24, 26, 154, 29, 16, 21, 18, 20, 22, 27, 146, 25, 17, 47, +&&\\ +&142, 15, 14, 139, 42, 1, 40, 39, 134, 7, 5, 2, 6, 129, 8] +&&\\ \hline \end{tabular} \end{scriptsize} \end{center} -\caption{Functions with DSCC Matrix and smallest MT\label{table:nc}} +\caption{Functions with DSCC Matrix and smallest MT}\label{table:nc} \end{table*} @@ -212,46 +180,80 @@ $\textcircled{e}$& Let us first discuss about results against the NIST test suite. In our experiments, 100 sequences (s = 100) of 1,000,000 bits are generated and tested. If the value $\mathbb{P}_T$ of any test is smaller than 0.0001, the sequences are considered to be not good enough -and the generator is unsuitable. Table~\ref{The passing rate} shows $\mathbb{P}_T$ of sequences based on discrete -chaotic iterations using different schemes. If there are at least two statistical values in a test, this test is +and the generator is unsuitable. + +Table~\ref{The passing rate} shows $\mathbb{P}_T$ of sequences based +on $\chi_{\textit{16HamG}}$ using different functions, namely +$\textcircled{a}$,\ldots, $\textcircled{e}$. +In this algorithm implementation, +the embedded PRNG \textit{Random} is the default Python PRNG, \textit{i.e.}, +the Mersenne Twister algorithm~\cite{matsumoto1998mersenne}. +Implementations for $\mathsf{N}=4, \dots, 8$ of this algorithm is evaluated +through the NIST test suite and results are given in columns +$\textit{MT}_4$, \ldots, $\textit{MT}_8$. +If there are at least two statistical values in a test, this test is marked with an asterisk and the average value is computed to characterize the statistics. -We can see in Table \ref{The passing rate} that all the rates are greater than 97/100, \textit{i.e.}, all the generators -achieve to pass the NIST battery of tests. +We first can see in Table \ref{The passing rate} that all the rates +are greater than 97/100, \textit{i.e.}, all the generators +achieve to pass the NIST battery of tests. +It can be noticed that adding chaos properties for Mersenne Twister +algorithm does not reduce its security against this statistical tests. -\begin{table} -\renewcommand{\arraystretch}{1.3} +\begin{table*} +\renewcommand{\arraystretch}{1.1} \begin{center} -\begin{scriptsize} +\begin{tiny} \setlength{\tabcolsep}{2pt} +\begin{tabular}{|l|r|r|r|r|r|} + \hline +Test & $\textit{MT}_4$ & $\textit{MT}_5$& $\textit{MT}_6$& $\textit{MT}_7$& $\textit{MT}_8$ + \\ \hline +Frequency (Monobit)& 0.924 (1.0)& 0.678 (0.98)& 0.102 (0.97)& 0.213 (0.98)& 0.719 (0.99) \\ \hline +Frequency within a Block& 0.514 (1.0)& 0.419 (0.98)& 0.129 (0.98)& 0.275 (0.99)& 0.455 (0.99)\\ \hline +Cumulative Sums (Cusum) *& 0.668 (1.0)& 0.568 (0.99)& 0.881 (0.98)& 0.529 (0.98)& 0.657 (0.995)\\ \hline +Runs& 0.494 (0.99)& 0.595 (0.97)& 0.071 (0.97)& 0.017 (1.0)& 0.834 (1.0)\\ \hline +Longest Run of Ones in a Block& 0.366 (0.99)& 0.554 (1.0)& 0.042 (0.99)& 0.051 (0.99)& 0.897 (0.97)\\ \hline +Binary Matrix Rank& 0.275 (0.98)& 0.494 (0.99)& 0.719 (1.0)& 0.334 (0.98)& 0.637 (0.99)\\ \hline +Discrete Fourier Transform (Spectral)& 0.122 (0.98)& 0.108 (0.99)& 0.108 (1.0)& 0.514 (0.99)& 0.534 (0.98)\\ \hline +Non-overlapping Template Matching*& 0.483 (0.990)& 0.507 (0.990)& 0.520 (0.988)& 0.494 (0.988)& 0.515 (0.989)\\ \hline +Overlapping Template Matching& 0.595 (0.99)& 0.759 (1.0)& 0.637 (1.0)& 0.554 (0.99)& 0.236 (1.0)\\ \hline +Maurer's "Universal Statistical"& 0.202 (0.99)& 0.000 (0.99)& 0.514 (0.98)& 0.883 (0.97)& 0.366 (0.99)\\ \hline +Approximate Entropy (m=10)& 0.616 (0.99)& 0.145 (0.99)& 0.455 (0.99)& 0.262 (0.97)& 0.494 (1.0)\\ \hline +Random Excursions *& 0.275 (1.0)& 0.495 (0.975)& 0.465 (0.979)& 0.452 (0.991)& 0.260 (0.989)\\ \hline +Random Excursions Variant *& 0.382 (0.995)& 0.400 (0.994)& 0.417 (0.984)& 0.456 (0.991)& 0.389 (0.991)\\ \hline +Serial* (m=10)& 0.629 (0.99)& 0.963 (0.99)& 0.366 (0.995)& 0.537 (0.985)& 0.253 (0.995)\\ \hline +Linear Complexity& 0.494 (0.99)& 0.514 (0.98)& 0.145 (1.0)& 0.657 (0.98)& 0.145 (0.99)\\ \hline +\end{tabular} -\begin{tabular}{|l|l|l|l|l|l|} -\hline -Method &$\textcircled{a}$& $\textcircled{b}$ & $\textcircled{c}$ & $\textcircled{d}$ & $\textcircled{e}$ \\ \hline\hline -Frequency (Monobit)& 0.851 (0.98)& 0.719 (0.99)& 0.699 (0.99)& 0.514 (1.0)& 0.798 (0.99)\\ \hline -Frequency (Monobit)& 0.851 (0.98)& 0.719 (0.99)& 0.699 (0.99)& 0.514 (1.0)& 0.798 (0.99)\\ \hline -Frequency within a Block& 0.262 (0.98)& 0.699 (0.98)& 0.867 (0.99)& 0.145 (1.0)& 0.455 (0.99)\\ \hline -Cumulative Sums (Cusum) *& 0.301 (0.98)& 0.521 (0.99)& 0.688 (0.99)& 0.888 (1.0)& 0.598 (1.0)\\ \hline -Runs& 0.224 (0.97)& 0.383 (0.97)& 0.108 (0.96)& 0.213 (0.99)& 0.616 (0.99)\\ \hline -Longest Run of 1s & 0.383 (1.0)& 0.474 (1.0)& 0.983 (0.99)& 0.699 (0.98)& 0.897 (0.96)\\ \hline -Binary Matrix Rank& 0.213 (1.0)& 0.867 (0.99)& 0.494 (0.98)& 0.162 (0.99)& 0.924 (0.99)\\ \hline -Disc. Fourier Transf. (Spect.)& 0.474 (1.0)& 0.739 (0.99)& 0.012 (1.0)& 0.678 (0.98)& 0.437 (0.99)\\ \hline -Unoverlapping Templ. Match.*& 0.505 (0.990)& 0.521 (0.990)& 0.510 (0.989)& 0.511 (0.990)& 0.499 (0.990)\\ \hline -Overlapping Temp. Match.& 0.574 (0.98)& 0.304 (0.99)& 0.437 (0.97)& 0.759 (0.98)& 0.275 (0.99)\\ \hline -Maurer's Universal Statistical& 0.759 (0.96)& 0.699 (0.97)& 0.191 (0.98)& 0.699 (1.0)& 0.798 (0.97)\\ \hline -Approximate Entropy (m=10)& 0.759 (0.99)& 0.162 (0.99)& 0.867 (0.99)& 0.534 (1.0)& 0.616 (0.99)\\ \hline -Random Excursions *& 0.666 (0.994)& 0.410 (0.962)& 0.287 (0.998)& 0.365 (0.994)& 0.480 (0.985)\\ \hline -Random Excursions Variant *& 0.337 (0.988)& 0.519 (0.984)& 0.549 (0.994)& 0.225 (0.995)& 0.533 (0.993)\\ \hline -Serial* (m=10)& 0.630 (0.99)& 0.529 (0.99)& 0.460 (0.99)& 0.302 (0.995)& 0.360 (0.985)\\ \hline -Linear Complexity& 0.719 (1.0)& 0.739 (0.99)& 0.759 (0.98)& 0.122 (0.97)& 0.514 (0.99)\\ \hline +\begin{tabular}{|l|r|r|r|r|r|} + \hline +Test +&$\textcircled{a}$& $\textcircled{b}$ & $\textcircled{c}$ & $\textcircled{d}$ & $\textcircled{e}$ \\ \hline +Frequency (Monobit)&0.129 (1.0)& 0.181 (1.0)& 0.637 (0.99)& 0.935 (1.0)& 0.978 (1.0)\\ \hline +Frequency within a Block& 0.275 (1.0)& 0.534 (0.98)& 0.066 (1.0)& 0.719 (1.0)& 0.366 (1.0)\\ \hline +Cumulative Sums (Cusum) *& 0.695 (1.0)& 0.540 (1.0)& 0.514 (0.985)& 0.773 (0.995)& 0.506 (0.99)\\ \hline +Runs& 0.897 (0.99)& 0.051 (1.0)& 0.102 (0.98)& 0.616 (0.99)& 0.191 (1.0)\\ \hline +Longest Run of Ones in a Block& 0.851 (1.0)& 0.595 (0.99)& 0.419 (0.98)& 0.616 (0.98)& 0.897 (1.0)\\ \hline +Binary Matrix Rank& 0.419 (1.0)& 0.946 (0.99)& 0.319 (0.99)& 0.739 (0.97)& 0.366 (1.0)\\ \hline +Discrete Fourier Transform (Spectral)& 0.867 (1.0)& 0.514 (1.0)& 0.145 (1.0)& 0.224 (0.99)& 0.304 (1.0)\\ \hline +Non-overlapping Template Matching*& 0.542 (0.990)& 0.512 (0.989)& 0.505 (0.990)& 0.494 (0.989)& 0.493 (0.991)\\ \hline +Overlapping Template Matching& 0.275 (0.99)& 0.080 (0.99)& 0.574 (0.98)& 0.798 (0.99)& 0.834 (0.99)\\ \hline +Maurer's "Universal Statistical"& 0.383 (0.99)& 0.991 (0.98)& 0.851 (1.0)& 0.595 (0.98)& 0.514 (1.0)\\ \hline +Approximate Entropy (m=10)& 0.935 (1.0)& 0.719 (1.0)& 0.883 (1.0)& 0.719 (0.97)& 0.366 (0.99)\\ \hline +Random Excursions *& 0.396 (0.991)& 0.217 (0.989)& 0.445 (0.975)& 0.743 (0.993)& 0.380 (0.990)\\ \hline +Random Excursions Variant *& 0.486 (0.997)& 0.373 (0.981)& 0.415 (0.994)& 0.424 (0.991)& 0.380 (0.991)\\ \hline +Serial* (m=10)&0.350 (1.0)& 0.678 (0.995)& 0.287 (0.995)& 0.740 (0.99)& 0.301 (0.98)\\ \hline +Linear Complexity& 0.455 (0.99)& 0.867 (1.0)& 0.401 (0.99)& 0.191 (0.97)& 0.699 (1.0)\\ \hline \end{tabular} -\end{scriptsize} + +\end{tiny} \end{center} \caption{NIST SP 800-22 test results ($\mathbb{P}_T$)} \label{The passing rate} -\end{table} +\end{table*} %%% Local Variables: