How does Bob make Alice aware that he can factor RSA keys and make sure that he and Alice can do business without either one of them getting ripped off or the NSA catching him.
Sounds like a job for Blacknet, or similar anonymous-broadcast systems. He can't easily hide the fact that *somebody* is in the business from the NSA, since he can't easily tell that Alice doesn't work for the NSA and isn't planning to publish his business's existence to the net. But if he and Alice are both remailer-users able to post to the Blacknet broadcast (using whatever mechanism, like alt.waste), Bob can post a note to Alice saying he is able to crack RSA keys for money, and Alice can post replies saying she doesn't believe him and here's a message to crack. There are cut-and-choose protocols described in Schneier that can handle (awkwardly) the mechanics of getting Bob to recode and return the message, and Alice to hand over the digicash, without either of them feeling too ripped off, assuming there's a digicash system in place that gives sufficient anonymity. Bob has a bit of an advantage in convincing Alice, since he can probably read her encrypted posts to the net - he can start teh conversation by posting to her on Blacknet with some keywords from messages she's posted to other people. That doesn't directly tell her that he's cracking RSA rather than IDEA/3DES, but he could also include a note that the first n bits of her private key are ....... Alternatively, he can go on a political rant about Too Many Secrets, but having seen that movie he can announce the details of his decryptor on sci.crypt *before* announcing that he's giving a lecture at Stanford... :-) Somebody, in the discussion about pricing, said that some of the proposed protocols would take too much CPU time, cracking lots of keys just to demonstrate that he can do it, and that he should always charge money to avoid overloading his 486 box. If he's going to go into the business of factoring RSA keys for money, he'll probably make enough to afford a few *new* computers once he hits up a couple of wealthy customers, if he's not spending it all on air travel and bodyguards. "Bob"