Cryptography: Theory and Practice:Pseudo-random Number Generation

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

Previous Table of Contents Next


Here is how the system works. To encrypt a plaintext x, choose a randomizer and compute y = eK(x,r). Any such value y = eK(x,r) can be decrypted to x. Property 2 is stating that the probability distribution of all encryptions of x cannot be distinguished from the probability distribution of all encryptions of x′ if x′ ≠ x. Informally, an encryption of x “looks like” an encryption of x′. The security parameter ε should be small: in practice we would want to have for some small c > 0.

We now present the Goldwasser-Micali Probabilistic Public-key Cryptosystem in Figure 12.9. This system encrypts one bit at a time. A 0 bit is encrypted to a random quadratic residue modulo n; a 1 bit is encrypted to a random pseudo-square modulo n. When Bob recieves an element he can use his knowledge of the factorization of n to determine whether y ∈ QR(n) or whether . He does this by computing

then


Figure 12.9  Goldwasser-Micali Probabilistic Public-key Cryptosystem

A more efficient probabilistic public-key cryptosystem was given by Blum and Goldwasser. The Blum-Goldwasser Probabilistic Public-key Cryptosystem is presented in Figure 12.10. The basic idea is as follows. A random seed s0 generates a sequence of psuedorandom bits using the BBS Generator. The zi’s are used as a keystream, i.e., the are exclusive-ored with the plaintext bits to form the ciphertext. As well, the element mod n is transmitted as part of the ciphertext.

When Bob receives the ciphertext, he can compute s0 from , then reconstruct the keystream, and finally exclusive-or the keystream with the ciphertext bits to obtain the plaintext. We should explain how Bob derives s0 from . Recall that each si-1 is the principal square root of si. Now, n = pq with pq ≡ 3 mod 4, so the square roots of any quadratic residue x modulo p are ±x(p+1)/4. Using properties of Jacobi symbols, we have that

It follows that x(p+1)/4 is the principal square root of x modulo p. Similarly, x(q+1)/4 is the principal square root of x modulo q. Then, using the Chinese remainder theorem, we can find the principal square root of x modulo n.


Figure 12.10  Blum-Goldwasser Probabilistic Public-key Cryptosystem

More generally, will be the principal root of x modulo p and will be the principal root of x modulo q. Since has order p - 1, we can reduce the exponent modulo p - 1 in the computation mod p. In a similar fashion, we can reduce the exponent modulo q - 1. In Figure 12.10, having obtained the principal roots of modulo p and modulo q (steps 1-4 of the decryption process), the Chinese remainder theorem is used to compute the principal root of modulo n.

Here is an example to illustrate.

Example 12.6

Suppose n = 192649, as in Example 12.4. Suppose further that Alice chooses r = 20749 and wants to encrypt the 20-bit plaintext string

She will first compute the keystream

exactly as in Example 12.4, and then exclusive-or it with the plaintext, to obtain the ciphertext

which she transmits to Bob. She also computes

and sends it to Bob.

Of course Bob knows the factorization n = 383 × 503, so (p + 1)/4 = 96 and (q + 1)/4 = 126. He begins by computing

and

Next, he calculates

and

Now Bob proceeds to solve the system of congruences

to obtain Alice’s seed r = 20749. Then he constructs Alice’s keystream from r. Finally, he exclusive-ors the keystream with the ciphertext to get the plaintext.

12.5 Notes and References

A lengthy treatment of PRBGs can be found in the book by Kranakis [KR86]. See also the survey paper by Lagarias [LA90].

The Shrinking Generator is due to Coppersmith, Krawczyk, and Mansour [CKM94]; another practical method of constructing PBRGs using LFSRs has been given by Gunther [GU88]. For methods of breaking the Linear Congruential Generator, see Boyar [BO89].

The basic theory of secure PRBGs is due to Yao [YA82], who proved the universality of the next bit test. Further basic results can be found in Blum and Micali [BM84]. The BBS Generator is described in [BBS86]. The security of the Quadratic Residues problem is studied by Goldwasser and Micali [GM84], on which we based much of Section 12.3.1. We have, however, used the approach of Brassard and Bratley [BB88A, Section 8.6] to reduce the error probability of an unbiased Monte Carlo algorithm.

Properties of the RSA Generator are studied in Alexi, Chor, Goldreich, and Schnorr [ACGS88]. PRBGs based on the Discrete Logarithm problem are treated in Blum and Micali [BM84], Long and Wigderson [LW88], and Håstad, Schrift, and Shamir [HSS93]. A sufficient condition for the secure extraction of multiple bits per iteration of a PRBG was proved by Vazirani and Vazirani [VV84].


Figure 12.11  Discrete Logarithm Generator

The idea of probabilistic encryption is due to Goldwasser and Micali [GM84]; the Blum-Goldwasser Cryptosystem is presented in [BG85].


Previous Table of Contents Next

Copyright © CRC Press LLC



Cryptography. Theory and Practice
Modern Cryptography: Theory and Practice
ISBN: 0130669431
EAN: 2147483647
Year: 1995
Pages: 133
Authors: Wenbo Mao

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net