 The RSA problem

The intractability of the RSA problem forms the basis for the security of the RSA public-key encryption scheme (§8.2) and the RSA signature scheme (§11.3.1).

3.28 Definition The RSA problem (RSAP) is the following: given a positive integer n that is a product of two distinct odd primes p and q, a positive integer e such that gcd(e, (p — l)(q — 1)) = 1, and an integer c, find an integer m such that me = c (mod n).

In other words, the RSA problem is that of finding eth roots modulo a composite integer n. The conditions imposed on the problem parameters n and e ensure that for each integer c € {0,1,... ,n — 1} there is exactly one in e (0,1,... ,ra — 1} such that me = c (mod 7i). Equivalently, the function / : Zn —» Zn defined as f(m) = me mod 72 is a permutation.

3.29 Remark fSQROOT vs. RSA problems) Since p — 1 is even, it follows that e is odd. In particular, e Ф 2, and hence the SQROOT problem (Definition 3.43) is not a special case of the RSA problem.

As is shown in §8.2.2(i), if the factors of n are known then the RSA problem can be easily solved. This fact is stated next.

3.30 Fact RSAP

It is widely believed that the RSA and the integer factorization problems are computationally equivalent, although no proof of this is known.

The security of the Goldwasser-Micali probabilistic public-key encryption scheme (§8.7) and the Blum-Blum-Shub pseudorandom bit generator (§5.5.2) are both based on the apparent intractability of the quadratic residuosity problem.

Recall from §2.4.5 that if n > 3 is an odd integer, then ,/„ is the set of all a e Z* having Jacobi symbol 1. Recall also that Q„ is the set of quadratic residues modulo n and that the set of pseudosquares modulo n is defined by Qn = Jn - Qn.

• 3.31 Definition The quadratic residuosity problem (QRP) is the following: given an odd composite integer n and a e J„, decide whether or not a is a quadratic residue modulo n.
• 3.32 Remark (QRP with a prime modulus) If n is a prime, then it is easy to decide whether a e Z* is a quadratic residue modulo n since, by definition, aQn if and only if (^) = 1, and the Legendre symbol (£) can be efficiently calculated by Algorithm 2.149.

Assume now that n is a product of two distinct odd primes p and q. It follows from Fact 2.137 that if a e Jn, then a € Qn if and only if (|) = 1. Thus, if the factorization of n is known, then QRP can be solved simply by computing the Legendre symbol (|). This observation can be generalized to all integers n and leads to the following fact.

3.33 Fact QRP FACTORING. That is, the QRP polytime reduces to the FACTORING problem.

On the other hand, if the factorization of n is unknown, then there is no efficient procedure known for solving QRP, other than by guessing the answer. If n = pq, then the probability of a correct guess is i since |Q„| = Qn (Fact 2.155). It is believed that the QRP is as difficult as the problem of factoring integers, although no proof of this is known.