Flexibility in $RSA$ and $DLOG$ standards?

Question

Today's security is based on $RSA$ and $DLOG$ primarily. If both go down then it is hard to imagine a scenario where internet can be salvaged quickly.

Assume $RSA$ with $n$ bit prime factors and $DLOG$ with $n$ bit prime modulus have a (possibly practially realizable (Shor's algorithm still has challenges in implementation) quauntum) algorithm with $\leq(20n)^{2.5}$ time (picked an exponent on par with today's linear programming complexity exponent and $20$ was a reasonable small number). Then if we take $10^{25}$ arithmetic operations as ultimate limit of realizable complexity then if $n\leq 5\times 10^8$ holds we can break it ($(20n)^{2.5}\leq10^{25}\iff(20n)^{}\leq10^{10}\iff2n\leq10^9$).

How large can $RSA$ and $DLOG$ keys be before the standard gives up?

Is it reasonable to assume $10^9$ bit keys are possible with next generation internet?

Answer 1

How large can RSA and DLOG keys be before the standard gives up?

In theory, they can be indefinitely long using some implementation adaptions. However, they would become too impractical compared to post-quantum algorithms which do not require such key lengths that no one will use them.

Is it reasonable to assume $10^9$ bit keys are possible with next generation internet?

I am not sure what you mean with "next generation internet", but the answer is most likely no, independently of what you mean with this. The reasoning for this is as follows: the hardness assumptions of RSA and ECC, on which the security of these schemes relies, are indeed based on factorization and the dlog problem. Hardness is here defined as: "there exists no polynomial-time algorithm which can solve this problem". However, with a sufficiently large error-corrected quantum computer and using Shor's algorithm, these hardness assumptions are not hard anymore. I.e.: this algorithm (and for d-log a slightly modified one) can solve these problems in polynomial time.

Solving this issue with keys of $10^9$ will never happen, because there exists plenty of algorithms which are based upon other hardness problems for which no polynomial solving algorithm is known in the presence of such quantum computers. Therefore: no, $10^9$ bit keys will most likely not be used anytime soon (next ~50 years).

If you are interested in public-key post-quantum algorithms which are in a competition by NIST to become the next standard, take a look here: https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions