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