Cryptography: Theory and Practice:Pseudo-random Number Generation

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

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.

**Table 12.4** Blum-Goldwasser Ciphertext
	`E1866663F17FDBD1DC8C8FD2EEBC36AD7F53795DBA3C9CE22D`
	`C9A9C7E2A56455501399CA6B98AED22C346A529A09C1936C61`
	`ECDE10B43D226EC683A669929F2FFB912BFA96A8302188C083`
	`46119E4F61AD8D0829BD1CDE1E37DBA9BCE65F40C0BCE48A80`
	`0B3D087D76ECD1805C65D9DB730B8D0943266D942CF04D7D4D`
	`76BFA891FA21BE76F767F1D5DCC7E3F1D86E39A9348B3`

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.

Table of Contents