X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/10e6981881d8b6f0b35ee256f3540d0a0c052324..9879779d913285ee14baad568f69be401dfd0fb3:/prng_gpu.tex?ds=sidebyside diff --git a/prng_gpu.tex b/prng_gpu.tex index 7d94e0c..0c9f9c7 100644 --- a/prng_gpu.tex +++ b/prng_gpu.tex @@ -1,4 +1,5 @@ -\documentclass{article} +%\documentclass{article} +\documentclass[10pt,journal,letterpaper,compsoc]{IEEEtran} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{fullpage} @@ -10,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} @@ -38,10 +44,10 @@ \begin{document} \author{Jacques M. Bahi, Rapha\"{e}l Couturier, Christophe -Guyeux, and Pierre-Cyrille Heam\thanks{Authors in alphabetic order}} +Guyeux, and Pierre-Cyrille Héam\thanks{Authors in alphabetic order}} -\maketitle +\IEEEcompsoctitleabstractindextext{ \begin{abstract} In this paper we present a new pseudorandom number generator (PRNG) on graphics processing units (GPU). This PRNG is based on the so-called chaotic iterations. It @@ -56,6 +62,13 @@ A chaotic version of the Blum-Goldwasser asymmetric key encryption scheme is fin \end{abstract} +} + +\maketitle + +\IEEEdisplaynotcompsoctitleabstractindextext +\IEEEpeerreviewmaketitle + \section{Introduction} @@ -77,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 @@ -111,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 @@ -135,7 +163,7 @@ allows us to generate almost 20 billion of pseudorandom numbers per second. Furthermore, we show that the proposed post-treatment preserves the cryptographical security of the inputted PRNG, when this last has such a property. -Last, but not least, we propose a rewritting of the Blum-Goldwasser asymmetric +Last, but not least, we propose a rewriting of the Blum-Goldwasser asymmetric key encryption protocol by using the proposed method. The remainder of this paper is organized as follows. In Section~\ref{section:related @@ -144,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}. @@ -153,8 +186,9 @@ We show in Section~\ref{sec:security analysis} that, if the inputted 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 Shum -in Section~\ref{sec:CSGPU}, and to an improvement of the +chaotic generator on GPU based on the famous Blum Blum Shub +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. @@ -162,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 @@ -216,7 +250,10 @@ We can finally remark that, to the best of our knowledge, no GPU implementation \label{section:BASIC RECALLS} This section is devoted to basic definitions and terminologies in the fields of -topological chaos and chaotic iterations. +topological chaos and chaotic iterations. We assume the reader is familiar +with basic notions on topology (see for instance~\cite{Devaney}). + + \subsection{Devaney's Chaotic Dynamical Systems} In the sequel $S^{n}$ denotes the $n^{th}$ term of a sequence $S$ and $V_{i}$ @@ -229,7 +266,7 @@ Consider a topological space $(\mathcal{X},\tau)$ and a continuous function $f : \mathcal{X} \rightarrow \mathcal{X}$. \begin{definition} -$f$ is said to be \emph{topologically transitive} if, for any pair of open sets +The function $f$ is said to be \emph{topologically transitive} if, for any pair of open sets $U,V \subset \mathcal{X}$, there exists $k>0$ such that $f^k(U) \cap V \neq \varnothing$. \end{definition} @@ -248,7 +285,7 @@ necessarily the same period). \begin{definition}[Devaney's formulation of chaos~\cite{Devaney}] -$f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and +The function $f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and topologically transitive. \end{definition} @@ -256,12 +293,12 @@ The chaos property is strongly linked to the notion of ``sensitivity'', defined on a metric space $(\mathcal{X},d)$ by: \begin{definition} -\label{sensitivity} $f$ has \emph{sensitive dependence on initial conditions} +\label{sensitivity} The function $f$ has \emph{sensitive dependence on initial conditions} if there exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that $d\left(f^{n}(x), f^{n}(y)\right) >\delta $. -$\delta$ is called the \emph{constant of sensitivity} of $f$. +The constant $\delta$ is called the \emph{constant of sensitivity} of $f$. \end{definition} Indeed, Banks \emph{et al.} have proven in~\cite{Banks92} that when $f$ is @@ -320,15 +357,15 @@ Let us now recall how to define a suitable metric space where chaotic iterations are continuous. For further explanations, see, e.g., \cite{guyeux10}. Let $\delta $ be the \emph{discrete Boolean metric}, $\delta -(x,y)=0\Leftrightarrow x=y.$ Given a function $f$, define the function: -\begin{equation} +(x,y)=0\Leftrightarrow x=y.$ Given a function $f$, define the function +$F_{f}: \llbracket1;\mathsf{N}\rrbracket\times \mathds{B}^{\mathsf{N}} +\longrightarrow \mathds{B}^{\mathsf{N}}$ +\begin{equation*} \begin{array}{lrll} -F_{f}: & \llbracket1;\mathsf{N}\rrbracket\times \mathds{B}^{\mathsf{N}} & -\longrightarrow & \mathds{B}^{\mathsf{N}} \\ -& (k,E) & \longmapsto & \left( E_{j}.\delta (k,j)+f(E)_{k}.\overline{\delta -(k,j)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},% +& (k,E) & \longmapsto & \left( E_{j}.\delta (k,j)+ f(E)_{k}.\overline{\delta +(k,j)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket}% \end{array}% -\end{equation}% +\end{equation*}% \noindent where + and . are the Boolean addition and product operations. Consider the phase space: \begin{equation} @@ -405,7 +442,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 @@ -462,30 +499,60 @@ 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{scriptsize} +\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{scriptsize} -\caption{PRNG with chaotic functions} +\end{small} +\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)} \KwOut{$y$ (a 32-bit word)} $z\leftarrow{z\oplus{(z\ll13)}}$\; @@ -493,37 +560,100 @@ $z\leftarrow{z\oplus{(z\gg17)}}$\; $z\leftarrow{z\oplus{(z\ll5)}}$\; $y\leftarrow{z}$\; return $y$\; -\medskip +\end{small} \caption{An arbitrary round of \textit{XORshift} algorithm} \label{XORshift} \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 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} +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} @@ -536,7 +666,7 @@ x^0 \in \llbracket 0, 2^\mathsf{N}-1 \rrbracket, S \in \llbracket 0, 2^\mathsf{N \label{equation Oplus} \end{equation} where $\oplus$ is for the bitwise exclusive or between two integers. -This rewritting can be understood as follows. The $n-$th term $S^n$ of the +This rewriting can be understood as follows. The $n-$th term $S^n$ of the sequence $S$, which is an integer of $\mathsf{N}$ binary digits, presents the list of cells to update in the state $x^n$ of the system (represented as an integer having $\mathsf{N}$ bits too). More precisely, the $k-$th @@ -564,9 +694,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 @@ -576,11 +709,11 @@ faster, does not deflate their topological chaos properties. \subsection{Proofs of Chaos of the General Formulation of the Chaotic Iterations} \label{deuxième def} Let us consider the discrete dynamical systems in chaotic iterations having -the general form: +the general form: $\forall n\in \mathds{N}^{\ast }$, $ \forall i\in +\llbracket1;\mathsf{N}\rrbracket $, \begin{equation} -\forall n\in \mathds{N}^{\ast }, \forall i\in -\llbracket1;\mathsf{N}\rrbracket ,x_i^n=\left\{ + x_i^n=\left\{ \begin{array}{ll} x_i^{n-1} & \text{ if } i \notin \mathcal{S}^n \\ \left(f(x^{n-1})\right)_{S^n} & \text{ if }i \in \mathcal{S}^n. @@ -605,14 +738,13 @@ Let us introduce the following function: where $\mathcal{P}\left(X\right)$ is for the powerset of the set $X$, that is, $Y \in \mathcal{P}\left(X\right) \Longleftrightarrow Y \subset X$. Given a function $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, define the function: -\begin{equation} -\begin{array}{lrll} -F_{f}: & \mathcal{P}\left(\llbracket1;\mathsf{N}\rrbracket \right) \times \mathds{B}^{\mathsf{N}} & -\longrightarrow & \mathds{B}^{\mathsf{N}} \\ -& (P,E) & \longmapsto & \left( E_{j}.\chi (j,P)+f(E)_{j}.\overline{\chi -(j,P)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},% +$F_{f}: \mathcal{P}\left(\llbracket1;\mathsf{N}\rrbracket \right) \times \mathds{B}^{\mathsf{N}} +\longrightarrow \mathds{B}^{\mathsf{N}}$ +\begin{equation*} +\begin{array}{rll} + (P,E) & \longmapsto & \left( E_{j}.\chi (j,P)+f(E)_{j}.\overline{\chi(j,P)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket}% \end{array}% -\end{equation}% +\end{equation*}% where + and . are the Boolean addition and product operations, and $\overline{x}$ is the negation of the Boolean $x$. Consider the phase space: @@ -622,7 +754,7 @@ Consider the phase space: \end{equation} \noindent and the map defined on $\mathcal{X}$: \begin{equation} -G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), \label{Gf} +G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), %\label{Gf} %%RAPH, j'ai viré ce label qui existe déjà avant... \end{equation} \noindent where $\sigma$ is the \emph{shift} function defined by $\sigma (S^{n})_{n\in \mathds{N}}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}\longrightarrow (S^{n+1})_{n\in @@ -649,17 +781,21 @@ Let us introduce: d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S}), \label{nouveau d} \end{equation} -\noindent where -\begin{equation} -\left\{ -\begin{array}{lll} -\displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}% -}\delta (E_{k},\check{E}_{k})}\textrm{ is once more the Hamming distance}, \\ -\displaystyle{d_{s}(S,\check{S})} & = & \displaystyle{\dfrac{9}{\mathsf{N}}% -\sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}.% -\end{array}% -\right. -\end{equation} +\noindent where $ \displaystyle{d_{e}(E,\check{E})} = \displaystyle{\sum_{k=1}^{\mathsf{N}% + }\delta (E_{k},\check{E}_{k})}$ is once more the Hamming distance, and +$ \displaystyle{d_{s}(S,\check{S})} = \displaystyle{\dfrac{9}{\mathsf{N}}% + \sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}$, +%%RAPH : ici, j'ai supprimé tous les sauts à la ligne +%% \begin{equation} +%% \left\{ +%% \begin{array}{lll} +%% \displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}% +%% }\delta (E_{k},\check{E}_{k})} \textrm{ is once more the Hamming distance}, \\ +%% \displaystyle{d_{s}(S,\check{S})} & = & \displaystyle{\dfrac{9}{\mathsf{N}}% +%% \sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}.% +%% \end{array}% +%% \right. +%% \end{equation} where $|X|$ is the cardinality of a set $X$ and $A\Delta B$ is for the symmetric difference, defined for sets A, B as $A\,\Delta\,B = (A \setminus B) \cup (B \setminus A)$. @@ -738,14 +874,16 @@ thus after $n_{2}$, the $k+2$ first terms of $S^n$ and $S$ are equal. \noindent As a consequence, the $k+1$ first entries of the strategies of $% G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are the same ($G_{f}$ is a shift of strategies) and due to the definition of $d_{s}$, the floating part of the distance between $(S^n,E^n)$ and $(S,E)$ is strictly less than $% -10^{-(k+1)}\leqslant \varepsilon $.\bigskip \newline +10^{-(k+1)}\leqslant \varepsilon $. + In conclusion, -$$ -\forall \varepsilon >0,\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N}% -,\forall n\geqslant N_{0}, - d\left( G_{f}(S^n,E^n);G_{f}(S,E)\right) +%%RAPH : ici j'ai rajouté une ligne +$ +\forall \varepsilon >0,$ $\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N} +,$ $\forall n\geqslant N_{0},$ +$ d\left( G_{f}(S^n,E^n);G_{f}(S,E)\right) \leqslant \varepsilon . -$$ +$ $G_{f}$ is consequently continuous. \end{proof} @@ -785,7 +923,7 @@ where $(s^0,s^1, \hdots)$ is the strategy of $Y$, satisfies the properties claimed in the lemma. \end{proof} -We can now prove Theorem~\ref{t:chaos des general}... +We can now prove the Theorem~\ref{t:chaos des general}. \begin{proof}[Theorem~\ref{t:chaos des general}] Firstly, strong transitivity implies transitivity. @@ -803,8 +941,10 @@ and $t_2\in\mathds{N}$ such that $E$ is reached from $(S',E')$ after $t_2$ iterations of $G_f$. Consider the strategy $\tilde S$ that alternates the first $t_1$ terms -of $S$ and the first $t_2$ terms of $S'$: $$\tilde -S=(S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots).$$ It +of $S$ and the first $t_2$ terms of $S'$: +%%RAPH : j'ai coupé la ligne en 2 +$$\tilde +S=(S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,$$$$\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots).$$ It is clear that $(\tilde S,E)$ is obtained from $(\tilde S,E)$ after $t_1+t_2$ iterations of $G_f$. So $(\tilde S,E)$ is a periodic point. Since $\tilde S_t=S_t$ for $tk$. +seed $s$ of length $m$, $G(s)$ (the output of $G$ on the input $s$) has size +$\ell_G(m)$ with $\ell_G(m)>m$. The notion of {\it secure} PRNGs can now be defined as follows. \begin{definition} A cryptographic PRNG $G$ is secure if for any probabilistic polynomial time algorithm $D$, for any positive polynomial $p$, and for all sufficiently -large $k$'s, -$$| \mathrm{Pr}[D(G(U_k))=1]-Pr[D(U_{\ell_G(k)})=1]|< \frac{1}{p(k)},$$ +large $m$'s, +$$| \mathrm{Pr}[D(G(U_m))=1]-Pr[D(U_{\ell_G(m)})=1]|< \frac{1}{p(m)},$$ where $U_r$ is the uniform distribution over $\{0,1\}^r$ and the -probabilities are taken over $U_N$, $U_{\ell_G(N)}$ as well as over the +probabilities are taken over $U_m$, $U_{\ell_G(m)}$ as well as over the internal coin tosses of $D$. \end{definition} @@ -1147,7 +1528,7 @@ distinguish a perfect uniform random generator from $G$ with a non negligible probability. The interested reader is referred to~\cite[chapter~3]{Goldreich} for more information. Note that it is quite easily possible to change the function $\ell$ into any polynomial -function $\ell^\prime$ satisfying $\ell^\prime(N)>N)$~\cite[Chapter 3.3]{Goldreich}. +function $\ell^\prime$ satisfying $\ell^\prime(m)>m)$~\cite[Chapter 3.3]{Goldreich}. The generation schema developed in (\ref{equation Oplus}) is based on a pseudorandom generator. Let $H$ be a cryptographic PRNG. We may assume, @@ -1202,8 +1583,10 @@ $y\bigoplus_{i=1}^{i=j} w_i^\prime=y\bigoplus_{i=1}^{i=j} w_i$. It follows, by a direct induction, that $w_i=w_i^\prime$. Furthermore, since $\mathbb{B}^{kN}$ is finite, each $\varphi_y$ is bijective. Therefore, and using (\ref{PCH-1}), one has +$\mathrm{Pr}[D^\prime(U_{kN})=1]=\mathrm{Pr}[D(\varphi_y(U_{kN}))=1]$ and, +therefore, \begin{equation}\label{PCH-2} -\mathrm{Pr}[D^\prime(U_{kN})=1]=\mathrm{Pr}[D(\varphi_y(U_{kN}))=1]=\mathrm{Pr}[D(U_{kN})=1]. +\mathrm{Pr}[D^\prime(U_{kN})=1]=\mathrm{Pr}[D(U_{kN})=1]. \end{equation} Now, using (\ref{PCH-1}) again, one has for every $x$, @@ -1212,7 +1595,7 @@ D^\prime(H(x))=D(\varphi_y(H(x))), \end{equation} where $y$ is randomly generated. By construction, $\varphi_y(H(x))=X(yx)$, thus -\begin{equation}\label{PCH-3} +\begin{equation}%\label{PCH-3} %%RAPH : j'ai viré ce label qui existe déjà, il est 3 ligne avant D^\prime(H(x))=D(yx), \end{equation} where $y$ is randomly generated. @@ -1239,7 +1622,7 @@ It is possible to build a cryptographically secure PRNG based on the previous algorithm (Algorithm~\ref{algo:gpu_kernel2}). Due to Proposition~\ref{cryptopreuve}, it simply consists in replacing the {\it xor-like} PRNG by a cryptographically secure one. -We have chosen the Blum Blum Shum generator~\cite{BBS} (usually denoted by BBS) having the form: +We have chosen the Blum Blum Shub generator~\cite{BBS} (usually denoted by BBS) having the form: $$x_{n+1}=x_n^2~ mod~ M$$ where $M$ is the product of two prime numbers (these prime numbers need to be congruent to 3 modulus 4). BBS is known to be very slow and only usable for cryptographic applications. @@ -1255,7 +1638,7 @@ lesser than $2^{16}$. So in practice we can choose prime numbers around indistinguishable bits is lesser than or equals to $log_2(log_2(M))$). In other words, to generate a 32-bits number, we need to use 8 times the BBS algorithm with possibly different combinations of $M$. This -approach is not sufficient to be able to pass all the TestU01, +approach is not sufficient to be able to pass all the tests of TestU01, as small values of $M$ for the BBS lead to small periods. So, in order to add randomness we have proceeded with the followings modifications. @@ -1290,7 +1673,7 @@ variable for BBS number 8 is stored in place 1. \end{itemize} \begin{algorithm} - +\begin{small} \KwIn{InternalVarBBSArray: array with internal variables of the 8 BBS in global memory\; NumThreads: Number of threads\; @@ -1326,7 +1709,7 @@ array\_shift[4]=\{0,1,3,7\}\; } store internal variables in InternalVarXorLikeArray[threadId] using a rotation\; } - +\end{small} \caption{main kernel for the BBS based PRNG GPU} \label{algo:bbs_gpu} \end{algorithm} @@ -1344,7 +1727,7 @@ variability. In these operations, we make twice a left shift of $t$ of \emph{at most} 3 bits, represented by \texttt{shift} in the algorithm, and we put \emph{exactly} the \texttt{shift} last bits from a BBS into the \texttt{shift} last bits of $t$. For this, an array named \texttt{array\_shift}, containing the -correspondance between the shift and the number obtained with \texttt{shift} 1 +correspondence between the shift and the number obtained with \texttt{shift} 1 to make the \texttt{and} operation is used. For example, with a left shift of 0, we make an and operation with 0, with a left shift of 3, we make an and operation with 7 (represented by 111 in binary mode). @@ -1358,6 +1741,41 @@ 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, +an attacker can realize $10^{12}$ clock cycles. +We thus wonder whether, during the PRNG's +lifetime, the attacker can distinguish this +sequence from truly random one, with a probability +greater than $\varepsilon = 0.2$. +We consider that $N$ has 900 bits. + +The random process is the BBS generator, which +is cryptographically secure. More precisely, it +is $(T,\varepsilon)-$secure: no +$(T,\varepsilon)-$distinguishing attack can be +successfully realized on this PRNG, if~\cite{Fischlin} +$$ +T \leqslant \dfrac{L(N)}{6 N (log_2(N))\varepsilon^{-2}M^2}-2^7 N \varepsilon^{-2} M^2 log_2 (8 N \varepsilon^{-1}M) +$$ +where $M$ is the length of the output ($M=100$ in +our example), and $L(N)$ is equal to +$$ +2.8\times 10^{-3} exp \left(1.9229 \times (N ~ln(2)^\frac{1}{3}) \times ln(N~ln 2)^\frac{2}{3}\right) +$$ +is the number of clock cycles to factor a $N-$bit +integer. + +A direct numerical application shows that this attacker +cannot achieve its $(10^{12},0.2)$ distinguishing +attack in that context. + +\end{color} + \subsection{Toward a Cryptographically Secure and Chaotic Asymmetric Cryptosystem} \label{Blum-Goldwasser} We finish this research work by giving some thoughts about the use of @@ -1414,9 +1832,11 @@ Alice will pick randomly $S^0$ in $\llbracket 0, 2^{\mathsf{N}-1}\rrbracket$ too her new public key will be $(S^0, N)$. To encrypt his message, Bob will compute -\begin{equation} -c = \left(m_0 \oplus (b_0 \oplus S^0), m_1 \oplus (b_0 \oplus b_1 \oplus S^0), \hdots, m_{L-1} \oplus (b_0 \oplus b_1 \hdots \oplus b_{L-1} \oplus S^0) \right) -\end{equation} +%%RAPH : ici, j'ai mis un simple $ +%\begin{equation} +$c = \left(m_0 \oplus (b_0 \oplus S^0), m_1 \oplus (b_0 \oplus b_1 \oplus S^0), \hdots, \right.$ +$ \left. m_{L-1} \oplus (b_0 \oplus b_1 \hdots \oplus b_{L-1} \oplus S^0) \right)$ +%%\end{equation} instead of $\left(m_0 \oplus b_0, m_1 \oplus b_1, \hdots, m_{L-1} \oplus b_{L-1} \right)$. The same decryption stage as in Blum-Goldwasser leads to the sequence @@ -1438,10 +1858,10 @@ namely the BigCrush. Furthermore, we have shown that when the inputted generator is cryptographically secure, then it is the case too for the PRNG we propose, thus leading to the possibility to develop fast and secure PRNGs using the GPU architecture. -Thoughts about an improvement of the Blum-Goldwasser cryptosystem, using the -proposed method, has been finally proposed. +\begin{color}{red} An improvement of the Blum-Goldwasser cryptosystem, making it +behaves chaotically, has finally been proposed. \end{color} -In future work we plan to extend these researches, building a parallel PRNG for clusters or +In future work we plan to extend this research, building a parallel PRNG for clusters or grid computing. Topological properties of the various proposed generators will be investigated, and the use of other categories of PRNGs as input will be studied too. The improvement of Blum-Goldwasser will be deepened. Finally, we