1 /* Copyright (C) 1995-1998 Eric Young (eay (at) cryptsoft.com) 2 * All rights reserved. 3 * 4 * This package is an SSL implementation written 5 * by Eric Young (eay (at) cryptsoft.com). 6 * The implementation was written so as to conform with Netscapes SSL. 7 * 8 * This library is free for commercial and non-commercial use as long as 9 * the following conditions are aheared to. The following conditions 10 * apply to all code found in this distribution, be it the RC4, RSA, 11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 12 * included with this distribution is covered by the same copyright terms 13 * except that the holder is Tim Hudson (tjh (at) cryptsoft.com). 14 * 15 * Copyright remains Eric Young's, and as such any Copyright notices in 16 * the code are not to be removed. 17 * If this package is used in a product, Eric Young should be given attribution 18 * as the author of the parts of the library used. 19 * This can be in the form of a textual message at program startup or 20 * in documentation (online or textual) provided with the package. 21 * 22 * Redistribution and use in source and binary forms, with or without 23 * modification, are permitted provided that the following conditions 24 * are met: 25 * 1. Redistributions of source code must retain the copyright 26 * notice, this list of conditions and the following disclaimer. 27 * 2. Redistributions in binary form must reproduce the above copyright 28 * notice, this list of conditions and the following disclaimer in the 29 * documentation and/or other materials provided with the distribution. 30 * 3. All advertising materials mentioning features or use of this software 31 * must display the following acknowledgement: 32 * "This product includes cryptographic software written by 33 * Eric Young (eay (at) cryptsoft.com)" 34 * The word 'cryptographic' can be left out if the rouines from the library 35 * being used are not cryptographic related :-). 36 * 4. If you include any Windows specific code (or a derivative thereof) from 37 * the apps directory (application code) you must include an acknowledgement: 38 * "This product includes software written by Tim Hudson (tjh (at) cryptsoft.com)" 39 * 40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 50 * SUCH DAMAGE. 51 * 52 * The licence and distribution terms for any publically available version or 53 * derivative of this code cannot be changed. i.e. this code cannot simply be 54 * copied and put under another distribution licence 55 * [including the GNU Public Licence.] 56 */ 57 /* ==================================================================== 58 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 59 * 60 * Portions of the attached software ("Contribution") are developed by 61 * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. 62 * 63 * The Contribution is licensed pursuant to the Eric Young open source 64 * license provided above. 65 * 66 * The binary polynomial arithmetic software is originally written by 67 * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems 68 * Laboratories. */ 69 70 /* Per C99, various stdint.h and inttypes.h macros (the latter used by bn.h) are 71 * unavailable in C++ unless some macros are defined. C++11 overruled this 72 * decision, but older Android NDKs still require it. */ 73 #if !defined(__STDC_CONSTANT_MACROS) 74 #define __STDC_CONSTANT_MACROS 75 #endif 76 #if !defined(__STDC_FORMAT_MACROS) 77 #define __STDC_FORMAT_MACROS 78 #endif 79 80 #include <assert.h> 81 #include <errno.h> 82 #include <limits.h> 83 #include <stdio.h> 84 #include <string.h> 85 86 #include <utility> 87 88 #include <gtest/gtest.h> 89 90 #include <openssl/bn.h> 91 #include <openssl/bytestring.h> 92 #include <openssl/crypto.h> 93 #include <openssl/err.h> 94 #include <openssl/mem.h> 95 96 #include "../../internal.h" 97 #include "../../test/file_test.h" 98 #include "../../test/test_util.h" 99 100 101 static int HexToBIGNUM(bssl::UniquePtr<BIGNUM> *out, const char *in) { 102 BIGNUM *raw = NULL; 103 int ret = BN_hex2bn(&raw, in); 104 out->reset(raw); 105 return ret; 106 } 107 108 static bssl::UniquePtr<BIGNUM> GetBIGNUM(FileTest *t, const char *attribute) { 109 std::string hex; 110 if (!t->GetAttribute(&hex, attribute)) { 111 return nullptr; 112 } 113 114 bssl::UniquePtr<BIGNUM> ret; 115 if (HexToBIGNUM(&ret, hex.c_str()) != static_cast<int>(hex.size())) { 116 t->PrintLine("Could not decode '%s'.", hex.c_str()); 117 return nullptr; 118 } 119 return ret; 120 } 121 122 static bool GetInt(FileTest *t, int *out, const char *attribute) { 123 bssl::UniquePtr<BIGNUM> ret = GetBIGNUM(t, attribute); 124 if (!ret) { 125 return false; 126 } 127 128 BN_ULONG word = BN_get_word(ret.get()); 129 if (word > INT_MAX) { 130 return false; 131 } 132 133 *out = static_cast<int>(word); 134 return true; 135 } 136 137 static testing::AssertionResult AssertBIGNUMSEqual( 138 const char *operation_expr, const char *expected_expr, 139 const char *actual_expr, const char *operation, const BIGNUM *expected, 140 const BIGNUM *actual) { 141 if (BN_cmp(expected, actual) == 0) { 142 return testing::AssertionSuccess(); 143 } 144 145 bssl::UniquePtr<char> expected_str(BN_bn2hex(expected)); 146 bssl::UniquePtr<char> actual_str(BN_bn2hex(actual)); 147 if (!expected_str || !actual_str) { 148 return testing::AssertionFailure() << "Error converting BIGNUMs to hex"; 149 } 150 151 return testing::AssertionFailure() 152 << "Wrong value for " << operation 153 << "\nActual: " << actual_str.get() << " (" << actual_expr 154 << ")\nExpected: " << expected_str.get() << " (" << expected_expr 155 << ")"; 156 } 157 158 #define EXPECT_BIGNUMS_EQUAL(op, a, b) \ 159 EXPECT_PRED_FORMAT3(AssertBIGNUMSEqual, op, a, b) 160 161 static void TestSum(FileTest *t, BN_CTX *ctx) { 162 bssl::UniquePtr<BIGNUM> a = GetBIGNUM(t, "A"); 163 bssl::UniquePtr<BIGNUM> b = GetBIGNUM(t, "B"); 164 bssl::UniquePtr<BIGNUM> sum = GetBIGNUM(t, "Sum"); 165 ASSERT_TRUE(a); 166 ASSERT_TRUE(b); 167 ASSERT_TRUE(sum); 168 169 bssl::UniquePtr<BIGNUM> ret(BN_new()); 170 ASSERT_TRUE(ret); 171 ASSERT_TRUE(BN_add(ret.get(), a.get(), b.get())); 172 EXPECT_BIGNUMS_EQUAL("A + B", sum.get(), ret.get()); 173 174 ASSERT_TRUE(BN_sub(ret.get(), sum.get(), a.get())); 175 EXPECT_BIGNUMS_EQUAL("Sum - A", b.get(), ret.get()); 176 177 ASSERT_TRUE(BN_sub(ret.get(), sum.get(), b.get())); 178 EXPECT_BIGNUMS_EQUAL("Sum - B", a.get(), ret.get()); 179 180 // Test that the functions work when |r| and |a| point to the same |BIGNUM|, 181 // or when |r| and |b| point to the same |BIGNUM|. TODO: Test the case where 182 // all of |r|, |a|, and |b| point to the same |BIGNUM|. 183 ASSERT_TRUE(BN_copy(ret.get(), a.get())); 184 ASSERT_TRUE(BN_add(ret.get(), ret.get(), b.get())); 185 EXPECT_BIGNUMS_EQUAL("A + B (r is a)", sum.get(), ret.get()); 186 187 ASSERT_TRUE(BN_copy(ret.get(), b.get())); 188 ASSERT_TRUE(BN_add(ret.get(), a.get(), ret.get())); 189 EXPECT_BIGNUMS_EQUAL("A + B (r is b)", sum.get(), ret.get()); 190 191 ASSERT_TRUE(BN_copy(ret.get(), sum.get())); 192 ASSERT_TRUE(BN_sub(ret.get(), ret.get(), a.get())); 193 EXPECT_BIGNUMS_EQUAL("Sum - A (r is a)", b.get(), ret.get()); 194 195 ASSERT_TRUE(BN_copy(ret.get(), a.get())); 196 ASSERT_TRUE(BN_sub(ret.get(), sum.get(), ret.get())); 197 EXPECT_BIGNUMS_EQUAL("Sum - A (r is b)", b.get(), ret.get()); 198 199 ASSERT_TRUE(BN_copy(ret.get(), sum.get())); 200 ASSERT_TRUE(BN_sub(ret.get(), ret.get(), b.get())); 201 EXPECT_BIGNUMS_EQUAL("Sum - B (r is a)", a.get(), ret.get()); 202 203 ASSERT_TRUE(BN_copy(ret.get(), b.get())); 204 ASSERT_TRUE(BN_sub(ret.get(), sum.get(), ret.get())); 205 EXPECT_BIGNUMS_EQUAL("Sum - B (r is b)", a.get(), ret.get()); 206 207 // Test |BN_uadd| and |BN_usub| with the prerequisites they are documented as 208 // having. Note that these functions are frequently used when the 209 // prerequisites don't hold. In those cases, they are supposed to work as if 210 // the prerequisite hold, but we don't test that yet. TODO: test that. 211 if (!BN_is_negative(a.get()) && 212 !BN_is_negative(b.get()) && BN_cmp(a.get(), b.get()) >= 0) { 213 ASSERT_TRUE(BN_uadd(ret.get(), a.get(), b.get())); 214 EXPECT_BIGNUMS_EQUAL("A +u B", sum.get(), ret.get()); 215 216 ASSERT_TRUE(BN_usub(ret.get(), sum.get(), a.get())); 217 EXPECT_BIGNUMS_EQUAL("Sum -u A", b.get(), ret.get()); 218 219 ASSERT_TRUE(BN_usub(ret.get(), sum.get(), b.get())); 220 EXPECT_BIGNUMS_EQUAL("Sum -u B", a.get(), ret.get()); 221 222 // Test that the functions work when |r| and |a| point to the same |BIGNUM|, 223 // or when |r| and |b| point to the same |BIGNUM|. TODO: Test the case where 224 // all of |r|, |a|, and |b| point to the same |BIGNUM|. 225 ASSERT_TRUE(BN_copy(ret.get(), a.get())); 226 ASSERT_TRUE(BN_uadd(ret.get(), ret.get(), b.get())); 227 EXPECT_BIGNUMS_EQUAL("A +u B (r is a)", sum.get(), ret.get()); 228 229 ASSERT_TRUE(BN_copy(ret.get(), b.get())); 230 ASSERT_TRUE(BN_uadd(ret.get(), a.get(), ret.get())); 231 EXPECT_BIGNUMS_EQUAL("A +u B (r is b)", sum.get(), ret.get()); 232 233 ASSERT_TRUE(BN_copy(ret.get(), sum.get())); 234 ASSERT_TRUE(BN_usub(ret.get(), ret.get(), a.get())); 235 EXPECT_BIGNUMS_EQUAL("Sum -u A (r is a)", b.get(), ret.get()); 236 237 ASSERT_TRUE(BN_copy(ret.get(), a.get())); 238 ASSERT_TRUE(BN_usub(ret.get(), sum.get(), ret.get())); 239 EXPECT_BIGNUMS_EQUAL("Sum -u A (r is b)", b.get(), ret.get()); 240 241 ASSERT_TRUE(BN_copy(ret.get(), sum.get())); 242 ASSERT_TRUE(BN_usub(ret.get(), ret.get(), b.get())); 243 EXPECT_BIGNUMS_EQUAL("Sum -u B (r is a)", a.get(), ret.get()); 244 245 ASSERT_TRUE(BN_copy(ret.get(), b.get())); 246 ASSERT_TRUE(BN_usub(ret.get(), sum.get(), ret.get())); 247 EXPECT_BIGNUMS_EQUAL("Sum -u B (r is b)", a.get(), ret.get()); 248 } 249 250 // Test with |BN_add_word| and |BN_sub_word| if |b| is small enough. 251 BN_ULONG b_word = BN_get_word(b.get()); 252 if (!BN_is_negative(b.get()) && b_word != (BN_ULONG)-1) { 253 ASSERT_TRUE(BN_copy(ret.get(), a.get())); 254 ASSERT_TRUE(BN_add_word(ret.get(), b_word)); 255 EXPECT_BIGNUMS_EQUAL("A + B (word)", sum.get(), ret.get()); 256 257 ASSERT_TRUE(BN_copy(ret.get(), sum.get())); 258 ASSERT_TRUE(BN_sub_word(ret.get(), b_word)); 259 EXPECT_BIGNUMS_EQUAL("Sum - B (word)", a.get(), ret.get()); 260 } 261 } 262 263 static void TestLShift1(FileTest *t, BN_CTX *ctx) { 264 bssl::UniquePtr<BIGNUM> a = GetBIGNUM(t, "A"); 265 bssl::UniquePtr<BIGNUM> lshift1 = GetBIGNUM(t, "LShift1"); 266 bssl::UniquePtr<BIGNUM> zero(BN_new()); 267 ASSERT_TRUE(a); 268 ASSERT_TRUE(lshift1); 269 ASSERT_TRUE(zero); 270 271 BN_zero(zero.get()); 272 273 bssl::UniquePtr<BIGNUM> ret(BN_new()), two(BN_new()), remainder(BN_new()); 274 ASSERT_TRUE(ret); 275 ASSERT_TRUE(two); 276 ASSERT_TRUE(remainder); 277 278 ASSERT_TRUE(BN_set_word(two.get(), 2)); 279 ASSERT_TRUE(BN_add(ret.get(), a.get(), a.get())); 280 EXPECT_BIGNUMS_EQUAL("A + A", lshift1.get(), ret.get()); 281 282 ASSERT_TRUE(BN_mul(ret.get(), a.get(), two.get(), ctx)); 283 EXPECT_BIGNUMS_EQUAL("A * 2", lshift1.get(), ret.get()); 284 285 ASSERT_TRUE( 286 BN_div(ret.get(), remainder.get(), lshift1.get(), two.get(), ctx)); 287 EXPECT_BIGNUMS_EQUAL("LShift1 / 2", a.get(), ret.get()); 288 EXPECT_BIGNUMS_EQUAL("LShift1 % 2", zero.get(), remainder.get()); 289 290 ASSERT_TRUE(BN_lshift1(ret.get(), a.get())); 291 EXPECT_BIGNUMS_EQUAL("A << 1", lshift1.get(), ret.get()); 292 293 ASSERT_TRUE(BN_rshift1(ret.get(), lshift1.get())); 294 EXPECT_BIGNUMS_EQUAL("LShift >> 1", a.get(), ret.get()); 295 296 ASSERT_TRUE(BN_rshift1(ret.get(), lshift1.get())); 297 EXPECT_BIGNUMS_EQUAL("LShift >> 1", a.get(), ret.get()); 298 299 // Set the LSB to 1 and test rshift1 again. 300 ASSERT_TRUE(BN_set_bit(lshift1.get(), 0)); 301 ASSERT_TRUE( 302 BN_div(ret.get(), nullptr /* rem */, lshift1.get(), two.get(), ctx)); 303 EXPECT_BIGNUMS_EQUAL("(LShift1 | 1) / 2", a.get(), ret.get()); 304 305 ASSERT_TRUE(BN_rshift1(ret.get(), lshift1.get())); 306 EXPECT_BIGNUMS_EQUAL("(LShift | 1) >> 1", a.get(), ret.get()); 307 } 308 309 static void TestLShift(FileTest *t, BN_CTX *ctx) { 310 bssl::UniquePtr<BIGNUM> a = GetBIGNUM(t, "A"); 311 bssl::UniquePtr<BIGNUM> lshift = GetBIGNUM(t, "LShift"); 312 ASSERT_TRUE(a); 313 ASSERT_TRUE(lshift); 314 int n = 0; 315 ASSERT_TRUE(GetInt(t, &n, "N")); 316 317 bssl::UniquePtr<BIGNUM> ret(BN_new()); 318 ASSERT_TRUE(ret); 319 ASSERT_TRUE(BN_lshift(ret.get(), a.get(), n)); 320 EXPECT_BIGNUMS_EQUAL("A << N", lshift.get(), ret.get()); 321 322 ASSERT_TRUE(BN_rshift(ret.get(), lshift.get(), n)); 323 EXPECT_BIGNUMS_EQUAL("A >> N", a.get(), ret.get()); 324 } 325 326 static void TestRShift(FileTest *t, BN_CTX *ctx) { 327 bssl::UniquePtr<BIGNUM> a = GetBIGNUM(t, "A"); 328 bssl::UniquePtr<BIGNUM> rshift = GetBIGNUM(t, "RShift"); 329 ASSERT_TRUE(a); 330 ASSERT_TRUE(rshift); 331 int n = 0; 332 ASSERT_TRUE(GetInt(t, &n, "N")); 333 334 bssl::UniquePtr<BIGNUM> ret(BN_new()); 335 ASSERT_TRUE(ret); 336 ASSERT_TRUE(BN_rshift(ret.get(), a.get(), n)); 337 EXPECT_BIGNUMS_EQUAL("A >> N", rshift.get(), ret.get()); 338 } 339 340 static void TestSquare(FileTest *t, BN_CTX *ctx) { 341 bssl::UniquePtr<BIGNUM> a = GetBIGNUM(t, "A"); 342 bssl::UniquePtr<BIGNUM> square = GetBIGNUM(t, "Square"); 343 bssl::UniquePtr<BIGNUM> zero(BN_new()); 344 ASSERT_TRUE(a); 345 ASSERT_TRUE(square); 346 ASSERT_TRUE(zero); 347 348 BN_zero(zero.get()); 349 350 bssl::UniquePtr<BIGNUM> ret(BN_new()), remainder(BN_new()); 351 ASSERT_TRUE(ret); 352 ASSERT_TRUE(remainder); 353 ASSERT_TRUE(BN_sqr(ret.get(), a.get(), ctx)); 354 EXPECT_BIGNUMS_EQUAL("A^2", square.get(), ret.get()); 355 356 ASSERT_TRUE(BN_mul(ret.get(), a.get(), a.get(), ctx)); 357 EXPECT_BIGNUMS_EQUAL("A * A", square.get(), ret.get()); 358 359 ASSERT_TRUE(BN_div(ret.get(), remainder.get(), square.get(), a.get(), ctx)); 360 EXPECT_BIGNUMS_EQUAL("Square / A", a.get(), ret.get()); 361 EXPECT_BIGNUMS_EQUAL("Square % A", zero.get(), remainder.get()); 362 363 BN_set_negative(a.get(), 0); 364 ASSERT_TRUE(BN_sqrt(ret.get(), square.get(), ctx)); 365 EXPECT_BIGNUMS_EQUAL("sqrt(Square)", a.get(), ret.get()); 366 367 // BN_sqrt should fail on non-squares and negative numbers. 368 if (!BN_is_zero(square.get())) { 369 bssl::UniquePtr<BIGNUM> tmp(BN_new()); 370 ASSERT_TRUE(tmp); 371 ASSERT_TRUE(BN_copy(tmp.get(), square.get())); 372 BN_set_negative(tmp.get(), 1); 373 374 EXPECT_FALSE(BN_sqrt(ret.get(), tmp.get(), ctx)) 375 << "BN_sqrt succeeded on a negative number"; 376 ERR_clear_error(); 377 378 BN_set_negative(tmp.get(), 0); 379 ASSERT_TRUE(BN_add(tmp.get(), tmp.get(), BN_value_one())); 380 EXPECT_FALSE(BN_sqrt(ret.get(), tmp.get(), ctx)) 381 << "BN_sqrt succeeded on a non-square"; 382 ERR_clear_error(); 383 } 384 } 385 386 static void TestProduct(FileTest *t, BN_CTX *ctx) { 387 bssl::UniquePtr<BIGNUM> a = GetBIGNUM(t, "A"); 388 bssl::UniquePtr<BIGNUM> b = GetBIGNUM(t, "B"); 389 bssl::UniquePtr<BIGNUM> product = GetBIGNUM(t, "Product"); 390 bssl::UniquePtr<BIGNUM> zero(BN_new()); 391 ASSERT_TRUE(a); 392 ASSERT_TRUE(b); 393 ASSERT_TRUE(product); 394 ASSERT_TRUE(zero); 395 396 BN_zero(zero.get()); 397 398 bssl::UniquePtr<BIGNUM> ret(BN_new()), remainder(BN_new()); 399 ASSERT_TRUE(ret); 400 ASSERT_TRUE(remainder); 401 ASSERT_TRUE(BN_mul(ret.get(), a.get(), b.get(), ctx)); 402 EXPECT_BIGNUMS_EQUAL("A * B", product.get(), ret.get()); 403 404 ASSERT_TRUE(BN_div(ret.get(), remainder.get(), product.get(), a.get(), ctx)); 405 EXPECT_BIGNUMS_EQUAL("Product / A", b.get(), ret.get()); 406 EXPECT_BIGNUMS_EQUAL("Product % A", zero.get(), remainder.get()); 407 408 ASSERT_TRUE(BN_div(ret.get(), remainder.get(), product.get(), b.get(), ctx)); 409 EXPECT_BIGNUMS_EQUAL("Product / B", a.get(), ret.get()); 410 EXPECT_BIGNUMS_EQUAL("Product % B", zero.get(), remainder.get()); 411 } 412 413 static void TestQuotient(FileTest *t, BN_CTX *ctx) { 414 bssl::UniquePtr<BIGNUM> a = GetBIGNUM(t, "A"); 415 bssl::UniquePtr<BIGNUM> b = GetBIGNUM(t, "B"); 416 bssl::UniquePtr<BIGNUM> quotient = GetBIGNUM(t, "Quotient"); 417 bssl::UniquePtr<BIGNUM> remainder = GetBIGNUM(t, "Remainder"); 418 ASSERT_TRUE(a); 419 ASSERT_TRUE(b); 420 ASSERT_TRUE(quotient); 421 ASSERT_TRUE(remainder); 422 423 bssl::UniquePtr<BIGNUM> ret(BN_new()), ret2(BN_new()); 424 ASSERT_TRUE(ret); 425 ASSERT_TRUE(ret2); 426 ASSERT_TRUE(BN_div(ret.get(), ret2.get(), a.get(), b.get(), ctx)); 427 EXPECT_BIGNUMS_EQUAL("A / B", quotient.get(), ret.get()); 428 EXPECT_BIGNUMS_EQUAL("A % B", remainder.get(), ret2.get()); 429 430 ASSERT_TRUE(BN_mul(ret.get(), quotient.get(), b.get(), ctx)); 431 ASSERT_TRUE(BN_add(ret.get(), ret.get(), remainder.get())); 432 EXPECT_BIGNUMS_EQUAL("Quotient * B + Remainder", a.get(), ret.get()); 433 434 // Test with |BN_mod_word| and |BN_div_word| if the divisor is small enough. 435 BN_ULONG b_word = BN_get_word(b.get()); 436 if (!BN_is_negative(b.get()) && b_word != (BN_ULONG)-1) { 437 BN_ULONG remainder_word = BN_get_word(remainder.get()); 438 ASSERT_NE(remainder_word, (BN_ULONG)-1); 439 ASSERT_TRUE(BN_copy(ret.get(), a.get())); 440 BN_ULONG ret_word = BN_div_word(ret.get(), b_word); 441 EXPECT_EQ(remainder_word, ret_word); 442 EXPECT_BIGNUMS_EQUAL("A / B (word)", quotient.get(), ret.get()); 443 444 ret_word = BN_mod_word(a.get(), b_word); 445 EXPECT_EQ(remainder_word, ret_word); 446 } 447 448 // Test BN_nnmod. 449 if (!BN_is_negative(b.get())) { 450 bssl::UniquePtr<BIGNUM> nnmod(BN_new()); 451 ASSERT_TRUE(nnmod); 452 ASSERT_TRUE(BN_copy(nnmod.get(), remainder.get())); 453 if (BN_is_negative(nnmod.get())) { 454 ASSERT_TRUE(BN_add(nnmod.get(), nnmod.get(), b.get())); 455 } 456 ASSERT_TRUE(BN_nnmod(ret.get(), a.get(), b.get(), ctx)); 457 EXPECT_BIGNUMS_EQUAL("A % B (non-negative)", nnmod.get(), ret.get()); 458 } 459 } 460 461 static void TestModMul(FileTest *t, BN_CTX *ctx) { 462 bssl::UniquePtr<BIGNUM> a = GetBIGNUM(t, "A"); 463 bssl::UniquePtr<BIGNUM> b = GetBIGNUM(t, "B"); 464 bssl::UniquePtr<BIGNUM> m = GetBIGNUM(t, "M"); 465 bssl::UniquePtr<BIGNUM> mod_mul = GetBIGNUM(t, "ModMul"); 466 ASSERT_TRUE(a); 467 ASSERT_TRUE(b); 468 ASSERT_TRUE(m); 469 ASSERT_TRUE(mod_mul); 470 471 bssl::UniquePtr<BIGNUM> ret(BN_new()); 472 ASSERT_TRUE(ret); 473 ASSERT_TRUE(BN_mod_mul(ret.get(), a.get(), b.get(), m.get(), ctx)); 474 EXPECT_BIGNUMS_EQUAL("A * B (mod M)", mod_mul.get(), ret.get()); 475 476 if (BN_is_odd(m.get())) { 477 // Reduce |a| and |b| and test the Montgomery version. 478 bssl::UniquePtr<BN_MONT_CTX> mont(BN_MONT_CTX_new()); 479 bssl::UniquePtr<BIGNUM> a_tmp(BN_new()), b_tmp(BN_new()); 480 ASSERT_TRUE(mont); 481 ASSERT_TRUE(a_tmp); 482 ASSERT_TRUE(b_tmp); 483 ASSERT_TRUE(BN_MONT_CTX_set(mont.get(), m.get(), ctx)); 484 ASSERT_TRUE(BN_nnmod(a_tmp.get(), a.get(), m.get(), ctx)); 485 ASSERT_TRUE(BN_nnmod(b_tmp.get(), b.get(), m.get(), ctx)); 486 ASSERT_TRUE(BN_to_montgomery(a_tmp.get(), a_tmp.get(), mont.get(), ctx)); 487 ASSERT_TRUE(BN_to_montgomery(b_tmp.get(), b_tmp.get(), mont.get(), ctx)); 488 ASSERT_TRUE(BN_mod_mul_montgomery(ret.get(), a_tmp.get(), b_tmp.get(), 489 mont.get(), ctx)); 490 ASSERT_TRUE(BN_from_montgomery(ret.get(), ret.get(), mont.get(), ctx)); 491 EXPECT_BIGNUMS_EQUAL("A * B (mod M) (Montgomery)", mod_mul.get(), 492 ret.get()); 493 } 494 } 495 496 static void TestModSquare(FileTest *t, BN_CTX *ctx) { 497 bssl::UniquePtr<BIGNUM> a = GetBIGNUM(t, "A"); 498 bssl::UniquePtr<BIGNUM> m = GetBIGNUM(t, "M"); 499 bssl::UniquePtr<BIGNUM> mod_square = GetBIGNUM(t, "ModSquare"); 500 ASSERT_TRUE(a); 501 ASSERT_TRUE(m); 502 ASSERT_TRUE(mod_square); 503 504 bssl::UniquePtr<BIGNUM> a_copy(BN_new()); 505 bssl::UniquePtr<BIGNUM> ret(BN_new()); 506 ASSERT_TRUE(ret); 507 ASSERT_TRUE(a_copy); 508 ASSERT_TRUE(BN_mod_mul(ret.get(), a.get(), a.get(), m.get(), ctx)); 509 EXPECT_BIGNUMS_EQUAL("A * A (mod M)", mod_square.get(), ret.get()); 510 511 // Repeat the operation with |a_copy|. 512 ASSERT_TRUE(BN_copy(a_copy.get(), a.get())); 513 ASSERT_TRUE(BN_mod_mul(ret.get(), a.get(), a_copy.get(), m.get(), ctx)); 514 EXPECT_BIGNUMS_EQUAL("A * A_copy (mod M)", mod_square.get(), ret.get()); 515 516 if (BN_is_odd(m.get())) { 517 // Reduce |a| and test the Montgomery version. 518 bssl::UniquePtr<BN_MONT_CTX> mont(BN_MONT_CTX_new()); 519 bssl::UniquePtr<BIGNUM> a_tmp(BN_new()); 520 ASSERT_TRUE(mont); 521 ASSERT_TRUE(a_tmp); 522 ASSERT_TRUE(BN_MONT_CTX_set(mont.get(), m.get(), ctx)); 523 ASSERT_TRUE(BN_nnmod(a_tmp.get(), a.get(), m.get(), ctx)); 524 ASSERT_TRUE(BN_to_montgomery(a_tmp.get(), a_tmp.get(), mont.get(), ctx)); 525 ASSERT_TRUE(BN_mod_mul_montgomery(ret.get(), a_tmp.get(), a_tmp.get(), 526 mont.get(), ctx)); 527 ASSERT_TRUE(BN_from_montgomery(ret.get(), ret.get(), mont.get(), ctx)); 528 EXPECT_BIGNUMS_EQUAL("A * A (mod M) (Montgomery)", mod_square.get(), 529 ret.get()); 530 531 // Repeat the operation with |a_copy|. 532 ASSERT_TRUE(BN_copy(a_copy.get(), a_tmp.get())); 533 ASSERT_TRUE(BN_mod_mul_montgomery(ret.get(), a_tmp.get(), a_copy.get(), 534 mont.get(), ctx)); 535 ASSERT_TRUE(BN_from_montgomery(ret.get(), ret.get(), mont.get(), ctx)); 536 EXPECT_BIGNUMS_EQUAL("A * A_copy (mod M) (Montgomery)", mod_square.get(), 537 ret.get()); 538 } 539 } 540 541 static void TestModExp(FileTest *t, BN_CTX *ctx) { 542 bssl::UniquePtr<BIGNUM> a = GetBIGNUM(t, "A"); 543 bssl::UniquePtr<BIGNUM> e = GetBIGNUM(t, "E"); 544 bssl::UniquePtr<BIGNUM> m = GetBIGNUM(t, "M"); 545 bssl::UniquePtr<BIGNUM> mod_exp = GetBIGNUM(t, "ModExp"); 546 ASSERT_TRUE(a); 547 ASSERT_TRUE(e); 548 ASSERT_TRUE(m); 549 ASSERT_TRUE(mod_exp); 550 551 bssl::UniquePtr<BIGNUM> ret(BN_new()); 552 ASSERT_TRUE(ret); 553 ASSERT_TRUE(BN_mod_exp(ret.get(), a.get(), e.get(), m.get(), ctx)); 554 EXPECT_BIGNUMS_EQUAL("A ^ E (mod M)", mod_exp.get(), ret.get()); 555 556 if (BN_is_odd(m.get())) { 557 ASSERT_TRUE( 558 BN_mod_exp_mont(ret.get(), a.get(), e.get(), m.get(), ctx, NULL)); 559 EXPECT_BIGNUMS_EQUAL("A ^ E (mod M) (Montgomery)", mod_exp.get(), 560 ret.get()); 561 562 ASSERT_TRUE(BN_mod_exp_mont_consttime(ret.get(), a.get(), e.get(), m.get(), 563 ctx, NULL)); 564 EXPECT_BIGNUMS_EQUAL("A ^ E (mod M) (constant-time)", mod_exp.get(), 565 ret.get()); 566 } 567 } 568 569 static void TestExp(FileTest *t, BN_CTX *ctx) { 570 bssl::UniquePtr<BIGNUM> a = GetBIGNUM(t, "A"); 571 bssl::UniquePtr<BIGNUM> e = GetBIGNUM(t, "E"); 572 bssl::UniquePtr<BIGNUM> exp = GetBIGNUM(t, "Exp"); 573 ASSERT_TRUE(a); 574 ASSERT_TRUE(e); 575 ASSERT_TRUE(exp); 576 577 bssl::UniquePtr<BIGNUM> ret(BN_new()); 578 ASSERT_TRUE(ret); 579 ASSERT_TRUE(BN_exp(ret.get(), a.get(), e.get(), ctx)); 580 EXPECT_BIGNUMS_EQUAL("A ^ E", exp.get(), ret.get()); 581 } 582 583 static void TestModSqrt(FileTest *t, BN_CTX *ctx) { 584 bssl::UniquePtr<BIGNUM> a = GetBIGNUM(t, "A"); 585 bssl::UniquePtr<BIGNUM> p = GetBIGNUM(t, "P"); 586 bssl::UniquePtr<BIGNUM> mod_sqrt = GetBIGNUM(t, "ModSqrt"); 587 bssl::UniquePtr<BIGNUM> mod_sqrt2(BN_new()); 588 ASSERT_TRUE(a); 589 ASSERT_TRUE(p); 590 ASSERT_TRUE(mod_sqrt); 591 ASSERT_TRUE(mod_sqrt2); 592 // There are two possible answers. 593 ASSERT_TRUE(BN_sub(mod_sqrt2.get(), p.get(), mod_sqrt.get())); 594 595 // -0 is 0, not P. 596 if (BN_is_zero(mod_sqrt.get())) { 597 BN_zero(mod_sqrt2.get()); 598 } 599 600 bssl::UniquePtr<BIGNUM> ret(BN_new()); 601 ASSERT_TRUE(ret); 602 ASSERT_TRUE(BN_mod_sqrt(ret.get(), a.get(), p.get(), ctx)); 603 if (BN_cmp(ret.get(), mod_sqrt2.get()) != 0) { 604 EXPECT_BIGNUMS_EQUAL("sqrt(A) (mod P)", mod_sqrt.get(), ret.get()); 605 } 606 } 607 608 static void TestNotModSquare(FileTest *t, BN_CTX *ctx) { 609 bssl::UniquePtr<BIGNUM> not_mod_square = GetBIGNUM(t, "NotModSquare"); 610 bssl::UniquePtr<BIGNUM> p = GetBIGNUM(t, "P"); 611 bssl::UniquePtr<BIGNUM> ret(BN_new()); 612 ASSERT_TRUE(not_mod_square); 613 ASSERT_TRUE(p); 614 ASSERT_TRUE(ret); 615 616 EXPECT_FALSE(BN_mod_sqrt(ret.get(), not_mod_square.get(), p.get(), ctx)) 617 << "BN_mod_sqrt unexpectedly succeeded."; 618 619 uint32_t err = ERR_peek_error(); 620 EXPECT_EQ(ERR_LIB_BN, ERR_GET_LIB(err)); 621 EXPECT_EQ(BN_R_NOT_A_SQUARE, ERR_GET_REASON(err)); 622 ERR_clear_error(); 623 } 624 625 static void TestModInv(FileTest *t, BN_CTX *ctx) { 626 bssl::UniquePtr<BIGNUM> a = GetBIGNUM(t, "A"); 627 bssl::UniquePtr<BIGNUM> m = GetBIGNUM(t, "M"); 628 bssl::UniquePtr<BIGNUM> mod_inv = GetBIGNUM(t, "ModInv"); 629 ASSERT_TRUE(a); 630 ASSERT_TRUE(m); 631 ASSERT_TRUE(mod_inv); 632 633 bssl::UniquePtr<BIGNUM> ret(BN_new()); 634 ASSERT_TRUE(ret); 635 ASSERT_TRUE(BN_mod_inverse(ret.get(), a.get(), m.get(), ctx)); 636 EXPECT_BIGNUMS_EQUAL("inv(A) (mod M)", mod_inv.get(), ret.get()); 637 } 638 639 class BNTest : public testing::Test { 640 protected: 641 void SetUp() override { 642 ctx_.reset(BN_CTX_new()); 643 ASSERT_TRUE(ctx_); 644 } 645 646 BN_CTX *ctx() { return ctx_.get(); } 647 648 private: 649 bssl::UniquePtr<BN_CTX> ctx_; 650 }; 651 652 TEST_F(BNTest, TestVectors) { 653 static const struct { 654 const char *name; 655 void (*func)(FileTest *t, BN_CTX *ctx); 656 } kTests[] = { 657 {"Sum", TestSum}, 658 {"LShift1", TestLShift1}, 659 {"LShift", TestLShift}, 660 {"RShift", TestRShift}, 661 {"Square", TestSquare}, 662 {"Product", TestProduct}, 663 {"Quotient", TestQuotient}, 664 {"ModMul", TestModMul}, 665 {"ModSquare", TestModSquare}, 666 {"ModExp", TestModExp}, 667 {"Exp", TestExp}, 668 {"ModSqrt", TestModSqrt}, 669 {"NotModSquare", TestNotModSquare}, 670 {"ModInv", TestModInv}, 671 }; 672 673 FileTestGTest("crypto/fipsmodule/bn/bn_tests.txt", [&](FileTest *t) { 674 for (const auto &test : kTests) { 675 if (t->GetType() == test.name) { 676 test.func(t, ctx()); 677 return; 678 } 679 } 680 FAIL() << "Unknown test type: " << t->GetType(); 681 }); 682 } 683 684 TEST_F(BNTest, BN2BinPadded) { 685 uint8_t zeros[256], out[256], reference[128]; 686 687 OPENSSL_memset(zeros, 0, sizeof(zeros)); 688 689 // Test edge case at 0. 690 bssl::UniquePtr<BIGNUM> n(BN_new()); 691 ASSERT_TRUE(n); 692 ASSERT_TRUE(BN_bn2bin_padded(NULL, 0, n.get())); 693 694 OPENSSL_memset(out, -1, sizeof(out)); 695 ASSERT_TRUE(BN_bn2bin_padded(out, sizeof(out), n.get())); 696 EXPECT_EQ(Bytes(zeros), Bytes(out)); 697 698 // Test a random numbers at various byte lengths. 699 for (size_t bytes = 128 - 7; bytes <= 128; bytes++) { 700 ASSERT_TRUE( 701 BN_rand(n.get(), bytes * 8, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY)); 702 ASSERT_EQ(bytes, BN_num_bytes(n.get())); 703 ASSERT_EQ(bytes, BN_bn2bin(n.get(), reference)); 704 705 // Empty buffer should fail. 706 EXPECT_FALSE(BN_bn2bin_padded(NULL, 0, n.get())); 707 708 // One byte short should fail. 709 EXPECT_FALSE(BN_bn2bin_padded(out, bytes - 1, n.get())); 710 711 // Exactly right size should encode. 712 ASSERT_TRUE(BN_bn2bin_padded(out, bytes, n.get())); 713 EXPECT_EQ(Bytes(reference, bytes), Bytes(out, bytes)); 714 715 // Pad up one byte extra. 716 ASSERT_TRUE(BN_bn2bin_padded(out, bytes + 1, n.get())); 717 EXPECT_EQ(0u, out[0]); 718 EXPECT_EQ(Bytes(reference, bytes), Bytes(out + 1, bytes)); 719 720 // Pad up to 256. 721 ASSERT_TRUE(BN_bn2bin_padded(out, sizeof(out), n.get())); 722 EXPECT_EQ(Bytes(zeros, sizeof(out) - bytes), 723 Bytes(out, sizeof(out) - bytes)); 724 EXPECT_EQ(Bytes(reference, bytes), Bytes(out + sizeof(out) - bytes, bytes)); 725 } 726 } 727 728 TEST_F(BNTest, LittleEndian) { 729 bssl::UniquePtr<BIGNUM> x(BN_new()); 730 bssl::UniquePtr<BIGNUM> y(BN_new()); 731 ASSERT_TRUE(x); 732 ASSERT_TRUE(y); 733 734 // Test edge case at 0. Fill |out| with garbage to ensure |BN_bn2le_padded| 735 // wrote the result. 736 uint8_t out[256], zeros[256]; 737 OPENSSL_memset(out, -1, sizeof(out)); 738 OPENSSL_memset(zeros, 0, sizeof(zeros)); 739 ASSERT_TRUE(BN_bn2le_padded(out, sizeof(out), x.get())); 740 EXPECT_EQ(Bytes(zeros), Bytes(out)); 741 742 ASSERT_TRUE(BN_le2bn(out, sizeof(out), y.get())); 743 EXPECT_BIGNUMS_EQUAL("BN_le2bn round-trip", x.get(), y.get()); 744 745 // Test random numbers at various byte lengths. 746 for (size_t bytes = 128 - 7; bytes <= 128; bytes++) { 747 ASSERT_TRUE( 748 BN_rand(x.get(), bytes * 8, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY)); 749 750 // Fill |out| with garbage to ensure |BN_bn2le_padded| wrote the result. 751 OPENSSL_memset(out, -1, sizeof(out)); 752 ASSERT_TRUE(BN_bn2le_padded(out, sizeof(out), x.get())); 753 754 // Compute the expected value by reversing the big-endian output. 755 uint8_t expected[sizeof(out)]; 756 ASSERT_TRUE(BN_bn2bin_padded(expected, sizeof(expected), x.get())); 757 for (size_t i = 0; i < sizeof(expected) / 2; i++) { 758 uint8_t tmp = expected[i]; 759 expected[i] = expected[sizeof(expected) - 1 - i]; 760 expected[sizeof(expected) - 1 - i] = tmp; 761 } 762 763 EXPECT_EQ(Bytes(out), Bytes(expected)); 764 765 // Make sure the decoding produces the same BIGNUM. 766 ASSERT_TRUE(BN_le2bn(out, bytes, y.get())); 767 EXPECT_BIGNUMS_EQUAL("BN_le2bn round-trip", x.get(), y.get()); 768 } 769 } 770 771 static int DecimalToBIGNUM(bssl::UniquePtr<BIGNUM> *out, const char *in) { 772 BIGNUM *raw = NULL; 773 int ret = BN_dec2bn(&raw, in); 774 out->reset(raw); 775 return ret; 776 } 777 778 TEST_F(BNTest, Dec2BN) { 779 bssl::UniquePtr<BIGNUM> bn; 780 int ret = DecimalToBIGNUM(&bn, "0"); 781 EXPECT_EQ(1, ret); 782 EXPECT_TRUE(BN_is_zero(bn.get())); 783 EXPECT_FALSE(BN_is_negative(bn.get())); 784 785 ret = DecimalToBIGNUM(&bn, "256"); 786 EXPECT_EQ(3, ret); 787 EXPECT_TRUE(BN_is_word(bn.get(), 256)); 788 EXPECT_FALSE(BN_is_negative(bn.get())); 789 790 ret = DecimalToBIGNUM(&bn, "-42"); 791 EXPECT_EQ(3, ret); 792 EXPECT_TRUE(BN_abs_is_word(bn.get(), 42)); 793 EXPECT_TRUE(BN_is_negative(bn.get())); 794 795 ret = DecimalToBIGNUM(&bn, "-0"); 796 EXPECT_EQ(2, ret); 797 EXPECT_TRUE(BN_is_zero(bn.get())); 798 EXPECT_FALSE(BN_is_negative(bn.get())); 799 800 ret = DecimalToBIGNUM(&bn, "42trailing garbage is ignored"); 801 EXPECT_EQ(2, ret); 802 EXPECT_TRUE(BN_abs_is_word(bn.get(), 42)); 803 EXPECT_FALSE(BN_is_negative(bn.get())); 804 } 805 806 TEST_F(BNTest, Hex2BN) { 807 bssl::UniquePtr<BIGNUM> bn; 808 int ret = HexToBIGNUM(&bn, "0"); 809 EXPECT_EQ(1, ret); 810 EXPECT_TRUE(BN_is_zero(bn.get())); 811 EXPECT_FALSE(BN_is_negative(bn.get())); 812 813 ret = HexToBIGNUM(&bn, "256"); 814 EXPECT_EQ(3, ret); 815 EXPECT_TRUE(BN_is_word(bn.get(), 0x256)); 816 EXPECT_FALSE(BN_is_negative(bn.get())); 817 818 ret = HexToBIGNUM(&bn, "-42"); 819 EXPECT_EQ(3, ret); 820 EXPECT_TRUE(BN_abs_is_word(bn.get(), 0x42)); 821 EXPECT_TRUE(BN_is_negative(bn.get())); 822 823 ret = HexToBIGNUM(&bn, "-0"); 824 EXPECT_EQ(2, ret); 825 EXPECT_TRUE(BN_is_zero(bn.get())); 826 EXPECT_FALSE(BN_is_negative(bn.get())); 827 828 ret = HexToBIGNUM(&bn, "abctrailing garbage is ignored"); 829 EXPECT_EQ(3, ret); 830 EXPECT_TRUE(BN_is_word(bn.get(), 0xabc)); 831 EXPECT_FALSE(BN_is_negative(bn.get())); 832 } 833 834 static bssl::UniquePtr<BIGNUM> ASCIIToBIGNUM(const char *in) { 835 BIGNUM *raw = NULL; 836 if (!BN_asc2bn(&raw, in)) { 837 return nullptr; 838 } 839 return bssl::UniquePtr<BIGNUM>(raw); 840 } 841 842 TEST_F(BNTest, ASC2BN) { 843 bssl::UniquePtr<BIGNUM> bn = ASCIIToBIGNUM("0"); 844 ASSERT_TRUE(bn); 845 EXPECT_TRUE(BN_is_zero(bn.get())); 846 EXPECT_FALSE(BN_is_negative(bn.get())); 847 848 bn = ASCIIToBIGNUM("256"); 849 ASSERT_TRUE(bn); 850 EXPECT_TRUE(BN_is_word(bn.get(), 256)); 851 EXPECT_FALSE(BN_is_negative(bn.get())); 852 853 bn = ASCIIToBIGNUM("-42"); 854 ASSERT_TRUE(bn); 855 EXPECT_TRUE(BN_abs_is_word(bn.get(), 42)); 856 EXPECT_TRUE(BN_is_negative(bn.get())); 857 858 bn = ASCIIToBIGNUM("0x1234"); 859 ASSERT_TRUE(bn); 860 EXPECT_TRUE(BN_is_word(bn.get(), 0x1234)); 861 EXPECT_FALSE(BN_is_negative(bn.get())); 862 863 bn = ASCIIToBIGNUM("0X1234"); 864 ASSERT_TRUE(bn); 865 EXPECT_TRUE(BN_is_word(bn.get(), 0x1234)); 866 EXPECT_FALSE(BN_is_negative(bn.get())); 867 868 bn = ASCIIToBIGNUM("-0xabcd"); 869 ASSERT_TRUE(bn); 870 EXPECT_TRUE(BN_abs_is_word(bn.get(), 0xabcd)); 871 EXPECT_FALSE(!BN_is_negative(bn.get())); 872 873 bn = ASCIIToBIGNUM("-0"); 874 ASSERT_TRUE(bn); 875 EXPECT_TRUE(BN_is_zero(bn.get())); 876 EXPECT_FALSE(BN_is_negative(bn.get())); 877 878 bn = ASCIIToBIGNUM("123trailing garbage is ignored"); 879 ASSERT_TRUE(bn); 880 EXPECT_TRUE(BN_is_word(bn.get(), 123)); 881 EXPECT_FALSE(BN_is_negative(bn.get())); 882 } 883 884 struct MPITest { 885 const char *base10; 886 const char *mpi; 887 size_t mpi_len; 888 }; 889 890 static const MPITest kMPITests[] = { 891 { "0", "\x00\x00\x00\x00", 4 }, 892 { "1", "\x00\x00\x00\x01\x01", 5 }, 893 { "-1", "\x00\x00\x00\x01\x81", 5 }, 894 { "128", "\x00\x00\x00\x02\x00\x80", 6 }, 895 { "256", "\x00\x00\x00\x02\x01\x00", 6 }, 896 { "-256", "\x00\x00\x00\x02\x81\x00", 6 }, 897 }; 898 899 TEST_F(BNTest, MPI) { 900 uint8_t scratch[8]; 901 902 for (const auto &test : kMPITests) { 903 SCOPED_TRACE(test.base10); 904 bssl::UniquePtr<BIGNUM> bn(ASCIIToBIGNUM(test.base10)); 905 ASSERT_TRUE(bn); 906 907 const size_t mpi_len = BN_bn2mpi(bn.get(), NULL); 908 ASSERT_LE(mpi_len, sizeof(scratch)) << "MPI size is too large to test"; 909 910 const size_t mpi_len2 = BN_bn2mpi(bn.get(), scratch); 911 EXPECT_EQ(mpi_len, mpi_len2); 912 EXPECT_EQ(Bytes(test.mpi, test.mpi_len), Bytes(scratch, mpi_len)); 913 914 bssl::UniquePtr<BIGNUM> bn2(BN_mpi2bn(scratch, mpi_len, NULL)); 915 ASSERT_TRUE(bn2) << "failed to parse"; 916 EXPECT_BIGNUMS_EQUAL("BN_mpi2bn", bn.get(), bn2.get()); 917 } 918 } 919 920 TEST_F(BNTest, Rand) { 921 bssl::UniquePtr<BIGNUM> bn(BN_new()); 922 ASSERT_TRUE(bn); 923 924 // Test BN_rand accounts for degenerate cases with |top| and |bottom| 925 // parameters. 926 ASSERT_TRUE(BN_rand(bn.get(), 0, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY)); 927 EXPECT_TRUE(BN_is_zero(bn.get())); 928 ASSERT_TRUE(BN_rand(bn.get(), 0, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD)); 929 EXPECT_TRUE(BN_is_zero(bn.get())); 930 931 ASSERT_TRUE(BN_rand(bn.get(), 1, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY)); 932 EXPECT_TRUE(BN_is_word(bn.get(), 1)); 933 ASSERT_TRUE(BN_rand(bn.get(), 1, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ANY)); 934 EXPECT_TRUE(BN_is_word(bn.get(), 1)); 935 ASSERT_TRUE(BN_rand(bn.get(), 1, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ODD)); 936 EXPECT_TRUE(BN_is_word(bn.get(), 1)); 937 938 ASSERT_TRUE(BN_rand(bn.get(), 2, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ANY)); 939 EXPECT_TRUE(BN_is_word(bn.get(), 3)); 940 } 941 942 TEST_F(BNTest, RandRange) { 943 bssl::UniquePtr<BIGNUM> bn(BN_new()), six(BN_new()); 944 ASSERT_TRUE(bn); 945 ASSERT_TRUE(six); 946 ASSERT_TRUE(BN_set_word(six.get(), 6)); 947 948 // Generate 1,000 random numbers and ensure they all stay in range. This check 949 // may flakily pass when it should have failed but will not flakily fail. 950 bool seen[6] = {false, false, false, false, false}; 951 for (unsigned i = 0; i < 1000; i++) { 952 SCOPED_TRACE(i); 953 ASSERT_TRUE(BN_rand_range_ex(bn.get(), 1, six.get())); 954 955 BN_ULONG word = BN_get_word(bn.get()); 956 if (BN_is_negative(bn.get()) || 957 word < 1 || 958 word >= 6) { 959 FAIL() << "BN_rand_range_ex generated invalid value: " << word; 960 } 961 962 seen[word] = true; 963 } 964 965 // Test that all numbers were accounted for. Note this test is probabilistic 966 // and may flakily fail when it should have passed. As an upper-bound on the 967 // failure probability, we'll never see any one number with probability 968 // (4/5)^1000, so the probability of failure is at most 5*(4/5)^1000. This is 969 // around 1 in 2^320. 970 for (unsigned i = 1; i < 6; i++) { 971 EXPECT_TRUE(seen[i]) << "BN_rand_range failed to generated " << i; 972 } 973 } 974 975 struct ASN1Test { 976 const char *value_ascii; 977 const char *der; 978 size_t der_len; 979 }; 980 981 static const ASN1Test kASN1Tests[] = { 982 {"0", "\x02\x01\x00", 3}, 983 {"1", "\x02\x01\x01", 3}, 984 {"127", "\x02\x01\x7f", 3}, 985 {"128", "\x02\x02\x00\x80", 4}, 986 {"0xdeadbeef", "\x02\x05\x00\xde\xad\xbe\xef", 7}, 987 {"0x0102030405060708", 988 "\x02\x08\x01\x02\x03\x04\x05\x06\x07\x08", 10}, 989 {"0xffffffffffffffff", 990 "\x02\x09\x00\xff\xff\xff\xff\xff\xff\xff\xff", 11}, 991 }; 992 993 struct ASN1InvalidTest { 994 const char *der; 995 size_t der_len; 996 }; 997 998 static const ASN1InvalidTest kASN1InvalidTests[] = { 999 // Bad tag. 1000 {"\x03\x01\x00", 3}, 1001 // Empty contents. 1002 {"\x02\x00", 2}, 1003 }; 1004 1005 // kASN1BuggyTests contains incorrect encodings and the corresponding, expected 1006 // results of |BN_parse_asn1_unsigned_buggy| given that input. 1007 static const ASN1Test kASN1BuggyTests[] = { 1008 // Negative numbers. 1009 {"128", "\x02\x01\x80", 3}, 1010 {"255", "\x02\x01\xff", 3}, 1011 // Unnecessary leading zeros. 1012 {"1", "\x02\x02\x00\x01", 4}, 1013 }; 1014 1015 TEST_F(BNTest, ASN1) { 1016 for (const ASN1Test &test : kASN1Tests) { 1017 SCOPED_TRACE(test.value_ascii); 1018 bssl::UniquePtr<BIGNUM> bn = ASCIIToBIGNUM(test.value_ascii); 1019 ASSERT_TRUE(bn); 1020 1021 // Test that the input is correctly parsed. 1022 bssl::UniquePtr<BIGNUM> bn2(BN_new()); 1023 ASSERT_TRUE(bn2); 1024 CBS cbs; 1025 CBS_init(&cbs, reinterpret_cast<const uint8_t*>(test.der), test.der_len); 1026 ASSERT_TRUE(BN_parse_asn1_unsigned(&cbs, bn2.get())); 1027 EXPECT_EQ(0u, CBS_len(&cbs)); 1028 EXPECT_BIGNUMS_EQUAL("decode ASN.1", bn.get(), bn2.get()); 1029 1030 // Test the value serializes correctly. 1031 bssl::ScopedCBB cbb; 1032 uint8_t *der; 1033 size_t der_len; 1034 ASSERT_TRUE(CBB_init(cbb.get(), 0)); 1035 ASSERT_TRUE(BN_marshal_asn1(cbb.get(), bn.get())); 1036 ASSERT_TRUE(CBB_finish(cbb.get(), &der, &der_len)); 1037 bssl::UniquePtr<uint8_t> delete_der(der); 1038 EXPECT_EQ(Bytes(test.der, test.der_len), Bytes(der, der_len)); 1039 1040 // |BN_parse_asn1_unsigned_buggy| parses all valid input. 1041 CBS_init(&cbs, reinterpret_cast<const uint8_t*>(test.der), test.der_len); 1042 ASSERT_TRUE(BN_parse_asn1_unsigned_buggy(&cbs, bn2.get())); 1043 EXPECT_EQ(0u, CBS_len(&cbs)); 1044 EXPECT_BIGNUMS_EQUAL("decode ASN.1 buggy", bn.get(), bn2.get()); 1045 } 1046 1047 for (const ASN1InvalidTest &test : kASN1InvalidTests) { 1048 SCOPED_TRACE(Bytes(test.der, test.der_len));; 1049 bssl::UniquePtr<BIGNUM> bn(BN_new()); 1050 ASSERT_TRUE(bn); 1051 CBS cbs; 1052 CBS_init(&cbs, reinterpret_cast<const uint8_t *>(test.der), test.der_len); 1053 EXPECT_FALSE(BN_parse_asn1_unsigned(&cbs, bn.get())) 1054 << "Parsed invalid input."; 1055 ERR_clear_error(); 1056 1057 // All tests in kASN1InvalidTests are also rejected by 1058 // |BN_parse_asn1_unsigned_buggy|. 1059 CBS_init(&cbs, reinterpret_cast<const uint8_t*>(test.der), test.der_len); 1060 EXPECT_FALSE(BN_parse_asn1_unsigned_buggy(&cbs, bn.get())) 1061 << "Parsed invalid input."; 1062 ERR_clear_error(); 1063 } 1064 1065 for (const ASN1Test &test : kASN1BuggyTests) { 1066 SCOPED_TRACE(Bytes(test.der, test.der_len)); 1067 1068 // These broken encodings are rejected by |BN_parse_asn1_unsigned|. 1069 bssl::UniquePtr<BIGNUM> bn(BN_new()); 1070 ASSERT_TRUE(bn); 1071 CBS cbs; 1072 CBS_init(&cbs, reinterpret_cast<const uint8_t*>(test.der), test.der_len); 1073 EXPECT_FALSE(BN_parse_asn1_unsigned(&cbs, bn.get())) 1074 << "Parsed invalid input."; 1075 ERR_clear_error(); 1076 1077 // However |BN_parse_asn1_unsigned_buggy| accepts them. 1078 bssl::UniquePtr<BIGNUM> bn2 = ASCIIToBIGNUM(test.value_ascii); 1079 ASSERT_TRUE(bn2); 1080 1081 CBS_init(&cbs, reinterpret_cast<const uint8_t*>(test.der), test.der_len); 1082 ASSERT_TRUE(BN_parse_asn1_unsigned_buggy(&cbs, bn.get())); 1083 EXPECT_EQ(0u, CBS_len(&cbs)); 1084 EXPECT_BIGNUMS_EQUAL("decode ASN.1 buggy", bn2.get(), bn.get()); 1085 } 1086 1087 // Serializing negative numbers is not supported. 1088 bssl::UniquePtr<BIGNUM> bn = ASCIIToBIGNUM("-1"); 1089 ASSERT_TRUE(bn); 1090 bssl::ScopedCBB cbb; 1091 ASSERT_TRUE(CBB_init(cbb.get(), 0)); 1092 EXPECT_FALSE(BN_marshal_asn1(cbb.get(), bn.get())) 1093 << "Serialized negative number."; 1094 ERR_clear_error(); 1095 } 1096 1097 TEST_F(BNTest, NegativeZero) { 1098 bssl::UniquePtr<BIGNUM> a(BN_new()); 1099 bssl::UniquePtr<BIGNUM> b(BN_new()); 1100 bssl::UniquePtr<BIGNUM> c(BN_new()); 1101 ASSERT_TRUE(a); 1102 ASSERT_TRUE(b); 1103 ASSERT_TRUE(c); 1104 1105 // Test that BN_mul never gives negative zero. 1106 ASSERT_TRUE(BN_set_word(a.get(), 1)); 1107 BN_set_negative(a.get(), 1); 1108 BN_zero(b.get()); 1109 ASSERT_TRUE(BN_mul(c.get(), a.get(), b.get(), ctx())); 1110 EXPECT_TRUE(BN_is_zero(c.get())); 1111 EXPECT_FALSE(BN_is_negative(c.get())); 1112 1113 bssl::UniquePtr<BIGNUM> numerator(BN_new()), denominator(BN_new()); 1114 ASSERT_TRUE(numerator); 1115 ASSERT_TRUE(denominator); 1116 1117 // Test that BN_div never gives negative zero in the quotient. 1118 ASSERT_TRUE(BN_set_word(numerator.get(), 1)); 1119 ASSERT_TRUE(BN_set_word(denominator.get(), 2)); 1120 BN_set_negative(numerator.get(), 1); 1121 ASSERT_TRUE( 1122 BN_div(a.get(), b.get(), numerator.get(), denominator.get(), ctx())); 1123 EXPECT_TRUE(BN_is_zero(a.get())); 1124 EXPECT_FALSE(BN_is_negative(a.get())); 1125 1126 // Test that BN_div never gives negative zero in the remainder. 1127 ASSERT_TRUE(BN_set_word(denominator.get(), 1)); 1128 ASSERT_TRUE( 1129 BN_div(a.get(), b.get(), numerator.get(), denominator.get(), ctx())); 1130 EXPECT_TRUE(BN_is_zero(b.get())); 1131 EXPECT_FALSE(BN_is_negative(b.get())); 1132 1133 // Test that BN_set_negative will not produce a negative zero. 1134 BN_zero(a.get()); 1135 BN_set_negative(a.get(), 1); 1136 EXPECT_FALSE(BN_is_negative(a.get())); 1137 1138 // Test that forcibly creating a negative zero does not break |BN_bn2hex| or 1139 // |BN_bn2dec|. 1140 a->neg = 1; 1141 bssl::UniquePtr<char> dec(BN_bn2dec(a.get())); 1142 bssl::UniquePtr<char> hex(BN_bn2hex(a.get())); 1143 ASSERT_TRUE(dec); 1144 ASSERT_TRUE(hex); 1145 EXPECT_STREQ("-0", dec.get()); 1146 EXPECT_STREQ("-0", hex.get()); 1147 1148 // Test that |BN_rshift| and |BN_rshift1| will not produce a negative zero. 1149 ASSERT_TRUE(BN_set_word(a.get(), 1)); 1150 BN_set_negative(a.get(), 1); 1151 1152 ASSERT_TRUE(BN_rshift(b.get(), a.get(), 1)); 1153 EXPECT_TRUE(BN_is_zero(b.get())); 1154 EXPECT_FALSE(BN_is_negative(b.get())); 1155 1156 ASSERT_TRUE(BN_rshift1(c.get(), a.get())); 1157 EXPECT_TRUE(BN_is_zero(c.get())); 1158 EXPECT_FALSE(BN_is_negative(c.get())); 1159 1160 // Test that |BN_div_word| will not produce a negative zero. 1161 ASSERT_NE((BN_ULONG)-1, BN_div_word(a.get(), 2)); 1162 EXPECT_TRUE(BN_is_zero(a.get())); 1163 EXPECT_FALSE(BN_is_negative(a.get())); 1164 } 1165 1166 TEST_F(BNTest, BadModulus) { 1167 bssl::UniquePtr<BIGNUM> a(BN_new()); 1168 bssl::UniquePtr<BIGNUM> b(BN_new()); 1169 bssl::UniquePtr<BIGNUM> zero(BN_new()); 1170 bssl::UniquePtr<BN_MONT_CTX> mont(BN_MONT_CTX_new()); 1171 ASSERT_TRUE(a); 1172 ASSERT_TRUE(b); 1173 ASSERT_TRUE(zero); 1174 ASSERT_TRUE(mont); 1175 1176 BN_zero(zero.get()); 1177 1178 EXPECT_FALSE(BN_div(a.get(), b.get(), BN_value_one(), zero.get(), ctx())); 1179 ERR_clear_error(); 1180 1181 EXPECT_FALSE( 1182 BN_mod_mul(a.get(), BN_value_one(), BN_value_one(), zero.get(), ctx())); 1183 ERR_clear_error(); 1184 1185 EXPECT_FALSE( 1186 BN_mod_exp(a.get(), BN_value_one(), BN_value_one(), zero.get(), ctx())); 1187 ERR_clear_error(); 1188 1189 EXPECT_FALSE(BN_mod_exp_mont(a.get(), BN_value_one(), BN_value_one(), 1190 zero.get(), ctx(), NULL)); 1191 ERR_clear_error(); 1192 1193 EXPECT_FALSE(BN_mod_exp_mont_consttime( 1194 a.get(), BN_value_one(), BN_value_one(), zero.get(), ctx(), nullptr)); 1195 ERR_clear_error(); 1196 1197 EXPECT_FALSE(BN_MONT_CTX_set(mont.get(), zero.get(), ctx())); 1198 ERR_clear_error(); 1199 1200 // Some operations also may not be used with an even modulus. 1201 ASSERT_TRUE(BN_set_word(b.get(), 16)); 1202 1203 EXPECT_FALSE(BN_MONT_CTX_set(mont.get(), b.get(), ctx())); 1204 ERR_clear_error(); 1205 1206 EXPECT_FALSE(BN_mod_exp_mont(a.get(), BN_value_one(), BN_value_one(), b.get(), 1207 ctx(), NULL)); 1208 ERR_clear_error(); 1209 1210 EXPECT_FALSE(BN_mod_exp_mont_consttime( 1211 a.get(), BN_value_one(), BN_value_one(), b.get(), ctx(), nullptr)); 1212 ERR_clear_error(); 1213 } 1214 1215 // Test that 1**0 mod 1 == 0. 1216 TEST_F(BNTest, ExpModZero) { 1217 bssl::UniquePtr<BIGNUM> zero(BN_new()), a(BN_new()), r(BN_new()); 1218 ASSERT_TRUE(zero); 1219 ASSERT_TRUE(a); 1220 ASSERT_TRUE(r); 1221 ASSERT_TRUE(BN_rand(a.get(), 1024, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY)); 1222 BN_zero(zero.get()); 1223 1224 ASSERT_TRUE( 1225 BN_mod_exp(r.get(), a.get(), zero.get(), BN_value_one(), nullptr)); 1226 EXPECT_TRUE(BN_is_zero(r.get())); 1227 1228 ASSERT_TRUE(BN_mod_exp_mont(r.get(), a.get(), zero.get(), BN_value_one(), 1229 nullptr, nullptr)); 1230 EXPECT_TRUE(BN_is_zero(r.get())); 1231 1232 ASSERT_TRUE(BN_mod_exp_mont_consttime(r.get(), a.get(), zero.get(), 1233 BN_value_one(), nullptr, nullptr)); 1234 EXPECT_TRUE(BN_is_zero(r.get())); 1235 1236 ASSERT_TRUE(BN_mod_exp_mont_word(r.get(), 42, zero.get(), BN_value_one(), 1237 nullptr, nullptr)); 1238 EXPECT_TRUE(BN_is_zero(r.get())); 1239 } 1240 1241 TEST_F(BNTest, SmallPrime) { 1242 static const unsigned kBits = 10; 1243 1244 bssl::UniquePtr<BIGNUM> r(BN_new()); 1245 ASSERT_TRUE(r); 1246 ASSERT_TRUE(BN_generate_prime_ex(r.get(), static_cast<int>(kBits), 0, NULL, 1247 NULL, NULL)); 1248 EXPECT_EQ(kBits, BN_num_bits(r.get())); 1249 } 1250 1251 TEST_F(BNTest, CmpWord) { 1252 static const BN_ULONG kMaxWord = (BN_ULONG)-1; 1253 1254 bssl::UniquePtr<BIGNUM> r(BN_new()); 1255 ASSERT_TRUE(r); 1256 ASSERT_TRUE(BN_set_word(r.get(), 0)); 1257 1258 EXPECT_EQ(BN_cmp_word(r.get(), 0), 0); 1259 EXPECT_LT(BN_cmp_word(r.get(), 1), 0); 1260 EXPECT_LT(BN_cmp_word(r.get(), kMaxWord), 0); 1261 1262 ASSERT_TRUE(BN_set_word(r.get(), 100)); 1263 1264 EXPECT_GT(BN_cmp_word(r.get(), 0), 0); 1265 EXPECT_GT(BN_cmp_word(r.get(), 99), 0); 1266 EXPECT_EQ(BN_cmp_word(r.get(), 100), 0); 1267 EXPECT_LT(BN_cmp_word(r.get(), 101), 0); 1268 EXPECT_LT(BN_cmp_word(r.get(), kMaxWord), 0); 1269 1270 BN_set_negative(r.get(), 1); 1271 1272 EXPECT_LT(BN_cmp_word(r.get(), 0), 0); 1273 EXPECT_LT(BN_cmp_word(r.get(), 100), 0); 1274 EXPECT_LT(BN_cmp_word(r.get(), kMaxWord), 0); 1275 1276 ASSERT_TRUE(BN_set_word(r.get(), kMaxWord)); 1277 1278 EXPECT_GT(BN_cmp_word(r.get(), 0), 0); 1279 EXPECT_GT(BN_cmp_word(r.get(), kMaxWord - 1), 0); 1280 EXPECT_EQ(BN_cmp_word(r.get(), kMaxWord), 0); 1281 1282 ASSERT_TRUE(BN_add(r.get(), r.get(), BN_value_one())); 1283 1284 EXPECT_GT(BN_cmp_word(r.get(), 0), 0); 1285 EXPECT_GT(BN_cmp_word(r.get(), kMaxWord), 0); 1286 1287 BN_set_negative(r.get(), 1); 1288 1289 EXPECT_LT(BN_cmp_word(r.get(), 0), 0); 1290 EXPECT_LT(BN_cmp_word(r.get(), kMaxWord), 0); 1291 } 1292 1293 TEST_F(BNTest, BN2Dec) { 1294 static const char *kBN2DecTests[] = { 1295 "0", 1296 "1", 1297 "-1", 1298 "100", 1299 "-100", 1300 "123456789012345678901234567890", 1301 "-123456789012345678901234567890", 1302 "123456789012345678901234567890123456789012345678901234567890", 1303 "-123456789012345678901234567890123456789012345678901234567890", 1304 }; 1305 1306 for (const char *test : kBN2DecTests) { 1307 SCOPED_TRACE(test); 1308 bssl::UniquePtr<BIGNUM> bn; 1309 int ret = DecimalToBIGNUM(&bn, test); 1310 ASSERT_NE(0, ret); 1311 1312 bssl::UniquePtr<char> dec(BN_bn2dec(bn.get())); 1313 ASSERT_TRUE(dec); 1314 EXPECT_STREQ(test, dec.get()); 1315 } 1316 } 1317 1318 TEST_F(BNTest, SetGetU64) { 1319 static const struct { 1320 const char *hex; 1321 uint64_t value; 1322 } kU64Tests[] = { 1323 {"0", UINT64_C(0x0)}, 1324 {"1", UINT64_C(0x1)}, 1325 {"ffffffff", UINT64_C(0xffffffff)}, 1326 {"100000000", UINT64_C(0x100000000)}, 1327 {"ffffffffffffffff", UINT64_C(0xffffffffffffffff)}, 1328 }; 1329 1330 for (const auto& test : kU64Tests) { 1331 SCOPED_TRACE(test.hex); 1332 bssl::UniquePtr<BIGNUM> bn(BN_new()), expected; 1333 ASSERT_TRUE(bn); 1334 ASSERT_TRUE(BN_set_u64(bn.get(), test.value)); 1335 ASSERT_TRUE(HexToBIGNUM(&expected, test.hex)); 1336 EXPECT_BIGNUMS_EQUAL("BN_set_u64", expected.get(), bn.get()); 1337 1338 uint64_t tmp; 1339 ASSERT_TRUE(BN_get_u64(bn.get(), &tmp)); 1340 EXPECT_EQ(test.value, tmp); 1341 1342 // BN_get_u64 ignores the sign bit. 1343 BN_set_negative(bn.get(), 1); 1344 ASSERT_TRUE(BN_get_u64(bn.get(), &tmp)); 1345 EXPECT_EQ(test.value, tmp); 1346 } 1347 1348 // Test that BN_get_u64 fails on large numbers. 1349 bssl::UniquePtr<BIGNUM> bn(BN_new()); 1350 ASSERT_TRUE(bn); 1351 ASSERT_TRUE(BN_lshift(bn.get(), BN_value_one(), 64)); 1352 1353 uint64_t tmp; 1354 EXPECT_FALSE(BN_get_u64(bn.get(), &tmp)); 1355 1356 BN_set_negative(bn.get(), 1); 1357 EXPECT_FALSE(BN_get_u64(bn.get(), &tmp)); 1358 } 1359 1360 TEST_F(BNTest, Pow2) { 1361 bssl::UniquePtr<BIGNUM> power_of_two(BN_new()), random(BN_new()), 1362 expected(BN_new()), actual(BN_new()); 1363 ASSERT_TRUE(power_of_two); 1364 ASSERT_TRUE(random); 1365 ASSERT_TRUE(expected); 1366 ASSERT_TRUE(actual); 1367 1368 // Choose an exponent. 1369 for (size_t e = 3; e < 512; e += 11) { 1370 SCOPED_TRACE(e); 1371 // Choose a bit length for our randoms. 1372 for (int len = 3; len < 512; len += 23) { 1373 SCOPED_TRACE(len); 1374 // Set power_of_two = 2^e. 1375 ASSERT_TRUE(BN_lshift(power_of_two.get(), BN_value_one(), (int)e)); 1376 1377 // Test BN_is_pow2 on power_of_two. 1378 EXPECT_TRUE(BN_is_pow2(power_of_two.get())); 1379 1380 // Pick a large random value, ensuring it isn't a power of two. 1381 ASSERT_TRUE( 1382 BN_rand(random.get(), len, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ANY)); 1383 1384 // Test BN_is_pow2 on |r|. 1385 EXPECT_FALSE(BN_is_pow2(random.get())); 1386 1387 // Test BN_mod_pow2 on |r|. 1388 ASSERT_TRUE( 1389 BN_mod(expected.get(), random.get(), power_of_two.get(), ctx())); 1390 ASSERT_TRUE(BN_mod_pow2(actual.get(), random.get(), e)); 1391 EXPECT_BIGNUMS_EQUAL("random (mod power_of_two)", expected.get(), 1392 actual.get()); 1393 1394 // Test BN_nnmod_pow2 on |r|. 1395 ASSERT_TRUE( 1396 BN_nnmod(expected.get(), random.get(), power_of_two.get(), ctx())); 1397 ASSERT_TRUE(BN_nnmod_pow2(actual.get(), random.get(), e)); 1398 EXPECT_BIGNUMS_EQUAL("random (mod power_of_two), non-negative", 1399 expected.get(), actual.get()); 1400 1401 // Test BN_nnmod_pow2 on -|r|. 1402 BN_set_negative(random.get(), 1); 1403 ASSERT_TRUE( 1404 BN_nnmod(expected.get(), random.get(), power_of_two.get(), ctx())); 1405 ASSERT_TRUE(BN_nnmod_pow2(actual.get(), random.get(), e)); 1406 EXPECT_BIGNUMS_EQUAL("-random (mod power_of_two), non-negative", 1407 expected.get(), actual.get()); 1408 } 1409 } 1410 } 1411 1412 static const int kPrimes[] = { 1413 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 1414 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 1415 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 1416 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 1417 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 1418 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 1419 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 1420 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 1421 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 1422 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 1423 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 1424 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 1425 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 1426 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 1427 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 1428 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1429 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1430 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1431 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1432 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1433 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1434 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1435 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1436 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1437 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1438 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1439 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1440 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 1441 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 1442 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 1443 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 1444 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 1445 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 1446 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 1447 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 1448 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 1449 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 1450 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 1451 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 1452 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 1453 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 1454 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 1455 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 1456 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 1457 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 1458 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 1459 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 1460 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 1461 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 1462 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 1463 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 1464 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 1465 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 1466 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 1467 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 1468 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 1469 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 1470 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 1471 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 1472 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 1473 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 1474 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 1475 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 1476 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 1477 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 1478 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 1479 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 1480 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 1481 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 1482 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 1483 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 1484 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 1485 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 1486 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 1487 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 1488 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 1489 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 1490 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 1491 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 1492 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 1493 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 1494 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 1495 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 1496 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 1497 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 1498 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 1499 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 1500 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 1501 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 1502 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 1503 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 1504 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 1505 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 1506 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 1507 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 1508 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 1509 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 1510 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 1511 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 1512 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 1513 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 1514 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 1515 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 1516 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 1517 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 1518 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 1519 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 1520 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 1521 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 1522 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 1523 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 1524 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007, 10009, 10037, 1525 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, 10103, 10111, 10133, 1526 10139, 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193, 10211, 10223, 1527 10243, 10247, 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313, 1528 10321, 10331, 10333, 10337, 10343, 10357, 10369, 10391, 10399, 10427, 10429, 1529 10433, 10453, 10457, 10459, 10463, 10477, 10487, 10499, 10501, 10513, 10529, 1530 10531, 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639, 1531 10651, 10657, 10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733, 1532 10739, 10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859, 1533 10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949, 10957, 1534 10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059, 11069, 11071, 1535 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161, 11171, 1536 11173, 11177, 11197, 11213, 11239, 11243, 11251, 11257, 11261, 11273, 11279, 1537 11287, 11299, 11311, 11317, 11321, 11329, 11351, 11353, 11369, 11383, 11393, 1538 11399, 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483, 11489, 11491, 1539 11497, 11503, 11519, 11527, 11549, 11551, 11579, 11587, 11593, 11597, 11617, 1540 11621, 11633, 11657, 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731, 1541 11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831, 1542 11833, 11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933, 1543 11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011, 12037, 1544 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109, 12113, 12119, 1545 12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211, 12227, 12239, 12241, 1546 12251, 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323, 12329, 12343, 1547 12347, 12373, 12377, 12379, 12391, 12401, 12409, 12413, 12421, 12433, 12437, 1548 12451, 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527, 1549 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601, 12611, 12613, 1550 12619, 12637, 12641, 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713, 1551 12721, 12739, 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823, 1552 12829, 12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923, 1553 12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007, 13009, 1554 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109, 13121, 13127, 1555 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187, 13217, 13219, 13229, 1556 13241, 13249, 13259, 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337, 1557 13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421, 13441, 13451, 13457, 1558 13463, 13469, 13477, 13487, 13499, 13513, 13523, 13537, 13553, 13567, 13577, 1559 13591, 13597, 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681, 13687, 1560 13691, 13693, 13697, 13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759, 1561 13763, 13781, 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877, 1562 13879, 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967, 1563 13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081, 14083, 1564 14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221, 1565 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323, 14327, 14341, 14347, 1566 14369, 14387, 14389, 14401, 14407, 14411, 14419, 14423, 14431, 14437, 14447, 1567 14449, 14461, 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549, 14551, 1568 14557, 14561, 14563, 14591, 14593, 14621, 14627, 14629, 14633, 14639, 14653, 1569 14657, 14669, 14683, 14699, 14713, 14717, 14723, 14731, 14737, 14741, 14747, 1570 14753, 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831, 1571 14843, 14851, 14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939, 1572 14947, 14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073, 1573 15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149, 15161, 1574 15173, 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259, 15263, 15269, 1575 15271, 15277, 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331, 15349, 1576 15359, 15361, 15373, 15377, 15383, 15391, 15401, 15413, 15427, 15439, 15443, 1577 15451, 15461, 15467, 15473, 15493, 15497, 15511, 15527, 15541, 15551, 15559, 1578 15569, 15581, 15583, 15601, 15607, 15619, 15629, 15641, 15643, 15647, 15649, 1579 15661, 15667, 15671, 15679, 15683, 15727, 15731, 15733, 15737, 15739, 15749, 1580 15761, 15767, 15773, 15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859, 1581 15877, 15881, 15887, 15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959, 1582 15971, 15973, 15991, 16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069, 1583 16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183, 16187, 1584 16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267, 16273, 16301, 1585 16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381, 16411, 16417, 16421, 1586 16427, 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493, 16519, 16529, 1587 16547, 16553, 16561, 16567, 16573, 16603, 16607, 16619, 16631, 16633, 16649, 1588 16651, 16657, 16661, 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747, 1589 16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843, 16871, 16879, 16883, 1590 16889, 16901, 16903, 16921, 16927, 16931, 16937, 16943, 16963, 16979, 16981, 1591 16987, 16993, 17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077, 1592 17093, 17099, 17107, 17117, 17123, 17137, 17159, 17167, 17183, 17189, 17191, 1593 17203, 17207, 17209, 17231, 17239, 17257, 17291, 17293, 17299, 17317, 17321, 1594 17327, 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389, 17393, 17401, 1595 17417, 17419, 17431, 17443, 17449, 17467, 17471, 17477, 17483, 17489, 17491, 1596 17497, 17509, 17519, 17539, 17551, 17569, 17573, 17579, 17581, 17597, 17599, 1597 17609, 17623, 17627, 17657, 17659, 17669, 17681, 17683, 17707, 17713, 17729, 1598 17737, 17747, 17749, 17761, 17783, 17789, 17791, 17807, 17827, 17837, 17839, 1599 17851, 17863, 17881, 17891, 17903, 17909, 17911, 17921, 17923, 17929, 17939, 1600 17957, 17959, 17971, 17977, 17981, 17987, 17989, 18013, 18041, 18043, 18047, 1601 18049, 18059, 18061, 18077, 18089, 18097, 18119, 18121, 18127, 18131, 18133, 1602 18143, 18149, 18169, 18181, 18191, 18199, 18211, 18217, 18223, 18229, 18233, 1603 18251, 18253, 18257, 18269, 18287, 18289, 18301, 18307, 18311, 18313, 18329, 1604 18341, 18353, 18367, 18371, 18379, 18397, 18401, 18413, 18427, 18433, 18439, 1605 18443, 18451, 18457, 18461, 18481, 18493, 18503, 18517, 18521, 18523, 18539, 1606 18541, 18553, 18583, 18587, 18593, 18617, 18637, 18661, 18671, 18679, 18691, 1607 18701, 18713, 18719, 18731, 18743, 18749, 18757, 18773, 18787, 18793, 18797, 1608 18803, 18839, 18859, 18869, 18899, 18911, 18913, 18917, 18919, 18947, 18959, 1609 18973, 18979, 19001, 19009, 19013, 19031, 19037, 19051, 19069, 19073, 19079, 1610 19081, 19087, 19121, 19139, 19141, 19157, 19163, 19181, 19183, 19207, 19211, 1611 19213, 19219, 19231, 19237, 19249, 19259, 19267, 19273, 19289, 19301, 19309, 1612 19319, 19333, 19373, 19379, 19381, 19387, 19391, 19403, 19417, 19421, 19423, 1613 19427, 19429, 19433, 19441, 19447, 19457, 19463, 19469, 19471, 19477, 19483, 1614 19489, 19501, 19507, 19531, 19541, 19543, 19553, 19559, 19571, 19577, 19583, 1615 19597, 19603, 19609, 19661, 19681, 19687, 19697, 19699, 19709, 19717, 19727, 1616 19739, 19751, 19753, 19759, 19763, 19777, 19793, 19801, 19813, 19819, 19841, 1617 19843, 19853, 19861, 19867, 19889, 19891, 19913, 19919, 19927, 19937, 19949, 1618 19961, 19963, 19973, 19979, 19991, 19993, 19997, 1619 }; 1620 1621 TEST_F(BNTest, PrimeChecking) { 1622 bssl::UniquePtr<BIGNUM> p(BN_new()); 1623 ASSERT_TRUE(p); 1624 int is_probably_prime_1 = 0, is_probably_prime_2 = 0; 1625 1626 const int max_prime = kPrimes[OPENSSL_ARRAY_SIZE(kPrimes)-1]; 1627 size_t next_prime_index = 0; 1628 1629 for (int i = 0; i <= max_prime; i++) { 1630 SCOPED_TRACE(i); 1631 bool is_prime = false; 1632 1633 if (i == kPrimes[next_prime_index]) { 1634 is_prime = true; 1635 next_prime_index++; 1636 } 1637 1638 ASSERT_TRUE(BN_set_word(p.get(), i)); 1639 ASSERT_TRUE(BN_primality_test( 1640 &is_probably_prime_1, p.get(), BN_prime_checks, ctx(), 1641 false /* do_trial_division */, nullptr /* callback */)); 1642 EXPECT_EQ(is_prime ? 1 : 0, is_probably_prime_1); 1643 ASSERT_TRUE(BN_primality_test( 1644 &is_probably_prime_2, p.get(), BN_prime_checks, ctx(), 1645 true /* do_trial_division */, nullptr /* callback */)); 1646 EXPECT_EQ(is_prime ? 1 : 0, is_probably_prime_2); 1647 } 1648 1649 // Negative numbers are not prime. 1650 ASSERT_TRUE(BN_set_word(p.get(), 7)); 1651 BN_set_negative(p.get(), 1); 1652 ASSERT_TRUE(BN_primality_test(&is_probably_prime_1, p.get(), BN_prime_checks, 1653 ctx(), false /* do_trial_division */, 1654 nullptr /* callback */)); 1655 EXPECT_EQ(0, is_probably_prime_1); 1656 ASSERT_TRUE(BN_primality_test(&is_probably_prime_2, p.get(), BN_prime_checks, 1657 ctx(), true /* do_trial_division */, 1658 nullptr /* callback */)); 1659 EXPECT_EQ(0, is_probably_prime_2); 1660 } 1661