![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
Here is how the system works. To encrypt a plaintext x, choose a randomizer 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 then
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 When Bob receives the ciphertext, he can compute s0 from 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.
More generally, 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 Alices seed r = 20749. Then he constructs Alices keystream from r. Finally, he exclusive-ors the keystream with the ciphertext to get the plaintext. 12.5 Notes and ReferencesA 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].
The idea of probabilistic encryption is due to Goldwasser and Micali [GM84]; the Blum-Goldwasser Cryptosystem is presented in [BG85].
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |