Re: Why RSA?

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

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.

> 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.

purpose: to make routines implemented and implemented well within
the PGP program available to programmers.

future purpose: to make a general purpose library of routines
helpful in implementing various crypto systems and protocols.

plan:  Take the PGP source and rip it apart into tiny pieces
and put it back together in an organized way.  Change the
Makefile structure to build various libraries and isolate
the main user interface routines into a seperate group of
files.  Basically a restructuring of PGP that will provide
various intermediate libraries that may be used by other programers
for linking within their program.

*IF* this becomes part of the standard PGP distribution all
non-portable code will be rewritten for various platforms and
you will be able to find a lib for just about any platform
you are coding or porting to.

I havent read through the PGP code myself, but I suggest
at least libraries for the random number routines (including
the system-specific keyboard routines for getting random
seeds), a library for the RSA and IDEA routines, and a library
of the lower-than-RSA math routines.

After this is done then various projects such as a tcl shell
can be written on top of the libraries.

If the library is successful then various additions can be made
to it to make it a true crypto library rather than just a
PGP library.  This could also benefit PGP if it is changed
to allow various crypto systems.

The benefits of this approach are many:  When implementing
PGP front ends you usually dont want the normal PGP front
end at all, and would rather just re-write your own on
top of the PGP code.  When you are coding simple crypto
libraries (like 'link' and 'Circ') it is nice to have a
drop-in cryptosystem library.  The advantages to import-
export are nice as well, you can write code that has no
crypto code in it at all and let the users grab the crypto
library to compile.

> 
> derek
>

> plan:  Take the PGP source and rip it apart into tiny pieces
> and put it back together in an organized way.  Change the
> Makefile structure to build various libraries and isolate
> the main user interface routines into a seperate group of
> files.  Basically a restructuring of PGP that will provide
> various intermediate libraries that may be used by other programers
> for linking within their program.

If you plan to do this yourself, I can guarantee you, 100%, that
*NONE* of your work will go into the next release of PGP!

The work you suggest is underway.  Please be patient, for if you
did look at the PGP code, you would see what spaghetti it really
is!  If you remain patient, and wait for the next release, then
maybe things will be a lot better for you!)

---A concerned citizen who hates people who re-invent the wheel
or duplicate others' efforts!!!

-derek

> If you plan to do this yourself, I can guarantee you, 100%, that
> *NONE* of your work will go into the next release of PGP!
> 
> The work you suggest is underway.  Please be patient, for if you
> did look at the PGP code, you would see what spaghetti it really
> is!  If you remain patient, and wait for the next release, then
> maybe things will be a lot better for you!)

Well, this highlights an issue -- should a Toolkit be based
on PGP or RSAREF?  If the releasers of PGP are disinclined
toward the project, perhaps RSAREF would make more sense
(though I suppose that depends on how much cypherpunks hate
RSAREF).

> -derek

derek
(er, damn, the *other* derek)

> Well, this highlights an issue -- should a Toolkit be based
> on PGP or RSAREF?  If the releasers of PGP are disinclined
> toward the project, perhaps RSAREF would make more sense
> (though I suppose that depends on how much cypherpunks hate
> RSAREF).

No, you misunderstand.  The "releasers of PGP" are ***NOT***
disinclined towards the project.  They are implementing your
suggestions for the next release!!!!!  The next release will, short of
actually BUILDING the library, have a set of functions that a
programmer can use to access the crypto routines and let anyone, for
example, put a front end on the pgp system!!!

No, the PGP implementors are not ignoring you.  Rather, they are in
the process of doing just as you have asked, and have been doing so
for some months now.  If you start work with the current (2.3A) PGP
release, then you will just be re-implementing something that the PGP
developers have been working on for a long time!

As I said, be patient.  What you want is right around the corner, but
if you jump out too soon, you might get hit by that proverbial truck
which is right in front of it!!!!  It will come to you soon enough!!

> > -derek
> 
> derek
> (er, damn, the *other* derek)

-derek  Damn, this is confusing!!! ;-)

According to Timothy Newsham:
> 
> > 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.

I'd also like to help.  I'm pretty good with C.  And I'm finishing my BS in
Mathematics.  I'm no expert,(yet) but I'd love to learn.  BTW, I did get an
'A' in Numerical Computation. ;^)  Lagers,


J. Michael Diehl   ;^)  |*The 2nd Amendment is there in case the 
mdiehl@triton.unm.edu   | Government forgets about the 1st!  <RL>
Mike.Diehl@f29.n301.z1  |*God is a good Physicist, and an even 
    .fidonet.org        | better Mathematician.  <Me>
al945@cwns9.ins.cwru.edu|*I'm just looking for the opportunity to 
 (505) 299-2282 (voice) | be Politically Incorrect! <Me>
Can we impeach him yet? |*Protected by 18 USC 2511 and 18 USC 2703. 
PGP Key = 7C06F1 = A6 27 E1 1D 5F B2 F2 F1  12 E7 53 2D 85 A2 10 5D