From: Adam Back <aba@dcs.ex.ac.uk>
Date: Mon, 19 Jan 1998 07:49:52 +0800
To: cypherpunks@cyberpass.net
Subject: proving that one knows how to break RSA
In-Reply-To: <gaTiJe29w165w@bwalk.dm.com>
Message-ID: <199801182343.XAA00268@server.eternity.org>
MIME-Version: 1.0
Content-Type: text/plain




Dimitri Vulis <dlv@bwalk.dm.com> writes:
> Bill Payne was with Sandia national lab (where they quite a bit of
> crypto work) Bill claims to have discovered a very fast
> factorization algorithm using shift registers, which he refuses to
> publish. While I haven't seen the algorithm, I believe he may well
> be right.

Bill Payne's claim to having discovered a faster factorization
algorithm than the current state of the art, allows us to invoke the
oft discussed mechanisms for the author to prove this ability without
divulging the algorithm, and then proceed to sell the algorithm to the
highest bidder, whilst minimizing his chances of being killed.

I am sure many here remember various past discussions which were based
on the "what if" question: one has discovered a fast factorization
algorithm and our aims as discoverer are to:

- maximise price for selling algorithm
- minimise chance of being killed by the NSA to silence one
- proving that we posses a fast algorithm 

Minimising our chances of being killed would seem to rely on:

- posting our sale via BlackNet (ie posting anonymously)
- having a disclosure mechanism in place which will be invoked on the
  eventuality of our premature death in an unfortunate `accident'

Bill Payne seems to have already blown the first option in disclosing
his identity.  His dilemma is now that if the highest bidder is the
NSA, they may kill him afterwards to prevent a release of the
algorithm.  This is where a robust disclosure mechanism in event of
premature death would be useful.  I hope Bill has invested in such a
plan.

Maximise price for selling algorithm: hold out for the highest bidder.
Or perhaps sell to multiple parties with NDAs (would NDAs be
sufficient to protect such valuable information?)

Are there any reasons why Bill should be refusing to divulge the
algorithm?  Perhaps he is waiting for a higher bid.  What is the
current highest bid?  What about alternate motives?  Perhaps he is not
interested in money, but rather in proving NSA incompetence?

Or if Bill doesn't in fact have an algorithm, what would be the
motives for falsely claiming that he does?  Is he working for the NSA
to spread FUD?

Lastly proving that Bill has a fast algorithm (or acess to some nice
hardware at NSA).  Several RSA public key challenges are posted and
Bill posts the factorization of the public key.  There are
conveniently pre-published RSA challenges in the form of rsa.com's RSA
factoring challenge with multiples of two primes ranging in sizes
going up in steps of 10 in decimal digits.

It would I think provide best assurance if challenges of both sorts
were broken, in that the RSA challenges have been available for some
time, and Bill could have been working on RSA 140 for the last 3 years
or whatever.

So, Bill what size challenge in bits would you like to break first?
I'll post one of your desired bit size.

Adam
-- 
Now officially an EAR violation...
Have *you* exported RSA today? --> http://www.dcs.ex.ac.uk/~aba/rsa/

print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`