on the `R' in `RSA'

["L. Detweiler" <ld231782@longs.lance.colostate.edu>]

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.