home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / crypt / 7052 < prev    next >
Encoding:
Internet Message Format  |  1993-01-21  |  2.9 KB
  1. Xref: sparky sci.crypt:7052 sci.math:18557
  2. Newsgroups: sci.crypt,sci.math
  3. Path: sparky!uunet!usc!sdd.hp.com!nigel.msen.com!fmsrl7!lynx.unm.edu!umn.edu!csus.edu!netcom.com!rcain
  4. From: rcain@netcom.com (Robert Cain)
  5. Subject: Re: RSA cracked? I don't think so..., HUGE primes?
  6. Message-ID: <1993Jan21.070521.9787@netcom.com>
  7. Organization: Netcom - Online Communication Services  (408 241-9760 guest) 
  8. References: <1993Jan20.231041.4691@zip.eecs.umich.edu>
  9. Distribution: na
  10. Date: Thu, 21 Jan 1993 07:05:21 GMT
  11. Lines: 52
  12.  
  13. gilgalad@quip.eecs.umich.edu (Ralph Seguin) writes:
  14. : A friend of mine posessing a masters in mathematics said that he had heard
  15. : and saw a flyer in his local math dept that RSA had been cracked.  I told
  16.  
  17. Could this flyer be obtained?
  18.  
  19. : him that I thought that this was a load of bunk.  We got into a heated
  20. : discussion and he claimed that methods of factoring large composites had
  21. : been developed that were several orders of magnitude faster than older
  22. : methods.  I told him that this was irrelevant, since you  could generated
  23. : arbitrarily large composites to form your key.  Even going 12 orders of
  24. : magnitude faster (1 trillion times faster), it could still take easily
  25. : several billion years to factor some of the smaller sized keys.  The
  26. : question that I have is: am I completely wrong here (ie, have I stuck
  27. : my foot and a good portion of my leg in my mouth ;) ?  Personally, I feel
  28.  
  29. If in fact there was a fundamental breakthrough in factoring it could make
  30. the size of the composite irrelevant but I am sure we would know about
  31. that.
  32.  
  33. : that the NSA posted that flyer to get people to refrain from using something
  34. : they are unable to crack ;>
  35.  
  36. Not even the NSA is that stupid (I hope :-)
  37.  
  38. : 
  39. : My second question is:  what is the best means available for generating
  40. : truly huge primes (200+ digits)?  Fermat and Mercene (sp?) numbers
  41. : are NOT secure.
  42.  
  43. Generating big random numbers and then testing them probabilistically for
  44. primality.  Sounds crude but it works.  The density of primes up in the 
  45. range desired is higher than intuition would lead one to believe.  I think
  46. that 100 attempts is larger than what is encountered on the average (and
  47. I'll be corrected if not :-)  The probibalistic test can be iterated
  48. for an arbitrarilarily high theoretical probability that one is prime.
  49. Well, I know that one is prime, you understand what I mean. :-)
  50.  
  51. I am less sure of this but I think that if the probabilistic test for
  52. primality actually yields a composite then the product of this with a
  53. real prime is about as hard to factor as a two prime composite.  The
  54. probability of getting two such composites is exceedingly small.
  55.  
  56. Bob
  57. -- 
  58. Bob Cain    rcain@netcom.com   408-358-2007
  59.  
  60.     'The meek shall inherit the earth--the rest of us will move on..'
  61.                                                     Sameer Parekh
  62.  
  63.  
  64.                PGP 1.0 or 2.0 public key available on request.
  65.