These are the real meat of the LUC vs RSA discussion that went on in sci.crypt in Dec 1992 when the DDJ article came out. (Amazing how all the "information" in this thread really boils down to a few sentences) - mch Newsgroups: sci.crypt Path: van-bc!cs.ubc.ca!utcsri!torn!cs.utexas.edu!sdd.hp.com!spool.mu.edu!agate!linus!linus.mitre.org!gauss!bs From: bs@gauss.mitre.org (Robert D. Silverman) Subject: Re: LUC Public-key Encryption Message-ID: <1992Dec11.171631.26834@linus.mitre.org> Sender: news@linus.mitre.org (News Service) Nntp-Posting-Host: gauss.mitre.org Organization: Research Computer Facility, MITRE Corporation, Bedford, MA References: <1992Dec11.134309.29150@msuinfo.cl.msu.edu> Date: Fri, 11 Dec 1992 17:16:31 GMT Lines: 32 In article <1992Dec11.134309.29150@msuinfo.cl.msu.edu> mrr@scss3.cl.msu.edu (Mark Riordan) writes: >The January 1993 issue of Dr. Dobb's Journal has an article by >Peter Smith on a new public-key encryption algorithm called LUC. >This algorithm, based on "Lucas sequences", resembles RSA in >that it involves modular arithmetic based on N, the product of two >large primes, and a second number, e. > >A Lucas sequence, V[i](P,Q), is defined as follows. P is the message This is nothing new. A 'Lucas Sequence' is nothing more than a disguised way of doing exponentiation in the twisted sub-group of a finite field with p^2 elements. This is the sub-group that has order p+1, as opposed to p-1, which is the group that RSA is based upon. This has been well known for a long time among number theorists. >The author, who is also the inventor of the LUC algorithm, While I won't cry 'plagiarism', since the author may be unaware of prior developments, for him to claim to be the 'inventor' is bogus at best. It is NOT new. >Not surprisingly, the author is attempting to patent the system >and is looking for people to license it to. A provisional patent He should not be able to patent this, since what he has done was all known before. -- Bob Silverman These are my opinions and not MITRE's. Mitre Corporation, Bedford, MA 01730 "You can lead a horse's ass to knowledge, but you can't make him think" Newsgroups: sci.crypt Path: van-bc!cs.ubc.ca!destroyer!gatech!usenet.ins.cwru.edu!agate!linus!linus.mitre.org!gauss!bs From: bs@gauss.mitre.org (Robert D. Silverman) Subject: Re: Are Lucas sequences an alternative to RSA? Message-ID: <1992Dec29.003035.10678@linus.mitre.org> Sender: news@linus.mitre.org (News Service) Nntp-Posting-Host: gauss.mitre.org Organization: Research Computer Facility, MITRE Corporation, Bedford, MA References: Date: Tue, 29 Dec 1992 00:30:35 GMT Lines: 41 In article jensen@aplcomm.jhuapl.edu (Robert Jensen) writes: :The January 1993 Dr. Dobb's contains a description of the use of :Lucas sequences as an alternative to RSA for public key encryption. :I seem to recall a previous assertion in this group that the :Lucas sequence system is just a disquised RSA. I don't recall any :details of the assertion or any follow up discussion. Does anyone have :an opinion on this alternative? The advertised advantage is that the :encrypted product of two messages is not the product of the individually :encrypted messages. This beats at least one attack on RSA. This last assertion is not correct. The same type of attack will (when possible) defeat the Lucas method as well. I was the one who posted the opinion. I did not say that using Lucas sequences was a disguised form of RSA. Rather it is a disguised form of discrete logs. And the "product" of two messages is the product of individual messages if one interprets "product" correctly. Once more, Using Lucas sequences is essentially the discrete logarithm method for the sub-field (or sub-group) of GF(p^2) that has order p+1. This is known as the twisted group (or field). Multiplication within this sub-field or sub-group is not ordinary multiplication mod N, but is rather a composition which amounts to adding the indices of two elements in a Lucas sequence. That is to say, if A_h and A_j are two elements in this sequence, then their "product" is A_(h+j). Exponentiation in this sub-field is done by appropriate compositions using the Lucas sequence, whereas exponentiation for RSA is done via modular multiplication. The "new" method appears to be valid, but it is well known among number theorists and cryptographers. It amounts to the discrete log problem for a PARTICULAR sub-field of a finite field. -- Bob Silverman These are my opinions and not MITRE's. Mitre Corporation, Bedford, MA 01730