From cdea906ee17a7138b88a76de59946faec4d948ce Mon Sep 17 00:00:00 2001
From: guyeux <guyeux@gmail.com>
Date: Wed, 7 Dec 2011 10:09:08 +0100
Subject: [PATCH] Ajout de Blum-Goldwasser

---
 mabase.bib   | 18 ++++++++++++++++++
 prng_gpu.tex | 45 ++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 62 insertions(+), 1 deletion(-)

diff --git a/mabase.bib b/mabase.bib
index aa9224d..6699bd3 100644
--- a/mabase.bib
+++ b/mabase.bib
@@ -753,6 +753,24 @@
   year = {1999}
 }
 
+
+@inproceedings{Blum:1985:EPP:19478.19501,
+ author = {Blum, Manuel and Goldwasser, Shafi},
+ title = {An efficient probabilistic public key encryption scheme which hides all partial information},
+ booktitle = {Proceedings of CRYPTO 84 on Advances in cryptology},
+ year = {1985},
+ isbn = {0-387-15658-5},
+ location = {Santa Barbara, California, United States},
+ pages = {289--302},
+ numpages = {14},
+ url = {http://dl.acm.org/citation.cfm?id=19478.19501},
+ acmid = {19501},
+ publisher = {Springer-Verlag New York, Inc.},
+ address = {New York, NY, USA},
+ keywords = {chosen cyphertext attack, integer factorization, partial information, passive adversaries, probabilistic encryption},
+} 
+
+
 @INPROCEEDINGS{bcgr11:ip,
   author = {Bahi, Jacques M. and Couchot, Jean-fran\c{c}ois and Guyeux, Christophe
 	and Richard, Adrien},
diff --git a/prng_gpu.tex b/prng_gpu.tex
index d7e4664..5ebe0ef 100644
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -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}
 
 
 
-- 
2.39.5