oz@nexus.YorkU.CA (Ozan Yigit) (05/17/91)
[The following article is from sci.crypt, and it is re-posted in these newsgroups for your information. The author had earlier announced rpem, a Privacy Enhanced Mail/public-key program. RSA thinks this code infringes on their patents.] >From: riordanmr@clvax1.cl.msu.edu (Mark Riordan) Newsgroups: sci.crypt Subject: rpem: RSA patent questions Keywords: RSA patent rpem Message-ID: <1991May16.201709.3086@msuinfo.cl.msu.edu> Date: 16 May 91 20:17:09 GMT Article-I.D.: msuinfo.1991May16.201709.3086 Posted: Thu May 16 16:17:09 1991 Sender: news@msuinfo.cl.msu.edu Organization: Michigan State University Lines: 115 I hate to bring up the old RSA software patent question again, but this time we have a real life situation. As you can see from the message below, RSA is unhappy with my releasing a public key encryption program. I claim that the algorithm here does not closely resemble RSA and therefore should not infringe upon the patent(s). They claim otherwise. I seek advice, or pointers to advice, in this real-life situation. ---------------------------------------------------------------------------- Incidentally, here is a quick sketch of "their" technique versus "mine": Both systems start with two primes, p and q. ----- RSA requires the user to select an arbitrary encryption key, e. From e, p, and q is computed the corresponding decryption key, d. Encryption and decryption are almost identical: ciphertext = plaintext^e mod pq plaintext = ciphertext^d mod pq ----- The system I use (which I call "Rabin" but which may not be the same as what most people call "Rabin"; I've never located the original paper) works like this: ciphertext = plaintext^2 mod pq Decryption is more difficult. The square roots of the ciphertext mod p and mod q are computed using Berlekamp's square root algorithm. (It's magic to me, and works only for prime moduli. If Berlekamp worked for composite moduli, the whole cipher would be worthless.) Then the Chinese Remainder Theorem is used on the these two square roots mod p and q to find the 4 square roots of the ciphertext mod pq. One of these square roots is the plaintext; the correct one is selected based on redundant information added in during the encryption process. ----------------------------------------------------------------- I'm not exactly putting my decision up to a vote on sci.crypt (what a ghastly thought that would be), but what do you folks think I should do? Email directly to me if you think that the net has suffered through patent discussions enough already. Mark Riordan riordanmr@clvax1.cl.msu.edu ===== Received mail follows ============================================ >From: jim@RSA.COM (Jim Bidzos) Message-Id: <9105161715.AA06925@RSA.COM> To: "Mark Riordan" <riordanmr@clvax1.cl.msu.edu> Cc: "pem-dev" <pem-dev@TIS.COM> Subject: Re: rpem: Simple Privacy Enhanced Mail system In-Reply-To: "Mark Riordan"'s message of 16 May 91 10:29:00 EDT <9105161431.AA07051@TIS.COM> Sender: pem-dev-relay@TIS.COM The author of the following message does not have direct Internet access. Paper mail will follow to Mark Riordan and Michigan State University. ---------------------------------------------------------------------- May 16, 1991 Dear Mr. Riordan, We refer to your posting to pem-dev@tis.com of May 16, 1991: > Announcing the initial release of "rpem", a mostly public domain > Privacy Enhanced Mail program incorporating a public key encryption system > The public key encryption algorithm used in rpem is Rabin's: > ciphertext = plaintext^2 mod pq (p, q are primes) > The public component of the key is pq, and the private component > is p and q. Rabin's algorithm is probably slower (on decryption) and less > aesthetically pleasing than RSA, for instance, but it's in the > public domain. Also, unlike RSA, breaking Rabin's scheme is provably > as hard as factoring a product of two primes. The Massachusetts Institute of Technology and the Board of Trustees of the Leland Stanford Junior University have granted Public Key Partners exclusive sublicensing rights to the following patents registered in the United States, and all of their corresponding foreign patents: Cryptographic Apparatus and Method ("Diffie-Hellman") .......................... No. 4,200,770 Public Key Cryptographic Apparatus and Method ("Hellman-Merkle") ............... No. 4,218,582 Cryptographic Communications System and Method ("RSA") .............................. No. 4,405,829 Exponential Cryptographic Apparatus and Method ("Hellman-Pohlig") ............... No. 4,424,414 These patents cover most known methods of practicing the art of public-key cryptography, including the system commonly known as "Rabin," which is NOT, contrary to your claim, public domain, and is covered by at least two of the patents listed above. WE HEREBY PLACE YOU AND ALL USERS OF YOUR IMPLEMENTATION OF PUBLIC KEY, ON NOTICE THAT THEY ARE INFRINGING ON THESE PATENTS AND WE RESERVE ALL OF OUR RIGHTS AND REMEDIES AT LAW. Yours, Public Key Partners Robert B. Fougner, Esq. Director of Licensing Jim Bidzos adds: One of the patents we cited has broad claims on cryptosystems based on exponentiation. This would cover a cryptosystem that used CR theorem, since it does tow (or more) exp's with a combining operation. The traditional Rabin method, we believe, is clearly covered by the RSA patent itself as the claims allude to non-odd e and/or d.
hollaar%basset.utah.edu@cs.utah.edu (Lee Hollaar) (05/18/91)
>I hate to bring up the old RSA software patent question again, but >this time we have a real life situation. >As you can see from the message below, RSA is unhappy with my releasing >a public key encryption program. >I claim that the algorithm here does not closely resemble RSA and >therefore should not infringe upon the patent(s). They claim otherwise. To know whether something infringes a patent, you have to read the claims in the patent. The claims can be much broader than the invention that the patent is to protect. This is particularly true for pioneering inventions. When reading the claims, you see if each element of the invention recited in the claim is present in your invention. If all elements are present, then you infringe the patent. If just one element of the claim is not present, then there is no infringement. If your invention contains things not present in the patent claim, and the claim describes the invention as "comprising" the elements, then you still infringe. If you have an element that is similar to, but not exactly like, one in the claim, you may still be infringing under the "doctrine of equivalence." The penalties for infringement can be stiff, and they are even worse for intentional infringement (which would probably be the case here because of the warning letter). The Court of Appeals for the Federal Circuit, which handles all patent infringement appeals, has made it almost impossible to be an innocent infringer of a valid patent that you know exists. And it's not just the person who distributes the program, but anybody who makes, uses, or sells the patented invention within the United States. Don't depend on information from people on the net who might not understand patent law. See a good patent attorney or patent agent. Lee Hollaar Professor of Computer Science Registered Patent Agent