commit 67cb49d045f04973ddba0f92fe8a8ad483c7da89
author David Benjamin <davidben@google.com> Thu Jun 09 18:57:56 2016 +0000
committer Adam Langley <agl@google.com> Thu Jun 09 19:05:31 2016 +0000
tree 26cb52b6787db5c4d7183529071f668631a1626e
parent 8f1e113a73e406db710479ea4d8478890c0514ea

Fix BN_mod_word bug.

On systems where we do not have BN_ULLONG (notably Win64), BN_mod_word() can
return incorrect results if the supplied modulus is too big.

(Imported from upstream's e82fd1b4574c8908b2c3bb68e1237f057a981820 and
e4c4b2766bb97b34ea3479252276ab7c66311809.)

Change-Id: Icee8a7c5c67a8ee14c276097f43a7c491e68c2f9
Reviewed-on: https://boringssl-review.googlesource.com/8233
Reviewed-by: Adam Langley <agl@google.com>

crypto/bn/bn_test.cc

diff --git a/crypto/bn/bn_test.cc b/crypto/bn/bn_test.cc
index fe8cfd0..d909ee2 100644
--- a/crypto/bn/bn_test.cc
+++ b/crypto/bn/bn_test.cc
@@ -850,11 +850,17 @@
       return false;
     }
     BN_ULONG s = b->d[0];
+    BN_ULONG rmod = BN_mod_word(b.get(), s);
     BN_ULONG r = BN_div_word(b.get(), s);
     if (r == (BN_ULONG)-1) {
       return false;
     }
 
+    if (rmod != r) {
+      fprintf(stderr, "Mod (word) test failed!\n");
+      return false;
+    }
+
     if (fp != NULL) {
       BN_print_fp(fp, a.get());
       puts_fp(fp, " / ");

crypto/bn/div.c

diff --git a/crypto/bn/div.c b/crypto/bn/div.c
index 6f67291..e824458 100644
--- a/crypto/bn/div.c
+++ b/crypto/bn/div.c
@@ -644,6 +644,20 @@
     return (BN_ULONG) -1;
   }
 
+#ifndef BN_ULLONG
+  /* If |w| is too long and we don't have |BN_ULLONG| then we need to fall back
+   * to using |BN_div_word|. */
+  if (w > ((BN_ULONG)1 << BN_BITS4)) {
+    BIGNUM *tmp = BN_dup(a);
+    if (tmp == NULL) {
+      return (BN_ULONG)-1;
+    }
+    ret = BN_div_word(tmp, w);
+    BN_free(tmp);
+    return ret;
+  }
+#endif
+
   w &= BN_MASK2;
   for (i = a->top - 1; i >= 0; i--) {
 #ifndef BN_ULLONG