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.

Wikipedia states that RSA challenge has been withdrawn.

Does it mean that an efficient factoring algorithm is "just around the corner"?

or are there some other reasons?

If the challenge was still open people would have even more confidence in RSA.

share|improve this question
1  
Perhaps RSA needed to invest that money into their new SecurID technology! :) –  Fixee Oct 12 '11 at 5:59
add comment

1 Answer 1

up vote 8 down vote accepted

RSA themselves (the company) say this in their RSA Factoring Challenge FAQ:

Why is the RSA Factoring Challenge no longer active?

Various cryptographic challenges — including the RSA Factoring Challenge — served in the early days of commercial cryptography to measure the state of progress in practical cryptanalysis and reward researchers for the new knowledge they have brought to the community. Now that the industry has a considerably more advanced understanding of the cryptanalytic strength of common symmetric-key and public-key algorithms, these challenges are no longer active. The records, however, are presented here for reference by interested cryptographers.

This, of course, does not really answer the question. Although there have been many optimizations, and computers have quite grown in both CPU power and RAM size, the best known algorithms for factorization have not qualitatively changed since the late 1980s, when the General Number Field Sieve was discovered. Even with GNFS, today's computers, and the fine brains of the authors of the RSA-768 factorization, a 1024-bit RSA modulus still seems out of reach. The money at stake was sizeable for an individual, but not that much for a company such as RSA (there was a 100k\$ prize on RSA-1024, 150k\$ for RSA-1536 and 200k\$ for RSA-2048; RSA Security appears to have a yearly revenue of more than 700 millions of dollars).

My guess is that they withdrew the challenges for a mixture of the two following reasons:

  • When a RSA challenge is broken, it makes bad press, and the press is worse if there is a prize, because it may serve as an highlight on the event (which is otherwise extremely technical).

  • An open challenge with a prize implies some kind of provisioning, which is bound to upset someone in the accounting department.

So, at some point, RSA Security decided that the inconvenience of maintaining the challenges exceeded the inconvenience of withdrawing (which your question incarnates: a suspicion of potential weaknesses).

One might notice that the withdrawal happened at about the same time than the bulk of the sieving work for RSA-768 began -- I do not have the exact timing, but it is conceivable that the withdrawal decision had been pending for awhile, and was triggered by rumours of the RSA-768 factorization effort.

share|improve this answer
    
What about research on custom cryptanalysis hardware such as TWIRL en.wikipedia.org/wiki/TWIRL –  Ethan Heilman Oct 12 '11 at 13:37
1  
@Ethan: it is interesting research, but TWIRL, like its predecessor TWINKLE, optimizes only the sieving -- that's the "easy" half of GNFS. The sieving for a 1024-bit integer can already be done with generic PC (with some RAM boost, e.g. 64 GB of RAM per PC -- expensive, but still off-the-shelf hardware). The second half of GNFS (the linear algebra step) turns out to be the bottleneck for large integers; and, right now, nobody knows how to actually run it for real, for a 1024-bit integer factorization. –  Thomas Pornin Oct 12 '11 at 13:59
    
According the wikipedia page: "[TWIRL'S designers] estimate that if TWIRL were built, it would be able to factor 1024-bit numbers in one year at the cost of 'a few dozen million US dollars'". Is this statement incorrect? Has something new been learned? –  Ethan Heilman Oct 12 '11 at 14:41
1  
@Ethan: that statement is based upon other work on custom circuits (FPGA, ASIC) specialized in the problem of doing the linear algebra step; the designers of TWIRL concentrate on the sieving. Whether the custom circuits work at all remains to be seen; contrary to the sieving, that part implies moving around a lot of data, a notoriously hard problem that cluster builders routinely face. I spoke with some experts on the subject (e.g. Bob Silvermann) and their general mood is cautious skepticism. –  Thomas Pornin Oct 12 '11 at 16:07
    
Thanks Thomas! Someone should turn this into a question. –  Ethan Heilman Oct 12 '11 at 18:49
add comment

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.