Path: gmdzi!unido!math.fu-berlin.de!ira.uka.de!sol.ctr.columbia.edu!
zaphod.mps.ohio-state.edu!sdd.hp.com!elroy.jpl.nasa.gov!ncar!midway!msuinfo!news
From: rior...@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
Sender: ne...@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 rior...@clvax1.cl.msu.edu
===== Received mail follows ============================================
From: j...@RSA.COM (Jim Bidzos)
Message-Id: <910516171...@RSA.COM>
To: "Mark Riordan" <rior...@clvax1.cl.msu.edu>
Cc: "pem-dev" <pem...@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
<910516143...@TIS.COM>
Sender: pem-de...@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...@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.
Path: gmdzi!unido!mcsun!uunet!zaphod.mps.ohio-state.edu!
uakari.primate.wisc.edu!caen!uwm.edu!linac!att!bellcore!epic!karn
From: karn@epic..bellcore.com (Phil R. Karn)
Newsgroups: sci.crypt,gnu.misc.discuss,misc.legal
Subject: Re: rpem: RSA patent questions
Message-ID: <1991May20.013244.21526@bellcore.bellcore.com>
Date: 20 May 91 01:32:44 GMT
References: <25666:May1904:50:0491@kramden.acf.nyu.edu>
<1991May20.000757.16705@ux1.cso.uiuc.edu>
<4703:May2000:47:5291@kramden.acf.nyu.edu>
Sender: use...@bellcore.bellcore.com (Poster of News)
Organization: Bell Communications Research, Inc
Lines: 18
Xref: gmdzi sci.crypt:53909 gnu.misc.discuss:42713 misc.legal:66292
Does anyone know the status of public key patents in Canada? I had
heard that RSA was patented only in the USA, but I don't know about
the others.
If only US patent protection exists for public key cryptography, then
the obvious thing to do with rpem is to put it up for anonymous FTP on
a site in Canada, beyond the protection of the US patent. Of course,
individual US users who retrieve and use it in the US could still be
sued for patent infringement, but this would be a lot harder than
going after a public FTP site (as demonstrated by the nonsense over
R/X-rated GIF images).
And since Canada is an exception to the State Department requirements
for licensing the export of cryptographic software, there should be
no problem on this score.
Phil