home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / crypt / 5878 < prev    next >
Encoding:
Internet Message Format  |  1992-12-21  |  1.8 KB
  1. Path: sparky!uunet!spool.mu.edu!uwm.edu!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!crabapple.srv.cs.cmu.edu!andrew.cmu.edu!<UNAUTHENTICATED>+
  2. From: Pat_Barron@transarc.com
  3. Newsgroups: sci.crypt
  4. Subject: Re: RSA questions
  5. Message-ID: <YfATb1f0Bwx2N93K0Z@transarc.com>
  6. Date: 18 Dec 92 06:18:09 GMT
  7. Article-I.D.: transarc.YfATb1f0Bwx2N93K0Z
  8. References: <PHR.92Dec14202839@napa.telebit.com>
  9.     <6gByVB5w164w@cellar.org>
  10. Organization: Carnegie Mellon, Pittsburgh, PA
  11. Lines: 30
  12. In-Reply-To: <6gByVB5w164w@cellar.org>
  13.  
  14. tsa@cellar.org (The Silent Assassin) writes:
  15. > > RSA works like this:
  16. > > 1. Pick two large primes p and q (with certain extra properties). Let N=pq.
  17. > 
  18. > What are the extra properties, and how large should they be to be reasonable
  19. > secure?
  20.  
  21. According to RSA's own info, the primes p and q were once recommended
  22. to be "strong" primes (a prime number p is "strong" if there are no
  23. large prime factors of (p-1) and (p+1)), but they claim that recent
  24. advances in factoring techniques have removed the advantages of using
  25. strong primes.  See the most excellent FAQ document, available for
  26. anonymous FTP from rsa.com, for mre details.
  27.  
  28. > > 2. Pick random exponent s.  The pair (N, s) will be the public key.
  29. > > 3. Compute secret key t, so that st = 1 mod (p-1)(q-1).  You can do
  30. > >    this efficiently if you know p and q, but it is intractable otherwise.
  31. > 
  32. > Huh?  1 mod x =x, correct?  That is. modulus is the remainder of integer
  33. > division, and when you take 1 and mod it, you will always have a remainder
  34. > equal to your original.
  35.  
  36. This confused me the first dozen times I read it, too.
  37.  
  38. The idea is not to compute t such that st = (1 mod (p-1)(q-1)).  You
  39. compute t such that st = 1, when taken mod (p-1)(q-1).  That's the
  40. definition of a multiplicative inverse.  The problem in the
  41. description is simply one of unclear terminology.
  42.  
  43. --Pat.
  44.