home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / sci / crypt / 6043 < prev    next >
Encoding:
Text File  |  1992-12-22  |  2.1 KB  |  48 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!ira.uka.de!chx400!bernina!neptune!nugget.inf.ethz.ch!marti
  3. From: marti@nugget.inf.ethz.ch (Robert Marti)
  4. Subject: Re: More RSA questions
  5. Message-ID: <1992Dec22.162354.26642@neptune.inf.ethz.ch>
  6. Sender: news@neptune.inf.ethz.ch (Mr News)
  7. Nntp-Posting-Host: nugget.inf.ethz.ch
  8. Organization: Dept. Informatik, Swiss Federal Institute of Technology (ETH), Zurich, CH
  9. References:  <AfATsxL0Bwx2F93KFX@transarc.com>
  10. Date: Tue, 22 Dec 1992 16:23:54 GMT
  11. Lines: 35
  12.  
  13. In article <AfATsxL0Bwx2F93KFX@transarc.com>, Pat_Barron@transarc.com writes:
  14. |> I was tinkering around with the RSA algorithm last night [...]
  15. |> 
  16. |> 1)  During the exponentiation, the numbers get *really* big.  Like, I
  17. |> was shocked at how quickly they got big.  Is there any shortcut for
  18. |> computing m^e mod n, without actually computing m^e first?
  19.  
  20. Yes.  Do the mod operations after each "round" (iteration or recursion)
  21. in your exponentiation algorithm.  See procedure expmod in SICP (*),
  22. page 47.
  23.  
  24.  
  25. |> 2)  I chose the private key and public exponent by brute force.  Is
  26. |> a better way to choose the private key than to factor (p-1)(q-1) and
  27. |> choose something with no common factors?
  28.  
  29. Since factoring is _expensive_ for large (p-1)(q-1), you're better off
  30. by generating a random integer e in some suitable range, say the range
  31. of all the integers which have one digit less than (p-1)(q-1), and then
  32. increment e until the gcd of e and (p-1)(q-1) is 1.  An implementation
  33. of gcd can be found in SICP (*), page 44.
  34.  
  35.     SICP:  Structure and Interpretation of Computer Programs.
  36.     By H. Abelson and G. Sussman.  MIT Press, 1985.
  37.  
  38. This is a great introductory book on computer programming.  It uses a
  39. nice little Lisp dialect called Scheme. All Scheme implementations I
  40. know support bignums, so you wouldn't even have to worry about the
  41. size of your integers.
  42.  
  43. -- 
  44. Robert Marti                    |  Phone:    +41 1 254 72 60
  45. Informationssysteme             |  FAX:      +41 1 262 39 73
  46. ETH-Zentrum                     |  E-Mail:   marti@inf.ethz.ch
  47. CH-8092 Zurich, Switzerland     |
  48.