User:Cspan64/Sandbox

From Wikipedia, the free encyclopedia

This user comes from Germany.

This user comes from Baden-Württemberg.

[edit] Key generation

To allow for decryption, the modulus used in Blum-Goldwasser encryption should be a Blum integer. This value is generated in the same manner as an RSA modulus, except that the prime factors $(p, q)$ must be congruent to 3 mod 4. (See RSA, key generation for details.)

Alice generates two large prime numbers $p \,$ and $q \,$ such that $p \ne q$ , randomly and independently of each other, where $(p, q) \equiv 3$ mod $4$ .
Alice computes $N = p q$ .
Alice can also precompute now $q^{-1} \,$ and $p^{-1} \,$ , so that

$a p + b q = 1$ (Bezout's identity) using the extended euclidean algorithm.

The public key is $N$ . The secret key is the factorization $(p, q)$ .

[edit] Message decryption

Alice receives $(c_0, \dots, c_{L-1}), y$ . She can recover $m$ using the following procedure:

Using the prime factorization $(p, q)$ , Alice computes $r_p = y^{((p+1)/4)^{L}}~mod~(p-1)$ and $r_q = y^{((q+1)/4)^{L}}~mod~(q-1)$ .
Compute the initial seed $x_0=q(q^{-1}~{mod}~p)r_p + p(p^{-1}~{mod}~q)r_q~{mod}~N$
From $x 0$ , recompute the bit-vector ${\vec b}$ using the BBS generator, as in the encryption algorithm.
Compute the plaintext by XORing the keystream with the ciphertext: ${\vec m} = {\vec c} \oplus {\vec b}$ .