When searching for a prime, the number of Miller-Rabin tests to be

performed will be done in accordance with a table published in the
Handbook of Applied Cryptography.  See Bug 65151.  Also, changes to
test program for this function.

3 files changed, 27 insertions, 9 deletions

diff --git a/security/nss/lib/freebl/mpi/Makefile.win b/security/nss/lib/freebl/mpi/Makefile.win
index bc75dcaed..1c403f4d3 100644
--- a/security/nss/lib/freebl/mpi/Makefile.win
+++ b/security/nss/lib/freebl/mpi/Makefile.win
@@ -181,6 +181,8 @@ mpi.lib: $(LIBOBJS)
 	ar -cvr mpi.lib $(LIBOBJS)
 	$(RANLIB) mpi.lib
 
+lib libs: mpi.lib
+
 #---------------------------------------
 
 MPTESTOBJS = mptest1.obj mptest2.obj mptest3.obj mptest3a.obj mptest4.obj \
@@ -252,8 +254,8 @@ doc:
 	(cd doc; ./build)
 
 clean:
-	rm -f *.obj *.lib *.pdb
-	rm -f utils/*.obj
+	rm -f *.obj *.lib *.pdb *.ilk
+	cd utils; rm -f *.obj *.lib *.pdb *.ilk
 
 distclean: clean
 	rm -f mptest? mpi-test metime mulsqr karatsuba
diff --git a/security/nss/lib/freebl/mpi/mpprime.c b/security/nss/lib/freebl/mpi/mpprime.c
index c7eaef08c..7e30b24bd 100644
--- a/security/nss/lib/freebl/mpi/mpprime.c
+++ b/security/nss/lib/freebl/mpi/mpprime.c
@@ -443,14 +443,31 @@ mp_err mpp_make_prime(mp_int *start, mp_size nBits, mp_size strong,
   MP_DIGITS(&q) = 0;
   MP_CHECKOK( mp_init(&trial) );
   MP_CHECKOK( mp_init(&q)     );
-  if (nBits >= 1024) {
+  /* values taken from table 4.4, HandBook of Applied Cryptography */
+  if (nBits >= 1300) {
+    num_tests = 2;
+  } else if (nBits >= 850) {
+    num_tests = 3;
+  } else if (nBits >= 650) {
+    num_tests = 4;
+  } else if (nBits >= 550) {
     num_tests = 5;
-  } else if (nBits >= 512) {
+  } else if (nBits >= 450) {
+    num_tests = 6;
+  } else if (nBits >= 400) {
     num_tests = 7;
-  } else if (nBits >= 384) {
+  } else if (nBits >= 350) {
+    num_tests = 8;
+  } else if (nBits >= 300) {
     num_tests = 9;
-  } else if (nBits >= 256) {
-    num_tests = 13;
+  } else if (nBits >= 250) {
+    num_tests = 12;
+  } else if (nBits >= 200) {
+    num_tests = 15;
+  } else if (nBits >= 150) {
+    num_tests = 18;
+  } else if (nBits >= 100) {
+    num_tests = 27;
   } else
     num_tests = 50;
 
diff --git a/security/nss/lib/freebl/mpi/utils/primegen.c b/security/nss/lib/freebl/mpi/utils/primegen.c
index 77b986dc9..1f7a593e1 100644
--- a/security/nss/lib/freebl/mpi/utils/primegen.c
+++ b/security/nss/lib/freebl/mpi/utils/primegen.c
@@ -172,8 +172,7 @@ int main(int argc, char *argv[])
       break;
     }
     FPUTC('\n', stderr);
-    printf("After %d tests, the following value is still probably prime:\n",
-	   NUM_TESTS);
+    puts("The following value is probably prime:");
     outlen = mp_radix_size(&testval, 10);
     out = calloc(outlen, sizeof(unsigned char));
     mp_toradix(&testval, (char *)out, 10);