legacy-libs/grpc-cloned/deps/grpc/third_party/boringssl/crypto/fipsmodule/bn/bn_test.cc

   1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   2  * All rights reserved.
   3  *
   4  * This package is an SSL implementation written
   5  * by Eric Young (eay@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@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@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@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/bio.h>
  91 #include <openssl/bn.h>
  92 #include <openssl/bytestring.h>
  93 #include <openssl/crypto.h>
  94 #include <openssl/err.h>
  95 #include <openssl/mem.h>
  96 #include <openssl/rand.h>
  97
  98 #include "./internal.h"
  99 #include "../../internal.h"
 100 #include "../../test/file_test.h"
 101 #include "../../test/test_util.h"
 102
 103
 104 static int HexToBIGNUM(bssl::UniquePtr<BIGNUM> *out, const char *in) {
 105   BIGNUM *raw = NULL;
 106   int ret = BN_hex2bn(&raw, in);
 107   out->reset(raw);
 108   return ret;
 109 }
 110
 111 // A BIGNUMFileTest wraps a FileTest to give |BIGNUM| values and also allows
 112 // injecting oversized |BIGNUM|s.
 113 class BIGNUMFileTest {
 114  public:
 115   BIGNUMFileTest(FileTest *t, unsigned large_mask)
 116       : t_(t), large_mask_(large_mask), num_bignums_(0) {}
 117
 118   unsigned num_bignums() const { return num_bignums_; }
 119
 120   bssl::UniquePtr<BIGNUM> GetBIGNUM(const char *attribute) {
 121     return GetBIGNUMImpl(attribute, true /* resize */);
 122   }
 123
 124   bool GetInt(int *out, const char *attribute) {
 125     bssl::UniquePtr<BIGNUM> ret =
 126         GetBIGNUMImpl(attribute, false /* don't resize */);
 127     if (!ret) {
 128       return false;
 129     }
 130
 131     BN_ULONG word = BN_get_word(ret.get());
 132     if (word > INT_MAX) {
 133       return false;
 134     }
 135
 136     *out = static_cast<int>(word);
 137     return true;
 138   }
 139
 140  private:
 141   bssl::UniquePtr<BIGNUM> GetBIGNUMImpl(const char *attribute, bool resize) {
 142     std::string hex;
 143     if (!t_->GetAttribute(&hex, attribute)) {
 144       return nullptr;
 145     }
 146
 147     bssl::UniquePtr<BIGNUM> ret;
 148     if (HexToBIGNUM(&ret, hex.c_str()) != static_cast<int>(hex.size())) {
 149       t_->PrintLine("Could not decode '%s'.", hex.c_str());
 150       return nullptr;
 151     }
 152     if (resize) {
 153       // Test with an oversized |BIGNUM| if necessary.
 154       if ((large_mask_ & (1 << num_bignums_)) &&
 155           !bn_resize_words(ret.get(), ret->width * 2 + 1)) {
 156         return nullptr;
 157       }
 158       num_bignums_++;
 159     }
 160     return ret;
 161   }
 162
 163   FileTest *t_;
 164   unsigned large_mask_;
 165   unsigned num_bignums_;
 166 };
 167
 168 static testing::AssertionResult AssertBIGNUMSEqual(
 169     const char *operation_expr, const char *expected_expr,
 170     const char *actual_expr, const char *operation, const BIGNUM *expected,
 171     const BIGNUM *actual) {
 172   if (BN_cmp(expected, actual) == 0) {
 173     return testing::AssertionSuccess();
 174   }
 175
 176   bssl::UniquePtr<char> expected_str(BN_bn2hex(expected));
 177   bssl::UniquePtr<char> actual_str(BN_bn2hex(actual));
 178   if (!expected_str || !actual_str) {
 179     return testing::AssertionFailure() << "Error converting BIGNUMs to hex";
 180   }
 181
 182   return testing::AssertionFailure()
 183          << "Wrong value for " << operation
 184          << "\nActual:   " << actual_str.get() << " (" << actual_expr
 185          << ")\nExpected: " << expected_str.get() << " (" << expected_expr
 186          << ")";
 187 }
 188
 189 #define EXPECT_BIGNUMS_EQUAL(op, a, b) \
 190   EXPECT_PRED_FORMAT3(AssertBIGNUMSEqual, op, a, b)
 191
 192 static void TestSum(BIGNUMFileTest *t, BN_CTX *ctx) {
 193   bssl::UniquePtr<BIGNUM> a = t->GetBIGNUM("A");
 194   bssl::UniquePtr<BIGNUM> b = t->GetBIGNUM("B");
 195   bssl::UniquePtr<BIGNUM> sum = t->GetBIGNUM("Sum");
 196   ASSERT_TRUE(a);
 197   ASSERT_TRUE(b);
 198   ASSERT_TRUE(sum);
 199
 200   bssl::UniquePtr<BIGNUM> ret(BN_new());
 201   ASSERT_TRUE(ret);
 202   ASSERT_TRUE(BN_add(ret.get(), a.get(), b.get()));
 203   EXPECT_BIGNUMS_EQUAL("A + B", sum.get(), ret.get());
 204
 205   ASSERT_TRUE(BN_sub(ret.get(), sum.get(), a.get()));
 206   EXPECT_BIGNUMS_EQUAL("Sum - A", b.get(), ret.get());
 207
 208   ASSERT_TRUE(BN_sub(ret.get(), sum.get(), b.get()));
 209   EXPECT_BIGNUMS_EQUAL("Sum - B", a.get(), ret.get());
 210
 211   // Test that the functions work when |r| and |a| point to the same |BIGNUM|,
 212   // or when |r| and |b| point to the same |BIGNUM|. TODO: Test the case where
 213   // all of |r|, |a|, and |b| point to the same |BIGNUM|.
 214   ASSERT_TRUE(BN_copy(ret.get(), a.get()));
 215   ASSERT_TRUE(BN_add(ret.get(), ret.get(), b.get()));
 216   EXPECT_BIGNUMS_EQUAL("A + B (r is a)", sum.get(), ret.get());
 217
 218   ASSERT_TRUE(BN_copy(ret.get(), b.get()));
 219   ASSERT_TRUE(BN_add(ret.get(), a.get(), ret.get()));
 220   EXPECT_BIGNUMS_EQUAL("A + B (r is b)", sum.get(), ret.get());
 221
 222   ASSERT_TRUE(BN_copy(ret.get(), sum.get()));
 223   ASSERT_TRUE(BN_sub(ret.get(), ret.get(), a.get()));
 224   EXPECT_BIGNUMS_EQUAL("Sum - A (r is a)", b.get(), ret.get());
 225
 226   ASSERT_TRUE(BN_copy(ret.get(), a.get()));
 227   ASSERT_TRUE(BN_sub(ret.get(), sum.get(), ret.get()));
 228   EXPECT_BIGNUMS_EQUAL("Sum - A (r is b)", b.get(), ret.get());
 229
 230   ASSERT_TRUE(BN_copy(ret.get(), sum.get()));
 231   ASSERT_TRUE(BN_sub(ret.get(), ret.get(), b.get()));
 232   EXPECT_BIGNUMS_EQUAL("Sum - B (r is a)", a.get(), ret.get());
 233
 234   ASSERT_TRUE(BN_copy(ret.get(), b.get()));
 235   ASSERT_TRUE(BN_sub(ret.get(), sum.get(), ret.get()));
 236   EXPECT_BIGNUMS_EQUAL("Sum - B (r is b)", a.get(), ret.get());
 237
 238   // Test |BN_uadd| and |BN_usub| with the prerequisites they are documented as
 239   // having. Note that these functions are frequently used when the
 240   // prerequisites don't hold. In those cases, they are supposed to work as if
 241   // the prerequisite hold, but we don't test that yet. TODO: test that.
 242   if (!BN_is_negative(a.get()) && !BN_is_negative(b.get())) {
 243     ASSERT_TRUE(BN_uadd(ret.get(), a.get(), b.get()));
 244     EXPECT_BIGNUMS_EQUAL("A +u B", sum.get(), ret.get());
 245
 246     ASSERT_TRUE(BN_usub(ret.get(), sum.get(), a.get()));
 247     EXPECT_BIGNUMS_EQUAL("Sum -u A", b.get(), ret.get());
 248
 249     ASSERT_TRUE(BN_usub(ret.get(), sum.get(), b.get()));
 250     EXPECT_BIGNUMS_EQUAL("Sum -u B", a.get(), ret.get());
 251
 252     // Test that the functions work when |r| and |a| point to the same |BIGNUM|,
 253     // or when |r| and |b| point to the same |BIGNUM|. TODO: Test the case where
 254     // all of |r|, |a|, and |b| point to the same |BIGNUM|.
 255     ASSERT_TRUE(BN_copy(ret.get(), a.get()));
 256     ASSERT_TRUE(BN_uadd(ret.get(), ret.get(), b.get()));
 257     EXPECT_BIGNUMS_EQUAL("A +u B (r is a)", sum.get(), ret.get());
 258
 259     ASSERT_TRUE(BN_copy(ret.get(), b.get()));
 260     ASSERT_TRUE(BN_uadd(ret.get(), a.get(), ret.get()));
 261     EXPECT_BIGNUMS_EQUAL("A +u B (r is b)", sum.get(), ret.get());
 262
 263     ASSERT_TRUE(BN_copy(ret.get(), sum.get()));
 264     ASSERT_TRUE(BN_usub(ret.get(), ret.get(), a.get()));
 265     EXPECT_BIGNUMS_EQUAL("Sum -u A (r is a)", b.get(), ret.get());
 266
 267     ASSERT_TRUE(BN_copy(ret.get(), a.get()));
 268     ASSERT_TRUE(BN_usub(ret.get(), sum.get(), ret.get()));
 269     EXPECT_BIGNUMS_EQUAL("Sum -u A (r is b)", b.get(), ret.get());
 270
 271     ASSERT_TRUE(BN_copy(ret.get(), sum.get()));
 272     ASSERT_TRUE(BN_usub(ret.get(), ret.get(), b.get()));
 273     EXPECT_BIGNUMS_EQUAL("Sum -u B (r is a)", a.get(), ret.get());
 274
 275     ASSERT_TRUE(BN_copy(ret.get(), b.get()));
 276     ASSERT_TRUE(BN_usub(ret.get(), sum.get(), ret.get()));
 277     EXPECT_BIGNUMS_EQUAL("Sum -u B (r is b)", a.get(), ret.get());
 278
 279     ASSERT_TRUE(bn_abs_sub_consttime(ret.get(), sum.get(), a.get(), ctx));
 280     EXPECT_BIGNUMS_EQUAL("|Sum - A|", b.get(), ret.get());
 281     ASSERT_TRUE(bn_abs_sub_consttime(ret.get(), a.get(), sum.get(), ctx));
 282     EXPECT_BIGNUMS_EQUAL("|A - Sum|", b.get(), ret.get());
 283
 284     ASSERT_TRUE(bn_abs_sub_consttime(ret.get(), sum.get(), b.get(), ctx));
 285     EXPECT_BIGNUMS_EQUAL("|Sum - B|", a.get(), ret.get());
 286     ASSERT_TRUE(bn_abs_sub_consttime(ret.get(), b.get(), sum.get(), ctx));
 287     EXPECT_BIGNUMS_EQUAL("|B - Sum|", a.get(), ret.get());
 288   }
 289
 290   // Test with |BN_add_word| and |BN_sub_word| if |b| is small enough.
 291   BN_ULONG b_word = BN_get_word(b.get());
 292   if (!BN_is_negative(b.get()) && b_word != (BN_ULONG)-1) {
 293     ASSERT_TRUE(BN_copy(ret.get(), a.get()));
 294     ASSERT_TRUE(BN_add_word(ret.get(), b_word));
 295     EXPECT_BIGNUMS_EQUAL("A + B (word)", sum.get(), ret.get());
 296
 297     ASSERT_TRUE(BN_copy(ret.get(), sum.get()));
 298     ASSERT_TRUE(BN_sub_word(ret.get(), b_word));
 299     EXPECT_BIGNUMS_EQUAL("Sum - B (word)", a.get(), ret.get());
 300   }
 301 }
 302
 303 static void TestLShift1(BIGNUMFileTest *t, BN_CTX *ctx) {
 304   bssl::UniquePtr<BIGNUM> a = t->GetBIGNUM("A");
 305   bssl::UniquePtr<BIGNUM> lshift1 = t->GetBIGNUM("LShift1");
 306   bssl::UniquePtr<BIGNUM> zero(BN_new());
 307   ASSERT_TRUE(a);
 308   ASSERT_TRUE(lshift1);
 309   ASSERT_TRUE(zero);
 310
 311   BN_zero(zero.get());
 312
 313   bssl::UniquePtr<BIGNUM> ret(BN_new()), two(BN_new()), remainder(BN_new());
 314   ASSERT_TRUE(ret);
 315   ASSERT_TRUE(two);
 316   ASSERT_TRUE(remainder);
 317
 318   ASSERT_TRUE(BN_set_word(two.get(), 2));
 319   ASSERT_TRUE(BN_add(ret.get(), a.get(), a.get()));
 320   EXPECT_BIGNUMS_EQUAL("A + A", lshift1.get(), ret.get());
 321
 322   ASSERT_TRUE(BN_mul(ret.get(), a.get(), two.get(), ctx));
 323   EXPECT_BIGNUMS_EQUAL("A * 2", lshift1.get(), ret.get());
 324
 325   ASSERT_TRUE(
 326       BN_div(ret.get(), remainder.get(), lshift1.get(), two.get(), ctx));
 327   EXPECT_BIGNUMS_EQUAL("LShift1 / 2", a.get(), ret.get());
 328   EXPECT_BIGNUMS_EQUAL("LShift1 % 2", zero.get(), remainder.get());
 329
 330   ASSERT_TRUE(BN_lshift1(ret.get(), a.get()));
 331   EXPECT_BIGNUMS_EQUAL("A << 1", lshift1.get(), ret.get());
 332
 333   ASSERT_TRUE(BN_lshift(ret.get(), a.get(), 1));
 334   EXPECT_BIGNUMS_EQUAL("A << 1 (variable shift)", lshift1.get(), ret.get());
 335
 336   ASSERT_TRUE(BN_rshift1(ret.get(), lshift1.get()));
 337   EXPECT_BIGNUMS_EQUAL("LShift >> 1", a.get(), ret.get());
 338
 339   ASSERT_TRUE(BN_rshift(ret.get(), lshift1.get(), 1));
 340   EXPECT_BIGNUMS_EQUAL("LShift >> 1 (variable shift)", a.get(), ret.get());
 341
 342   ASSERT_TRUE(bn_rshift_secret_shift(ret.get(), lshift1.get(), 1, ctx));
 343   EXPECT_BIGNUMS_EQUAL("LShift >> 1 (secret shift)", a.get(), ret.get());
 344
 345   // Set the LSB to 1 and test rshift1 again.
 346   ASSERT_TRUE(BN_set_bit(lshift1.get(), 0));
 347   ASSERT_TRUE(
 348       BN_div(ret.get(), nullptr /* rem */, lshift1.get(), two.get(), ctx));
 349   EXPECT_BIGNUMS_EQUAL("(LShift1 | 1) / 2", a.get(), ret.get());
 350
 351   ASSERT_TRUE(BN_rshift1(ret.get(), lshift1.get()));
 352   EXPECT_BIGNUMS_EQUAL("(LShift | 1) >> 1", a.get(), ret.get());
 353
 354   ASSERT_TRUE(BN_rshift(ret.get(), lshift1.get(), 1));
 355   EXPECT_BIGNUMS_EQUAL("(LShift | 1) >> 1 (variable shift)", a.get(),
 356                        ret.get());
 357
 358   ASSERT_TRUE(bn_rshift_secret_shift(ret.get(), lshift1.get(), 1, ctx));
 359   EXPECT_BIGNUMS_EQUAL("(LShift | 1) >> 1 (secret shift)", a.get(), ret.get());
 360 }
 361
 362 static void TestLShift(BIGNUMFileTest *t, BN_CTX *ctx) {
 363   bssl::UniquePtr<BIGNUM> a = t->GetBIGNUM("A");
 364   bssl::UniquePtr<BIGNUM> lshift = t->GetBIGNUM("LShift");
 365   ASSERT_TRUE(a);
 366   ASSERT_TRUE(lshift);
 367   int n = 0;
 368   ASSERT_TRUE(t->GetInt(&n, "N"));
 369
 370   bssl::UniquePtr<BIGNUM> ret(BN_new());
 371   ASSERT_TRUE(ret);
 372   ASSERT_TRUE(BN_lshift(ret.get(), a.get(), n));
 373   EXPECT_BIGNUMS_EQUAL("A << N", lshift.get(), ret.get());
 374
 375   ASSERT_TRUE(BN_copy(ret.get(), a.get()));
 376   ASSERT_TRUE(BN_lshift(ret.get(), ret.get(), n));
 377   EXPECT_BIGNUMS_EQUAL("A << N (in-place)", lshift.get(), ret.get());
 378
 379   ASSERT_TRUE(BN_rshift(ret.get(), lshift.get(), n));
 380   EXPECT_BIGNUMS_EQUAL("A >> N", a.get(), ret.get());
 381
 382   ASSERT_TRUE(bn_rshift_secret_shift(ret.get(), lshift.get(), n, ctx));
 383   EXPECT_BIGNUMS_EQUAL("A >> N (secret shift)", a.get(), ret.get());
 384 }
 385
 386 static void TestRShift(BIGNUMFileTest *t, BN_CTX *ctx) {
 387   bssl::UniquePtr<BIGNUM> a = t->GetBIGNUM("A");
 388   bssl::UniquePtr<BIGNUM> rshift = t->GetBIGNUM("RShift");
 389   ASSERT_TRUE(a);
 390   ASSERT_TRUE(rshift);
 391   int n = 0;
 392   ASSERT_TRUE(t->GetInt(&n, "N"));
 393
 394   bssl::UniquePtr<BIGNUM> ret(BN_new());
 395   ASSERT_TRUE(ret);
 396   ASSERT_TRUE(BN_rshift(ret.get(), a.get(), n));
 397   EXPECT_BIGNUMS_EQUAL("A >> N", rshift.get(), ret.get());
 398
 399   ASSERT_TRUE(BN_copy(ret.get(), a.get()));
 400   ASSERT_TRUE(BN_rshift(ret.get(), ret.get(), n));
 401   EXPECT_BIGNUMS_EQUAL("A >> N (in-place)", rshift.get(), ret.get());
 402
 403   ASSERT_TRUE(bn_rshift_secret_shift(ret.get(), a.get(), n, ctx));
 404   EXPECT_BIGNUMS_EQUAL("A >> N (secret shift)", rshift.get(), ret.get());
 405
 406   ASSERT_TRUE(BN_copy(ret.get(), a.get()));
 407   ASSERT_TRUE(bn_rshift_secret_shift(ret.get(), ret.get(), n, ctx));
 408   EXPECT_BIGNUMS_EQUAL("A >> N (in-place secret shift)", rshift.get(),
 409                        ret.get());
 410 }
 411
 412 static void TestSquare(BIGNUMFileTest *t, BN_CTX *ctx) {
 413   bssl::UniquePtr<BIGNUM> a = t->GetBIGNUM("A");
 414   bssl::UniquePtr<BIGNUM> square = t->GetBIGNUM("Square");
 415   bssl::UniquePtr<BIGNUM> zero(BN_new());
 416   ASSERT_TRUE(a);
 417   ASSERT_TRUE(square);
 418   ASSERT_TRUE(zero);
 419
 420   BN_zero(zero.get());
 421
 422   bssl::UniquePtr<BIGNUM> ret(BN_new()), remainder(BN_new());
 423   ASSERT_TRUE(ret);
 424   ASSERT_TRUE(remainder);
 425   ASSERT_TRUE(BN_sqr(ret.get(), a.get(), ctx));
 426   EXPECT_BIGNUMS_EQUAL("A^2", square.get(), ret.get());
 427
 428   ASSERT_TRUE(BN_mul(ret.get(), a.get(), a.get(), ctx));
 429   EXPECT_BIGNUMS_EQUAL("A * A", square.get(), ret.get());
 430
 431   if (!BN_is_zero(a.get())) {
 432     ASSERT_TRUE(BN_div(ret.get(), remainder.get(), square.get(), a.get(), ctx));
 433     EXPECT_BIGNUMS_EQUAL("Square / A", a.get(), ret.get());
 434     EXPECT_BIGNUMS_EQUAL("Square % A", zero.get(), remainder.get());
 435   }
 436
 437   BN_set_negative(a.get(), 0);
 438   ASSERT_TRUE(BN_sqrt(ret.get(), square.get(), ctx));
 439   EXPECT_BIGNUMS_EQUAL("sqrt(Square)", a.get(), ret.get());
 440
 441   // BN_sqrt should fail on non-squares and negative numbers.
 442   if (!BN_is_zero(square.get())) {
 443     bssl::UniquePtr<BIGNUM> tmp(BN_new());
 444     ASSERT_TRUE(tmp);
 445     ASSERT_TRUE(BN_copy(tmp.get(), square.get()));
 446     BN_set_negative(tmp.get(), 1);
 447
 448     EXPECT_FALSE(BN_sqrt(ret.get(), tmp.get(), ctx))
 449         << "BN_sqrt succeeded on a negative number";
 450     ERR_clear_error();
 451
 452     BN_set_negative(tmp.get(), 0);
 453     ASSERT_TRUE(BN_add(tmp.get(), tmp.get(), BN_value_one()));
 454     EXPECT_FALSE(BN_sqrt(ret.get(), tmp.get(), ctx))
 455         << "BN_sqrt succeeded on a non-square";
 456     ERR_clear_error();
 457   }
 458
 459 #if !defined(BORINGSSL_SHARED_LIBRARY)
 460   int a_width = bn_minimal_width(a.get());
 461   if (a_width <= BN_SMALL_MAX_WORDS) {
 462     for (size_t num_a = a_width; num_a <= BN_SMALL_MAX_WORDS; num_a++) {
 463       SCOPED_TRACE(num_a);
 464       size_t num_r = 2 * num_a;
 465       // Use newly-allocated buffers so ASan will catch out-of-bounds writes.
 466       std::unique_ptr<BN_ULONG[]> a_words(new BN_ULONG[num_a]),
 467           r_words(new BN_ULONG[num_r]);
 468       ASSERT_TRUE(bn_copy_words(a_words.get(), num_a, a.get()));
 469
 470       ASSERT_TRUE(bn_mul_small(r_words.get(), num_r, a_words.get(), num_a,
 471                                a_words.get(), num_a));
 472       ASSERT_TRUE(bn_set_words(ret.get(), r_words.get(), num_r));
 473       EXPECT_BIGNUMS_EQUAL("A * A (words)", square.get(), ret.get());
 474
 475       OPENSSL_memset(r_words.get(), 'A', num_r * sizeof(BN_ULONG));
 476       ASSERT_TRUE(bn_sqr_small(r_words.get(), num_r, a_words.get(), num_a));
 477
 478       ASSERT_TRUE(bn_set_words(ret.get(), r_words.get(), num_r));
 479       EXPECT_BIGNUMS_EQUAL("A^2 (words)", square.get(), ret.get());
 480     }
 481   }
 482 #endif
 483 }
 484
 485 static void TestProduct(BIGNUMFileTest *t, BN_CTX *ctx) {
 486   bssl::UniquePtr<BIGNUM> a = t->GetBIGNUM("A");
 487   bssl::UniquePtr<BIGNUM> b = t->GetBIGNUM("B");
 488   bssl::UniquePtr<BIGNUM> product = t->GetBIGNUM("Product");
 489   bssl::UniquePtr<BIGNUM> zero(BN_new());
 490   ASSERT_TRUE(a);
 491   ASSERT_TRUE(b);
 492   ASSERT_TRUE(product);
 493   ASSERT_TRUE(zero);
 494
 495   BN_zero(zero.get());
 496
 497   bssl::UniquePtr<BIGNUM> ret(BN_new()), remainder(BN_new());
 498   ASSERT_TRUE(ret);
 499   ASSERT_TRUE(remainder);
 500   ASSERT_TRUE(BN_mul(ret.get(), a.get(), b.get(), ctx));
 501   EXPECT_BIGNUMS_EQUAL("A * B", product.get(), ret.get());
 502
 503   if (!BN_is_zero(a.get())) {
 504     ASSERT_TRUE(
 505         BN_div(ret.get(), remainder.get(), product.get(), a.get(), ctx));
 506     EXPECT_BIGNUMS_EQUAL("Product / A", b.get(), ret.get());
 507     EXPECT_BIGNUMS_EQUAL("Product % A", zero.get(), remainder.get());
 508   }
 509
 510   if (!BN_is_zero(b.get())) {
 511     ASSERT_TRUE(
 512         BN_div(ret.get(), remainder.get(), product.get(), b.get(), ctx));
 513     EXPECT_BIGNUMS_EQUAL("Product / B", a.get(), ret.get());
 514     EXPECT_BIGNUMS_EQUAL("Product % B", zero.get(), remainder.get());
 515   }
 516
 517 #if !defined(BORINGSSL_SHARED_LIBRARY)
 518   BN_set_negative(a.get(), 0);
 519   BN_set_negative(b.get(), 0);
 520   BN_set_negative(product.get(), 0);
 521
 522   int a_width = bn_minimal_width(a.get());
 523   int b_width = bn_minimal_width(b.get());
 524   if (a_width <= BN_SMALL_MAX_WORDS && b_width <= BN_SMALL_MAX_WORDS) {
 525     for (size_t num_a = static_cast<size_t>(a_width);
 526          num_a <= BN_SMALL_MAX_WORDS; num_a++) {
 527       SCOPED_TRACE(num_a);
 528       for (size_t num_b = static_cast<size_t>(b_width);
 529            num_b <= BN_SMALL_MAX_WORDS; num_b++) {
 530         SCOPED_TRACE(num_b);
 531         size_t num_r = num_a + num_b;
 532         // Use newly-allocated buffers so ASan will catch out-of-bounds writes.
 533         std::unique_ptr<BN_ULONG[]> a_words(new BN_ULONG[num_a]),
 534             b_words(new BN_ULONG[num_b]), r_words(new BN_ULONG[num_r]);
 535         ASSERT_TRUE(bn_copy_words(a_words.get(), num_a, a.get()));
 536         ASSERT_TRUE(bn_copy_words(b_words.get(), num_b, b.get()));
 537
 538         ASSERT_TRUE(bn_mul_small(r_words.get(), num_r, a_words.get(), num_a,
 539                                  b_words.get(), num_b));
 540         ASSERT_TRUE(bn_set_words(ret.get(), r_words.get(), num_r));
 541         EXPECT_BIGNUMS_EQUAL("A * B (words)", product.get(), ret.get());
 542       }
 543     }
 544   }
 545 #endif
 546 }
 547
 548 static void TestQuotient(BIGNUMFileTest *t, BN_CTX *ctx) {
 549   bssl::UniquePtr<BIGNUM> a = t->GetBIGNUM("A");
 550   bssl::UniquePtr<BIGNUM> b = t->GetBIGNUM("B");
 551   bssl::UniquePtr<BIGNUM> quotient = t->GetBIGNUM("Quotient");
 552   bssl::UniquePtr<BIGNUM> remainder = t->GetBIGNUM("Remainder");
 553   ASSERT_TRUE(a);
 554   ASSERT_TRUE(b);
 555   ASSERT_TRUE(quotient);
 556   ASSERT_TRUE(remainder);
 557
 558   bssl::UniquePtr<BIGNUM> ret(BN_new()), ret2(BN_new());
 559   ASSERT_TRUE(ret);
 560   ASSERT_TRUE(ret2);
 561   ASSERT_TRUE(BN_div(ret.get(), ret2.get(), a.get(), b.get(), ctx));
 562   EXPECT_BIGNUMS_EQUAL("A / B", quotient.get(), ret.get());
 563   EXPECT_BIGNUMS_EQUAL("A % B", remainder.get(), ret2.get());
 564
 565   ASSERT_TRUE(BN_mul(ret.get(), quotient.get(), b.get(), ctx));
 566   ASSERT_TRUE(BN_add(ret.get(), ret.get(), remainder.get()));
 567   EXPECT_BIGNUMS_EQUAL("Quotient * B + Remainder", a.get(), ret.get());
 568
 569   // The remaining division variants only handle a positive quotient.
 570   if (BN_is_negative(b.get())) {
 571     BN_set_negative(b.get(), 0);
 572     BN_set_negative(quotient.get(), !BN_is_negative(quotient.get()));
 573   }
 574
 575   bssl::UniquePtr<BIGNUM> nnmod(BN_new());
 576   ASSERT_TRUE(nnmod);
 577   ASSERT_TRUE(BN_copy(nnmod.get(), remainder.get()));
 578   if (BN_is_negative(nnmod.get())) {
 579     ASSERT_TRUE(BN_add(nnmod.get(), nnmod.get(), b.get()));
 580   }
 581   ASSERT_TRUE(BN_nnmod(ret.get(), a.get(), b.get(), ctx));
 582   EXPECT_BIGNUMS_EQUAL("A % B (non-negative)", nnmod.get(), ret.get());
 583
 584   // The remaining division variants only handle a positive numerator.
 585   if (BN_is_negative(a.get())) {
 586     BN_set_negative(a.get(), 0);
 587     BN_set_negative(quotient.get(), 0);
 588     BN_set_negative(remainder.get(), 0);
 589   }
 590
 591   // Test with |BN_mod_word| and |BN_div_word| if the divisor is small enough.
 592   BN_ULONG b_word = BN_get_word(b.get());
 593   if (b_word != (BN_ULONG)-1) {
 594     BN_ULONG remainder_word = BN_get_word(remainder.get());
 595     ASSERT_NE(remainder_word, (BN_ULONG)-1);
 596     ASSERT_TRUE(BN_copy(ret.get(), a.get()));
 597     BN_ULONG ret_word = BN_div_word(ret.get(), b_word);
 598     EXPECT_EQ(remainder_word, ret_word);
 599     EXPECT_BIGNUMS_EQUAL("A / B (word)", quotient.get(), ret.get());
 600
 601     ret_word = BN_mod_word(a.get(), b_word);
 602     EXPECT_EQ(remainder_word, ret_word);
 603
 604     if (b_word <= 0xffff) {
 605       EXPECT_EQ(remainder_word, bn_mod_u16_consttime(a.get(), b_word));
 606     }
 607   }
 608
 609   ASSERT_TRUE(bn_div_consttime(ret.get(), ret2.get(), a.get(), b.get(), ctx));
 610   EXPECT_BIGNUMS_EQUAL("A / B (constant-time)", quotient.get(), ret.get());
 611   EXPECT_BIGNUMS_EQUAL("A % B (constant-time)", remainder.get(), ret2.get());
 612 }
 613
 614 static void TestModMul(BIGNUMFileTest *t, BN_CTX *ctx) {
 615   bssl::UniquePtr<BIGNUM> a = t->GetBIGNUM("A");
 616   bssl::UniquePtr<BIGNUM> b = t->GetBIGNUM("B");
 617   bssl::UniquePtr<BIGNUM> m = t->GetBIGNUM("M");
 618   bssl::UniquePtr<BIGNUM> mod_mul = t->GetBIGNUM("ModMul");
 619   ASSERT_TRUE(a);
 620   ASSERT_TRUE(b);
 621   ASSERT_TRUE(m);
 622   ASSERT_TRUE(mod_mul);
 623
 624   bssl::UniquePtr<BIGNUM> ret(BN_new());
 625   ASSERT_TRUE(ret);
 626   ASSERT_TRUE(BN_mod_mul(ret.get(), a.get(), b.get(), m.get(), ctx));
 627   EXPECT_BIGNUMS_EQUAL("A * B (mod M)", mod_mul.get(), ret.get());
 628
 629   if (BN_is_odd(m.get())) {
 630     // Reduce |a| and |b| and test the Montgomery version.
 631     bssl::UniquePtr<BN_MONT_CTX> mont(
 632         BN_MONT_CTX_new_for_modulus(m.get(), ctx));
 633     bssl::UniquePtr<BIGNUM> a_tmp(BN_new()), b_tmp(BN_new());
 634     ASSERT_TRUE(mont);
 635     ASSERT_TRUE(a_tmp);
 636     ASSERT_TRUE(b_tmp);
 637     ASSERT_TRUE(BN_nnmod(a.get(), a.get(), m.get(), ctx));
 638     ASSERT_TRUE(BN_nnmod(b.get(), b.get(), m.get(), ctx));
 639     ASSERT_TRUE(BN_to_montgomery(a_tmp.get(), a.get(), mont.get(), ctx));
 640     ASSERT_TRUE(BN_to_montgomery(b_tmp.get(), b.get(), mont.get(), ctx));
 641     ASSERT_TRUE(BN_mod_mul_montgomery(ret.get(), a_tmp.get(), b_tmp.get(),
 642                                       mont.get(), ctx));
 643     ASSERT_TRUE(BN_from_montgomery(ret.get(), ret.get(), mont.get(), ctx));
 644     EXPECT_BIGNUMS_EQUAL("A * B (mod M) (Montgomery)", mod_mul.get(),
 645                          ret.get());
 646
 647 #if !defined(BORINGSSL_SHARED_LIBRARY)
 648     size_t m_width = static_cast<size_t>(bn_minimal_width(m.get()));
 649     if (m_width <= BN_SMALL_MAX_WORDS) {
 650       std::unique_ptr<BN_ULONG[]> a_words(new BN_ULONG[m_width]),
 651           b_words(new BN_ULONG[m_width]), r_words(new BN_ULONG[m_width]);
 652       ASSERT_TRUE(bn_copy_words(a_words.get(), m_width, a.get()));
 653       ASSERT_TRUE(bn_copy_words(b_words.get(), m_width, b.get()));
 654       ASSERT_TRUE(bn_to_montgomery_small(a_words.get(), m_width, a_words.get(),
 655                                          m_width, mont.get()));
 656       ASSERT_TRUE(bn_to_montgomery_small(b_words.get(), m_width, b_words.get(),
 657                                          m_width, mont.get()));
 658       ASSERT_TRUE(bn_mod_mul_montgomery_small(
 659           r_words.get(), m_width, a_words.get(), m_width, b_words.get(), m_width,
 660           mont.get()));
 661       // Use the second half of |tmp| so ASan will catch out-of-bounds writes.
 662       ASSERT_TRUE(bn_from_montgomery_small(r_words.get(), m_width, r_words.get(),
 663                                            m_width, mont.get()));
 664       ASSERT_TRUE(bn_set_words(ret.get(), r_words.get(), m_width));
 665       EXPECT_BIGNUMS_EQUAL("A * B (mod M) (Montgomery, words)", mod_mul.get(),
 666                            ret.get());
 667     }
 668 #endif
 669   }
 670 }
 671
 672 static void TestModSquare(BIGNUMFileTest *t, BN_CTX *ctx) {
 673   bssl::UniquePtr<BIGNUM> a = t->GetBIGNUM("A");
 674   bssl::UniquePtr<BIGNUM> m = t->GetBIGNUM("M");
 675   bssl::UniquePtr<BIGNUM> mod_square = t->GetBIGNUM("ModSquare");
 676   ASSERT_TRUE(a);
 677   ASSERT_TRUE(m);
 678   ASSERT_TRUE(mod_square);
 679
 680   bssl::UniquePtr<BIGNUM> a_copy(BN_new());
 681   bssl::UniquePtr<BIGNUM> ret(BN_new());
 682   ASSERT_TRUE(ret);
 683   ASSERT_TRUE(a_copy);
 684   ASSERT_TRUE(BN_mod_mul(ret.get(), a.get(), a.get(), m.get(), ctx));
 685   EXPECT_BIGNUMS_EQUAL("A * A (mod M)", mod_square.get(), ret.get());
 686
 687   // Repeat the operation with |a_copy|.
 688   ASSERT_TRUE(BN_copy(a_copy.get(), a.get()));
 689   ASSERT_TRUE(BN_mod_mul(ret.get(), a.get(), a_copy.get(), m.get(), ctx));
 690   EXPECT_BIGNUMS_EQUAL("A * A_copy (mod M)", mod_square.get(), ret.get());
 691
 692   if (BN_is_odd(m.get())) {
 693     // Reduce |a| and test the Montgomery version.
 694     bssl::UniquePtr<BN_MONT_CTX> mont(
 695         BN_MONT_CTX_new_for_modulus(m.get(), ctx));
 696     bssl::UniquePtr<BIGNUM> a_tmp(BN_new());
 697     ASSERT_TRUE(mont);
 698     ASSERT_TRUE(a_tmp);
 699     ASSERT_TRUE(BN_nnmod(a.get(), a.get(), m.get(), ctx));
 700     ASSERT_TRUE(BN_to_montgomery(a_tmp.get(), a.get(), mont.get(), ctx));
 701     ASSERT_TRUE(BN_mod_mul_montgomery(ret.get(), a_tmp.get(), a_tmp.get(),
 702                                       mont.get(), ctx));
 703     ASSERT_TRUE(BN_from_montgomery(ret.get(), ret.get(), mont.get(), ctx));
 704     EXPECT_BIGNUMS_EQUAL("A * A (mod M) (Montgomery)", mod_square.get(),
 705                          ret.get());
 706
 707     // Repeat the operation with |a_copy|.
 708     ASSERT_TRUE(BN_copy(a_copy.get(), a_tmp.get()));
 709     ASSERT_TRUE(BN_mod_mul_montgomery(ret.get(), a_tmp.get(), a_copy.get(),
 710                                       mont.get(), ctx));
 711     ASSERT_TRUE(BN_from_montgomery(ret.get(), ret.get(), mont.get(), ctx));
 712     EXPECT_BIGNUMS_EQUAL("A * A_copy (mod M) (Montgomery)", mod_square.get(),
 713                          ret.get());
 714
 715 #if !defined(BORINGSSL_SHARED_LIBRARY)
 716     size_t m_width = static_cast<size_t>(bn_minimal_width(m.get()));
 717     if (m_width <= BN_SMALL_MAX_WORDS) {
 718       std::unique_ptr<BN_ULONG[]> a_words(new BN_ULONG[m_width]),
 719           a_copy_words(new BN_ULONG[m_width]), r_words(new BN_ULONG[m_width]);
 720       ASSERT_TRUE(bn_copy_words(a_words.get(), m_width, a.get()));
 721       ASSERT_TRUE(bn_to_montgomery_small(a_words.get(), m_width, a_words.get(),
 722                                          m_width, mont.get()));
 723       ASSERT_TRUE(bn_mod_mul_montgomery_small(
 724           r_words.get(), m_width, a_words.get(), m_width, a_words.get(),
 725           m_width, mont.get()));
 726       ASSERT_TRUE(bn_from_montgomery_small(r_words.get(), m_width,
 727                                            r_words.get(), m_width, mont.get()));
 728       ASSERT_TRUE(bn_set_words(ret.get(), r_words.get(), m_width));
 729       EXPECT_BIGNUMS_EQUAL("A * A (mod M) (Montgomery, words)",
 730                            mod_square.get(), ret.get());
 731
 732       // Repeat the operation with |a_copy_words|.
 733       OPENSSL_memcpy(a_copy_words.get(), a_words.get(),
 734                      m_width * sizeof(BN_ULONG));
 735       ASSERT_TRUE(bn_mod_mul_montgomery_small(
 736           r_words.get(), m_width, a_words.get(), m_width, a_copy_words.get(),
 737           m_width, mont.get()));
 738       // Use the second half of |tmp| so ASan will catch out-of-bounds writes.
 739       ASSERT_TRUE(bn_from_montgomery_small(r_words.get(), m_width,
 740                                            r_words.get(), m_width, mont.get()));
 741       ASSERT_TRUE(bn_set_words(ret.get(), r_words.get(), m_width));
 742       EXPECT_BIGNUMS_EQUAL("A * A_copy (mod M) (Montgomery, words)",
 743                            mod_square.get(), ret.get());
 744     }
 745 #endif
 746   }
 747 }
 748
 749 static void TestModExp(BIGNUMFileTest *t, BN_CTX *ctx) {
 750   bssl::UniquePtr<BIGNUM> a = t->GetBIGNUM("A");
 751   bssl::UniquePtr<BIGNUM> e = t->GetBIGNUM("E");
 752   bssl::UniquePtr<BIGNUM> m = t->GetBIGNUM("M");
 753   bssl::UniquePtr<BIGNUM> mod_exp = t->GetBIGNUM("ModExp");
 754   ASSERT_TRUE(a);
 755   ASSERT_TRUE(e);
 756   ASSERT_TRUE(m);
 757   ASSERT_TRUE(mod_exp);
 758
 759   bssl::UniquePtr<BIGNUM> ret(BN_new());
 760   ASSERT_TRUE(ret);
 761   ASSERT_TRUE(BN_mod_exp(ret.get(), a.get(), e.get(), m.get(), ctx));
 762   EXPECT_BIGNUMS_EQUAL("A ^ E (mod M)", mod_exp.get(), ret.get());
 763
 764   if (BN_is_odd(m.get())) {
 765     ASSERT_TRUE(
 766         BN_mod_exp_mont(ret.get(), a.get(), e.get(), m.get(), ctx, NULL));
 767     EXPECT_BIGNUMS_EQUAL("A ^ E (mod M) (Montgomery)", mod_exp.get(),
 768                          ret.get());
 769
 770     ASSERT_TRUE(BN_mod_exp_mont_consttime(ret.get(), a.get(), e.get(), m.get(),
 771                                           ctx, NULL));
 772     EXPECT_BIGNUMS_EQUAL("A ^ E (mod M) (constant-time)", mod_exp.get(),
 773                          ret.get());
 774
 775 #if !defined(BORINGSSL_SHARED_LIBRARY)
 776     size_t m_width = static_cast<size_t>(bn_minimal_width(m.get()));
 777     if (m_width <= BN_SMALL_MAX_WORDS) {
 778       bssl::UniquePtr<BN_MONT_CTX> mont(
 779           BN_MONT_CTX_new_for_modulus(m.get(), ctx));
 780       ASSERT_TRUE(mont.get());
 781       ASSERT_TRUE(BN_nnmod(a.get(), a.get(), m.get(), ctx));
 782       std::unique_ptr<BN_ULONG[]> r_words(new BN_ULONG[m_width]),
 783           a_words(new BN_ULONG[m_width]);
 784       ASSERT_TRUE(bn_copy_words(a_words.get(), m_width, a.get()));
 785       ASSERT_TRUE(bn_to_montgomery_small(a_words.get(), m_width, a_words.get(),
 786                                          m_width, mont.get()));
 787       ASSERT_TRUE(bn_mod_exp_mont_small(r_words.get(), m_width, a_words.get(),
 788                                         m_width, e->d, e->width, mont.get()));
 789       ASSERT_TRUE(bn_from_montgomery_small(r_words.get(), m_width,
 790                                            r_words.get(), m_width, mont.get()));
 791       ASSERT_TRUE(bn_set_words(ret.get(), r_words.get(), m_width));
 792       EXPECT_BIGNUMS_EQUAL("A ^ E (mod M) (Montgomery, words)", mod_exp.get(),
 793                            ret.get());
 794     }
 795 #endif
 796   }
 797 }
 798
 799 static void TestExp(BIGNUMFileTest *t, BN_CTX *ctx) {
 800   bssl::UniquePtr<BIGNUM> a = t->GetBIGNUM("A");
 801   bssl::UniquePtr<BIGNUM> e = t->GetBIGNUM("E");
 802   bssl::UniquePtr<BIGNUM> exp = t->GetBIGNUM("Exp");
 803   ASSERT_TRUE(a);
 804   ASSERT_TRUE(e);
 805   ASSERT_TRUE(exp);
 806
 807   bssl::UniquePtr<BIGNUM> ret(BN_new());
 808   ASSERT_TRUE(ret);
 809   ASSERT_TRUE(BN_exp(ret.get(), a.get(), e.get(), ctx));
 810   EXPECT_BIGNUMS_EQUAL("A ^ E", exp.get(), ret.get());
 811 }
 812
 813 static void TestModSqrt(BIGNUMFileTest *t, BN_CTX *ctx) {
 814   bssl::UniquePtr<BIGNUM> a = t->GetBIGNUM("A");
 815   bssl::UniquePtr<BIGNUM> p = t->GetBIGNUM("P");
 816   bssl::UniquePtr<BIGNUM> mod_sqrt = t->GetBIGNUM("ModSqrt");
 817   bssl::UniquePtr<BIGNUM> mod_sqrt2(BN_new());
 818   ASSERT_TRUE(a);
 819   ASSERT_TRUE(p);
 820   ASSERT_TRUE(mod_sqrt);
 821   ASSERT_TRUE(mod_sqrt2);
 822   // There are two possible answers.
 823   ASSERT_TRUE(BN_sub(mod_sqrt2.get(), p.get(), mod_sqrt.get()));
 824
 825   // -0 is 0, not P.
 826   if (BN_is_zero(mod_sqrt.get())) {
 827     BN_zero(mod_sqrt2.get());
 828   }
 829
 830   bssl::UniquePtr<BIGNUM> ret(BN_new());
 831   ASSERT_TRUE(ret);
 832   ASSERT_TRUE(BN_mod_sqrt(ret.get(), a.get(), p.get(), ctx));
 833   if (BN_cmp(ret.get(), mod_sqrt2.get()) != 0) {
 834     EXPECT_BIGNUMS_EQUAL("sqrt(A) (mod P)", mod_sqrt.get(), ret.get());
 835   }
 836 }
 837
 838 static void TestNotModSquare(BIGNUMFileTest *t, BN_CTX *ctx) {
 839   bssl::UniquePtr<BIGNUM> not_mod_square = t->GetBIGNUM("NotModSquare");
 840   bssl::UniquePtr<BIGNUM> p = t->GetBIGNUM("P");
 841   bssl::UniquePtr<BIGNUM> ret(BN_new());
 842   ASSERT_TRUE(not_mod_square);
 843   ASSERT_TRUE(p);
 844   ASSERT_TRUE(ret);
 845
 846   EXPECT_FALSE(BN_mod_sqrt(ret.get(), not_mod_square.get(), p.get(), ctx))
 847       << "BN_mod_sqrt unexpectedly succeeded.";
 848
 849   uint32_t err = ERR_peek_error();
 850   EXPECT_EQ(ERR_LIB_BN, ERR_GET_LIB(err));
 851   EXPECT_EQ(BN_R_NOT_A_SQUARE, ERR_GET_REASON(err));
 852   ERR_clear_error();
 853 }
 854
 855 static void TestModInv(BIGNUMFileTest *t, BN_CTX *ctx) {
 856   bssl::UniquePtr<BIGNUM> a = t->GetBIGNUM("A");
 857   bssl::UniquePtr<BIGNUM> m = t->GetBIGNUM("M");
 858   bssl::UniquePtr<BIGNUM> mod_inv = t->GetBIGNUM("ModInv");
 859   ASSERT_TRUE(a);
 860   ASSERT_TRUE(m);
 861   ASSERT_TRUE(mod_inv);
 862
 863   bssl::UniquePtr<BIGNUM> ret(BN_new());
 864   ASSERT_TRUE(ret);
 865   ASSERT_TRUE(BN_mod_inverse(ret.get(), a.get(), m.get(), ctx));
 866   EXPECT_BIGNUMS_EQUAL("inv(A) (mod M)", mod_inv.get(), ret.get());
 867
 868   ASSERT_TRUE(BN_gcd(ret.get(), a.get(), m.get(), ctx));
 869   EXPECT_BIGNUMS_EQUAL("GCD(A, M)", BN_value_one(), ret.get());
 870
 871   ASSERT_TRUE(BN_nnmod(a.get(), a.get(), m.get(), ctx));
 872   int no_inverse;
 873   ASSERT_TRUE(
 874       bn_mod_inverse_consttime(ret.get(), &no_inverse, a.get(), m.get(), ctx));
 875   EXPECT_BIGNUMS_EQUAL("inv(A) (mod M) (constant-time)", mod_inv.get(),
 876                        ret.get());
 877 }
 878
 879 static void TestGCD(BIGNUMFileTest *t, BN_CTX *ctx) {
 880   bssl::UniquePtr<BIGNUM> a = t->GetBIGNUM("A");
 881   bssl::UniquePtr<BIGNUM> b = t->GetBIGNUM("B");
 882   bssl::UniquePtr<BIGNUM> gcd = t->GetBIGNUM("GCD");
 883   bssl::UniquePtr<BIGNUM> lcm = t->GetBIGNUM("LCM");
 884   ASSERT_TRUE(a);
 885   ASSERT_TRUE(b);
 886   ASSERT_TRUE(gcd);
 887   ASSERT_TRUE(lcm);
 888
 889   bssl::UniquePtr<BIGNUM> ret(BN_new());
 890   ASSERT_TRUE(ret);
 891   ASSERT_TRUE(BN_gcd(ret.get(), a.get(), b.get(), ctx));
 892   EXPECT_BIGNUMS_EQUAL("GCD(A, B)", gcd.get(), ret.get());
 893
 894   if (!BN_is_one(gcd.get())) {
 895     EXPECT_FALSE(BN_mod_inverse(ret.get(), a.get(), b.get(), ctx))
 896         << "A^-1 (mod B) computed, but it does not exist";
 897     EXPECT_FALSE(BN_mod_inverse(ret.get(), b.get(), a.get(), ctx))
 898         << "B^-1 (mod A) computed, but it does not exist";
 899
 900     if (!BN_is_zero(b.get())) {
 901       bssl::UniquePtr<BIGNUM> a_reduced(BN_new());
 902       ASSERT_TRUE(a_reduced);
 903       ASSERT_TRUE(BN_nnmod(a_reduced.get(), a.get(), b.get(), ctx));
 904       int no_inverse;
 905       EXPECT_FALSE(bn_mod_inverse_consttime(ret.get(), &no_inverse,
 906                                             a_reduced.get(), b.get(), ctx))
 907           << "A^-1 (mod B) computed, but it does not exist";
 908       EXPECT_TRUE(no_inverse);
 909     }
 910
 911     if (!BN_is_zero(a.get())) {
 912       bssl::UniquePtr<BIGNUM> b_reduced(BN_new());
 913       ASSERT_TRUE(b_reduced);
 914       ASSERT_TRUE(BN_nnmod(b_reduced.get(), b.get(), a.get(), ctx));
 915       int no_inverse;
 916       EXPECT_FALSE(bn_mod_inverse_consttime(ret.get(), &no_inverse,
 917                                             b_reduced.get(), a.get(), ctx))
 918           << "B^-1 (mod A) computed, but it does not exist";
 919       EXPECT_TRUE(no_inverse);
 920     }
 921   }
 922
 923   int is_relative_prime;
 924   ASSERT_TRUE(
 925       bn_is_relatively_prime(&is_relative_prime, a.get(), b.get(), ctx));
 926   EXPECT_EQ(is_relative_prime, BN_is_one(gcd.get()));
 927
 928   if (!BN_is_zero(gcd.get())) {
 929     ASSERT_TRUE(bn_lcm_consttime(ret.get(), a.get(), b.get(), ctx));
 930     EXPECT_BIGNUMS_EQUAL("LCM(A, B)", lcm.get(), ret.get());
 931   }
 932 }
 933
 934 class BNTest : public testing::Test {
 935  protected:
 936   void SetUp() override {
 937     ctx_.reset(BN_CTX_new());
 938     ASSERT_TRUE(ctx_);
 939   }
 940
 941   BN_CTX *ctx() { return ctx_.get(); }
 942
 943  private:
 944   bssl::UniquePtr<BN_CTX> ctx_;
 945 };
 946
 947 TEST_F(BNTest, TestVectors) {
 948   static const struct {
 949     const char *name;
 950     void (*func)(BIGNUMFileTest *t, BN_CTX *ctx);
 951   } kTests[] = {
 952       {"Sum", TestSum},
 953       {"LShift1", TestLShift1},
 954       {"LShift", TestLShift},
 955       {"RShift", TestRShift},
 956       {"Square", TestSquare},
 957       {"Product", TestProduct},
 958       {"Quotient", TestQuotient},
 959       {"ModMul", TestModMul},
 960       {"ModSquare", TestModSquare},
 961       {"ModExp", TestModExp},
 962       {"Exp", TestExp},
 963       {"ModSqrt", TestModSqrt},
 964       {"NotModSquare", TestNotModSquare},
 965       {"ModInv", TestModInv},
 966       {"GCD", TestGCD},
 967   };
 968
 969   FileTestGTest("crypto/fipsmodule/bn/bn_tests.txt", [&](FileTest *t) {
 970     void (*func)(BIGNUMFileTest *t, BN_CTX *ctx) = nullptr;
 971     for (const auto &test : kTests) {
 972       if (t->GetType() == test.name) {
 973         func = test.func;
 974         break;
 975       }
 976     }
 977     if (!func) {
 978       FAIL() << "Unknown test type: " << t->GetType();
 979       return;
 980     }
 981
 982     // Run the test with normalize-sized |BIGNUM|s.
 983     BIGNUMFileTest bn_test(t, 0);
 984     BN_CTX_start(ctx());
 985     func(&bn_test, ctx());
 986     BN_CTX_end(ctx());
 987     unsigned num_bignums = bn_test.num_bignums();
 988
 989     // Repeat the test with all combinations of large and small |BIGNUM|s.
 990     for (unsigned large_mask = 1; large_mask < (1u << num_bignums);
 991          large_mask++) {
 992       SCOPED_TRACE(large_mask);
 993       BIGNUMFileTest bn_test2(t, large_mask);
 994       BN_CTX_start(ctx());
 995       func(&bn_test2, ctx());
 996       BN_CTX_end(ctx());
 997     }
 998   });
 999 }
1000
1001 TEST_F(BNTest, BN2BinPadded) {
1002   uint8_t zeros[256], out[256], reference[128];
1003
1004   OPENSSL_memset(zeros, 0, sizeof(zeros));
1005
1006   // Test edge case at 0.
1007   bssl::UniquePtr<BIGNUM> n(BN_new());
1008   ASSERT_TRUE(n);
1009   ASSERT_TRUE(BN_bn2bin_padded(NULL, 0, n.get()));
1010
1011   OPENSSL_memset(out, -1, sizeof(out));
1012   ASSERT_TRUE(BN_bn2bin_padded(out, sizeof(out), n.get()));
1013   EXPECT_EQ(Bytes(zeros), Bytes(out));
1014
1015   // Test a random numbers at various byte lengths.
1016   for (size_t bytes = 128 - 7; bytes <= 128; bytes++) {
1017     ASSERT_TRUE(
1018         BN_rand(n.get(), bytes * 8, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY));
1019     ASSERT_EQ(bytes, BN_num_bytes(n.get()));
1020     ASSERT_EQ(bytes, BN_bn2bin(n.get(), reference));
1021
1022     // Empty buffer should fail.
1023     EXPECT_FALSE(BN_bn2bin_padded(NULL, 0, n.get()));
1024
1025     // One byte short should fail.
1026     EXPECT_FALSE(BN_bn2bin_padded(out, bytes - 1, n.get()));
1027
1028     // Exactly right size should encode.
1029     ASSERT_TRUE(BN_bn2bin_padded(out, bytes, n.get()));
1030     EXPECT_EQ(Bytes(reference, bytes), Bytes(out, bytes));
1031
1032     // Pad up one byte extra.
1033     ASSERT_TRUE(BN_bn2bin_padded(out, bytes + 1, n.get()));
1034     EXPECT_EQ(0u, out[0]);
1035     EXPECT_EQ(Bytes(reference, bytes), Bytes(out + 1, bytes));
1036
1037     // Pad up to 256.
1038     ASSERT_TRUE(BN_bn2bin_padded(out, sizeof(out), n.get()));
1039     EXPECT_EQ(Bytes(zeros, sizeof(out) - bytes),
1040               Bytes(out, sizeof(out) - bytes));
1041     EXPECT_EQ(Bytes(reference, bytes), Bytes(out + sizeof(out) - bytes, bytes));
1042
1043     // Repeat some tests with a non-minimal |BIGNUM|.
1044     EXPECT_TRUE(bn_resize_words(n.get(), 32));
1045
1046     EXPECT_FALSE(BN_bn2bin_padded(out, bytes - 1, n.get()));
1047
1048     ASSERT_TRUE(BN_bn2bin_padded(out, bytes + 1, n.get()));
1049     EXPECT_EQ(0u, out[0]);
1050     EXPECT_EQ(Bytes(reference, bytes), Bytes(out + 1, bytes));
1051   }
1052 }
1053
1054 TEST_F(BNTest, LittleEndian) {
1055   bssl::UniquePtr<BIGNUM> x(BN_new());
1056   bssl::UniquePtr<BIGNUM> y(BN_new());
1057   ASSERT_TRUE(x);
1058   ASSERT_TRUE(y);
1059
1060   // Test edge case at 0. Fill |out| with garbage to ensure |BN_bn2le_padded|
1061   // wrote the result.
1062   uint8_t out[256], zeros[256];
1063   OPENSSL_memset(out, -1, sizeof(out));
1064   OPENSSL_memset(zeros, 0, sizeof(zeros));
1065   ASSERT_TRUE(BN_bn2le_padded(out, sizeof(out), x.get()));
1066   EXPECT_EQ(Bytes(zeros), Bytes(out));
1067
1068   ASSERT_TRUE(BN_le2bn(out, sizeof(out), y.get()));
1069   EXPECT_BIGNUMS_EQUAL("BN_le2bn round-trip", x.get(), y.get());
1070
1071   // Test random numbers at various byte lengths.
1072   for (size_t bytes = 128 - 7; bytes <= 128; bytes++) {
1073     ASSERT_TRUE(
1074         BN_rand(x.get(), bytes * 8, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY));
1075
1076     // Fill |out| with garbage to ensure |BN_bn2le_padded| wrote the result.
1077     OPENSSL_memset(out, -1, sizeof(out));
1078     ASSERT_TRUE(BN_bn2le_padded(out, sizeof(out), x.get()));
1079
1080     // Compute the expected value by reversing the big-endian output.
1081     uint8_t expected[sizeof(out)];
1082     ASSERT_TRUE(BN_bn2bin_padded(expected, sizeof(expected), x.get()));
1083     for (size_t i = 0; i < sizeof(expected) / 2; i++) {
1084       uint8_t tmp = expected[i];
1085       expected[i] = expected[sizeof(expected) - 1 - i];
1086       expected[sizeof(expected) - 1 - i] = tmp;
1087     }
1088
1089     EXPECT_EQ(Bytes(out), Bytes(expected));
1090
1091     // Make sure the decoding produces the same BIGNUM.
1092     ASSERT_TRUE(BN_le2bn(out, bytes, y.get()));
1093     EXPECT_BIGNUMS_EQUAL("BN_le2bn round-trip", x.get(), y.get());
1094   }
1095 }
1096
1097 static int DecimalToBIGNUM(bssl::UniquePtr<BIGNUM> *out, const char *in) {
1098   BIGNUM *raw = NULL;
1099   int ret = BN_dec2bn(&raw, in);
1100   out->reset(raw);
1101   return ret;
1102 }
1103
1104 TEST_F(BNTest, Dec2BN) {
1105   bssl::UniquePtr<BIGNUM> bn;
1106   int ret = DecimalToBIGNUM(&bn, "0");
1107   ASSERT_EQ(1, ret);
1108   EXPECT_TRUE(BN_is_zero(bn.get()));
1109   EXPECT_FALSE(BN_is_negative(bn.get()));
1110
1111   ret = DecimalToBIGNUM(&bn, "256");
1112   ASSERT_EQ(3, ret);
1113   EXPECT_TRUE(BN_is_word(bn.get(), 256));
1114   EXPECT_FALSE(BN_is_negative(bn.get()));
1115
1116   ret = DecimalToBIGNUM(&bn, "-42");
1117   ASSERT_EQ(3, ret);
1118   EXPECT_TRUE(BN_abs_is_word(bn.get(), 42));
1119   EXPECT_TRUE(BN_is_negative(bn.get()));
1120
1121   ret = DecimalToBIGNUM(&bn, "-0");
1122   ASSERT_EQ(2, ret);
1123   EXPECT_TRUE(BN_is_zero(bn.get()));
1124   EXPECT_FALSE(BN_is_negative(bn.get()));
1125
1126   ret = DecimalToBIGNUM(&bn, "42trailing garbage is ignored");
1127   ASSERT_EQ(2, ret);
1128   EXPECT_TRUE(BN_abs_is_word(bn.get(), 42));
1129   EXPECT_FALSE(BN_is_negative(bn.get()));
1130 }
1131
1132 TEST_F(BNTest, Hex2BN) {
1133   bssl::UniquePtr<BIGNUM> bn;
1134   int ret = HexToBIGNUM(&bn, "0");
1135   ASSERT_EQ(1, ret);
1136   EXPECT_TRUE(BN_is_zero(bn.get()));
1137   EXPECT_FALSE(BN_is_negative(bn.get()));
1138
1139   ret = HexToBIGNUM(&bn, "256");
1140   ASSERT_EQ(3, ret);
1141   EXPECT_TRUE(BN_is_word(bn.get(), 0x256));
1142   EXPECT_FALSE(BN_is_negative(bn.get()));
1143
1144   ret = HexToBIGNUM(&bn, "-42");
1145   ASSERT_EQ(3, ret);
1146   EXPECT_TRUE(BN_abs_is_word(bn.get(), 0x42));
1147   EXPECT_TRUE(BN_is_negative(bn.get()));
1148
1149   ret = HexToBIGNUM(&bn, "-0");
1150   ASSERT_EQ(2, ret);
1151   EXPECT_TRUE(BN_is_zero(bn.get()));
1152   EXPECT_FALSE(BN_is_negative(bn.get()));
1153
1154   ret = HexToBIGNUM(&bn, "abctrailing garbage is ignored");
1155   ASSERT_EQ(3, ret);
1156   EXPECT_TRUE(BN_is_word(bn.get(), 0xabc));
1157   EXPECT_FALSE(BN_is_negative(bn.get()));
1158 }
1159
1160 static bssl::UniquePtr<BIGNUM> ASCIIToBIGNUM(const char *in) {
1161   BIGNUM *raw = NULL;
1162   if (!BN_asc2bn(&raw, in)) {
1163     return nullptr;
1164   }
1165   return bssl::UniquePtr<BIGNUM>(raw);
1166 }
1167
1168 TEST_F(BNTest, ASC2BN) {
1169   bssl::UniquePtr<BIGNUM> bn = ASCIIToBIGNUM("0");
1170   ASSERT_TRUE(bn);
1171   EXPECT_TRUE(BN_is_zero(bn.get()));
1172   EXPECT_FALSE(BN_is_negative(bn.get()));
1173
1174   bn = ASCIIToBIGNUM("256");
1175   ASSERT_TRUE(bn);
1176   EXPECT_TRUE(BN_is_word(bn.get(), 256));
1177   EXPECT_FALSE(BN_is_negative(bn.get()));
1178
1179   bn = ASCIIToBIGNUM("-42");
1180   ASSERT_TRUE(bn);
1181   EXPECT_TRUE(BN_abs_is_word(bn.get(), 42));
1182   EXPECT_TRUE(BN_is_negative(bn.get()));
1183
1184   bn = ASCIIToBIGNUM("0x1234");
1185   ASSERT_TRUE(bn);
1186   EXPECT_TRUE(BN_is_word(bn.get(), 0x1234));
1187   EXPECT_FALSE(BN_is_negative(bn.get()));
1188
1189   bn = ASCIIToBIGNUM("0X1234");
1190   ASSERT_TRUE(bn);
1191   EXPECT_TRUE(BN_is_word(bn.get(), 0x1234));
1192   EXPECT_FALSE(BN_is_negative(bn.get()));
1193
1194   bn = ASCIIToBIGNUM("-0xabcd");
1195   ASSERT_TRUE(bn);
1196   EXPECT_TRUE(BN_abs_is_word(bn.get(), 0xabcd));
1197   EXPECT_FALSE(!BN_is_negative(bn.get()));
1198
1199   bn = ASCIIToBIGNUM("-0");
1200   ASSERT_TRUE(bn);
1201   EXPECT_TRUE(BN_is_zero(bn.get()));
1202   EXPECT_FALSE(BN_is_negative(bn.get()));
1203
1204   bn = ASCIIToBIGNUM("123trailing garbage is ignored");
1205   ASSERT_TRUE(bn);
1206   EXPECT_TRUE(BN_is_word(bn.get(), 123));
1207   EXPECT_FALSE(BN_is_negative(bn.get()));
1208 }
1209
1210 struct MPITest {
1211   const char *base10;
1212   const char *mpi;
1213   size_t mpi_len;
1214 };
1215
1216 static const MPITest kMPITests[] = {
1217   { "0", "\x00\x00\x00\x00", 4 },
1218   { "1", "\x00\x00\x00\x01\x01", 5 },
1219   { "-1", "\x00\x00\x00\x01\x81", 5 },
1220   { "128", "\x00\x00\x00\x02\x00\x80", 6 },
1221   { "256", "\x00\x00\x00\x02\x01\x00", 6 },
1222   { "-256", "\x00\x00\x00\x02\x81\x00", 6 },
1223 };
1224
1225 TEST_F(BNTest, MPI) {
1226   uint8_t scratch[8];
1227
1228   for (const auto &test : kMPITests) {
1229     SCOPED_TRACE(test.base10);
1230     bssl::UniquePtr<BIGNUM> bn(ASCIIToBIGNUM(test.base10));
1231     ASSERT_TRUE(bn);
1232
1233     const size_t mpi_len = BN_bn2mpi(bn.get(), NULL);
1234     ASSERT_LE(mpi_len, sizeof(scratch)) << "MPI size is too large to test";
1235
1236     const size_t mpi_len2 = BN_bn2mpi(bn.get(), scratch);
1237     EXPECT_EQ(mpi_len, mpi_len2);
1238     EXPECT_EQ(Bytes(test.mpi, test.mpi_len), Bytes(scratch, mpi_len));
1239
1240     bssl::UniquePtr<BIGNUM> bn2(BN_mpi2bn(scratch, mpi_len, NULL));
1241     ASSERT_TRUE(bn2) << "failed to parse";
1242     EXPECT_BIGNUMS_EQUAL("BN_mpi2bn", bn.get(), bn2.get());
1243   }
1244 }
1245
1246 TEST_F(BNTest, Rand) {
1247   bssl::UniquePtr<BIGNUM> bn(BN_new());
1248   ASSERT_TRUE(bn);
1249
1250   static const int kTop[] = {BN_RAND_TOP_ANY, BN_RAND_TOP_ONE, BN_RAND_TOP_TWO};
1251   static const int kBottom[] = {BN_RAND_BOTTOM_ANY, BN_RAND_BOTTOM_ODD};
1252   for (unsigned bits = 0; bits < 256; bits++) {
1253     SCOPED_TRACE(bits);
1254     for (int top : kTop) {
1255       SCOPED_TRACE(top);
1256       for (int bottom : kBottom) {
1257         SCOPED_TRACE(bottom);
1258
1259         // Generate 100 numbers and ensure that they have the expected bit
1260         // patterns. The probability of any one bit not covering both its values
1261         // is 2^-100.
1262         bool seen_n_1_clear = false, seen_n_1_set = false;
1263         bool seen_n_2_clear = false, seen_n_2_set = false;
1264         bool seen_0_clear = false, seen_0_set = false;
1265         for (int i = 0; i < 100; i++) {
1266           ASSERT_TRUE(BN_rand(bn.get(), bits, top, bottom));
1267           EXPECT_LE(BN_num_bits(bn.get()), bits);
1268           if (BN_is_bit_set(bn.get(), bits - 1)) {
1269             seen_n_1_set = true;
1270           } else {
1271             seen_n_1_clear = true;
1272           }
1273           if (BN_is_bit_set(bn.get(), bits - 2)) {
1274             seen_n_2_set = true;
1275           } else {
1276             seen_n_2_clear = true;
1277           }
1278           if (BN_is_bit_set(bn.get(), 0)) {
1279             seen_0_set = true;
1280           } else {
1281             seen_0_clear = true;
1282           }
1283         }
1284
1285         if (bits > 0) {
1286           EXPECT_TRUE(seen_0_set);
1287           EXPECT_TRUE(seen_n_1_set);
1288           if (bits > 1) {
1289             EXPECT_TRUE(seen_n_2_set);
1290           }
1291         }
1292
1293         if (bits == 0) {
1294           // Nothing additional to check. The |BN_num_bits| check ensures we
1295           // always got zero.
1296         } else if (bits == 1) {
1297           // Bit zero is bit n-1.
1298           EXPECT_EQ(bottom == BN_RAND_BOTTOM_ANY && top == BN_RAND_TOP_ANY,
1299                     seen_0_clear);
1300         } else if (bits == 2) {
1301           // Bit zero is bit n-2.
1302           EXPECT_EQ(bottom == BN_RAND_BOTTOM_ANY && top != BN_RAND_TOP_TWO,
1303                     seen_0_clear);
1304           EXPECT_EQ(top == BN_RAND_TOP_ANY, seen_n_1_clear);
1305         } else {
1306           EXPECT_EQ(bottom == BN_RAND_BOTTOM_ANY, seen_0_clear);
1307           EXPECT_EQ(top != BN_RAND_TOP_TWO, seen_n_2_clear);
1308           EXPECT_EQ(top == BN_RAND_TOP_ANY, seen_n_1_clear);
1309         }
1310       }
1311     }
1312   }
1313 }
1314
1315 TEST_F(BNTest, RandRange) {
1316   bssl::UniquePtr<BIGNUM> bn(BN_new()), six(BN_new());
1317   ASSERT_TRUE(bn);
1318   ASSERT_TRUE(six);
1319   ASSERT_TRUE(BN_set_word(six.get(), 6));
1320
1321   // Generate 1,000 random numbers and ensure they all stay in range. This check
1322   // may flakily pass when it should have failed but will not flakily fail.
1323   bool seen[6] = {false, false, false, false, false};
1324   for (unsigned i = 0; i < 1000; i++) {
1325     SCOPED_TRACE(i);
1326     ASSERT_TRUE(BN_rand_range_ex(bn.get(), 1, six.get()));
1327
1328     BN_ULONG word = BN_get_word(bn.get());
1329     if (BN_is_negative(bn.get()) ||
1330         word < 1 ||
1331         word >= 6) {
1332       FAIL() << "BN_rand_range_ex generated invalid value: " << word;
1333     }
1334
1335     seen[word] = true;
1336   }
1337
1338   // Test that all numbers were accounted for. Note this test is probabilistic
1339   // and may flakily fail when it should have passed. As an upper-bound on the
1340   // failure probability, we'll never see any one number with probability
1341   // (4/5)^1000, so the probability of failure is at most 5*(4/5)^1000. This is
1342   // around 1 in 2^320.
1343   for (unsigned i = 1; i < 6; i++) {
1344     EXPECT_TRUE(seen[i]) << "BN_rand_range failed to generated " << i;
1345   }
1346 }
1347
1348 struct ASN1Test {
1349   const char *value_ascii;
1350   const char *der;
1351   size_t der_len;
1352 };
1353
1354 static const ASN1Test kASN1Tests[] = {
1355     {"0", "\x02\x01\x00", 3},
1356     {"1", "\x02\x01\x01", 3},
1357     {"127", "\x02\x01\x7f", 3},
1358     {"128", "\x02\x02\x00\x80", 4},
1359     {"0xdeadbeef", "\x02\x05\x00\xde\xad\xbe\xef", 7},
1360     {"0x0102030405060708",
1361      "\x02\x08\x01\x02\x03\x04\x05\x06\x07\x08", 10},
1362     {"0xffffffffffffffff",
1363       "\x02\x09\x00\xff\xff\xff\xff\xff\xff\xff\xff", 11},
1364 };
1365
1366 struct ASN1InvalidTest {
1367   const char *der;
1368   size_t der_len;
1369 };
1370
1371 static const ASN1InvalidTest kASN1InvalidTests[] = {
1372     // Bad tag.
1373     {"\x03\x01\x00", 3},
1374     // Empty contents.
1375     {"\x02\x00", 2},
1376     // Negative numbers.
1377     {"\x02\x01\x80", 3},
1378     {"\x02\x01\xff", 3},
1379     // Unnecessary leading zeros.
1380     {"\x02\x02\x00\x01", 4},
1381 };
1382
1383 TEST_F(BNTest, ASN1) {
1384   for (const ASN1Test &test : kASN1Tests) {
1385     SCOPED_TRACE(test.value_ascii);
1386     bssl::UniquePtr<BIGNUM> bn = ASCIIToBIGNUM(test.value_ascii);
1387     ASSERT_TRUE(bn);
1388
1389     // Test that the input is correctly parsed.
1390     bssl::UniquePtr<BIGNUM> bn2(BN_new());
1391     ASSERT_TRUE(bn2);
1392     CBS cbs;
1393     CBS_init(&cbs, reinterpret_cast<const uint8_t*>(test.der), test.der_len);
1394     ASSERT_TRUE(BN_parse_asn1_unsigned(&cbs, bn2.get()));
1395     EXPECT_EQ(0u, CBS_len(&cbs));
1396     EXPECT_BIGNUMS_EQUAL("decode ASN.1", bn.get(), bn2.get());
1397
1398     // Test the value serializes correctly.
1399     bssl::ScopedCBB cbb;
1400     uint8_t *der;
1401     size_t der_len;
1402     ASSERT_TRUE(CBB_init(cbb.get(), 0));
1403     ASSERT_TRUE(BN_marshal_asn1(cbb.get(), bn.get()));
1404     ASSERT_TRUE(CBB_finish(cbb.get(), &der, &der_len));
1405     bssl::UniquePtr<uint8_t> delete_der(der);
1406     EXPECT_EQ(Bytes(test.der, test.der_len), Bytes(der, der_len));
1407   }
1408
1409   for (const ASN1InvalidTest &test : kASN1InvalidTests) {
1410     SCOPED_TRACE(Bytes(test.der, test.der_len));;
1411     bssl::UniquePtr<BIGNUM> bn(BN_new());
1412     ASSERT_TRUE(bn);
1413     CBS cbs;
1414     CBS_init(&cbs, reinterpret_cast<const uint8_t *>(test.der), test.der_len);
1415     EXPECT_FALSE(BN_parse_asn1_unsigned(&cbs, bn.get()))
1416         << "Parsed invalid input.";
1417     ERR_clear_error();
1418   }
1419
1420   // Serializing negative numbers is not supported.
1421   bssl::UniquePtr<BIGNUM> bn = ASCIIToBIGNUM("-1");
1422   ASSERT_TRUE(bn);
1423   bssl::ScopedCBB cbb;
1424   ASSERT_TRUE(CBB_init(cbb.get(), 0));
1425   EXPECT_FALSE(BN_marshal_asn1(cbb.get(), bn.get()))
1426       << "Serialized negative number.";
1427   ERR_clear_error();
1428 }
1429
1430 TEST_F(BNTest, NegativeZero) {
1431   bssl::UniquePtr<BIGNUM> a(BN_new());
1432   bssl::UniquePtr<BIGNUM> b(BN_new());
1433   bssl::UniquePtr<BIGNUM> c(BN_new());
1434   ASSERT_TRUE(a);
1435   ASSERT_TRUE(b);
1436   ASSERT_TRUE(c);
1437
1438   // Test that BN_mul never gives negative zero.
1439   ASSERT_TRUE(BN_set_word(a.get(), 1));
1440   BN_set_negative(a.get(), 1);
1441   BN_zero(b.get());
1442   ASSERT_TRUE(BN_mul(c.get(), a.get(), b.get(), ctx()));
1443   EXPECT_TRUE(BN_is_zero(c.get()));
1444   EXPECT_FALSE(BN_is_negative(c.get()));
1445
1446   bssl::UniquePtr<BIGNUM> numerator(BN_new()), denominator(BN_new());
1447   ASSERT_TRUE(numerator);
1448   ASSERT_TRUE(denominator);
1449
1450   // Test that BN_div never gives negative zero in the quotient.
1451   ASSERT_TRUE(BN_set_word(numerator.get(), 1));
1452   ASSERT_TRUE(BN_set_word(denominator.get(), 2));
1453   BN_set_negative(numerator.get(), 1);
1454   ASSERT_TRUE(
1455       BN_div(a.get(), b.get(), numerator.get(), denominator.get(), ctx()));
1456   EXPECT_TRUE(BN_is_zero(a.get()));
1457   EXPECT_FALSE(BN_is_negative(a.get()));
1458
1459   // Test that BN_div never gives negative zero in the remainder.
1460   ASSERT_TRUE(BN_set_word(denominator.get(), 1));
1461   ASSERT_TRUE(
1462       BN_div(a.get(), b.get(), numerator.get(), denominator.get(), ctx()));
1463   EXPECT_TRUE(BN_is_zero(b.get()));
1464   EXPECT_FALSE(BN_is_negative(b.get()));
1465
1466   // Test that BN_set_negative will not produce a negative zero.
1467   BN_zero(a.get());
1468   BN_set_negative(a.get(), 1);
1469   EXPECT_FALSE(BN_is_negative(a.get()));
1470
1471   // Test that forcibly creating a negative zero does not break |BN_bn2hex| or
1472   // |BN_bn2dec|.
1473   a->neg = 1;
1474   bssl::UniquePtr<char> dec(BN_bn2dec(a.get()));
1475   bssl::UniquePtr<char> hex(BN_bn2hex(a.get()));
1476   ASSERT_TRUE(dec);
1477   ASSERT_TRUE(hex);
1478   EXPECT_STREQ("-0", dec.get());
1479   EXPECT_STREQ("-0", hex.get());
1480
1481   // Test that |BN_rshift| and |BN_rshift1| will not produce a negative zero.
1482   ASSERT_TRUE(BN_set_word(a.get(), 1));
1483   BN_set_negative(a.get(), 1);
1484
1485   ASSERT_TRUE(BN_rshift(b.get(), a.get(), 1));
1486   EXPECT_TRUE(BN_is_zero(b.get()));
1487   EXPECT_FALSE(BN_is_negative(b.get()));
1488
1489   ASSERT_TRUE(BN_rshift1(c.get(), a.get()));
1490   EXPECT_TRUE(BN_is_zero(c.get()));
1491   EXPECT_FALSE(BN_is_negative(c.get()));
1492
1493   // Test that |BN_div_word| will not produce a negative zero.
1494   ASSERT_NE((BN_ULONG)-1, BN_div_word(a.get(), 2));
1495   EXPECT_TRUE(BN_is_zero(a.get()));
1496   EXPECT_FALSE(BN_is_negative(a.get()));
1497 }
1498
1499 TEST_F(BNTest, BadModulus) {
1500   bssl::UniquePtr<BIGNUM> a(BN_new());
1501   bssl::UniquePtr<BIGNUM> b(BN_new());
1502   bssl::UniquePtr<BIGNUM> zero(BN_new());
1503   ASSERT_TRUE(a);
1504   ASSERT_TRUE(b);
1505   ASSERT_TRUE(zero);
1506
1507   BN_zero(zero.get());
1508
1509   EXPECT_FALSE(BN_div(a.get(), b.get(), BN_value_one(), zero.get(), ctx()));
1510   ERR_clear_error();
1511
1512   EXPECT_FALSE(
1513       BN_mod_mul(a.get(), BN_value_one(), BN_value_one(), zero.get(), ctx()));
1514   ERR_clear_error();
1515
1516   EXPECT_FALSE(
1517       BN_mod_exp(a.get(), BN_value_one(), BN_value_one(), zero.get(), ctx()));
1518   ERR_clear_error();
1519
1520   EXPECT_FALSE(BN_mod_exp_mont(a.get(), BN_value_one(), BN_value_one(),
1521                                zero.get(), ctx(), NULL));
1522   ERR_clear_error();
1523
1524   EXPECT_FALSE(BN_mod_exp_mont_consttime(
1525       a.get(), BN_value_one(), BN_value_one(), zero.get(), ctx(), nullptr));
1526   ERR_clear_error();
1527
1528   bssl::UniquePtr<BN_MONT_CTX> mont(
1529       BN_MONT_CTX_new_for_modulus(zero.get(), ctx()));
1530   EXPECT_FALSE(mont);
1531   ERR_clear_error();
1532
1533   // Some operations also may not be used with an even modulus.
1534   ASSERT_TRUE(BN_set_word(b.get(), 16));
1535
1536   mont.reset(BN_MONT_CTX_new_for_modulus(b.get(), ctx()));
1537   EXPECT_FALSE(mont);
1538   ERR_clear_error();
1539
1540   EXPECT_FALSE(BN_mod_exp_mont(a.get(), BN_value_one(), BN_value_one(), b.get(),
1541                                ctx(), NULL));
1542   ERR_clear_error();
1543
1544   EXPECT_FALSE(BN_mod_exp_mont_consttime(
1545       a.get(), BN_value_one(), BN_value_one(), b.get(), ctx(), nullptr));
1546   ERR_clear_error();
1547 }
1548
1549 // Test that 1**0 mod 1 == 0.
1550 TEST_F(BNTest, ExpModZero) {
1551   bssl::UniquePtr<BIGNUM> zero(BN_new()), a(BN_new()), r(BN_new());
1552   ASSERT_TRUE(zero);
1553   ASSERT_TRUE(a);
1554   ASSERT_TRUE(r);
1555   ASSERT_TRUE(BN_rand(a.get(), 1024, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY));
1556   BN_zero(zero.get());
1557
1558   ASSERT_TRUE(
1559       BN_mod_exp(r.get(), a.get(), zero.get(), BN_value_one(), nullptr));
1560   EXPECT_TRUE(BN_is_zero(r.get()));
1561
1562   ASSERT_TRUE(BN_mod_exp_mont(r.get(), a.get(), zero.get(), BN_value_one(),
1563                               nullptr, nullptr));
1564   EXPECT_TRUE(BN_is_zero(r.get()));
1565
1566   ASSERT_TRUE(BN_mod_exp_mont_consttime(r.get(), a.get(), zero.get(),
1567                                         BN_value_one(), nullptr, nullptr));
1568   EXPECT_TRUE(BN_is_zero(r.get()));
1569
1570   ASSERT_TRUE(BN_mod_exp_mont_word(r.get(), 42, zero.get(), BN_value_one(),
1571                                    nullptr, nullptr));
1572   EXPECT_TRUE(BN_is_zero(r.get()));
1573 }
1574
1575 TEST_F(BNTest, SmallPrime) {
1576   static const unsigned kBits = 10;
1577
1578   bssl::UniquePtr<BIGNUM> r(BN_new());
1579   ASSERT_TRUE(r);
1580   ASSERT_TRUE(BN_generate_prime_ex(r.get(), static_cast<int>(kBits), 0, NULL,
1581                                   NULL, NULL));
1582   EXPECT_EQ(kBits, BN_num_bits(r.get()));
1583 }
1584
1585 TEST_F(BNTest, CmpWord) {
1586   static const BN_ULONG kMaxWord = (BN_ULONG)-1;
1587
1588   bssl::UniquePtr<BIGNUM> r(BN_new());
1589   ASSERT_TRUE(r);
1590   ASSERT_TRUE(BN_set_word(r.get(), 0));
1591
1592   EXPECT_EQ(BN_cmp_word(r.get(), 0), 0);
1593   EXPECT_LT(BN_cmp_word(r.get(), 1), 0);
1594   EXPECT_LT(BN_cmp_word(r.get(), kMaxWord), 0);
1595
1596   ASSERT_TRUE(BN_set_word(r.get(), 100));
1597
1598   EXPECT_GT(BN_cmp_word(r.get(), 0), 0);
1599   EXPECT_GT(BN_cmp_word(r.get(), 99), 0);
1600   EXPECT_EQ(BN_cmp_word(r.get(), 100), 0);
1601   EXPECT_LT(BN_cmp_word(r.get(), 101), 0);
1602   EXPECT_LT(BN_cmp_word(r.get(), kMaxWord), 0);
1603
1604   BN_set_negative(r.get(), 1);
1605
1606   EXPECT_LT(BN_cmp_word(r.get(), 0), 0);
1607   EXPECT_LT(BN_cmp_word(r.get(), 100), 0);
1608   EXPECT_LT(BN_cmp_word(r.get(), kMaxWord), 0);
1609
1610   ASSERT_TRUE(BN_set_word(r.get(), kMaxWord));
1611
1612   EXPECT_GT(BN_cmp_word(r.get(), 0), 0);
1613   EXPECT_GT(BN_cmp_word(r.get(), kMaxWord - 1), 0);
1614   EXPECT_EQ(BN_cmp_word(r.get(), kMaxWord), 0);
1615
1616   ASSERT_TRUE(BN_add(r.get(), r.get(), BN_value_one()));
1617
1618   EXPECT_GT(BN_cmp_word(r.get(), 0), 0);
1619   EXPECT_GT(BN_cmp_word(r.get(), kMaxWord), 0);
1620
1621   BN_set_negative(r.get(), 1);
1622
1623   EXPECT_LT(BN_cmp_word(r.get(), 0), 0);
1624   EXPECT_LT(BN_cmp_word(r.get(), kMaxWord), 0);
1625 }
1626
1627 TEST_F(BNTest, BN2Dec) {
1628   static const char *kBN2DecTests[] = {
1629       "0",
1630       "1",
1631       "-1",
1632       "100",
1633       "-100",
1634       "123456789012345678901234567890",
1635       "-123456789012345678901234567890",
1636       "123456789012345678901234567890123456789012345678901234567890",
1637       "-123456789012345678901234567890123456789012345678901234567890",
1638   };
1639
1640   for (const char *test : kBN2DecTests) {
1641     SCOPED_TRACE(test);
1642     bssl::UniquePtr<BIGNUM> bn;
1643     int ret = DecimalToBIGNUM(&bn, test);
1644     ASSERT_NE(0, ret);
1645
1646     bssl::UniquePtr<char> dec(BN_bn2dec(bn.get()));
1647     ASSERT_TRUE(dec);
1648     EXPECT_STREQ(test, dec.get());
1649   }
1650 }
1651
1652 TEST_F(BNTest, SetGetU64) {
1653   static const struct {
1654     const char *hex;
1655     uint64_t value;
1656   } kU64Tests[] = {
1657       {"0", UINT64_C(0x0)},
1658       {"1", UINT64_C(0x1)},
1659       {"ffffffff", UINT64_C(0xffffffff)},
1660       {"100000000", UINT64_C(0x100000000)},
1661       {"ffffffffffffffff", UINT64_C(0xffffffffffffffff)},
1662   };
1663
1664   for (const auto& test : kU64Tests) {
1665     SCOPED_TRACE(test.hex);
1666     bssl::UniquePtr<BIGNUM> bn(BN_new()), expected;
1667     ASSERT_TRUE(bn);
1668     ASSERT_TRUE(BN_set_u64(bn.get(), test.value));
1669     ASSERT_TRUE(HexToBIGNUM(&expected, test.hex));
1670     EXPECT_BIGNUMS_EQUAL("BN_set_u64", expected.get(), bn.get());
1671
1672     uint64_t tmp;
1673     ASSERT_TRUE(BN_get_u64(bn.get(), &tmp));
1674     EXPECT_EQ(test.value, tmp);
1675
1676     // BN_get_u64 ignores the sign bit.
1677     BN_set_negative(bn.get(), 1);
1678     ASSERT_TRUE(BN_get_u64(bn.get(), &tmp));
1679     EXPECT_EQ(test.value, tmp);
1680   }
1681
1682   // Test that BN_get_u64 fails on large numbers.
1683   bssl::UniquePtr<BIGNUM> bn(BN_new());
1684   ASSERT_TRUE(bn);
1685   ASSERT_TRUE(BN_lshift(bn.get(), BN_value_one(), 64));
1686
1687   uint64_t tmp;
1688   EXPECT_FALSE(BN_get_u64(bn.get(), &tmp));
1689
1690   BN_set_negative(bn.get(), 1);
1691   EXPECT_FALSE(BN_get_u64(bn.get(), &tmp));
1692 }
1693
1694 TEST_F(BNTest, Pow2) {
1695   bssl::UniquePtr<BIGNUM> power_of_two(BN_new()), random(BN_new()),
1696       expected(BN_new()), actual(BN_new());
1697   ASSERT_TRUE(power_of_two);
1698   ASSERT_TRUE(random);
1699   ASSERT_TRUE(expected);
1700   ASSERT_TRUE(actual);
1701
1702   // Choose an exponent.
1703   for (size_t e = 3; e < 512; e += 11) {
1704     SCOPED_TRACE(e);
1705     // Choose a bit length for our randoms.
1706     for (int len = 3; len < 512; len += 23) {
1707       SCOPED_TRACE(len);
1708       // Set power_of_two = 2^e.
1709       ASSERT_TRUE(BN_lshift(power_of_two.get(), BN_value_one(), (int)e));
1710
1711       // Test BN_is_pow2 on power_of_two.
1712       EXPECT_TRUE(BN_is_pow2(power_of_two.get()));
1713
1714       // Pick a large random value, ensuring it isn't a power of two.
1715       ASSERT_TRUE(
1716           BN_rand(random.get(), len, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ANY));
1717
1718       // Test BN_is_pow2 on |r|.
1719       EXPECT_FALSE(BN_is_pow2(random.get()));
1720
1721       // Test BN_mod_pow2 on |r|.
1722       ASSERT_TRUE(
1723           BN_mod(expected.get(), random.get(), power_of_two.get(), ctx()));
1724       ASSERT_TRUE(BN_mod_pow2(actual.get(), random.get(), e));
1725       EXPECT_BIGNUMS_EQUAL("random (mod power_of_two)", expected.get(),
1726                            actual.get());
1727
1728       // Test BN_nnmod_pow2 on |r|.
1729       ASSERT_TRUE(
1730           BN_nnmod(expected.get(), random.get(), power_of_two.get(), ctx()));
1731       ASSERT_TRUE(BN_nnmod_pow2(actual.get(), random.get(), e));
1732       EXPECT_BIGNUMS_EQUAL("random (mod power_of_two), non-negative",
1733                            expected.get(), actual.get());
1734
1735       // Test BN_nnmod_pow2 on -|r|.
1736       BN_set_negative(random.get(), 1);
1737       ASSERT_TRUE(
1738           BN_nnmod(expected.get(), random.get(), power_of_two.get(), ctx()));
1739       ASSERT_TRUE(BN_nnmod_pow2(actual.get(), random.get(), e));
1740       EXPECT_BIGNUMS_EQUAL("-random (mod power_of_two), non-negative",
1741                            expected.get(), actual.get());
1742     }
1743   }
1744 }
1745
1746 static const int kPrimes[] = {
1747     2,     3,     5,     7,     11,    13,    17,    19,    23,    29,    31,
1748     37,    41,    43,    47,    53,    59,    61,    67,    71,    73,    79,
1749     83,    89,    97,    101,   103,   107,   109,   113,   127,   131,   137,
1750     139,   149,   151,   157,   163,   167,   173,   179,   181,   191,   193,
1751     197,   199,   211,   223,   227,   229,   233,   239,   241,   251,   257,
1752     263,   269,   271,   277,   281,   283,   293,   307,   311,   313,   317,
1753     331,   337,   347,   349,   353,   359,   367,   373,   379,   383,   389,
1754     397,   401,   409,   419,   421,   431,   433,   439,   443,   449,   457,
1755     461,   463,   467,   479,   487,   491,   499,   503,   509,   521,   523,
1756     541,   547,   557,   563,   569,   571,   577,   587,   593,   599,   601,
1757     607,   613,   617,   619,   631,   641,   643,   647,   653,   659,   661,
1758     673,   677,   683,   691,   701,   709,   719,   727,   733,   739,   743,
1759     751,   757,   761,   769,   773,   787,   797,   809,   811,   821,   823,
1760     827,   829,   839,   853,   857,   859,   863,   877,   881,   883,   887,
1761     907,   911,   919,   929,   937,   941,   947,   953,   967,   971,   977,
1762     983,   991,   997,   1009,  1013,  1019,  1021,  1031,  1033,  1039,  1049,
1763     1051,  1061,  1063,  1069,  1087,  1091,  1093,  1097,  1103,  1109,  1117,
1764     1123,  1129,  1151,  1153,  1163,  1171,  1181,  1187,  1193,  1201,  1213,
1765     1217,  1223,  1229,  1231,  1237,  1249,  1259,  1277,  1279,  1283,  1289,
1766     1291,  1297,  1301,  1303,  1307,  1319,  1321,  1327,  1361,  1367,  1373,
1767     1381,  1399,  1409,  1423,  1427,  1429,  1433,  1439,  1447,  1451,  1453,
1768     1459,  1471,  1481,  1483,  1487,  1489,  1493,  1499,  1511,  1523,  1531,
1769     1543,  1549,  1553,  1559,  1567,  1571,  1579,  1583,  1597,  1601,  1607,
1770     1609,  1613,  1619,  1621,  1627,  1637,  1657,  1663,  1667,  1669,  1693,
1771     1697,  1699,  1709,  1721,  1723,  1733,  1741,  1747,  1753,  1759,  1777,
1772     1783,  1787,  1789,  1801,  1811,  1823,  1831,  1847,  1861,  1867,  1871,
1773     1873,  1877,  1879,  1889,  1901,  1907,  1913,  1931,  1933,  1949,  1951,
1774     1973,  1979,  1987,  1993,  1997,  1999,  2003,  2011,  2017,  2027,  2029,
1775     2039,  2053,  2063,  2069,  2081,  2083,  2087,  2089,  2099,  2111,  2113,
1776     2129,  2131,  2137,  2141,  2143,  2153,  2161,  2179,  2203,  2207,  2213,
1777     2221,  2237,  2239,  2243,  2251,  2267,  2269,  2273,  2281,  2287,  2293,
1778     2297,  2309,  2311,  2333,  2339,  2341,  2347,  2351,  2357,  2371,  2377,
1779     2381,  2383,  2389,  2393,  2399,  2411,  2417,  2423,  2437,  2441,  2447,
1780     2459,  2467,  2473,  2477,  2503,  2521,  2531,  2539,  2543,  2549,  2551,
1781     2557,  2579,  2591,  2593,  2609,  2617,  2621,  2633,  2647,  2657,  2659,
1782     2663,  2671,  2677,  2683,  2687,  2689,  2693,  2699,  2707,  2711,  2713,
1783     2719,  2729,  2731,  2741,  2749,  2753,  2767,  2777,  2789,  2791,  2797,
1784     2801,  2803,  2819,  2833,  2837,  2843,  2851,  2857,  2861,  2879,  2887,
1785     2897,  2903,  2909,  2917,  2927,  2939,  2953,  2957,  2963,  2969,  2971,
1786     2999,  3001,  3011,  3019,  3023,  3037,  3041,  3049,  3061,  3067,  3079,
1787     3083,  3089,  3109,  3119,  3121,  3137,  3163,  3167,  3169,  3181,  3187,
1788     3191,  3203,  3209,  3217,  3221,  3229,  3251,  3253,  3257,  3259,  3271,
1789     3299,  3301,  3307,  3313,  3319,  3323,  3329,  3331,  3343,  3347,  3359,
1790     3361,  3371,  3373,  3389,  3391,  3407,  3413,  3433,  3449,  3457,  3461,
1791     3463,  3467,  3469,  3491,  3499,  3511,  3517,  3527,  3529,  3533,  3539,
1792     3541,  3547,  3557,  3559,  3571,  3581,  3583,  3593,  3607,  3613,  3617,
1793     3623,  3631,  3637,  3643,  3659,  3671,  3673,  3677,  3691,  3697,  3701,
1794     3709,  3719,  3727,  3733,  3739,  3761,  3767,  3769,  3779,  3793,  3797,
1795     3803,  3821,  3823,  3833,  3847,  3851,  3853,  3863,  3877,  3881,  3889,
1796     3907,  3911,  3917,  3919,  3923,  3929,  3931,  3943,  3947,  3967,  3989,
1797     4001,  4003,  4007,  4013,  4019,  4021,  4027,  4049,  4051,  4057,  4073,
1798     4079,  4091,  4093,  4099,  4111,  4127,  4129,  4133,  4139,  4153,  4157,
1799     4159,  4177,  4201,  4211,  4217,  4219,  4229,  4231,  4241,  4243,  4253,
1800     4259,  4261,  4271,  4273,  4283,  4289,  4297,  4327,  4337,  4339,  4349,
1801     4357,  4363,  4373,  4391,  4397,  4409,  4421,  4423,  4441,  4447,  4451,
1802     4457,  4463,  4481,  4483,  4493,  4507,  4513,  4517,  4519,  4523,  4547,
1803     4549,  4561,  4567,  4583,  4591,  4597,  4603,  4621,  4637,  4639,  4643,
1804     4649,  4651,  4657,  4663,  4673,  4679,  4691,  4703,  4721,  4723,  4729,
1805     4733,  4751,  4759,  4783,  4787,  4789,  4793,  4799,  4801,  4813,  4817,
1806     4831,  4861,  4871,  4877,  4889,  4903,  4909,  4919,  4931,  4933,  4937,
1807     4943,  4951,  4957,  4967,  4969,  4973,  4987,  4993,  4999,  5003,  5009,
1808     5011,  5021,  5023,  5039,  5051,  5059,  5077,  5081,  5087,  5099,  5101,
1809     5107,  5113,  5119,  5147,  5153,  5167,  5171,  5179,  5189,  5197,  5209,
1810     5227,  5231,  5233,  5237,  5261,  5273,  5279,  5281,  5297,  5303,  5309,
1811     5323,  5333,  5347,  5351,  5381,  5387,  5393,  5399,  5407,  5413,  5417,
1812     5419,  5431,  5437,  5441,  5443,  5449,  5471,  5477,  5479,  5483,  5501,
1813     5503,  5507,  5519,  5521,  5527,  5531,  5557,  5563,  5569,  5573,  5581,
1814     5591,  5623,  5639,  5641,  5647,  5651,  5653,  5657,  5659,  5669,  5683,
1815     5689,  5693,  5701,  5711,  5717,  5737,  5741,  5743,  5749,  5779,  5783,
1816     5791,  5801,  5807,  5813,  5821,  5827,  5839,  5843,  5849,  5851,  5857,
1817     5861,  5867,  5869,  5879,  5881,  5897,  5903,  5923,  5927,  5939,  5953,
1818     5981,  5987,  6007,  6011,  6029,  6037,  6043,  6047,  6053,  6067,  6073,
1819     6079,  6089,  6091,  6101,  6113,  6121,  6131,  6133,  6143,  6151,  6163,
1820     6173,  6197,  6199,  6203,  6211,  6217,  6221,  6229,  6247,  6257,  6263,
1821     6269,  6271,  6277,  6287,  6299,  6301,  6311,  6317,  6323,  6329,  6337,
1822     6343,  6353,  6359,  6361,  6367,  6373,  6379,  6389,  6397,  6421,  6427,
1823     6449,  6451,  6469,  6473,  6481,  6491,  6521,  6529,  6547,  6551,  6553,
1824     6563,  6569,  6571,  6577,  6581,  6599,  6607,  6619,  6637,  6653,  6659,
1825     6661,  6673,  6679,  6689,  6691,  6701,  6703,  6709,  6719,  6733,  6737,
1826     6761,  6763,  6779,  6781,  6791,  6793,  6803,  6823,  6827,  6829,  6833,
1827     6841,  6857,  6863,  6869,  6871,  6883,  6899,  6907,  6911,  6917,  6947,
1828     6949,  6959,  6961,  6967,  6971,  6977,  6983,  6991,  6997,  7001,  7013,
1829     7019,  7027,  7039,  7043,  7057,  7069,  7079,  7103,  7109,  7121,  7127,
1830     7129,  7151,  7159,  7177,  7187,  7193,  7207,  7211,  7213,  7219,  7229,
1831     7237,  7243,  7247,  7253,  7283,  7297,  7307,  7309,  7321,  7331,  7333,
1832     7349,  7351,  7369,  7393,  7411,  7417,  7433,  7451,  7457,  7459,  7477,
1833     7481,  7487,  7489,  7499,  7507,  7517,  7523,  7529,  7537,  7541,  7547,
1834     7549,  7559,  7561,  7573,  7577,  7583,  7589,  7591,  7603,  7607,  7621,
1835     7639,  7643,  7649,  7669,  7673,  7681,  7687,  7691,  7699,  7703,  7717,
1836     7723,  7727,  7741,  7753,  7757,  7759,  7789,  7793,  7817,  7823,  7829,
1837     7841,  7853,  7867,  7873,  7877,  7879,  7883,  7901,  7907,  7919,  7927,
1838     7933,  7937,  7949,  7951,  7963,  7993,  8009,  8011,  8017,  8039,  8053,
1839     8059,  8069,  8081,  8087,  8089,  8093,  8101,  8111,  8117,  8123,  8147,
1840     8161,  8167,  8171,  8179,  8191,  8209,  8219,  8221,  8231,  8233,  8237,
1841     8243,  8263,  8269,  8273,  8287,  8291,  8293,  8297,  8311,  8317,  8329,
1842     8353,  8363,  8369,  8377,  8387,  8389,  8419,  8423,  8429,  8431,  8443,
1843     8447,  8461,  8467,  8501,  8513,  8521,  8527,  8537,  8539,  8543,  8563,
1844     8573,  8581,  8597,  8599,  8609,  8623,  8627,  8629,  8641,  8647,  8663,
1845     8669,  8677,  8681,  8689,  8693,  8699,  8707,  8713,  8719,  8731,  8737,
1846     8741,  8747,  8753,  8761,  8779,  8783,  8803,  8807,  8819,  8821,  8831,
1847     8837,  8839,  8849,  8861,  8863,  8867,  8887,  8893,  8923,  8929,  8933,
1848     8941,  8951,  8963,  8969,  8971,  8999,  9001,  9007,  9011,  9013,  9029,
1849     9041,  9043,  9049,  9059,  9067,  9091,  9103,  9109,  9127,  9133,  9137,
1850     9151,  9157,  9161,  9173,  9181,  9187,  9199,  9203,  9209,  9221,  9227,
1851     9239,  9241,  9257,  9277,  9281,  9283,  9293,  9311,  9319,  9323,  9337,
1852     9341,  9343,  9349,  9371,  9377,  9391,  9397,  9403,  9413,  9419,  9421,
1853     9431,  9433,  9437,  9439,  9461,  9463,  9467,  9473,  9479,  9491,  9497,
1854     9511,  9521,  9533,  9539,  9547,  9551,  9587,  9601,  9613,  9619,  9623,
1855     9629,  9631,  9643,  9649,  9661,  9677,  9679,  9689,  9697,  9719,  9721,
1856     9733,  9739,  9743,  9749,  9767,  9769,  9781,  9787,  9791,  9803,  9811,
1857     9817,  9829,  9833,  9839,  9851,  9857,  9859,  9871,  9883,  9887,  9901,
1858     9907,  9923,  9929,  9931,  9941,  9949,  9967,  9973,  10007, 10009, 10037,
1859     10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, 10103, 10111, 10133,
1860     10139, 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193, 10211, 10223,
1861     10243, 10247, 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313,
1862     10321, 10331, 10333, 10337, 10343, 10357, 10369, 10391, 10399, 10427, 10429,
1863     10433, 10453, 10457, 10459, 10463, 10477, 10487, 10499, 10501, 10513, 10529,
1864     10531, 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639,
1865     10651, 10657, 10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733,
1866     10739, 10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859,
1867     10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949, 10957,
1868     10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059, 11069, 11071,
1869     11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161, 11171,
1870     11173, 11177, 11197, 11213, 11239, 11243, 11251, 11257, 11261, 11273, 11279,
1871     11287, 11299, 11311, 11317, 11321, 11329, 11351, 11353, 11369, 11383, 11393,
1872     11399, 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483, 11489, 11491,
1873     11497, 11503, 11519, 11527, 11549, 11551, 11579, 11587, 11593, 11597, 11617,
1874     11621, 11633, 11657, 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731,
1875     11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831,
1876     11833, 11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933,
1877     11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011, 12037,
1878     12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109, 12113, 12119,
1879     12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211, 12227, 12239, 12241,
1880     12251, 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323, 12329, 12343,
1881     12347, 12373, 12377, 12379, 12391, 12401, 12409, 12413, 12421, 12433, 12437,
1882     12451, 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527,
1883     12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601, 12611, 12613,
1884     12619, 12637, 12641, 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713,
1885     12721, 12739, 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823,
1886     12829, 12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923,
1887     12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007, 13009,
1888     13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109, 13121, 13127,
1889     13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187, 13217, 13219, 13229,
1890     13241, 13249, 13259, 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337,
1891     13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421, 13441, 13451, 13457,
1892     13463, 13469, 13477, 13487, 13499, 13513, 13523, 13537, 13553, 13567, 13577,
1893     13591, 13597, 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681, 13687,
1894     13691, 13693, 13697, 13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759,
1895     13763, 13781, 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877,
1896     13879, 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967,
1897     13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081, 14083,
1898     14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221,
1899     14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323, 14327, 14341, 14347,
1900     14369, 14387, 14389, 14401, 14407, 14411, 14419, 14423, 14431, 14437, 14447,
1901     14449, 14461, 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549, 14551,
1902     14557, 14561, 14563, 14591, 14593, 14621, 14627, 14629, 14633, 14639, 14653,
1903     14657, 14669, 14683, 14699, 14713, 14717, 14723, 14731, 14737, 14741, 14747,
1904     14753, 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831,
1905     14843, 14851, 14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939,
1906     14947, 14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073,
1907     15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149, 15161,
1908     15173, 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259, 15263, 15269,
1909     15271, 15277, 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331, 15349,
1910     15359, 15361, 15373, 15377, 15383, 15391, 15401, 15413, 15427, 15439, 15443,
1911     15451, 15461, 15467, 15473, 15493, 15497, 15511, 15527, 15541, 15551, 15559,
1912     15569, 15581, 15583, 15601, 15607, 15619, 15629, 15641, 15643, 15647, 15649,
1913     15661, 15667, 15671, 15679, 15683, 15727, 15731, 15733, 15737, 15739, 15749,
1914     15761, 15767, 15773, 15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859,
1915     15877, 15881, 15887, 15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959,
1916     15971, 15973, 15991, 16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069,
1917     16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183, 16187,
1918     16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267, 16273, 16301,
1919     16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381, 16411, 16417, 16421,
1920     16427, 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493, 16519, 16529,
1921     16547, 16553, 16561, 16567, 16573, 16603, 16607, 16619, 16631, 16633, 16649,
1922     16651, 16657, 16661, 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747,
1923     16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843, 16871, 16879, 16883,
1924     16889, 16901, 16903, 16921, 16927, 16931, 16937, 16943, 16963, 16979, 16981,
1925     16987, 16993, 17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077,
1926     17093, 17099, 17107, 17117, 17123, 17137, 17159, 17167, 17183, 17189, 17191,
1927     17203, 17207, 17209, 17231, 17239, 17257, 17291, 17293, 17299, 17317, 17321,
1928     17327, 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389, 17393, 17401,
1929     17417, 17419, 17431, 17443, 17449, 17467, 17471, 17477, 17483, 17489, 17491,
1930     17497, 17509, 17519, 17539, 17551, 17569, 17573, 17579, 17581, 17597, 17599,
1931     17609, 17623, 17627, 17657, 17659, 17669, 17681, 17683, 17707, 17713, 17729,
1932     17737, 17747, 17749, 17761, 17783, 17789, 17791, 17807, 17827, 17837, 17839,
1933     17851, 17863, 17881, 17891, 17903, 17909, 17911, 17921, 17923, 17929, 17939,
1934     17957, 17959, 17971, 17977, 17981, 17987, 17989, 18013, 18041, 18043, 18047,
1935     18049, 18059, 18061, 18077, 18089, 18097, 18119, 18121, 18127, 18131, 18133,
1936     18143, 18149, 18169, 18181, 18191, 18199, 18211, 18217, 18223, 18229, 18233,
1937     18251, 18253, 18257, 18269, 18287, 18289, 18301, 18307, 18311, 18313, 18329,
1938     18341, 18353, 18367, 18371, 18379, 18397, 18401, 18413, 18427, 18433, 18439,
1939     18443, 18451, 18457, 18461, 18481, 18493, 18503, 18517, 18521, 18523, 18539,
1940     18541, 18553, 18583, 18587, 18593, 18617, 18637, 18661, 18671, 18679, 18691,
1941     18701, 18713, 18719, 18731, 18743, 18749, 18757, 18773, 18787, 18793, 18797,
1942     18803, 18839, 18859, 18869, 18899, 18911, 18913, 18917, 18919, 18947, 18959,
1943     18973, 18979, 19001, 19009, 19013, 19031, 19037, 19051, 19069, 19073, 19079,
1944     19081, 19087, 19121, 19139, 19141, 19157, 19163, 19181, 19183, 19207, 19211,
1945     19213, 19219, 19231, 19237, 19249, 19259, 19267, 19273, 19289, 19301, 19309,
1946     19319, 19333, 19373, 19379, 19381, 19387, 19391, 19403, 19417, 19421, 19423,
1947     19427, 19429, 19433, 19441, 19447, 19457, 19463, 19469, 19471, 19477, 19483,
1948     19489, 19501, 19507, 19531, 19541, 19543, 19553, 19559, 19571, 19577, 19583,
1949     19597, 19603, 19609, 19661, 19681, 19687, 19697, 19699, 19709, 19717, 19727,
1950     19739, 19751, 19753, 19759, 19763, 19777, 19793, 19801, 19813, 19819, 19841,
1951     19843, 19853, 19861, 19867, 19889, 19891, 19913, 19919, 19927, 19937, 19949,
1952     19961, 19963, 19973, 19979, 19991, 19993, 19997,
1953 };
1954
1955 TEST_F(BNTest, PrimeChecking) {
1956   bssl::UniquePtr<BIGNUM> p(BN_new());
1957   ASSERT_TRUE(p);
1958   int is_probably_prime_1 = 0, is_probably_prime_2 = 0;
1959   enum bn_primality_result_t result_3;
1960
1961   const int max_prime = kPrimes[OPENSSL_ARRAY_SIZE(kPrimes)-1];
1962   size_t next_prime_index = 0;
1963
1964   for (int i = 0; i <= max_prime; i++) {
1965     SCOPED_TRACE(i);
1966     bool is_prime = false;
1967
1968     if (i == kPrimes[next_prime_index]) {
1969       is_prime = true;
1970       next_prime_index++;
1971     }
1972
1973     ASSERT_TRUE(BN_set_word(p.get(), i));
1974     ASSERT_TRUE(BN_primality_test(
1975         &is_probably_prime_1, p.get(), BN_prime_checks, ctx(),
1976         false /* do_trial_division */, nullptr /* callback */));
1977     EXPECT_EQ(is_prime ? 1 : 0, is_probably_prime_1);
1978     ASSERT_TRUE(BN_primality_test(
1979         &is_probably_prime_2, p.get(), BN_prime_checks, ctx(),
1980         true /* do_trial_division */, nullptr /* callback */));
1981     EXPECT_EQ(is_prime ? 1 : 0, is_probably_prime_2);
1982     if (i > 3 && i % 2 == 1) {
1983       ASSERT_TRUE(BN_enhanced_miller_rabin_primality_test(
1984           &result_3, p.get(), BN_prime_checks, ctx(), nullptr /* callback */));
1985       EXPECT_EQ(is_prime, result_3 == bn_probably_prime);
1986     }
1987   }
1988
1989   // Negative numbers are not prime.
1990   ASSERT_TRUE(BN_set_word(p.get(), 7));
1991   BN_set_negative(p.get(), 1);
1992   ASSERT_TRUE(BN_primality_test(&is_probably_prime_1, p.get(), BN_prime_checks,
1993                                 ctx(), false /* do_trial_division */,
1994                                 nullptr /* callback */));
1995   EXPECT_EQ(0, is_probably_prime_1);
1996   ASSERT_TRUE(BN_primality_test(&is_probably_prime_2, p.get(), BN_prime_checks,
1997                                 ctx(), true /* do_trial_division */,
1998                                 nullptr /* callback */));
1999   EXPECT_EQ(0, is_probably_prime_2);
2000
2001   // The following composite numbers come from http://oeis.org/A014233 and are
2002   // such that the first several primes are not a Rabin-Miller composite
2003   // witness.
2004   static const char *kA014233[] = {
2005       "2047",
2006       "1373653",
2007       "25326001",
2008       "3215031751",
2009       "2152302898747",
2010       "3474749660383",
2011       "341550071728321",
2012       "3825123056546413051",
2013       "318665857834031151167461",
2014       "3317044064679887385961981",
2015   };
2016   for (const char *str : kA014233) {
2017     SCOPED_TRACE(str);
2018     EXPECT_NE(0, DecimalToBIGNUM(&p, str));
2019
2020     ASSERT_TRUE(BN_primality_test(
2021         &is_probably_prime_1, p.get(), BN_prime_checks, ctx(),
2022         false /* do_trial_division */, nullptr /* callback */));
2023     EXPECT_EQ(0, is_probably_prime_1);
2024
2025     ASSERT_TRUE(BN_primality_test(
2026         &is_probably_prime_2, p.get(), BN_prime_checks, ctx(),
2027         true /* do_trial_division */, nullptr /* callback */));
2028     EXPECT_EQ(0, is_probably_prime_2);
2029
2030     ASSERT_TRUE(BN_enhanced_miller_rabin_primality_test(
2031         &result_3, p.get(), BN_prime_checks, ctx(), nullptr /* callback */));
2032     EXPECT_EQ(bn_composite, result_3);
2033   }
2034 }
2035
2036 TEST_F(BNTest, NumBitsWord) {
2037   constexpr BN_ULONG kOne = 1;
2038
2039   // 2^(N-1) takes N bits.
2040   for (unsigned i = 1; i < BN_BITS2; i++) {
2041     EXPECT_EQ(i, BN_num_bits_word(kOne << (i - 1))) << i;
2042   }
2043
2044   // 2^N - 1 takes N bits.
2045   for (unsigned i = 0; i < BN_BITS2; i++) {
2046     EXPECT_EQ(i, BN_num_bits_word((kOne << i) - 1)) << i;
2047   }
2048
2049   for (unsigned i = 1; i < 100; i++) {
2050     // Generate a random value of a random length.
2051     uint8_t buf[1 + sizeof(BN_ULONG)];
2052     RAND_bytes(buf, sizeof(buf));
2053
2054     BN_ULONG w;
2055     memcpy(&w, &buf[1], sizeof(w));
2056
2057     const unsigned num_bits = buf[0] % (BN_BITS2 + 1);
2058     if (num_bits == BN_BITS2) {
2059       w |= kOne << (BN_BITS2 - 1);
2060     } else if (num_bits == 0) {
2061       w = 0;
2062     } else {
2063       w &= (kOne << num_bits) - 1;
2064       w |= kOne << (num_bits - 1);
2065     }
2066
2067     EXPECT_EQ(num_bits, BN_num_bits_word(w)) << w;
2068   }
2069 }
2070
2071 #if !defined(BORINGSSL_SHARED_LIBRARY)
2072 TEST_F(BNTest, LessThanWords) {
2073   // kTestVectors is an array of 256-bit values in sorted order.
2074   static const BN_ULONG kTestVectors[][256 / BN_BITS2] = {
2075       {TOBN(0x00000000, 0x00000000), TOBN(0x00000000, 0x00000000),
2076        TOBN(0x00000000, 0x00000000), TOBN(0x00000000, 0x00000000)},
2077       {TOBN(0x00000000, 0x00000001), TOBN(0x00000000, 0x00000000),
2078        TOBN(0x00000000, 0x00000000), TOBN(0x00000000, 0x00000000)},
2079       {TOBN(0x00000000, 0x00000002), TOBN(0x00000000, 0x00000000),
2080        TOBN(0x00000000, 0x00000000), TOBN(0x00000000, 0x00000000)},
2081       {TOBN(0x00000000, 0x0000ffff), TOBN(0x00000000, 0x00000000),
2082        TOBN(0x00000000, 0x00000000), TOBN(0x00000000, 0x00000000)},
2083       {TOBN(0x00000000, 0x83339914), TOBN(0x00000000, 0x00000000),
2084        TOBN(0x00000000, 0x00000000), TOBN(0x00000000, 0x00000000)},
2085       {TOBN(0x00000000, 0xfffffffe), TOBN(0x00000000, 0x00000000),
2086        TOBN(0x00000000, 0x00000000), TOBN(0x00000000, 0x00000000)},
2087       {TOBN(0x00000000, 0xffffffff), TOBN(0x00000000, 0x00000000),
2088        TOBN(0x00000000, 0x00000000), TOBN(0x00000000, 0x00000000)},
2089       {TOBN(0xed17ac85, 0x83339914), TOBN(0x00000000, 0x00000000),
2090        TOBN(0x00000000, 0x00000000), TOBN(0x00000000, 0x00000000)},
2091       {TOBN(0xffffffff, 0xffffffff), TOBN(0x00000000, 0x00000000),
2092        TOBN(0x00000000, 0x00000000), TOBN(0x00000000, 0x00000000)},
2093       {TOBN(0x00000000, 0x83339914), TOBN(0x00000000, 0x00000001),
2094        TOBN(0x00000000, 0x00000000), TOBN(0x00000000, 0x00000000)},
2095       {TOBN(0xffffffff, 0xffffffff), TOBN(0xffffffff, 0xffffffff),
2096        TOBN(0x00000000, 0x00000000), TOBN(0x00000000, 0x00000000)},
2097       {TOBN(0xffffffff, 0xffffffff), TOBN(0xffffffff, 0xffffffff),
2098        TOBN(0xffffffff, 0xffffffff), TOBN(0x00000000, 0x00000000)},
2099       {TOBN(0x00000000, 0x00000000), TOBN(0x1d6f60ba, 0x893ba84c),
2100        TOBN(0x597d89b3, 0x754abe9f), TOBN(0xb504f333, 0xf9de6484)},
2101       {TOBN(0x00000000, 0x83339915), TOBN(0x1d6f60ba, 0x893ba84c),
2102        TOBN(0x597d89b3, 0x754abe9f), TOBN(0xb504f333, 0xf9de6484)},
2103       {TOBN(0xed17ac85, 0x00000000), TOBN(0x1d6f60ba, 0x893ba84c),
2104        TOBN(0x597d89b3, 0x754abe9f), TOBN(0xb504f333, 0xf9de6484)},
2105       {TOBN(0xed17ac85, 0x83339915), TOBN(0x1d6f60ba, 0x893ba84c),
2106        TOBN(0x597d89b3, 0x754abe9f), TOBN(0xb504f333, 0xf9de6484)},
2107       {TOBN(0xed17ac85, 0xffffffff), TOBN(0x1d6f60ba, 0x893ba84c),
2108        TOBN(0x597d89b3, 0x754abe9f), TOBN(0xb504f333, 0xf9de6484)},
2109       {TOBN(0xffffffff, 0x83339915), TOBN(0x1d6f60ba, 0x893ba84c),
2110        TOBN(0x597d89b3, 0x754abe9f), TOBN(0xb504f333, 0xf9de6484)},
2111       {TOBN(0xffffffff, 0xffffffff), TOBN(0x1d6f60ba, 0x893ba84c),
2112        TOBN(0x597d89b3, 0x754abe9f), TOBN(0xb504f333, 0xf9de6484)},
2113       {TOBN(0x00000000, 0x00000000), TOBN(0x00000000, 0x00000000),
2114        TOBN(0x00000000, 0x00000000), TOBN(0xffffffff, 0xffffffff)},
2115       {TOBN(0x00000000, 0x00000000), TOBN(0x00000000, 0x00000000),
2116        TOBN(0xffffffff, 0xffffffff), TOBN(0xffffffff, 0xffffffff)},
2117       {TOBN(0x00000000, 0x00000001), TOBN(0x00000000, 0x00000000),
2118        TOBN(0xffffffff, 0xffffffff), TOBN(0xffffffff, 0xffffffff)},
2119       {TOBN(0x00000000, 0x00000000), TOBN(0xffffffff, 0xffffffff),
2120        TOBN(0xffffffff, 0xffffffff), TOBN(0xffffffff, 0xffffffff)},
2121       {TOBN(0xffffffff, 0xffffffff), TOBN(0xffffffff, 0xffffffff),
2122        TOBN(0xffffffff, 0xffffffff), TOBN(0xffffffff, 0xffffffff)},
2123   };
2124
2125   // Determine where the single-word values stop.
2126   size_t one_word;
2127   for (one_word = 0; one_word < OPENSSL_ARRAY_SIZE(kTestVectors); one_word++) {
2128     int is_word = 1;
2129     for (size_t i = 1; i < OPENSSL_ARRAY_SIZE(kTestVectors[one_word]); i++) {
2130       if (kTestVectors[one_word][i] != 0) {
2131         is_word = 0;
2132         break;
2133       }
2134     }
2135     if (!is_word) {
2136       break;
2137     }
2138   }
2139
2140   for (size_t i = 0; i < OPENSSL_ARRAY_SIZE(kTestVectors); i++) {
2141     SCOPED_TRACE(i);
2142     for (size_t j = 0; j < OPENSSL_ARRAY_SIZE(kTestVectors); j++) {
2143       SCOPED_TRACE(j);
2144       EXPECT_EQ(i < j ? 1 : 0,
2145                 bn_less_than_words(kTestVectors[i], kTestVectors[j],
2146                                    OPENSSL_ARRAY_SIZE(kTestVectors[i])));
2147       for (size_t k = 0; k < one_word; k++) {
2148         SCOPED_TRACE(k);
2149         EXPECT_EQ(k <= i && i < j ? 1 : 0,
2150                   bn_in_range_words(kTestVectors[i], kTestVectors[k][0],
2151                                     kTestVectors[j],
2152                                     OPENSSL_ARRAY_SIZE(kTestVectors[i])));
2153       }
2154     }
2155   }
2156
2157   EXPECT_EQ(0, bn_less_than_words(NULL, NULL, 0));
2158   EXPECT_EQ(0, bn_in_range_words(NULL, 0, NULL, 0));
2159 }
2160 #endif  // !BORINGSSL_SHARED_LIBRARY
2161
2162 TEST_F(BNTest, NonMinimal) {
2163   bssl::UniquePtr<BIGNUM> ten(BN_new());
2164   ASSERT_TRUE(ten);
2165   ASSERT_TRUE(BN_set_word(ten.get(), 10));
2166
2167   bssl::UniquePtr<BIGNUM> ten_copy(BN_dup(ten.get()));
2168   ASSERT_TRUE(ten_copy);
2169
2170   bssl::UniquePtr<BIGNUM> eight(BN_new());
2171   ASSERT_TRUE(eight);
2172   ASSERT_TRUE(BN_set_word(eight.get(), 8));
2173
2174   bssl::UniquePtr<BIGNUM> forty_two(BN_new());
2175   ASSERT_TRUE(forty_two);
2176   ASSERT_TRUE(BN_set_word(forty_two.get(), 42));
2177
2178   bssl::UniquePtr<BIGNUM> two_exp_256(BN_new());
2179   ASSERT_TRUE(two_exp_256);
2180   ASSERT_TRUE(BN_lshift(two_exp_256.get(), BN_value_one(), 256));
2181
2182   bssl::UniquePtr<BIGNUM> zero(BN_new());
2183   ASSERT_TRUE(zero);
2184   BN_zero(zero.get());
2185
2186   for (size_t width = 1; width < 10; width++) {
2187     SCOPED_TRACE(width);
2188     // Make |ten| and |zero| wider.
2189     EXPECT_TRUE(bn_resize_words(ten.get(), width));
2190     EXPECT_EQ(static_cast<int>(width), ten->width);
2191     EXPECT_TRUE(bn_resize_words(zero.get(), width));
2192     EXPECT_EQ(static_cast<int>(width), zero->width);
2193
2194     EXPECT_TRUE(BN_abs_is_word(ten.get(), 10));
2195     EXPECT_TRUE(BN_is_word(ten.get(), 10));
2196     EXPECT_EQ(10u, BN_get_word(ten.get()));
2197     uint64_t v;
2198     ASSERT_TRUE(BN_get_u64(ten.get(), &v));
2199     EXPECT_EQ(10u, v);
2200
2201     EXPECT_TRUE(BN_equal_consttime(ten.get(), ten_copy.get()));
2202     EXPECT_TRUE(BN_equal_consttime(ten_copy.get(), ten.get()));
2203     EXPECT_EQ(BN_cmp(ten.get(), ten_copy.get()), 0);
2204     EXPECT_EQ(BN_cmp(ten_copy.get(), ten.get()), 0);
2205
2206     EXPECT_FALSE(BN_equal_consttime(ten.get(), eight.get()));
2207     EXPECT_LT(BN_cmp(eight.get(), ten.get()), 0);
2208     EXPECT_GT(BN_cmp(ten.get(), eight.get()), 0);
2209
2210     EXPECT_FALSE(BN_equal_consttime(ten.get(), forty_two.get()));
2211     EXPECT_GT(BN_cmp(forty_two.get(), ten.get()), 0);
2212     EXPECT_LT(BN_cmp(ten.get(), forty_two.get()), 0);
2213
2214     EXPECT_FALSE(BN_equal_consttime(ten.get(), two_exp_256.get()));
2215     EXPECT_GT(BN_cmp(two_exp_256.get(), ten.get()), 0);
2216     EXPECT_LT(BN_cmp(ten.get(), two_exp_256.get()), 0);
2217
2218     EXPECT_EQ(4u, BN_num_bits(ten.get()));
2219     EXPECT_EQ(1u, BN_num_bytes(ten.get()));
2220     EXPECT_FALSE(BN_is_pow2(ten.get()));
2221
2222     bssl::UniquePtr<char> hex(BN_bn2hex(ten.get()));
2223     EXPECT_STREQ("0a", hex.get());
2224     hex.reset(BN_bn2hex(zero.get()));
2225     EXPECT_STREQ("0", hex.get());
2226
2227     bssl::UniquePtr<BIO> bio(BIO_new(BIO_s_mem()));
2228     ASSERT_TRUE(bio);
2229     ASSERT_TRUE(BN_print(bio.get(), ten.get()));
2230     const uint8_t *ptr;
2231     size_t len;
2232     ASSERT_TRUE(BIO_mem_contents(bio.get(), &ptr, &len));
2233     // TODO(davidben): |BN_print| removes leading zeros within a byte, while
2234     // |BN_bn2hex| rounds up to a byte, except for zero which it prints as
2235     // "0". Fix this discrepancy?
2236     EXPECT_EQ(Bytes("a"), Bytes(ptr, len));
2237
2238     bio.reset(BIO_new(BIO_s_mem()));
2239     ASSERT_TRUE(bio);
2240     ASSERT_TRUE(BN_print(bio.get(), zero.get()));
2241     ASSERT_TRUE(BIO_mem_contents(bio.get(), &ptr, &len));
2242     EXPECT_EQ(Bytes("0"), Bytes(ptr, len));
2243   }
2244
2245   // |ten| may be resized back down to one word.
2246   EXPECT_TRUE(bn_resize_words(ten.get(), 1));
2247   EXPECT_EQ(1, ten->width);
2248
2249   // But not to zero words, which it does not fit.
2250   EXPECT_FALSE(bn_resize_words(ten.get(), 0));
2251
2252   EXPECT_TRUE(BN_is_pow2(eight.get()));
2253   EXPECT_TRUE(bn_resize_words(eight.get(), 4));
2254   EXPECT_EQ(4, eight->width);
2255   EXPECT_TRUE(BN_is_pow2(eight.get()));
2256
2257   // |BN_MONT_CTX| is always stored minimally and uses the same R independent of
2258   // input width.
2259   static const uint8_t kP[] = {
2260       0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
2261       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff,
2262       0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2263   };
2264   bssl::UniquePtr<BIGNUM> p(BN_bin2bn(kP, sizeof(kP), nullptr));
2265   ASSERT_TRUE(p);
2266
2267   bssl::UniquePtr<BN_MONT_CTX> mont(
2268       BN_MONT_CTX_new_for_modulus(p.get(), ctx()));
2269   ASSERT_TRUE(mont);
2270
2271   ASSERT_TRUE(bn_resize_words(p.get(), 32));
2272   bssl::UniquePtr<BN_MONT_CTX> mont2(
2273       BN_MONT_CTX_new_for_modulus(p.get(), ctx()));
2274   ASSERT_TRUE(mont2);
2275
2276   EXPECT_EQ(mont->N.width, mont2->N.width);
2277   EXPECT_EQ(0, BN_cmp(&mont->RR, &mont2->RR));
2278 }
2279
2280 TEST_F(BNTest, CountLowZeroBits) {
2281   bssl::UniquePtr<BIGNUM> bn(BN_new());
2282   ASSERT_TRUE(bn);
2283
2284   for (int i = 0; i < BN_BITS2; i++) {
2285     SCOPED_TRACE(i);
2286     for (int set_high_bits = 0; set_high_bits < 2; set_high_bits++) {
2287       BN_ULONG word = ((BN_ULONG)1) << i;
2288       if (set_high_bits) {
2289         BN_ULONG junk;
2290         RAND_bytes(reinterpret_cast<uint8_t *>(&junk), sizeof(junk));
2291         word |= junk & ~(word - 1);
2292       }
2293       SCOPED_TRACE(word);
2294
2295       ASSERT_TRUE(BN_set_word(bn.get(), word));
2296       EXPECT_EQ(i, BN_count_low_zero_bits(bn.get()));
2297       ASSERT_TRUE(bn_resize_words(bn.get(), 16));
2298       EXPECT_EQ(i, BN_count_low_zero_bits(bn.get()));
2299
2300       ASSERT_TRUE(BN_set_word(bn.get(), word));
2301       ASSERT_TRUE(BN_lshift(bn.get(), bn.get(), BN_BITS2 * 5));
2302       EXPECT_EQ(i + BN_BITS2 * 5, BN_count_low_zero_bits(bn.get()));
2303       ASSERT_TRUE(bn_resize_words(bn.get(), 16));
2304       EXPECT_EQ(i + BN_BITS2 * 5, BN_count_low_zero_bits(bn.get()));
2305
2306       ASSERT_TRUE(BN_set_word(bn.get(), word));
2307       ASSERT_TRUE(BN_set_bit(bn.get(), BN_BITS2 * 5));
2308       EXPECT_EQ(i, BN_count_low_zero_bits(bn.get()));
2309       ASSERT_TRUE(bn_resize_words(bn.get(), 16));
2310       EXPECT_EQ(i, BN_count_low_zero_bits(bn.get()));
2311     }
2312   }
2313
2314   BN_zero(bn.get());
2315   EXPECT_EQ(0, BN_count_low_zero_bits(bn.get()));
2316   ASSERT_TRUE(bn_resize_words(bn.get(), 16));
2317   EXPECT_EQ(0, BN_count_low_zero_bits(bn.get()));
2318 }