Ajout de Blum-Goldwasser

[prng_gpu.git] / prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 74b78a90e60f39ce45dbb35945db7bf3685d2adb..5ebe0efb295e6ae78a21bead73fd1cf8cef19b52 100644 (file)
--- 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()\;
   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\;
     shared\_mem[threadId]=t\;

-    x = x $\oplus$ t\;
+    x = x $\hat{ }$ t\;

 
     store the new PRNG in NewNb[NumThreads*threadId+i]\;
   }
 
     store the new PRNG in NewNb[NumThreads*threadId+i]\;
   }


@@ -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|=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\;
     shared\_mem[threadId]=t\;

-    x = x $\oplus$ t\;
+    x = x $\hat{ }$ t\;

 
     store the new PRNG in NewNb[NumThreads*threadId+i]\;
   }
 
     store the new PRNG in NewNb[NumThreads*threadId+i]\;
   }


@@ -1326,8 +1326,51 @@ been used.
 
 
 
 
 
 

-\subsection{A Secure Asymetric Cryptosystem}
+\subsection{A Cryptographically Secure and Chaotic Asymetric Cryptosystem}

 
 

+\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 an 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 $[1,N$ 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 O(loglogN) of the least-significant bits of xi 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$.
+\end{enumerate}
+The ciphertext is $(c, y)$, where $y=x_{0}^{2^{L}}~mod~N.$.
+
+
+When Alice receives $(c_0, \dots, c_{L-1}), y$, 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 Recompute the bit-vector $b$ by using BBS and $x_0$.
+\item Compute 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}