Public-Key Cryptography - A Classical Introduction to Cryptography: Applications for Communications Security - page 233

s
2

Setup . We have to generate two random primes of bits. We know that this works

( s 4 ) elementary operations by using the Miller-Rabin
test over random integers. Then, multiplying p and q costs

within a complexity of O

( s 2 ), finding an

O

( s 2 ), and computing d requires

invertible e costs one gcd computation, hence O

( s 2 ) as well. In total the complexity is

an extended Euclid algorithm, hence O

( s 4 ).
Encryption . The encryption costs one full modular exponential, hence

O

( s 3 ). We
however often choose e in order to decrease this complexity. For instance, with
e

O

( s 2 ).
Decryption . The decryption costs one modular exponential, hence

2 16

= 17 or e = + 1, the complexity is O

( s 3 ).

O

The security analysis is more tricky. Obviously, the knowledge of p and q is enough
to recover the secret key and thus to break the system: we just need to invert e modulo
( p

1). Therefore the factorization of N enables breaking the system. This
does not mean that RSA is as strong as factoring is hard, although it is believed to be
so. Here are a few problems.

− 1)( q −

RSADP (RSA Decryption Problem)
Input : an RSA public key ( e N ), an encrypted message y .

Problem : compute x such that y

,

x e = mod N .

RSAKRP (RSA Key Recovery Problem)
Input : an RSA public key ( e N ).

Problem : compute d such that x ed

,

Z N .

mod N = x for any x ∈

RSAEMP (RSA Exponent Multiple Problem)
Input : an RSA modulus N .
Problem : find an integer k such that x k Z N (i.e.

mod N = 1 for any x ∈ λ ( N )

divides k ).
RSAOP (RSA Order Problem)
Input : an RSA modulus N .
Problem : compute the order of Z N (i.e. ϕ ( N )).

RSAFP (RSA Factorization Problem)
Input : an RSA modulus N .
Problem : compute the factorization of N .

Obviously, RSADP reduces to RSAKRP. Indeed, the secret key enables the decryption!
Reducing the other way is still an open problem: we cannot prove at this time that the
secret key is necessary in order to decrypt, nor that decrypting enables the computation
of the secret key. What we can prove is that RSAKRP is equivalent to RSAFP (i.e., the
knowledge of the secret key is equivalent to the ability to factorize N ), which does not
mean that decrypting is equivalent to factorizing. For this let us first do the following
reductions.

RSAKRP reduces to RSAOP . Clearly, if we can compute the order

ϕ ( N ) which

1), we can invert e modulo this order and get a d .
RSAOP is equivalent to RSAFP . Clearly, if we can factorize N ,weget p and q
and we can compute

is equal to ( p − 1)( q −

ϕ ( N ) = ( p − 1)( q − 1). Conversely, if we have ϕ ( N ), we