diff options
author | tb <> | 2022-12-01 20:50:10 +0000 |
---|---|---|
committer | tb <> | 2022-12-01 20:50:10 +0000 |
commit | 1ee4f78484654f244b792d02de8a59790eaa8d57 (patch) | |
tree | 9c919d8b5975d41dccaa87e47c91d601f9dd9857 /src/regress/lib/libcrypto/bn/bn_test.c | |
parent | 27a426a371fafd6a5de905f5335425a4f20844fb (diff) | |
download | openbsd-1ee4f78484654f244b792d02de8a59790eaa8d57.tar.gz openbsd-1ee4f78484654f244b792d02de8a59790eaa8d57.tar.bz2 openbsd-1ee4f78484654f244b792d02de8a59790eaa8d57.zip |
Flatten structure of libcrypto/bn tests
The bn tests were distributed into three subdirectories rather randomly.
It's cleaner and easier to maintain if all this is in a single directory.
Use consistent names for the .c files, unify handling of the tests with
the exception of bn_test, which is special.
Discussed with jsing
Diffstat (limited to 'src/regress/lib/libcrypto/bn/bn_test.c')
-rw-r--r-- | src/regress/lib/libcrypto/bn/bn_test.c | 2624 |
1 files changed, 2624 insertions, 0 deletions
diff --git a/src/regress/lib/libcrypto/bn/bn_test.c b/src/regress/lib/libcrypto/bn/bn_test.c new file mode 100644 index 0000000000..c1feddeda1 --- /dev/null +++ b/src/regress/lib/libcrypto/bn/bn_test.c | |||
@@ -0,0 +1,2624 @@ | |||
1 | /* $OpenBSD: bn_test.c,v 1.1 2022/12/01 20:50:10 tb Exp $ */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
7 | * The implementation was written so as to conform with Netscapes SSL. | ||
8 | * | ||
9 | * This library is free for commercial and non-commercial use as long as | ||
10 | * the following conditions are aheared to. The following conditions | ||
11 | * apply to all code found in this distribution, be it the RC4, RSA, | ||
12 | * lhash, DES, etc., code; not just the SSL code. The SSL documentation | ||
13 | * included with this distribution is covered by the same copyright terms | ||
14 | * except that the holder is Tim Hudson (tjh@cryptsoft.com). | ||
15 | * | ||
16 | * Copyright remains Eric Young's, and as such any Copyright notices in | ||
17 | * the code are not to be removed. | ||
18 | * If this package is used in a product, Eric Young should be given attribution | ||
19 | * as the author of the parts of the library used. | ||
20 | * This can be in the form of a textual message at program startup or | ||
21 | * in documentation (online or textual) provided with the package. | ||
22 | * | ||
23 | * Redistribution and use in source and binary forms, with or without | ||
24 | * modification, are permitted provided that the following conditions | ||
25 | * are met: | ||
26 | * 1. Redistributions of source code must retain the copyright | ||
27 | * notice, this list of conditions and the following disclaimer. | ||
28 | * 2. Redistributions in binary form must reproduce the above copyright | ||
29 | * notice, this list of conditions and the following disclaimer in the | ||
30 | * documentation and/or other materials provided with the distribution. | ||
31 | * 3. All advertising materials mentioning features or use of this software | ||
32 | * must display the following acknowledgement: | ||
33 | * "This product includes cryptographic software written by | ||
34 | * Eric Young (eay@cryptsoft.com)" | ||
35 | * The word 'cryptographic' can be left out if the rouines from the library | ||
36 | * being used are not cryptographic related :-). | ||
37 | * 4. If you include any Windows specific code (or a derivative thereof) from | ||
38 | * the apps directory (application code) you must include an acknowledgement: | ||
39 | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" | ||
40 | * | ||
41 | * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND | ||
42 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||
43 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
44 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | ||
45 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | ||
46 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | ||
47 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | ||
48 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | ||
49 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | ||
50 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | ||
51 | * SUCH DAMAGE. | ||
52 | * | ||
53 | * The licence and distribution terms for any publically available version or | ||
54 | * derivative of this code cannot be changed. i.e. this code cannot simply be | ||
55 | * copied and put under another distribution licence | ||
56 | * [including the GNU Public Licence.] | ||
57 | */ | ||
58 | /* ==================================================================== | ||
59 | * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. | ||
60 | * | ||
61 | * Portions of the attached software ("Contribution") are developed by | ||
62 | * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. | ||
63 | * | ||
64 | * The Contribution is licensed pursuant to the Eric Young open source | ||
65 | * license provided above. | ||
66 | * | ||
67 | * The binary polynomial arithmetic software is originally written by | ||
68 | * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems Laboratories. | ||
69 | * | ||
70 | */ | ||
71 | |||
72 | /* Until the key-gen callbacks are modified to use newer prototypes, we allow | ||
73 | * deprecated functions for openssl-internal code */ | ||
74 | #ifdef OPENSSL_NO_DEPRECATED | ||
75 | #undef OPENSSL_NO_DEPRECATED | ||
76 | #endif | ||
77 | |||
78 | #include <stdio.h> | ||
79 | #include <stdlib.h> | ||
80 | #include <string.h> | ||
81 | |||
82 | #include <openssl/bio.h> | ||
83 | #include <openssl/bn.h> | ||
84 | #include <openssl/x509.h> | ||
85 | #include <openssl/err.h> | ||
86 | |||
87 | int BN_mod_exp_ct(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, | ||
88 | const BIGNUM *m, BN_CTX *ctx); | ||
89 | int BN_mod_exp_nonct(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, | ||
90 | const BIGNUM *m, BN_CTX *ctx); | ||
91 | int BN_mod_exp_mont_ct(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, | ||
92 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx); | ||
93 | int BN_mod_exp_mont_nonct(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, | ||
94 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx); | ||
95 | |||
96 | int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom); | ||
97 | |||
98 | const int num0 = 100; /* number of tests */ | ||
99 | const int num1 = 50; /* additional tests for some functions */ | ||
100 | const int num2 = 5; /* number of tests for slow functions */ | ||
101 | |||
102 | int test_add(BIO *bp); | ||
103 | int test_sub(BIO *bp); | ||
104 | int test_lshift1(BIO *bp); | ||
105 | int test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_); | ||
106 | int test_rshift1(BIO *bp); | ||
107 | int test_rshift(BIO *bp, BN_CTX *ctx); | ||
108 | int test_div(BIO *bp, BN_CTX *ctx); | ||
109 | int test_div_word(BIO *bp); | ||
110 | int test_div_recp(BIO *bp, BN_CTX *ctx); | ||
111 | int test_mul(BIO *bp); | ||
112 | int test_sqr(BIO *bp, BN_CTX *ctx); | ||
113 | int test_mont(BIO *bp, BN_CTX *ctx); | ||
114 | int test_mod(BIO *bp, BN_CTX *ctx); | ||
115 | int test_mod_mul(BIO *bp, BN_CTX *ctx); | ||
116 | int test_mod_exp(BIO *bp, BN_CTX *ctx); | ||
117 | int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx); | ||
118 | int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx); | ||
119 | int test_mod_exp_sizes(BIO *bp, BN_CTX *ctx); | ||
120 | int test_exp(BIO *bp, BN_CTX *ctx); | ||
121 | int test_gf2m_add(BIO *bp); | ||
122 | int test_gf2m_mod(BIO *bp); | ||
123 | int test_gf2m_mod_mul(BIO *bp, BN_CTX *ctx); | ||
124 | int test_gf2m_mod_sqr(BIO *bp, BN_CTX *ctx); | ||
125 | int test_gf2m_mod_inv(BIO *bp, BN_CTX *ctx); | ||
126 | int test_gf2m_mod_div(BIO *bp, BN_CTX *ctx); | ||
127 | int test_gf2m_mod_exp(BIO *bp, BN_CTX *ctx); | ||
128 | int test_gf2m_mod_sqrt(BIO *bp, BN_CTX *ctx); | ||
129 | int test_gf2m_mod_solve_quad(BIO *bp, BN_CTX *ctx); | ||
130 | int test_kron(BIO *bp, BN_CTX *ctx); | ||
131 | int test_sqrt(BIO *bp, BN_CTX *ctx); | ||
132 | int rand_neg(void); | ||
133 | static int results = 0; | ||
134 | |||
135 | static unsigned char lst[] = | ||
136 | "\xC6\x4F\x43\x04\x2A\xEA\xCA\x6E\x58\x36\x80\x5B\xE8\xC9" | ||
137 | "\x9B\x04\x5D\x48\x36\xC2\xFD\x16\xC9\x64\xF0"; | ||
138 | |||
139 | #define PRINT_ERROR printf("Error in %s [%s:%d]\n", __func__, __FILE__, \ | ||
140 | __LINE__) | ||
141 | |||
142 | #define CHECK_GOTO(a) do { \ | ||
143 | if (!(a)) { \ | ||
144 | PRINT_ERROR; \ | ||
145 | rc = 0; \ | ||
146 | goto err; \ | ||
147 | } \ | ||
148 | } while (0) | ||
149 | |||
150 | static void | ||
151 | message(BIO *out, char *m) | ||
152 | { | ||
153 | fprintf(stderr, "test %s\n", m); | ||
154 | BIO_puts(out, "print \"test "); | ||
155 | BIO_puts(out, m); | ||
156 | BIO_puts(out, "\\n\"\n"); | ||
157 | } | ||
158 | |||
159 | int | ||
160 | main(int argc, char *argv[]) | ||
161 | { | ||
162 | BN_CTX *ctx; | ||
163 | BIO *out; | ||
164 | char *outfile = NULL; | ||
165 | |||
166 | results = 0; | ||
167 | |||
168 | argc--; | ||
169 | argv++; | ||
170 | while (argc >= 1) { | ||
171 | if (strcmp(*argv, "-results") == 0) | ||
172 | results = 1; | ||
173 | else if (strcmp(*argv, "-out") == 0) { | ||
174 | if (--argc < 1) | ||
175 | break; | ||
176 | outfile= *(++argv); | ||
177 | } | ||
178 | argc--; | ||
179 | argv++; | ||
180 | } | ||
181 | |||
182 | |||
183 | ctx = BN_CTX_new(); | ||
184 | if (ctx == NULL) | ||
185 | exit(1); | ||
186 | |||
187 | out = BIO_new(BIO_s_file()); | ||
188 | if (out == NULL) | ||
189 | exit(1); | ||
190 | if (outfile == NULL) { | ||
191 | BIO_set_fp(out, stdout, BIO_NOCLOSE); | ||
192 | } else { | ||
193 | if (!BIO_write_filename(out, outfile)) { | ||
194 | perror(outfile); | ||
195 | exit(1); | ||
196 | } | ||
197 | } | ||
198 | |||
199 | if (!results) | ||
200 | BIO_puts(out, "obase=16\nibase=16\n"); | ||
201 | |||
202 | message(out, "BN_add"); | ||
203 | if (!test_add(out)) | ||
204 | goto err; | ||
205 | (void)BIO_flush(out); | ||
206 | |||
207 | message(out, "BN_sub"); | ||
208 | if (!test_sub(out)) | ||
209 | goto err; | ||
210 | (void)BIO_flush(out); | ||
211 | |||
212 | message(out, "BN_lshift1"); | ||
213 | if (!test_lshift1(out)) | ||
214 | goto err; | ||
215 | (void)BIO_flush(out); | ||
216 | |||
217 | message(out, "BN_lshift (fixed)"); | ||
218 | if (!test_lshift(out, ctx, BN_bin2bn(lst, sizeof(lst) - 1, NULL))) | ||
219 | goto err; | ||
220 | (void)BIO_flush(out); | ||
221 | |||
222 | message(out, "BN_lshift"); | ||
223 | if (!test_lshift(out, ctx, NULL)) | ||
224 | goto err; | ||
225 | (void)BIO_flush(out); | ||
226 | |||
227 | message(out, "BN_rshift1"); | ||
228 | if (!test_rshift1(out)) | ||
229 | goto err; | ||
230 | (void)BIO_flush(out); | ||
231 | |||
232 | message(out, "BN_rshift"); | ||
233 | if (!test_rshift(out, ctx)) | ||
234 | goto err; | ||
235 | (void)BIO_flush(out); | ||
236 | |||
237 | message(out, "BN_sqr"); | ||
238 | if (!test_sqr(out, ctx)) | ||
239 | goto err; | ||
240 | (void)BIO_flush(out); | ||
241 | |||
242 | message(out, "BN_mul"); | ||
243 | if (!test_mul(out)) | ||
244 | goto err; | ||
245 | (void)BIO_flush(out); | ||
246 | |||
247 | message(out, "BN_div"); | ||
248 | if (!test_div(out, ctx)) | ||
249 | goto err; | ||
250 | (void)BIO_flush(out); | ||
251 | |||
252 | message(out, "BN_div_word"); | ||
253 | if (!test_div_word(out)) | ||
254 | goto err; | ||
255 | (void)BIO_flush(out); | ||
256 | |||
257 | message(out, "BN_div_recp"); | ||
258 | if (!test_div_recp(out, ctx)) | ||
259 | goto err; | ||
260 | (void)BIO_flush(out); | ||
261 | |||
262 | message(out, "BN_mod"); | ||
263 | if (!test_mod(out, ctx)) | ||
264 | goto err; | ||
265 | (void)BIO_flush(out); | ||
266 | |||
267 | message(out, "BN_mod_mul"); | ||
268 | if (!test_mod_mul(out, ctx)) | ||
269 | goto err; | ||
270 | (void)BIO_flush(out); | ||
271 | |||
272 | message(out, "BN_mont"); | ||
273 | if (!test_mont(out, ctx)) | ||
274 | goto err; | ||
275 | (void)BIO_flush(out); | ||
276 | |||
277 | message(out, "BN_mod_exp"); | ||
278 | if (!test_mod_exp(out, ctx)) | ||
279 | goto err; | ||
280 | (void)BIO_flush(out); | ||
281 | |||
282 | message(out, "BN_mod_exp_mont_consttime"); | ||
283 | if (!test_mod_exp_mont_consttime(out, ctx)) | ||
284 | goto err; | ||
285 | (void)BIO_flush(out); | ||
286 | |||
287 | message(out, "BN_mod_exp_mont5"); | ||
288 | if (!test_mod_exp_mont5(out, ctx)) | ||
289 | goto err; | ||
290 | (void)BIO_flush(out); | ||
291 | |||
292 | message(out, "BN_exp"); | ||
293 | if (!test_exp(out, ctx)) | ||
294 | goto err; | ||
295 | (void)BIO_flush(out); | ||
296 | |||
297 | message(out, "BN_kronecker"); | ||
298 | if (!test_kron(out, ctx)) | ||
299 | goto err; | ||
300 | (void)BIO_flush(out); | ||
301 | |||
302 | message(out, "BN_mod_sqrt"); | ||
303 | if (!test_sqrt(out, ctx)) | ||
304 | goto err; | ||
305 | (void)BIO_flush(out); | ||
306 | |||
307 | message(out, "Modexp with different sizes"); | ||
308 | if (!test_mod_exp_sizes(out, ctx)) | ||
309 | goto err; | ||
310 | (void)BIO_flush(out); | ||
311 | |||
312 | #ifndef OPENSSL_NO_EC2M | ||
313 | message(out, "BN_GF2m_add"); | ||
314 | if (!test_gf2m_add(out)) | ||
315 | goto err; | ||
316 | (void)BIO_flush(out); | ||
317 | |||
318 | message(out, "BN_GF2m_mod"); | ||
319 | if (!test_gf2m_mod(out)) | ||
320 | goto err; | ||
321 | (void)BIO_flush(out); | ||
322 | |||
323 | message(out, "BN_GF2m_mod_mul"); | ||
324 | if (!test_gf2m_mod_mul(out, ctx)) | ||
325 | goto err; | ||
326 | (void)BIO_flush(out); | ||
327 | |||
328 | message(out, "BN_GF2m_mod_sqr"); | ||
329 | if (!test_gf2m_mod_sqr(out, ctx)) | ||
330 | goto err; | ||
331 | (void)BIO_flush(out); | ||
332 | |||
333 | message(out, "BN_GF2m_mod_inv"); | ||
334 | if (!test_gf2m_mod_inv(out, ctx)) | ||
335 | goto err; | ||
336 | (void)BIO_flush(out); | ||
337 | |||
338 | message(out, "BN_GF2m_mod_div"); | ||
339 | if (!test_gf2m_mod_div(out, ctx)) | ||
340 | goto err; | ||
341 | (void)BIO_flush(out); | ||
342 | |||
343 | message(out, "BN_GF2m_mod_exp"); | ||
344 | if (!test_gf2m_mod_exp(out, ctx)) | ||
345 | goto err; | ||
346 | (void)BIO_flush(out); | ||
347 | |||
348 | message(out, "BN_GF2m_mod_sqrt"); | ||
349 | if (!test_gf2m_mod_sqrt(out, ctx)) | ||
350 | goto err; | ||
351 | (void)BIO_flush(out); | ||
352 | |||
353 | message(out, "BN_GF2m_mod_solve_quad"); | ||
354 | if (!test_gf2m_mod_solve_quad(out, ctx)) | ||
355 | goto err; | ||
356 | (void)BIO_flush(out); | ||
357 | #endif | ||
358 | BN_CTX_free(ctx); | ||
359 | BIO_free(out); | ||
360 | |||
361 | exit(0); | ||
362 | err: | ||
363 | BIO_puts(out, "1\n"); /* make sure the Perl script fed by bc notices | ||
364 | * the failure, see test_bn in test/Makefile.ssl*/ | ||
365 | |||
366 | (void)BIO_flush(out); | ||
367 | ERR_load_crypto_strings(); | ||
368 | ERR_print_errors_fp(stderr); | ||
369 | exit(1); | ||
370 | } | ||
371 | |||
372 | int | ||
373 | test_add(BIO *bp) | ||
374 | { | ||
375 | BIGNUM *a = NULL, *b = NULL, *c = NULL; | ||
376 | int i; | ||
377 | int rc = 1; | ||
378 | |||
379 | if ((a = BN_new()) == NULL) | ||
380 | goto err; | ||
381 | if ((b = BN_new()) == NULL) | ||
382 | goto err; | ||
383 | if ((c = BN_new()) == NULL) | ||
384 | goto err; | ||
385 | |||
386 | CHECK_GOTO(BN_bntest_rand(a, 512, 0, 0)); | ||
387 | for (i = 0; i < num0; i++) { | ||
388 | CHECK_GOTO(BN_bntest_rand(b, 450 + i, 0, 0)); | ||
389 | BN_set_negative(a, rand_neg()); | ||
390 | BN_set_negative(b, rand_neg()); | ||
391 | CHECK_GOTO(BN_add(c, a, b)); | ||
392 | if (bp != NULL) { | ||
393 | if (!results) { | ||
394 | CHECK_GOTO(BN_print(bp, a)); | ||
395 | BIO_puts(bp, " + "); | ||
396 | CHECK_GOTO(BN_print(bp, b)); | ||
397 | BIO_puts(bp, " - "); | ||
398 | } | ||
399 | CHECK_GOTO(BN_print(bp, c)); | ||
400 | BIO_puts(bp, "\n"); | ||
401 | } | ||
402 | BN_set_negative(a, !BN_is_negative(a)); | ||
403 | BN_set_negative(b, !BN_is_negative(b)); | ||
404 | CHECK_GOTO(BN_add(c, c, b)); | ||
405 | CHECK_GOTO(BN_add(c, c, a)); | ||
406 | if (!BN_is_zero(c)) { | ||
407 | fprintf(stderr, "Add test failed!\n"); | ||
408 | rc = 0; | ||
409 | break; | ||
410 | } | ||
411 | } | ||
412 | |||
413 | err: | ||
414 | BN_free(a); | ||
415 | BN_free(b); | ||
416 | BN_free(c); | ||
417 | |||
418 | return rc; | ||
419 | } | ||
420 | |||
421 | int | ||
422 | test_sub(BIO *bp) | ||
423 | { | ||
424 | BIGNUM *a = NULL, *b = NULL, *c = NULL; | ||
425 | int i; | ||
426 | int rc = 1; | ||
427 | |||
428 | if ((a = BN_new()) == NULL) | ||
429 | goto err; | ||
430 | if ((b = BN_new()) == NULL) | ||
431 | goto err; | ||
432 | if ((c = BN_new()) == NULL) | ||
433 | goto err; | ||
434 | |||
435 | for (i = 0; i < num0 + num1; i++) { | ||
436 | if (i < num1) { | ||
437 | CHECK_GOTO(BN_bntest_rand(a, 512, 0, 0)); | ||
438 | CHECK_GOTO(BN_copy(b, a)); | ||
439 | if (BN_set_bit(a, i) == 0) { | ||
440 | rc = 0; | ||
441 | break; | ||
442 | } | ||
443 | CHECK_GOTO(BN_add_word(b, i)); | ||
444 | } else { | ||
445 | CHECK_GOTO(BN_bntest_rand(b, 400 + i - num1, 0, 0)); | ||
446 | BN_set_negative(a, rand_neg()); | ||
447 | BN_set_negative(b, rand_neg()); | ||
448 | } | ||
449 | CHECK_GOTO(BN_sub(c, a, b)); | ||
450 | if (bp != NULL) { | ||
451 | if (!results) { | ||
452 | CHECK_GOTO(BN_print(bp, a)); | ||
453 | BIO_puts(bp, " - "); | ||
454 | CHECK_GOTO(BN_print(bp, b)); | ||
455 | BIO_puts(bp, " - "); | ||
456 | } | ||
457 | CHECK_GOTO(BN_print(bp, c)); | ||
458 | BIO_puts(bp, "\n"); | ||
459 | } | ||
460 | CHECK_GOTO(BN_add(c, c, b)); | ||
461 | CHECK_GOTO(BN_sub(c, c, a)); | ||
462 | if (!BN_is_zero(c)) { | ||
463 | fprintf(stderr, "Subtract test failed!\n"); | ||
464 | rc = 0; | ||
465 | break; | ||
466 | } | ||
467 | } | ||
468 | err: | ||
469 | BN_free(a); | ||
470 | BN_free(b); | ||
471 | BN_free(c); | ||
472 | return (rc); | ||
473 | } | ||
474 | |||
475 | int | ||
476 | test_div(BIO *bp, BN_CTX *ctx) | ||
477 | { | ||
478 | BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL; | ||
479 | int i; | ||
480 | int rc = 1; | ||
481 | |||
482 | if ((a = BN_new()) == NULL) | ||
483 | goto err; | ||
484 | if ((b = BN_new()) == NULL) | ||
485 | goto err; | ||
486 | if ((c = BN_new()) == NULL) | ||
487 | goto err; | ||
488 | if ((d = BN_new()) == NULL) | ||
489 | goto err; | ||
490 | if ((e = BN_new()) == NULL) | ||
491 | goto err; | ||
492 | |||
493 | CHECK_GOTO(BN_one(a)); | ||
494 | CHECK_GOTO(BN_zero(b)); | ||
495 | |||
496 | if (BN_div(d, c, a, b, ctx)) { | ||
497 | fprintf(stderr, "Division by zero succeeded!\n"); | ||
498 | return (0); | ||
499 | } | ||
500 | |||
501 | for (i = 0; i < num0 + num1; i++) { | ||
502 | if (i < num1) { | ||
503 | CHECK_GOTO(BN_bntest_rand(a, 400, 0, 0)); | ||
504 | CHECK_GOTO(BN_copy(b, a)); | ||
505 | CHECK_GOTO(BN_lshift(a, a, i)); | ||
506 | CHECK_GOTO(BN_add_word(a, i)); | ||
507 | } else | ||
508 | CHECK_GOTO(BN_bntest_rand(b, 50 + 3 * (i - num1), 0, 0)); | ||
509 | BN_set_negative(a, rand_neg()); | ||
510 | BN_set_negative(b, rand_neg()); | ||
511 | CHECK_GOTO(BN_div(d, c, a, b, ctx)); | ||
512 | if (bp != NULL) { | ||
513 | if (!results) { | ||
514 | CHECK_GOTO(BN_print(bp, a)); | ||
515 | BIO_puts(bp, " / "); | ||
516 | CHECK_GOTO(BN_print(bp, b)); | ||
517 | BIO_puts(bp, " - "); | ||
518 | } | ||
519 | CHECK_GOTO(BN_print(bp, d)); | ||
520 | BIO_puts(bp, "\n"); | ||
521 | |||
522 | if (!results) { | ||
523 | CHECK_GOTO(BN_print(bp, a)); | ||
524 | BIO_puts(bp, " % "); | ||
525 | CHECK_GOTO(BN_print(bp, b)); | ||
526 | BIO_puts(bp, " - "); | ||
527 | } | ||
528 | CHECK_GOTO(BN_print(bp, c)); | ||
529 | BIO_puts(bp, "\n"); | ||
530 | } | ||
531 | CHECK_GOTO(BN_mul(e, d, b, ctx)); | ||
532 | CHECK_GOTO(BN_add(d, e, c)); | ||
533 | CHECK_GOTO(BN_sub(d, d, a)); | ||
534 | if (!BN_is_zero(d)) { | ||
535 | fprintf(stderr, "Division test failed!\n"); | ||
536 | rc = 0; | ||
537 | break; | ||
538 | } | ||
539 | } | ||
540 | err: | ||
541 | BN_free(a); | ||
542 | BN_free(b); | ||
543 | BN_free(c); | ||
544 | BN_free(d); | ||
545 | BN_free(e); | ||
546 | return (rc); | ||
547 | } | ||
548 | |||
549 | static void | ||
550 | print_word(BIO *bp, BN_ULONG w) | ||
551 | { | ||
552 | #ifdef SIXTY_FOUR_BIT | ||
553 | if (sizeof(w) > sizeof(unsigned long)) { | ||
554 | unsigned long h = (unsigned long)(w >> 32), l = (unsigned long)(w); | ||
555 | |||
556 | if (h) | ||
557 | BIO_printf(bp, "%lX%08lX", h, l); | ||
558 | else | ||
559 | BIO_printf(bp, "%lX", l); | ||
560 | return; | ||
561 | } | ||
562 | #endif | ||
563 | BIO_printf(bp, BN_HEX_FMT1, w); | ||
564 | } | ||
565 | |||
566 | int | ||
567 | test_div_word(BIO *bp) | ||
568 | { | ||
569 | BIGNUM *a = NULL, *b = NULL; | ||
570 | BN_ULONG r, rmod, s = 0; | ||
571 | int i; | ||
572 | int rc = 1; | ||
573 | |||
574 | if ((a = BN_new()) == NULL) | ||
575 | goto err; | ||
576 | if ((b = BN_new()) == NULL) | ||
577 | goto err; | ||
578 | |||
579 | for (i = 0; i < num0; i++) { | ||
580 | do { | ||
581 | if (!BN_bntest_rand(a, 512, -1, 0) || | ||
582 | !BN_bntest_rand(b, BN_BITS2, -1, 0)) { | ||
583 | rc = 0; | ||
584 | break; | ||
585 | } | ||
586 | s = BN_get_word(b); | ||
587 | } while (!s); | ||
588 | |||
589 | if (!BN_copy(b, a)) { | ||
590 | rc = 0; | ||
591 | break; | ||
592 | } | ||
593 | |||
594 | rmod = BN_mod_word(b, s); | ||
595 | r = BN_div_word(b, s); | ||
596 | |||
597 | if (r == (BN_ULONG)-1 || rmod == (BN_ULONG)-1) { | ||
598 | rc = 0; | ||
599 | break; | ||
600 | } | ||
601 | |||
602 | if (rmod != r) { | ||
603 | fprintf(stderr, "Mod (word) test failed!\n"); | ||
604 | rc = 0; | ||
605 | break; | ||
606 | } | ||
607 | |||
608 | if (bp != NULL) { | ||
609 | if (!results) { | ||
610 | CHECK_GOTO(BN_print(bp, a)); | ||
611 | BIO_puts(bp, " / "); | ||
612 | print_word(bp, s); | ||
613 | BIO_puts(bp, " - "); | ||
614 | } | ||
615 | CHECK_GOTO(BN_print(bp, b)); | ||
616 | BIO_puts(bp, "\n"); | ||
617 | |||
618 | if (!results) { | ||
619 | CHECK_GOTO(BN_print(bp, a)); | ||
620 | BIO_puts(bp, " % "); | ||
621 | print_word(bp, s); | ||
622 | BIO_puts(bp, " - "); | ||
623 | } | ||
624 | print_word(bp, r); | ||
625 | BIO_puts(bp, "\n"); | ||
626 | } | ||
627 | CHECK_GOTO(BN_mul_word(b, s)); | ||
628 | CHECK_GOTO(BN_add_word(b, r)); | ||
629 | CHECK_GOTO(BN_sub(b, a, b)); | ||
630 | if (!BN_is_zero(b)) { | ||
631 | fprintf(stderr, "Division (word) test failed!\n"); | ||
632 | rc = 0; | ||
633 | break; | ||
634 | } | ||
635 | } | ||
636 | err: | ||
637 | BN_free(a); | ||
638 | BN_free(b); | ||
639 | |||
640 | return rc; | ||
641 | } | ||
642 | |||
643 | int | ||
644 | test_div_recp(BIO *bp, BN_CTX *ctx) | ||
645 | { | ||
646 | BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL; | ||
647 | BN_RECP_CTX *recp = NULL; | ||
648 | int i; | ||
649 | int rc = 1; | ||
650 | |||
651 | if ((a = BN_new()) == NULL) | ||
652 | goto err; | ||
653 | if ((b = BN_new()) == NULL) | ||
654 | goto err; | ||
655 | if ((c = BN_new()) == NULL) | ||
656 | goto err; | ||
657 | if ((d = BN_new()) == NULL) | ||
658 | goto err; | ||
659 | if ((e = BN_new()) == NULL) | ||
660 | goto err; | ||
661 | |||
662 | if ((recp = BN_RECP_CTX_new()) == NULL) | ||
663 | goto err; | ||
664 | |||
665 | for (i = 0; i < num0 + num1; i++) { | ||
666 | if (i < num1) { | ||
667 | CHECK_GOTO(BN_bntest_rand(a, 400, 0, 0)); | ||
668 | CHECK_GOTO(BN_copy(b, a)); | ||
669 | CHECK_GOTO(BN_lshift(a, a, i)); | ||
670 | CHECK_GOTO(BN_add_word(a, i)); | ||
671 | } else | ||
672 | CHECK_GOTO(BN_bntest_rand(b, 50 + 3 * (i - num1), 0, 0)); | ||
673 | BN_set_negative(a, rand_neg()); | ||
674 | BN_set_negative(b, rand_neg()); | ||
675 | CHECK_GOTO(BN_RECP_CTX_set(recp, b, ctx)); | ||
676 | CHECK_GOTO(BN_div_recp(d, c, a, recp, ctx)); | ||
677 | if (bp != NULL) { | ||
678 | if (!results) { | ||
679 | CHECK_GOTO(BN_print(bp, a)); | ||
680 | BIO_puts(bp, " / "); | ||
681 | CHECK_GOTO(BN_print(bp, b)); | ||
682 | BIO_puts(bp, " - "); | ||
683 | } | ||
684 | CHECK_GOTO(BN_print(bp, d)); | ||
685 | BIO_puts(bp, "\n"); | ||
686 | |||
687 | if (!results) { | ||
688 | CHECK_GOTO(BN_print(bp, a)); | ||
689 | BIO_puts(bp, " % "); | ||
690 | CHECK_GOTO(BN_print(bp, b)); | ||
691 | BIO_puts(bp, " - "); | ||
692 | } | ||
693 | CHECK_GOTO(BN_print(bp, c)); | ||
694 | BIO_puts(bp, "\n"); | ||
695 | } | ||
696 | CHECK_GOTO(BN_mul(e, d, b, ctx)); | ||
697 | CHECK_GOTO(BN_add(d, e, c)); | ||
698 | CHECK_GOTO(BN_sub(d, d, a)); | ||
699 | if (!BN_is_zero(d)) { | ||
700 | fprintf(stderr, "Reciprocal division test failed!\n"); | ||
701 | fprintf(stderr, "a="); | ||
702 | CHECK_GOTO(BN_print_fp(stderr, a)); | ||
703 | fprintf(stderr, "\nb="); | ||
704 | CHECK_GOTO(BN_print_fp(stderr, b)); | ||
705 | fprintf(stderr, "\n"); | ||
706 | rc = 0; | ||
707 | break; | ||
708 | } | ||
709 | } | ||
710 | err: | ||
711 | BN_free(a); | ||
712 | BN_free(b); | ||
713 | BN_free(c); | ||
714 | BN_free(d); | ||
715 | BN_free(e); | ||
716 | BN_RECP_CTX_free(recp); | ||
717 | return (rc); | ||
718 | } | ||
719 | |||
720 | int | ||
721 | test_mul(BIO *bp) | ||
722 | { | ||
723 | BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL; | ||
724 | int i; | ||
725 | int rc = 1; | ||
726 | BN_CTX *ctx; | ||
727 | |||
728 | ctx = BN_CTX_new(); | ||
729 | if (ctx == NULL) | ||
730 | exit(1); | ||
731 | |||
732 | if ((a = BN_new()) == NULL) | ||
733 | goto err; | ||
734 | if ((b = BN_new()) == NULL) | ||
735 | goto err; | ||
736 | if ((c = BN_new()) == NULL) | ||
737 | goto err; | ||
738 | if ((d = BN_new()) == NULL) | ||
739 | goto err; | ||
740 | if ((e = BN_new()) == NULL) | ||
741 | goto err; | ||
742 | |||
743 | for (i = 0; i < num0 + num1; i++) { | ||
744 | if (i <= num1) { | ||
745 | CHECK_GOTO(BN_bntest_rand(a, 100, 0, 0)); | ||
746 | CHECK_GOTO(BN_bntest_rand(b, 100, 0, 0)); | ||
747 | } else | ||
748 | CHECK_GOTO(BN_bntest_rand(b, i - num1, 0, 0)); | ||
749 | BN_set_negative(a, rand_neg()); | ||
750 | BN_set_negative(b, rand_neg()); | ||
751 | CHECK_GOTO(BN_mul(c, a, b, ctx)); | ||
752 | if (bp != NULL) { | ||
753 | if (!results) { | ||
754 | CHECK_GOTO(BN_print(bp, a)); | ||
755 | BIO_puts(bp, " * "); | ||
756 | CHECK_GOTO(BN_print(bp, b)); | ||
757 | BIO_puts(bp, " - "); | ||
758 | } | ||
759 | CHECK_GOTO(BN_print(bp, c)); | ||
760 | BIO_puts(bp, "\n"); | ||
761 | } | ||
762 | CHECK_GOTO(BN_div(d, e, c, a, ctx)); | ||
763 | CHECK_GOTO(BN_sub(d, d, b)); | ||
764 | if (!BN_is_zero(d) || !BN_is_zero(e)) { | ||
765 | fprintf(stderr, "Multiplication test failed!\n"); | ||
766 | rc = 0; | ||
767 | break; | ||
768 | } | ||
769 | } | ||
770 | err: | ||
771 | BN_free(a); | ||
772 | BN_free(b); | ||
773 | BN_free(c); | ||
774 | BN_free(d); | ||
775 | BN_free(e); | ||
776 | BN_CTX_free(ctx); | ||
777 | return (rc); | ||
778 | } | ||
779 | |||
780 | int | ||
781 | test_sqr(BIO *bp, BN_CTX *ctx) | ||
782 | { | ||
783 | BIGNUM *a = NULL, *c = NULL, *d = NULL, *e = NULL; | ||
784 | int i, rc = 0; | ||
785 | |||
786 | if ((a = BN_new()) == NULL) | ||
787 | goto err; | ||
788 | if ((c = BN_new()) == NULL) | ||
789 | goto err; | ||
790 | if ((d = BN_new()) == NULL) | ||
791 | goto err; | ||
792 | if ((e = BN_new()) == NULL) | ||
793 | goto err; | ||
794 | |||
795 | for (i = 0; i < num0; i++) { | ||
796 | CHECK_GOTO(BN_bntest_rand(a, 40 + i * 10, 0, 0)); | ||
797 | BN_set_negative(a, rand_neg()); | ||
798 | CHECK_GOTO(BN_sqr(c, a, ctx)); | ||
799 | if (bp != NULL) { | ||
800 | if (!results) { | ||
801 | CHECK_GOTO(BN_print(bp, a)); | ||
802 | BIO_puts(bp, " * "); | ||
803 | CHECK_GOTO(BN_print(bp, a)); | ||
804 | BIO_puts(bp, " - "); | ||
805 | } | ||
806 | CHECK_GOTO(BN_print(bp, c)); | ||
807 | BIO_puts(bp, "\n"); | ||
808 | } | ||
809 | CHECK_GOTO(BN_div(d, e, c, a, ctx)); | ||
810 | CHECK_GOTO(BN_sub(d, d, a)); | ||
811 | if (!BN_is_zero(d) || !BN_is_zero(e)) { | ||
812 | fprintf(stderr, "Square test failed!\n"); | ||
813 | goto err; | ||
814 | } | ||
815 | } | ||
816 | |||
817 | /* Regression test for a BN_sqr overflow bug. */ | ||
818 | if (!BN_hex2bn(&a, "80000000000000008000000000000001" | ||
819 | "FFFFFFFFFFFFFFFE0000000000000000")) { | ||
820 | fprintf(stderr, "BN_hex2bn failed\n"); | ||
821 | goto err; | ||
822 | } | ||
823 | CHECK_GOTO(BN_sqr(c, a, ctx)); | ||
824 | if (bp != NULL) { | ||
825 | if (!results) { | ||
826 | CHECK_GOTO(BN_print(bp, a)); | ||
827 | BIO_puts(bp, " * "); | ||
828 | CHECK_GOTO(BN_print(bp, a)); | ||
829 | BIO_puts(bp, " - "); | ||
830 | } | ||
831 | CHECK_GOTO(BN_print(bp, c)); | ||
832 | BIO_puts(bp, "\n"); | ||
833 | } | ||
834 | CHECK_GOTO(BN_mul(d, a, a, ctx)); | ||
835 | if (BN_cmp(c, d)) { | ||
836 | fprintf(stderr, | ||
837 | "Square test failed: BN_sqr and BN_mul produce " | ||
838 | "different results!\n"); | ||
839 | goto err; | ||
840 | } | ||
841 | |||
842 | /* Regression test for a BN_sqr overflow bug. */ | ||
843 | if (!BN_hex2bn(&a, "80000000000000000000000080000001" | ||
844 | "FFFFFFFE000000000000000000000000")) { | ||
845 | fprintf(stderr, "BN_hex2bn failed\n"); | ||
846 | goto err; | ||
847 | } | ||
848 | CHECK_GOTO(BN_sqr(c, a, ctx)); | ||
849 | if (bp != NULL) { | ||
850 | if (!results) { | ||
851 | CHECK_GOTO(BN_print(bp, a)); | ||
852 | BIO_puts(bp, " * "); | ||
853 | CHECK_GOTO(BN_print(bp, a)); | ||
854 | BIO_puts(bp, " - "); | ||
855 | } | ||
856 | CHECK_GOTO(BN_print(bp, c)); | ||
857 | BIO_puts(bp, "\n"); | ||
858 | } | ||
859 | CHECK_GOTO(BN_mul(d, a, a, ctx)); | ||
860 | if (BN_cmp(c, d)) { | ||
861 | fprintf(stderr, "Square test failed: BN_sqr and BN_mul produce " | ||
862 | "different results!\n"); | ||
863 | goto err; | ||
864 | } | ||
865 | rc = 1; | ||
866 | err: | ||
867 | BN_free(a); | ||
868 | BN_free(c); | ||
869 | BN_free(d); | ||
870 | BN_free(e); | ||
871 | return rc; | ||
872 | } | ||
873 | |||
874 | int | ||
875 | test_mont(BIO *bp, BN_CTX *ctx) | ||
876 | { | ||
877 | BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *A = NULL, *B = NULL; | ||
878 | BIGNUM *n = NULL; | ||
879 | int i; | ||
880 | int rc = 1; | ||
881 | BN_MONT_CTX *mont; | ||
882 | |||
883 | mont = BN_MONT_CTX_new(); | ||
884 | if (mont == NULL) | ||
885 | return 0; | ||
886 | |||
887 | if ((a = BN_new()) == NULL) | ||
888 | goto err; | ||
889 | if ((b = BN_new()) == NULL) | ||
890 | goto err; | ||
891 | if ((c = BN_new()) == NULL) | ||
892 | goto err; | ||
893 | if ((d = BN_new()) == NULL) | ||
894 | goto err; | ||
895 | if ((A = BN_new()) == NULL) | ||
896 | goto err; | ||
897 | if ((B = BN_new()) == NULL) | ||
898 | goto err; | ||
899 | if ((n = BN_new()) == NULL) | ||
900 | goto err; | ||
901 | |||
902 | CHECK_GOTO(BN_zero(n)); | ||
903 | if (BN_MONT_CTX_set(mont, n, ctx)) { | ||
904 | fprintf(stderr, "BN_MONT_CTX_set succeeded for zero modulus!\n"); | ||
905 | return (0); | ||
906 | } | ||
907 | |||
908 | CHECK_GOTO(BN_set_word(n, 16)); | ||
909 | if (BN_MONT_CTX_set(mont, n, ctx)) { | ||
910 | fprintf(stderr, "BN_MONT_CTX_set succeeded for even modulus!\n"); | ||
911 | return (0); | ||
912 | } | ||
913 | |||
914 | CHECK_GOTO(BN_bntest_rand(a, 100, 0, 0)); | ||
915 | CHECK_GOTO(BN_bntest_rand(b, 100, 0, 0)); | ||
916 | for (i = 0; i < num2; i++) { | ||
917 | int bits = (200 * (i + 1)) / num2; | ||
918 | |||
919 | if (bits == 0) | ||
920 | continue; | ||
921 | CHECK_GOTO(BN_bntest_rand(n, bits, 0, 1)); | ||
922 | CHECK_GOTO(BN_MONT_CTX_set(mont, n, ctx)); | ||
923 | |||
924 | CHECK_GOTO(BN_nnmod(a, a, n, ctx)); | ||
925 | CHECK_GOTO(BN_nnmod(b, b, n, ctx)); | ||
926 | |||
927 | CHECK_GOTO(BN_to_montgomery(A, a, mont, ctx)); | ||
928 | CHECK_GOTO(BN_to_montgomery(B, b, mont, ctx)); | ||
929 | |||
930 | CHECK_GOTO(BN_mod_mul_montgomery(c, A, B, mont, ctx)); | ||
931 | CHECK_GOTO(BN_from_montgomery(A, c, mont, ctx)); | ||
932 | if (bp != NULL) { | ||
933 | if (!results) { | ||
934 | CHECK_GOTO(BN_print(bp, a)); | ||
935 | BIO_puts(bp, " * "); | ||
936 | CHECK_GOTO(BN_print(bp, b)); | ||
937 | BIO_puts(bp, " % "); | ||
938 | /* n == &mont->N */ | ||
939 | CHECK_GOTO(BN_print(bp, n)); | ||
940 | BIO_puts(bp, " - "); | ||
941 | } | ||
942 | CHECK_GOTO(BN_print(bp, A)); | ||
943 | BIO_puts(bp, "\n"); | ||
944 | } | ||
945 | CHECK_GOTO(BN_mod_mul(d, a, b, n, ctx)); | ||
946 | CHECK_GOTO(BN_sub(d, d, A)); | ||
947 | if (!BN_is_zero(d)) { | ||
948 | fprintf(stderr, "Montgomery multiplication test failed!\n"); | ||
949 | rc = 0; | ||
950 | break; | ||
951 | } | ||
952 | } | ||
953 | err: | ||
954 | BN_MONT_CTX_free(mont); | ||
955 | BN_free(a); | ||
956 | BN_free(b); | ||
957 | BN_free(c); | ||
958 | BN_free(d); | ||
959 | BN_free(A); | ||
960 | BN_free(B); | ||
961 | BN_free(n); | ||
962 | return (rc); | ||
963 | } | ||
964 | |||
965 | int | ||
966 | test_mod(BIO *bp, BN_CTX *ctx) | ||
967 | { | ||
968 | BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL; | ||
969 | int i; | ||
970 | int rc = 1; | ||
971 | |||
972 | if ((a = BN_new()) == NULL) | ||
973 | goto err; | ||
974 | if ((b = BN_new()) == NULL) | ||
975 | goto err; | ||
976 | if ((c = BN_new()) == NULL) | ||
977 | goto err; | ||
978 | if ((d = BN_new()) == NULL) | ||
979 | goto err; | ||
980 | if ((e = BN_new()) == NULL) | ||
981 | goto err; | ||
982 | |||
983 | CHECK_GOTO(BN_bntest_rand(a, 1024, 0, 0)); | ||
984 | for (i = 0; i < num0; i++) { | ||
985 | CHECK_GOTO(BN_bntest_rand(b, 450 + i * 10, 0, 0)); | ||
986 | BN_set_negative(a, rand_neg()); | ||
987 | BN_set_negative(b, rand_neg()); | ||
988 | CHECK_GOTO(BN_mod(c, a, b, ctx)); | ||
989 | if (bp != NULL) { | ||
990 | if (!results) { | ||
991 | CHECK_GOTO(BN_print(bp, a)); | ||
992 | BIO_puts(bp, " % "); | ||
993 | CHECK_GOTO(BN_print(bp, b)); | ||
994 | BIO_puts(bp, " - "); | ||
995 | } | ||
996 | CHECK_GOTO(BN_print(bp, c)); | ||
997 | BIO_puts(bp, "\n"); | ||
998 | } | ||
999 | CHECK_GOTO(BN_div(d, e, a, b, ctx)); | ||
1000 | CHECK_GOTO(BN_sub(e, e, c)); | ||
1001 | if (!BN_is_zero(e)) { | ||
1002 | fprintf(stderr, "Modulo test failed!\n"); | ||
1003 | rc = 0; | ||
1004 | break; | ||
1005 | } | ||
1006 | } | ||
1007 | err: | ||
1008 | BN_free(a); | ||
1009 | BN_free(b); | ||
1010 | BN_free(c); | ||
1011 | BN_free(d); | ||
1012 | BN_free(e); | ||
1013 | return (rc); | ||
1014 | } | ||
1015 | |||
1016 | int | ||
1017 | test_mod_mul(BIO *bp, BN_CTX *ctx) | ||
1018 | { | ||
1019 | BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL; | ||
1020 | int i, j; | ||
1021 | int rc = 1; | ||
1022 | |||
1023 | if ((a = BN_new()) == NULL) | ||
1024 | goto err; | ||
1025 | if ((b = BN_new()) == NULL) | ||
1026 | goto err; | ||
1027 | if ((c = BN_new()) == NULL) | ||
1028 | goto err; | ||
1029 | if ((d = BN_new()) == NULL) | ||
1030 | goto err; | ||
1031 | if ((e = BN_new()) == NULL) | ||
1032 | goto err; | ||
1033 | |||
1034 | CHECK_GOTO(BN_one(a)); | ||
1035 | CHECK_GOTO(BN_one(b)); | ||
1036 | CHECK_GOTO(BN_zero(c)); | ||
1037 | if (BN_mod_mul(e, a, b, c, ctx)) { | ||
1038 | fprintf(stderr, "BN_mod_mul with zero modulus succeeded!\n"); | ||
1039 | return (0); | ||
1040 | } | ||
1041 | |||
1042 | for (j = 0; j < 3; j++) { | ||
1043 | CHECK_GOTO(BN_bntest_rand(c, 1024, 0, 0)); | ||
1044 | for (i = 0; i < num0; i++) { | ||
1045 | CHECK_GOTO(BN_bntest_rand(a, 475 + i * 10, 0, 0)); | ||
1046 | CHECK_GOTO(BN_bntest_rand(b, 425 + i * 11, 0, 0)); | ||
1047 | BN_set_negative(a, rand_neg()); | ||
1048 | BN_set_negative(b, rand_neg()); | ||
1049 | if (!BN_mod_mul(e, a, b, c, ctx)) { | ||
1050 | unsigned long l; | ||
1051 | |||
1052 | while ((l = ERR_get_error())) | ||
1053 | fprintf(stderr, "ERROR:%s\n", | ||
1054 | ERR_error_string(l, NULL)); | ||
1055 | exit(1); | ||
1056 | } | ||
1057 | if (bp != NULL) { | ||
1058 | if (!results) { | ||
1059 | CHECK_GOTO(BN_print(bp, a)); | ||
1060 | BIO_puts(bp, " * "); | ||
1061 | CHECK_GOTO(BN_print(bp, b)); | ||
1062 | BIO_puts(bp, " % "); | ||
1063 | CHECK_GOTO(BN_print(bp, c)); | ||
1064 | if ((BN_is_negative(a) ^ BN_is_negative(b)) && | ||
1065 | !BN_is_zero(e)) { | ||
1066 | /* If (a*b) % c is negative, c must be added | ||
1067 | * in order to obtain the normalized remainder | ||
1068 | * (new with OpenSSL 0.9.7, previous versions of | ||
1069 | * BN_mod_mul could generate negative results) | ||
1070 | */ | ||
1071 | BIO_puts(bp, " + "); | ||
1072 | CHECK_GOTO(BN_print(bp, c)); | ||
1073 | } | ||
1074 | BIO_puts(bp, " - "); | ||
1075 | } | ||
1076 | CHECK_GOTO(BN_print(bp, e)); | ||
1077 | BIO_puts(bp, "\n"); | ||
1078 | } | ||
1079 | CHECK_GOTO(BN_mul(d, a, b, ctx)); | ||
1080 | CHECK_GOTO(BN_sub(d, d, e)); | ||
1081 | CHECK_GOTO(BN_div(a, b, d, c, ctx)); | ||
1082 | if (!BN_is_zero(b)) { | ||
1083 | fprintf(stderr, "Modulo multiply test failed!\n"); | ||
1084 | ERR_print_errors_fp(stderr); | ||
1085 | rc = 0; | ||
1086 | goto err; | ||
1087 | } | ||
1088 | } | ||
1089 | } | ||
1090 | err: | ||
1091 | BN_free(a); | ||
1092 | BN_free(b); | ||
1093 | BN_free(c); | ||
1094 | BN_free(d); | ||
1095 | BN_free(e); | ||
1096 | return (rc); | ||
1097 | } | ||
1098 | |||
1099 | int | ||
1100 | test_mod_exp(BIO *bp, BN_CTX *ctx) | ||
1101 | { | ||
1102 | BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL; | ||
1103 | int i; | ||
1104 | int rc = 1; | ||
1105 | |||
1106 | if ((a = BN_new()) == NULL) | ||
1107 | goto err; | ||
1108 | if ((b = BN_new()) == NULL) | ||
1109 | goto err; | ||
1110 | if ((c = BN_new()) == NULL) | ||
1111 | goto err; | ||
1112 | if ((d = BN_new()) == NULL) | ||
1113 | goto err; | ||
1114 | if ((e = BN_new()) == NULL) | ||
1115 | goto err; | ||
1116 | |||
1117 | CHECK_GOTO(BN_one(a)); | ||
1118 | CHECK_GOTO(BN_one(b)); | ||
1119 | CHECK_GOTO(BN_zero(c)); | ||
1120 | if (BN_mod_exp(d, a, b, c, ctx)) { | ||
1121 | fprintf(stderr, "BN_mod_exp with zero modulus succeeded!\n"); | ||
1122 | rc = 0; | ||
1123 | goto err; | ||
1124 | } | ||
1125 | if (BN_mod_exp_ct(d, a, b, c, ctx)) { | ||
1126 | fprintf(stderr, "BN_mod_exp_ct with zero modulus succeeded!\n"); | ||
1127 | rc = 0; | ||
1128 | goto err; | ||
1129 | } | ||
1130 | if (BN_mod_exp_nonct(d, a, b, c, ctx)) { | ||
1131 | fprintf(stderr, "BN_mod_exp_nonct with zero modulus succeeded!\n"); | ||
1132 | rc = 0; | ||
1133 | goto err; | ||
1134 | } | ||
1135 | |||
1136 | CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */ | ||
1137 | for (i = 0; i < num2; i++) { | ||
1138 | CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0)); | ||
1139 | CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0)); | ||
1140 | |||
1141 | if (!BN_mod_exp(d, a, b, c, ctx)) { | ||
1142 | rc = 0; | ||
1143 | break; | ||
1144 | } | ||
1145 | |||
1146 | if (bp != NULL) { | ||
1147 | if (!results) { | ||
1148 | CHECK_GOTO(BN_print(bp, a)); | ||
1149 | BIO_puts(bp, " ^ "); | ||
1150 | CHECK_GOTO(BN_print(bp, b)); | ||
1151 | BIO_puts(bp, " % "); | ||
1152 | CHECK_GOTO(BN_print(bp, c)); | ||
1153 | BIO_puts(bp, " - "); | ||
1154 | } | ||
1155 | CHECK_GOTO(BN_print(bp, d)); | ||
1156 | BIO_puts(bp, "\n"); | ||
1157 | } | ||
1158 | CHECK_GOTO(BN_exp(e, a, b, ctx)); | ||
1159 | CHECK_GOTO(BN_sub(e, e, d)); | ||
1160 | CHECK_GOTO(BN_div(a, b, e, c, ctx)); | ||
1161 | if (!BN_is_zero(b)) { | ||
1162 | fprintf(stderr, "Modulo exponentiation test failed!\n"); | ||
1163 | rc = 0; | ||
1164 | break; | ||
1165 | } | ||
1166 | } | ||
1167 | |||
1168 | CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */ | ||
1169 | for (i = 0; i < num2; i++) { | ||
1170 | CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0)); | ||
1171 | CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0)); | ||
1172 | |||
1173 | if (!BN_mod_exp_ct(d, a, b, c, ctx)) { | ||
1174 | rc = 0; | ||
1175 | break; | ||
1176 | } | ||
1177 | |||
1178 | if (bp != NULL) { | ||
1179 | if (!results) { | ||
1180 | CHECK_GOTO(BN_print(bp, a)); | ||
1181 | BIO_puts(bp, " ^ "); | ||
1182 | CHECK_GOTO(BN_print(bp, b)); | ||
1183 | BIO_puts(bp, " % "); | ||
1184 | CHECK_GOTO(BN_print(bp, c)); | ||
1185 | BIO_puts(bp, " - "); | ||
1186 | } | ||
1187 | CHECK_GOTO(BN_print(bp, d)); | ||
1188 | BIO_puts(bp, "\n"); | ||
1189 | } | ||
1190 | CHECK_GOTO(BN_exp(e, a, b, ctx)); | ||
1191 | CHECK_GOTO(BN_sub(e, e, d)); | ||
1192 | CHECK_GOTO(BN_div(a, b, e, c, ctx)); | ||
1193 | if (!BN_is_zero(b)) { | ||
1194 | fprintf(stderr, "Modulo exponentiation test failed!\n"); | ||
1195 | rc = 0; | ||
1196 | break; | ||
1197 | } | ||
1198 | } | ||
1199 | |||
1200 | CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */ | ||
1201 | for (i = 0; i < num2; i++) { | ||
1202 | CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0)); | ||
1203 | CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0)); | ||
1204 | |||
1205 | if (!BN_mod_exp_nonct(d, a, b, c, ctx)) { | ||
1206 | rc = 0; | ||
1207 | break; | ||
1208 | } | ||
1209 | |||
1210 | if (bp != NULL) { | ||
1211 | if (!results) { | ||
1212 | CHECK_GOTO(BN_print(bp, a)); | ||
1213 | BIO_puts(bp, " ^ "); | ||
1214 | CHECK_GOTO(BN_print(bp, b)); | ||
1215 | BIO_puts(bp, " % "); | ||
1216 | CHECK_GOTO(BN_print(bp, c)); | ||
1217 | BIO_puts(bp, " - "); | ||
1218 | } | ||
1219 | CHECK_GOTO(BN_print(bp, d)); | ||
1220 | BIO_puts(bp, "\n"); | ||
1221 | } | ||
1222 | CHECK_GOTO(BN_exp(e, a, b, ctx)); | ||
1223 | CHECK_GOTO(BN_sub(e, e, d)); | ||
1224 | CHECK_GOTO(BN_div(a, b, e, c, ctx)); | ||
1225 | if (!BN_is_zero(b)) { | ||
1226 | fprintf(stderr, "Modulo exponentiation test failed!\n"); | ||
1227 | rc = 0; | ||
1228 | break; | ||
1229 | } | ||
1230 | } | ||
1231 | err: | ||
1232 | BN_free(a); | ||
1233 | BN_free(b); | ||
1234 | BN_free(c); | ||
1235 | BN_free(d); | ||
1236 | BN_free(e); | ||
1237 | return (rc); | ||
1238 | } | ||
1239 | |||
1240 | int | ||
1241 | test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx) | ||
1242 | { | ||
1243 | BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL; | ||
1244 | int i; | ||
1245 | int rc = 1; | ||
1246 | |||
1247 | if ((a = BN_new()) == NULL) | ||
1248 | goto err; | ||
1249 | if ((b = BN_new()) == NULL) | ||
1250 | goto err; | ||
1251 | if ((c = BN_new()) == NULL) | ||
1252 | goto err; | ||
1253 | if ((d = BN_new()) == NULL) | ||
1254 | goto err; | ||
1255 | if ((e = BN_new()) == NULL) | ||
1256 | goto err; | ||
1257 | |||
1258 | CHECK_GOTO(BN_one(a)); | ||
1259 | CHECK_GOTO(BN_one(b)); | ||
1260 | CHECK_GOTO(BN_zero(c)); | ||
1261 | if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) { | ||
1262 | fprintf(stderr, "BN_mod_exp_mont_consttime with zero modulus " | ||
1263 | "succeeded\n"); | ||
1264 | rc = 0; | ||
1265 | goto err; | ||
1266 | } | ||
1267 | |||
1268 | CHECK_GOTO(BN_set_word(c, 16)); | ||
1269 | if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) { | ||
1270 | fprintf(stderr, "BN_mod_exp_mont_consttime with even modulus " | ||
1271 | "succeeded\n"); | ||
1272 | rc = 0; | ||
1273 | goto err; | ||
1274 | } | ||
1275 | |||
1276 | CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */ | ||
1277 | for (i = 0; i < num2; i++) { | ||
1278 | CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0)); | ||
1279 | CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0)); | ||
1280 | |||
1281 | if (!BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) { | ||
1282 | rc = 0; | ||
1283 | break; | ||
1284 | } | ||
1285 | |||
1286 | if (bp != NULL) { | ||
1287 | if (!results) { | ||
1288 | CHECK_GOTO(BN_print(bp, a)); | ||
1289 | BIO_puts(bp, " ^ "); | ||
1290 | CHECK_GOTO(BN_print(bp, b)); | ||
1291 | BIO_puts(bp, " % "); | ||
1292 | CHECK_GOTO(BN_print(bp, c)); | ||
1293 | BIO_puts(bp, " - "); | ||
1294 | } | ||
1295 | CHECK_GOTO(BN_print(bp, d)); | ||
1296 | BIO_puts(bp, "\n"); | ||
1297 | } | ||
1298 | CHECK_GOTO(BN_exp(e, a, b, ctx)); | ||
1299 | CHECK_GOTO(BN_sub(e, e, d)); | ||
1300 | CHECK_GOTO(BN_div(a, b, e, c, ctx)); | ||
1301 | if (!BN_is_zero(b)) { | ||
1302 | fprintf(stderr, "Modulo exponentiation test failed!\n"); | ||
1303 | rc = 0; | ||
1304 | break; | ||
1305 | } | ||
1306 | } | ||
1307 | err: | ||
1308 | BN_free(a); | ||
1309 | BN_free(b); | ||
1310 | BN_free(c); | ||
1311 | BN_free(d); | ||
1312 | BN_free(e); | ||
1313 | return (rc); | ||
1314 | } | ||
1315 | |||
1316 | /* | ||
1317 | * Test constant-time modular exponentiation with 1024-bit inputs, which on | ||
1318 | * x86_64 cause a different code branch to be taken. | ||
1319 | */ | ||
1320 | int | ||
1321 | test_mod_exp_mont5(BIO *bp, BN_CTX *ctx) | ||
1322 | { | ||
1323 | BIGNUM *a = NULL, *p = NULL, *m = NULL, *d = NULL, *e = NULL; | ||
1324 | BIGNUM *b = NULL, *n = NULL, *c = NULL; | ||
1325 | BN_MONT_CTX *mont = NULL; | ||
1326 | int len; | ||
1327 | int rc = 1; | ||
1328 | |||
1329 | if ((a = BN_new()) == NULL) | ||
1330 | goto err; | ||
1331 | if ((p = BN_new()) == NULL) | ||
1332 | goto err; | ||
1333 | if ((m = BN_new()) == NULL) | ||
1334 | goto err; | ||
1335 | if ((d = BN_new()) == NULL) | ||
1336 | goto err; | ||
1337 | if ((e = BN_new()) == NULL) | ||
1338 | goto err; | ||
1339 | if ((b = BN_new()) == NULL) | ||
1340 | goto err; | ||
1341 | if ((n = BN_new()) == NULL) | ||
1342 | goto err; | ||
1343 | if ((c = BN_new()) == NULL) | ||
1344 | goto err; | ||
1345 | |||
1346 | CHECK_GOTO(mont = BN_MONT_CTX_new()); | ||
1347 | |||
1348 | CHECK_GOTO(BN_bntest_rand(m, 1024, 0, 1)); /* must be odd for montgomery */ | ||
1349 | /* Zero exponent */ | ||
1350 | CHECK_GOTO(BN_bntest_rand(a, 1024, 0, 0)); | ||
1351 | CHECK_GOTO(BN_zero(p)); | ||
1352 | if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)) { | ||
1353 | rc = 0; | ||
1354 | goto err; | ||
1355 | } | ||
1356 | if (!BN_is_one(d)) { | ||
1357 | fprintf(stderr, "Modular exponentiation test failed!\n"); | ||
1358 | rc = 0; | ||
1359 | goto err; | ||
1360 | } | ||
1361 | /* Regression test for carry bug in mulx4x_mont */ | ||
1362 | len = BN_hex2bn(&a, | ||
1363 | "7878787878787878787878787878787878787878787878787878787878787878" | ||
1364 | "7878787878787878787878787878787878787878787878787878787878787878" | ||
1365 | "7878787878787878787878787878787878787878787878787878787878787878" | ||
1366 | "7878787878787878787878787878787878787878787878787878787878787878"); | ||
1367 | CHECK_GOTO(len); | ||
1368 | len = BN_hex2bn(&b, | ||
1369 | "095D72C08C097BA488C5E439C655A192EAFB6380073D8C2664668EDDB4060744" | ||
1370 | "E16E57FB4EDB9AE10A0CEFCDC28A894F689A128379DB279D48A2E20849D68593" | ||
1371 | "9B7803BCF46CEBF5C533FB0DD35B080593DE5472E3FE5DB951B8BFF9B4CB8F03" | ||
1372 | "9CC638A5EE8CDD703719F8000E6A9F63BEED5F2FCD52FF293EA05A251BB4AB81"); | ||
1373 | CHECK_GOTO(len); | ||
1374 | len = BN_hex2bn(&n, | ||
1375 | "D78AF684E71DB0C39CFF4E64FB9DB567132CB9C50CC98009FEB820B26F2DED9B" | ||
1376 | "91B9B5E2B83AE0AE4EB4E0523CA726BFBE969B89FD754F674CE99118C3F2D1C5" | ||
1377 | "D81FDC7C54E02B60262B241D53C040E99E45826ECA37A804668E690E1AFC1CA4" | ||
1378 | "2C9A15D84D4954425F0B7642FC0BD9D7B24E2618D2DCC9B729D944BADACFDDAF"); | ||
1379 | CHECK_GOTO(len); | ||
1380 | CHECK_GOTO(BN_MONT_CTX_set(mont, n, ctx)); | ||
1381 | CHECK_GOTO(BN_mod_mul_montgomery(c, a, b, mont, ctx)); | ||
1382 | CHECK_GOTO(BN_mod_mul_montgomery(d, b, a, mont, ctx)); | ||
1383 | if (BN_cmp(c, d)) { | ||
1384 | fprintf(stderr, "Montgomery multiplication test failed:" | ||
1385 | " a*b != b*a.\n"); | ||
1386 | rc = 0; | ||
1387 | goto err; | ||
1388 | } | ||
1389 | /* Regression test for carry bug in sqr[x]8x_mont */ | ||
1390 | len = BN_hex2bn(&n, | ||
1391 | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" | ||
1392 | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" | ||
1393 | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" | ||
1394 | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" | ||
1395 | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" | ||
1396 | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" | ||
1397 | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" | ||
1398 | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF00" | ||
1399 | "0000000000000000000000000000000000000000000000000000000000000000" | ||
1400 | "0000000000000000000000000000000000000000000000000000000000000000" | ||
1401 | "0000000000000000000000000000000000000000000000000000000000000000" | ||
1402 | "0000000000000000000000000000000000000000000000000000000000000000" | ||
1403 | "0000000000000000000000000000000000000000000000000000000000000000" | ||
1404 | "0000000000000000000000000000000000000000000000000000000000000000" | ||
1405 | "0000000000000000000000000000000000000000000000000000000000000000" | ||
1406 | "00000000000000000000000000000000000000000000000000FFFFFFFFFFFFFF"); | ||
1407 | CHECK_GOTO(len); | ||
1408 | len = BN_hex2bn(&a, | ||
1409 | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" | ||
1410 | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" | ||
1411 | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" | ||
1412 | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" | ||
1413 | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" | ||
1414 | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" | ||
1415 | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" | ||
1416 | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF0000000000" | ||
1417 | "0000000000000000000000000000000000000000000000000000000000000000" | ||
1418 | "0000000000000000000000000000000000000000000000000000000000000000" | ||
1419 | "0000000000000000000000000000000000000000000000000000000000000000" | ||
1420 | "0000000000000000000000000000000000000000000000000000000000000000" | ||
1421 | "0000000000000000000000000000000000000000000000000000000000000000" | ||
1422 | "0000000000000000000000000000000000000000000000000000000000000000" | ||
1423 | "0000000000000000000000000000000000000000000000000000000000000000" | ||
1424 | "000000000000000000000000000000000000000000FFFFFFFFFFFFFF00000000"); | ||
1425 | CHECK_GOTO(len); | ||
1426 | BN_free(b); | ||
1427 | CHECK_GOTO(b = BN_dup(a)); | ||
1428 | CHECK_GOTO(BN_MONT_CTX_set(mont, n, ctx)); | ||
1429 | CHECK_GOTO(BN_mod_mul_montgomery(c, a, a, mont, ctx)); | ||
1430 | CHECK_GOTO(BN_mod_mul_montgomery(d, a, b, mont, ctx)); | ||
1431 | if (BN_cmp(c, d)) { | ||
1432 | fprintf(stderr, "Montgomery multiplication test failed:" | ||
1433 | " a**2 != a*a.\n"); | ||
1434 | rc = 0; | ||
1435 | goto err; | ||
1436 | } | ||
1437 | /* Zero input */ | ||
1438 | CHECK_GOTO(BN_bntest_rand(p, 1024, 0, 0)); | ||
1439 | CHECK_GOTO(BN_zero(a)); | ||
1440 | if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)) { | ||
1441 | rc = 0; | ||
1442 | goto err; | ||
1443 | } | ||
1444 | if (!BN_is_zero(d)) { | ||
1445 | fprintf(stderr, "Modular exponentiation test failed!\n"); | ||
1446 | rc = 0; | ||
1447 | goto err; | ||
1448 | } | ||
1449 | /* | ||
1450 | * Craft an input whose Montgomery representation is 1, i.e., shorter | ||
1451 | * than the modulus m, in order to test the const time precomputation | ||
1452 | * scattering/gathering. | ||
1453 | */ | ||
1454 | CHECK_GOTO(BN_one(a)); | ||
1455 | CHECK_GOTO(BN_MONT_CTX_set(mont, m, ctx)); | ||
1456 | if (!BN_from_montgomery(e, a, mont, ctx)) { | ||
1457 | rc = 0; | ||
1458 | goto err; | ||
1459 | } | ||
1460 | if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL)) { | ||
1461 | rc = 0; | ||
1462 | goto err; | ||
1463 | } | ||
1464 | if (!BN_mod_exp_simple(a, e, p, m, ctx)) { | ||
1465 | rc = 0; | ||
1466 | goto err; | ||
1467 | } | ||
1468 | if (BN_cmp(a, d) != 0) { | ||
1469 | fprintf(stderr, "Modular exponentiation test failed!\n"); | ||
1470 | rc = 0; | ||
1471 | goto err; | ||
1472 | } | ||
1473 | /* Finally, some regular test vectors. */ | ||
1474 | CHECK_GOTO(BN_bntest_rand(e, 1024, 0, 0)); | ||
1475 | if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL)) { | ||
1476 | rc = 0; | ||
1477 | goto err; | ||
1478 | } | ||
1479 | if (!BN_mod_exp_simple(a, e, p, m, ctx)) { | ||
1480 | rc = 0; | ||
1481 | goto err; | ||
1482 | } | ||
1483 | if (BN_cmp(a, d) != 0) { | ||
1484 | fprintf(stderr, "Modular exponentiation test failed!\n"); | ||
1485 | rc = 0; | ||
1486 | goto err; | ||
1487 | } | ||
1488 | err: | ||
1489 | BN_free(a); | ||
1490 | BN_free(p); | ||
1491 | BN_free(m); | ||
1492 | BN_free(d); | ||
1493 | BN_free(e); | ||
1494 | BN_free(b); | ||
1495 | BN_free(n); | ||
1496 | BN_free(c); | ||
1497 | BN_MONT_CTX_free(mont); | ||
1498 | return (rc); | ||
1499 | } | ||
1500 | |||
1501 | int | ||
1502 | test_exp(BIO *bp, BN_CTX *ctx) | ||
1503 | { | ||
1504 | BIGNUM *a = NULL, *b = NULL, *d = NULL, *e = NULL, *one = NULL; | ||
1505 | int i; | ||
1506 | int rc = 1; | ||
1507 | |||
1508 | if ((a = BN_new()) == NULL) | ||
1509 | goto err; | ||
1510 | if ((b = BN_new()) == NULL) | ||
1511 | goto err; | ||
1512 | if ((d = BN_new()) == NULL) | ||
1513 | goto err; | ||
1514 | if ((e = BN_new()) == NULL) | ||
1515 | goto err; | ||
1516 | if ((one = BN_new()) == NULL) | ||
1517 | goto err; | ||
1518 | CHECK_GOTO(BN_one(one)); | ||
1519 | |||
1520 | for (i = 0; i < num2; i++) { | ||
1521 | CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0)); | ||
1522 | CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0)); | ||
1523 | |||
1524 | if (BN_exp(d, a, b, ctx) <= 0) { | ||
1525 | rc = 0; | ||
1526 | break; | ||
1527 | } | ||
1528 | |||
1529 | if (bp != NULL) { | ||
1530 | if (!results) { | ||
1531 | CHECK_GOTO(BN_print(bp, a)); | ||
1532 | BIO_puts(bp, " ^ "); | ||
1533 | CHECK_GOTO(BN_print(bp, b)); | ||
1534 | BIO_puts(bp, " - "); | ||
1535 | } | ||
1536 | CHECK_GOTO(BN_print(bp, d)); | ||
1537 | BIO_puts(bp, "\n"); | ||
1538 | } | ||
1539 | CHECK_GOTO(BN_one(e)); | ||
1540 | for (; !BN_is_zero(b); BN_sub(b, b, one)) | ||
1541 | CHECK_GOTO(BN_mul(e, e, a, ctx)); | ||
1542 | CHECK_GOTO(BN_sub(e, e, d)); | ||
1543 | if (!BN_is_zero(e)) { | ||
1544 | fprintf(stderr, "Exponentiation test failed!\n"); | ||
1545 | rc = 0; | ||
1546 | break; | ||
1547 | } | ||
1548 | } | ||
1549 | err: | ||
1550 | BN_free(a); | ||
1551 | BN_free(b); | ||
1552 | BN_free(d); | ||
1553 | BN_free(e); | ||
1554 | BN_free(one); | ||
1555 | return (rc); | ||
1556 | } | ||
1557 | |||
1558 | #ifndef OPENSSL_NO_EC2M | ||
1559 | int | ||
1560 | test_gf2m_add(BIO *bp) | ||
1561 | { | ||
1562 | BIGNUM *a = NULL, *b = NULL, *c = NULL; | ||
1563 | int i, rc = 0; | ||
1564 | |||
1565 | if ((a = BN_new()) == NULL) | ||
1566 | goto err; | ||
1567 | if ((b = BN_new()) == NULL) | ||
1568 | goto err; | ||
1569 | if ((c = BN_new()) == NULL) | ||
1570 | goto err; | ||
1571 | |||
1572 | for (i = 0; i < num0; i++) { | ||
1573 | CHECK_GOTO(BN_rand(a, 512, 0, 0)); | ||
1574 | CHECK_GOTO(BN_copy(b, BN_value_one())); | ||
1575 | BN_set_negative(a, rand_neg()); | ||
1576 | BN_set_negative(b, rand_neg()); | ||
1577 | CHECK_GOTO(BN_GF2m_add(c, a, b)); | ||
1578 | #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ | ||
1579 | if (bp != NULL) { | ||
1580 | if (!results) { | ||
1581 | CHECK_GOTO(BN_print(bp, a)); | ||
1582 | BIO_puts(bp, " ^ "); | ||
1583 | CHECK_GOTO(BN_print(bp, b)); | ||
1584 | BIO_puts(bp, " = "); | ||
1585 | } | ||
1586 | CHECK_GOTO(BN_print(bp, c)); | ||
1587 | BIO_puts(bp, "\n"); | ||
1588 | } | ||
1589 | #endif | ||
1590 | /* Test that two added values have the correct parity. */ | ||
1591 | if ((BN_is_odd(a) && BN_is_odd(c)) | ||
1592 | || (!BN_is_odd(a) && !BN_is_odd(c))) { | ||
1593 | fprintf(stderr, "GF(2^m) addition test (a) failed!\n"); | ||
1594 | goto err; | ||
1595 | } | ||
1596 | CHECK_GOTO(BN_GF2m_add(c, c, c)); | ||
1597 | /* Test that c + c = 0. */ | ||
1598 | if (!BN_is_zero(c)) { | ||
1599 | fprintf(stderr, "GF(2^m) addition test (b) failed!\n"); | ||
1600 | goto err; | ||
1601 | } | ||
1602 | } | ||
1603 | rc = 1; | ||
1604 | err: | ||
1605 | BN_free(a); | ||
1606 | BN_free(b); | ||
1607 | BN_free(c); | ||
1608 | return rc; | ||
1609 | } | ||
1610 | |||
1611 | int | ||
1612 | test_gf2m_mod(BIO *bp) | ||
1613 | { | ||
1614 | BIGNUM *a = NULL, *b[2] = { 0 }, *c = NULL, *d = NULL, *e = NULL; | ||
1615 | int i, j; | ||
1616 | int p0[] = { 163, 7, 6, 3, 0, -1 }; | ||
1617 | int p1[] = { 193, 15, 0, -1 }; | ||
1618 | int rc = 0; | ||
1619 | |||
1620 | if ((a = BN_new()) == NULL) | ||
1621 | goto err; | ||
1622 | if ((b[0] = BN_new()) == NULL) | ||
1623 | goto err; | ||
1624 | if ((b[1] = BN_new()) == NULL) | ||
1625 | goto err; | ||
1626 | if ((c = BN_new()) == NULL) | ||
1627 | goto err; | ||
1628 | if ((d = BN_new()) == NULL) | ||
1629 | goto err; | ||
1630 | if ((e = BN_new()) == NULL) | ||
1631 | goto err; | ||
1632 | |||
1633 | CHECK_GOTO(BN_GF2m_arr2poly(p0, b[0])); | ||
1634 | CHECK_GOTO(BN_GF2m_arr2poly(p1, b[1])); | ||
1635 | |||
1636 | for (i = 0; i < num0; i++) { | ||
1637 | CHECK_GOTO(BN_bntest_rand(a, 1024, 0, 0)); | ||
1638 | for (j = 0; j < 2; j++) { | ||
1639 | CHECK_GOTO(BN_GF2m_mod(c, a, b[j])); | ||
1640 | #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ | ||
1641 | if (bp != NULL) { | ||
1642 | if (!results) { | ||
1643 | CHECK_GOTO(BN_print(bp, a)); | ||
1644 | BIO_puts(bp, " % "); | ||
1645 | CHECK_GOTO(BN_print(bp, b[j])); | ||
1646 | BIO_puts(bp, " - "); | ||
1647 | CHECK_GOTO(BN_print(bp, c)); | ||
1648 | BIO_puts(bp, "\n"); | ||
1649 | } | ||
1650 | } | ||
1651 | #endif | ||
1652 | CHECK_GOTO(BN_GF2m_add(d, a, c)); | ||
1653 | CHECK_GOTO(BN_GF2m_mod(e, d, b[j])); | ||
1654 | /* Test that a + (a mod p) mod p == 0. */ | ||
1655 | if (!BN_is_zero(e)) { | ||
1656 | fprintf(stderr, "GF(2^m) modulo test failed!\n"); | ||
1657 | goto err; | ||
1658 | } | ||
1659 | } | ||
1660 | } | ||
1661 | rc = 1; | ||
1662 | err: | ||
1663 | BN_free(a); | ||
1664 | BN_free(b[0]); | ||
1665 | BN_free(b[1]); | ||
1666 | BN_free(c); | ||
1667 | BN_free(d); | ||
1668 | BN_free(e); | ||
1669 | return rc; | ||
1670 | } | ||
1671 | |||
1672 | int | ||
1673 | test_gf2m_mod_mul(BIO *bp, BN_CTX *ctx) | ||
1674 | { | ||
1675 | BIGNUM *a = NULL, *b[2] = { 0 }, *c = NULL, *d = NULL, *e = NULL, *f = NULL; | ||
1676 | BIGNUM *g = NULL, *h = NULL; | ||
1677 | int i, j; | ||
1678 | int p0[] = { 163, 7, 6, 3, 0, -1 }; | ||
1679 | int p1[] = { 193, 15, 0, -1 }; | ||
1680 | int rc = 0; | ||
1681 | |||
1682 | if ((a = BN_new()) == NULL) | ||
1683 | goto err; | ||
1684 | if ((b[0] = BN_new()) == NULL) | ||
1685 | goto err; | ||
1686 | if ((b[1] = BN_new()) == NULL) | ||
1687 | goto err; | ||
1688 | if ((c = BN_new()) == NULL) | ||
1689 | goto err; | ||
1690 | if ((d = BN_new()) == NULL) | ||
1691 | goto err; | ||
1692 | if ((e = BN_new()) == NULL) | ||
1693 | goto err; | ||
1694 | if ((f = BN_new()) == NULL) | ||
1695 | goto err; | ||
1696 | if ((g = BN_new()) == NULL) | ||
1697 | goto err; | ||
1698 | if ((h = BN_new()) == NULL) | ||
1699 | goto err; | ||
1700 | |||
1701 | CHECK_GOTO(BN_GF2m_arr2poly(p0, b[0])); | ||
1702 | CHECK_GOTO(BN_GF2m_arr2poly(p1, b[1])); | ||
1703 | |||
1704 | for (i = 0; i < num0; i++) { | ||
1705 | CHECK_GOTO(BN_bntest_rand(a, 1024, 0, 0)); | ||
1706 | CHECK_GOTO(BN_bntest_rand(c, 1024, 0, 0)); | ||
1707 | CHECK_GOTO(BN_bntest_rand(d, 1024, 0, 0)); | ||
1708 | for (j = 0; j < 2; j++) { | ||
1709 | CHECK_GOTO(BN_GF2m_mod_mul(e, a, c, b[j], ctx)); | ||
1710 | #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ | ||
1711 | if (bp != NULL) { | ||
1712 | if (!results) { | ||
1713 | CHECK_GOTO(BN_print(bp, a)); | ||
1714 | BIO_puts(bp, " * "); | ||
1715 | CHECK_GOTO(BN_print(bp, c)); | ||
1716 | BIO_puts(bp, " % "); | ||
1717 | CHECK_GOTO(BN_print(bp, b[j])); | ||
1718 | BIO_puts(bp, " - "); | ||
1719 | CHECK_GOTO(BN_print(bp, e)); | ||
1720 | BIO_puts(bp, "\n"); | ||
1721 | } | ||
1722 | } | ||
1723 | #endif | ||
1724 | CHECK_GOTO(BN_GF2m_add(f, a, d)); | ||
1725 | CHECK_GOTO(BN_GF2m_mod_mul(g, f, c, b[j], ctx)); | ||
1726 | CHECK_GOTO(BN_GF2m_mod_mul(h, d, c, b[j], ctx)); | ||
1727 | CHECK_GOTO(BN_GF2m_add(f, e, g)); | ||
1728 | CHECK_GOTO(BN_GF2m_add(f, f, h)); | ||
1729 | /* Test that (a+d)*c = a*c + d*c. */ | ||
1730 | if (!BN_is_zero(f)) { | ||
1731 | fprintf(stderr, "GF(2^m) modular multiplication test failed!\n"); | ||
1732 | goto err; | ||
1733 | } | ||
1734 | } | ||
1735 | } | ||
1736 | rc = 1; | ||
1737 | err: | ||
1738 | BN_free(a); | ||
1739 | BN_free(b[0]); | ||
1740 | BN_free(b[1]); | ||
1741 | BN_free(c); | ||
1742 | BN_free(d); | ||
1743 | BN_free(e); | ||
1744 | BN_free(f); | ||
1745 | BN_free(g); | ||
1746 | BN_free(h); | ||
1747 | return rc; | ||
1748 | } | ||
1749 | |||
1750 | int | ||
1751 | test_gf2m_mod_sqr(BIO *bp, BN_CTX *ctx) | ||
1752 | { | ||
1753 | BIGNUM *a = NULL, *b[2] = { 0 }, *c = NULL, *d = NULL; | ||
1754 | int i, j, rc = 0; | ||
1755 | int p0[] = { 163, 7, 6, 3, 0, -1 }; | ||
1756 | int p1[] = { 193, 15, 0, -1 }; | ||
1757 | |||
1758 | if ((a = BN_new()) == NULL) | ||
1759 | goto err; | ||
1760 | if ((b[0] = BN_new()) == NULL) | ||
1761 | goto err; | ||
1762 | if ((b[1] = BN_new()) == NULL) | ||
1763 | goto err; | ||
1764 | if ((c = BN_new()) == NULL) | ||
1765 | goto err; | ||
1766 | if ((d = BN_new()) == NULL) | ||
1767 | goto err; | ||
1768 | |||
1769 | CHECK_GOTO(BN_GF2m_arr2poly(p0, b[0])); | ||
1770 | CHECK_GOTO(BN_GF2m_arr2poly(p1, b[1])); | ||
1771 | |||
1772 | for (i = 0; i < num0; i++) { | ||
1773 | CHECK_GOTO(BN_bntest_rand(a, 1024, 0, 0)); | ||
1774 | for (j = 0; j < 2; j++) { | ||
1775 | CHECK_GOTO(BN_GF2m_mod_sqr(c, a, b[j], ctx)); | ||
1776 | CHECK_GOTO(BN_copy(d, a)); | ||
1777 | CHECK_GOTO(BN_GF2m_mod_mul(d, a, d, b[j], ctx)); | ||
1778 | #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ | ||
1779 | if (bp != NULL) { | ||
1780 | if (!results) { | ||
1781 | CHECK_GOTO(BN_print(bp, a)); | ||
1782 | BIO_puts(bp, " ^ 2 % "); | ||
1783 | CHECK_GOTO(BN_print(bp, b[j])); | ||
1784 | BIO_puts(bp, " = "); | ||
1785 | CHECK_GOTO(BN_print(bp, c)); | ||
1786 | BIO_puts(bp, "; a * a = "); | ||
1787 | CHECK_GOTO(BN_print(bp, d)); | ||
1788 | BIO_puts(bp, "\n"); | ||
1789 | } | ||
1790 | } | ||
1791 | #endif | ||
1792 | CHECK_GOTO(BN_GF2m_add(d, c, d)); | ||
1793 | /* Test that a*a = a^2. */ | ||
1794 | if (!BN_is_zero(d)) { | ||
1795 | fprintf(stderr, "GF(2^m) modular squaring test failed!\n"); | ||
1796 | goto err; | ||
1797 | } | ||
1798 | } | ||
1799 | } | ||
1800 | rc = 1; | ||
1801 | err: | ||
1802 | BN_free(a); | ||
1803 | BN_free(b[0]); | ||
1804 | BN_free(b[1]); | ||
1805 | BN_free(c); | ||
1806 | BN_free(d); | ||
1807 | return rc; | ||
1808 | } | ||
1809 | |||
1810 | int | ||
1811 | test_gf2m_mod_inv(BIO *bp, BN_CTX *ctx) | ||
1812 | { | ||
1813 | BIGNUM *a = NULL, *b[2] = { 0 }, *c = NULL, *d = NULL; | ||
1814 | int i, j, rc = 0; | ||
1815 | int p0[] = { 163, 7, 6, 3, 0, -1 }; | ||
1816 | int p1[] = { 193, 15, 0, -1 }; | ||
1817 | |||
1818 | if ((a = BN_new()) == NULL) | ||
1819 | goto err; | ||
1820 | if ((b[0] = BN_new()) == NULL) | ||
1821 | goto err; | ||
1822 | if ((b[1] = BN_new()) == NULL) | ||
1823 | goto err; | ||
1824 | if ((c = BN_new()) == NULL) | ||
1825 | goto err; | ||
1826 | if ((d = BN_new()) == NULL) | ||
1827 | goto err; | ||
1828 | |||
1829 | CHECK_GOTO(BN_GF2m_arr2poly(p0, b[0])); | ||
1830 | CHECK_GOTO(BN_GF2m_arr2poly(p1, b[1])); | ||
1831 | |||
1832 | for (i = 0; i < num0; i++) { | ||
1833 | CHECK_GOTO(BN_bntest_rand(a, 512, 0, 0)); | ||
1834 | for (j = 0; j < 2; j++) { | ||
1835 | CHECK_GOTO(BN_GF2m_mod_inv(c, a, b[j], ctx)); | ||
1836 | CHECK_GOTO(BN_GF2m_mod_mul(d, a, c, b[j], ctx)); | ||
1837 | #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ | ||
1838 | if (bp != NULL) { | ||
1839 | if (!results) { | ||
1840 | CHECK_GOTO(BN_print(bp, a)); | ||
1841 | BIO_puts(bp, " * "); | ||
1842 | CHECK_GOTO(BN_print(bp, c)); | ||
1843 | BIO_puts(bp, " - 1 % "); | ||
1844 | CHECK_GOTO(BN_print(bp, b[j])); | ||
1845 | BIO_puts(bp, "\n"); | ||
1846 | } | ||
1847 | } | ||
1848 | #endif | ||
1849 | /* Test that ((1/a)*a) = 1. */ | ||
1850 | if (!BN_is_one(d)) { | ||
1851 | fprintf(stderr, "GF(2^m) modular inversion test failed!\n"); | ||
1852 | goto err; | ||
1853 | } | ||
1854 | } | ||
1855 | } | ||
1856 | rc = 1; | ||
1857 | err: | ||
1858 | BN_free(a); | ||
1859 | BN_free(b[0]); | ||
1860 | BN_free(b[1]); | ||
1861 | BN_free(c); | ||
1862 | BN_free(d); | ||
1863 | return rc; | ||
1864 | } | ||
1865 | |||
1866 | int | ||
1867 | test_gf2m_mod_div(BIO *bp, BN_CTX *ctx) | ||
1868 | { | ||
1869 | BIGNUM *a = NULL, *b[2] = { 0 }, *c = NULL, *d = NULL, *e = NULL, *f = NULL; | ||
1870 | int i, j, rc = 0; | ||
1871 | int p0[] = { 163, 7, 6, 3, 0, -1 }; | ||
1872 | int p1[] = { 193, 15, 0, -1 }; | ||
1873 | |||
1874 | if ((a = BN_new()) == NULL) | ||
1875 | goto err; | ||
1876 | if ((b[0] = BN_new()) == NULL) | ||
1877 | goto err; | ||
1878 | if ((b[1] = BN_new()) == NULL) | ||
1879 | goto err; | ||
1880 | if ((c = BN_new()) == NULL) | ||
1881 | goto err; | ||
1882 | if ((d = BN_new()) == NULL) | ||
1883 | goto err; | ||
1884 | if ((e = BN_new()) == NULL) | ||
1885 | goto err; | ||
1886 | if ((f = BN_new()) == NULL) | ||
1887 | goto err; | ||
1888 | |||
1889 | CHECK_GOTO(BN_GF2m_arr2poly(p0, b[0])); | ||
1890 | CHECK_GOTO(BN_GF2m_arr2poly(p1, b[1])); | ||
1891 | |||
1892 | for (i = 0; i < num0; i++) { | ||
1893 | CHECK_GOTO(BN_bntest_rand(a, 512, 0, 0)); | ||
1894 | CHECK_GOTO(BN_bntest_rand(c, 512, 0, 0)); | ||
1895 | for (j = 0; j < 2; j++) { | ||
1896 | CHECK_GOTO(BN_GF2m_mod_div(d, a, c, b[j], ctx)); | ||
1897 | CHECK_GOTO(BN_GF2m_mod_mul(e, d, c, b[j], ctx)); | ||
1898 | CHECK_GOTO(BN_GF2m_mod_div(f, a, e, b[j], ctx)); | ||
1899 | #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ | ||
1900 | if (bp != NULL) { | ||
1901 | if (!results) { | ||
1902 | CHECK_GOTO(BN_print(bp, a)); | ||
1903 | BIO_puts(bp, " = "); | ||
1904 | CHECK_GOTO(BN_print(bp, c)); | ||
1905 | BIO_puts(bp, " * "); | ||
1906 | CHECK_GOTO(BN_print(bp, d)); | ||
1907 | BIO_puts(bp, " % "); | ||
1908 | CHECK_GOTO(BN_print(bp, b[j])); | ||
1909 | BIO_puts(bp, "\n"); | ||
1910 | } | ||
1911 | } | ||
1912 | #endif | ||
1913 | /* Test that ((a/c)*c)/a = 1. */ | ||
1914 | if (!BN_is_one(f)) { | ||
1915 | fprintf(stderr, "GF(2^m) modular division test failed!\n"); | ||
1916 | goto err; | ||
1917 | } | ||
1918 | } | ||
1919 | } | ||
1920 | rc = 1; | ||
1921 | err: | ||
1922 | BN_free(a); | ||
1923 | BN_free(b[0]); | ||
1924 | BN_free(b[1]); | ||
1925 | BN_free(c); | ||
1926 | BN_free(d); | ||
1927 | BN_free(e); | ||
1928 | BN_free(f); | ||
1929 | return rc; | ||
1930 | } | ||
1931 | |||
1932 | int | ||
1933 | test_gf2m_mod_exp(BIO *bp, BN_CTX *ctx) | ||
1934 | { | ||
1935 | BIGNUM *a = NULL, *b[2] = { 0 }, *c = NULL, *d = NULL, *e = NULL, *f = NULL; | ||
1936 | int i, j, rc = 0; | ||
1937 | int p0[] = { 163, 7, 6, 3, 0, -1 }; | ||
1938 | int p1[] = { 193, 15, 0, -1 }; | ||
1939 | |||
1940 | if ((a = BN_new()) == NULL) | ||
1941 | goto err; | ||
1942 | if ((b[0] = BN_new()) == NULL) | ||
1943 | goto err; | ||
1944 | if ((b[1] = BN_new()) == NULL) | ||
1945 | goto err; | ||
1946 | if ((c = BN_new()) == NULL) | ||
1947 | goto err; | ||
1948 | if ((d = BN_new()) == NULL) | ||
1949 | goto err; | ||
1950 | if ((e = BN_new()) == NULL) | ||
1951 | goto err; | ||
1952 | if ((f = BN_new()) == NULL) | ||
1953 | goto err; | ||
1954 | |||
1955 | CHECK_GOTO(BN_GF2m_arr2poly(p0, b[0])); | ||
1956 | CHECK_GOTO(BN_GF2m_arr2poly(p1, b[1])); | ||
1957 | |||
1958 | for (i = 0; i < num0; i++) { | ||
1959 | CHECK_GOTO(BN_bntest_rand(a, 512, 0, 0)); | ||
1960 | CHECK_GOTO(BN_bntest_rand(c, 512, 0, 0)); | ||
1961 | CHECK_GOTO(BN_bntest_rand(d, 512, 0, 0)); | ||
1962 | for (j = 0; j < 2; j++) { | ||
1963 | CHECK_GOTO(BN_GF2m_mod_exp(e, a, c, b[j], ctx)); | ||
1964 | CHECK_GOTO(BN_GF2m_mod_exp(f, a, d, b[j], ctx)); | ||
1965 | CHECK_GOTO(BN_GF2m_mod_mul(e, e, f, b[j], ctx)); | ||
1966 | CHECK_GOTO(BN_add(f, c, d)); | ||
1967 | CHECK_GOTO(BN_GF2m_mod_exp(f, a, f, b[j], ctx)); | ||
1968 | #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ | ||
1969 | if (bp != NULL) { | ||
1970 | if (!results) { | ||
1971 | CHECK_GOTO(BN_print(bp, a)); | ||
1972 | BIO_puts(bp, " ^ ("); | ||
1973 | CHECK_GOTO(BN_print(bp, c)); | ||
1974 | BIO_puts(bp, " + "); | ||
1975 | CHECK_GOTO(BN_print(bp, d)); | ||
1976 | BIO_puts(bp, ") = "); | ||
1977 | CHECK_GOTO(BN_print(bp, e)); | ||
1978 | BIO_puts(bp, "; - "); | ||
1979 | CHECK_GOTO(BN_print(bp, f)); | ||
1980 | BIO_puts(bp, " % "); | ||
1981 | CHECK_GOTO(BN_print(bp, b[j])); | ||
1982 | BIO_puts(bp, "\n"); | ||
1983 | } | ||
1984 | } | ||
1985 | #endif | ||
1986 | CHECK_GOTO(BN_GF2m_add(f, e, f)); | ||
1987 | /* Test that a^(c+d)=a^c*a^d. */ | ||
1988 | if (!BN_is_zero(f)) { | ||
1989 | fprintf(stderr, "GF(2^m) modular exponentiation test failed!\n"); | ||
1990 | goto err; | ||
1991 | } | ||
1992 | } | ||
1993 | } | ||
1994 | rc = 1; | ||
1995 | err: | ||
1996 | BN_free(a); | ||
1997 | BN_free(b[0]); | ||
1998 | BN_free(b[1]); | ||
1999 | BN_free(c); | ||
2000 | BN_free(d); | ||
2001 | BN_free(e); | ||
2002 | BN_free(f); | ||
2003 | return rc; | ||
2004 | } | ||
2005 | |||
2006 | int | ||
2007 | test_gf2m_mod_sqrt(BIO *bp, BN_CTX *ctx) | ||
2008 | { | ||
2009 | BIGNUM *a = NULL, *b[2] = { 0 }, *c = NULL, *d = NULL, *e = NULL, *f = NULL; | ||
2010 | int i, j, rc = 0; | ||
2011 | int p0[] = { 163, 7, 6, 3, 0, -1 }; | ||
2012 | int p1[] = { 193, 15, 0, -1 }; | ||
2013 | |||
2014 | if ((a = BN_new()) == NULL) | ||
2015 | goto err; | ||
2016 | if ((b[0] = BN_new()) == NULL) | ||
2017 | goto err; | ||
2018 | if ((b[1] = BN_new()) == NULL) | ||
2019 | goto err; | ||
2020 | if ((c = BN_new()) == NULL) | ||
2021 | goto err; | ||
2022 | if ((d = BN_new()) == NULL) | ||
2023 | goto err; | ||
2024 | if ((e = BN_new()) == NULL) | ||
2025 | goto err; | ||
2026 | if ((f = BN_new()) == NULL) | ||
2027 | goto err; | ||
2028 | |||
2029 | CHECK_GOTO(BN_GF2m_arr2poly(p0, b[0])); | ||
2030 | CHECK_GOTO(BN_GF2m_arr2poly(p1, b[1])); | ||
2031 | |||
2032 | for (i = 0; i < num0; i++) { | ||
2033 | CHECK_GOTO(BN_bntest_rand(a, 512, 0, 0)); | ||
2034 | for (j = 0; j < 2; j++) { | ||
2035 | CHECK_GOTO(BN_GF2m_mod(c, a, b[j])); | ||
2036 | CHECK_GOTO(BN_GF2m_mod_sqrt(d, a, b[j], ctx)); | ||
2037 | CHECK_GOTO(BN_GF2m_mod_sqr(e, d, b[j], ctx)); | ||
2038 | #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ | ||
2039 | if (bp != NULL) { | ||
2040 | if (!results) { | ||
2041 | CHECK_GOTO(BN_print(bp, d)); | ||
2042 | BIO_puts(bp, " ^ 2 - "); | ||
2043 | CHECK_GOTO(BN_print(bp, a)); | ||
2044 | BIO_puts(bp, "\n"); | ||
2045 | } | ||
2046 | } | ||
2047 | #endif | ||
2048 | CHECK_GOTO(BN_GF2m_add(f, c, e)); | ||
2049 | /* Test that d^2 = a, where d = sqrt(a). */ | ||
2050 | if (!BN_is_zero(f)) { | ||
2051 | fprintf(stderr, "GF(2^m) modular square root test failed!\n"); | ||
2052 | goto err; | ||
2053 | } | ||
2054 | } | ||
2055 | } | ||
2056 | rc = 1; | ||
2057 | err: | ||
2058 | BN_free(a); | ||
2059 | BN_free(b[0]); | ||
2060 | BN_free(b[1]); | ||
2061 | BN_free(c); | ||
2062 | BN_free(d); | ||
2063 | BN_free(e); | ||
2064 | BN_free(f); | ||
2065 | return rc; | ||
2066 | } | ||
2067 | |||
2068 | int | ||
2069 | test_gf2m_mod_solve_quad(BIO *bp, BN_CTX *ctx) | ||
2070 | { | ||
2071 | BIGNUM *a = NULL, *b[2] = { 0 }, *c = NULL, *d = NULL, *e = NULL; | ||
2072 | int i, j, s = 0, t, rc = 0; | ||
2073 | int p0[] = { 163, 7, 6, 3, 0, -1 }; | ||
2074 | int p1[] = { 193, 15, 0, -1 }; | ||
2075 | |||
2076 | if ((a = BN_new()) == NULL) | ||
2077 | goto err; | ||
2078 | if ((b[0] = BN_new()) == NULL) | ||
2079 | goto err; | ||
2080 | if ((b[1] = BN_new()) == NULL) | ||
2081 | goto err; | ||
2082 | if ((c = BN_new()) == NULL) | ||
2083 | goto err; | ||
2084 | if ((d = BN_new()) == NULL) | ||
2085 | goto err; | ||
2086 | if ((e = BN_new()) == NULL) | ||
2087 | goto err; | ||
2088 | |||
2089 | CHECK_GOTO(BN_GF2m_arr2poly(p0, b[0])); | ||
2090 | CHECK_GOTO(BN_GF2m_arr2poly(p1, b[1])); | ||
2091 | |||
2092 | for (i = 0; i < num0; i++) { | ||
2093 | CHECK_GOTO(BN_bntest_rand(a, 512, 0, 0)); | ||
2094 | for (j = 0; j < 2; j++) { | ||
2095 | t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx); | ||
2096 | if (t) { | ||
2097 | s++; | ||
2098 | CHECK_GOTO(BN_GF2m_mod_sqr(d, c, b[j], ctx)); | ||
2099 | CHECK_GOTO(BN_GF2m_add(d, c, d)); | ||
2100 | CHECK_GOTO(BN_GF2m_mod(e, a, b[j])); | ||
2101 | #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ | ||
2102 | if (bp != NULL) { | ||
2103 | if (!results) { | ||
2104 | CHECK_GOTO(BN_print(bp, c)); | ||
2105 | BIO_puts(bp, " is root of z^2 + z = "); | ||
2106 | CHECK_GOTO(BN_print(bp, a)); | ||
2107 | BIO_puts(bp, " % "); | ||
2108 | CHECK_GOTO(BN_print(bp, b[j])); | ||
2109 | BIO_puts(bp, "\n"); | ||
2110 | } | ||
2111 | } | ||
2112 | #endif | ||
2113 | CHECK_GOTO(BN_GF2m_add(e, e, d)); | ||
2114 | /* Test that solution of quadratic c satisfies c^2 + c = a. */ | ||
2115 | if (!BN_is_zero(e)) { | ||
2116 | fprintf(stderr, "GF(2^m) modular solve quadratic test failed!\n"); | ||
2117 | goto err; | ||
2118 | } | ||
2119 | |||
2120 | } else { | ||
2121 | #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ | ||
2122 | if (bp != NULL) { | ||
2123 | if (!results) { | ||
2124 | BIO_puts(bp, "There are no roots of z^2 + z = "); | ||
2125 | CHECK_GOTO(BN_print(bp, a)); | ||
2126 | BIO_puts(bp, " % "); | ||
2127 | CHECK_GOTO(BN_print(bp, b[j])); | ||
2128 | BIO_puts(bp, "\n"); | ||
2129 | } | ||
2130 | } | ||
2131 | #endif | ||
2132 | } | ||
2133 | } | ||
2134 | } | ||
2135 | if (s == 0) { | ||
2136 | fprintf(stderr, "All %d tests of GF(2^m) modular solve quadratic resulted in no roots;\n", num0); | ||
2137 | fprintf(stderr, "this is very unlikely and probably indicates an error.\n"); | ||
2138 | goto err; | ||
2139 | } | ||
2140 | rc = 1; | ||
2141 | err: | ||
2142 | BN_free(a); | ||
2143 | BN_free(b[0]); | ||
2144 | BN_free(b[1]); | ||
2145 | BN_free(c); | ||
2146 | BN_free(d); | ||
2147 | BN_free(e); | ||
2148 | return rc; | ||
2149 | } | ||
2150 | #endif | ||
2151 | static int | ||
2152 | genprime_cb(int p, int n, BN_GENCB *arg) | ||
2153 | { | ||
2154 | char c = '*'; | ||
2155 | |||
2156 | if (p == 0) | ||
2157 | c = '.'; | ||
2158 | if (p == 1) | ||
2159 | c = '+'; | ||
2160 | if (p == 2) | ||
2161 | c = '*'; | ||
2162 | if (p == 3) | ||
2163 | c = '\n'; | ||
2164 | putc(c, stderr); | ||
2165 | return (1); | ||
2166 | } | ||
2167 | |||
2168 | int | ||
2169 | test_kron(BIO *bp, BN_CTX *ctx) | ||
2170 | { | ||
2171 | BIGNUM *a = NULL, *b = NULL, *r = NULL, *t = NULL; | ||
2172 | BN_GENCB *cb = NULL; | ||
2173 | int i; | ||
2174 | int legendre, kronecker; | ||
2175 | int rc = 0; | ||
2176 | |||
2177 | if ((a = BN_new()) == NULL) | ||
2178 | goto err; | ||
2179 | if ((b = BN_new()) == NULL) | ||
2180 | goto err; | ||
2181 | if ((r = BN_new()) == NULL) | ||
2182 | goto err; | ||
2183 | if ((t = BN_new()) == NULL) | ||
2184 | goto err; | ||
2185 | |||
2186 | if ((cb = BN_GENCB_new()) == NULL) | ||
2187 | goto err; | ||
2188 | |||
2189 | BN_GENCB_set(cb, genprime_cb, NULL); | ||
2190 | |||
2191 | /* | ||
2192 | * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In | ||
2193 | * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is | ||
2194 | * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we | ||
2195 | * generate a random prime b and compare these values for a number of | ||
2196 | * random a's. (That is, we run the Solovay-Strassen primality test to | ||
2197 | * confirm that b is prime, except that we don't want to test whether b | ||
2198 | * is prime but whether BN_kronecker works.) | ||
2199 | */ | ||
2200 | |||
2201 | if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, cb)) | ||
2202 | goto err; | ||
2203 | BN_set_negative(b, rand_neg()); | ||
2204 | putc('\n', stderr); | ||
2205 | |||
2206 | for (i = 0; i < num0; i++) { | ||
2207 | if (!BN_bntest_rand(a, 512, 0, 0)) | ||
2208 | goto err; | ||
2209 | BN_set_negative(a, rand_neg()); | ||
2210 | |||
2211 | /* t := (|b|-1)/2 (note that b is odd) */ | ||
2212 | if (!BN_copy(t, b)) | ||
2213 | goto err; | ||
2214 | BN_set_negative(t, 0); | ||
2215 | if (!BN_sub_word(t, 1)) | ||
2216 | goto err; | ||
2217 | if (!BN_rshift1(t, t)) | ||
2218 | goto err; | ||
2219 | /* r := a^t mod b */ | ||
2220 | BN_set_negative(b, 0); | ||
2221 | |||
2222 | if (!BN_mod_exp_recp(r, a, t, b, ctx)) | ||
2223 | goto err; | ||
2224 | BN_set_negative(b, 1); | ||
2225 | |||
2226 | if (BN_is_word(r, 1)) | ||
2227 | legendre = 1; | ||
2228 | else if (BN_is_zero(r)) | ||
2229 | legendre = 0; | ||
2230 | else { | ||
2231 | if (!BN_add_word(r, 1)) | ||
2232 | goto err; | ||
2233 | if (0 != BN_ucmp(r, b)) { | ||
2234 | fprintf(stderr, "Legendre symbol computation failed\n"); | ||
2235 | goto err; | ||
2236 | } | ||
2237 | legendre = -1; | ||
2238 | } | ||
2239 | |||
2240 | kronecker = BN_kronecker(a, b, ctx); | ||
2241 | if (kronecker < -1) | ||
2242 | goto err; | ||
2243 | /* we actually need BN_kronecker(a, |b|) */ | ||
2244 | if (BN_is_negative(a) && BN_is_negative(b)) | ||
2245 | kronecker = -kronecker; | ||
2246 | |||
2247 | if (legendre != kronecker) { | ||
2248 | fprintf(stderr, "legendre != kronecker; a = "); | ||
2249 | CHECK_GOTO(BN_print_fp(stderr, a)); | ||
2250 | fprintf(stderr, ", b = "); | ||
2251 | CHECK_GOTO(BN_print_fp(stderr, b)); | ||
2252 | fprintf(stderr, "\n"); | ||
2253 | goto err; | ||
2254 | } | ||
2255 | |||
2256 | putc('.', stderr); | ||
2257 | } | ||
2258 | |||
2259 | putc('\n', stderr); | ||
2260 | rc = 1; | ||
2261 | |||
2262 | err: | ||
2263 | BN_GENCB_free(cb); | ||
2264 | BN_free(a); | ||
2265 | BN_free(b); | ||
2266 | BN_free(r); | ||
2267 | BN_free(t); | ||
2268 | return rc; | ||
2269 | } | ||
2270 | |||
2271 | int | ||
2272 | test_sqrt(BIO *bp, BN_CTX *ctx) | ||
2273 | { | ||
2274 | BIGNUM *a = NULL, *p = NULL, *r = NULL; | ||
2275 | BN_GENCB *cb = NULL; | ||
2276 | int i, j; | ||
2277 | int rc = 0; | ||
2278 | |||
2279 | if ((a = BN_new()) == NULL) | ||
2280 | goto err; | ||
2281 | if ((p = BN_new()) == NULL) | ||
2282 | goto err; | ||
2283 | if ((r = BN_new()) == NULL) | ||
2284 | goto err; | ||
2285 | |||
2286 | if ((cb = BN_GENCB_new()) == NULL) | ||
2287 | goto err; | ||
2288 | |||
2289 | BN_GENCB_set(cb, genprime_cb, NULL); | ||
2290 | |||
2291 | for (i = 0; i < 16; i++) { | ||
2292 | if (i < 8) { | ||
2293 | unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 }; | ||
2294 | |||
2295 | if (!BN_set_word(p, primes[i])) | ||
2296 | goto err; | ||
2297 | } else { | ||
2298 | if (!BN_set_word(a, 32)) | ||
2299 | goto err; | ||
2300 | if (!BN_set_word(r, 2 * i + 1)) | ||
2301 | goto err; | ||
2302 | |||
2303 | if (!BN_generate_prime_ex(p, 256, 0, a, r, cb)) | ||
2304 | goto err; | ||
2305 | putc('\n', stderr); | ||
2306 | } | ||
2307 | BN_set_negative(p, rand_neg()); | ||
2308 | |||
2309 | for (j = 0; j < num2; j++) { | ||
2310 | /* | ||
2311 | * construct 'a' such that it is a square modulo p, but in | ||
2312 | * general not a proper square and not reduced modulo p | ||
2313 | */ | ||
2314 | if (!BN_bntest_rand(r, 256, 0, 3)) | ||
2315 | goto err; | ||
2316 | if (!BN_nnmod(r, r, p, ctx)) | ||
2317 | goto err; | ||
2318 | if (!BN_mod_sqr(r, r, p, ctx)) | ||
2319 | goto err; | ||
2320 | if (!BN_bntest_rand(a, 256, 0, 3)) | ||
2321 | goto err; | ||
2322 | if (!BN_nnmod(a, a, p, ctx)) | ||
2323 | goto err; | ||
2324 | if (!BN_mod_sqr(a, a, p, ctx)) | ||
2325 | goto err; | ||
2326 | if (!BN_mul(a, a, r, ctx)) | ||
2327 | goto err; | ||
2328 | if (rand_neg()) | ||
2329 | if (!BN_sub(a, a, p)) | ||
2330 | goto err; | ||
2331 | |||
2332 | if (!BN_mod_sqrt(r, a, p, ctx)) | ||
2333 | goto err; | ||
2334 | if (!BN_mod_sqr(r, r, p, ctx)) | ||
2335 | goto err; | ||
2336 | |||
2337 | if (!BN_nnmod(a, a, p, ctx)) | ||
2338 | goto err; | ||
2339 | |||
2340 | if (BN_cmp(a, r) != 0) { | ||
2341 | fprintf(stderr, "BN_mod_sqrt failed: a = "); | ||
2342 | CHECK_GOTO(BN_print_fp(stderr, a)); | ||
2343 | fprintf(stderr, ", r = "); | ||
2344 | CHECK_GOTO(BN_print_fp(stderr, r)); | ||
2345 | fprintf(stderr, ", p = "); | ||
2346 | CHECK_GOTO(BN_print_fp(stderr, p)); | ||
2347 | fprintf(stderr, "\n"); | ||
2348 | goto err; | ||
2349 | } | ||
2350 | |||
2351 | putc('.', stderr); | ||
2352 | } | ||
2353 | |||
2354 | putc('\n', stderr); | ||
2355 | } | ||
2356 | rc = 1; | ||
2357 | |||
2358 | err: | ||
2359 | BN_GENCB_free(cb); | ||
2360 | BN_free(a); | ||
2361 | BN_free(p); | ||
2362 | BN_free(r); | ||
2363 | return rc; | ||
2364 | } | ||
2365 | |||
2366 | int | ||
2367 | test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_) | ||
2368 | { | ||
2369 | BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL; | ||
2370 | int i; | ||
2371 | int rc = 1; | ||
2372 | |||
2373 | if ((b = BN_new()) == NULL) | ||
2374 | goto err; | ||
2375 | if ((c = BN_new()) == NULL) | ||
2376 | goto err; | ||
2377 | if ((d = BN_new()) == NULL) | ||
2378 | goto err; | ||
2379 | CHECK_GOTO(BN_one(c)); | ||
2380 | |||
2381 | if (a_) | ||
2382 | a = a_; | ||
2383 | else { | ||
2384 | if ((a = BN_new()) == NULL) | ||
2385 | goto err; | ||
2386 | CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0)); | ||
2387 | BN_set_negative(a, rand_neg()); | ||
2388 | } | ||
2389 | for (i = 0; i < num0; i++) { | ||
2390 | CHECK_GOTO(BN_lshift(b, a, i + 1)); | ||
2391 | CHECK_GOTO(BN_add(c, c, c)); | ||
2392 | if (bp != NULL) { | ||
2393 | if (!results) { | ||
2394 | CHECK_GOTO(BN_print(bp, a)); | ||
2395 | BIO_puts(bp, " * "); | ||
2396 | CHECK_GOTO(BN_print(bp, c)); | ||
2397 | BIO_puts(bp, " - "); | ||
2398 | } | ||
2399 | CHECK_GOTO(BN_print(bp, b)); | ||
2400 | BIO_puts(bp, "\n"); | ||
2401 | } | ||
2402 | CHECK_GOTO(BN_mul(d, a, c, ctx)); | ||
2403 | CHECK_GOTO(BN_sub(d, d, b)); | ||
2404 | if (!BN_is_zero(d)) { | ||
2405 | fprintf(stderr, "Left shift test failed!\n"); | ||
2406 | fprintf(stderr, "a="); | ||
2407 | CHECK_GOTO(BN_print_fp(stderr, a)); | ||
2408 | fprintf(stderr, "\nb="); | ||
2409 | CHECK_GOTO(BN_print_fp(stderr, b)); | ||
2410 | fprintf(stderr, "\nc="); | ||
2411 | CHECK_GOTO(BN_print_fp(stderr, c)); | ||
2412 | fprintf(stderr, "\nd="); | ||
2413 | CHECK_GOTO(BN_print_fp(stderr, d)); | ||
2414 | fprintf(stderr, "\n"); | ||
2415 | rc = 0; | ||
2416 | break; | ||
2417 | } | ||
2418 | } | ||
2419 | err: | ||
2420 | BN_free(a); | ||
2421 | BN_free(b); | ||
2422 | BN_free(c); | ||
2423 | BN_free(d); | ||
2424 | return (rc); | ||
2425 | } | ||
2426 | |||
2427 | int | ||
2428 | test_lshift1(BIO *bp) | ||
2429 | { | ||
2430 | BIGNUM *a = NULL, *b = NULL, *c = NULL; | ||
2431 | int i; | ||
2432 | int rc = 1; | ||
2433 | |||
2434 | if ((a = BN_new()) == NULL) | ||
2435 | goto err; | ||
2436 | if ((b = BN_new()) == NULL) | ||
2437 | goto err; | ||
2438 | if ((c = BN_new()) == NULL) | ||
2439 | goto err; | ||
2440 | |||
2441 | CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0)); | ||
2442 | BN_set_negative(a, rand_neg()); | ||
2443 | for (i = 0; i < num0; i++) { | ||
2444 | CHECK_GOTO(BN_lshift1(b, a)); | ||
2445 | if (bp != NULL) { | ||
2446 | if (!results) { | ||
2447 | CHECK_GOTO(BN_print(bp, a)); | ||
2448 | BIO_puts(bp, " * 2"); | ||
2449 | BIO_puts(bp, " - "); | ||
2450 | } | ||
2451 | CHECK_GOTO(BN_print(bp, b)); | ||
2452 | BIO_puts(bp, "\n"); | ||
2453 | } | ||
2454 | CHECK_GOTO(BN_add(c, a, a)); | ||
2455 | CHECK_GOTO(BN_sub(a, b, c)); | ||
2456 | if (!BN_is_zero(a)) { | ||
2457 | fprintf(stderr, "Left shift one test failed!\n"); | ||
2458 | rc = 0; | ||
2459 | break; | ||
2460 | } | ||
2461 | |||
2462 | CHECK_GOTO(BN_copy(a, b)); | ||
2463 | } | ||
2464 | err: | ||
2465 | BN_free(a); | ||
2466 | BN_free(b); | ||
2467 | BN_free(c); | ||
2468 | return (rc); | ||
2469 | } | ||
2470 | |||
2471 | int | ||
2472 | test_rshift(BIO *bp, BN_CTX *ctx) | ||
2473 | { | ||
2474 | BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL; | ||
2475 | int i; | ||
2476 | int rc = 1; | ||
2477 | |||
2478 | if ((a = BN_new()) == NULL) | ||
2479 | goto err; | ||
2480 | if ((b = BN_new()) == NULL) | ||
2481 | goto err; | ||
2482 | if ((c = BN_new()) == NULL) | ||
2483 | goto err; | ||
2484 | if ((d = BN_new()) == NULL) | ||
2485 | goto err; | ||
2486 | if ((e = BN_new()) == NULL) | ||
2487 | goto err; | ||
2488 | CHECK_GOTO(BN_one(c)); | ||
2489 | |||
2490 | CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0)); | ||
2491 | BN_set_negative(a, rand_neg()); | ||
2492 | for (i = 0; i < num0; i++) { | ||
2493 | CHECK_GOTO(BN_rshift(b, a, i + 1)); | ||
2494 | CHECK_GOTO(BN_add(c, c, c)); | ||
2495 | if (bp != NULL) { | ||
2496 | if (!results) { | ||
2497 | CHECK_GOTO(BN_print(bp, a)); | ||
2498 | BIO_puts(bp, " / "); | ||
2499 | CHECK_GOTO(BN_print(bp, c)); | ||
2500 | BIO_puts(bp, " - "); | ||
2501 | } | ||
2502 | CHECK_GOTO(BN_print(bp, b)); | ||
2503 | BIO_puts(bp, "\n"); | ||
2504 | } | ||
2505 | CHECK_GOTO(BN_div(d, e, a, c, ctx)); | ||
2506 | CHECK_GOTO(BN_sub(d, d, b)); | ||
2507 | if (!BN_is_zero(d)) { | ||
2508 | fprintf(stderr, "Right shift test failed!\n"); | ||
2509 | rc = 0; | ||
2510 | break; | ||
2511 | } | ||
2512 | } | ||
2513 | err: | ||
2514 | BN_free(a); | ||
2515 | BN_free(b); | ||
2516 | BN_free(c); | ||
2517 | BN_free(d); | ||
2518 | BN_free(e); | ||
2519 | return (rc); | ||
2520 | } | ||
2521 | |||
2522 | int | ||
2523 | test_rshift1(BIO *bp) | ||
2524 | { | ||
2525 | BIGNUM *a = NULL, *b = NULL, *c = NULL; | ||
2526 | int i; | ||
2527 | int rc = 1; | ||
2528 | |||
2529 | if ((a = BN_new()) == NULL) | ||
2530 | goto err; | ||
2531 | if ((b = BN_new()) == NULL) | ||
2532 | goto err; | ||
2533 | if ((c = BN_new()) == NULL) | ||
2534 | goto err; | ||
2535 | |||
2536 | CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0)); | ||
2537 | BN_set_negative(a, rand_neg()); | ||
2538 | for (i = 0; i < num0; i++) { | ||
2539 | CHECK_GOTO(BN_rshift1(b, a)); | ||
2540 | if (bp != NULL) { | ||
2541 | if (!results) { | ||
2542 | CHECK_GOTO(BN_print(bp, a)); | ||
2543 | BIO_puts(bp, " / 2"); | ||
2544 | BIO_puts(bp, " - "); | ||
2545 | } | ||
2546 | CHECK_GOTO(BN_print(bp, b)); | ||
2547 | BIO_puts(bp, "\n"); | ||
2548 | } | ||
2549 | CHECK_GOTO(BN_sub(c, a, b)); | ||
2550 | CHECK_GOTO(BN_sub(c, c, b)); | ||
2551 | if (!BN_is_zero(c) && !BN_abs_is_word(c, 1)) { | ||
2552 | fprintf(stderr, "Right shift one test failed!\n"); | ||
2553 | rc = 0; | ||
2554 | break; | ||
2555 | } | ||
2556 | CHECK_GOTO(BN_copy(a, b)); | ||
2557 | } | ||
2558 | err: | ||
2559 | BN_free(a); | ||
2560 | BN_free(b); | ||
2561 | BN_free(c); | ||
2562 | return (rc); | ||
2563 | } | ||
2564 | |||
2565 | int | ||
2566 | rand_neg(void) | ||
2567 | { | ||
2568 | static unsigned int neg = 0; | ||
2569 | static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 }; | ||
2570 | |||
2571 | return (sign[(neg++) % 8]); | ||
2572 | } | ||
2573 | |||
2574 | int | ||
2575 | test_mod_exp_sizes(BIO *bp, BN_CTX *ctx) | ||
2576 | { | ||
2577 | BN_MONT_CTX *mont_ctx = NULL; | ||
2578 | BIGNUM *p = NULL, *x = NULL, *y = NULL, *r = NULL, *r2 = NULL; | ||
2579 | int size; | ||
2580 | int rc = 0; | ||
2581 | |||
2582 | BN_CTX_start(ctx); | ||
2583 | CHECK_GOTO(p = BN_CTX_get(ctx)); | ||
2584 | CHECK_GOTO(x = BN_CTX_get(ctx)); | ||
2585 | CHECK_GOTO(y = BN_CTX_get(ctx)); | ||
2586 | CHECK_GOTO(r = BN_CTX_get(ctx)); | ||
2587 | CHECK_GOTO(r2 = BN_CTX_get(ctx)); | ||
2588 | mont_ctx = BN_MONT_CTX_new(); | ||
2589 | |||
2590 | if (r2 == NULL || mont_ctx == NULL) | ||
2591 | goto err; | ||
2592 | |||
2593 | if (!BN_generate_prime_ex(p, 32, 0, NULL, NULL, NULL) || | ||
2594 | !BN_MONT_CTX_set(mont_ctx, p, ctx)) | ||
2595 | goto err; | ||
2596 | |||
2597 | for (size = 32; size < 1024; size += 8) { | ||
2598 | if (!BN_rand(x, size, -1, 0) || | ||
2599 | !BN_rand(y, size, -1, 0) || | ||
2600 | !BN_mod_exp_mont_consttime(r, x, y, p, ctx, mont_ctx) || | ||
2601 | !BN_mod_exp(r2, x, y, p, ctx)) | ||
2602 | goto err; | ||
2603 | |||
2604 | if (BN_cmp(r, r2) != 0) { | ||
2605 | char *r_str = NULL; | ||
2606 | char *r2_str = NULL; | ||
2607 | CHECK_GOTO(r_str = BN_bn2hex(r)); | ||
2608 | CHECK_GOTO(r2_str = BN_bn2hex(r2)); | ||
2609 | |||
2610 | printf("Incorrect answer at size %d: %s vs %s\n", | ||
2611 | size, r_str, r2_str); | ||
2612 | free(r_str); | ||
2613 | free(r2_str); | ||
2614 | goto err; | ||
2615 | } | ||
2616 | } | ||
2617 | |||
2618 | rc = 1; | ||
2619 | |||
2620 | err: | ||
2621 | BN_MONT_CTX_free(mont_ctx); | ||
2622 | BN_CTX_end(ctx); | ||
2623 | return rc; | ||
2624 | } | ||