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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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).
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:
the number RSA 1024 appears to not have been factorized, but many companies already moved on to 2048 or even 4096.