I was wondering aren't the most used prime factorization algorithms a symbolic mile behind the security of the RSA cryptosystem?
The way it looks to me is that every time an algorithm is able to crack RSA or in specific to find the two prime factors, you can just simply change the size of the prime factors.
Is it really that simple?
Anyways thank you all for your time and effort!
$\begingroup$
$\endgroup$
4
-
$\begingroup$ You can always increase the key size, but this comes at a cost: Time. When you're working in e.g. a 16384 bit group things are going to take a noticeably longer time. $\endgroup$– puzzlepalaceJun 15, 2017 at 16:57
-
$\begingroup$ @puzzlepalace but the effectivity of most factoring algorithms depend on computing power, so when it is possible to crack p and q, it is probable that you can upscale the computer power to make the calculations. (Moore's law: en.wikipedia.org/wiki/Moore%27s_law ) $\endgroup$– Faded CaptainJun 15, 2017 at 17:12
-
2$\begingroup$ That logic rather assumes that attacker's and the defender's capabilities rise at similar rates. This obviously isn't true if the attacker is trying to break encrypted traffic that was encrypted N years ago... $\endgroup$– ponchoJun 15, 2017 at 17:15
-
$\begingroup$ If the legitimate usage speed would scale the same as the speed of attacks, there would be little security in using RSA. $\endgroup$– SEJPMJun 15, 2017 at 17:16
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Is it really that simple?
If it weren't we would have to abandon RSA.
Here's why: To be able to run RSA somewhat decently fast, it needs to run in polynomial time in some parameter, let's call it $\lambda$. RSA is basically the same as modular exponentiation and thus runs in time $\mathcal O(\lambda^3)$ when $2^\lambda\approx n$. Now the best known generic factorization method, the GNFS runs in time $L_n\left[\frac13,\sqrt[3]{\frac{64}9}\right]=\exp\left(\left(\sqrt[3]{\frac{64}9}+o(1)\right)\cdot\sqrt[3]{\ln{2^\lambda}}\cdot\sqrt[3]{\ln{\ln{2^\lambda}}}^2\right)$, which is sub-exponential in $\lambda$. So if we double the key length (that is $\lambda$), we may 8-fold our workload, but we also take the attacker's workload to the power of at least $\sqrt[3]2$, which turns an $2^{80}$ attack into an $>2^{110}$ attack, thus increasing the attack complexity by at least a billion.
Now assume we could factor in time $\mathcal O(\lambda^n)$ for some somewhat small $n$. Now if we double the key length, we (the legitimate user) take 8-times the time, but the attacker now only takes $2^n$ times the time, so if he has $2^{n-3}$ as many cores or as good cores, he could recover the new key in the same time as before. So we'd have to repeat the increase in key length a few times (assuming $n\leq 20$) so that we, the user, get an edge of the attacker, but at this point key length become so large that RSA will be too slow to be good choice, especially if you consider low-power embedded systems.
