Tech Insider					     Technology and Trends


			      USENET Archives

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

			        About USENET

USENET (Users’ Network) was a bulletin board shared among many computer
systems around the world. USENET was a logical network, sitting on top
of several physical networks, among them UUCP, BLICN, BERKNET, X.25, and
the ARPANET. Sites on USENET included many universities, private companies
and research organizations. See USENET Archives.

		       SCO Files Lawsuit Against IBM

March 7, 2003 - The SCO Group filed legal action against IBM in the State 
Court of Utah for trade secrets misappropriation, tortious interference, 
unfair competition and breach of contract. The complaint alleges that IBM 
made concentrated efforts to improperly destroy the economic value of 
UNIX, particularly UNIX on Intel, to benefit IBM's Linux services 
business. See SCO vs IBM.

The materials and information included in this website may only be used
for purposes such as criticism, review, private study, scholarship, or
research.

Electronic mail:			       WorldWideWeb:
   tech-insider@outlook.com			  http://tech-insider.org/