Subversion Repositories planix.SVN

#include "os.h"
#include <mp.h>
#include <libsec.h>

// find a prime p of length n and a generator alpha of Z^*_p
// Alg 4.86 Menezes et al () Handbook, p.164
void
gensafeprime(mpint *p, mpint *alpha, int n, int accuracy)
{
        mpint *q, *b;

        q = mpnew(n-1);
        while(1){
                genprime(q, n-1, accuracy);
                mpleft(q, 1, p);
                mpadd(p, mpone, p); // p = 2*q+1
                if(probably_prime(p, accuracy))
                        break;
        }
        // now find a generator alpha of the multiplicative
        // group Z*_p of order p-1=2q
        b = mpnew(0);
        while(1){
                mprand(n, genrandom, alpha);
                mpmod(alpha, p, alpha);
                mpmul(alpha, alpha, b);
                mpmod(b, p, b);
                if(mpcmp(b, mpone) == 0)
                        continue;
                mpexp(alpha, q, p, b);
                if(mpcmp(b, mpone) != 0)
                        break;
        }
        mpfree(b);
        mpfree(q);
}