First, my sincere gratitude for the replies to my queries regarding public key cryptography patents. To pay back such generosity, I will summarize. Also, I have done a little more digging and will present my findings, even though those findings include more questions! My original question was why cypherpunks don't just pick some non-RSA public key algorithm to achieve widespread distribution of cryptographic tools. My contention is that for such widespread distribution to occur, the price must be small in comparison to the average user's electronic communication outlay, and the tools must be beyond reproach legally so that it can be distributed by commercial email tool providers in a form that is elegantly integrated into the user's environment. My mother will not fetch, install, and configure PGP, though she might pay $10 - $20 more for an email product with "privacy enhancements". My reading of the comp.patents FAQ leads me to understand that any use of PGP by an individual in the U.S. is in violation of U.S. law (though the chances of being prosecuted are vanishingly small). Cypherpunks probably don't care too much about that, but the masses waiting for conversion probably do. The reasons for the desirability of widespread public key tools are obvious, even without considering the collapse of governments. For example, digital signatures can be used to authenticate electronically-distributed software upgrades, and so on (but this is all old hat to the folks on this list!). Unfortunately, as Perry Metzger pointed out:

All are patented in so far as one of the patents covers ALL public key schemes. Some, like Rabin's scheme, have possible technical advantages over RSA.

First, a note: "Rabin's scheme" is (as Perry said) the one provably linked to factoring (a major advance!) and I assume it's the one implemented in RPEM. According to the RIPEM FAQ, PKP squashed that development by claiming that their patents were broad enough to cover Rabin's scheme, and the effort was abandoned "for pragmatic reasons" (another example of how superior technology can be suppressed by monopolies). Now, I've looked a little further into the patent issue, and I remain kind of confused. I went to the library and read the four patents in question (but only made a hardcopy of the first chronologically). I found the documents difficult to understand (for legal rather than crypto-tech reasons). All four applications were made in 1977-1978, and the patents were granted variously from 1980-1984. The earliest one has Hellman, Diffie, and Merkle as inventors; the second just Hellman and Merkle. Both are assigned to Stanford University. It seems to me that one of these is the one that covers, broadly, public key cryptography -- presumably the earliest one (4,200,770), since it has all three major players as inventors and the language of the eight claims seems to be rather broad (though only the second patent, 4,218,582, has the phrase "public key" in its title). Patent 4,405,829, granted in 1983, is for the RSA algorithm [footnote: the RSA patent apparently celebrated its tenth birthday two days ago; was there a party?]. There is no overlap between this patent's inventors and assignees and the earlier more general patent. Here's a question for somebody in the know: if the earlier patents cover all public key cryptography and RSA is a public key system, isn't it in violation of the earlier broader patent? Does PKP pay license fees to Stanford, or were they granted exclusive rights by Stanford as well as MIT? Similarly, apparently a public-key scheme called Warlock has been granted patent protection. How is this possible if somebody else holds patents covering all of public key encryption? If I understand patents correctly (hah!) they last for 17 years from the time they are granted. This means that the earliest public key patent will expire in about 3.5 years. After that presumably there will be no restrictions on new public key systems. The RSA patent would expire in 2000. If somebody could clarify which patent is the "broad" public key patent, I'd appreciate it (even with them right in front of me, I can't tell)! My guess is that it would have to be either 4,200,770 or 4,218,582 -- if it's the latter, how did Merkle get squeezed out of inventorship? Respondents to my initial questions pointed out that the patents may be over-broad and could be challenged on those grounds; given the history of how public key crypto was invented, it seems to me that it would be difficult to contend that the idea is obvious (Simmons says that the idea "stunned" the crypto community) -- but I'm no lawyer, and I'll leave that issue to those with more skill, brains, and money than me! For now, then, my conclusion is that for four more years at least, licensing RSA from PKP is probably the only viable commercial option for companies who wish to give their users public key crypto capabilities. It seems that the designers of Internet Privacy Enhanced Mail (PEM) agreed with this assessment, as they took the unusual step of including proprietary RSA in their standard. For their part, in RFC 1170, PKP states: "We assure the interested parties that Public Key Partners will comply with all of the policies of ANSI and the IEEE concerning the availability of licenses to practice this art. Specifically, in support of any RSA signature standard which may be adopted, Public Key Partners hereby gives its assurance that licenses to practice RSA signatures will be available under reasonable terms and conditions on a non-discriminatory basis." That sounds good -- but is troublingly vague. I have stated earlier what *I* think is are "reasonable terms" for the inclusion of a minor feature like PEM-compliance in an email processing system, but I don't get to decide that. If anybody knows more specifically how the standards bodies interpreted "reasonable", please let me know. As I am contemplating developing a PEM-compliant product, I will be writing to PKP to discuss licensing arrangements, but information from others (best: expressed publicly) would be helpful. If RSA is the only game in town, let's at least be clear about the price of admission. There seems to be a chance that manufacturing PGP-aware products (but not distributing PGP itself) could slide by, but it could also be interpreted as "inducement to infringe" which would apparently be actionable. The second point in my earlier message, largely obsoleted by the answer to the first, involved the development of new public key systems. Given that selling or otherwise using or distributing a new system now would invite litigation, the question is rather moot, but I'd like to thank L. Detweiler and P. Metzger for their comments on the all-important issue of trusting new algorithms. Finally, I suppose that it's always possible to come up with some radically new encryption technique that could be used to support authentication and yet have nothing to do with public key crypto... but I'm not holding my breath. Regarding the recent proposals for the construction of a toolkit, I'm all in favor and would personally welcome the opportunity to contribute to such an effort as a hands-on supplement to my crypto education. I have extensive experience with C and C++, and am VERY familiar with TCL (pronounced 'tickle', for those not in the know). A good start would be a clear statement of purpose. If this "Why RSA" thread has been too basic and has caused frustration for that reason, please forgive me. I have learned a great deal, and I hope that somebody somewhere else has profited as well. derek