9. Blum-Goldwasser PKC We refer to the notation and concepts of the previous ex-

ercise to implement a public-key cryptosystem (due to M. Blum and S. Goldwasser)

which requires computational resources comparable to those of RSA but which, un-

like RSA, has the security feature that the encryption algorithm is not deterministic.⁸

For two large Blum integers *p* and *q* (see the previous exercise), we let their product

*n* = *p* · *q* be the public key. Messages are bit strings *M* of length *l* ∈ N. Your im-

plementation should allow for changing the parameters *p*, *q*, and *l*. Please reuse (or adapt) software that you have written for earlier exercises as you see fit.

(a) Implement the encryption of *l*-bit messages *M*, given a public key *n* = *p* · *q*:

(i) randomly select a nonzero *x* ∈ Z_*n*;

(ii) compute the *x_i* for *i* = 0, 1, ..., *l* + 1 as in the previous exercise, where *b_i*

is the least significant bit of *x_i*;

(iii) let the encrypted text be the pair (*x_l*₊₁, *C*), where *C* is the bitwise exclu-

sive-or of *M* and the string *b₁b₂* ... *b_l*.

(b) Implement the decryption component as follows.

(i) Compute the "private" key

$$

d \stackrel{\text{def}}{=} 2^{-(l+1)} \text{ mod } (p-1) \cdot (q-1).

$$

(ii) Given a cipher-text (*x'*, *C*), where *x'* ∈ Z_*n* and *C* is a binary word of length

*l*, we think of *x'* as the seed and compute the sequence

$$x_0 \stackrel{def}{=} (x')^d \mod n,$$
$$x_{i+1} \stackrel{def}{=} (x_i)^2 \mod n$$
accordingly for i = 0, 1,..., l-1. Letting b'i be the least significant bit of x'i, the decrypted text is the bitwise exclusive-or of C and the string b'1b'2...b'l.

(c) Prove that this scheme is sound using equation (2.15), and explain why all its components have efficient implementations.

(d) Do you have to recompute d for handling a new message?

(e) Does the security of this public-key cryptosystem depend on the size of l or n?

(f) Experiment with various choices of l and study the performance of this crypto-
system as a function of l.
(g) What does or should your implementation do if x' = 0 mod n?
(h) Suppose that we change all preceding occurrences of l + 1 to l. Could you still prove soundness? Could you still guarantee the security of the cryptosystem?
(i) Can an attacker launch a chosen plain-text attack if she knows only the public key?
(j) How often does a single encryption or decryption operation require a call to the underlying RSA function for modular exponentiation? Thinking of this opera-
tion as the performance bottleneck, what do your findings say about the efficiency of this PKC?