X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/0cafd2bf1c7bf4758d8f1aa902d08d880419b67d..4635b3f66f097ccf0ad342948e2a29906bdbb32a:/prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 74b78a9..6782175 100644
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -996,9 +996,9 @@ tab1, tab2: Arrays containing combinations of size combination\_size\;}
   o2 = threadIdx-offset+tab2[offset]\;
   \For{i=1 to n} {
     t=xor-like()\;
-    t=t$\oplus$shmem[o1]$\oplus$shmem[o2]\;
+    t=t $\hat{ }$ shmem[o1] $\hat{ }$ shmem[o2]\;
     shared\_mem[threadId]=t\;
-    x = x $\oplus$ t\;
+    x = x $\hat{ }$ t\;
 
     store the new PRNG in NewNb[NumThreads*threadId+i]\;
   }
@@ -1118,15 +1118,15 @@ In this section the concatenation of two strings $u$ and $v$ is classically
 denoted by $uv$.
 In a cryptographic context, a pseudorandom generator is a deterministic
 algorithm $G$ transforming strings  into strings and such that, for any
-seed $w$ of length $N$, $G(w)$ (the output of $G$ on the input $w$) has size
-$\ell_G(N)$ with $\ell_G(N)>N$.
+seed $k$ of length $k$, $G(k)$ (the output of $G$ on the input $k$) has size
+$\ell_G(k)$ with $\ell_G(k)>k$.
 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(N)},$$
+$$| \mathrm{Pr}[D(G(U_k))=1]-Pr[D(U_{\ell_G(k)})=1]|< \frac{1}{p(k)},$$
 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
 internal coin tosses of $D$. 
@@ -1305,9 +1305,9 @@ tab: 2D Arrays containing 16 combinations (in first dimension)  of size combinat
     t|=BBS1(bbs1)\&7\;
      t<<=BBS7(bbs7)\&3\;
     t|=BBS2(bbs2)\&7\;
-    t=t$\oplus$shmem[o1]$\oplus$shmem[o2]\;
+    t=t $\hat{ }$ shmem[o1] $\hat{ }$ shmem[o2]\;
     shared\_mem[threadId]=t\;
-    x = x $\oplus$ t\;
+    x = x $\hat{ }$ t\;
 
     store the new PRNG in NewNb[NumThreads*threadId+i]\;
   }
@@ -1326,10 +1326,72 @@ been used.
 
 
 
-\subsection{A Secure Asymetric Cryptosystem}
+\subsection{Toward a Cryptographically Secure and Chaotic Asymmetric Cryptosystem}
 
+We finish this research work by giving some thoughts about the use of
+the proposed PRNG in an asymmetric cryptosystem.
+This first approach will be further investigated in a future work.
 
+\subsubsection{Recalls of the Blum-Goldwasser Probabilistic Cryptosystem}
 
+The Blum-Goldwasser cryptosystem is a cryptographically secure asymmetric key encryption algorithm 
+proposed in 1984~\cite{Blum:1985:EPP:19478.19501}.  The encryption algorithm 
+implements a XOR-based stream cipher using the BBS PRNG, in order to generate 
+the keystream. Decryption is done by obtaining the initial seed thanks to
+the final state of the BBS generator and the secret key, thus leading to the
+ reconstruction of the keystream.
+
+The key generation consists in generating two prime numbers $(p,q)$, 
+randomly and independently of each other, that are
+ congruent to 3 mod 4, and to compute the modulus $N=pq$.
+The public key is $N$, whereas the secret key is the factorization $(p,q)$.
+
+
+Suppose Bob wishes to send a string $m=(m_0, \dots, m_{L-1})$ of $L$ bits to Alice:
+\begin{enumerate}
+\item Bob picks an integer $r$ randomly in the interval $\llbracket 1,N\rrbracket$ and computes $x_0 = r^2~mod~N$.
+\item He uses the BBS to generate the keystream of $L$ pseudorandom bits $(b_0, \dots, b_{L-1})$, as follows. For $i=0$ to $L-1$,
+\begin{itemize}
+\item $i=0$.
+\item While $i \leqslant L-1$:
+\begin{itemize}
+\item Set $b_i$ equal to the least-significant\footnote{BBS can securely output up to $\mathsf{N} = \lfloor log(log(N)) \rfloor$ of the least-significant bits of $x_i$ during each round.} bit of $x_i$,
+\item $i=i+1$,
+\item $x_i = (x_{i-1})^2~mod~N.$
+\end{itemize}
+\end{itemize}
+\item The ciphertext is computed by XORing the plaintext bits $m$ with the keystream: $ c = (c_0, \dots, c_{L-1}) = m \oplus  b$. This ciphertext is $[c, y]$, where $y=x_{0}^{2^{L}}~mod~N.$
+\end{enumerate}
+
+
+When Alice receives $\left[(c_0, \dots, c_{L-1}), y\right]$, she can recover $m$ as follows:
+\begin{enumerate}
+\item Using the secret key $(p,q)$, she computes $r_p = y^{((p+1)/4)^{L}}~mod~p$ and $r_q = y^{((q+1)/4)^{L}}~mod~q$.
+\item The initial seed can be obtained using the following procedure: $x_0=q(q^{-1}~{mod}~p)r_p + p(p^{-1}~{mod}~q)r_q~{mod}~N$.
+\item She recomputes the bit-vector $b$ by using BBS and $x_0$.
+\item Alice computes finally the plaintext by XORing the keystream with the ciphertext: $ m = c \oplus  b$.
+\end{enumerate}
+
+
+\subsubsection{Proposal of a new Asymmetric Cryptosystem Adapted from Blum-Goldwasser}
+
+We propose to adapt the Blum-Goldwasser protocol as follows. 
+Let $\mathsf{N} = \lfloor log(log(N)) \rfloor$ be the number of bits that can
+be obtained securely with the BBS generator using the public key $N$ of Alice.
+Alice will pick randomly $S^0$ in $\llbracket 0, 2^{\mathsf{N}-1}\rrbracket$ too, and
+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}
+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 
+$\left(m_0 \oplus S^0, m_1 \oplus S^0, \hdots, m_{L-1} \oplus S^0 \right)$.
+Thus, with a simple use of $S^0$, Alice can obtained the plaintext.
+By doing so, the proposed generator is used in place of BBS, leading to
+the inheritance of all the properties presented in this paper.
 
 \section{Conclusion}