7.8 Security of the RSA algorithm
The security of the RSA algorithm relies on the following three assumptions:
The factoring problem is hard for the given public modulus n
The RSA problem is hard
The public keys of Alice and Bob are authentic
We will discuss each of these assumptions in turn.
7.8.1 The factoring problem
If an attacker manages to compute the two prime factors p and q of the public modulus n, they can repeat the steps taken by Alice when she computed her key pair. In particular, an attacker could compute Alice’s secret key and compromise the whole system. Therefore, the security of the RSA cryptosystem is crucially based on the intractability of the integer factorization problem, which is in general defined as follows:
Given a positive integer n, find its prime factors p1 to pk such that
where pi are pairwise distinct primes.
The fastest algorithm to factorize semiprimes, which are numbers of the form n = p ⋅ q with p and q primes of approximately equal...