Introduction to Cryptography with Open-Source Software

108 Cryptography with Open-Source Software

Weakness of Rabin

A major weakness of the Rabin cryptosystem is that it is completely

insecure against a chosen-ciphertext attack. Suppose the four square roots

s

1

, s

2

, s

3

, s

4

correspo nding to a known plaintext m are all known. Compute

the values

gcd(s

i

− s

j

, N)

for all possible pairs of square roots. (Recall that N is the public key, so it

is known.) A value not equal to 1 will be a factor of N . For example, in the

above example,

s

1

= 490,

s

2

= 1897,

s

3

= 180,

s

4

= 1587.

Now the gcds of all the differences with N = 2077 can be calculated:

gcd(s

1

− s

2

, N) = 67,

gcd(s

1

− s

3

, N) = 31,

gcd(s

1

− s

4

, N) = 1,

gcd(s

2

− s

3

, N) = 1,

gcd(s

2

− s

4

, N) = 31,

gcd(s

3

− s

4

, N) = 67.

Both factors of N have bee n deter mined, and the system is