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