jbuck@epimass.EPI.COM (Joe Buck) (01/01/70)
In article <3988@well.UUCP> shibumi@well.UUCP (Kenton A. Hoover) writes: >>You can patent anything that you can convince the patent office to >>issue you a patent for. In article <7335@ism780c.UUCP> tim@ism780c.UUCP (Tim Smith) writes: >The patent office will issue for almost anything that hasnt yet been invented >and that meets the 'what can be patented' standard. The strength of your >patent is almost always only determined through litigation. That was my point. The patent is no good unless the courts will enforce it, and I suspect that the RSA patent will fall as soon as an organization with sufficient legal resources decides to challenge it. But don't try this at home if you don't want to spend time in court. -- - Joe Buck {uunet,ucbvax,sun,decwrl,<smart-site>}!epimass.epi.com!jbuck Old internet mailers: jbuck%epimass.epi.com@uunet.uu.net
mlm@nl.cs.cmu.edu (Michael Mauldin) (09/15/87)
I agree with jbuck@epimass's assessment of the situation. As I
remember it, you can't patent something that can be done (in principle)
by a person using pencil and paper.
Several months ago I posted a request asking just what about RSA the
MIT patent covers. I got no answers. It seems to me that they can be
patenting any of a number of things:
o their special purpose hardware to perform RSA
o their method of selecting primes (again probably only
as it's imbedded in ROM in some hardware).
o their specific approach to choosing primes and using
exponentiation (their specific algorithm)
o the general notion of using C = M^E mod pq
The first two would hold up, because you can patent a system with
algorithms embedded in it, but then the algorithm itself is not
necessarily protected. The last two seem to violate the pencil and
paper test.
Not wanting to spend the time or money to ask the patent office for a
copy of the patent, I hoped I could find out on the net. Does anyone
know specifically what the Patent was granted for/what they claimed?
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-3890andy@rocky.UUCP (09/18/87)
In article <25@nl.cs.cmu.edu> mlm@nl.cs.cmu.edu (Michael Mauldin) writes: > o the general notion of using C = M^E mod pq I believe that the patent covers the use of this equation for a specific purpose. Patents protect applications of phenomena, not the phenomena. The patent doesn't cover other uses of this equation. -andy ps - The "pencil and paper" rule is bogus. Copiers are patentable. -- 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
jewett@hpl-opus.UUCP (09/18/87)
> Not wanting to spend the time or money to ask the patent office for a > copy of the patent, I hoped I could find out on the net. Does anyone > know specifically what the Patent was granted for/what they claimed? > Michael L. Mauldin (Fuzzy) Department of Computer Science From my mouldy archives... /***** hpl-opus:net.crypt / mit-eddi!baldwin / 6:16 am Jul 25, 1985*/ To: Whom It May Concern From: Ronald L. Rivest NE43-324, 545 Technology Square, MIT Laboratory for Computer Science Cambridge Mass. 02139 (Phone: 617-253-5880, ARPA: RIVEST@MIT-MC) Date: July 22, 1985 Re: RSA Patent This letter is in response to a number of inquiries that were received regarding the RSA cryptosystem, stimulated by recent articles and letters in BYTE magazine (and elsewhere). Yes, the RSA cryptosystem is patented, by MIT. The U.S. patent number is 4,405,829. To my knowledge there are no foreign patents. If you read the patent, you will discover that it is not an "algorithm" patent. It does not matter how (i.e. with what algorithm) the RSA computation is performed, only that the cryptographic communications system has black boxes for doing that computation. I believe the patent is well-drafted and would stand up to challenge easily. It covers both software and hardware implementations. MIT has granted an exclusive sublicense on the patent to a new company called "RSA Security, Inc.". This company was founded by the inventors of the RSA cryptosystem (myself, Adi Shamir, and Len Adleman). The objective of the company is to commercialize and exploit the RSA cryptosystem, through a variety of techniques, including direct end-user product sales (software systems such as COMSAFE (TM) and MAILSAFE (TM) for the IBM PC), sales custom chips for performing RSA computations, consulting for integrating RSA into applications, joint venture arrangements, sublicenses, standards, etc. RSA Security is eager to work with those who have an interest in using the RSA cryptosystem. If you would like more information, please contact either myself or Ralph Bennett President, RSA Security Inc. 1717 Karameos Drive Sunnyvale, California 94087 (408) 730-8701 /* ---------- */
tim@ism780c.UUCP (Tim Smith) (09/19/87)
In article <25@nl.cs.cmu.edu> mlm@nl.cs.cmu.edu (Michael Mauldin) writes:
< I agree with jbuck@epimass's assessment of the situation. As I
< remember it, you can't patent something that can be done (in principle)
< by a person using pencil and paper.
You can patent anything that you can convince the patent office to
issue you a patent for.
The book "Software Law - A Primer" ( or something like that ) has
some examples of patents that have been granted that are similar
to RSA.
For example, there was some manufacturing process that involved the
use of feedback ( if I remember correctly ). Someone came up with
the idea of using a specific function to control the feedback.
It was a fairly simple function, too. One that shows up in other
things. Something like y=exp(-x).
Their patent was not an attempt to patent the exponential function.
Their patent was an attempt to patent the use of an exponential
function as a key step in making a specific type of item.
The patent was granted. This did not mean that other people could
not use exponential functions. It just meant that other people
could not use them in the same way when making the same type of
product as the patent holder.
I suspect that the RSA patent would be similar. Anyone can use
the functions that RSA uses for things other than a public key
cryptography system. It would only be the specific use that
would be covered by the patent.
Disclaimer: What do I know? I am just a person who read a book
that covered this. Consult a real lawyer before taking anything
I say seriously!
--
Tim Smith, Knowledgian {sdcrdcf,uunet}!ism780c!tim
tim@ism780c.isc.com
"Oh I wish I were Matthew Wiener, That is who I truly want to be,
'Cause if I were Matthew Wiener, Tim Maroney would send flames to me"shibumi@well.UUCP (09/20/87)
In article <7335@ism780c.UUCP> tim@ism780c.UUCP (Tim Smith) writes: >You can patent anything that you can convince the patent office to >issue you a patent for. The patent office will issue for almost anything that hasnt yet been invented and that meets the 'what can be patented' standard. The strength of your patent is almost always only determined through litigation. -- ! Kenton A. Hoover {hoptoad,hplabs,lll-lcc,ptsfa}!well!shibumi ! ! SNAIL: 1748 Clement Street ! ! Prescriptive Technology San Francisco, CA 94121 ! ! "Evil will always triumph over good because good is dumb!" !
rab@well.UUCP (Bob Bickford) (09/21/87)
Andy Freeman writes: >Michael Mauldin writes: >> o the general notion of using C = M^E mod pq >I believe that the patent covers the use of this equation for >a specific purpose. Patents protect applications of phenomena, >not the phenomena. The patent doesn't cover other uses of this >equation. >ps - The "pencil and paper" rule is bogus. Copiers are patentable. Specific copier technology is sometimes patentable. The idea of a copier is not. The use of reflected light in a copier is not patentable. Etc. You get the idea, I hope. Whether or not this rather ridiculous patent holds up in court, you may be sure that lots of people (myself included) are already using o the general notion of using C = M^E mod pq for our intellectual amusement, as well as occasional protection of data, for signatures, or whatever. -- Robert Bickford {hplabs, ucbvax, lll-lcc, ptsfa}!well!rab /-------------------------------------v-------------------------------------\ | Don't Blame Me: I Voted Libertarian | Ron Paul: Libertarian for President | \-------------------------------------^-------------------------------------/
tjt@lll-risky.arpa (Tim Tessin) (09/21/87)
In article <25@nl.cs.cmu.edu> mlm@nl.cs.cmu.edu (Michael Mauldin) writes: > > Several months ago I posted a request asking just what about RSA the > MIT patent covers. I got no answers. > Not wanting to spend the time or money to ask the patent office for a > copy of the patent, I hoped I could find out on the net. Does anyone > know specifically what the Patent was granted for/what they claimed? > > Michael L. Mauldin (Fuzzy) Well, I am having cracker-jack Government patent lawyers take a look at the RSA Patent. The patent grants some rights to the U.S. Government, so my answer may not be for everyone. I have a copy of the patent, but I can't really read it (you need a recursive descent parser to wade through some of the clauses :-)). They seem to be patenting the "implementation" of an algorithm for a specific purpose (cryptography). The example posted earlier on the use of exp() for feedback loops is probably very similar. I'll let ya'll know what I find out. 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
mjr@osiris.UUCP (Marcus J. Ranum) (09/22/87)
In article <1509@epimass.EPI.COM>, jbuck@epimass.EPI.COM (Joe Buck) writes: > > That was my point. The patent is no good unless the courts will > enforce it, and I suspect that the RSA patent will fall as soon as an > organization with sufficient legal resources decides to challenge it. > But don't try this at home if you don't want to spend time in court. Unless, of course, IBM, AT&T, the NSA or someone with hordes of lawyers decides to try to defend it. Hell, just anyone with enough money who decides to make a deal with R&S&A. Or is it just that my perception of reality is warped ?? -- 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
henry@utzoo.UUCP (Henry Spencer) (09/22/87)
> Whether or not this rather ridiculous patent holds up in court...
Why is it ridiculous? If one ignores the minutiae of US patent law for
the moment, RS&A clearly have produced an honest-to-God invention: a
useful idea that is neither obvious nor in the domain of natural law.
(Nature may have supplied the properties of the integers, but using them
for encryption is strictly a human concept.) They *should* be able to
patent it and have the patent hold up in court. Now, it's not clear that
they *can* under current patent law, but that's another issue. Is there
any reason for considering the idea "ridiculous" other than the
spoiled-brat desire to use their invention without paying royalties?
--
"There's a lot more to do in space | Henry Spencer @ U of Toronto Zoology
than sending people to Mars." --Bova | {allegra,ihnp4,decvax,utai}!utzoo!henryrab@well.UUCP (09/24/87)
In article <8640@utzoo.UUCP> henry@utzoo.UUCP (Henry Spencer) writes: + > Whether or not this rather ridiculous patent holds up in court... + + Why is it ridiculous? If one ignores the minutiae of US patent law for + the moment, RS&A clearly have produced an honest-to-God invention: a + useful idea that is neither obvious nor in the domain of natural law. + (Nature may have supplied the properties of the integers, but using them + for encryption is strictly a human concept.) They *should* be able to + patent it and have the patent hold up in court. Now, it's not clear that + they *can* under current patent law, but that's another issue. Is there + any reason for considering the idea "ridiculous" other than the + spoiled-brat desire to use their invention without paying royalties? All rudeness aside (the temptation is great.....), the point of the ongoing discussion here has been precisely the fact that the patent would appear to cover not just a single defineable invention but in fact an entire class of possible inventions, discovered or otherwise. It is on this basis that I described the patent as "ridiculous". Waiving (for the sake of discussion) the question of whether anyone can in fact patent an algorithm, and assuming (again, for the sake of discussion) that this patent did in fact cover a specific algorithm, then I for one would feel honor bound to respect it. (Not, by the way, because of any silly law, but because of my libertarian belief in the primacy of individual rights, which include the right(s) to intellectual property. But that's another subject.) However, this patent would appear to attempt to include any and all such algorithms, discovered or not, and for that reason I find it not deserving of the respect one would normally give toilet paper. By the way, I have noticed you several times use the phrase "spoiled brat" when arguing on the net. (Do you have children?) This is known as an 'ad hominem' attack. Don't bother; if we want to stoop to that sort of thing we can all go into conventional politics. -- Robert Bickford {hplabs, ucbvax, lll-lcc, ptsfa}!well!rab /-------------------------------------v-------------------------------------\ | Don't Blame Me: I Voted Libertarian | Ron Paul: Libertarian for President | \-------------------------------------^-------------------------------------/
andy@rocky.UUCP (09/25/87)
In article <4023@well.UUCP> rab@well.UUCP (Bob Bickford) writes: > All rudeness aside (the temptation is great.....), the point of the >ongoing discussion here has been precisely the fact that the patent would >appear to cover not just a single defineable invention but in fact an >entire class of possible inventions, discovered or otherwise. Since no one has bothered to actually look up the RSA patent to find out what is covered, various people on the net have assumed that what it covers supports their position. One possibility is that it is for the use of a certain integer function to encrypt digital information. Another possibility is that it is for one way to encrypt digital information using integer functions with certain properties. A third possibility is that it covers encryption of digital information using integer functions with certain properties. Bob's objection suggests that he thinks that the RSA patent is one of the latter two. > However, this patent would appear to attempt to include any >and all such algorithms, discovered or not, and for that reason I find it >not deserving of the respect one would normally give toilet paper. True, the broad patents described above don't list the integer functions, they merely describe them. I fail to see why this is objectionable. For example, let's say that the US patent office was open when the pulley was invented. Bob's like-minded ancestor would have objected to a pulley patent unless it covered only pulleys made out of materials the inventor mentioned. Many of the rest of us would settle for a description of the properties that the the pulley material must have. So Bob, what do you think the RSA patent covers? What do you think it would be legitimate for it to cover? -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
ks@a.cs.okstate.edu (Kurt F. Sauer) (09/25/87)
Please move this non-technical discussion of patent law away from sci.crypt. Thank you. Kurt F. Sauer Tulsa, OK
srt@duke.cs.duke.edu (Stephen R. Tate) (09/25/87)
In article <104@lll-risky.arpa> tjt@lll-risky.arpa.arpa (Tim Tessin) writes: > >They seem >to be patenting the "implementation" of an algorithm for a specific >purpose (cryptography). The example posted earlier on the use >of exp() for feedback loops is probably very similar. >I'll let ya'll know what I find out. > >Tim Tessin - Lawrence Livermore National Laboratory I mentioned before that I have a copy of a public key cryptosystem using RSA that has been released in the public domain. So how is this effected? One possible point is that the person who wrote it lives in Canada. Does this mean he doesn't have to abide by US Patents? How about importing such a thing into the US? Maybe the guy is just not aware that it is patented and should be notified? -- Steve Tate UUCP: ..!{ihnp4,decvax}!duke!srt CSNET: srt@duke ARPA: srt@cs.duke.edu "There ain't nothin' in the world that a T-Bone Shuffle won't cure."
devine@vianet.UUCP (Bob Devine) (09/25/87)
In article <615@rocky.STANFORD.EDU>, andy@rocky.STANFORD.EDU (Andy Freeman) writes: > Since no one has bothered to actually look up the RSA patent to find > out what is covered, various people on the net have assumed that what > it covers supports their position. [ I've added misc.legal to the distribution -- Bob] Well, since I couldn't get my hands on a copy of the patent quick enough to contribute to this discussion, I talked to someone who has read it. Philip Zimmerman wrote the IEEE Computer article last year about RSA. Since he lives within a local-call distance, I asked him about his take on the patent. His comments: 1. The patent does not cover an implementation (hardware nor software) of the RSA algorithm. 2. Many side issues are also listed in the patent. (eg. using 3 primes, bootstrapping into another algorithm) 3. It seemed to him that patenting the algorithm is like patenting a mathematical idea. [I agree. Remember folks, the patent test of "novel and unobvious" is easily passed when dealing with judges who were Poli-Sci majors. :-)] So, he concluded that a patent challenge would likely win. Now other points are with the patent process itself: while it is not totally clear, it looks like software is NOT patentable (but can be copyrighted easily enough) because the idea, per se, is in the underlying algorithm. Be careful in distinquishing between an algorithm and a process; the courts did but it seems rather artificial to me. If you read patents, many times they will show the idea manifested as a hardware device. I think even Ritchie's setuid idea used a hardware diagram. I conclude that a hardware version of RSA is definitely patentable but that pushing it to more than that is questionable. Now if RSA is patentable (patents are easily obtained) and stands up to challenges (RSA probably wouldn't), it still has to guard against infringement. And, oh lordy, there's been a ton o' infringement. It seems that everyone and their uncle has come up with their own implementation of RSA. RSA Inc. has not attempted to stop infringment (I haven't heard of any). So, it may fall like Ritchie's setuid patent because of non-enforcement. yet another non-lawyer, Bob Devine
tjt@lll-risky.arpa (Tim Tessin) (09/26/87)
In article <615@rocky.STANFORD.EDU> andy@rocky.UUCP (Andy Freeman) writes: > > Since no one has bothered to actually look up the RSA patent to find > out what is covered, various people on the net have assumed that what > it covers supports their position. One possibility is that it is for > the use of a certain integer function to encrypt digital information. > Another possibility is that it is for one way to encrypt digital information > using integer functions with certain properties. A third possibility is > that it covers encryption of digital information using integer functions > with certain properties. Bob's objection suggests that he thinks that the > RSA patent is one of the latter two. > ... > So Bob, what do you think the RSA patent covers? What do you think it > would be legitimate for it to cover? > > Andy Freeman Ok, here are the facts. Disclaimer: my description here of what our lawyers said may not fully render the legal opinion of the U.S. Government on this matter. First the patent itself: U.S. Patent # 4,405,829 Title: Cryptographic communications system and method Inventors: Rivest, Shamir, Adleman Assignee: Massachusetts Institute of Tech. Filed: Dec. 14, 1977 Granted: Sep. 20, 1983 40 Claims, 7 Drawing Figures Abstract: A cryptographic communications system and method. The system includes a communications channel coupled to at least one terminal having an encoding device and to at least one terminal having a decoding device. A message-to-be-transferred is enciphered to ciphertext at the encoding terminal by first encoding the message as a number M in a predetermined set, and then raising that number to a first predetermined power (associated with the intended receiver) and finally computing the remainder, or residue, C, when the exponentiated number is divided by the product of two predetermined prime numbers (associated with the intended receiver). The residue C is the ciphertext. The ciphertext is deciphered to the original message at the decoding terminal in a similar manner by raising the ciphertext to a second predetermined power (associated with the intended receiver), and then computing the residue, M', when the exponentiated ciphertext is divided by the product of the two predetermined prime numbers associated with the intended receier. The residue M' corresponds to the original encoded message M. There follows a detailed description of the math and examples are given. Then come the claims (which are the actual legal claims to which infringement protection is given). The claims basically state (there are 40 of them) that rendering this algorithm into hardware or rendering the specific methods to encrypt a message into an implementation (such as a software package), and combining them with a communications channel of any kind, is protected. Note the significance of the term METHOD. ANY methodical, repeatable use of the steps required to encrypt a message using the algorithm is protected! This means coding the RSA algorithm and combining it with a communications channel without an agreement with the RSA company is an infringment. 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. (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.) Of course, the burden of a patent infringment suit is on RSA. They must sue you to gain an infringment judgement. Do you feel lucky? You are free to use the math to provide any other product other than a cryptographic comunications system. Presumably, you could use the algorithm to encrypt files stored locally, as long as you didn't transmit them anywhere and have someone decrypt them (but this is not a legal opinion). Hope this clears things up a bit. (You Government sites, don't touch that dial! More to follow when it comes in.) 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
mjr@osiris.UUCP (Marcus J. Ranum) (09/27/87)
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
andy@rocky.UUCP (09/28/87)
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
mlm@nl.cs.cmu.edu.UUCP (09/28/87)
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
tjt@lll-risky.arpa (Tim Tessin) (09/28/87)
In article <10307@duke.cs.duke.edu> srt@duke.UUCP (Stephen R. Tate) writes: > > I mentioned before that I have a copy of a public key cryptosystem > using RSA that has been released in the public domain. So how is > this effected? One possible point is that the person who wrote it > lives in Canada. Does this mean he doesn't have to abide by US > Patents? How about importing such a thing into the US? Maybe the > guy is just not aware that it is patented and should be notified? Or he doesn't care. Legally, it is RSA's job to go after him and anyone using that "public domain" version. If they don't, then the patent rights can be challenged on the basis that they don't enforce them. What are the chances of getting caught if you are not distributing the stuff? Probably, close to zero. We have been advised by our legal staff to always go to the source of a "public domain" release and obtain the necessary information from the author to insure that the stuff is really "public domain" before we incorporate it into anything other than our own hacking. 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
jbn@glacier.STANFORD.EDU (John B. Nagle) (09/29/87)
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 Naglerab@well.UUCP (Bob Bickford) (09/29/87)
[Line eater? WHAT line ea
If you have information about the person who has released a public-domain
program that implements an algorithm similar to the RSA one, please send
me the info (or post it) on how to obtain a copy. BBS numbers, or
whatever.
--
Robert Bickford {hplabs, ucbvax, lll-lcc, ptsfa}!well!rab
/-------------------------------------v-------------------------------------\
| Don't Blame Me: I Voted Libertarian | Ron Paul: Libertarian for President |
\-------------------------------------^-------------------------------------/tjt@lll-risky.arpa (Tim Tessin) (09/29/87)
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
mitch@stride1.UUCP (09/30/87)
In article <107@lll-risky.arpa> tjt@lll-tis.arpa (Tim Tessin) writes: >In article <10307@duke.cs.duke.edu> srt@duke.UUCP (Stephen R. Tate) writes: >> >> Patents? How about importing such a thing into the US? Maybe the > >Or he doesn't care. Legally, it is RSA's job to go after him and anyone >using that "public domain" version. If they don't, then the patent rights >can be challenged on the basis that they don't enforce them. >What are the chances of getting caught if you are not distributing the >stuff? Probably, close to zero. We have been I expect that one of the characteristics of a "good" encryption scheme is that it is this side of impossible to demonstrate from the encrypted message which scheme was used to encrypt the original. Because of this difficulty I wonder if the patent holders of RSA could ever prosecute anyone for *using* RSA. That difficulty may prove an interesting point should someone try to take them to task for non-enforcement. Well, I think that the RSA patent holders need to get off their duff and get their invention out as a product. A lot of us would use it if priced in a reasonable way. Selling or advertising such a product is another topic. Thanks for the Soap. Thomas P. Mitchell (mitch@stride1.Stride.COM) Phone: (702) 322-6868 TWX: 910-395-6073 MicroSage Computer Systems Inc. a Division of Stride Micro. Opinions expressed are probably mine.
tjt@lll-risky.arpa (Tim Tessin) (10/01/87)
In article <683@stride.Stride.COM> (Thomas P. Mitchell) writes: > Well, I think that the RSA patent holders need to get off their > duff and get their invention out as a product. A lot of us would > use it if priced in a reasonable way. RSA based products are available from RSA Data Security (415-595-8782) for reasonable prices. They have two products, Mailsafe and BSAFE. Mailsafe is a product which sends encrypted electronic mail between PC's. BSAFE is the coded RSA algorithms in 'C'. My only objection to paying them lots of money is that if the Government already has rights to the stuff, I will only pay them a reasonable charge for the implementation, not for rights to use it. 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
mitch@stride1.UUCP (Thomas P. Mitchell) (10/05/87)
In article <109@lll-risky.arpa> tjt@lll-risky.arpa (Tim Tessin) writes: >In article <683@stride.Stride.COM> (Thomas P. Mitchell) writes: >> Well, I think that the RSA patent holders need to get off their >> duff and get their invention out as a product. A lot of us would >> use it if priced in a reasonable way. > >RSA based products are available from RSA Data Security >(415-595-8782) for reasonable prices. They have two products, >Mailsafe and BSAFE. Mailsafe is a >product which sends encrypted electronic mail between PC's. BSAFE >is the coded RSA algorithms in 'C'. Thanks Tim; I called and these are available for MS-DOS. They are not presently available for other environments, VAX or NCR machines (or ours Stride). With a pre-payment of royalties ($10,000) one could get the subroutine libraries (*.o files) for BSAFE. Then with the libraries one could set out to build some thing useful. None of which could be exported outside of the US without limiting the bit size of the keys and stripping out DES. >lots of money is that if the Government already has rights to the >stuff, I will only pay them a reasonable charge for the implementation, >not for rights to use it. Amen Perhaps we in this group are barking up the wrong tree. Rather than building a vault we might consider an envelope. Something not too tough but strong enough to keep the postman from reading the mail by holding it up to the light. If we use VAX hours as a standard measure of decryption difficulty I would consider 2-5 VAX hours per K bytes of message a good envelope. Thomas P. Mitchell (mitch@stride1.Stride.COM) Phone: (702) 322-6868 TWX: 910-395-6073 MicroSage Computer Systems Inc. a Division of Stride Micro. Opinions expressed are probably mine.
ljdickey@water.UUCP (10/14/87)
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