derek@cs.wisc.edu (Derek Zahn) posted a conscientious summary of comments on the development of public key cryptographic techniques, a subject discussed with a particular urgency and irony lately. I'd like to comment on one paragraph:
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!
Public key cryptography is not just a `stunning' idea -- it is fundamentally revolutionary, because it solves `cryptography's catch-22'. This is a paragraph from a tentative version of the cryptography faq (not available yet): === 6.2. How does public-key cryptography solve cryptography's Catch-22? In a classic cryptosystem, if you want your friends to be able to send secret messages to you, you have to make sure nobody other than them sees the key K. In a public-key cryptosystem, you just publish X, and you don't have to worry about spies. Hence public key cryptography `solves' one of the most vexing problems of all prior cryptography: the necessity of establishing a secure channel for the exchange of the key. To establish a secure channel one uses cryptography, but private key cryptography requires a secure channel! In resolving the dilemma, public key cryptography has been considered by many to be a `revolutionary technology,' representing a breakthrough that makes routine communication encryption practical and potentially ubiquitous. === Public key cryptography also represents a throbbing, excruciating, perhaps even *deadly* black eye for the NSA. The subject is given a brief treatment in the final chapter of _Puzzle_Palace_ by Bamford, all that was evident in 1980 (very close to its inception), but at even that early time it was regarded as `stunning'. That chapter also notes how the NSA had viewed with increasing desperation the academic community's increasing interest in cryptographic research, and this manifested itself in an atmosphere of increased tension between researchers and the agency, such that the latter attempted to stifle the former at the patent office and the journal submission boxes in outrageous and insideous ways -- P. Karn had a delicious expression for this a long time ago on the list, something like `poking from the shadows'. In addition to this, handfuls of scattered cryptographic enterprises and budding entrepreneurs have been harassed as well. This always happens behind the facade of some other government agency. In fact, many victims battled for a long time before they even discoverd the NSA was behind their sorry, wretched plight or dismal failures. Maybe a term better connoting the NSA's true unique depravity in our free society would be `shadow molesting'. The NSA was fundamentally in fear of, and continues to be terrified by and repress, new discoveries that would render old cryptographic ciphers breakable or yield new unbreakable ones, either outside of its control. Nowhere else than in the NSA or cryptography itself are doctrines regarding `security in obscurity', and `information is power', more tenaciously held, or more prominent. Only in cryptography is the mere *knowledge* of an efficient factoring algorithm paramount and priceless -- in mathematics it would only be a curiosity. But beyond this, public key cryptography in general and the RSA algorithm in particular represent an *extraordinary* breakthrough in cryptographic research that apparently caught the NSA totally unaware and off guard. It may have been a very humbling experience for the agency, which has sought the `cream of the crop' in engineers, technicians, mathematicians and theorists, spending tens of billions of dollars a year for decades to cultivate its own secret research, to find that it had been outdone in a few years of intense and focused outside research (I have the opinion that the NSA did *not* discover it secretly, others may differ--it would be interesting to analyze their reaction to try to determine that aspect in particular). Public key cryptography is a `stunning' testament to the power and tradition of open dialog in scientific research, and the fundamentally lackluster performance of any government agency, no matter how well funded or tightly coordinated, in comparison to the combined, vast, disconnected, worldwide talent and ingenuity that feeds voraciously off open scientific journals. Public key cryptography stands in bold, victorious defiance of NSA suppression. The final point to make is that RSA and public key systems have led to an amazing cornucopia of scientific results and spurred other critical mathematical theories. In particular the field of *complexity theory* has been to a large part driven directly by questions associated with public key cryptography. The unsolved perplexities in cryptographic research seem to cut to the core of the frontiers of interesting mathematical and computational ideas, such as factoring, that the world's foremost minds have grappled with for millenia -- Gauss, Fermat, Euler, et. al. (with new modern heroes). Cryptographic algorithms embodied in RSA in particular represent one of the most beautiful examples of the interplay between theoretical and practical science. What other program in the world simultaneously utilizes Fermat's Little Theorem to test for primes and guarantees privacy to multitudes in daily email? By the way, D. Zahn's `Simmons' reference above may be to the following (if he pointed out what it was, I missed it): [SIM91] G. Simmons (ed.), Contemporary Cryptology: the Science of Information Integrity. IEEE press, 1991. I'd also be interested in hearing of any other accounts that match my own passion for the subject :) Also, if others have any educated opinion, evidence, or theories of whether public key crypto was *undiscovered* by the NSA prior to the publication of Diffie and Hellman and RSA, I'd read them with great fascination. Note that this is *not* quite the same as `attempts to bar its publication' although those are always eye opening as well. p.s. feel free to redistribute this anywhere, but email me where you sent it.