When the always well-informed John Young reported that the US Patent Office had issued MIT Prof. Ron Rivest US Patent 5835600 for a "Block encryption algorithm with data-dependent rotations," Eric Cordian <emc@wire.insync.net> growled:

So we can't use the rotate instruction with a data-dependent shift count in a block encryption algorithm without a license from Ron?

Foo on that.

Really, Mr. Cordian, you should read a patent before you foo at it. See: http://jya.com/rivest111098.htm This particular patent is probably less than it first appears to be. When a patent is marked as "divisional" of a specific application, it means it has been broken off and separated from a prior patent application. In this case, when Rivest sought a patent for RC5, a block cipher which is notable for the elegant simplicity that has become Ron's trademark style, the Patent Examiner suggested that he refile the application in two parts: one on the encryption method, and a second on the key-schedule structure. The patent on the RC5 encryption method, US5724428 -- which has generally been referred to as the RC5 patent -- was issued March 3, 1998, with the same title ("Block encryption algorithm with data-dependent rotations") and an identical Abstract to this more recent patent, US5835600, which was issued Nov. 10. See: http://www.patents.ibm.com/details?pn=US05724428__&language=en This latest patent, US5835600, only covers the design of the key schedule used in RC5 (and RC6). Period. The data-dependent rotation claims were in the earlier RC5 patent. Even Ron's initial RC5 patent, however, referred to data-dependent rotations only in the context that they are used in RC5. It surely is not any universal IP claim. Among the relevant prior work Rivest cited in his original application (and US5724428) was Wolfram Becker's work for IBM in the 1970s -- patented in US4157454 -- which seems to rely on data-dependent rotations too. Note that the Patent Examiners determined that Becker's work did not impinge upon or otherwise disqualify Rivest's specific RC5 claims. (I wouldn't hazard a guess as to whether RSA's RC5 patent covers IBM's MARS algorithm, as some have suggested, just because MARS also uses data-dependent rotations. Some on this list may be competent to dice the issues that fine but I am not.) Mr. Cordian ventured an additional opinion or two: |>As you may have guessed, I'm not a fan of permitting software to be |>patented. Particularly things like RSA for which obvious prior art |>existed.... Eric Michael Cordian is a Persistant Network Nym which has been around for quite a while. It recently caught to eye of some crypto mavens on these lists when Cordian revealed himself as both a pseudonym and a collective identity. E.M. Cordian has been the net persona behind which a group of self-described cryptographic professionals have raised $7,500 in donations to underwrite the "DES Analytic Crack Project," an <ahem> ambitious effort "to develop ANSI C code which will break DES in under one day on a $5k workstation." See: http://www.cyberspace.org/~enoch/crakfaq.html 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. Horseshit! Stanford and Cylink couldn't find it, despite a highly motivated and well-funded search. They doubtless would have paid you handsomely for your evidence and definitive testimony, but you missed your chance. Now you'll -- collectively, Sirs? -- just have to settle for being another cadre in the crowd that hoots and sneers at Ron Rivest whenever he comes up with something new which significantly enhances our cryptographic arsenal (and has the gall to patent it or otherwise claim IP ownership.) Seems like a demeaning role for a group of professionals which claim to collectively have "decades of practical experience in successfully implementing the most complex computer algorithms." Suerte, _Vin PS. Regarding the debate about whether RC6 will be freely available, my understanding (as a consulant to RSA) is that Jim Gillogly has it right. If RC6 is selected as the American AES, RSA (now a subsidary of Security Dynamics) will relinquish all patent rights and royalty expectations. If RC6 is not selected as the AES -- and given the decades of conflict, antagonism, and competition between the spooks of the NSA and RSA, RC6 is surely a remote long shot -- RSA will offer it as a commercial product. The two RC5 patents appear to cover RC6. The AES evaluation process will provide an invaluable high-stress testbed for Rivest's innovative use of data-dependent rotations. When the AES is chosen by the NSA -- whichever algorithm is finally chosen -- the cryptographic community will know a lot more about the security and viability of this particular Rivest design. Then we can start wondering what Rivest will come up with for Ron's Code (RC) 7. ----- Vin McLellan + The Privacy Guild + <vin@shore.net> 53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548 -- <@><@> --

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