home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / sci / crypt / 6249 < prev    next >
Encoding:
Text File  |  1992-12-29  |  2.5 KB  |  54 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!darwin.sura.net!paladin.american.edu!gatech!usenet.ins.cwru.edu!agate!linus!linus.mitre.org!gauss!bs
  3. From: bs@gauss.mitre.org (Robert D. Silverman)
  4. Subject: Re: Are Lucas sequences an alternative to RSA?
  5. Message-ID: <1992Dec29.003035.10678@linus.mitre.org>
  6. Sender: news@linus.mitre.org (News Service)
  7. Nntp-Posting-Host: gauss.mitre.org
  8. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  9. References: <Bzzp1F.MEy@netnews.jhuapl.edu>
  10. Date: Tue, 29 Dec 1992 00:30:35 GMT
  11. Lines: 41
  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.  Does anyone have
  19. :an opinion on this alternative?  The advertised advantage is that the
  20. :encrypted product of two messages is not the product of the individually
  21. :encrypted messages.  This beats at least one attack on RSA.
  22.  
  23. This last assertion is not correct. The same type of attack will (when
  24. possible) defeat the Lucas method as well.
  25.  
  26. I was the one who posted the opinion. I did not say that using Lucas
  27. sequences was a disguised form of RSA. Rather it is a disguised form
  28. of discrete logs. And the "product" of two messages is the product of
  29. individual messages if one interprets "product" correctly.
  30.  
  31. Once more, 
  32.  
  33. Using Lucas sequences is essentially the discrete logarithm method
  34. for the sub-field (or sub-group) of GF(p^2) that has order p+1.
  35. This is known as the twisted group (or field). Multiplication 
  36. within this sub-field or sub-group is not ordinary multiplication mod N,
  37. but is rather a composition which amounts to adding the indices of
  38. two elements in a Lucas sequence. That is to say, if A_h and A_j are
  39. two elements in this sequence, then their "product" is A_(h+j).
  40.  
  41. Exponentiation in this sub-field is done by appropriate compositions
  42. using the Lucas sequence, whereas exponentiation for RSA is done via
  43. modular multiplication.
  44.  
  45. The "new" method appears to be valid, but it is well known among
  46. number theorists and cryptographers. It amounts to the discrete log
  47. problem for a PARTICULAR sub-field of a finite field.
  48.  
  49. --
  50. Bob Silverman
  51. These are my opinions and not MITRE's.
  52. Mitre Corporation, Bedford, MA 01730
  53. "You can lead a horse's ass to knowledge, but you can't make him think"
  54.