Quadratic Ciphers - Introduction to Cryptography with Java Applets - page 207

Some ciphers do not need to use chaining, for they are already stream ciphers. The fol-
lowing public key cipher is a perfect example.

10.6 BLUM-GOLDWASSER PROBABILISTIC CIPHER

This is another public key cipher based on quadratic congruences, which uses a mask at the
bit level with an exclusive-or operation. This cipher qualifies as a stream cipher, which
encrypts the same block differently depending on its position in the plaintext. Note that
Rabin and most of the other block ciphers presented thus far do not have this property; that
is, they always map a particular plaintext to the same ciphertext, unless we employ some
type of chaining.
To generate keys for Blum-Goldwasser, one must choose two large primes, p and q , both
congruent to 3 modulo 4, and let n = pq . At current levels of computing power, n should be
at least 1024 bits in length. Then, using the extended Euclidean algorithm, find two integers
a and b such that

ap + bq = 1.

The public key is the integer n , and the private key is the 4 values a , b , p , and q .
To encrypt a message (anyone can do this with the public key n ), one does the follow-
ing.
1. Let k be the largest integer not exceeding log 2 n , and let h be the largest integer not exceed-

ing log 2 k . Represent the plaintext message P as an array m 1 m 2 . . . m t of length t where
each m i is a binary number of length h .

2. Select a random square x 0 modulo n . One can do this by selecting a random integer r

between 1 and n 1, then setting

x 0 r 2 (mod n ) (0 < x 0 < n )

Now, for i = 1 to t (in order) do
• Let x i x i 1 2 (mod n ) (0 < x i < n )
• Let p i be the h least significant bits of x i .
• Let c i = p i m i .
4. Compute x t 1 x t 2 (mod n ) (0 < x t 1 < n )
5. Send the ciphertext message C = c 1 c 2 . . . c t and the integer x t 1 .
Note that only knowledge of n is required to encrypt. Now, to decrypt, the individual
possessing the private key values a , b , p , and q proceeds as follows.

3.

(( p + 1)/4) t 1 (mod p

1. Let d 1) (0 ≤ d < p 1)

(( q + 1)/4) t 1 (mod q

2. Let e 1) (0 ≤ e < q 1)

Let u x t 1 d (mod p )

3. (0 ≤ u < p )

Let v x t 1 e (mod q )

4. (0 ≤ v < q )

5. Retrieve x 0 by taking x 0 vap + ubq (mod n ) (0 < x 0 < n )