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