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