home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / crypt / 5938 < prev    next >
Encoding:
Text File  |  1992-12-21  |  1.9 KB  |  49 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!telebit!phr
  3. From: phr@telebit.com (Paul Rubin)
  4. Subject: Re: More RSA questions
  5. In-Reply-To: Pat_Barron@transarc.com's message of 18 Dec 92 06:37:17 GMT
  6. Message-ID: <PHR.92Dec18183513@napa.telebit.com>
  7. Sender: news@telebit.com
  8. Nntp-Posting-Host: napa.telebit.com
  9. Organization: Telebit Corporation; Sunnyvale, CA, USA
  10. References: <AfATsxL0Bwx2F93KFX@transarc.com>
  11. Date: 18 Dec 92 18:35:13
  12. Lines: 35
  13.  
  14. In article <AfATsxL0Bwx2F93KFX@transarc.com> Pat_Barron@transarc.com writes:
  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?  Like, can
  19.    I loop somehow, accumulating partial results, until at the end I have
  20.    the value m^e mod n, without having actually computed m^e first?  Even
  21.    if I choose, say, 3 or 5 as the private key, the public exponent tends
  22.    to be big enough that m^e is way beyond the capacity of a 32-bit
  23.    unsigned integer.
  24.  
  25. Compute m^e mod n by repeated squaring and multiplication mod n.
  26. Here is pseudo-C for it (warning, this routine may infringe RSA patent :-) )
  27.    
  28. int expmod (int x, int s, int n)  /* compute x^s mod n */
  29. {
  30.    int p;
  31.    if (s == 0) return 1;
  32.    p = expmod (x, s/2, n); /* an efficient version wouldn't recurse */
  33.    p = p * p;
  34.    if (s % 2 == 1) 
  35.     p *= x;
  36.    return p % n;
  37. }
  38.  
  39.    2)  I chose the private key and public exponent by brute force.  Is
  40.    a better way to choose the private key than to factor (p-1)(q-1) and
  41.    choose something with no common factors?  Is there a better way to
  42.    find the public exponent than just trying all the possible values
  43.    until you find it (which is what I did)?
  44.  
  45. The public exponent should just be a random number between 3 and the modulus.
  46.  
  47. To tell if A and B have common factors, you don't have to factor either
  48. A or B.  Just use the Euclidean GCD algorithm, which is very efficient.
  49.