Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

How can someone estimate the number of years needed to factor an RSA key based on the advancement of technology if followed Moore's law?

share|improve this question
1  
An estimation based on Moore's law and current integer factorization is not a realistic estimate (and probably it will state something like thousands of years for RSA 2048). The reason is that having a more powerful computer does not matter much, when compared to finding a more efficient factoring algorithm. The general number sieve is the best algorithm we know, but a better algorithm might be found in the near future (or not). Also, there are approaches to optimize various aspects of the GNS, like polynomial selecation, which might speed up the process compared to today's method. –  tylo Oct 21 '13 at 17:19

2 Answers 2

It is hard. Main problem is that RSA key breaking relies on integer factorization, for which the most efficient (known) algorithms use CPU but also RAM, with constraints on parallel computation. Moore's law is already a crude approximation of how CPU power evolves over time for a given budget; it fails to take into account memory size and latency (two distinct things).

In fact, Moore's law, as expressed by Gordon Moore, is about transistor density, which does not equate with performance; and Moore himself changed it occasionally. The version that was fashionable about 12 years ago was: "every three years, one can put four times as many transistors in a given area, and clock that twice faster". This translates to an increase in computational power of 1 bit per year when breaking symmetric algorithms with FPGA or ASIC; but for general purpose computers, this is more like a double in power every 18 months, because register size does not increase as fast, and even when registers grow, the data elements we put in them do not. Also, over the last decade, clock rate of CPU has more or less stabilized, so Moore's law can be maintained only through parallelism -- multiple cores. But not all algorithms are amenable to easy parallelism, in particular the big matrix reduction which is the last step of General Number Field Sieve, the current best algorithm for breaking RSA. That matrix reduction appears to be the bottleneck for keys longer than the current record (768 bits).

Read section 6 of this report for a discussion and pointers on the subject. All see this site for estimates computed by various organizations, and even more pointers.

share|improve this answer

Start with this formula: http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity

and either invert the formula or use newtons approximation.

as for the offset to work on:

http://en.wikipedia.org/wiki/RSA_numbers

the number RSA 1024 appears to not have been factorized, but many companies already moved on to 2048 or even 4096.

share|improve this answer
    
Unfortunately this answer links to a Wikipedia page with an incorrect formula: it confuses the number of bits of a number and its natural logarithm; and it misses an $o(1)$ term. The correct formula is here. –  fgrieu Oct 20 '13 at 10:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.