Recommended key size for life long key

[Robert J. Hansen]

On 9/8/2013 5:00 PM, Leo Gaspard wrote:
> BTW, the statement "[Dan Boneh] proved that breaking RSA is not 
> equivalent to factoring" is wrong : he did not prove that breaking 
> RSA is easier than factoring numbers ; only that a whole ways of 
> proving that breaking RSA is as hard as factoring numbers are 
> ineffective ; thereby reducing the search space for potential valid 
> ways of proving the conjecture. Hence the title of the article : 
> "Breaking RSA *may* not be equivalent to factoring". Please pardon
> me if I misunderstood the english used in the abstract.

>From the abstract, "We provide evidence that breaking low-exponent RSA
cannot be equivalent to factoring integers ... an oracle for breaking
RSA does not help in factoring integers."

The title involves the word 'may' out of an abundance of caution and a
decent respect for the opinions of the mathematical community.  Whether
he's proven it or not is not really for him to claim, but for the
mathematical community.  He's provided a conjecture and strong evidence
to support it, and I feel his conjecture is well-proven.  Your mileage
may vary.  :)

> Oh, and... Please correct me if I am mistaken, but I believe the
> best we can do at the moment, even with a quantum computer is Shor's 
> algorithm, taking a time of O(log^3 n). Thus, going from 2k keys to 
> 10k keys makes if approx. 125 times harder to break.

A factor of 125 is so small as to be irrelevant.

The real obstacle is that Shor's algorithm requires 2n qubits to be
formed in an ensemble, so you'd be going from requiring a 4k quantum
computer to a 20k quantum computer.  Given decoherence, that might
amount to a much more insurmountable obstacle.  Still, my money is on QC.

> And the first part is, still in my opinion, only here to explain why 
> 10k RSA keys were chosen for the experiment. Explaining that, 
> according to our current estimates, they might potentially resist 
> until 2100, assuming no major breakthrough is made until then in the 
> cryptanalysis field.

The problem is the exact same thing can be said for RSA-2048.  RSA-2048
is expected to last at least the next 25 years; it may last for the next
century.  Hard to say.  Depends a lot on the progression of science
fiction level technologies, like quantum computation.  And again, anyone
trying to predict out past about 25 years needs to explain why they are
able to do this where NIST, RSA Data Security, and so many others have
failed to be able to do this.