home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / crypt / 7146 < prev    next >
Encoding:
Internet Message Format  |  1993-01-25  |  1.8 KB
  1. Path: sparky!uunet!olivea!decwrl!waikato.ac.nz!aukuni.ac.nz!mike-l.cs.aukuni.ac.nz!user
  2. From: m_lennon@cs.auckland.ac.nz (Mike Lennon)
  3. Newsgroups: sci.crypt
  4. Subject: LUC vs RSA
  5. Message-ID: <m_lennon-260193122101@mike-l.cs.aukuni.ac.nz>
  6. Date: 25 Jan 93 23:40:25 GMT
  7. Sender: news@ccu1.aukuni.ac.nz (News Owner)
  8. Followup-To: sci.crypt
  9. Organization: Computer Science Dept
  10. Lines: 25
  11. Nntp-Posting-Host: mike-l.cs.aukuni.ac.nz
  12.  
  13. The Dr Dobbs article claims that LUC is stronger than RSA.  In fact we now
  14. have "proof" of that claim, in the sense that we have worked out a way
  15. (actually refined an old way - we're well aware that this type of attack is
  16. well known) to forge RSA signatures, using just public information.  The
  17. basic method is to factorise a message just before it's signed (i.e. after
  18. the hashing algorithm has been applied), then recover the signatures of the
  19. prime factors by using an elimination method on factorised random messages.
  20.  Unfortunately with a 512 bit key it all takes too many lifetimes to be
  21. feasible in "general", but it becomes at least capable of consideration if
  22. :
  23. * The message is hashed to a short (eg 128-bit) block.
  24. * Either the number 3 is used as the RSA encryption exponent,
  25. * Or there is a Notary Public you can use which signs things that are
  26. obtained from the message in a predictable way (eg hashing or addition of
  27. time stamp).
  28.  
  29. The interesting thing is that hashing is no protection whatsoever - it
  30. makes things simpler for the first stage (in practice, by reducing the size
  31. of the message to factorise), and it doesn't stop the Notary Public attack
  32. because the thing which the N.P. signs is obtained predictably from the
  33. message sent to it.
  34.  
  35. Because factorising LUC signatures does not get you anywhere (the
  36. signatures of the factors are no use at all), LUC can continue to be used
  37. with short signature blocks, exponent 3, and simple Notary Publics. 
  38.