1
$\begingroup$

In RSA we have value of n and e which is known to sender. If the sender keep maintaining a database of possible n's he can easy calculate $\phi(n)$ because he already know $p$ and $q$ then. $d$ is $e^{-1} \mod \phi(n)$.

If we choose a large number which is product of two primes, can an attacker predict value of $d$?

$\endgroup$
1
$\begingroup$

Technically you're right, if you get the two prime-factors of n (p and q), then you can calculate everything else pretty easily.

But that's the problem! There is no known way to calculate p and q efficiently, but it is also unproven, if there really isn't a suitable algorithm and RSA is purposefully implemented in that way.

This is actually one of the big unsolved questions in mathematics.

See:

Also your idea with storing a database of possible n's is infeasible, because this database would be unimaginably huge. You would have to store all possible calculations which would easily be greater than the number of atoms in the universe by far.

$\endgroup$
  • 1
    $\begingroup$ Neither Factoring nor the RSA Problem are known to be NP-Hard, therefore, finding a polynomial time algorithm to any of them has no impact on the P vs NP issue. $\endgroup$ – Hilder Vítor Lima Pereira Apr 9 '18 at 13:36
  • $\begingroup$ It's clearly of the class NP (second link) and thought to be NP-complete, but as I said: unproven. $\endgroup$ – AleksanderRas Apr 9 '18 at 13:50
  • $\begingroup$ Even without storing, there's not enough energy in the universe to compute all semiprimes, or the prime factors, for RSA sizes actually used. $\endgroup$ – dave_thompson_085 Apr 10 '18 at 3:51

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