Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!mit-eddie!ll-xn!ames!lll-tis!lll-risky!tjt
From: tjt@lll-risky.arpa (Tim Tessin)
Newsgroups: sci.crypt,comp.misc
Subject: Re: public key encryption and RSA patent status
Message-ID: <108@lll-risky.arpa>
Date: Tue, 29-Sep-87 14:13:23 EDT
Article-I.D.: lll-risk.108
Posted: Tue Sep 29 14:13:23 1987
Date-Received: Thu, 1-Oct-87 04:25:27 EDT
References: <106@lll-risky.arpa> <622@rocky.STANFORD.EDU> <30@nl.cs.cmu.edu>
Reply-To: tjt@lll-risky.arpa.arpa (Tim Tessin)
Lines: 69
Keywords: RSA patent
Xref: mnetor sci.crypt:593 comp.misc:1361

In article <30@nl.cs.cmu.edu> mlm@nl.cs.cmu.edu (Michael Mauldin) writes:
> 
> I've already suggested another function:
> 
> 	C=M^E mod (p*q*r)  which gives
> 	M=C^D mod (p*q*r), where D = invert (E, (p-1)(q-1)(r-1))
> 
> The RSA method generalizes to any number of secret primes because of
> the properties of the  Euler totient function.
> 
> Maybe you could even convince the judge that "more primes are better"
> and that your function is an "improvement" over the RSA patent.

I really didn't want to type all this in, but I might as well.  This
is the text covering what the scope of the claims are (but not the 
actual claims):

From U.S. Patent 4,405,829:
- In general, the present invention provides secure communications as a 
- practical matter because the operation of evaluating a polynomial
- modulo n, where n is a large composite number, may be easily inverted
- only with the knowledge of the factors of n.  In the preferred
- embodiment described above, n=p*q, where p and q are prime, and the
- message M is transformed by evaluating the polynomial f(M)=M^e mod n,
- where gcd(e,(p-1)*(q-1)) = 1.
- 
- In alternative embodiments, the present invention may use a modulus n
- which is a product of three or more primes (not necessarily distinct).
- Decoding may be perfomed modulo each of the prime factors of n and the
- results combined using "Chinese remaindering" or any equivalent method
- to obtain the result modulo n.
- 
- In still other embodiments, the message M may be encoded to ciphertext
- C by evaluating a polynomial a(e)M^e + a(e-1)M^(e-1) + ... + a0 mod n
- where e and a(e), a(e-1),...a0 are numbers.  In such embodiments, C
- may be decoded utilizing conventional root-finding techniques,
- choosing which of any roots is the proper decoded version, for example, 
- by the internal redundancy of the message.
- [constraints on e and totient function omitted]
- 
- In yet other embodiments, the message M may be encoded to ciphertext C
- by the performance of an ordered succession of invertible operations
- (modulo n) on M, with the succession including at least
- exponentiatoin, and in various embodiments, such other invertible
- operations as adding, subtracting, multiplying or dividing by
- constants (positive or negative), and simple bit manipulations (e.g.
- complementing or permuting bits).  Decoding is accomplished by
- applying a second succession of invertible operations [...] each 
- corresponding to one of the operations in the encoding succession,
- [...] in reverse order [...].
- 
- Similarly, the following variations on the use of the encoding/decoding
- devices are to be considered as obvious to one skilled in the prior
- art and therefore within the intended scope of the attached claims:
-   (1) using the encoding/decoding devices in cipher-feedback mode
-       instead of the simple block encoding method described here, or as a
-       pseudo-random number generator for use to generate pads,
   ** [does this mean we can't use it to store local messages??] **
-   (2) signatures may be effected by signing a transformed version of the
-       message, where the transformation is publicly known and not
-       necessarily invertible.  (It may, for example, compress the message 
-       to be signed into a shorter form, thus giving shorter signatures).
-   (3) using the present invention to transmit keys to be used in another
-       encryption method for encoding subsequent messages.

Tim Tessin - Lawrence Livermore National Laboratory 
Phone: (415) 423-4560 / 422-8971
ARPA:  tjt@lll-tis.ARPA
UUCP:  {ihnp4,dual,sun}!lll-lcc!lll-tis!tjt