RSA Laboratories

2.3.5 What improvements are likely in factoring capability?

Factoring (see Question 2.3.3) has become easier over the last 15 years for three reasons: computer hardware has become more powerful, computers have become more plentiful and inexpensive, and better factoring algorithms have emerged.

Hardware improvement will continue inexorably, but it is important to realize hardware improvements make the RSA cryptosystem more secure, not less. This is because a hardware improvement that allows an attacker to factor a number two digits longer than before will at the same time allow a legitimate RSA algorithm user to use a key dozens of digits longer than before. Therefore, although the hardware improvement does help the attacker, it helps the legitimate user much more. However, there is a danger that in the future factoring will take place using faster machines than are currently available, and these machines may be used to attack RSA cryptosystem keys generated in the past. In this scenario, the attacker alone benefits from the hardware improvement. This consideration argues for using a larger key size today than one might otherwise consider warranted. It also argues for replacing one's key with a longer key every few years, in order to take advantage of the extra security offered by hardware improvements. This point holds for other public-key systems as well.

Recently, the number of computers has increased dramatically. While the computers have become steadily more powerful, the increase in their power has not compared to their increase in number. Since some factoring algorithms can be done with multiple computers working together, the more computers devoted to a problem, the faster the problem can be solved. Unlike the hardware improvement factor, prevalence of computers does not make the RSA cryptosystem more secure

Better factoring algorithms have been more help to the attacker than have hardware improvements. As the RSA cryptosystem and cryptography in general have attracted much attention, so has the factoring problem, and many researchers have found new factoring methods or improved upon others. This has made factoring easier for numbers of any size, irrespective of the speed of the hardware. However, factoring is still a very difficult problem.

Increasing the key size can offset any decrease in security due to algorithm improvements. In fact, between general computer hardware improvements and special-purpose hardware improvements, increases in key size (maintaining a constant speed of RSA algorithm operations) have kept pace or exceeded increases in algorithm efficiency, resulting in no net loss of security. As long as hardware continues to improve at a faster rate than the rate at which the complexity of factoring algorithms decreases, the security of the RSA cryptosystem will increase, assuming users regularly increase their key sizes by appropriate amounts. The open question is how much faster factoring algorithms can get; there could be some intrinsic limit to factoring speed, but this limit remains unknown. However, if an "easy" solution to the factoring problem can be found, the associated increase in key sizes will render the RSA system impractical.

Factoring is widely believed to be a hard problem (see Question 2.3.1), but this has not yet been proven. Therefore, there remains a possibility that an easy factoring algorithm will be discovered. This development, which could seriously weaken the RSA cryptosystem, would be highly surprising and the possibility is considered remote by the researchers most active in factoring research

There is also the possibility someone will prove factoring is difficult. Such a development, while unexpected at the current state of theoretical factoring research, would guarantee the security of the RSA cryptosystem beyond a certain key size.

Even if no breakthroughs are discovered in factoring algorithms, both factoring and discrete logarithm problems (see Question 2.3.7) can be solved efficiently on a quantum computer (see Question 7.17) if one is ever developed.

Top of the page