Discussion Forums

Information Security   < Previous   Next >

Possible Factoring Breakthrough
Ryan Pierce / Townsend Analytics Ltd. / Archipelago LLC
26 Feb 2002 5:21PM ET

A paper has been released that documents a proposed algorithm that can, allegedly, cause a dramatic speedup in factoring large numbers in parallel computers.

The difficulty of factoring large numbers is the basis behind the security of the RSA algorithm, which is the basis of most PKI.

The theoretical gain is the ability to factor a number with 3 times as many bits for the same cost. However, whether this can be achieved is yet unknown. The author of the paper is seeking a research grant to determine whether his approach is practical.

While I don't think this is a cause to panic, it is a good wakeup call. Computers are getting faster. And math (might) be getting better. Attacks that would have been prohibitively expensive years ago are becoming more feasible. DES can be broken in days for less than the cost of the average house in Chicago. When given a choice, it may be worth considering lengthening one's RSA keys.

The paper is available at:

http://cr.yp.to/papers/nfscircuit.ps

Someone has translated it into PDF here:

http://home.columbus.rr.com/aphoward/nfscircuit.pdf