greg@ideath.goldenbear.com (Greg Broiles) writes:

If Alice wants proof that Bob can factor large numbers, Alice should generate many of them - say, 1,000,000 of them. She sends them to Bob and says "Hey, factor one and send me the results as soon as you're done." The chances are 1 in 1,000,000 that Bob is giving away a useful service for free

Bob is now doing at least twice as much work as before. He is factoring a random key and a real one for each customer he does business with. Since the existance of a breakthrough in factorization is certainly of interest to people who do not want keys factored, Bob will get lots of requests from the curious, who have no interest in buying his services. Should he prove to someone in the academic community that he can indeed factor keys, people would simply stop using RSA and Bob's economic future would be bleak indeed. Bob needs to charge a lot for his services, and not give free demos. The protocol needs to require that the customers commit to the fee before Bob demonstrates his talent. This will discourage enquiries by the frivilous.

What they both need are trusted friends, attorneys, or agents - Bob puts an ad in the newspaper, saying "I can factor big numbers. Contact me through my attorney - her name is [...]."

Gaaak! All these people. You are making Bob paranoid. Bob is definitely not going to put an ad in the paper. His customers are foreign and domestic law enforcement and intelligence services and corporate security folks. Bob wants to keep an extremely low profile with the Great Unwashed. Isn't there some way for Bob to conduct business using the remailer at Hacktic and anonymous DigiCash(TM)? Bob does not wish to find himself at the bottom of a large body of water wearing concrete galoshes. Bob wishes to factor a few numbers, transfer the money offshore, and retire without the general public being aware that RSA has been compromised.

I don't have a damn thing to do with either law enforcement or the intelligence community, but I bet that folks would be willing, upon occasion, to pay between $100K and $1M for factorizations of other folks' RSA private keys. The trend towards civil forfeiture of "drug money" will probably lead to higher prices for key factoring - folks who could factor big numbers might even be able to negotiate for "points" of the gross take, rather like big-name actors/directors or sports figures.

I agree. I think that $100 a bit would be an extremely reasonable price for factoring a 1024 bit modulus. -- Mike Duvos $ PGP 2.6 Public Key available $ mpd@netcom.com $ via Finger. $