-4
$\begingroup$

Is there a former proof for why larger prime numbers make RSA securer? Maybe a theorem to show that it takes much more time to find out the private key if primes are larger?

$\endgroup$
2
$\begingroup$

Increasing the prime numbers does not necessarily lead to an increase in security of the RSA. As an example, when the private exponent is less than $\frac{N^{\frac{1}{4}}}{3}$, Wiener's attack is able to factor $N$ in the polynomial time.

There are other attacks against this system, which can be found in "Twenty Years of Attacks on the RSA Cryptosystem" and "Thirty Years of Attacks on the RSA Cryptosystem".

$\endgroup$
2
$\begingroup$

The idea that RSA relies on the difficulty of integer factorization is called the RSA problem. The efficiency of the different methods to perform integer factorization is discussed in a similar article on Wikipedia.

Theoretically, there may be more efficient methods to perform factorization; we cannot prove that there aren't. Therefore we cannot prove RSA is secure either.

$\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.