home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / crypt / 5883 < prev    next >
Encoding:
Internet Message Format  |  1992-12-21  |  1.7 KB
  1. Path: sparky!uunet!cs.utexas.edu!zaphod.mps.ohio-state.edu!swrinde!emory!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: More RSA questions
  5. Message-ID: <AfATsxL0Bwx2F93KFX@transarc.com>
  6. Date: 18 Dec 92 06:37:17 GMT
  7. Article-I.D.: transarc.AfATsxL0Bwx2F93KFX
  8. Organization: Carnegie Mellon, Pittsburgh, PA
  9. Lines: 24
  10.  
  11. I was tinkering around with the RSA algorithm last night, using really
  12. small primes (e.g., 13 and 17) to generate keys.  The idea was that I
  13. only wanted to use a 16-bit modulus, so I could avoid doing any
  14. extended precision arithmetic, and so I could do the exponentation via
  15. a naive "compute x^y by looping and multiplying by x, y times
  16. (remember, this is just a toy implementation, and it's not intended
  17. to do any "real" work).  But I ran into a few snags:
  18.  
  19. 1)  During the exponentiation, the numbers get *really* big.  Like, I
  20. was shocked at how quickly they got big.  Is there any shortcut for
  21. computing m^e mod n, without actually computing m^e first?  Like, can
  22. I loop somehow, accumulating partial results, until at the end I have
  23. the value m^e mod n, without having actually computed m^e first?  Even
  24. if I choose, say, 3 or 5 as the private key, the public exponent tends
  25. to be big enough that m^e is way beyond the capacity of a 32-bit
  26. unsigned integer.
  27.  
  28. 2)  I chose the private key and public exponent by brute force.  Is
  29. a better way to choose the private key than to factor (p-1)(q-1) and
  30. choose something with no common factors?  Is there a better way to
  31. find the public exponent than just trying all the possible values
  32. until you find it (which is what I did)?
  33.  
  34. --Pat.
  35.