home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / crypt / 2776 < prev    next >
Encoding:
Text File  |  1992-07-29  |  3.1 KB  |  86 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!cis.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!agate!linus!linus.mitre.org!news
  3. From: lewis@aera8700.mitre.org (Keith Lewis)
  4. Subject: Re: RSA Public Key Generations.
  5. Message-ID: <1992Jul29.200956.23672@linus.mitre.org>
  6. Sender: news@linus.mitre.org (News Service)
  7. Nntp-Posting-Host: aera8700.mitre.org
  8. Organization: The MITRE Corporation
  9. References:   <avalon.712399566@coombs>
  10. Date: Wed, 29 Jul 1992 20:09:56 GMT
  11. Lines: 73
  12.  
  13. In article <avalon.712399566@coombs>, avalon@coombs.anu.edu.au (Darren Reed) writes:
  14. >Hi, I've been looking at implementing RSA encrpytion and have found that
  15. >generating the initial keys is a somewhat tricky.  The only algorithm
  16. >I have found for generation the public key is:
  17.  
  18. [find large primes x and y]
  19. >N = x*y
  20. >p*s mod (x-1)(y-1) = 1
  21. >
  22. >and solve for p. :(
  23. >
  24. >Is there an easy way to solve this problem ?
  25.  
  26. p*s = 1 + c * (x-1) * (y-1)
  27.  
  28. Pick a value for c other than zero.
  29.  
  30. You are now solving for p and s.  Try to factor 1 + c * (x-1) * (y-1). You
  31. don't have to factor it completely, just enough so that p and s are  both
  32. large (greater than N ** 0.33333, for example).  If you can't, start over
  33. with a different c.
  34.  
  35. I know this algorithm will work, but I cannot guarantee that it will be 
  36. cryptographically strong.
  37.  
  38. Here's a better one.  I haven't taken the time to understand it myself; it's
  39. from Phillip Zimmermann's PGP.  Context:  p=x, q=y, e=p, d=s.
  40.  
  41. First find a small e which has no factors in common with (p-1)*(q-1).
  42. Then use inv(d, e, (p-1)*(q-1)) below to find d.  
  43.  
  44. void inv(unitptr x,unitptr a,unitptr n)
  45.     /* Euclid's algorithm extended to compute multiplicative inverse.
  46.        Computes x such that a*x mod n = 1, where 0<a<n */
  47. {
  48.     /*    The variable u is unnecessary for the algorithm, but is 
  49.         included in comments for mathematical clarity. 
  50.     */
  51.     short i;
  52.     unit y[MAX_UNIT_PRECISION], temp[MAX_UNIT_PRECISION];
  53.     unit gcopies[3][MAX_UNIT_PRECISION], vcopies[3][MAX_UNIT_PRECISION];
  54. #define g(i) (  &(gcopies[i][0])  )
  55. #define v(i) (  &(vcopies[i][0])  )
  56. /*    unit ucopies[3][MAX_UNIT_PRECISION]; */
  57. /* #define u(i) (  &(ucopies[i][0])  ) */
  58.     mp_move(g(0),n); mp_move(g(1),a);
  59. /*    mp_init(u(0),1); mp_init(u(1),0); */
  60.     mp_init(v(0),0); mp_init(v(1),1);
  61.     i=1;
  62.     while (testne(g(i),0))
  63.     {    /* we know that at this point,  g(i) = u(i)*n + v(i)*a  */    
  64.         mp_udiv( g(iplus1), y, g(iminus1), g(i) );
  65.         mp_mult(temp,y,v(i)); mp_move(v(iplus1),v(iminus1)); mp_sub(v(iplus1),temp);
  66.     /*    mp_mult(temp,y,u(i)); mp_move(u(iplus1),u(iminus1)); mp_sub(u(iplus1),temp); */
  67.         i = iplus1;
  68.     }
  69.     mp_move(x,v(iminus1));
  70.     if (mp_tstminus(x))
  71.         mp_add(x,n);
  72.     mp_burn(g(iminus1));    /* burn the evidence on the stack...*/
  73.     mp_burn(g(iplus1));
  74.     mp_burn(v(0));
  75.     mp_burn(v(1));
  76.     mp_burn(v(2));
  77.     mp_burn(y);
  78.     mp_burn(temp);
  79. #undef g
  80. #undef v
  81. }    /* inv */
  82.  
  83. Keith Lewis             klewis@mitre.org          "Mr. Cheap"
  84. I don't dance to music; music dances to me.  Email me for my corrected PGP key.
  85. The above may not (yet) represent the opinions of my employer.
  86.