# Why would an efficient integer factorization algorithm render RSA insecure?

I know that RSA relies on the integer factorization problem: given two primes p and q, their product p . q is easy to compute. But not feasible (i.e., polynomial-time) an algorithm is known that could factor an arbitrary product p.q.

Why would an efficient integer factorization algorithm render RSA insecure?

• Hint: How is the RSA private key computed? – yyyyyyy Aug 5 '18 at 14:50
• For k = (m; d; e), ek (x) = x^e mod m and dk (y) = y^d mod m. The values m and e comprise as the public key. The values m and d comprise as the private key. – M.J.Watson Aug 5 '18 at 15:06
• Ok let's formulate it differently. If you have $p,q,e$ how do you come up with $m,d$? Hint: This is what happens during key generation. – SEJPM Aug 5 '18 at 16:21
• @SEJPM m = p.q and d = e ^ -1 mod((p-1)(q-1)) with extended Euclidean algorithm i can compute d. – M.J.Watson Aug 5 '18 at 16:26
• I would re-phrase SEJPMs comment as "Now that you know that, can you answer your question? ", meaning supply the answer you now have in the answer box below. – Ella Rose Aug 5 '18 at 19:37

I know that RSA relies on the integer factorization problem: given two primes $p$ and $q$, their product $p . q$ is easy to compute. But not feasible (i.e., polynomial-time) an algorithm is known that could factor an arbitrary product $p.q$.

Hence, multiplication of primes $p.q$ is believed to be a one-way function. Let $e,m$ be positive integers.

Lets define $f:z_m \rightarrow z_m$ by $f(x):= x^e \mod m$

$f(x)$ can be computed efficiently using the square and multiply algorithm, on the other hand, solving $y=x^e \bmod m$ for $x$ (i.e computing the $e$-th root of $y$ modulo $m$) is thought to be hard. This is the RSA problem. Hence modular exponentiation is believed to be a one-way function.

Also, RSA Key Generation gives us the hint

1)Choose two large distinct prime number $p$ and $q$.

2)Compute $m = p.q$

3)$φ= (p-1)(q-1)$

4)Choose an integer e such that $1<e<φ$ and $\operatorname{gcd}(e,φ) =1$

5)Compute $d=e^{-1} \bmod φ$. (The extended algorithm computes $gcd(e,φ)$ and $d$.

6)Publish $m$ and $e$ keep $d$ private.

The integer factorisation problem and the RSA problem are computationally hard. A polynomial-time quantum factorisation problem is known. To prevent plaintext attacks and other attacks, RSA in practice employs random padding of the message.

Side-channel attacks on RSA implementations are known that determine private keys such as $d$ and $m$. The key size for RSA refers to the bit size of the modulus. A brute-force attack is possible (in principle), but not necessary: an attacker can instead try to factor the modulus.