home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / sci / crypt / 6247 < prev    next >
Encoding:
Text File  |  1992-12-29  |  2.9 KB  |  66 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!spool.mu.edu!agate!usenet.ins.cwru.edu!gatech!swrinde!cs.utexas.edu!torn!nott!uotcsi2!news
  3. From: cbbrowne@csi.uottawa.ca (Christopher Browne)
  4. Subject: Re: Are Lucas sequences an alternative to RSA?
  5. Message-ID: <1992Dec29.001512.12943@csi.uottawa.ca>
  6. Sender: news@csi.uottawa.ca
  7. Nntp-Posting-Host: prge
  8. Organization: Dept. of Computer Science, University of Ottawa
  9. References: <Bzzp1F.MEy@netnews.jhuapl.edu>
  10. Date: Tue, 29 Dec 92 00:15:12 GMT
  11. Lines: 53
  12.  
  13. In article <Bzzp1F.MEy@netnews.jhuapl.edu> jensen@aplcomm.jhuapl.edu (Robert Jensen) writes:
  14. >The January 1993 Dr. Dobb's contains a description of the use of
  15. >Lucas sequences as an alternative to RSA for public key encryption.
  16. >I seem to recall a previous assertion in this group that the
  17. >Lucas sequence system is just a disquised RSA.  I don't recall any
  18. >details of the assertion or any follow up discussion.  
  19.  
  20. I don't remember hearing such an assertion.
  21.  
  22. >Does anyone have an opinion on this alternative?  
  23.  
  24. My opinion is divided; it looks like it's SLIGHTLY stronger than RSA,
  25. but not fundamentally so.
  26.  
  27. >The advertised advantage is that the
  28. >encrypted product of two messages is not the product of the individually
  29. >encrypted messages.  This beats at least one attack on RSA.
  30.  
  31. It beats ONE attack on a naive implementation of an RSA message
  32. protocol.
  33.  
  34. However, from what I can tell, only a stupid implementation would be
  35. particularly susceptible to such an attack.
  36.  
  37. It's been said time and time again here that it's not JUST the
  38. encryption algorithm that's important; the WHOLE messaging system has
  39. got to be strong.  And with even a half-hearted set of messaging
  40. protocols, the attack shouldn't be effective.  All you need do is add
  41. some random salt (or an MD5 signature) to the message before
  42. re-encrypting, and the weakness is covered.
  43.  
  44. The "problem" with the Lucas system, from what I can tell, is that
  45. it's not evident that it's FUNDAMENTALLY stronger than RSA.  It still
  46. stands or falls based on the assumption that it is very difficult to
  47. factor the product of two enormous prime numbers.
  48.  
  49. I would have been much more excited if LUC involved some OTHER
  50. hard-to-reverse operation rather than prime factoring.
  51.  
  52. Supposing some prime-factoring algorithm comes out next week that
  53. kills RSA, LUC would become similarly useless.  I don't foresee such
  54. an algorithm coming, but certainly it WOULD kill 'em both.
  55.  
  56. I'd like to see other more fundamental advantages to LUC; there was a
  57. claim in the article that it might be faster than RSA, which would
  58. qualify.  There might be other advantages that make it harder to
  59. break.  I'd love to hear about it.
  60.  
  61. -- 
  62. Christopher Browne                |     PGP 2.0 key available
  63. cbbrowne@csi.uottawa.ca           |======================================
  64. University of Ottawa              | Genius may have its limitations, but
  65. Master of System Science Program  | stupidity is not thus handicapped.
  66.