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