🚀 go-pugleaf

In article <Bzzp1F.MEy@netnews.jhuapl.edu> 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
"You can lead a horse's ass to knowledge, but you can't make him think"