-3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Hint: How is the RSA private key computed? $\endgroup$ – yyyyyyy Aug 5 '18 at 14:50
  • $\begingroup$ 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. $\endgroup$ – M.J.Watson Aug 5 '18 at 15:06
  • $\begingroup$ 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. $\endgroup$ – SEJPM Aug 5 '18 at 16:21
  • $\begingroup$ @SEJPM m = p.q and d = e ^ -1 mod((p-1)(q-1)) with extended Euclidean algorithm i can compute d. $\endgroup$ – M.J.Watson Aug 5 '18 at 16:26
  • 2
    $\begingroup$ 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. $\endgroup$ – Ella Rose Aug 5 '18 at 19:37
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.