diff options
Diffstat (limited to 'crypto')
-rw-r--r-- | crypto/bn/bn_test.cc | 160 | ||||
-rw-r--r-- | crypto/bn/bn_tests.txt | 326 | ||||
-rw-r--r-- | crypto/bn/check_bn_tests.go | 20 |
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) } |