Convert test_mod_exp and test_mod_exp_consttime.

Honestly, with this size of number, they're pretty bad test vectors.
test_mod_exp_mont5 will be imported in the next commit which should help.

This was done by taking test_mod_exp's generation, running it a few times
(since otherwise the modulus is always the same). I also ran it a few times
with the odd constraint removed since BN_mod_exp is supposed to support it,
even if it's not actually useful.

BUG=31

Change-Id: Id53953f0544123a5ea71efac534946055dd5aabc
Reviewed-on: https://boringssl-review.googlesource.com/8610
Reviewed-by: David Benjamin <davidben@google.com>
diff --git a/crypto/bn/bn_test.cc b/crypto/bn/bn_test.cc
index bdd5ff0..f2a33ec 100644
--- a/crypto/bn/bn_test.cc
+++ b/crypto/bn/bn_test.cc
@@ -100,8 +100,6 @@
 
 static int rand_neg();
 
-static bool test_mod_exp(FILE *fp, BN_CTX *ctx);
-static bool test_mod_exp_mont_consttime(FILE *fp, BN_CTX *ctx);
 static bool test_exp(FILE *fp, BN_CTX *ctx);
 static bool test_mod_sqrt(FILE *fp, BN_CTX *ctx);
 static bool test_mod_exp_mont5(FILE *fp, BN_CTX *ctx);
@@ -174,15 +172,8 @@
                          "| grep -v 0 */\n");
   puts_fp(bc_file.get(), "obase=16\nibase=16\n");
 
-  message(bc_file.get(), "BN_mod_exp");
-  if (!test_mod_exp(bc_file.get(), ctx.get())) {
-    return 1;
-  }
-  flush_fp(bc_file.get());
-
   message(bc_file.get(), "BN_mod_exp_mont_consttime");
-  if (!test_mod_exp_mont_consttime(bc_file.get(), ctx.get()) ||
-      !test_mod_exp_mont5(bc_file.get(), ctx.get())) {
+  if (!test_mod_exp_mont5(bc_file.get(), ctx.get())) {
     return 1;
   }
   flush_fp(bc_file.get());
@@ -635,6 +626,37 @@
   return true;
 }
 
+static bool TestModExp(FileTest *t, BN_CTX *ctx) {
+  ScopedBIGNUM a = GetBIGNUM(t, "A");
+  ScopedBIGNUM e = GetBIGNUM(t, "E");
+  ScopedBIGNUM m = GetBIGNUM(t, "M");
+  ScopedBIGNUM mod_exp = GetBIGNUM(t, "ModExp");
+  if (!a || !e || !m || !mod_exp) {
+    return false;
+  }
+
+  ScopedBIGNUM ret(BN_new());
+  if (!ret ||
+      !BN_mod_exp(ret.get(), a.get(), e.get(), m.get(), ctx) ||
+      !ExpectBIGNUMsEqual(t, "A ^ E (mod M)", mod_exp.get(), ret.get())) {
+    return false;
+  }
+
+  if (BN_is_odd(m.get())) {
+    if (!BN_mod_exp_mont(ret.get(), a.get(), e.get(), m.get(), ctx, NULL) ||
+        !ExpectBIGNUMsEqual(t, "A ^ E (mod M) (Montgomery)", mod_exp.get(),
+                            ret.get()) ||
+        !BN_mod_exp_mont_consttime(ret.get(), a.get(), e.get(), m.get(), ctx,
+                                   NULL) ||
+        !ExpectBIGNUMsEqual(t, "A ^ E (mod M) (constant-time)", mod_exp.get(),
+                            ret.get())) {
+      return false;
+    }
+  }
+
+  return true;
+}
+
 struct Test {
   const char *name;
   bool (*func)(FileTest *t, BN_CTX *ctx);
@@ -649,6 +671,7 @@
     {"Product", TestProduct},
     {"Quotient", TestQuotient},
     {"ModMul", TestModMul},
+    {"ModExp", TestModExp},
 };
 
 static bool RunTest(FileTest *t, void *arg) {
@@ -670,114 +693,6 @@
   return sign[(neg++) % 8];
 }
 
-static bool test_mod_exp(FILE *fp, BN_CTX *ctx) {
-  ScopedBIGNUM a(BN_new());
-  ScopedBIGNUM b(BN_new());
-  ScopedBIGNUM c(BN_new());
-  ScopedBIGNUM d(BN_new());
-  ScopedBIGNUM e(BN_new());
-  if (!a || !b || !c || !d || !e) {
-    return false;
-  }
-
-  if (!BN_rand(c.get(), 30, 0, 1)) {  // must be odd for montgomery
-    return false;
-  }
-  for (int i = 0; i < num2; i++) {
-    if (!BN_rand(a.get(), 20 + i * 5, 0, 0) ||
-        !BN_rand(b.get(), 2 + i, 0, 0) ||
-        !BN_mod_exp(d.get(), a.get(), b.get(), c.get(), ctx)) {
-      return false;
-    }
-
-    if (fp != NULL) {
-      BN_print_fp(fp, a.get());
-      puts_fp(fp, " ^ ");
-      BN_print_fp(fp, b.get());
-      puts_fp(fp, " % ");
-      BN_print_fp(fp, c.get());
-      puts_fp(fp, " - ");
-      BN_print_fp(fp, d.get());
-      puts_fp(fp, "\n");
-    }
-    if (!BN_exp(e.get(), a.get(), b.get(), ctx) ||
-        !BN_sub(e.get(), e.get(), d.get()) ||
-        !BN_div(a.get(), b.get(), e.get(), c.get(), ctx)) {
-      return false;
-    }
-    if (!BN_is_zero(b.get())) {
-      fprintf(stderr, "Modulo exponentiation test failed!\n");
-      return false;
-    }
-  }
-
-   // Regression test for carry propagation bug in sqr8x_reduction.
-  if (!HexToBIGNUM(&a, "050505050505") ||
-      !HexToBIGNUM(&b, "02") ||
-      !HexToBIGNUM(
-          &c,
-          "4141414141414141414141274141414141414141414141414141414141414141"
-          "4141414141414141414141414141414141414141414141414141414141414141"
-          "4141414141414141414141800000000000000000000000000000000000000000"
-          "0000000000000000000000000000000000000000000000000000000000000000"
-          "0000000000000000000000000000000000000000000000000000000000000000"
-          "0000000000000000000000000000000000000000000000000000000001") ||
-      !BN_mod_exp(d.get(), a.get(), b.get(), c.get(), ctx) ||
-      !BN_mul(e.get(), a.get(), a.get(), ctx)) {
-    return false;
-  }
-  if (BN_cmp(d.get(), e.get()) != 0) {
-    fprintf(stderr, "BN_mod_exp and BN_mul produce different results!\n");
-    return false;
-  }
-
-  return true;
-}
-
-static bool test_mod_exp_mont_consttime(FILE *fp, BN_CTX *ctx) {
-  ScopedBIGNUM a(BN_new());
-  ScopedBIGNUM b(BN_new());
-  ScopedBIGNUM c(BN_new());
-  ScopedBIGNUM d(BN_new());
-  ScopedBIGNUM e(BN_new());
-  if (!a || !b || !c || !d || !e) {
-    return false;
-  }
-
-  if (!BN_rand(c.get(), 30, 0, 1)) {  // must be odd for montgomery
-    return false;
-  }
-  for (int i = 0; i < num2; i++) {
-    if (!BN_rand(a.get(), 20 + i * 5, 0, 0) ||
-        !BN_rand(b.get(), 2 + i, 0, 0) ||
-        !BN_mod_exp_mont_consttime(d.get(), a.get(), b.get(), c.get(), ctx,
-                                   NULL)) {
-      return false;
-    }
-
-    if (fp != NULL) {
-      BN_print_fp(fp, a.get());
-      puts_fp(fp, " ^ ");
-      BN_print_fp(fp, b.get());
-      puts_fp(fp, " % ");
-      BN_print_fp(fp, c.get());
-      puts_fp(fp, " - ");
-      BN_print_fp(fp, d.get());
-      puts_fp(fp, "\n");
-    }
-    if (!BN_exp(e.get(), a.get(), b.get(), ctx) ||
-        !BN_sub(e.get(), e.get(), d.get()) ||
-        !BN_div(a.get(), b.get(), e.get(), c.get(), ctx)) {
-      return false;
-    }
-    if (!BN_is_zero(b.get())) {
-      fprintf(stderr, "Modulo exponentiation test failed!\n");
-      return false;
-    }
-  }
-  return true;
-}
-
 // Test constant-time modular exponentiation with 1024-bit inputs,
 // which on x86_64 cause a different code branch to be taken.
 static bool test_mod_exp_mont5(FILE *fp, BN_CTX *ctx) {
diff --git a/crypto/bn/bn_tests.txt b/crypto/bn/bn_tests.txt
index 0d353d9..d99e1bd 100644
--- a/crypto/bn/bn_tests.txt
+++ b/crypto/bn/bn_tests.txt
@@ -9714,3 +9714,264 @@
 A = ca6c51ba2f410d09bf71d60fe
 B = 8bdfa8fe5ef3b2ad02bc63c4d
 M = 84daecf412b8c50ad6dfdb546c3eb783dcc6f32003eda914bb
+
+
+# ModExp tests.
+#
+# These test vectors satisfy A ^ E = ModExp (mod M) and 0 <= ModExp < M.
+
+# Regression test for carry propagation bug in sqr8x_reduction.
+ModExp = 19324b647d967d644b3219
+A = 050505050505
+E = 02
+M = 414141414141414141414127414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
+
+ModExp = 208f8aa0
+A = 86b49
+E = 2
+M = 30d26ecb
+
+ModExp = 27308229
+A = 17591bb
+E = 6
+M = 30d26ecb
+
+ModExp = 2bdf498f
+A = 21292626
+E = d
+M = 30d26ecb
+
+ModExp = 11317167
+A = 4a655df24
+E = 10
+M = 30d26ecb
+
+ModExp = 2e1b88e
+A = da6b761a86
+E = 35
+M = 30d26ecb
+
+ModExp = 20a12ec3
+A = ea811
+E = 2
+M = 23bc042f
+
+ModExp = c42ced
+A = 1011a6a
+E = 4
+M = 23bc042f
+
+ModExp = 4637d79
+A = 28d9a601
+E = 8
+M = 23bc042f
+
+ModExp = 20e5669b
+A = 72fe6bc20
+E = 11
+M = 23bc042f
+
+ModExp = 142ab9e3
+A = 9a07b9363c
+E = 29
+M = 23bc042f
+
+ModExp = 14c64646
+A = 822df
+E = 3
+M = 30915765
+
+ModExp = 160e35a2
+A = 15ea542
+E = 5
+M = 30915765
+
+ModExp = 2f23a488
+A = 34d2e02e
+E = e
+M = 30915765
+
+ModExp = 28e67f93
+A = 636a32703
+E = 14
+M = 30915765
+
+ModExp = 29bfeaa5
+A = c8646998e6
+E = 2c
+M = 30915765
+
+ModExp = 30959e22
+A = 81dad
+E = 3
+M = 326dd68d
+
+ModExp = 1a1da4fa
+A = 116adb9
+E = 5
+M = 326dd68d
+
+ModExp = 272bf0d8
+A = 2d21ef08
+E = 8
+M = 326dd68d
+
+ModExp = 29f5054b
+A = 76989850a
+E = 16
+M = 326dd68d
+
+ModExp = e6c7b77
+A = b88ee70d2a
+E = 3e
+M = 326dd68d
+
+ModExp = 369605e1
+A = cf26f
+E = 2
+M = 3ce082eb
+
+ModExp = 168a3c5d
+A = 1f82caf
+E = 5
+M = 3ce082eb
+
+ModExp = 125c4bb8
+A = 2e9c4c07
+E = 9
+M = 3ce082eb
+
+ModExp = 1c5fe761
+A = 523ab37f1
+E = 14
+M = 3ce082eb
+
+ModExp = 21703009
+A = dc832165e8
+E = 20
+M = 3ce082eb
+
+ModExp = 1228d1e
+A = a5555
+E = 3
+M = 24665b27
+
+ModExp = 5226af4
+A = 1077bd6
+E = 4
+M = 24665b27
+
+ModExp = 1b14eac1
+A = 2db3a834
+E = f
+M = 24665b27
+
+ModExp = 161727bc
+A = 6bd962cb6
+E = 19
+M = 24665b27
+
+ModExp = 10d61d0d
+A = c10caed407
+E = 28
+M = 24665b27
+
+ModExp = 233da406
+A = b125f
+E = 3
+M = 33509981
+
+ModExp = 24032799
+A = 1656b7c
+E = 6
+M = 33509981
+
+ModExp = 129ecebe
+A = 2e671504
+E = a
+M = 33509981
+
+ModExp = 20c20bac
+A = 4d7a2de44
+E = 1f
+M = 33509981
+
+ModExp = 2e3ce9d3
+A = c53b3def4d
+E = 31
+M = 33509981
+
+ModExp = 12fadfd6
+A = b4cf8
+E = 2
+M = 36e9d4ae
+
+ModExp = 457ac85
+A = 1b1c7e9
+E = 7
+M = 36e9d4ae
+
+ModExp = 31debef4
+A = 3a973028
+E = d
+M = 36e9d4ae
+
+ModExp = 2333ad93
+A = 552b97c45
+E = 11
+M = 36e9d4ae
+
+ModExp = 99ba1fb
+A = 8bfb949cbb
+E = 28
+M = 36e9d4ae
+
+ModExp = 27b691de
+A = 93492
+E = 3
+M = 298fdb16
+
+ModExp = 3c2b70f
+A = 14e7b0d
+E = 4
+M = 298fdb16
+
+ModExp = 1486cda7
+A = 29acff81
+E = c
+M = 298fdb16
+
+ModExp = 11725275
+A = 507489205
+E = 13
+M = 298fdb16
+
+ModExp = 24d14627
+A = e71c55606d
+E = 35
+M = 298fdb16
+
+ModExp = 222b8d14
+A = 9b1a0
+E = 3
+M = 3db59d12
+
+ModExp = 3b8bd47d
+A = 13f4e8d
+E = 7
+M = 3db59d12
+
+ModExp = 17e72356
+A = 334774ce
+E = a
+M = 3db59d12
+
+ModExp = 306447ca
+A = 47079ddd2
+E = 12
+M = 3db59d12
+
+ModExp = 90bef3b
+A = a75d62616d
+E = 37
+M = 3db59d12
diff --git a/crypto/bn/check_bn_tests.go b/crypto/bn/check_bn_tests.go
index 9e710d8..d49c2b7 100644
--- a/crypto/bn/check_bn_tests.go
+++ b/crypto/bn/check_bn_tests.go
@@ -217,6 +217,11 @@
 				r = r.Mod(r, test.Values["M"])
 				checkResult(test, "A * B (mod M)", "ModMul", r)
 			}
+		case "ModExp":
+			if checkKeys(test, "A", "E", "M", "ModExp") {
+				r := new(big.Int).Exp(test.Values["A"], test.Values["E"], test.Values["M"])
+				checkResult(test, "A ^ E (mod M)", "ModExp", r)
+			}
 		default:
 			fmt.Fprintf(os.Stderr, "Line %d: unknown test type %q.\n", test.LineNumber, test.Type)
 		}