Re: RSA200 prime cracked

From: Paul Leyland (paul_at_leyland.vispa.com)
Date: 05/14/05


Date: 14 May 2005 19:39:31 +0100


"Matt" <MattCrypto@gmail.com> writes:

> Tom St Denis wrote:
> > Matt wrote:
> > > Thanks for the clarifications. One thing has been puzzling me: why
> > > factor RSA-200 (with 663 bits) for no prize when the somewhat
> smaller
> > > RSA-640 (640 bits) carries a US$20,000 bounty?
> >
> > Simple. <snip>
> > So they removed the previous challenge to avoid having to pay twice.
>
> I think you misunderstood my question: I was asking why Bahr, Böhm,
> Franke and Kleinjung chose to factor RSA-200 rather than RSA-640 (since
> the latter carries a prize and the former does not).
>
> Incidentally, does anyone know whether the original RSA challenge had
> prizes? Or were they just introduced with the new RSA challenge
> numbers?

I've been factoring RSA challenge numbers for well over ten years now.
They fell into three classes and a unique example.

The unique example was RSA-129. The challenge was posted in August
1977 edition of Scientific American. The USD 100 prize was paid by
Messrs R, S and A themselves. We donated the money to the Free
Software Foundation.

The first challenges issued by RSA Inc were of "hard" integers ranging
from RSA-100 in steps of 10 digits up to RSA-500 or so. Arjen Lenstra
and Mark Manasse factored the first two (RSA-100 and RSA110) and I
joined in around RSA-120 or RSA-130. I genuinely forget which, though
I definitely played a role in RSA-140 because I have a copy of the
check paid out to us.

The second set of challenges, running at the same time as the first,
were of partition numbers. They started at p(19997), I believe, and
continued with p(x) for prime values of x essentially without limit.
I got quite a bunch of those before losing interest, picking up a few
hundred dollars in the process.

The first two sets were eventually retired and replaced by the current
series which have a "significant" (whatever that means) number of bits
in them. So far RSA-512 and RSA-576 have been factored; I helped with
both.

In every single case, dealing with the prize money has been more
trouble than it's worth. Splitting it between numerous contributors,
all of whom made different contributions (sin quality and quantity);
dealing with foreign currency conversion; dealing with taxation
regimes; dealing with corporate and university poilicies --- all are
far too much hassle for the relatively limited reward, and a few
kilobucks is relatively limited once it has been split a few hundred
ways.

Paul

-- 
Hanging on in quiet desperation is the English way.
The time is gone, the song is over.
Thought I'd something more to say.


Relevant Pages

  • Re: Searchindexer -- for whose benefit?
    ... RSA was secure. ... factoring method, and the prize money didn't act as a motivation ... the prize. ... As an RSA employee, wouldn't you have been ineligible for the prize? ...
    (rec.arts.sf.fandom)
  • Re: Searchindexer -- for whose benefit?
    ... factoring method, and the prize money didn't act as a motivation ... the prize. ... As an RSA employee, wouldn't you have been ineligible for the prize? ... Would it have been possible to claim *all* the prizes by factoring all ...
    (rec.arts.sf.fandom)
  • RSA Factoring Challenge - legitimate?
    ... Several people mentioned the "RSA Factoring Challenge" numbers over the ... Would they actually pay the prize ...
    (sci.crypt)
  • Re: JSH: On integer factorization
    ... i am a victom of RSA too... ... using my factoring tricks i factored one of their numbers ... yet did not get a prize ... ... Please give exact details on: ...
    (sci.math)
  • Re: RSA Challenge Question
    ... would happen if someone came up with a polynomial time algorithm for ... RSA is not used for encryption. ... *them* (Sally Jane) submit the results, wherein Chappy calls John Doe, ... prize retrieval process is. ...
    (sci.crypt)