Exercises

12.1  Consider the Linear Congruential Generator defined by s_i = (as_i-1 + b) mod M. Suppose that M = qa + 1 where a is odd and q is even, and suppose that b = 1. Show that the next bit predictor B_i(z) = 1 - z for the i bit is an ε-next bit predictor, where

12.2  Suppose we have an RSA Generator with n = 36863, b = 229 and seed s₀ = 25. Compute the first 100 bits produced by this generator.

12.3  A PRBG based on the Discrete Logarithm problem is given in Figure 12.11. Suppose p = 21383, the primitive element α = 5 and the seed s₀ = 15886. Compute the first 100 bits produced by this generator.

12.4  Suppose that Bob has knowledge of the factorization n = pq in the BBS Generator.

(a)  Show how Bob can use this knowledge to compute any s_i from so with 2k multiplications modulo φ(n) and 2k multiplications modulo n, where n has k bits in its binary representation. (If i is large compared to k, then this approach represents a substantial improvement over the i multiplications required to sequentially compute s₀, …, s_i.)

(b)  Use this method to compute s₁₀₀₀₀ if n = 59701 = 227 × 263 and s₀ = 17995.

12.5  We proved that, in order to reduce the error probability of an unbiased Monte Carlo algorithm from 1/2 - ε to δ, where δ + ε < 1/2, it suffices to run the algorithm m times, where

Prove that this value of m is O(1/(δε²).

12.6  Suppose Bob receives some ciphertext which was encrypted with the Blum-Goldwasser Probabilistic Public-key Cryptosystem. The original plaintext consisted of English text. Each alphabetic character was converted to a bitstring of length five in the obvious way: A ↔ 00000, B ↔ 00001, …, Z ↔ 11001. The plaintext consisted of 236 alphabetic characters, so a bitstring of length 1180 resulted. This bitstring was then encrypted. The resulting ciphertext bitstring was then converted to a hexadecimal representation, to save space. The final string of 295 hexadecimal characters is presented in Table 12.4. Also, s₁₁₈₁ = 20291 is part of the ciphertext, and n = 29893 is Bob’s public key. Bob’s secret factorization of n is n = pq, where p = 167 and q = 179.

Your task is to decrypt the given ciphertext and restore the original English plaintext, which was taken from “Under the Hammer,” by John Mortimer, Penguin Books, 1994.