home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / crypt / 5967 < prev    next >
Encoding:
Internet Message Format  |  1992-12-21  |  2.0 KB

  1. Path: sparky!uunet!noc.near.net!hri.com!spool.mu.edu!darwin.sura.net!mlb.semi.harris.com!rtfm.mlb.fl.us!luckey
  2. From: luckey@rtfm.mlb.fl.us (Jon Luckey)
  3. Newsgroups: sci.crypt
  4. Subject: Re: More RSA questions
  5. Message-ID: <1992Dec20.182659.7848@rtfm.mlb.fl.us>
  6. Date: 20 Dec 92 18:26:59 GMT
  7. References: <AfATsxL0Bwx2F93KFX@transarc.com>
  8. Organization: We don't need no stinkin' batches!
  9. Lines: 40
  10.  
  11. Pat_Barron@transarc.com writes:
  12.  
  13. >I was tinkering around with the RSA algorithm last night, using really
  14. >small primes (e.g., 13 and 17) to generate keys.  The idea was that I
  15. >only wanted to use a 16-bit modulus, so I could avoid doing any
  16. >extended precision arithmetic, and so I could do the exponentation via
  17. >a naive "compute x^y by looping and multiplying by x, y times
  18. >(remember, this is just a toy implementation, and it's not intended
  19. >to do any "real" work).  But I ran into a few snags:
  20.  
  21. >1)  During the exponentiation, the numbers get *really* big.  Like, I
  22. >was shocked at how quickly they got big.  Is there any shortcut for
  23. >computing m^e mod n, without actually computing m^e first?  Like, can
  24. >I loop somehow, accumulating partial results, until at the end I have
  25. >the value m^e mod n, without having actually computed m^e first?  Even
  26. >if I choose, say, 3 or 5 as the private key, the public exponent tends
  27. >to be big enough that m^e is way beyond the capacity of a 32-bit
  28. >unsigned integer.
  29.  
  30. > [another RSA question ommitted]
  31.  
  32. There are already a few replies to your message giving better
  33. ways to calculate z=x^y mod n.  But if all you want to do is simply
  34. modify your original program, keeping your brute force expotentiation
  35. method, then just do a modulus after each multiply.
  36.  
  37. I.E change your code that looks like
  38.  
  39.       Z:=1;
  40.       FOR I:= 1 TO Y DO Z:= Z*X;
  41.  
  42. into
  43.       Z:=1;
  44.       FOR I:= 1 TO Y DO Z:= (Z*X) MOD N;
  45.  
  46. which will keep you from running into interactions with the implict
  47. modulo that computer interger arithmatic involves.
  48.  
  49. you might even be able to stay within 16 bit integers and not have to
  50. worry about 32 bits at all.
  51.