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);

}