20060303a

1 files changed, 36 insertions, 0 deletions

diff --git a/libsec/port/gensafeprime.c b/libsec/port/gensafeprime.c
new file mode 100644
index 00000000..e95c94c9
--- /dev/null
+++ b/libsec/port/gensafeprime.c
@@ -0,0 +1,36 @@
+#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);
+}