🚀 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.  

I don't remember hearing such an assertion.

>Does anyone have an opinion on this alternative?  

My opinion is divided; it looks like it's SLIGHTLY stronger than RSA,
but not fundamentally so.

>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.

It beats ONE attack on a naive implementation of an RSA message
protocol.

However, from what I can tell, only a stupid implementation would be
particularly susceptible to such an attack.

It's been said time and time again here that it's not JUST the
encryption algorithm that's important; the WHOLE messaging system has
got to be strong.  And with even a half-hearted set of messaging
protocols, the attack shouldn't be effective.  All you need do is add
some random salt (or an MD5 signature) to the message before
re-encrypting, and the weakness is covered.

The "problem" with the Lucas system, from what I can tell, is that
it's not evident that it's FUNDAMENTALLY stronger than RSA.  It still
stands or falls based on the assumption that it is very difficult to
factor the product of two enormous prime numbers.

I would have been much more excited if LUC involved some OTHER
hard-to-reverse operation rather than prime factoring.

Supposing some prime-factoring algorithm comes out next week that
kills RSA, LUC would become similarly useless.  I don't foresee such
an algorithm coming, but certainly it WOULD kill 'em both.

I'd like to see other more fundamental advantages to LUC; there was a
claim in the article that it might be faster than RSA, which would
qualify.  There might be other advantages that make it harder to
break.  I'd love to hear about it.

-- 
Christopher Browne                |     PGP 2.0 key available
cbbrowne@csi.uottawa.ca           |======================================
University of Ottawa              | Genius may have its limitations, but
Master of System Science Program  | stupidity is not thus handicapped.