Computer Security and Cryptography

17.6 RABIN'S QUADRATIC RESIDUE SIGNATURE PROTOCOL

We begin by considering the important result of Michael Rabin who proved in Rabin [1979] the equivalence of the security of a signature scheme and the difficulty of factorization. We make use of the material on quadratic residues in Section 13.4.

Rabin's Quadratic Residue Signature Protocol depends on the equivalence of three problems:

Problem A

Given: N = pq, a product of two primes p, q,

Find: The factors p, q.

Problem B

Given: N = pq, a product of two primes p, q and an integer x = s² (modulo N),

Find: All quadratic residues of x, the four solutions y₁, y₂, y₃, y₄ of y² − x = 0 (modulo N).

Problem C

Given: N = pq, a product of two primes p, q and an integer x = s² (modulo N),

Find: Any quadratic residue of x, a solution y of y² − x = 0 (modulo N).

The Chinese Remainder Theorem shows how to find the quadratic residue y² − x = 0 (modulo N) from the solutions of (modulo p) and (modulo q). Berlekamp's Algorithm (Proposition 13.4) shows how to compute quadratic residues if the factors of N = pq are known. Proposition 13.7 concludes that Problems A and B are equivalent. The equivalence of Problem C to Problem B follows from Proposition 17.1.

Proposition 17.1 : If the algorithm solves the problem

Given: N = pq, a product of two primes ...