From: smb@research.att.com
Date: Fri, 24 Sep 93 08:28:37 PDT
To: derek@cs.wisc.edu (Derek Zahn)
Subject: Re: Why RSA?
Message-ID: <9309241524.AA24281@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


Let me try to answer some of these questions by giving a broad overview
of patent law.  I'm not a lawyer, but I've spent a lot of time talking
to lawyers about patents during the last several years, and about what
they are and aren't.

First of all, a patent is (theoretically) a contract between an inventor
and society.  In return for the inventor teaching everyone about the
new idea, he or she gets a monopoly on use of that idea for a limited
period (normally 17 years in the U.S.).

Patents cover the right to build, make, import, or even *use* the
protected idea.

A patent is *not* a license to do something.  Rather, it is the right
to prevent others from doing it.  Thus, if I invented the pencil, and
you invented the eraser, neither of us could make a pencil+eraser without
permission from the other.

Patent infringement is not a crime; you cannot go to jail for it.  It is
a civil offense, and the patent holder has to sue you for infringing.

You can get a patent for things that are new, useful, and non-obvious.
All three criteria must be satisfied.  Note specifically that a new
use for an old idea is patentable.  R, S, and A did not patent particular
equations; rather, they patented certain specific uses for those
equations.  If you can find a new use for them, you're home free.
(I and a colleague almost did that.  We came up with a new application
for them, and we felt that the security of our scheme would be
strengthened tremendously by the work that's gone into RSA.  However,
our application was just different enough that I managed to crack
it.  Sigh.  But better that I cracked it before publishing...)

For our purposes, a patent consists of two major parts.  The first is
more or less a technical paper; this is what you're supposed to learn
from.  Some of the language is rather stylized, but for the most part
it will be comprehensible to someone who understands the field.
The second part is the ``claims''; these are written in very dense
legalese, and are supposed to delimit exactly what's new.  You infringe
a patent if your activity includes all of the elements of any one
claim.  Writing good claims is at the heart of a patent attorney's
skills.  You want to claim as much as you possibly can, even if you
think some of it is worthless -- but you have to make sure that what
you claim doesn't include prior art.  In the RSA patent, for example,
almost every claim speaks of both encryption and decryption.  The
idea of mine that I alluded to involved encryption only; thus, it
did not fall within the scope of all but one of the RSA claims.  For
various other reasons, it didn't fall within the scope of the other
one.

	 > All are patented in so far as one of the patents covers ALL public k
	ey
	 > schemes. Some, like Rabin's scheme, have possible technical advantag
	es
	 > 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).

Well, Rabin's scheme has other problems as well, including the lack of
an unambiguous decryption algorithm.  You get a few answers, one of which
will be correct.

Under patent law, though, the ``superior'' technology hasn't been suppressed.
Rather, Rabin would need a license from RSA (and Diffie-Hellman) to
practice his invention.  And he couldn't have come up with his idea
unless RSA had been published.

	 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?

As I explained above, a patent does not infringe per se.  However,
practicing RSA would indeed require a license from Stanford.  But
both Stanford and MIT assigned exclusive licensing rights to those
patents to Public Key Partners, a deal which arguably violates the
antitrust laws.  (Down, libertarians, down.  I know you don't believe
in such things...)

Anyway, patent 4200770 claims virtually all mechanisms for public key
distribution or exchange systems.  Exponential key exchange is the
particular example given; it's claimed, too.  Patent 4218582 claims
all of public-key cryptography.  The knapsack system was the particular
system given; it was claimed, as well.

I should note here -- to patent something, while you don't (as a rule)
have to build it, you do have to show that it's buildable.  If there's
any doubt, the patent examiner can order you to produce one.  This is
used to deal with perpetual motion machines and the like.  The concept
of public key cryptography couldn't have been patented without a
working example.  And, while knapsack systems were subsequently cracked,
at the time the patent was issued there were no (publicly) known attacks.

	 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?

Have a look at "The first ten years of public key cryptography", Diffie, W.,
Proceedings of the IEEE 76:5, 1988, pp 560-577.

	 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!

There was some question of prior art published more than one year before
the patent was filed.  See "Multi-user cryptographic techniques",
Diffie and Hellman, AFIPS Proceedings 45, pp109-112, June 8, 1976.
The patent apparently contains some language explaing why that doesn't
count, and in particular because there was no demonstration that it was
even possible to build such a thing as a public key cryptosystem.