henry@utzoo.UUCP (Henry Spencer) (07/03/87)
Anybody know of a reasonably good public-key encryption system which has
not been broken like the knapsack algorithm and is not patented like RSA?
We have an urgent application for such a thing, and I would rather avoid
patent infringement. I haven't been following the public-key business
very closely, so I don't have a good picture of what's current.
--
Mars must wait -- we have un- Henry Spencer @ U of Toronto Zoology
finished business on the Moon. {allegra,ihnp4,decvax,pyramid}!utzoo!henrybs@linus.UUCP (Robert D. Silverman) (07/05/87)
In article <8248@utzoo.UUCP] henry@utzoo.UUCP (Henry Spencer) writes:
]Anybody know of a reasonably good public-key encryption system which has
]not been broken like the knapsack algorithm and is not patented like RSA?
]We have an urgent application for such a thing, and I would rather avoid
It doesn't exist.
Bob Silvermanmlm@nl.cs.cmu.edu (Michael Mauldin) (07/06/87)
I have heard Michael Shamos of Unilogic (who is both a practicing attorney and a PhD in Computer Science) lecture on copyrights, patents, trade secrets and trademarks on several occasions. Each time, he has said that one cannot patent algorithms (at least in the US). There is an exclusion clause that says you cannot patent something that can be done "with pencil and paper," so algorithms by themselves are not protectable. One way around this is to patent a system with an algorithm embedded in it. The system then enjoys patent protection. So ROM code in firmware is protected along with the rest of the device using it. How does this relate to the legal status of RSA? Is it just Rivest's special purpose chip that is patented? A particular setting of some of the parameters? Or are all exponentiation ciphers (M^e mod pq) protected? I can find no mention in Denning82 "Cryptography and Data Security" that the RSA scheme of public key encryption is patented. Surely she would have mentioned it. 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
ralphw@ius2.cs.cmu.edu (Ralph Hyre) (07/06/87)
In article <12@nl.cs.cmu.edu> mlm@nl.cs.cmu.edu (Michael Mauldin) writes: > >I have heard Michael Shamos of Unilogic (who is both a practicing >attorney and a PhD in Computer Science) lecture on copyrights, patents, >trade secrets and trademarks on several occasions. Each time, he has >said that one cannot patent algorithms (at least in the US). There is >an exclusion clause that says you cannot patent something that can be >done "with pencil and paper," so algorithms by themselves are not >protectable. > >One way around this is to patent a system with an algorithm embedded in >it. The system then enjoys patent protection. So ROM code in firmware >is protected along with the rest of the device using it. > >How does this relate to the legal status of RSA? Is it just Rivest's >special purpose chip that is patented? A particular setting of some of >the parameters? Or are all exponentiation ciphers (M^e mod pq) protected? I believe that the use of RSA in a "cryptographics communications system" is patented. Unfortunately this seems to cover most of the normal applications in which RSA is useful. (encrypting a message, transmitting it to someone, and decrypting it.) I'd appreciate it if someone could post the specifics (ie definition of a cryptographics commuications system, etc.) -- - Ralph W. Hyre, Jr. Internet: ralphw@ius2.cs.cmu.edu Phone:(412)268-{2847,3275} CMU-{BUGS,DARK} Amateur Packet Radio: N3FGW@W2XO, or c/o W3VC, CMU Radio Club, Pittsburgh, PA
misha@cernvax.UUCP (misha) (07/07/87)
In article <8457@linus.UUCP> bs@linus.UUCP (Robert D. Silverman) writes: >In article <8248@utzoo.UUCP] henry@utzoo.UUCP (Henry Spencer) writes: >]Anybody know of a reasonably good public-key encryption system which has >]not been broken like the knapsack algorithm and is not patented like RSA? >]We have an urgent application for such a thing, and I would rather avoid > >It doesn't exist. > >Bob Silverman What about Michael Rabin's scheme? It is possibly more secure than RSA since Rabin proves it to be as intractable as factorization. Like RSA, the scheme involves a number n=p*q, a product of two large primes, but encryption and decryption functions are different. Also, they are a lot faster to compute. The scheme is described in MIT note MIT/LCS/TR-212 of January 1979. In fact, Rabin's scheme seems to be a clear winner over RSA, and I haven't heard of anybody finding flaws in it or applying for a patent. Anybody has more information? Michael Kharitonov misha@cernvax.bitnet
galvin@udel.UUCP (07/07/87)
In article <8457@linus.UUCP> bs@linus.UUCP (Robert D. Silverman) writes: >In article <8248@utzoo.UUCP] henry@utzoo.UUCP (Henry Spencer) writes: >]Anybody know of a reasonably good public-key encryption system which has >]not been broken like the knapsack algorithm and is not patented like RSA? > >It doesn't exist. Not true. As far as I know any algorithm based on computing logarithms in a finite field are available. Cylink is marketing a product called SEEK which is based on this, but there are many variations of the algorithm and I can't imagine they could have a "lock" on all of them, since you can't patent an algorithm. References available on request. galvin@udel.edu -- James M Galvin
devine@vianet.UUCP (Bob Devine) (07/09/87)
In article <12@nl.cs.cmu.edu> mlm@nl.cs.cmu.edu (Michael Mauldin) writes: > [...] algorithms by themselves are not protectable. >One way around this is to patent a system with an algorithm embedded in >it. The system then enjoys patent protection. So ROM code in firmware >is protected along with the rest of the device using it. [Doesn't this protection stem from the case where a manufacturer wanted to protect a program that handled the curing of rubber?] It may be that the RSA algorithm is protected in this way. The algorithm HAS been issued a patent (Patent 4,405,829 held by MIT and licensed by RSA Data Security Inc). Bob Devine
mlm@nl.cs.cmu.edu (Michael Mauldin) (07/13/87)
In article <321@louie.udel.EDU>, galvin@udel.EDU (James M Galvin) writes: >>> Anybody know of a reasonably good public-key encryption system which has >>> not been broken like the knapsack algorithm and is not patented like RSA? >> >> It doesn't exist. > > Not true. As far as I know any algorithm based on computing logarithms > in a finite field are available. How about using an exponentiation cipher based on three or more secret primes instead of just two (like the RSA scheme): C = exp (M, E) mod N M = exp (C, D) mod N Where: M = message (clear) text C = cipher text N = p*q*r p,q,r are large 'safe' primes Then phi(N) = (p-1)(q-1)(r-1) E,D such that gcd(D,phi(N)) = 1 and E*D = 1 mod phi(N) (for example, fix D, compute E = invert (D, phi(N))) A prime p is safe if p = 2p'+1 for some prime p'. To use k primes p(i), just compute __ N = || p(i) i=1,k __ phi(N) = || (p(i)-1) i=1,k The neat trick is that you could still use RSA hardware for encryption and decryption, since the enciphering/deciphering step is still C = exp (M, E) mod N, the only difference is the method of computing the actual values of E, D, and N. Questions: Is this different enough from RSA to avoid patent infringement? Does choosing modulus N with a few factors (say 3 to 10) rather than just 2 make it much easier to factor N? Are there any known pitfalls to using more than 2 primes? What's the state of the art in factoring large numbers. How fast can it be done on various computers (Vax, Sun, PC, Cray, VLSI)? 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
spencert@itsgw.RPI.EDU (Thomas Spencer) (07/17/87)
> In article <8457@linus.UUCP> bs@linus.UUCP (Robert D. Silverman) writes: [Henry Spencer's request for a good public-key cyrpto-system deleted] >What about Michael Rabin's scheme? It is possibly more secure than RSA >since Rabin proves it to be as intractable as factorization. Like RSA, >the scheme involves a number n=p*q, a product of two large primes, but >encryption and decryption functions are different. Also, they are a lot >faster to compute. >The scheme is described in MIT note MIT/LCS/TR-212 of January 1979. > >In fact, Rabin's scheme seems to be a clear winner over RSA, and I haven't >heard of anybody finding flaws in it or applying for a patent. Anybody has >more information? > >Michael Kharitonov >misha@cernvax.bitnet As you probably know, Rabin's scheme is just like RSA except that it uses the exponent 2, instead of some exponent to relatively prime to (p-1)(q-1). Thus, it may be covered by the RSA patent. Get a lawyer to read the RSA patent, if you plan to do anything serious with the system. The proof that beaking this scheme is equivalent to factoring points out a fatal weakness of the system if it is used as a signature system. If we assume that the advesary can force you to sign arbitrary messages, he can easily break the system as follows: 1. He picks a random number x. 2. He computes x^2. 3. He makes you sign x^2 to obtain y. 4. With probability 1/2 y is neither x nor -x (mod n). 5. If so x+y is a multpile of p or q and factoring n is now easy. I hope that this helps. -Tom Spencer spencert@cs.rpi.edu
bs@linus.UUCP (Robert D. Silverman) (07/18/87)
]>]Anybody know of a reasonably good public-key encryption system which has ]>]not been broken like the knapsack algorithm and is not patented like RSA? ]> ]>It doesn't exist. ] ]Not true. As far as I know any algorithm based on computing logarithms ]in a finite field are available. Cylink is marketing a product called Sorry, but due to the efforts of Odlyzko, Coppersmith, et. al. the discrete log in GF(p^q) problem is effectively solvable. Bob Silverman