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