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