Convert BN_mod_sqrt tests to bn_tests.txt.

That removes the last of the bc stuff.

BUG=31

Change-Id: If64c974b75c36daf14c46f07b0d9355b7cd0adcb
Reviewed-on: https://boringssl-review.googlesource.com/8711
Reviewed-by: David Benjamin <davidben@google.com>

3 files changed, 376 insertions, 130 deletions

diff --git a/crypto/bn/bn_test.cc b/crypto/bn/bn_test.cc
index 91994000..fbcab0b5 100644
--- a/crypto/bn/bn_test.cc
+++ b/crypto/bn/bn_test.cc
@@ -90,17 +90,6 @@
 #include "../crypto/test/test_util.h"
 
 
-// This program tests the BIGNUM implementation. It takes an optional -bc
-// argument to write a transcript compatible with the UNIX bc utility.
-//
-// TODO(davidben): Rather than generate random inputs and depend on bc to check
-// the results, most of these tests should use known answers.
-
-static const int num2 = 5;   // number of tests for slow functions
-
-static int rand_neg();
-
-static bool test_mod_sqrt(FILE *fp, BN_CTX *ctx);
 static bool TestBN2BinPadded(BN_CTX *ctx);
 static bool TestDec2BN(BN_CTX *ctx);
 static bool TestHex2BN(BN_CTX *ctx);
@@ -114,48 +103,11 @@ static bool TestExpModZero();
 static bool TestSmallPrime(BN_CTX *ctx);
 static bool RunTest(FileTest *t, void *arg);
 
-// A wrapper around puts that takes its arguments in the same order as our *_fp
-// functions.
-static void puts_fp(FILE *out, const char *m) {
-  if (out != nullptr) {
-    fputs(m, out);
-  }
-}
-
-static void flush_fp(FILE *out) {
-  if (out != nullptr) {
-    fflush(out);
-  }
-}
-
-static void message(FILE *out, const char *m) {
-  puts_fp(out, "print \"test ");
-  puts_fp(out, m);
-  puts_fp(out, "\\n\"\n");
-}
-
 int main(int argc, char *argv[]) {
   CRYPTO_library_init();
 
-  ScopedFILE bc_file;
-  const char *name = argv[0];
-  argc--;
-  argv++;
-  if (argc > 0 && strcmp(argv[0], "-bc") == 0) {
-    if (argc < 2) {
-      fprintf(stderr, "Missing parameter to -bc\n");
-      return 1;
-    }
-    bc_file.reset(fopen(argv[1], "w+"));
-    if (!bc_file) {
-      fprintf(stderr, "Failed to open %s: %s\n", argv[1], strerror(errno));
-    }
-    argc -= 2;
-    argv += 2;
-  }
-
-  if (argc != 1) {
-    fprintf(stderr, "%s [-bc BC_FILE] TEST_FILE\n", name);
+  if (argc != 2) {
+    fprintf(stderr, "%s TEST_FILE\n", argv[0]);
     return 1;
   }
 
@@ -164,18 +116,6 @@ int main(int argc, char *argv[]) {
     return 1;
   }
 
-  puts_fp(bc_file.get(), "/* This script, when run through the UNIX bc utility, "
-                         "should produce a sequence of zeros. */\n");
-  puts_fp(bc_file.get(), "/* tr a-f A-F < bn_test.out | sed s/BAsE/base/ | bc "
-                         "| grep -v 0 */\n");
-  puts_fp(bc_file.get(), "obase=16\nibase=16\n");
-
-  message(bc_file.get(), "BN_mod_sqrt");
-  if (!test_mod_sqrt(bc_file.get(), ctx.get())) {
-    return 1;
-  }
-  flush_fp(bc_file.get());
-
   if (!TestBN2BinPadded(ctx.get()) ||
       !TestDec2BN(ctx.get()) ||
       !TestHex2BN(ctx.get()) ||
@@ -190,7 +130,7 @@ int main(int argc, char *argv[]) {
     return 1;
   }
 
-  return FileTestMain(RunTest, ctx.get(), argv[0]);
+  return FileTestMain(RunTest, ctx.get(), argv[1]);
 }
 
 static int HexToBIGNUM(ScopedBIGNUM *out, const char *in) {
@@ -661,6 +601,32 @@ static bool TestExp(FileTest *t, BN_CTX *ctx) {
   return true;
 }
 
+static bool TestModSqrt(FileTest *t, BN_CTX *ctx) {
+  ScopedBIGNUM a = GetBIGNUM(t, "A");
+  ScopedBIGNUM p = GetBIGNUM(t, "P");
+  ScopedBIGNUM mod_sqrt = GetBIGNUM(t, "ModSqrt");
+  if (!a || !p || !mod_sqrt) {
+    return false;
+  }
+
+  ScopedBIGNUM ret(BN_new());
+  ScopedBIGNUM ret2(BN_new());
+  if (!ret ||
+      !ret2 ||
+      !BN_mod_sqrt(ret.get(), a.get(), p.get(), ctx) ||
+      // There are two possible answers.
+      !BN_sub(ret2.get(), p.get(), ret.get())) {
+    return false;
+  }
+
+  if (BN_cmp(ret2.get(), mod_sqrt.get()) != 0 &&
+      !ExpectBIGNUMsEqual(t, "sqrt(A) (mod P)", mod_sqrt.get(), ret.get())) {
+    return false;
+  }
+
+  return true;
+}
+
 struct Test {
   const char *name;
   bool (*func)(FileTest *t, BN_CTX *ctx);
@@ -677,6 +643,7 @@ static const Test kTests[] = {
     {"ModMul", TestModMul},
     {"ModExp", TestModExp},
     {"Exp", TestExp},
+    {"ModSqrt", TestModSqrt},
 };
 
 static bool RunTest(FileTest *t, void *arg) {
@@ -691,73 +658,6 @@ static bool RunTest(FileTest *t, void *arg) {
   return false;
 }
 
-static int rand_neg() {
-  static unsigned int neg = 0;
-  static const int sign[8] = {0, 0, 0, 1, 1, 0, 1, 1};
-
-  return sign[(neg++) % 8];
-}
-
-static bool test_mod_sqrt(FILE *fp, BN_CTX *ctx) {
-  ScopedBIGNUM a(BN_new());
-  ScopedBIGNUM p(BN_new());
-  ScopedBIGNUM r(BN_new());
-  if (!a || !p || !r) {
-    return false;
-  }
-
-  for (int i = 0; i < 16; i++) {
-    if (i < 8) {
-      const unsigned kPrimes[8] = {2, 3, 5, 7, 11, 13, 17, 19};
-      if (!BN_set_word(p.get(), kPrimes[i])) {
-        return false;
-      }
-    } else {
-      if (!BN_set_word(a.get(), 32) ||
-          !BN_set_word(r.get(), 2 * i + 1) ||
-          !BN_generate_prime_ex(p.get(), 256, 0, a.get(), r.get(), nullptr)) {
-        return false;
-      }
-    }
-    p->neg = rand_neg();
-
-    for (int j = 0; j < num2; j++) {
-      // construct 'a' such that it is a square modulo p, but in general not a
-      // proper square and not reduced modulo p
-      if (!BN_rand(r.get(), 256, 0, 3) ||
-          !BN_nnmod(r.get(), r.get(), p.get(), ctx) ||
-          !BN_mod_sqr(r.get(), r.get(), p.get(), ctx) ||
-          !BN_rand(a.get(), 256, 0, 3) ||
-          !BN_nnmod(a.get(), a.get(), p.get(), ctx) ||
-          !BN_mod_sqr(a.get(), a.get(), p.get(), ctx) ||
-          !BN_mul(a.get(), a.get(), r.get(), ctx)) {
-        return false;
-      }
-      if (rand_neg() && !BN_sub(a.get(), a.get(), p.get())) {
-        return false;
-      }
-
-      if (!BN_mod_sqrt(r.get(), a.get(), p.get(), ctx) ||
-          !BN_mod_sqr(r.get(), r.get(), p.get(), ctx) ||
-          !BN_nnmod(a.get(), a.get(), p.get(), ctx)) {
-        return false;
-      }
-
-      if (BN_cmp(a.get(), r.get()) != 0) {
-        fprintf(stderr, "BN_mod_sqrt failed: a = ");
-        BN_print_fp(stderr, a.get());
-        fprintf(stderr, ", r = ");
-        BN_print_fp(stderr, r.get());
-        fprintf(stderr, ", p = ");
-        BN_print_fp(stderr, p.get());
-        fprintf(stderr, "\n");
-        return false;
-      }
-    }
-  }
-  return true;
-}
-
 static bool TestBN2BinPadded(BN_CTX *ctx) {
   uint8_t zeros[256], out[256], reference[128];
 
diff --git a/crypto/bn/bn_tests.txt b/crypto/bn/bn_tests.txt
index 48678bc6..cf85813c 100644
--- a/crypto/bn/bn_tests.txt
+++ b/crypto/bn/bn_tests.txt
@@ -10203,3 +10203,329 @@ E = 1a
 Exp = a0ea5f6a4de49beb8fb7f0dab280d6a32c5a3814c9a5153a7944cec0a9028497846a8a89044348721a0bb5f0c3ded3e980574ea321b0cdb0ead4f4e93841ea7478a7f15d9729b646a8165813a0750e8124f5465dda9b105e1bbeff18fd09c09a2e26610d9176d253b877c3a8908a6be521cbe1e472a7a1b7820e4e890f8f28aacd34609c686e76e15b01bd9324a71290812724ea564d11c874a6765b262c3e57d479da0287a76026a1e8fe53da0b02405da1d379eaa30fc65f
 A = fccec0f6df
 E = 25
+
+
+# ModSqrt tests.
+#
+# These test vectors satisfy ModSqrt * ModSqrt = A (mod P) with P a prime.
+# ModSqrt is in [0, (P-1)/2].
+
+ModSqrt = 1
+A = 1
+P = 2
+
+ModSqrt = 1
+A = 1
+P = 2
+
+ModSqrt = 1
+A = 1
+P = 2
+
+ModSqrt = 1
+A = -1
+P = 2
+
+ModSqrt = 1
+A = -1
+P = 2
+
+ModSqrt = 0
+A = 0
+P = 3
+
+ModSqrt = 0
+A = -3
+P = 3
+
+ModSqrt = 0
+A = -3
+P = 3
+
+ModSqrt = 0
+A = 0
+P = 3
+
+ModSqrt = 0
+A = 0
+P = 3
+
+ModSqrt = 0
+A = 0
+P = 5
+
+ModSqrt = 1
+A = -4
+P = 5
+
+ModSqrt = 0
+A = -5
+P = 5
+
+ModSqrt = 2
+A = 4
+P = 5
+
+ModSqrt = 0
+A = -5
+P = 5
+
+ModSqrt = 3
+A = -5
+P = 7
+
+ModSqrt = 0
+A = 0
+P = 7
+
+ModSqrt = 0
+A = 0
+P = 7
+
+ModSqrt = 2
+A = 4
+P = 7
+
+ModSqrt = 3
+A = -5
+P = 7
+
+ModSqrt = 4
+A = 10
+P = b
+
+ModSqrt = 0
+A = 0
+P = b
+
+ModSqrt = 3
+A = -2
+P = b
+
+ModSqrt = 3
+A = -2
+P = b
+
+ModSqrt = 2
+A = 4
+P = b
+
+ModSqrt = 2
+A = 1e
+P = d
+
+ModSqrt = 2
+A = 1e
+P = d
+
+ModSqrt = 0
+A = -d
+P = d
+
+ModSqrt = 0
+A = -d
+P = d
+
+ModSqrt = 3
+A = 9
+P = d
+
+ModSqrt = 8
+A = d
+P = 11
+
+ModSqrt = 6
+A = df
+P = 11
+
+ModSqrt = 4
+A = 10
+P = 11
+
+ModSqrt = 5
+A = 90
+P = 11
+
+ModSqrt = 3
+A = 80
+P = 11
+
+ModSqrt = 9
+A = -e
+P = 13
+
+ModSqrt = 7
+A = 7d
+P = 13
+
+ModSqrt = 6
+A = 37
+P = 13
+
+ModSqrt = 1
+A = 1
+P = 13
+
+ModSqrt = 8
+A = 1a
+P = 13
+
+ModSqrt = 54d4cf0fafe265056a29016778cea6b712bc66a132fb5e6b6865e9b49e4c97ec
+A = 599c10484b22d0b5a115268c7538ca99b3253a311a4ab1ca11c3665b0bec393a1167d1ad94fb84cb2c7ad7e2c933e8f613bdd08fe1f1aa4a9b0b9de0c8a7c9d4
+P = cfc4ccae35458ab5be1a1bc0664188253301f8702af4f8fb19fed12de0c653b1
+
+ModSqrt = 38a7365a15365e911286c1be2a7afe76ef390234d76269e04dee17313f6ea54d
+A = 1c4aabb4d8369710131c664ecf2849e963c1bc31d66e0b939bacf99a870c71f24ed71bdddcf566f3908271fee43fc1ebb51eac7e3153efae641b49d2e796a12a
+P = cfc4ccae35458ab5be1a1bc0664188253301f8702af4f8fb19fed12de0c653b1
+
+ModSqrt = 35ab18a560dece04725667f640ca61d1d59f14d191f94c79f58531acd097d444
+A = 685168ae855d60eba220d803f5296459b30a289580668db9ed51bca51cc2d453a937e13819ae34f7a9a143ac96d17420c53919167e46279b562b550be1cd9abc
+P = cfc4ccae35458ab5be1a1bc0664188253301f8702af4f8fb19fed12de0c653b1
+
+ModSqrt = 288370029e87024175e5bec0eab0929179f42e16995e7f6194eefc61061e54f4
+A = 2a14ab77c045bdc48220ba9c463e1a4b4049cb01edb53be0937767eb2ec19b7d719855052281250a36a0b76d9a5d967d0756e1ded7a052f7056191ad66bcfc9
+P = cfc4ccae35458ab5be1a1bc0664188253301f8702af4f8fb19fed12de0c653b1
+
+ModSqrt = 32255cf01dc943577ec2bcb221b98491d7a1130d046d6c68e95fedff643ce3a4
+A = e26f6dd46a513a1dd3fb14b71be1d4c9e9d79eda1cde10ea4d1eb8abfd4d5857572205e247184dd0cbefa37b5c0bf680ba2bd28c5741f725cfe2aae37419baf
+P = cfc4ccae35458ab5be1a1bc0664188253301f8702af4f8fb19fed12de0c653b1
+
+ModSqrt = 5172345e801ada63fbc4782e32583cc3b4fea88b9e6dfd542f3542f8538ade66
+A = 40dafa8342b302bb04b1f3ddb3b9015a8fc1b597857c115b40631c7be9e22de89358fca23b331596ee5ff304dad7811e6d8e8822f7aa533c9e7c882634ea550
+P = a6813d316f9aca30f98b4f864b8b4b8f51493af930bd4d3a1b205a710e99add3
+
+ModSqrt = 4dcf63c423bf0e39aca2293d57f6792d023db649d6719fe936446904b9f7e60d
+A = 5bcdb514bbe84261e169203e8017909b60c9bb330400c766ee01b0189378e70e61867a164a12643ddc9e94b61e09e5b158cbe85be228a3cc48f95a552958b8f2
+P = a6813d316f9aca30f98b4f864b8b4b8f51493af930bd4d3a1b205a710e99add3
+
+ModSqrt = cf77c5c2d12a500b75cbfb1f3e66ee75d886b9365cf4f8b4d1bd18a6be0f387
+A = 4652ddc2ea7b460d8ec3c9059b8f9b5dae6cac55b51f2ad86fcb336b25235737965cc515e2ff0b54835015b7ebeeda6fadd986471d8cb424d309fc353d1e269
+P = a6813d316f9aca30f98b4f864b8b4b8f51493af930bd4d3a1b205a710e99add3
+
+ModSqrt = 1e0549e4c5a26023e9d24fd8c67419960746f82b1ecd113bdac66f570a475d87
+A = 5f4a6d450ab1390d96ab1deaa0ba18f897cb63daf0c9e1ef6c08e804c26b5e842f6c08f13db5d4a6e88f07af2a3cb04fa06fc3e59c410b9356f025ed81acc74
+P = a6813d316f9aca30f98b4f864b8b4b8f51493af930bd4d3a1b205a710e99add3
+
+ModSqrt = 144481a781d831c1ca046ca9e322d79ad4d2c6dd9f780bea9d1ced9cd20b7b23
+A = 4c254fabca441017132b9eacd4ca40a336db3e5c09715773fa07af095989a91cc968ff07a9ff56ed06b0ce0c5269f7b2ab68564ecab9f4467a7e96b6cc6b21b7
+P = a6813d316f9aca30f98b4f864b8b4b8f51493af930bd4d3a1b205a710e99add3
+
+ModSqrt = 216fecc7667f488a3d2d102a38b46b4860ab858300b8638af4f34e1103fd73ba
+A = 17878f8048227573a9d70f53c0e76ff13fe9f56e9c984c92514d3d13dec23c816661f0618d21371b80dfd885cb59551bdf80046f65f22ea9b89c78645a6e455a
+P = bd37c850cf7d702bac879f3c21a51a5a4df2b8eb0935861e0753a6eb62261a95
+
+ModSqrt = 458e5e789ccd2417174f7e30bb31914b9656bd8cf2b9f5a9752a8737a67707bc
+A = 5c7d39a4bb04e69201aa519f80ee7e62ea14ca55e13656d1da3f45367e2fb2d061aa2940708d02ac67d35cd2ccf54a1bf95bcbc759779e692cfdcbb3aa1a05b
+P = bd37c850cf7d702bac879f3c21a51a5a4df2b8eb0935861e0753a6eb62261a95
+
+ModSqrt = 543125a16c2bb8b8f8a2c39c497e5224ec77533602d7dbe24002e32dcbd2ef1a
+A = 3413afae333b2ad9ff45c7f3c7e5934b3127e8b1a55225958ee6ccf42423e81559bf070ad3f3353b78c0ffd41475af49f59d268ef78bdae879f5155e8d1cc07
+P = bd37c850cf7d702bac879f3c21a51a5a4df2b8eb0935861e0753a6eb62261a95
+
+ModSqrt = 10e16859c67bdb2eaab52a7c847dbf37162eda258a9f6262ebacfe4cbbbc1080
+A = 21ce7905894faf220bdf4a82a2d855994ca2dc9feaecaa53c7f146e1f49934215695e9bb46ba370b7005a90c399674caa8969eb442e7914d90f749774d7fd194
+P = bd37c850cf7d702bac879f3c21a51a5a4df2b8eb0935861e0753a6eb62261a95
+
+ModSqrt = 32a00586adc6f6cc2b1a04e1be0ab569fde235e1436c38b6af92bc5ebd60bc1c
+A = 350da4fd8cf03c12f7dd6ac6d3ab801a3413964083e374662aaf878d6838b97d4feb9e52cd307a25b113e101661a865463ee2480c626aa4e2ec437d72e7bae4c
+P = bd37c850cf7d702bac879f3c21a51a5a4df2b8eb0935861e0753a6eb62261a95
+
+ModSqrt = 971f75bc7afa8b4b50f1d4b05e52deac7d4836a08d30546f29649bf1ca6a247
+A = 655ed4c5d8d0afb4f9360372ee1ef1303898d2423e585108a3303faedb55064d2ef25666ed4c4d71fe6063fea1f3142b435714b0e30b339dd791d347c884654
+P = 9810151ad4bc9c5d68fc326395b509f2625bfebca1c3801ad4da7539fdbaa6f7
+
+ModSqrt = 48fa882b7cb6a29de9e3769f72eb67f1efd4d2af56f0c7e410c610efcbce2065
+A = 14f3503f33b243800eac1defaab33e04c01e80163fb3efd03860970cc016832431ca4fc6d1b760f4f40166b0b8b3c40dbebc81460cc10890172243770338f090
+P = 9810151ad4bc9c5d68fc326395b509f2625bfebca1c3801ad4da7539fdbaa6f7
+
+ModSqrt = 236fd7e397ea7f8bc2a288eb7236ca41936fa702b7dccca56c8852e147511f7d
+A = 1bbd0980feac854782813bcde4da85e8a054549a1b515e065da4236528035e756882e29e762cf60453e375cca9dc6ff637f9558bf86646e3b928f68f82af7efe
+P = 9810151ad4bc9c5d68fc326395b509f2625bfebca1c3801ad4da7539fdbaa6f7
+
+ModSqrt = 693f0cbe8c81b0afde0cd2f83e53795dcae6b0cc4ba930ab5c752400d787f14
+A = 7b20f9664b23907e152ab8c9a907f72e8670c1c38ab4cd1411ea7c2159c09aa131afe068929b8e6ad1409b74c04975180d1cd0a9fa74e923c3fd451e8da2c34
+P = 9810151ad4bc9c5d68fc326395b509f2625bfebca1c3801ad4da7539fdbaa6f7
+
+ModSqrt = 4a086c50b0bad576501ddb6280743b2c9d247841eb7f14d90561432ff7dca6f0
+A = 4367431ec0cd0d7626538b93a090c30fe0c97c18ca03b97ddae304b619112b5b4d02bf0f041fa3fd673f9ef2ceb07eb2079d11c56dd903b1a87e8252a97b8079
+P = 9810151ad4bc9c5d68fc326395b509f2625bfebca1c3801ad4da7539fdbaa6f7
+
+ModSqrt = 18f8433fa468d8065157708f1f1e53b8e31d39c6011fbc2bad93de1b5548e19c
+A = 739c032bb4139c199c40f548d37234298772e4ccb9d3ba28412b60ad23b4c465b0787e2382f1c5a4a87af2d20eb978b7dcbe73f2112249477d15c8a85e54a79
+P = adcd56924f73836ebe4dccfe006ad3b1e5076562cd11b161642cab7af2284659
+
+ModSqrt = 49e3c8eef5e067cabd51a7c01384ce05ab8f4342f655559d8a689eb7b20e0106
+A = 18400c2cc3e06b99b4e39c77b9af5ff0e9c683f1708321afa4cd5b6988d13b36b1d9eb4379b7902d9ceb40c03f814b2b6a01b90509bbb4532f13ab1571c4d04a
+P = adcd56924f73836ebe4dccfe006ad3b1e5076562cd11b161642cab7af2284659
+
+ModSqrt = 35548c530745f440329325cc8a5fbd90c16a7f0788879a4869bc4d4f73acda0e
+A = 181a3c5ab02566e7166c4d6d2f2bd4a8ecc25991a98d270bde80cf4332766a7068b14240bf5f5dcd45e90ef252596da3eb05b11d68b2063f7b3a825742593ca9
+P = adcd56924f73836ebe4dccfe006ad3b1e5076562cd11b161642cab7af2284659
+
+ModSqrt = 1ab7046e6af061ade5f9719008fa4d989007e2a579a134a5b9f19ec410984096
+A = 1008a03e211fab0d45856377079bc96b0776c2d4c0175661f3493246cea2ab0a02a706c85314fb707ad9906bedb2cfd577d62092ae08ff21d7b949373ea954c7
+P = adcd56924f73836ebe4dccfe006ad3b1e5076562cd11b161642cab7af2284659
+
+ModSqrt = 2be9e3e7515960d90f115b89f60dedc173a73ce163b4036e85b7b6a76fd90852
+A = 392053a9f0100540a8e1a0c353e922068a84dad3a4a8e8962fbc0bee2b6a06e20d08ade16eb1409a16acfcac3db5c43c421505e07035ca308b15c4a6db0864c0
+P = adcd56924f73836ebe4dccfe006ad3b1e5076562cd11b161642cab7af2284659
+
+ModSqrt = 5b301bb93bdcf050183107e36258b53b4805918114ea1c2227b0911d5b4dc077
+A = 55e55e5f94dc3d7aabc921f6469d85fa2e1e92a87347c57afad5872306ae69f9fb99297d1e3e793dd9e8632244208154de5da7114fd876383bf1422f7ece024
+P = d43280ac150f725f4a2a1dceb1c79bcac57855a4eba72ae93762d09bcb2444fb
+
+ModSqrt = 2df9609e2f5a5156c3260461b2ee52eacdef00bd8b091479813143a6c5283f71
+A = 2099325b7f12fe77353ddf3f2b2c5ef77b49671b150af954cf84e9675e3ecde3e057084641a633d19533b4712ab49924c8b5c31d591abcc88291f51253fa2a7
+P = d43280ac150f725f4a2a1dceb1c79bcac57855a4eba72ae93762d09bcb2444fb
+
+ModSqrt = dfab751710e9008e25e422d1199d6fbec4dc7fba35b4da9d225a746eb4126a0
+A = c006af53d4737fb293584df6ffe2e4cb3fd8dc77fb7c1f13b97bb9c249e3ee5fb9feff7488265b3093906c08a4946f142ac7b491937d24bfba6413366ce371d
+P = d43280ac150f725f4a2a1dceb1c79bcac57855a4eba72ae93762d09bcb2444fb
+
+ModSqrt = 26bc030008d6c60a09fb0e16093a649fcb40c6c21a8e2da2353ba4b07c4f85d5
+A = 1eaabcfad2ed349ac9356e6f4da0b301266ddde811cb0f817aba8f5c10fb8b8ba9d0ef2dd386b668f16eac296118fdb8cb7afe1b865648c81c2fa3cf21f2711b
+P = d43280ac150f725f4a2a1dceb1c79bcac57855a4eba72ae93762d09bcb2444fb
+
+ModSqrt = 35051b1482ec2578f3dc0000a422cb5111e43c37f1ac20b1844d3de2128c4556
+A = 315ff9de178681116f2a5fa78eebf4818e1d680435eacdfaf9d0e5c4fc01fc034b352c82fd52c81ca30d68864952dacc99d08269c9dd7ca99ccf22da98c3840
+P = d43280ac150f725f4a2a1dceb1c79bcac57855a4eba72ae93762d09bcb2444fb
+
+ModSqrt = a5474252885cacf004c460a7793ff0b0a2187bb1a9ed700ae3470199faef71f
+A = 19856fc1351c4b02abf573bb2fc6ff92355fa369d62bb8f2260fa772fb1693f509a56cad661930abcac049dd70f4b16bed4a4c172e73e772504c9990ce7f92f
+P = dc315fd52684fba79e577a204de9053b11a5d7a414263fec9eff6ff62188829d
+
+ModSqrt = 12daf4722387ecf47de1b0b6b110a062dc5ea2685bc9dbde66b8d15622985029
+A = fb8479787069116abc42abfd7dc0c24d2ad04fe0c04b42a6dff714af715d17e0fd77855f950f264542b06d48e8818de813ddb7975798b7debefcdaa5ff86beb
+P = dc315fd52684fba79e577a204de9053b11a5d7a414263fec9eff6ff62188829d
+
+ModSqrt = 397996ed5c0ac6ad32e43c337e9de421b87774cc162bf7ac7bbedf4a9029255e
+A = 5aa04353321bd2de92481be740357f979da464b53aa39111fdbb734cf7af6b3857d1baa08d3a126a3dd34a2fbae2bf2b84e900686c1d31505b390185acef5fe5
+P = dc315fd52684fba79e577a204de9053b11a5d7a414263fec9eff6ff62188829d
+
+ModSqrt = 2cf4b844a54ba359dc592ef1b49f43fcfeae84d1087edfefdd0b9174b43c0a3c
+A = 365a8650510bcfd8fa87432f167cf487234c215857403b9270b5eebeafa48cd6da47fd60dc311b94d1d72baad0447c31f0b212d755f46c256e16e5e015e6546e
+P = dc315fd52684fba79e577a204de9053b11a5d7a414263fec9eff6ff62188829d
+
+ModSqrt = 9277c73043ff767c3fa606f0cd66b9d854a600c8c18287f191ce277758c3f31
+A = 62cec3901626d03e8df66299a87c54b1f7a55cafc99f0b6bba1b5d51a3d2b7d2171c9135a9d8a5346d436e0136b12e515e703e3cd84ecfe154eb94c6772a6d72
+P = dc315fd52684fba79e577a204de9053b11a5d7a414263fec9eff6ff62188829d
+
+ModSqrt = 4189e5a90c1b1abdc1c7c05b3587e6f362e06f927b6cf5f0d271aab3d6f90765
+A = 336b8d0f9dac842c696bc020f49c6aa023842c16f2052eb02f17959006554ca0012042c80c72590f21c6bf5a3714c9cb552aa69730e33db93a56a909b273f39
+P = 9df9d6cc20b8540411af4e5357ef2b0353cb1f2ab5ffc3e246b41c32f71e951f
+
+ModSqrt = 36ccd38cb5a6bd8a73bca55936a2227c503664422c2296faf7e2b1c6a375a43a
+A = fecfd60a376befbe48d2c4f6d070d716d2f403cd5daefbce62b720df44deb605162c8f20f49fd7ec30d4f8e70d803d45b3a44b5d912baa3410d991165d7c507
+P = 9df9d6cc20b8540411af4e5357ef2b0353cb1f2ab5ffc3e246b41c32f71e951f
+
+ModSqrt = 198fc8569be172dc9b71023ed3d42d2ba94bae4099643f6517ab03f540527fdb
+A = 65bebdb00a96fc814ec44b81f98b59fba3c30203928fa5214c51e0a97091645280c947b005847f239758482b9bfc45b066fde340d1fe32fc9c1bf02e1b2d0ec
+P = 9df9d6cc20b8540411af4e5357ef2b0353cb1f2ab5ffc3e246b41c32f71e951f
+
+ModSqrt = 21b7f74c30ded681d6138cf8e6fd798f32a049e94138e982f1845df3dc9e686f
+A = 9a30b791c1ba4f394b4e3dcd5837e474237f4fe8987b255c098a47b2c14c598ec69d2beae444dd4fe9c4ede8173d2b187677cc706a3c28f3b81627d8a5fb6fd
+P = 9df9d6cc20b8540411af4e5357ef2b0353cb1f2ab5ffc3e246b41c32f71e951f
+
+ModSqrt = a1d52989f12f204d3d2167d9b1e6c8a6174c0c786a979a5952383b7b8bd186
+A = 2eee37cf06228a387788188e650bc6d8a2ff402931443f69156a29155eca07dcb45f3aac238d92943c0c25c896098716baa433f25bd696a142f5a69d5d937e81
+P = 9df9d6cc20b8540411af4e5357ef2b0353cb1f2ab5ffc3e246b41c32f71e951f
diff --git a/crypto/bn/check_bn_tests.go b/crypto/bn/check_bn_tests.go
index 96411667..68e79e04 100644
--- a/crypto/bn/check_bn_tests.go
+++ b/crypto/bn/check_bn_tests.go
@@ -227,6 +227,26 @@ func main() {
 				r := new(big.Int).Exp(test.Values["A"], test.Values["E"], nil)
 				checkResult(test, "A ^ E", "Exp", r)
 			}
+		case "ModSqrt":
+			bigOne := new(big.Int).SetInt64(1)
+			bigTwo := new(big.Int).SetInt64(2)
+
+			if checkKeys(test, "A", "P", "ModSqrt") {
+				test.Values["A"].Mod(test.Values["A"], test.Values["P"])
+
+				r := new(big.Int).Mul(test.Values["ModSqrt"], test.Values["ModSqrt"])
+				r = r.Mod(r, test.Values["P"])
+				checkResult(test, "ModSqrt ^ 2 (mod P)", "A", r)
+
+				if (test.Values["P"].Cmp(bigTwo) > 0) {
+					pMinus1Over2 := new(big.Int).Sub(test.Values["P"], bigOne)
+					pMinus1Over2.Rsh(pMinus1Over2, 1)
+
+					if test.Values["ModSqrt"].Cmp(pMinus1Over2) > 0 {
+						fmt.Fprintf(os.Stderr, "Line %d: ModSqrt should be minimal.\n", test.LineNumber)
+					}
+				}
+			}
 		default:
 			fmt.Fprintf(os.Stderr, "Line %d: unknown test type %q.\n", test.LineNumber, test.Type)
 		}