home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / alt / hackers / 1342 < prev    next >
Encoding:
Internet Message Format  |  1992-08-31  |  1.4 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!att!dptg!ulysses!ulysses.att.com!smb
  2. From: smb@ulysses.att.com (Steven Bellovin)
  3. Newsgroups: alt.hackers
  4. Subject: Re: Prime Number Generator
  5. Message-ID: <17166@ulysses.att.com>
  6. Date: 31 Aug 92 22:33:27 GMT
  7. References: <grtyj5-@rpi.edu> <1992Aug31.160225.26724@gateway.novell.com>
  8. Sender: netnews@ulysses.att.com
  9. Lines: 22
  10. Approved: xyzzy@plugh.cave.org
  11.  
  12. In article <1992Aug31.160225.26724@gateway.novell.com>, alex@otis (The Console 
  13. DJ) writes:
  14. > Someone correct me if I am wrong but the whole idea behind the encryption is
  15. > the large prime numbers are difficult to  calulate??? Actually there should
  16. > be no known algorithm (except brute force try every number thingy).
  17.  
  18. OK, you're wrong...  Generating large prime numbers is quite easy -- one
  19. generates random odd numbers, does a few trial divisions, then applies
  20. as many iterations as desired of probabilistic prime number generators.
  21. The Sieve of Erastosthenes or exhaustive division trials would take far
  22. too long for numbers of cryptographic interest, which are several hundred
  23. bits long, at the very least.
  24.  
  25. The hard problems are things like factoring large numbers, or calculating
  26. discrete logarithms in finite fields.  If you're interested in the subject,
  27. read sci.crypt for a while.  Or read some books or papers on the subject.
  28. The book I recommend is Davies and Prices's ``Security for Computer
  29. Networks''.
  30.  
  31.  
  32.         --Steve Bellovin
  33.  
  34.