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