X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/10e6981881d8b6f0b35ee256f3540d0a0c052324..3010272fc200ffae4e9223ba48c5f3caf05a4256:/prng_gpu.tex?ds=sidebyside diff --git a/prng_gpu.tex b/prng_gpu.tex index 7d94e0c..55fc756 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} @@ -38,10 +39,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 +57,13 @@ A chaotic version of the Blum-Goldwasser asymmetric key encryption scheme is fin \end{abstract} +} + +\maketitle + +\IEEEdisplaynotcompsoctitleabstractindextext +\IEEEpeerreviewmaketitle + \section{Introduction} @@ -135,7 +143,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 @@ -216,7 +224,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 +240,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 +259,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 +267,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 @@ -321,11 +332,13 @@ 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: +%%RAPH : ici j'ai coupé la dernière ligne en 2, c'est moche mais bon \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,E) & \longmapsto & \left( E_{j}.\delta (k,j)+ \right.\\ +& & & \left. f(E)_{k}.\overline{\delta (k,j)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},% \end{array}% \end{equation}% @@ -467,8 +480,9 @@ generator taken alone. Furthermore, our generator 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)} @@ -480,12 +494,16 @@ $s\leftarrow{\textit{XORshift}(n)}$\; $x\leftarrow{F_f(s,x)}$\; } return $x$\; -%\end{scriptsize} +\end{small} \caption{PRNG with chaotic functions} \label{CI Algorithm} \end{algorithm} + + + \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,7 +511,7 @@ $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} @@ -536,7 +554,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 @@ -605,12 +623,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: +%%RAPH : j'ai coupé la dernière ligne en 2, c'est moche \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},% +& (P,E) & \longmapsto & \left( E_{j}.\chi (j,P)+\right.\\ +& & &\left.f(E)_{j}.\overline{\chi(j,P)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},% \end{array}% \end{equation}% where + and . are the Boolean addition and product operations, and $\overline{x}$ @@ -622,7 +641,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 +668,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)$. @@ -740,12 +763,14 @@ G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are the same ($G_{f}$ is a shift of strategies) the distance between $(S^n,E^n)$ and $(S,E)$ is strictly less than $% 10^{-(k+1)}\leqslant \varepsilon $.\bigskip \newline In conclusion, -$$ +%%RAPH : ici j'ai rajouté une ligne +\begin{flushleft}$$ \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) +,\forall n\geqslant N_{0},$$ +$$ d\left( G_{f}(S^n,E^n);G_{f}(S,E)\right) \leqslant \varepsilon . $$ +\end{flushleft} $G_{f}$ is consequently continuous. \end{proof} @@ -785,7 +810,11 @@ where $(s^0,s^1, \hdots)$ is the strategy of $Y$, satisfies the properties claimed in the lemma. \end{proof} +<<<<<<< HEAD +We can now prove the Theorem~\ref{t:chaos des general}. +======= We can now prove Theorem~\ref{t:chaos des general}... +>>>>>>> e55d237aba022a66cc2d7650d295b29169878f45 \begin{proof}[Theorem~\ref{t:chaos des general}] Firstly, strong transitivity implies transitivity. @@ -803,8 +832,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 +1184,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 +1239,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 +1251,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. @@ -1255,7 +1294,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 +1329,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 +1365,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 +1383,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). @@ -1414,9 +1453,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