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

TABLE 10.3

c i =p i +

i x i x i (in binary) p i m i m i

1 61585 1111000010010001 0001 1001 1000

2 245137 111011110110010001 0001 1100 1101

3 9347 10010010000011 0011 0010 0001

4 144197 100011001101000101 0101 1111 1010

5 188862 101110000110111110 1110 1010 0100

TABLE 10.4

m i =p i +

i x i x i (in binary) p i c i c i

1 61585 1111000010010001 0001 1000 1001

2 245137 111011110110010001 0001 1101 1100

3 9347 10010010000011 0011 0001 0010

4 144197 100011001101000101 0101 1010 1111

5 188862 101110000110111110 1110 0100 1010

To decrypt the message, the recipient must retrieve the random seed that the sender chose.
Then she can compute the same sequence of squares x 1 , x 2 , x 3 , x 4 , x 5 and retrieve the plain-
text by

-ing the 4 least significant bits of the squares with the ciphertext. She does this by
computing

d ((503 + 1)/4) 6

302 (mod 502)

e ((563 + 1)/4) 6

101 (mod 562)

67738 302

u 468 (mod 503)

v 67738 101

90 (mod 563).
Finally, she obtains x 0 , the lnr of vap + ubq modulo n .
x 0

258507 (mod 283189)
For completeness, Table 10.4 shows the recovery process.
Thus, the plaintext P = 1001 1100 0010 1111 1010 is regained.

90 122 503 + 468 109 563

10.7

WEAKNESSES OF THE BLUM-GOLDWASSER PROBABILISTIC
CIPHER
This cipher can be broken if the following weaknesses are not dealt with. First, the primes
must be chosen carefully; for example, we must avoid primes p for which the factorization