🚀 go-pugleaf

In article <avalon.712399566@coombs>, avalon@coombs.anu.edu.au (Darren Reed) writes:
>Hi, I've been looking at implementing RSA encrpytion and have found that
>generating the initial keys is a somewhat tricky.  The only algorithm
>I have found for generation the public key is:

[find large primes x and y]
>N = x*y
>p*s mod (x-1)(y-1) = 1
>
>and solve for p. :(
>
>Is there an easy way to solve this problem ?

p*s = 1 + c * (x-1) * (y-1)

Pick a value for c other than zero.

You are now solving for p and s.  Try to factor 1 + c * (x-1) * (y-1). You
don't have to factor it completely, just enough so that p and s are  both
large (greater than N ** 0.33333, for example).  If you can't, start over
with a different c.

I know this algorithm will work, but I cannot guarantee that it will be 
cryptographically strong.

Here's a better one.  I haven't taken the time to understand it myself; it's
from Phillip Zimmermann's PGP.  Context:  p=x, q=y, e=p, d=s.

First find a small e which has no factors in common with (p-1)*(q-1).
Then use inv(d, e, (p-1)*(q-1)) below to find d.  

void inv(unitptr x,unitptr a,unitptr n)
    /* Euclid's algorithm extended to compute multiplicative inverse.
       Computes x such that a*x mod n = 1, where 0<a<n */
{
    /*    The variable u is unnecessary for the algorithm, but is 
        included in comments for mathematical clarity. 
    */
    short i;
    unit y[MAX_UNIT_PRECISION], temp[MAX_UNIT_PRECISION];
    unit gcopies[3][MAX_UNIT_PRECISION], vcopies[3][MAX_UNIT_PRECISION];
#define g(i) (  &(gcopies[i][0])  )
#define v(i) (  &(vcopies[i][0])  )
/*    unit ucopies[3][MAX_UNIT_PRECISION]; */
/* #define u(i) (  &(ucopies[i][0])  ) */
    mp_move(g(0),n); mp_move(g(1),a);
/*    mp_init(u(0),1); mp_init(u(1),0); */
    mp_init(v(0),0); mp_init(v(1),1);
    i=1;
    while (testne(g(i),0))
    {    /* we know that at this point,  g(i) = u(i)*n + v(i)*a  */    
        mp_udiv( g(iplus1), y, g(iminus1), g(i) );
        mp_mult(temp,y,v(i)); mp_move(v(iplus1),v(iminus1)); mp_sub(v(iplus1),temp);
    /*    mp_mult(temp,y,u(i)); mp_move(u(iplus1),u(iminus1)); mp_sub(u(iplus1),temp); */
        i = iplus1;
    }
    mp_move(x,v(iminus1));
    if (mp_tstminus(x))
        mp_add(x,n);
    mp_burn(g(iminus1));    /* burn the evidence on the stack...*/
    mp_burn(g(iplus1));
    mp_burn(v(0));
    mp_burn(v(1));
    mp_burn(v(2));
    mp_burn(y);
    mp_burn(temp);
#undef g
#undef v
}    /* inv */

Keith Lewis             klewis@mitre.org          "Mr. Cheap"
I don't dance to music; music dances to me.  Email me for my corrected PGP key.
The above may not (yet) represent the opinions of my employer.