home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / crypt / 5962 < prev    next >
Encoding:
Text File  |  1992-12-21  |  2.1 KB  |  47 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!uwm.edu!linac!att!mcdchg!chinet!schneier
  3. From: schneier@chinet.chi.il.us (Bruce Schneier)
  4. Subject: Re: More RSA questions
  5. Message-ID: <BzJn50.GK0@chinet.chi.il.us>
  6. Organization: Chinet - Public Access UNIX
  7. References: <AfATsxL0Bwx2F93KFX@transarc.com>
  8. Date: Sun, 20 Dec 1992 05:55:47 GMT
  9. Lines: 36
  10.  
  11. In article <AfATsxL0Bwx2F93KFX@transarc.com> Pat_Barron@transarc.com writes:
  12. >I was tinkering around with the RSA algorithm last night, using really
  13. >small primes (e.g., 13 and 17) to generate keys.  The idea was that I
  14. >only wanted to use a 16-bit modulus, so I could avoid doing any
  15. >extended precision arithmetic, and so I could do the exponentation via
  16. >a naive "compute x^y by looping and multiplying by x, y times
  17. >(remember, this is just a toy implementation, and it's not intended
  18. >to do any "real" work).  But I ran into a few snags:
  19. >
  20. >1)  During the exponentiation, the numbers get *really* big.  Like, I
  21. >was shocked at how quickly they got big.  Is there any shortcut for
  22. >computing m^e mod n, without actually computing m^e first?  Like, can
  23. >I loop somehow, accumulating partial results, until at the end I have
  24. >the value m^e mod n, without having actually computed m^e first?  Even
  25. >if I choose, say, 3 or 5 as the private key, the public exponent tends
  26. >to be big enough that m^e is way beyond the capacity of a 32-bit
  27. >unsigned integer.
  28. >
  29. Take the modulus after each multiplication, not once after you are finished
  30. with all the multiplications i the exponentiation.
  31.  
  32. >2)  I chose the private key and public exponent by brute force.  Is
  33. >a better way to choose the private key than to factor (p-1)(q-1) and
  34. >choose something with no common factors?  Is there a better way to
  35. >find the public exponent than just trying all the possible values
  36. >until you find it (which is what I did)?
  37. >
  38. Use Euclid's algorithm; it's easy.
  39.  
  40. I have a suggestion.  I wrote an article in the May 92 issue of Dr. Dobbs
  41. Journal about public-key cryptography.  It discusses how to do RSA.  There's
  42. one realy irritating typo in the second column of page 26, but other than
  43. that the article gives a good description of how RsA works.
  44.  
  45. Bruce
  46.  
  47.