🚀 go-pugleaf

In article <106@lll-risky.arpa>, tjt@lll-risky.arpa (Tim Tessin) writes:

> [...] how one might implement a crypto-system without infringment, the
> legal-eagles say you're screwed.  (This is if you are a commercial
> venture.  Exactly what the U.S. Government has as patent rights are
> still being determined.  The research was partly funded by
> the U.S. Government and it retains some rights.)

***>>>>TORCH ALERT<<<<***

	If the research was partly funded by government grants, is it not
then the case that the TAXPAYERS own part of it ? I thought the procedure
would then be that it HAS to be available through the US Government printing
agency, at cost ?! 

	Let's be real - the US Government ("for the people" and all that shit)
keeps spending the taxpayer's money on stuff like DARPA and UCB's grants, and
then lets people go Copyright the work, or patent it. Has anyone ever tried
to make an issue out of this ? Who said that the government could waive its
share of the rights to RSA ?

***>>>>FLAME OFF<<<<***

--mjr();

PS - I *KNOW* (before you flame me) that the preceeding was totally idealistic
and unrealistic. I like to occasionally make such postings/flames so that at
least some of the readers on the net will get an idea of how badly the amerikan
publik gets boned up the a** by its government.
-- 
If they think you're crude, go technical; if they think you're technical,
go crude. I'm a very technical boy. So I get as crude as possible. These
days, though, you have to be pretty technical before you can even aspire
to crudeness...			         -Johnny Mnemonic

In article <106@lll-risky.arpa> tjt@lll-tis.arpa (Tim Tessin) writes:
[He quoted the abstract of the patent.  Someone tell him that
 facts are less important than uninformed opinion. :)

 Surprise!  The abstract says that it covers the use of one function
 for encryption.  The patent doesn't claim to cover other functions
 with similar properties.]

[He then discusses the impact of this patent.]

>Barring any procedural errors MIT and RSA made in obtaining the patent
>(a low probability) and barring excruciating analysis of the patent to
>determine just exactly how one might implement a crypto-system without
>infringment, the legal-eagles say you're screwed.

If that the abstract is a fair representation of what the patent
actually covers, the RSA patent is quite narrow.  It covers the use
of ONE trapdoor function.  Devices that work with RSA encryption systems
are covered, but devices/programs that use other functions are not.

So, what are the relevant properties (to encryption) of the function RSA
chose?  What are other functions with these properties?

-andy
-- 
Andy Freeman
UUCP:  {arpa gateways, decwrl, sun, hplabs, rutgers}!sushi.stanford.edu!andy
ARPA:  andy@sushi.stanford.edu
(415) 329-1718/723-3088 home/cubicle

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.

Maybe you can hide the exponential as a loop of multiplications.
Remember, judges are not mathematicians -- they have to rely on expert
testimony to make decisions about math (I had a math sciences
professor once who made a fortune consulting as an expert witness in
redistricting trials, since he was an expert in the theory of voting).
If it sounds like it's different, the judge will probably believe it's
different.

[ Excuse me, I have to go mail a copy of this function to myself in an
   unopened letter. ]

Michael L. Mauldin (Fuzzy)		Department of Computer Science
ARPA: Michael.Mauldin@NL.CS.CMU.EDU	Carnegie-Mellon University
Phone: (412) 268-3065			Pittsburgh, PA  15213-3890

     The RSA patent covers only the product-of-two-large-primes public
key cryptosystem.  One can still use a knapsack-based public key system.
Solutions are known for the knapsack problem, of course.  But ways are
known to factor large numbers, too, and recent progress in this area has been
rapid.  Recent contributors to this group have reported on their work in
factoring, and are factoring numbers of sizes that used to be considered
reasonable for RSA algorithms.  So RSA really is obsolete technology.

     I don't believe that at present there are any really satisfactory
functions known for public-key systems.  

					John Nagle

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

In article <622@rocky.STANFORD.EDU> andy@rocky.UUCP (Andy Freeman) writes:

>So, what are the relevant properties (to encryption) of the function RSA
>chose?  

The idea is that everybody can know the encryption algorithm,
but find it very hard (unlikely in a reasonable time) to decode.

>What are other functions with these properties?

This is the big search...  Find one, and you can have a patent too.

-- 
 L. J. Dickey, Faculty of Mathematics, University of Waterloo. 
 ljdickey@watmath.UUCP		UUCP: ...!uunet!watmath!ljdickey
 ljdickey%water@waterloo.edu	ljdickey@watdcs.BITNET		
 ljdickey%water%waterloo.csnet@csnet-relay.ARPA