# Flexibility in $RSA$ and $DLOG$ standards?

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?

• Somebody made a proposal for PQ-RSA that uses terabyte sized keys. Yes, you read that right. Keys large enough that even a quantum computer can't crack it in a lifetime. Obviously it's a satirical proposal (because it's so obviously impractical), but it's very real nonetheless. – Natanael May 8 '19 at 13:21

Is it reasonable to assume $$10^9$$ bit keys are possible with next generation internet?
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).