# How can one calculate the estimated RSA key life based on Moore's law?

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?

• 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
Commented Oct 21, 2013 at 17:19

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.

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.

• 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
Commented Oct 20, 2013 at 10:27

Additionally the discussion on this topic from the NIST standards is very beneficial. They explain thoroughly the means by which they establish their standards and the manner in which it is possible to abstract a more general notion of security and compare strengths of symmetric and asymmetric cryptosystems reliably. Here is the link.