Add "small" variants of Montgomery logic.
These use the square and multiply functions added earlier.
Change-Id: I723834f9a227a9983b752504a2d7ce0223c43d24
Reviewed-on: https://boringssl-review.googlesource.com/23070
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/bn/bn_test.cc b/crypto/fipsmodule/bn/bn_test.cc
index 7376989..d2a875b 100644
--- a/crypto/fipsmodule/bn/bn_test.cc
+++ b/crypto/fipsmodule/bn/bn_test.cc
@@ -542,15 +542,39 @@
ASSERT_TRUE(a_tmp);
ASSERT_TRUE(b_tmp);
ASSERT_TRUE(BN_MONT_CTX_set(mont.get(), m.get(), ctx));
- ASSERT_TRUE(BN_nnmod(a_tmp.get(), a.get(), m.get(), ctx));
- ASSERT_TRUE(BN_nnmod(b_tmp.get(), b.get(), m.get(), ctx));
- ASSERT_TRUE(BN_to_montgomery(a_tmp.get(), a_tmp.get(), mont.get(), ctx));
- ASSERT_TRUE(BN_to_montgomery(b_tmp.get(), b_tmp.get(), mont.get(), ctx));
+ ASSERT_TRUE(BN_nnmod(a.get(), a.get(), m.get(), ctx));
+ ASSERT_TRUE(BN_nnmod(b.get(), b.get(), m.get(), ctx));
+ ASSERT_TRUE(BN_to_montgomery(a_tmp.get(), a.get(), mont.get(), ctx));
+ ASSERT_TRUE(BN_to_montgomery(b_tmp.get(), b.get(), mont.get(), ctx));
ASSERT_TRUE(BN_mod_mul_montgomery(ret.get(), a_tmp.get(), b_tmp.get(),
mont.get(), ctx));
ASSERT_TRUE(BN_from_montgomery(ret.get(), ret.get(), mont.get(), ctx));
EXPECT_BIGNUMS_EQUAL("A * B (mod M) (Montgomery)", mod_mul.get(),
ret.get());
+
+#if !defined(BORINGSSL_SHARED_LIBRARY)
+ if (m->top <= BN_SMALL_MAX_WORDS) {
+ std::unique_ptr<BN_ULONG[]> a_words(new BN_ULONG[m->top]),
+ b_words(new BN_ULONG[m->top]), r_words(new BN_ULONG[m->top]);
+ OPENSSL_memset(a_words.get(), 0, m->top * sizeof(BN_ULONG));
+ OPENSSL_memcpy(a_words.get(), a->d, a->top * sizeof(BN_ULONG));
+ OPENSSL_memset(b_words.get(), 0, m->top * sizeof(BN_ULONG));
+ OPENSSL_memcpy(b_words.get(), b->d, b->top * sizeof(BN_ULONG));
+ ASSERT_TRUE(bn_to_montgomery_small(a_words.get(), m->top, a_words.get(),
+ m->top, mont.get()));
+ ASSERT_TRUE(bn_to_montgomery_small(b_words.get(), m->top, b_words.get(),
+ m->top, mont.get()));
+ ASSERT_TRUE(bn_mod_mul_montgomery_small(
+ r_words.get(), m->top, a_words.get(), m->top, b_words.get(), m->top,
+ mont.get()));
+ // Use the second half of |tmp| so ASan will catch out-of-bounds writes.
+ ASSERT_TRUE(bn_from_montgomery_small(r_words.get(), m->top, r_words.get(),
+ m->top, mont.get()));
+ ASSERT_TRUE(bn_set_words(ret.get(), r_words.get(), m->top));
+ EXPECT_BIGNUMS_EQUAL("A * B (mod M) (Montgomery, words)", mod_mul.get(),
+ ret.get());
+ }
+#endif
}
}
@@ -581,8 +605,8 @@
ASSERT_TRUE(mont);
ASSERT_TRUE(a_tmp);
ASSERT_TRUE(BN_MONT_CTX_set(mont.get(), m.get(), ctx));
- ASSERT_TRUE(BN_nnmod(a_tmp.get(), a.get(), m.get(), ctx));
- ASSERT_TRUE(BN_to_montgomery(a_tmp.get(), a_tmp.get(), mont.get(), ctx));
+ ASSERT_TRUE(BN_nnmod(a.get(), a.get(), m.get(), ctx));
+ ASSERT_TRUE(BN_to_montgomery(a_tmp.get(), a.get(), mont.get(), ctx));
ASSERT_TRUE(BN_mod_mul_montgomery(ret.get(), a_tmp.get(), a_tmp.get(),
mont.get(), ctx));
ASSERT_TRUE(BN_from_montgomery(ret.get(), ret.get(), mont.get(), ctx));
@@ -596,6 +620,38 @@
ASSERT_TRUE(BN_from_montgomery(ret.get(), ret.get(), mont.get(), ctx));
EXPECT_BIGNUMS_EQUAL("A * A_copy (mod M) (Montgomery)", mod_square.get(),
ret.get());
+
+#if !defined(BORINGSSL_SHARED_LIBRARY)
+ if (m->top <= BN_SMALL_MAX_WORDS) {
+ std::unique_ptr<BN_ULONG[]> a_words(new BN_ULONG[m->top]),
+ a_copy_words(new BN_ULONG[m->top]), r_words(new BN_ULONG[m->top]);
+ OPENSSL_memset(a_words.get(), 0, m->top * sizeof(BN_ULONG));
+ OPENSSL_memcpy(a_words.get(), a->d, a->top * sizeof(BN_ULONG));
+ ASSERT_TRUE(bn_to_montgomery_small(a_words.get(), m->top, a_words.get(),
+ m->top, mont.get()));
+ ASSERT_TRUE(bn_mod_mul_montgomery_small(
+ r_words.get(), m->top, a_words.get(), m->top, a_words.get(), m->top,
+ mont.get()));
+ ASSERT_TRUE(bn_from_montgomery_small(r_words.get(), m->top, r_words.get(),
+ m->top, mont.get()));
+ ASSERT_TRUE(bn_set_words(ret.get(), r_words.get(), m->top));
+ EXPECT_BIGNUMS_EQUAL("A * A (mod M) (Montgomery, words)",
+ mod_square.get(), ret.get());
+
+ // Repeat the operation with |a_copy_words|.
+ OPENSSL_memcpy(a_copy_words.get(), a_words.get(),
+ m->top * sizeof(BN_ULONG));
+ ASSERT_TRUE(bn_mod_mul_montgomery_small(
+ r_words.get(), m->top, a_words.get(), m->top, a_copy_words.get(),
+ m->top, mont.get()));
+ // Use the second half of |tmp| so ASan will catch out-of-bounds writes.
+ ASSERT_TRUE(bn_from_montgomery_small(r_words.get(), m->top, r_words.get(),
+ m->top, mont.get()));
+ ASSERT_TRUE(bn_set_words(ret.get(), r_words.get(), m->top));
+ EXPECT_BIGNUMS_EQUAL("A * A_copy (mod M) (Montgomery, words)",
+ mod_square.get(), ret.get());
+ }
+#endif
}
}
diff --git a/crypto/fipsmodule/bn/internal.h b/crypto/fipsmodule/bn/internal.h
index 634435f..2f5dbbb 100644
--- a/crypto/fipsmodule/bn/internal.h
+++ b/crypto/fipsmodule/bn/internal.h
@@ -335,6 +335,38 @@
// one on success and zero on programmer error.
int bn_sqr_small(BN_ULONG *r, size_t num_r, const BN_ULONG *a, size_t num_a);
+// In the following functions, the modulus must be at most |BN_SMALL_MAX_WORDS|
+// words long.
+
+// bn_to_montgomery_small sets |r| to |a| translated to the Montgomery domain.
+// |num_a| and |num_r| must be the length of the modulus, which is
+// |mont->N.top|. |a| must be fully reduced. This function returns one on
+// success and zero if lengths are inconsistent. |r| and |a| may alias.
+int bn_to_montgomery_small(BN_ULONG *r, size_t num_r, const BN_ULONG *a,
+ size_t num_a, const BN_MONT_CTX *mont);
+
+// bn_from_montgomery_small sets |r| to |a| translated out of the Montgomery
+// domain. |num_r| must be the length of the modulus, which is |mont->N.top|.
+// |a| must be at most |mont->N.top| * R and |num_a| must be at most 2 *
+// |mont->N.top|. This function returns one on success and zero if lengths are
+// inconsistent. |r| and |a| may alias.
+int bn_from_montgomery_small(BN_ULONG *r, size_t num_r, const BN_ULONG *a,
+ size_t num_a, const BN_MONT_CTX *mont);
+
+// bn_mod_mul_montgomery_small sets |r| to |a| * |b| mod |mont->N|. Both inputs
+// and outputs are in the Montgomery domain. |num_r| must be the length of the
+// modulus, which is |mont->N.top|. This function returns one on success and
+// zero on internal error or inconsistent lengths. Any two of |r|, |a|, and |b|
+// may alias.
+//
+// This function requires |a| * |b| < N * R, where N is the modulus and R is the
+// Montgomery divisor, 2^(N.top * BN_BITS2). This should generally be satisfied
+// by ensuring |a| and |b| are fully reduced, however ECDSA has one computation
+// which requires the more general bound.
+int bn_mod_mul_montgomery_small(BN_ULONG *r, size_t num_r, const BN_ULONG *a,
+ size_t num_a, const BN_ULONG *b, size_t num_b,
+ const BN_MONT_CTX *mont);
+
#if defined(__cplusplus)
} // extern C
diff --git a/crypto/fipsmodule/bn/montgomery.c b/crypto/fipsmodule/bn/montgomery.c
index f09ada8..e8505da 100644
--- a/crypto/fipsmodule/bn/montgomery.c
+++ b/crypto/fipsmodule/bn/montgomery.c
@@ -416,3 +416,68 @@
BN_CTX_end(ctx);
return ret;
}
+
+int bn_to_montgomery_small(BN_ULONG *r, size_t num_r, const BN_ULONG *a,
+ size_t num_a, const BN_MONT_CTX *mont) {
+ return bn_mod_mul_montgomery_small(r, num_r, a, num_a, mont->RR.d,
+ mont->RR.top, mont);
+}
+
+int bn_from_montgomery_small(BN_ULONG *r, size_t num_r, const BN_ULONG *a,
+ size_t num_a, const BN_MONT_CTX *mont) {
+ size_t num_n = mont->N.top;
+ if (num_a > 2 * num_n || num_r != num_n || num_n > BN_SMALL_MAX_WORDS) {
+ OPENSSL_PUT_ERROR(BN, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
+ return 0;
+ }
+ BN_ULONG tmp[BN_SMALL_MAX_WORDS * 2];
+ size_t num_tmp = 2 * num_n;
+ OPENSSL_memcpy(tmp, a, num_a * sizeof(BN_ULONG));
+ OPENSSL_memset(tmp + num_a, 0, (num_tmp - num_a) * sizeof(BN_ULONG));
+ int ret = bn_from_montgomery_in_place(r, num_r, tmp, num_tmp, mont);
+ OPENSSL_cleanse(tmp, num_tmp * sizeof(BN_ULONG));
+ return ret;
+}
+
+int bn_mod_mul_montgomery_small(BN_ULONG *r, size_t num_r, const BN_ULONG *a,
+ size_t num_a, const BN_ULONG *b, size_t num_b,
+ const BN_MONT_CTX *mont) {
+ size_t num_n = mont->N.top;
+ if (num_r != num_n || num_a + num_b > 2 * num_n ||
+ num_n > BN_SMALL_MAX_WORDS) {
+ OPENSSL_PUT_ERROR(BN, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
+ return 0;
+ }
+
+#if defined(OPENSSL_BN_ASM_MONT)
+ // |bn_mul_mont| requires at least 128 bits of limbs, at least for x86.
+ if (num_n >= (128 / BN_BITS2) &&
+ num_a == num_n &&
+ num_b == num_n) {
+ if (!bn_mul_mont(r, a, b, mont->N.d, mont->n0, num_n)) {
+ assert(0); // The check above ensures this won't happen.
+ OPENSSL_PUT_ERROR(BN, ERR_R_INTERNAL_ERROR);
+ return 0;
+ }
+ return 1;
+ }
+#endif
+
+ // Compute the product.
+ BN_ULONG tmp[2 * BN_SMALL_MAX_WORDS];
+ size_t num_tmp = 2 * num_n;
+ size_t num_ab = num_a + num_b;
+ if (a == b && num_a == num_b) {
+ if (!bn_sqr_small(tmp, num_ab, a, num_a)) {
+ return 0;
+ }
+ } else if (!bn_mul_small(tmp, num_ab, a, num_a, b, num_b)) {
+ return 0;
+ }
+
+ // Zero-extend to full width and reduce.
+ OPENSSL_memset(tmp + num_ab, 0, (num_tmp - num_ab) * sizeof(BN_ULONG));
+ int ret = bn_from_montgomery_in_place(r, num_r, tmp, num_tmp, mont);
+ OPENSSL_cleanse(tmp, num_tmp * sizeof(BN_ULONG));
+ return ret;
+}
