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.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Perhaps RSA needed to invest that money into their new SecurID technology! :) $\endgroup$– FixeeOct 12, 2011 at 5:59
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
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.
answered Oct 11, 2011 at 18:50
-
$\begingroup$ What about research on custom cryptanalysis hardware such as TWIRL en.wikipedia.org/wiki/TWIRL $\endgroup$ Oct 12, 2011 at 13:37
-
3$\begingroup$ @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. $\endgroup$ Oct 12, 2011 at 13:59
-
$\begingroup$ 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? $\endgroup$ Oct 12, 2011 at 14:41
-
3$\begingroup$ @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. $\endgroup$ Oct 12, 2011 at 16:07
-
$\begingroup$ Thanks Thomas! Someone should turn this into a question. $\endgroup$ Oct 12, 2011 at 18:49
$\begingroup$
$\endgroup$
1
Initially the prizes would have been useful to prove the safety of their system. However they have driven a lot of academic effort and in effect the prizes were deemed at some stage to be counter productive I assume. This would especially have been the case if someone has made a quantum computer and factored all of the challenges in at once: dramatically bad publicity.
-
1$\begingroup$ First: you can't assume someone would easily build a quantum computer. Second: one of the reason is the increasing power of the computers made the challenge not worth it anymore. $\endgroup$– BivJul 25, 2016 at 14:53