And why do we have to use big numbers for RSA? Is it because of some RSA restrictions like p=q=3 mod 4?
2
-
3$\begingroup$ Hint: study the runtime of the best known algorithm against RSA, GNFS; and of the best known algorithm against standard ECC crypto, Pollard's rho. $\endgroup$– fgrieu-onstrike ♦Jan 4, 2021 at 16:15
-
$\begingroup$ Dupe crypto.stackexchange.com/questions/3958/… crypto.stackexchange.com/questions/25577/… crypto.stackexchange.com/questions/31439/… and cross security.stackexchange.com/questions/59190/… $\endgroup$– dave_thompson_085Jan 5, 2021 at 2:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
There are some more efficient algorithms (still super-polynomial time, not enough to actually break them) to solve discrete logarithm problems and integer factorization problems, hence keys based on these problems are longer than EC based cryptographic keys which provide equivalent security, in which no such algorithms significantly better than birthday attack are known.
-
$\begingroup$ I know there are algorithms which require more time to solve these problems than other algorithms but my question is, what makes these algorithms take less time than the other? What makes RSA more vulnerable to attacks than EC? $\endgroup$– das42r4Jan 11, 2021 at 19:24