Re: Rivest Patent

[Vin McLellan <vin@shore.net>]

	Vin McLellan <vin@shore.net> wrote:

>> Now, it seems to me reasonable, albiet academic, to argue whether or not
>>software
>> should be patentable.  It is also certainly reasonable to argue whether
>>or not
>> cryptographic algorithms should be patentable.
>>
>> On the other hand, it seems to me unreasonable, willfully ill-informed,
>> and/or  malovelent to declare -- in the face of several judicial rulings
>> which have firmly ratified the RSA PKC patent -- that  "prior art" exists
>> which should have invalidated that patent.

	Eric Michael Cordian <emc@wire.insync.net> -- the "Nym" or
pseudonym for someone who says he is a group of people, and who has been
collecting  $500 donations from folks willing to help the Cordian Group
sponsor an algebraic attack on the DES (See the "DES Analytic Crack
Project" at http://www.cyberspace.org/~enoch/crakfaq.html) -- spun off an
individual voice to respond:

>Judicial rulings notwithstanding, a description of that which is now known
>as RSA Public Key Cryptography was published in a book of algorithms which
>pre-dated by quite a few years its patenting and commercial promotion by
>the current patent holders.

	When I read Cordian's claim, I asked Ron Rivest if he had ever
heard of such a thing.  Prof. Rivest was curious, but said was all news to
him. To the best of his knowledge, he said, there had never been anything
like a description of the RSA public key cryptosystem published prior to
the paper he, Adi Shamir and Len Adelman, published in April, 1977: "On
Digital Signatures and Public Key Cryptosystems."

	Last year, former Cylink attorney Pat Flinn suggested that one
possible  challenge to the RSA patent might be to highlight the similarity
between the RSA PKC and the Pohlig-Hellman crypto system, invented at
Stanford University in 1975. For an invention to be patentable, of course,
it must be useful, novel, and non-obvious. Flinn argued that the
reformulation of the Pohlig-Hellman algorithm with a modulus that was the
product of two prime numbers was a potentially "obvious" enhancement.

	But not even Pat Flinn claimed to know anything about a
"description of that which is now known as RSA Public Key Cryptography"
being published somewhere -- anywhere -- years before the RSA cryptosystem
was invented and named at MIT.

	As Matt Blaze pointed out, there have also been recent reports
about secret research into public-key cryptosystems by cryptographers
within the British cryptographic service, GCHQ, in the early 1970s.
According to former NSA Director Bobby Ray Inman, the NSA was working on
PKC even earlier. Until last December, when the Brits released a GCHQ
historical paper written by John Ellis in 1987, there had been little or no
unclassified information available about this pioneering research. See:
http://www.nytimes.com/library/cyber/week/122497encrypt.html   We still
don't know what was done at the NSA, by whom, and when. Secret government
R&D, however, is not really relevant to intellectual property claims on
public key crypto. Full publication of the details of an invention -- in
exchange for a limited-duration property right -- is really at the heart of
the patent process.  Except in extraordinary circumstances, the NSA doesn't
play in this league.

	In the commecial world, on the other hand, it's hard to think of
priceless information being kept secret (particularly when it is only worth
something if it is on a bargaining table.) In the lawsuits between
Stanford/Cylink and RSA Data Security over the scope and validity of the
Stanford and RSA patents, "obvious prior art" -- certainly evidence that
the RSA cryptosystem had been published by someone other than the MIT
inventors before 1977 -- would have been worth tens of millions of dollars.
It might have been potentially worth that much to Pat Flinn himself.

	Since I knew that no mention of such a document or book had ever
emerged in Cylink's multi-year campaign to invalidate the RSA patent, it
seemed a safe bet to challenge Mr. Cordian directly.

	"There was no such book. Cordian's statement is just not true," I
declared.

	Mr. Cordian replied with dry scorn:

>>> Only a complete moron would place himself in the position of trying to
>>> prove such an all-encompassing negative.

	(Not light of hand, our Mr. Cordian.  Yet not all negative
propositions are impossible to prove.  For the rest, I'll leave it to the
List and other readers to decide which of us deserves a Dunce Cap for
placing himself in an untenable position.)

	Mr. Cordian didn't press his initial argument that a cryptographic
algorithm, even if embodied in a pseudo-mechanical device or process,
doesn't deserve patent protection. Since 1981, the US Courts have allowed a
process which includes a mathematical algorithm to be patented  -- if the
algorithm is merely part of an otherwise patentable process. For the RSA
cryptosystem, this seems reasonably straightforward to those without a
religious bias.

	To quote the Federal Court in the Schlafly Case, affirmed by the
Circuit Court:

"Taken as a whole, the RSA patent is entitled to patent protection. The
claims of the patent make use of known structures, a communications
channel, an encoding device and a decoding device, to produce a practical
invention, i.e. a means for securely transmitting messages across an
insecure line. The messages are comprised of word signals that are
transformed from one state, plaintext, to another state, ciphertext, by the
patented invention. The word signals are then transmitted across an
insecure line and transformed by the decoding device from ciphertext into
plaintext. As such, the claimed invention is not merely a disembodied
mathematical concept but rather a specific machine designed to transform
and transmit word signals."

	(I was never impressed by the absolutist argument against patents
on math-based processes. Mr. Cordian summarized this POV: "The fact that
the [RSA] patent couldn't be successfully challenged even though its
mathematical underpinnings were well known years prior reflects badly only
upon the notion of mathematical patents, and hardly refutes the facts in
evidence." By that logic, it seems to me, a basic knowledge of physics
could invalidate almost all patents for mechanical inventions.)

	The second traditional attack upon the RSA public key cryptosystem,
noted above, is the charge that it was "obvious" or insufficiently novel.
Section 103 of the US Patent Act provides that a patent is invalid "if the
differences between the subject matter sought to be patented and the prior
art are such that the subject matter as a whole would have been obvious at
the time the invention was made to a person having ordinary skill in the
art...."

	If, as Mr. Cordian claimed, there was "a description of that which
is now known as RSA Public Key Cryptography" published in some book years
before the 1976 (re)discovery of the RSA cryptosystem by Rivest, Shamir,
and Adleman, it would have -- and clearly should have -- invalidated the
RSA patent under that rule.

	So what do we get when Mr. Cordian finally chooses to reveal to a
curious List the source of his amazing report that the RSA public key
cryptosystem was actually published in the _19th_ Century?

	Patrick J. Flinn!  Hey, what a surprise!

	As his hallowed source, Mr. Cordian cites a footnote from Flinn's
impassioned 1997 denunciation of the RSA patent in the Cyberlaw journal.

	Read one-time Cylink attorney Flinn at
http://www.cyberlaw.com/rsa.html (and a brisk bare-knuckle retort from Bob
Haslam, RSADSI's attorney, at http://www.cyberlaw.com/rthrsa.html.)

	Flinn led the team of patent and litigation lawyers that
represented Cylink Corporation in its suit against RSA Data Security Inc.
to determine the validity and scope of the RSA PKC patent after the breakup
of an early RSA/Cylink licensing partnership. In a separate case, Flinn's
team also represented Cylink and Stanford University against RSADSI in a
suit which sought to define the validity and scope of the so-called
Stanford patents: the Hellman-Merkle Patent and the Diffie-Hellman Patent.

	Critics of Flinn's Cyberlaw article characterized him as a one-time
Cylink gunslinger who had already failed in several attempts to invalidate
the RSA patent -- and who was finally bounced from the case in 1996 when
Cylink decided that further litigation was futile and potentially
disasterous. Cylink subsequently negotiated the purchase of a license for
the RSA public key cryptosystem from RSADSI.

	RSA's attorneys, as you might expect, rudely dismissed Flinn's
list of potential vulnerabilities in the RSA patent in Cyberlaw. They
pointed out that Flinn's arguments were being published, rather than heard
in a courtroom, because those same arguments had failed to impress several
judges and hearing officers.  "As a matter of fact," declared RSA attorney
Bob Haslam, "none of Mr. Flinn's three arguments about the supposed
invalidity of the RSA Patent have ever been remotely successful in actual
litigation."

	To its credit, Flinn's Cyberlaw article doesn't really try to be
anything but a determined advocate's last-ditch list of legal attacks that
might -- with a good tailwind behind them -- potentially chip, limit, or
even invalidate RSA's teflon-coated PKC patent.  Flinn's Cyberlaw
presentation drew notably unsympathetic responses from the law profs and IP
experts on the Cyberia mailing list -- although they seemed to admire his
style and gall in publishing a case he wasn't going to be allowed try
before a judge or jury.

	For all that, the pretentions of Flinn's Cyberlaw footnote on 19th
Century Mathematics turned out to be _far, far_ less than what Mr. Cordian
had claimed.

	Mr. Cordian must have discovered this when he went back and pulled
up his source data. Then -- to put it diplomatically -- Mr. Cordian seems
to have decided to flim-flam the List a little. Rather than admit an error,
a little over-enthusiasm in his recollection of the facts, Cordian decided
bluff it out.

	He quoted for us only the beginning of Flinn's footnote, and he
ignored the rest of the footnoted text -- which, quite inconveniently for
him, seemed to directly refute his initial claim.

	(A nymed net-gent like Mr. Cordian -- who hides his real identity
behind the Cordian pseudonym -- can perhaps risk his reputation a little
more carelessly than the rest of us. If he soils this one, after all, he
can just pony up for a new identity.)

	Wrote Mr. Cordian:

>Quoting "Cyberlaw":
>
>    "There are a number of references in the prior art, moreover,
>     to using the problem of factoring composite numbers in
>     cryptography, dating back to the 19th century.
>
>    "In 1870, a book by William S. Jevons described the
>     relationship of one-way functions to cryptography and went
>     on to discuss specifically the factorization problem used
>     to create the "trap-door" in the RSA system."

	Actually, the first line of Cordian's quote is from the main text
of Flinn's article: http://www.cyberlaw.com/rsa.html. The second line is
from Flinn's Footnote # 64.

	The _full_ text of Footnote # 64 reads as follows:

[64] In 1870, a book by William S. Jevons described the relationship of
one-way functions to cryptography and went on to discuss specifically the
factorization problem used to create the "trap-door" in the RSA system. In
July, 1996, one observer commented on the Jevons book in this way:

In his book The Principles of Science: A Treatise on Logic and Scientific
Method, written and published in the 1890's, William S. Jevons observed
that there are many situations where the 'direct' operation is relatively
easy, but the 'inverse' operation is significantly more difficult, One
example mentioned briefly is that enciphering (encryption) is easy while
deciphering (decryption) is not. In the same section of Chapter 7:
Introduction titled 'Induction an Inverse Operation', much more attention
is devoted to the principle that multiplication of integers is easy, but
finding the (prime) factors of the product is much harder. Thus, Jevons
anticipated a key feature of the RSA Algorithm for public key cryptography,
though he certainly did not invent the concept of public key cryptography.

Solomon W. Golomb, On Factoring Jevons' Number, CRYPTOLOGIA 243 (July 1996)
(emphasis added).

	<End of quoted text.>

	(The conflict between the 1870 and 1890 dates cited in different
paragraphs for the pub date of Jevon's "The Principles of Science" is as
published in the original Cyberlaw article. I have no explanation, but the
1870 date seems most likely.  William Stanley Jevons, an astonishingly
prolific American economist, philosopher, and logician, was born 1835 and
died in 1882. He is probably the W.S. Jevons cited here, but I can't be
sure since I can find this title among the list of Jevon books in the
Library of Congress.)

	The Cryptologia journal, unfortunately, is not yet available
on-line, and the Golomb article doesn't seems available elsewhere.  Might
be worth digging that up. I'd love to read more of what Shannon Award
winner Sol Golomb had to say about the relationship between Jevon's 19th
Century mathematical research and public key cryptography.

	I think it is appropriate to note, however, that Prof. Golomb did
_not_ conclude that the functionality of the RSA public key cryptosystem
was "obvious" to anyone familiar with Jevons' work.

	Suerte,
		_Vin


-----
"Cryptography is like literacy in the Dark Ages. Infinitely potent, for
good and ill... yet basically an intellectual construct, an idea, which by
its nature will resist efforts to restrict it to bureaucrats and others who
deem only themselves worthy of such Privilege."
_ A Thinking Man's Creed for Crypto  _vbm.

 *     Vin McLellan + The Privacy Guild + <vin@shore.net>    *
      53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548