6
$\begingroup$

Using the L-notation, integer factorization of an integer $n$ has the best known complexity of $L_n[1/3,c]$ using general number field sieve. Would discovery of an algorithm with complexity $L_n[1/4,c]$ be of any consequential significance to security of RSA-2048? If my computation is correct, for $c \approx 2$, it shows the complexity is reduced from $10^{36}$ to $10^{23}$, which seems doable with today's hardware. But I'm not confident in my computation or my assumptions about the capabilities of today's hardware.

Edit: here are my computations and assumptions: $\log(2^{2048})\approx1420$. $L_n[1/3,2]\approx \exp [2 (1420)^{1/3} (\log 1420)^{^{1 - 1/3}}]\approx 10^{36}$. $L_n[1/4,2]\approx \exp [2 (1420)^{1/4} (\log 1420)^{^{1 - 1/4}}]\approx 10^{23}$. Assuming $10^9$ possibilities can be tested every second and there are $10^6$ such processing units, it takes 3 years to crack RSA-2048: $10^{23} / (10^{9}\cdot60\cdot60\cdot24\cdot365)\approx 3 \times 10^6$.

$\endgroup$
4
$\begingroup$

Let's first quickly recap what $L_n[\alpha,c]$ actually means.

$$L_n[\alpha,c]=e^{(c+o(1))(\ln n)^{\alpha}(\ln\ln n)^{1-\alpha}}$$

$o(1)$ hides a constant (implementation and platform dependent) factor. For the rest of my answer I'll have to assume that the hidden factor is the same for the GNFS and the hypothetical $L_n[\alpha,c]$ algorithm (i.e. derived from $L_{2^{2048}}[1/3,(64/9)^{1/3}]=2^{112} \Rightarrow o(1)\approx -0.08035$).

In the next step you just plug-in your values for $\alpha$ and $c$ and get the result, for $\alpha=1/4$, this is:

$$L_{2^{2048}}[1/4,(64/9)^{1/3}]\approx 2^{72.15}$$

So if the algorithm is similarly fast (in terms of $c$ and hidden factors) it would reduce the security of 2048-bit RSA from roughly 112-bit to 72-bit which is considered borderline breakable (for nation states) right now.

Much more interesting though is the question how long would a modulus need to be in order to provide the same 112-bit security RSA-2048 did. This would ramp up the modulus length from 2048 to 7319 bits (!). And for 128-bit security you'd roughly need 10,891 bits instead of the roughly 3072 bits (extrapolation above would give 2800) right now.

$\endgroup$
  • 3
    $\begingroup$ The assumption "the hidden factor is the same for the GNFS and the hypothetical algorithm" does not have much ground. These constants are not just a matter of implementation and platform, they can vary a lot from one $L_n[\alpha,c]$ algorithm to another $L_n[\alpha',c']$ algorithm. The fact that these two algorithms (GNFS and the hypothetical one) both solve the same problem by no means justifies that the underlying constants are comparable. Deriving actual numbers from asymptotics is a risky business. $\endgroup$ – Calodeon Jan 5 '16 at 22:26
5
$\begingroup$

Unfortunately, deriving actual numbers from asymptotic bounds makes little sense (after all, $10^{36}$ and $10^{23}$ are both $O(1)$). Getting an idea of the actual cost of running an algorithm requires a fine analysis of the algorithm itself; asymptotic results are not sufficient. An $L_n[1/4]$ algorithm for factoring would be a great theoretical result, but it wouldn't necessarily perform better than the current algorithms on, say, RSA-2048.

Fear the hidden constant factors.

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