]>
Commit | Line | Data |
---|---|---|
d02b48c6 | 1 | /* crypto/bn/bntest.c */ |
58964a49 | 2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) |
d02b48c6 RE |
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. | |
0f113f3e | 8 | * |
d02b48c6 RE |
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). | |
0f113f3e | 15 | * |
d02b48c6 RE |
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. | |
0f113f3e | 22 | * |
d02b48c6 RE |
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 :-). | |
0f113f3e | 37 | * 4. If you include any Windows specific code (or a derivative thereof) from |
d02b48c6 RE |
38 | * the apps directory (application code) you must include an acknowledgement: |
39 | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" | |
0f113f3e | 40 | * |
d02b48c6 RE |
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. | |
0f113f3e | 52 | * |
d02b48c6 RE |
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 | */ | |
1dc920c8 BM |
58 | /* ==================================================================== |
59 | * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. | |
60 | * | |
0f113f3e | 61 | * Portions of the attached software ("Contribution") are developed by |
1dc920c8 BM |
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 | * | |
0f113f3e | 67 | * The binary polynomial arithmetic software is originally written by |
1dc920c8 BM |
68 | * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems Laboratories. |
69 | * | |
70 | */ | |
d02b48c6 RE |
71 | |
72 | #include <stdio.h> | |
73 | #include <stdlib.h> | |
74 | #include <string.h> | |
17e3dd1c | 75 | |
41d2a336 | 76 | #include "e_os.h" |
17e3dd1c | 77 | |
ec577822 BM |
78 | #include <openssl/bio.h> |
79 | #include <openssl/bn.h> | |
80 | #include <openssl/rand.h> | |
81 | #include <openssl/x509.h> | |
82 | #include <openssl/err.h> | |
d02b48c6 | 83 | |
8927c278 FLM |
84 | #include "../crypto/bn/bn_lcl.h" |
85 | ||
df2ee0e2 BL |
86 | static const int num0 = 100; /* number of tests */ |
87 | static const int num1 = 50; /* additional tests for some functions */ | |
88 | static const int num2 = 5; /* number of tests for slow functions */ | |
cae55bfc | 89 | |
dfeab068 RE |
90 | int test_add(BIO *bp); |
91 | int test_sub(BIO *bp); | |
92 | int test_lshift1(BIO *bp); | |
0f113f3e | 93 | int test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_); |
dfeab068 | 94 | int test_rshift1(BIO *bp); |
0f113f3e MC |
95 | int test_rshift(BIO *bp, BN_CTX *ctx); |
96 | int test_div(BIO *bp, BN_CTX *ctx); | |
cf9056cf | 97 | int test_div_word(BIO *bp); |
0f113f3e | 98 | int test_div_recp(BIO *bp, BN_CTX *ctx); |
dfeab068 | 99 | int test_mul(BIO *bp); |
0f113f3e MC |
100 | int test_sqr(BIO *bp, BN_CTX *ctx); |
101 | int test_mont(BIO *bp, BN_CTX *ctx); | |
102 | int test_mod(BIO *bp, BN_CTX *ctx); | |
103 | int test_mod_mul(BIO *bp, BN_CTX *ctx); | |
104 | int test_mod_exp(BIO *bp, BN_CTX *ctx); | |
105 | int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx); | |
cdfe0fdd | 106 | int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx); |
0f113f3e | 107 | int test_exp(BIO *bp, BN_CTX *ctx); |
1dc920c8 BM |
108 | int test_gf2m_add(BIO *bp); |
109 | int test_gf2m_mod(BIO *bp); | |
0f113f3e MC |
110 | int test_gf2m_mod_mul(BIO *bp, BN_CTX *ctx); |
111 | int test_gf2m_mod_sqr(BIO *bp, BN_CTX *ctx); | |
112 | int test_gf2m_mod_inv(BIO *bp, BN_CTX *ctx); | |
113 | int test_gf2m_mod_div(BIO *bp, BN_CTX *ctx); | |
114 | int test_gf2m_mod_exp(BIO *bp, BN_CTX *ctx); | |
115 | int test_gf2m_mod_sqrt(BIO *bp, BN_CTX *ctx); | |
116 | int test_gf2m_mod_solve_quad(BIO *bp, BN_CTX *ctx); | |
117 | int test_kron(BIO *bp, BN_CTX *ctx); | |
118 | int test_sqrt(BIO *bp, BN_CTX *ctx); | |
119 | int test_small_prime(BIO *bp, BN_CTX *ctx); | |
120 | int test_probable_prime_coprime(BIO *bp, BN_CTX *ctx); | |
d02b48c6 | 121 | int rand_neg(void); |
0f113f3e | 122 | static int results = 0; |
d02b48c6 | 123 | |
0f113f3e MC |
124 | static unsigned char lst[] = |
125 | "\xC6\x4F\x43\x04\x2A\xEA\xCA\x6E\x58\x36\x80\x5B\xE8\xC9" | |
126 | "\x9B\x04\x5D\x48\x36\xC2\xFD\x16\xC9\x64\xF0"; | |
4da88a8d | 127 | |
0f113f3e MC |
128 | static const char rnd_seed[] = |
129 | "string to make the random number generator think it has entropy"; | |
0c50e02b | 130 | |
667ac4ec | 131 | static void message(BIO *out, char *m) |
0f113f3e MC |
132 | { |
133 | fprintf(stderr, "test %s\n", m); | |
134 | BIO_puts(out, "print \"test "); | |
135 | BIO_puts(out, m); | |
136 | BIO_puts(out, "\\n\"\n"); | |
137 | } | |
cae55bfc | 138 | |
6b691a5c | 139 | int main(int argc, char *argv[]) |
0f113f3e MC |
140 | { |
141 | BN_CTX *ctx; | |
142 | BIO *out; | |
143 | char *outfile = NULL; | |
144 | ||
145 | results = 0; | |
146 | ||
147 | RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_generate_prime may fail */ | |
148 | ||
149 | argc--; | |
150 | argv++; | |
151 | while (argc >= 1) { | |
152 | if (strcmp(*argv, "-results") == 0) | |
153 | results = 1; | |
154 | else if (strcmp(*argv, "-out") == 0) { | |
155 | if (--argc < 1) | |
156 | break; | |
157 | outfile = *(++argv); | |
158 | } | |
159 | argc--; | |
160 | argv++; | |
161 | } | |
162 | ||
163 | ctx = BN_CTX_new(); | |
164 | if (ctx == NULL) | |
165 | EXIT(1); | |
166 | ||
167 | out = BIO_new(BIO_s_file()); | |
168 | if (out == NULL) | |
169 | EXIT(1); | |
170 | if (outfile == NULL) { | |
0f81f5f7 | 171 | BIO_set_fp(out, stdout, BIO_NOCLOSE | BIO_FP_TEXT); |
0f113f3e MC |
172 | } else { |
173 | if (!BIO_write_filename(out, outfile)) { | |
174 | perror(outfile); | |
175 | EXIT(1); | |
176 | } | |
177 | } | |
ca904707 RL |
178 | #ifdef OPENSSL_SYS_VMS |
179 | { | |
180 | BIO *tmpbio = BIO_new(BIO_f_linebuffer()); | |
181 | out = BIO_push(tmpbio, out); | |
182 | } | |
183 | #endif | |
0f113f3e MC |
184 | |
185 | if (!results) | |
186 | BIO_puts(out, "obase=16\nibase=16\n"); | |
187 | ||
188 | message(out, "BN_add"); | |
189 | if (!test_add(out)) | |
190 | goto err; | |
191 | (void)BIO_flush(out); | |
192 | ||
193 | message(out, "BN_sub"); | |
194 | if (!test_sub(out)) | |
195 | goto err; | |
196 | (void)BIO_flush(out); | |
197 | ||
198 | message(out, "BN_lshift1"); | |
199 | if (!test_lshift1(out)) | |
200 | goto err; | |
201 | (void)BIO_flush(out); | |
202 | ||
203 | message(out, "BN_lshift (fixed)"); | |
204 | if (!test_lshift(out, ctx, BN_bin2bn(lst, sizeof(lst) - 1, NULL))) | |
205 | goto err; | |
206 | (void)BIO_flush(out); | |
207 | ||
208 | message(out, "BN_lshift"); | |
209 | if (!test_lshift(out, ctx, NULL)) | |
210 | goto err; | |
211 | (void)BIO_flush(out); | |
212 | ||
213 | message(out, "BN_rshift1"); | |
214 | if (!test_rshift1(out)) | |
215 | goto err; | |
216 | (void)BIO_flush(out); | |
217 | ||
218 | message(out, "BN_rshift"); | |
219 | if (!test_rshift(out, ctx)) | |
220 | goto err; | |
221 | (void)BIO_flush(out); | |
222 | ||
223 | message(out, "BN_sqr"); | |
224 | if (!test_sqr(out, ctx)) | |
225 | goto err; | |
226 | (void)BIO_flush(out); | |
227 | ||
228 | message(out, "BN_mul"); | |
229 | if (!test_mul(out)) | |
230 | goto err; | |
231 | (void)BIO_flush(out); | |
232 | ||
233 | message(out, "BN_div"); | |
234 | if (!test_div(out, ctx)) | |
235 | goto err; | |
236 | (void)BIO_flush(out); | |
237 | ||
238 | message(out, "BN_div_word"); | |
239 | if (!test_div_word(out)) | |
240 | goto err; | |
241 | (void)BIO_flush(out); | |
242 | ||
243 | message(out, "BN_div_recp"); | |
244 | if (!test_div_recp(out, ctx)) | |
245 | goto err; | |
246 | (void)BIO_flush(out); | |
247 | ||
248 | message(out, "BN_mod"); | |
249 | if (!test_mod(out, ctx)) | |
250 | goto err; | |
251 | (void)BIO_flush(out); | |
252 | ||
253 | message(out, "BN_mod_mul"); | |
254 | if (!test_mod_mul(out, ctx)) | |
255 | goto err; | |
256 | (void)BIO_flush(out); | |
257 | ||
258 | message(out, "BN_mont"); | |
259 | if (!test_mont(out, ctx)) | |
260 | goto err; | |
261 | (void)BIO_flush(out); | |
262 | ||
263 | message(out, "BN_mod_exp"); | |
264 | if (!test_mod_exp(out, ctx)) | |
265 | goto err; | |
266 | (void)BIO_flush(out); | |
267 | ||
268 | message(out, "BN_mod_exp_mont_consttime"); | |
269 | if (!test_mod_exp_mont_consttime(out, ctx)) | |
270 | goto err; | |
271 | if (!test_mod_exp_mont5(out, ctx)) | |
272 | goto err; | |
273 | (void)BIO_flush(out); | |
274 | ||
275 | message(out, "BN_exp"); | |
276 | if (!test_exp(out, ctx)) | |
277 | goto err; | |
278 | (void)BIO_flush(out); | |
279 | ||
280 | message(out, "BN_kronecker"); | |
281 | if (!test_kron(out, ctx)) | |
282 | goto err; | |
283 | (void)BIO_flush(out); | |
284 | ||
285 | message(out, "BN_mod_sqrt"); | |
286 | if (!test_sqrt(out, ctx)) | |
287 | goto err; | |
288 | (void)BIO_flush(out); | |
289 | ||
290 | message(out, "Small prime generation"); | |
291 | if (!test_small_prime(out, ctx)) | |
292 | goto err; | |
293 | (void)BIO_flush(out); | |
96a4c31b | 294 | |
ecb9966e | 295 | #ifdef OPENSSL_SYS_WIN32 |
0f113f3e | 296 | message(out, "Probable prime generation with coprimes disabled"); |
ecb9966e | 297 | #else |
0f113f3e MC |
298 | message(out, "Probable prime generation with coprimes"); |
299 | if (!test_probable_prime_coprime(out, ctx)) | |
300 | goto err; | |
ecb9966e | 301 | #endif |
0f113f3e | 302 | (void)BIO_flush(out); |
8927c278 | 303 | |
b3310161 | 304 | #ifndef OPENSSL_NO_EC2M |
0f113f3e MC |
305 | message(out, "BN_GF2m_add"); |
306 | if (!test_gf2m_add(out)) | |
307 | goto err; | |
308 | (void)BIO_flush(out); | |
309 | ||
310 | message(out, "BN_GF2m_mod"); | |
311 | if (!test_gf2m_mod(out)) | |
312 | goto err; | |
313 | (void)BIO_flush(out); | |
314 | ||
315 | message(out, "BN_GF2m_mod_mul"); | |
316 | if (!test_gf2m_mod_mul(out, ctx)) | |
317 | goto err; | |
318 | (void)BIO_flush(out); | |
319 | ||
320 | message(out, "BN_GF2m_mod_sqr"); | |
321 | if (!test_gf2m_mod_sqr(out, ctx)) | |
322 | goto err; | |
323 | (void)BIO_flush(out); | |
324 | ||
325 | message(out, "BN_GF2m_mod_inv"); | |
326 | if (!test_gf2m_mod_inv(out, ctx)) | |
327 | goto err; | |
328 | (void)BIO_flush(out); | |
329 | ||
330 | message(out, "BN_GF2m_mod_div"); | |
331 | if (!test_gf2m_mod_div(out, ctx)) | |
332 | goto err; | |
333 | (void)BIO_flush(out); | |
334 | ||
335 | message(out, "BN_GF2m_mod_exp"); | |
336 | if (!test_gf2m_mod_exp(out, ctx)) | |
337 | goto err; | |
338 | (void)BIO_flush(out); | |
339 | ||
340 | message(out, "BN_GF2m_mod_sqrt"); | |
341 | if (!test_gf2m_mod_sqrt(out, ctx)) | |
342 | goto err; | |
343 | (void)BIO_flush(out); | |
344 | ||
345 | message(out, "BN_GF2m_mod_solve_quad"); | |
346 | if (!test_gf2m_mod_solve_quad(out, ctx)) | |
347 | goto err; | |
348 | (void)BIO_flush(out); | |
b3310161 | 349 | #endif |
0f113f3e MC |
350 | BN_CTX_free(ctx); |
351 | BIO_free(out); | |
352 | ||
353 | EXIT(0); | |
354 | err: | |
355 | BIO_puts(out, "1\n"); /* make sure the Perl script fed by bc | |
356 | * notices the failure, see test_bn in | |
357 | * test/Makefile.ssl */ | |
358 | (void)BIO_flush(out); | |
359 | ERR_load_crypto_strings(); | |
360 | ERR_print_errors_fp(stderr); | |
361 | EXIT(1); | |
0f113f3e | 362 | } |
d02b48c6 | 363 | |
6b691a5c | 364 | int test_add(BIO *bp) |
0f113f3e MC |
365 | { |
366 | BIGNUM *a, *b, *c; | |
367 | int i; | |
368 | ||
369 | a = BN_new(); | |
370 | b = BN_new(); | |
371 | c = BN_new(); | |
372 | ||
373 | BN_bntest_rand(a, 512, 0, 0); | |
374 | for (i = 0; i < num0; i++) { | |
375 | BN_bntest_rand(b, 450 + i, 0, 0); | |
376 | a->neg = rand_neg(); | |
377 | b->neg = rand_neg(); | |
378 | BN_add(c, a, b); | |
379 | if (bp != NULL) { | |
380 | if (!results) { | |
381 | BN_print(bp, a); | |
382 | BIO_puts(bp, " + "); | |
383 | BN_print(bp, b); | |
384 | BIO_puts(bp, " - "); | |
385 | } | |
386 | BN_print(bp, c); | |
387 | BIO_puts(bp, "\n"); | |
388 | } | |
389 | a->neg = !a->neg; | |
390 | b->neg = !b->neg; | |
391 | BN_add(c, c, b); | |
392 | BN_add(c, c, a); | |
393 | if (!BN_is_zero(c)) { | |
394 | fprintf(stderr, "Add test failed!\n"); | |
395 | return 0; | |
396 | } | |
397 | } | |
398 | BN_free(a); | |
399 | BN_free(b); | |
400 | BN_free(c); | |
401 | return (1); | |
402 | } | |
d02b48c6 | 403 | |
6b691a5c | 404 | int test_sub(BIO *bp) |
0f113f3e MC |
405 | { |
406 | BIGNUM *a, *b, *c; | |
407 | int i; | |
408 | ||
409 | a = BN_new(); | |
410 | b = BN_new(); | |
411 | c = BN_new(); | |
412 | ||
413 | for (i = 0; i < num0 + num1; i++) { | |
414 | if (i < num1) { | |
415 | BN_bntest_rand(a, 512, 0, 0); | |
416 | BN_copy(b, a); | |
417 | if (BN_set_bit(a, i) == 0) | |
418 | return (0); | |
419 | BN_add_word(b, i); | |
420 | } else { | |
421 | BN_bntest_rand(b, 400 + i - num1, 0, 0); | |
422 | a->neg = rand_neg(); | |
423 | b->neg = rand_neg(); | |
424 | } | |
425 | BN_sub(c, a, b); | |
426 | if (bp != NULL) { | |
427 | if (!results) { | |
428 | BN_print(bp, a); | |
429 | BIO_puts(bp, " - "); | |
430 | BN_print(bp, b); | |
431 | BIO_puts(bp, " - "); | |
432 | } | |
433 | BN_print(bp, c); | |
434 | BIO_puts(bp, "\n"); | |
435 | } | |
436 | BN_add(c, c, b); | |
437 | BN_sub(c, c, a); | |
438 | if (!BN_is_zero(c)) { | |
439 | fprintf(stderr, "Subtract test failed!\n"); | |
440 | return 0; | |
441 | } | |
442 | } | |
443 | BN_free(a); | |
444 | BN_free(b); | |
445 | BN_free(c); | |
446 | return (1); | |
447 | } | |
d02b48c6 | 448 | |
6b691a5c | 449 | int test_div(BIO *bp, BN_CTX *ctx) |
0f113f3e MC |
450 | { |
451 | BIGNUM *a, *b, *c, *d, *e; | |
452 | int i; | |
453 | ||
454 | a = BN_new(); | |
455 | b = BN_new(); | |
456 | c = BN_new(); | |
457 | d = BN_new(); | |
458 | e = BN_new(); | |
459 | ||
a9009e51 EK |
460 | BN_one(a); |
461 | BN_zero(b); | |
462 | ||
463 | if (BN_div(d, c, a, b, ctx)) { | |
464 | fprintf(stderr, "Division by zero succeeded!\n"); | |
465 | return 0; | |
466 | } | |
467 | ||
0f113f3e MC |
468 | for (i = 0; i < num0 + num1; i++) { |
469 | if (i < num1) { | |
470 | BN_bntest_rand(a, 400, 0, 0); | |
471 | BN_copy(b, a); | |
472 | BN_lshift(a, a, i); | |
473 | BN_add_word(a, i); | |
474 | } else | |
475 | BN_bntest_rand(b, 50 + 3 * (i - num1), 0, 0); | |
476 | a->neg = rand_neg(); | |
477 | b->neg = rand_neg(); | |
478 | BN_div(d, c, a, b, ctx); | |
479 | if (bp != NULL) { | |
480 | if (!results) { | |
481 | BN_print(bp, a); | |
482 | BIO_puts(bp, " / "); | |
483 | BN_print(bp, b); | |
484 | BIO_puts(bp, " - "); | |
485 | } | |
486 | BN_print(bp, d); | |
487 | BIO_puts(bp, "\n"); | |
488 | ||
489 | if (!results) { | |
490 | BN_print(bp, a); | |
491 | BIO_puts(bp, " % "); | |
492 | BN_print(bp, b); | |
493 | BIO_puts(bp, " - "); | |
494 | } | |
495 | BN_print(bp, c); | |
496 | BIO_puts(bp, "\n"); | |
497 | } | |
498 | BN_mul(e, d, b, ctx); | |
499 | BN_add(d, e, c); | |
500 | BN_sub(d, d, a); | |
501 | if (!BN_is_zero(d)) { | |
502 | fprintf(stderr, "Division test failed!\n"); | |
503 | return 0; | |
504 | } | |
505 | } | |
506 | BN_free(a); | |
507 | BN_free(b); | |
508 | BN_free(c); | |
509 | BN_free(d); | |
510 | BN_free(e); | |
511 | return (1); | |
512 | } | |
513 | ||
514 | static void print_word(BIO *bp, BN_ULONG w) | |
515 | { | |
8169dd73 | 516 | #ifdef SIXTY_FOUR_BIT |
0f113f3e MC |
517 | if (sizeof(w) > sizeof(unsigned long)) { |
518 | unsigned long h = (unsigned long)(w >> 32), l = (unsigned long)(w); | |
519 | ||
520 | if (h) | |
521 | BIO_printf(bp, "%lX%08lX", h, l); | |
522 | else | |
523 | BIO_printf(bp, "%lX", l); | |
524 | return; | |
525 | } | |
8169dd73 | 526 | #endif |
0f113f3e MC |
527 | BIO_printf(bp, BN_HEX_FMT1, w); |
528 | } | |
8169dd73 | 529 | |
cf9056cf | 530 | int test_div_word(BIO *bp) |
0f113f3e MC |
531 | { |
532 | BIGNUM *a, *b; | |
533 | BN_ULONG r, s; | |
534 | int i; | |
535 | ||
536 | a = BN_new(); | |
537 | b = BN_new(); | |
538 | ||
539 | for (i = 0; i < num0; i++) { | |
540 | do { | |
541 | BN_bntest_rand(a, 512, -1, 0); | |
542 | BN_bntest_rand(b, BN_BITS2, -1, 0); | |
4d04226c | 543 | } while (BN_is_zero(b)); |
0f113f3e | 544 | |
4d04226c | 545 | s = b->d[0]; |
0f113f3e MC |
546 | BN_copy(b, a); |
547 | r = BN_div_word(b, s); | |
548 | ||
549 | if (bp != NULL) { | |
550 | if (!results) { | |
551 | BN_print(bp, a); | |
552 | BIO_puts(bp, " / "); | |
553 | print_word(bp, s); | |
554 | BIO_puts(bp, " - "); | |
555 | } | |
556 | BN_print(bp, b); | |
557 | BIO_puts(bp, "\n"); | |
558 | ||
559 | if (!results) { | |
560 | BN_print(bp, a); | |
561 | BIO_puts(bp, " % "); | |
562 | print_word(bp, s); | |
563 | BIO_puts(bp, " - "); | |
564 | } | |
565 | print_word(bp, r); | |
566 | BIO_puts(bp, "\n"); | |
567 | } | |
568 | BN_mul_word(b, s); | |
569 | BN_add_word(b, r); | |
570 | BN_sub(b, a, b); | |
571 | if (!BN_is_zero(b)) { | |
572 | fprintf(stderr, "Division (word) test failed!\n"); | |
573 | return 0; | |
574 | } | |
575 | } | |
576 | BN_free(a); | |
577 | BN_free(b); | |
578 | return (1); | |
579 | } | |
cf9056cf | 580 | |
6b691a5c | 581 | int test_div_recp(BIO *bp, BN_CTX *ctx) |
0f113f3e MC |
582 | { |
583 | BIGNUM *a, *b, *c, *d, *e; | |
584 | BN_RECP_CTX *recp; | |
585 | int i; | |
586 | ||
587 | recp = BN_RECP_CTX_new(); | |
588 | a = BN_new(); | |
589 | b = BN_new(); | |
590 | c = BN_new(); | |
591 | d = BN_new(); | |
592 | e = BN_new(); | |
593 | ||
594 | for (i = 0; i < num0 + num1; i++) { | |
595 | if (i < num1) { | |
596 | BN_bntest_rand(a, 400, 0, 0); | |
597 | BN_copy(b, a); | |
598 | BN_lshift(a, a, i); | |
599 | BN_add_word(a, i); | |
600 | } else | |
601 | BN_bntest_rand(b, 50 + 3 * (i - num1), 0, 0); | |
602 | a->neg = rand_neg(); | |
603 | b->neg = rand_neg(); | |
604 | BN_RECP_CTX_set(recp, b, ctx); | |
605 | BN_div_recp(d, c, a, recp, ctx); | |
606 | if (bp != NULL) { | |
607 | if (!results) { | |
608 | BN_print(bp, a); | |
609 | BIO_puts(bp, " / "); | |
610 | BN_print(bp, b); | |
611 | BIO_puts(bp, " - "); | |
612 | } | |
613 | BN_print(bp, d); | |
614 | BIO_puts(bp, "\n"); | |
615 | ||
616 | if (!results) { | |
617 | BN_print(bp, a); | |
618 | BIO_puts(bp, " % "); | |
619 | BN_print(bp, b); | |
620 | BIO_puts(bp, " - "); | |
621 | } | |
622 | BN_print(bp, c); | |
623 | BIO_puts(bp, "\n"); | |
624 | } | |
625 | BN_mul(e, d, b, ctx); | |
626 | BN_add(d, e, c); | |
627 | BN_sub(d, d, a); | |
628 | if (!BN_is_zero(d)) { | |
629 | fprintf(stderr, "Reciprocal division test failed!\n"); | |
630 | fprintf(stderr, "a="); | |
631 | BN_print_fp(stderr, a); | |
632 | fprintf(stderr, "\nb="); | |
633 | BN_print_fp(stderr, b); | |
634 | fprintf(stderr, "\n"); | |
635 | return 0; | |
636 | } | |
637 | } | |
638 | BN_free(a); | |
639 | BN_free(b); | |
640 | BN_free(c); | |
641 | BN_free(d); | |
642 | BN_free(e); | |
643 | BN_RECP_CTX_free(recp); | |
644 | return (1); | |
645 | } | |
d02b48c6 | 646 | |
6b691a5c | 647 | int test_mul(BIO *bp) |
0f113f3e MC |
648 | { |
649 | BIGNUM *a, *b, *c, *d, *e; | |
650 | int i; | |
651 | BN_CTX *ctx; | |
652 | ||
653 | ctx = BN_CTX_new(); | |
654 | if (ctx == NULL) | |
655 | EXIT(1); | |
656 | ||
657 | a = BN_new(); | |
658 | b = BN_new(); | |
659 | c = BN_new(); | |
660 | d = BN_new(); | |
661 | e = BN_new(); | |
662 | ||
663 | for (i = 0; i < num0 + num1; i++) { | |
664 | if (i <= num1) { | |
665 | BN_bntest_rand(a, 100, 0, 0); | |
666 | BN_bntest_rand(b, 100, 0, 0); | |
667 | } else | |
668 | BN_bntest_rand(b, i - num1, 0, 0); | |
669 | a->neg = rand_neg(); | |
670 | b->neg = rand_neg(); | |
671 | BN_mul(c, a, b, ctx); | |
672 | if (bp != NULL) { | |
673 | if (!results) { | |
674 | BN_print(bp, a); | |
675 | BIO_puts(bp, " * "); | |
676 | BN_print(bp, b); | |
677 | BIO_puts(bp, " - "); | |
678 | } | |
679 | BN_print(bp, c); | |
680 | BIO_puts(bp, "\n"); | |
681 | } | |
682 | BN_div(d, e, c, a, ctx); | |
683 | BN_sub(d, d, b); | |
684 | if (!BN_is_zero(d) || !BN_is_zero(e)) { | |
685 | fprintf(stderr, "Multiplication test failed!\n"); | |
686 | return 0; | |
687 | } | |
688 | } | |
689 | BN_free(a); | |
690 | BN_free(b); | |
691 | BN_free(c); | |
692 | BN_free(d); | |
693 | BN_free(e); | |
694 | BN_CTX_free(ctx); | |
695 | return (1); | |
696 | } | |
d02b48c6 | 697 | |
6b691a5c | 698 | int test_sqr(BIO *bp, BN_CTX *ctx) |
0f113f3e MC |
699 | { |
700 | BIGNUM *a, *c, *d, *e; | |
701 | int i, ret = 0; | |
702 | ||
703 | a = BN_new(); | |
704 | c = BN_new(); | |
705 | d = BN_new(); | |
706 | e = BN_new(); | |
707 | if (a == NULL || c == NULL || d == NULL || e == NULL) { | |
708 | goto err; | |
709 | } | |
710 | ||
711 | for (i = 0; i < num0; i++) { | |
712 | BN_bntest_rand(a, 40 + i * 10, 0, 0); | |
713 | a->neg = rand_neg(); | |
714 | BN_sqr(c, a, ctx); | |
715 | if (bp != NULL) { | |
716 | if (!results) { | |
717 | BN_print(bp, a); | |
718 | BIO_puts(bp, " * "); | |
719 | BN_print(bp, a); | |
720 | BIO_puts(bp, " - "); | |
721 | } | |
722 | BN_print(bp, c); | |
723 | BIO_puts(bp, "\n"); | |
724 | } | |
725 | BN_div(d, e, c, a, ctx); | |
726 | BN_sub(d, d, a); | |
727 | if (!BN_is_zero(d) || !BN_is_zero(e)) { | |
728 | fprintf(stderr, "Square test failed!\n"); | |
729 | goto err; | |
730 | } | |
731 | } | |
732 | ||
733 | /* Regression test for a BN_sqr overflow bug. */ | |
734 | BN_hex2bn(&a, | |
735 | "80000000000000008000000000000001" | |
736 | "FFFFFFFFFFFFFFFE0000000000000000"); | |
737 | BN_sqr(c, a, ctx); | |
738 | if (bp != NULL) { | |
739 | if (!results) { | |
740 | BN_print(bp, a); | |
741 | BIO_puts(bp, " * "); | |
742 | BN_print(bp, a); | |
743 | BIO_puts(bp, " - "); | |
744 | } | |
745 | BN_print(bp, c); | |
746 | BIO_puts(bp, "\n"); | |
747 | } | |
748 | BN_mul(d, a, a, ctx); | |
749 | if (BN_cmp(c, d)) { | |
750 | fprintf(stderr, "Square test failed: BN_sqr and BN_mul produce " | |
751 | "different results!\n"); | |
752 | goto err; | |
753 | } | |
754 | ||
755 | /* Regression test for a BN_sqr overflow bug. */ | |
756 | BN_hex2bn(&a, | |
757 | "80000000000000000000000080000001" | |
758 | "FFFFFFFE000000000000000000000000"); | |
759 | BN_sqr(c, a, ctx); | |
760 | if (bp != NULL) { | |
761 | if (!results) { | |
762 | BN_print(bp, a); | |
763 | BIO_puts(bp, " * "); | |
764 | BN_print(bp, a); | |
765 | BIO_puts(bp, " - "); | |
766 | } | |
767 | BN_print(bp, c); | |
768 | BIO_puts(bp, "\n"); | |
769 | } | |
770 | BN_mul(d, a, a, ctx); | |
771 | if (BN_cmp(c, d)) { | |
772 | fprintf(stderr, "Square test failed: BN_sqr and BN_mul produce " | |
773 | "different results!\n"); | |
774 | goto err; | |
775 | } | |
776 | ret = 1; | |
777 | err: | |
23a1d5e9 RS |
778 | BN_free(a); |
779 | BN_free(c); | |
780 | BN_free(d); | |
781 | BN_free(e); | |
0f113f3e MC |
782 | return ret; |
783 | } | |
d02b48c6 | 784 | |
6b691a5c | 785 | int test_mont(BIO *bp, BN_CTX *ctx) |
0f113f3e MC |
786 | { |
787 | BIGNUM *a, *b, *c, *d, *A, *B; | |
788 | BIGNUM *n; | |
789 | int i; | |
790 | BN_MONT_CTX *mont; | |
791 | ||
792 | a = BN_new(); | |
793 | b = BN_new(); | |
794 | c = BN_new(); | |
795 | d = BN_new(); | |
796 | A = BN_new(); | |
797 | B = BN_new(); | |
798 | n = BN_new(); | |
799 | ||
800 | mont = BN_MONT_CTX_new(); | |
801 | if (mont == NULL) | |
802 | return 0; | |
803 | ||
a9009e51 EK |
804 | BN_zero(n); |
805 | if (BN_MONT_CTX_set(mont, n, ctx)) { | |
806 | fprintf(stderr, "BN_MONT_CTX_set succeeded for zero modulus!\n"); | |
807 | return 0; | |
808 | } | |
809 | ||
810 | BN_set_word(n, 16); | |
811 | if (BN_MONT_CTX_set(mont, n, ctx)) { | |
812 | fprintf(stderr, "BN_MONT_CTX_set succeeded for even modulus!\n"); | |
813 | return 0; | |
814 | } | |
815 | ||
0f113f3e MC |
816 | BN_bntest_rand(a, 100, 0, 0); |
817 | BN_bntest_rand(b, 100, 0, 0); | |
818 | for (i = 0; i < num2; i++) { | |
819 | int bits = (200 * (i + 1)) / num2; | |
820 | ||
821 | if (bits == 0) | |
822 | continue; | |
823 | BN_bntest_rand(n, bits, 0, 1); | |
824 | BN_MONT_CTX_set(mont, n, ctx); | |
825 | ||
826 | BN_nnmod(a, a, n, ctx); | |
827 | BN_nnmod(b, b, n, ctx); | |
828 | ||
829 | BN_to_montgomery(A, a, mont, ctx); | |
830 | BN_to_montgomery(B, b, mont, ctx); | |
831 | ||
832 | BN_mod_mul_montgomery(c, A, B, mont, ctx); | |
833 | BN_from_montgomery(A, c, mont, ctx); | |
834 | if (bp != NULL) { | |
835 | if (!results) { | |
0f113f3e MC |
836 | BN_print(bp, a); |
837 | BIO_puts(bp, " * "); | |
838 | BN_print(bp, b); | |
839 | BIO_puts(bp, " % "); | |
840 | BN_print(bp, &mont->N); | |
841 | BIO_puts(bp, " - "); | |
842 | } | |
843 | BN_print(bp, A); | |
844 | BIO_puts(bp, "\n"); | |
845 | } | |
846 | BN_mod_mul(d, a, b, n, ctx); | |
847 | BN_sub(d, d, A); | |
848 | if (!BN_is_zero(d)) { | |
849 | fprintf(stderr, "Montgomery multiplication test failed!\n"); | |
850 | return 0; | |
851 | } | |
852 | } | |
853 | BN_MONT_CTX_free(mont); | |
854 | BN_free(a); | |
855 | BN_free(b); | |
856 | BN_free(c); | |
857 | BN_free(d); | |
858 | BN_free(A); | |
859 | BN_free(B); | |
860 | BN_free(n); | |
861 | return (1); | |
862 | } | |
d02b48c6 | 863 | |
6b691a5c | 864 | int test_mod(BIO *bp, BN_CTX *ctx) |
0f113f3e MC |
865 | { |
866 | BIGNUM *a, *b, *c, *d, *e; | |
867 | int i; | |
868 | ||
869 | a = BN_new(); | |
870 | b = BN_new(); | |
871 | c = BN_new(); | |
872 | d = BN_new(); | |
873 | e = BN_new(); | |
874 | ||
875 | BN_bntest_rand(a, 1024, 0, 0); | |
876 | for (i = 0; i < num0; i++) { | |
877 | BN_bntest_rand(b, 450 + i * 10, 0, 0); | |
878 | a->neg = rand_neg(); | |
879 | b->neg = rand_neg(); | |
880 | BN_mod(c, a, b, ctx); | |
881 | if (bp != NULL) { | |
882 | if (!results) { | |
883 | BN_print(bp, a); | |
884 | BIO_puts(bp, " % "); | |
885 | BN_print(bp, b); | |
886 | BIO_puts(bp, " - "); | |
887 | } | |
888 | BN_print(bp, c); | |
889 | BIO_puts(bp, "\n"); | |
890 | } | |
891 | BN_div(d, e, a, b, ctx); | |
892 | BN_sub(e, e, c); | |
893 | if (!BN_is_zero(e)) { | |
894 | fprintf(stderr, "Modulo test failed!\n"); | |
895 | return 0; | |
896 | } | |
897 | } | |
898 | BN_free(a); | |
899 | BN_free(b); | |
900 | BN_free(c); | |
901 | BN_free(d); | |
902 | BN_free(e); | |
903 | return (1); | |
904 | } | |
d02b48c6 | 905 | |
6b691a5c | 906 | int test_mod_mul(BIO *bp, BN_CTX *ctx) |
0f113f3e MC |
907 | { |
908 | BIGNUM *a, *b, *c, *d, *e; | |
909 | int i, j; | |
910 | ||
911 | a = BN_new(); | |
912 | b = BN_new(); | |
913 | c = BN_new(); | |
914 | d = BN_new(); | |
915 | e = BN_new(); | |
916 | ||
a9009e51 EK |
917 | BN_one(a); |
918 | BN_one(b); | |
919 | BN_zero(c); | |
920 | if (BN_mod_mul(e, a, b, c, ctx)) { | |
921 | fprintf(stderr, "BN_mod_mul with zero modulus succeeded!\n"); | |
922 | return 0; | |
923 | } | |
924 | ||
0f113f3e MC |
925 | for (j = 0; j < 3; j++) { |
926 | BN_bntest_rand(c, 1024, 0, 0); | |
927 | for (i = 0; i < num0; i++) { | |
928 | BN_bntest_rand(a, 475 + i * 10, 0, 0); | |
929 | BN_bntest_rand(b, 425 + i * 11, 0, 0); | |
930 | a->neg = rand_neg(); | |
931 | b->neg = rand_neg(); | |
932 | if (!BN_mod_mul(e, a, b, c, ctx)) { | |
933 | unsigned long l; | |
934 | ||
935 | while ((l = ERR_get_error())) | |
936 | fprintf(stderr, "ERROR:%s\n", ERR_error_string(l, NULL)); | |
937 | EXIT(1); | |
938 | } | |
939 | if (bp != NULL) { | |
940 | if (!results) { | |
941 | BN_print(bp, a); | |
942 | BIO_puts(bp, " * "); | |
943 | BN_print(bp, b); | |
944 | BIO_puts(bp, " % "); | |
945 | BN_print(bp, c); | |
946 | if ((a->neg ^ b->neg) && !BN_is_zero(e)) { | |
947 | /* | |
948 | * If (a*b) % c is negative, c must be added in order | |
949 | * to obtain the normalized remainder (new with | |
950 | * OpenSSL 0.9.7, previous versions of BN_mod_mul | |
951 | * could generate negative results) | |
952 | */ | |
953 | BIO_puts(bp, " + "); | |
954 | BN_print(bp, c); | |
955 | } | |
956 | BIO_puts(bp, " - "); | |
957 | } | |
958 | BN_print(bp, e); | |
959 | BIO_puts(bp, "\n"); | |
960 | } | |
961 | BN_mul(d, a, b, ctx); | |
962 | BN_sub(d, d, e); | |
963 | BN_div(a, b, d, c, ctx); | |
964 | if (!BN_is_zero(b)) { | |
965 | fprintf(stderr, "Modulo multiply test failed!\n"); | |
966 | ERR_print_errors_fp(stderr); | |
967 | return 0; | |
968 | } | |
969 | } | |
970 | } | |
971 | BN_free(a); | |
972 | BN_free(b); | |
973 | BN_free(c); | |
974 | BN_free(d); | |
975 | BN_free(e); | |
976 | return (1); | |
977 | } | |
d02b48c6 | 978 | |
6b691a5c | 979 | int test_mod_exp(BIO *bp, BN_CTX *ctx) |
0f113f3e MC |
980 | { |
981 | BIGNUM *a, *b, *c, *d, *e; | |
982 | int i; | |
983 | ||
984 | a = BN_new(); | |
985 | b = BN_new(); | |
986 | c = BN_new(); | |
987 | d = BN_new(); | |
988 | e = BN_new(); | |
989 | ||
a9009e51 EK |
990 | BN_one(a); |
991 | BN_one(b); | |
992 | BN_zero(c); | |
993 | if (BN_mod_exp(d, a, b, c, ctx)) { | |
994 | fprintf(stderr, "BN_mod_exp with zero modulus succeeded!\n"); | |
995 | return 0; | |
996 | } | |
997 | ||
0f113f3e MC |
998 | BN_bntest_rand(c, 30, 0, 1); /* must be odd for montgomery */ |
999 | for (i = 0; i < num2; i++) { | |
1000 | BN_bntest_rand(a, 20 + i * 5, 0, 0); | |
1001 | BN_bntest_rand(b, 2 + i, 0, 0); | |
1002 | ||
1003 | if (!BN_mod_exp(d, a, b, c, ctx)) | |
1004 | return (0); | |
1005 | ||
1006 | if (bp != NULL) { | |
1007 | if (!results) { | |
1008 | BN_print(bp, a); | |
1009 | BIO_puts(bp, " ^ "); | |
1010 | BN_print(bp, b); | |
1011 | BIO_puts(bp, " % "); | |
1012 | BN_print(bp, c); | |
1013 | BIO_puts(bp, " - "); | |
1014 | } | |
1015 | BN_print(bp, d); | |
1016 | BIO_puts(bp, "\n"); | |
1017 | } | |
1018 | BN_exp(e, a, b, ctx); | |
1019 | BN_sub(e, e, d); | |
1020 | BN_div(a, b, e, c, ctx); | |
1021 | if (!BN_is_zero(b)) { | |
1022 | fprintf(stderr, "Modulo exponentiation test failed!\n"); | |
1023 | return 0; | |
1024 | } | |
1025 | } | |
1026 | BN_free(a); | |
1027 | BN_free(b); | |
1028 | BN_free(c); | |
1029 | BN_free(d); | |
1030 | BN_free(e); | |
1031 | return (1); | |
1032 | } | |
d02b48c6 | 1033 | |
46a64376 | 1034 | int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx) |
0f113f3e MC |
1035 | { |
1036 | BIGNUM *a, *b, *c, *d, *e; | |
1037 | int i; | |
1038 | ||
1039 | a = BN_new(); | |
1040 | b = BN_new(); | |
1041 | c = BN_new(); | |
1042 | d = BN_new(); | |
1043 | e = BN_new(); | |
1044 | ||
a9009e51 EK |
1045 | BN_one(a); |
1046 | BN_one(b); | |
1047 | BN_zero(c); | |
1048 | if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) { | |
1049 | fprintf(stderr, "BN_mod_exp_mont_consttime with zero modulus " | |
1050 | "succeeded\n"); | |
1051 | return 0; | |
1052 | } | |
1053 | ||
1054 | BN_set_word(c, 16); | |
1055 | if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) { | |
1056 | fprintf(stderr, "BN_mod_exp_mont_consttime with even modulus " | |
1057 | "succeeded\n"); | |
1058 | return 0; | |
1059 | } | |
1060 | ||
0f113f3e MC |
1061 | BN_bntest_rand(c, 30, 0, 1); /* must be odd for montgomery */ |
1062 | for (i = 0; i < num2; i++) { | |
1063 | BN_bntest_rand(a, 20 + i * 5, 0, 0); | |
1064 | BN_bntest_rand(b, 2 + i, 0, 0); | |
1065 | ||
1066 | if (!BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) | |
1067 | return (00); | |
1068 | ||
1069 | if (bp != NULL) { | |
1070 | if (!results) { | |
1071 | BN_print(bp, a); | |
1072 | BIO_puts(bp, " ^ "); | |
1073 | BN_print(bp, b); | |
1074 | BIO_puts(bp, " % "); | |
1075 | BN_print(bp, c); | |
1076 | BIO_puts(bp, " - "); | |
1077 | } | |
1078 | BN_print(bp, d); | |
1079 | BIO_puts(bp, "\n"); | |
1080 | } | |
1081 | BN_exp(e, a, b, ctx); | |
1082 | BN_sub(e, e, d); | |
1083 | BN_div(a, b, e, c, ctx); | |
1084 | if (!BN_is_zero(b)) { | |
1085 | fprintf(stderr, "Modulo exponentiation test failed!\n"); | |
1086 | return 0; | |
1087 | } | |
1088 | } | |
1089 | BN_free(a); | |
1090 | BN_free(b); | |
1091 | BN_free(c); | |
1092 | BN_free(d); | |
1093 | BN_free(e); | |
1094 | return (1); | |
1095 | } | |
1096 | ||
1097 | /* | |
1098 | * Test constant-time modular exponentiation with 1024-bit inputs, which on | |
1099 | * x86_64 cause a different code branch to be taken. | |
cdfe0fdd BM |
1100 | */ |
1101 | int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx) | |
0f113f3e MC |
1102 | { |
1103 | BIGNUM *a, *p, *m, *d, *e; | |
0f113f3e MC |
1104 | BN_MONT_CTX *mont; |
1105 | ||
1106 | a = BN_new(); | |
1107 | p = BN_new(); | |
1108 | m = BN_new(); | |
1109 | d = BN_new(); | |
1110 | e = BN_new(); | |
0f113f3e MC |
1111 | mont = BN_MONT_CTX_new(); |
1112 | ||
1113 | BN_bntest_rand(m, 1024, 0, 1); /* must be odd for montgomery */ | |
1114 | /* Zero exponent */ | |
1115 | BN_bntest_rand(a, 1024, 0, 0); | |
1116 | BN_zero(p); | |
1117 | if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)) | |
1118 | return 0; | |
1119 | if (!BN_is_one(d)) { | |
1120 | fprintf(stderr, "Modular exponentiation test failed!\n"); | |
1121 | return 0; | |
1122 | } | |
1123 | /* Zero input */ | |
1124 | BN_bntest_rand(p, 1024, 0, 0); | |
1125 | BN_zero(a); | |
1126 | if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)) | |
1127 | return 0; | |
1128 | if (!BN_is_zero(d)) { | |
1129 | fprintf(stderr, "Modular exponentiation test failed!\n"); | |
1130 | return 0; | |
1131 | } | |
1132 | /* | |
1133 | * Craft an input whose Montgomery representation is 1, i.e., shorter | |
1134 | * than the modulus m, in order to test the const time precomputation | |
1135 | * scattering/gathering. | |
1136 | */ | |
1137 | BN_one(a); | |
1138 | BN_MONT_CTX_set(mont, m, ctx); | |
1139 | if (!BN_from_montgomery(e, a, mont, ctx)) | |
1140 | return 0; | |
1141 | if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL)) | |
1142 | return 0; | |
1143 | if (!BN_mod_exp_simple(a, e, p, m, ctx)) | |
1144 | return 0; | |
1145 | if (BN_cmp(a, d) != 0) { | |
1146 | fprintf(stderr, "Modular exponentiation test failed!\n"); | |
1147 | return 0; | |
1148 | } | |
1149 | /* Finally, some regular test vectors. */ | |
1150 | BN_bntest_rand(e, 1024, 0, 0); | |
1151 | if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL)) | |
1152 | return 0; | |
1153 | if (!BN_mod_exp_simple(a, e, p, m, ctx)) | |
1154 | return 0; | |
1155 | if (BN_cmp(a, d) != 0) { | |
1156 | fprintf(stderr, "Modular exponentiation test failed!\n"); | |
1157 | return 0; | |
1158 | } | |
2d540402 | 1159 | BN_MONT_CTX_free(mont); |
0f113f3e MC |
1160 | BN_free(a); |
1161 | BN_free(p); | |
1162 | BN_free(m); | |
1163 | BN_free(d); | |
1164 | BN_free(e); | |
1165 | return (1); | |
1166 | } | |
cdfe0fdd | 1167 | |
6b691a5c | 1168 | int test_exp(BIO *bp, BN_CTX *ctx) |
0f113f3e MC |
1169 | { |
1170 | BIGNUM *a, *b, *d, *e, *one; | |
1171 | int i; | |
1172 | ||
1173 | a = BN_new(); | |
1174 | b = BN_new(); | |
1175 | d = BN_new(); | |
1176 | e = BN_new(); | |
1177 | one = BN_new(); | |
1178 | BN_one(one); | |
1179 | ||
1180 | for (i = 0; i < num2; i++) { | |
1181 | BN_bntest_rand(a, 20 + i * 5, 0, 0); | |
1182 | BN_bntest_rand(b, 2 + i, 0, 0); | |
1183 | ||
1184 | if (BN_exp(d, a, b, ctx) <= 0) | |
1185 | return (0); | |
1186 | ||
1187 | if (bp != NULL) { | |
1188 | if (!results) { | |
1189 | BN_print(bp, a); | |
1190 | BIO_puts(bp, " ^ "); | |
1191 | BN_print(bp, b); | |
1192 | BIO_puts(bp, " - "); | |
1193 | } | |
1194 | BN_print(bp, d); | |
1195 | BIO_puts(bp, "\n"); | |
1196 | } | |
1197 | BN_one(e); | |
1198 | for (; !BN_is_zero(b); BN_sub(b, b, one)) | |
1199 | BN_mul(e, e, a, ctx); | |
1200 | BN_sub(e, e, d); | |
1201 | if (!BN_is_zero(e)) { | |
1202 | fprintf(stderr, "Exponentiation test failed!\n"); | |
1203 | return 0; | |
1204 | } | |
1205 | } | |
1206 | BN_free(a); | |
1207 | BN_free(b); | |
1208 | BN_free(d); | |
1209 | BN_free(e); | |
1210 | BN_free(one); | |
1211 | return (1); | |
1212 | } | |
1213 | ||
b3310161 | 1214 | #ifndef OPENSSL_NO_EC2M |
1dc920c8 | 1215 | int test_gf2m_add(BIO *bp) |
0f113f3e MC |
1216 | { |
1217 | BIGNUM *a, *b, *c; | |
1218 | int i, ret = 0; | |
1219 | ||
1220 | a = BN_new(); | |
1221 | b = BN_new(); | |
1222 | c = BN_new(); | |
1223 | ||
1224 | for (i = 0; i < num0; i++) { | |
1225 | BN_rand(a, 512, 0, 0); | |
1226 | BN_copy(b, BN_value_one()); | |
1227 | a->neg = rand_neg(); | |
1228 | b->neg = rand_neg(); | |
1229 | BN_GF2m_add(c, a, b); | |
0f113f3e MC |
1230 | /* Test that two added values have the correct parity. */ |
1231 | if ((BN_is_odd(a) && BN_is_odd(c)) | |
1232 | || (!BN_is_odd(a) && !BN_is_odd(c))) { | |
1233 | fprintf(stderr, "GF(2^m) addition test (a) failed!\n"); | |
1234 | goto err; | |
1235 | } | |
1236 | BN_GF2m_add(c, c, c); | |
1237 | /* Test that c + c = 0. */ | |
1238 | if (!BN_is_zero(c)) { | |
1239 | fprintf(stderr, "GF(2^m) addition test (b) failed!\n"); | |
1240 | goto err; | |
1241 | } | |
1242 | } | |
1243 | ret = 1; | |
1244 | err: | |
1245 | BN_free(a); | |
1246 | BN_free(b); | |
1247 | BN_free(c); | |
1248 | return ret; | |
1249 | } | |
1dc920c8 BM |
1250 | |
1251 | int test_gf2m_mod(BIO *bp) | |
0f113f3e MC |
1252 | { |
1253 | BIGNUM *a, *b[2], *c, *d, *e; | |
1254 | int i, j, ret = 0; | |
1255 | int p0[] = { 163, 7, 6, 3, 0, -1 }; | |
1256 | int p1[] = { 193, 15, 0, -1 }; | |
1257 | ||
1258 | a = BN_new(); | |
1259 | b[0] = BN_new(); | |
1260 | b[1] = BN_new(); | |
1261 | c = BN_new(); | |
1262 | d = BN_new(); | |
1263 | e = BN_new(); | |
1264 | ||
1265 | BN_GF2m_arr2poly(p0, b[0]); | |
1266 | BN_GF2m_arr2poly(p1, b[1]); | |
1267 | ||
1268 | for (i = 0; i < num0; i++) { | |
1269 | BN_bntest_rand(a, 1024, 0, 0); | |
1270 | for (j = 0; j < 2; j++) { | |
1271 | BN_GF2m_mod(c, a, b[j]); | |
0f113f3e MC |
1272 | BN_GF2m_add(d, a, c); |
1273 | BN_GF2m_mod(e, d, b[j]); | |
1274 | /* Test that a + (a mod p) mod p == 0. */ | |
1275 | if (!BN_is_zero(e)) { | |
1276 | fprintf(stderr, "GF(2^m) modulo test failed!\n"); | |
1277 | goto err; | |
1278 | } | |
1279 | } | |
1280 | } | |
1281 | ret = 1; | |
1282 | err: | |
1283 | BN_free(a); | |
1284 | BN_free(b[0]); | |
1285 | BN_free(b[1]); | |
1286 | BN_free(c); | |
1287 | BN_free(d); | |
1288 | BN_free(e); | |
1289 | return ret; | |
1290 | } | |
1291 | ||
1292 | int test_gf2m_mod_mul(BIO *bp, BN_CTX *ctx) | |
1293 | { | |
1294 | BIGNUM *a, *b[2], *c, *d, *e, *f, *g, *h; | |
1295 | int i, j, ret = 0; | |
1296 | int p0[] = { 163, 7, 6, 3, 0, -1 }; | |
1297 | int p1[] = { 193, 15, 0, -1 }; | |
1298 | ||
1299 | a = BN_new(); | |
1300 | b[0] = BN_new(); | |
1301 | b[1] = BN_new(); | |
1302 | c = BN_new(); | |
1303 | d = BN_new(); | |
1304 | e = BN_new(); | |
1305 | f = BN_new(); | |
1306 | g = BN_new(); | |
1307 | h = BN_new(); | |
1308 | ||
1309 | BN_GF2m_arr2poly(p0, b[0]); | |
1310 | BN_GF2m_arr2poly(p1, b[1]); | |
1311 | ||
1312 | for (i = 0; i < num0; i++) { | |
1313 | BN_bntest_rand(a, 1024, 0, 0); | |
1314 | BN_bntest_rand(c, 1024, 0, 0); | |
1315 | BN_bntest_rand(d, 1024, 0, 0); | |
1316 | for (j = 0; j < 2; j++) { | |
1317 | BN_GF2m_mod_mul(e, a, c, b[j], ctx); | |
0f113f3e MC |
1318 | BN_GF2m_add(f, a, d); |
1319 | BN_GF2m_mod_mul(g, f, c, b[j], ctx); | |
1320 | BN_GF2m_mod_mul(h, d, c, b[j], ctx); | |
1321 | BN_GF2m_add(f, e, g); | |
1322 | BN_GF2m_add(f, f, h); | |
1323 | /* Test that (a+d)*c = a*c + d*c. */ | |
1324 | if (!BN_is_zero(f)) { | |
1325 | fprintf(stderr, | |
1326 | "GF(2^m) modular multiplication test failed!\n"); | |
1327 | goto err; | |
1328 | } | |
1329 | } | |
1330 | } | |
1331 | ret = 1; | |
1332 | err: | |
1333 | BN_free(a); | |
1334 | BN_free(b[0]); | |
1335 | BN_free(b[1]); | |
1336 | BN_free(c); | |
1337 | BN_free(d); | |
1338 | BN_free(e); | |
1339 | BN_free(f); | |
1340 | BN_free(g); | |
1341 | BN_free(h); | |
1342 | return ret; | |
1343 | } | |
1344 | ||
1345 | int test_gf2m_mod_sqr(BIO *bp, BN_CTX *ctx) | |
1346 | { | |
1347 | BIGNUM *a, *b[2], *c, *d; | |
1348 | int i, j, ret = 0; | |
1349 | int p0[] = { 163, 7, 6, 3, 0, -1 }; | |
1350 | int p1[] = { 193, 15, 0, -1 }; | |
1351 | ||
1352 | a = BN_new(); | |
1353 | b[0] = BN_new(); | |
1354 | b[1] = BN_new(); | |
1355 | c = BN_new(); | |
1356 | d = BN_new(); | |
1357 | ||
1358 | BN_GF2m_arr2poly(p0, b[0]); | |
1359 | BN_GF2m_arr2poly(p1, b[1]); | |
1360 | ||
1361 | for (i = 0; i < num0; i++) { | |
1362 | BN_bntest_rand(a, 1024, 0, 0); | |
1363 | for (j = 0; j < 2; j++) { | |
1364 | BN_GF2m_mod_sqr(c, a, b[j], ctx); | |
1365 | BN_copy(d, a); | |
1366 | BN_GF2m_mod_mul(d, a, d, b[j], ctx); | |
0f113f3e MC |
1367 | BN_GF2m_add(d, c, d); |
1368 | /* Test that a*a = a^2. */ | |
1369 | if (!BN_is_zero(d)) { | |
1370 | fprintf(stderr, "GF(2^m) modular squaring test failed!\n"); | |
1371 | goto err; | |
1372 | } | |
1373 | } | |
1374 | } | |
1375 | ret = 1; | |
1376 | err: | |
1377 | BN_free(a); | |
1378 | BN_free(b[0]); | |
1379 | BN_free(b[1]); | |
1380 | BN_free(c); | |
1381 | BN_free(d); | |
1382 | return ret; | |
1383 | } | |
1384 | ||
1385 | int test_gf2m_mod_inv(BIO *bp, BN_CTX *ctx) | |
1386 | { | |
1387 | BIGNUM *a, *b[2], *c, *d; | |
1388 | int i, j, ret = 0; | |
1389 | int p0[] = { 163, 7, 6, 3, 0, -1 }; | |
1390 | int p1[] = { 193, 15, 0, -1 }; | |
1391 | ||
1392 | a = BN_new(); | |
1393 | b[0] = BN_new(); | |
1394 | b[1] = BN_new(); | |
1395 | c = BN_new(); | |
1396 | d = BN_new(); | |
1397 | ||
1398 | BN_GF2m_arr2poly(p0, b[0]); | |
1399 | BN_GF2m_arr2poly(p1, b[1]); | |
1400 | ||
1401 | for (i = 0; i < num0; i++) { | |
1402 | BN_bntest_rand(a, 512, 0, 0); | |
1403 | for (j = 0; j < 2; j++) { | |
1404 | BN_GF2m_mod_inv(c, a, b[j], ctx); | |
1405 | BN_GF2m_mod_mul(d, a, c, b[j], ctx); | |
0f113f3e MC |
1406 | /* Test that ((1/a)*a) = 1. */ |
1407 | if (!BN_is_one(d)) { | |
1408 | fprintf(stderr, "GF(2^m) modular inversion test failed!\n"); | |
1409 | goto err; | |
1410 | } | |
1411 | } | |
1412 | } | |
1413 | ret = 1; | |
1414 | err: | |
1415 | BN_free(a); | |
1416 | BN_free(b[0]); | |
1417 | BN_free(b[1]); | |
1418 | BN_free(c); | |
1419 | BN_free(d); | |
1420 | return ret; | |
1421 | } | |
1422 | ||
1423 | int test_gf2m_mod_div(BIO *bp, BN_CTX *ctx) | |
1424 | { | |
1425 | BIGNUM *a, *b[2], *c, *d, *e, *f; | |
1426 | int i, j, ret = 0; | |
1427 | int p0[] = { 163, 7, 6, 3, 0, -1 }; | |
1428 | int p1[] = { 193, 15, 0, -1 }; | |
1429 | ||
1430 | a = BN_new(); | |
1431 | b[0] = BN_new(); | |
1432 | b[1] = BN_new(); | |
1433 | c = BN_new(); | |
1434 | d = BN_new(); | |
1435 | e = BN_new(); | |
1436 | f = BN_new(); | |
1437 | ||
1438 | BN_GF2m_arr2poly(p0, b[0]); | |
1439 | BN_GF2m_arr2poly(p1, b[1]); | |
1440 | ||
1441 | for (i = 0; i < num0; i++) { | |
1442 | BN_bntest_rand(a, 512, 0, 0); | |
1443 | BN_bntest_rand(c, 512, 0, 0); | |
1444 | for (j = 0; j < 2; j++) { | |
1445 | BN_GF2m_mod_div(d, a, c, b[j], ctx); | |
1446 | BN_GF2m_mod_mul(e, d, c, b[j], ctx); | |
1447 | BN_GF2m_mod_div(f, a, e, b[j], ctx); | |
0f113f3e MC |
1448 | /* Test that ((a/c)*c)/a = 1. */ |
1449 | if (!BN_is_one(f)) { | |
1450 | fprintf(stderr, "GF(2^m) modular division test failed!\n"); | |
1451 | goto err; | |
1452 | } | |
1453 | } | |
1454 | } | |
1455 | ret = 1; | |
1456 | err: | |
1457 | BN_free(a); | |
1458 | BN_free(b[0]); | |
1459 | BN_free(b[1]); | |
1460 | BN_free(c); | |
1461 | BN_free(d); | |
1462 | BN_free(e); | |
1463 | BN_free(f); | |
1464 | return ret; | |
1465 | } | |
1466 | ||
1467 | int test_gf2m_mod_exp(BIO *bp, BN_CTX *ctx) | |
1468 | { | |
1469 | BIGNUM *a, *b[2], *c, *d, *e, *f; | |
1470 | int i, j, ret = 0; | |
1471 | int p0[] = { 163, 7, 6, 3, 0, -1 }; | |
1472 | int p1[] = { 193, 15, 0, -1 }; | |
1473 | ||
1474 | a = BN_new(); | |
1475 | b[0] = BN_new(); | |
1476 | b[1] = BN_new(); | |
1477 | c = BN_new(); | |
1478 | d = BN_new(); | |
1479 | e = BN_new(); | |
1480 | f = BN_new(); | |
1481 | ||
1482 | BN_GF2m_arr2poly(p0, b[0]); | |
1483 | BN_GF2m_arr2poly(p1, b[1]); | |
1484 | ||
1485 | for (i = 0; i < num0; i++) { | |
1486 | BN_bntest_rand(a, 512, 0, 0); | |
1487 | BN_bntest_rand(c, 512, 0, 0); | |
1488 | BN_bntest_rand(d, 512, 0, 0); | |
1489 | for (j = 0; j < 2; j++) { | |
1490 | BN_GF2m_mod_exp(e, a, c, b[j], ctx); | |
1491 | BN_GF2m_mod_exp(f, a, d, b[j], ctx); | |
1492 | BN_GF2m_mod_mul(e, e, f, b[j], ctx); | |
1493 | BN_add(f, c, d); | |
1494 | BN_GF2m_mod_exp(f, a, f, b[j], ctx); | |
0f113f3e MC |
1495 | BN_GF2m_add(f, e, f); |
1496 | /* Test that a^(c+d)=a^c*a^d. */ | |
1497 | if (!BN_is_zero(f)) { | |
1498 | fprintf(stderr, | |
1499 | "GF(2^m) modular exponentiation test failed!\n"); | |
1500 | goto err; | |
1501 | } | |
1502 | } | |
1503 | } | |
1504 | ret = 1; | |
1505 | err: | |
1506 | BN_free(a); | |
1507 | BN_free(b[0]); | |
1508 | BN_free(b[1]); | |
1509 | BN_free(c); | |
1510 | BN_free(d); | |
1511 | BN_free(e); | |
1512 | BN_free(f); | |
1513 | return ret; | |
1514 | } | |
1515 | ||
1516 | int test_gf2m_mod_sqrt(BIO *bp, BN_CTX *ctx) | |
1517 | { | |
1518 | BIGNUM *a, *b[2], *c, *d, *e, *f; | |
1519 | int i, j, ret = 0; | |
1520 | int p0[] = { 163, 7, 6, 3, 0, -1 }; | |
1521 | int p1[] = { 193, 15, 0, -1 }; | |
1522 | ||
1523 | a = BN_new(); | |
1524 | b[0] = BN_new(); | |
1525 | b[1] = BN_new(); | |
1526 | c = BN_new(); | |
1527 | d = BN_new(); | |
1528 | e = BN_new(); | |
1529 | f = BN_new(); | |
1530 | ||
1531 | BN_GF2m_arr2poly(p0, b[0]); | |
1532 | BN_GF2m_arr2poly(p1, b[1]); | |
1533 | ||
1534 | for (i = 0; i < num0; i++) { | |
1535 | BN_bntest_rand(a, 512, 0, 0); | |
1536 | for (j = 0; j < 2; j++) { | |
1537 | BN_GF2m_mod(c, a, b[j]); | |
1538 | BN_GF2m_mod_sqrt(d, a, b[j], ctx); | |
1539 | BN_GF2m_mod_sqr(e, d, b[j], ctx); | |
0f113f3e MC |
1540 | BN_GF2m_add(f, c, e); |
1541 | /* Test that d^2 = a, where d = sqrt(a). */ | |
1542 | if (!BN_is_zero(f)) { | |
1543 | fprintf(stderr, "GF(2^m) modular square root test failed!\n"); | |
1544 | goto err; | |
1545 | } | |
1546 | } | |
1547 | } | |
1548 | ret = 1; | |
1549 | err: | |
1550 | BN_free(a); | |
1551 | BN_free(b[0]); | |
1552 | BN_free(b[1]); | |
1553 | BN_free(c); | |
1554 | BN_free(d); | |
1555 | BN_free(e); | |
1556 | BN_free(f); | |
1557 | return ret; | |
1558 | } | |
1559 | ||
1560 | int test_gf2m_mod_solve_quad(BIO *bp, BN_CTX *ctx) | |
1561 | { | |
1562 | BIGNUM *a, *b[2], *c, *d, *e; | |
1563 | int i, j, s = 0, t, ret = 0; | |
1564 | int p0[] = { 163, 7, 6, 3, 0, -1 }; | |
1565 | int p1[] = { 193, 15, 0, -1 }; | |
1566 | ||
1567 | a = BN_new(); | |
1568 | b[0] = BN_new(); | |
1569 | b[1] = BN_new(); | |
1570 | c = BN_new(); | |
1571 | d = BN_new(); | |
1572 | e = BN_new(); | |
1573 | ||
1574 | BN_GF2m_arr2poly(p0, b[0]); | |
1575 | BN_GF2m_arr2poly(p1, b[1]); | |
1576 | ||
1577 | for (i = 0; i < num0; i++) { | |
1578 | BN_bntest_rand(a, 512, 0, 0); | |
1579 | for (j = 0; j < 2; j++) { | |
1580 | t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx); | |
1581 | if (t) { | |
1582 | s++; | |
1583 | BN_GF2m_mod_sqr(d, c, b[j], ctx); | |
1584 | BN_GF2m_add(d, c, d); | |
1585 | BN_GF2m_mod(e, a, b[j]); | |
0f113f3e MC |
1586 | BN_GF2m_add(e, e, d); |
1587 | /* | |
1588 | * Test that solution of quadratic c satisfies c^2 + c = a. | |
1589 | */ | |
1590 | if (!BN_is_zero(e)) { | |
1591 | fprintf(stderr, | |
1592 | "GF(2^m) modular solve quadratic test failed!\n"); | |
1593 | goto err; | |
1594 | } | |
1595 | ||
0f113f3e MC |
1596 | } |
1597 | } | |
1598 | } | |
1599 | if (s == 0) { | |
1600 | fprintf(stderr, | |
1601 | "All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n", | |
1602 | num0); | |
1603 | fprintf(stderr, | |
1604 | "this is very unlikely and probably indicates an error.\n"); | |
1605 | goto err; | |
1606 | } | |
1607 | ret = 1; | |
1608 | err: | |
1609 | BN_free(a); | |
1610 | BN_free(b[0]); | |
1611 | BN_free(b[1]); | |
1612 | BN_free(c); | |
1613 | BN_free(d); | |
1614 | BN_free(e); | |
1615 | return ret; | |
1616 | } | |
b3310161 | 1617 | #endif |
2aaec9cc | 1618 | static int genprime_cb(int p, int n, BN_GENCB *arg) |
0f113f3e MC |
1619 | { |
1620 | char c = '*'; | |
1621 | ||
1622 | if (p == 0) | |
1623 | c = '.'; | |
1624 | if (p == 1) | |
1625 | c = '+'; | |
1626 | if (p == 2) | |
1627 | c = '*'; | |
1628 | if (p == 3) | |
1629 | c = '\n'; | |
1630 | putc(c, stderr); | |
1631 | fflush(stderr); | |
1632 | return 1; | |
1633 | } | |
bdec3c53 | 1634 | |
c7820896 | 1635 | int test_kron(BIO *bp, BN_CTX *ctx) |
0f113f3e MC |
1636 | { |
1637 | BN_GENCB cb; | |
1638 | BIGNUM *a, *b, *r, *t; | |
1639 | int i; | |
1640 | int legendre, kronecker; | |
1641 | int ret = 0; | |
1642 | ||
1643 | a = BN_new(); | |
1644 | b = BN_new(); | |
1645 | r = BN_new(); | |
1646 | t = BN_new(); | |
1647 | if (a == NULL || b == NULL || r == NULL || t == NULL) | |
1648 | goto err; | |
1649 | ||
1650 | BN_GENCB_set(&cb, genprime_cb, NULL); | |
1651 | ||
1652 | /* | |
1653 | * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In | |
1654 | * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is | |
1655 | * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we | |
1656 | * generate a random prime b and compare these values for a number of | |
1657 | * random a's. (That is, we run the Solovay-Strassen primality test to | |
1658 | * confirm that b is prime, except that we don't want to test whether b | |
1659 | * is prime but whether BN_kronecker works.) | |
1660 | */ | |
1661 | ||
1662 | if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, &cb)) | |
1663 | goto err; | |
1664 | b->neg = rand_neg(); | |
1665 | putc('\n', stderr); | |
1666 | ||
1667 | for (i = 0; i < num0; i++) { | |
1668 | if (!BN_bntest_rand(a, 512, 0, 0)) | |
1669 | goto err; | |
1670 | a->neg = rand_neg(); | |
1671 | ||
1672 | /* t := (|b|-1)/2 (note that b is odd) */ | |
1673 | if (!BN_copy(t, b)) | |
1674 | goto err; | |
1675 | t->neg = 0; | |
1676 | if (!BN_sub_word(t, 1)) | |
1677 | goto err; | |
1678 | if (!BN_rshift1(t, t)) | |
1679 | goto err; | |
1680 | /* r := a^t mod b */ | |
1681 | b->neg = 0; | |
1682 | ||
1683 | if (!BN_mod_exp_recp(r, a, t, b, ctx)) | |
1684 | goto err; | |
1685 | b->neg = 1; | |
1686 | ||
1687 | if (BN_is_word(r, 1)) | |
1688 | legendre = 1; | |
1689 | else if (BN_is_zero(r)) | |
1690 | legendre = 0; | |
1691 | else { | |
1692 | if (!BN_add_word(r, 1)) | |
1693 | goto err; | |
1694 | if (0 != BN_ucmp(r, b)) { | |
1695 | fprintf(stderr, "Legendre symbol computation failed\n"); | |
1696 | goto err; | |
1697 | } | |
1698 | legendre = -1; | |
1699 | } | |
1700 | ||
1701 | kronecker = BN_kronecker(a, b, ctx); | |
1702 | if (kronecker < -1) | |
1703 | goto err; | |
1704 | /* we actually need BN_kronecker(a, |b|) */ | |
1705 | if (a->neg && b->neg) | |
1706 | kronecker = -kronecker; | |
1707 | ||
1708 | if (legendre != kronecker) { | |
1709 | fprintf(stderr, "legendre != kronecker; a = "); | |
1710 | BN_print_fp(stderr, a); | |
1711 | fprintf(stderr, ", b = "); | |
1712 | BN_print_fp(stderr, b); | |
1713 | fprintf(stderr, "\n"); | |
1714 | goto err; | |
1715 | } | |
1716 | ||
1717 | putc('.', stderr); | |
1718 | fflush(stderr); | |
1719 | } | |
1720 | ||
1721 | putc('\n', stderr); | |
1722 | fflush(stderr); | |
1723 | ret = 1; | |
bdec3c53 | 1724 | err: |
23a1d5e9 RS |
1725 | BN_free(a); |
1726 | BN_free(b); | |
1727 | BN_free(r); | |
1728 | BN_free(t); | |
0f113f3e MC |
1729 | return ret; |
1730 | } | |
c7820896 | 1731 | |
cd2eebfd | 1732 | int test_sqrt(BIO *bp, BN_CTX *ctx) |
0f113f3e MC |
1733 | { |
1734 | BN_GENCB cb; | |
1735 | BIGNUM *a, *p, *r; | |
1736 | int i, j; | |
1737 | int ret = 0; | |
1738 | ||
1739 | a = BN_new(); | |
1740 | p = BN_new(); | |
1741 | r = BN_new(); | |
1742 | if (a == NULL || p == NULL || r == NULL) | |
1743 | goto err; | |
1744 | ||
1745 | BN_GENCB_set(&cb, genprime_cb, NULL); | |
1746 | ||
1747 | for (i = 0; i < 16; i++) { | |
1748 | if (i < 8) { | |
1749 | unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 }; | |
1750 | ||
1751 | if (!BN_set_word(p, primes[i])) | |
1752 | goto err; | |
1753 | } else { | |
1754 | if (!BN_set_word(a, 32)) | |
1755 | goto err; | |
1756 | if (!BN_set_word(r, 2 * i + 1)) | |
1757 | goto err; | |
1758 | ||
1759 | if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb)) | |
1760 | goto err; | |
1761 | putc('\n', stderr); | |
1762 | } | |
1763 | p->neg = rand_neg(); | |
1764 | ||
1765 | for (j = 0; j < num2; j++) { | |
1766 | /* | |
1767 | * construct 'a' such that it is a square modulo p, but in | |
1768 | * general not a proper square and not reduced modulo p | |
1769 | */ | |
1770 | if (!BN_bntest_rand(r, 256, 0, 3)) | |
1771 | goto err; | |
1772 | if (!BN_nnmod(r, r, p, ctx)) | |
1773 | goto err; | |
1774 | if (!BN_mod_sqr(r, r, p, ctx)) | |
1775 | goto err; | |
1776 | if (!BN_bntest_rand(a, 256, 0, 3)) | |
1777 | goto err; | |
1778 | if (!BN_nnmod(a, a, p, ctx)) | |
1779 | goto err; | |
1780 | if (!BN_mod_sqr(a, a, p, ctx)) | |
1781 | goto err; | |
1782 | if (!BN_mul(a, a, r, ctx)) | |
1783 | goto err; | |
1784 | if (rand_neg()) | |
1785 | if (!BN_sub(a, a, p)) | |
1786 | goto err; | |
1787 | ||
1788 | if (!BN_mod_sqrt(r, a, p, ctx)) | |
1789 | goto err; | |
1790 | if (!BN_mod_sqr(r, r, p, ctx)) | |
1791 | goto err; | |
1792 | ||
1793 | if (!BN_nnmod(a, a, p, ctx)) | |
1794 | goto err; | |
1795 | ||
1796 | if (BN_cmp(a, r) != 0) { | |
1797 | fprintf(stderr, "BN_mod_sqrt failed: a = "); | |
1798 | BN_print_fp(stderr, a); | |
1799 | fprintf(stderr, ", r = "); | |
1800 | BN_print_fp(stderr, r); | |
1801 | fprintf(stderr, ", p = "); | |
1802 | BN_print_fp(stderr, p); | |
1803 | fprintf(stderr, "\n"); | |
1804 | goto err; | |
1805 | } | |
1806 | ||
1807 | putc('.', stderr); | |
1808 | fflush(stderr); | |
1809 | } | |
1810 | ||
1811 | putc('\n', stderr); | |
1812 | fflush(stderr); | |
1813 | } | |
1814 | ret = 1; | |
cd2eebfd | 1815 | err: |
23a1d5e9 RS |
1816 | BN_free(a); |
1817 | BN_free(p); | |
1818 | BN_free(r); | |
0f113f3e MC |
1819 | return ret; |
1820 | } | |
1821 | ||
1822 | int test_small_prime(BIO *bp, BN_CTX *ctx) | |
1823 | { | |
1824 | static const int bits = 10; | |
1825 | int ret = 0; | |
1826 | BIGNUM *r; | |
1827 | ||
1828 | r = BN_new(); | |
1829 | if (!BN_generate_prime_ex(r, bits, 0, NULL, NULL, NULL)) | |
1830 | goto err; | |
1831 | if (BN_num_bits(r) != bits) { | |
1832 | BIO_printf(bp, "Expected %d bit prime, got %d bit number\n", bits, | |
1833 | BN_num_bits(r)); | |
1834 | goto err; | |
1835 | } | |
1836 | ||
1837 | ret = 1; | |
1838 | ||
1839 | err: | |
1840 | BN_clear_free(r); | |
1841 | return ret; | |
1842 | } | |
1843 | ||
ecb9966e | 1844 | #ifndef OPENSSL_SYS_WIN32 |
8927c278 | 1845 | int test_probable_prime_coprime(BIO *bp, BN_CTX *ctx) |
0f113f3e MC |
1846 | { |
1847 | int i, j, ret = 0; | |
1848 | BIGNUM *r; | |
1849 | BN_ULONG primes[5] = { 2, 3, 5, 7, 11 }; | |
1850 | ||
1851 | r = BN_new(); | |
1852 | ||
1853 | for (i = 0; i < 1000; i++) { | |
1854 | if (!bn_probable_prime_dh_coprime(r, 1024, ctx)) | |
1855 | goto err; | |
1856 | ||
1857 | for (j = 0; j < 5; j++) { | |
1858 | if (BN_mod_word(r, primes[j]) == 0) { | |
8b68b7e9 BL |
1859 | BIO_printf(bp, "Number generated is not coprime to " |
1860 | BN_DEC_FMT1 ":\n", primes[j]); | |
0f113f3e MC |
1861 | BN_print_fp(stdout, r); |
1862 | BIO_printf(bp, "\n"); | |
1863 | goto err; | |
1864 | } | |
1865 | } | |
1866 | } | |
1867 | ||
1868 | ret = 1; | |
1869 | ||
1870 | err: | |
1871 | BN_clear_free(r); | |
1872 | return ret; | |
1873 | } | |
ecb9966e | 1874 | #endif |
0f113f3e MC |
1875 | int test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_) |
1876 | { | |
1877 | BIGNUM *a, *b, *c, *d; | |
1878 | int i; | |
1879 | ||
1880 | b = BN_new(); | |
1881 | c = BN_new(); | |
1882 | d = BN_new(); | |
1883 | BN_one(c); | |
1884 | ||
1885 | if (a_) | |
1886 | a = a_; | |
1887 | else { | |
1888 | a = BN_new(); | |
1889 | BN_bntest_rand(a, 200, 0, 0); | |
1890 | a->neg = rand_neg(); | |
1891 | } | |
1892 | for (i = 0; i < num0; i++) { | |
1893 | BN_lshift(b, a, i + 1); | |
1894 | BN_add(c, c, c); | |
1895 | if (bp != NULL) { | |
1896 | if (!results) { | |
1897 | BN_print(bp, a); | |
1898 | BIO_puts(bp, " * "); | |
1899 | BN_print(bp, c); | |
1900 | BIO_puts(bp, " - "); | |
1901 | } | |
1902 | BN_print(bp, b); | |
1903 | BIO_puts(bp, "\n"); | |
1904 | } | |
1905 | BN_mul(d, a, c, ctx); | |
1906 | BN_sub(d, d, b); | |
1907 | if (!BN_is_zero(d)) { | |
1908 | fprintf(stderr, "Left shift test failed!\n"); | |
1909 | fprintf(stderr, "a="); | |
1910 | BN_print_fp(stderr, a); | |
1911 | fprintf(stderr, "\nb="); | |
1912 | BN_print_fp(stderr, b); | |
1913 | fprintf(stderr, "\nc="); | |
1914 | BN_print_fp(stderr, c); | |
1915 | fprintf(stderr, "\nd="); | |
1916 | BN_print_fp(stderr, d); | |
1917 | fprintf(stderr, "\n"); | |
1918 | return 0; | |
1919 | } | |
1920 | } | |
1921 | BN_free(a); | |
1922 | BN_free(b); | |
1923 | BN_free(c); | |
1924 | BN_free(d); | |
1925 | return (1); | |
1926 | } | |
d02b48c6 | 1927 | |
6b691a5c | 1928 | int test_lshift1(BIO *bp) |
0f113f3e MC |
1929 | { |
1930 | BIGNUM *a, *b, *c; | |
1931 | int i; | |
1932 | ||
1933 | a = BN_new(); | |
1934 | b = BN_new(); | |
1935 | c = BN_new(); | |
1936 | ||
1937 | BN_bntest_rand(a, 200, 0, 0); | |
1938 | a->neg = rand_neg(); | |
1939 | for (i = 0; i < num0; i++) { | |
1940 | BN_lshift1(b, a); | |
1941 | if (bp != NULL) { | |
1942 | if (!results) { | |
1943 | BN_print(bp, a); | |
1944 | BIO_puts(bp, " * 2"); | |
1945 | BIO_puts(bp, " - "); | |
1946 | } | |
1947 | BN_print(bp, b); | |
1948 | BIO_puts(bp, "\n"); | |
1949 | } | |
1950 | BN_add(c, a, a); | |
1951 | BN_sub(a, b, c); | |
1952 | if (!BN_is_zero(a)) { | |
1953 | fprintf(stderr, "Left shift one test failed!\n"); | |
1954 | return 0; | |
1955 | } | |
1956 | ||
1957 | BN_copy(a, b); | |
1958 | } | |
1959 | BN_free(a); | |
1960 | BN_free(b); | |
1961 | BN_free(c); | |
1962 | return (1); | |
1963 | } | |
1964 | ||
1965 | int test_rshift(BIO *bp, BN_CTX *ctx) | |
1966 | { | |
1967 | BIGNUM *a, *b, *c, *d, *e; | |
1968 | int i; | |
1969 | ||
1970 | a = BN_new(); | |
1971 | b = BN_new(); | |
1972 | c = BN_new(); | |
1973 | d = BN_new(); | |
1974 | e = BN_new(); | |
1975 | BN_one(c); | |
1976 | ||
1977 | BN_bntest_rand(a, 200, 0, 0); | |
1978 | a->neg = rand_neg(); | |
1979 | for (i = 0; i < num0; i++) { | |
1980 | BN_rshift(b, a, i + 1); | |
1981 | BN_add(c, c, c); | |
1982 | if (bp != NULL) { | |
1983 | if (!results) { | |
1984 | BN_print(bp, a); | |
1985 | BIO_puts(bp, " / "); | |
1986 | BN_print(bp, c); | |
1987 | BIO_puts(bp, " - "); | |
1988 | } | |
1989 | BN_print(bp, b); | |
1990 | BIO_puts(bp, "\n"); | |
1991 | } | |
1992 | BN_div(d, e, a, c, ctx); | |
1993 | BN_sub(d, d, b); | |
1994 | if (!BN_is_zero(d)) { | |
1995 | fprintf(stderr, "Right shift test failed!\n"); | |
1996 | return 0; | |
1997 | } | |
1998 | } | |
1999 | BN_free(a); | |
2000 | BN_free(b); | |
2001 | BN_free(c); | |
2002 | BN_free(d); | |
2003 | BN_free(e); | |
2004 | return (1); | |
2005 | } | |
d02b48c6 | 2006 | |
6b691a5c | 2007 | int test_rshift1(BIO *bp) |
0f113f3e MC |
2008 | { |
2009 | BIGNUM *a, *b, *c; | |
2010 | int i; | |
2011 | ||
2012 | a = BN_new(); | |
2013 | b = BN_new(); | |
2014 | c = BN_new(); | |
2015 | ||
2016 | BN_bntest_rand(a, 200, 0, 0); | |
2017 | a->neg = rand_neg(); | |
2018 | for (i = 0; i < num0; i++) { | |
2019 | BN_rshift1(b, a); | |
2020 | if (bp != NULL) { | |
2021 | if (!results) { | |
2022 | BN_print(bp, a); | |
2023 | BIO_puts(bp, " / 2"); | |
2024 | BIO_puts(bp, " - "); | |
2025 | } | |
2026 | BN_print(bp, b); | |
2027 | BIO_puts(bp, "\n"); | |
2028 | } | |
2029 | BN_sub(c, a, b); | |
2030 | BN_sub(c, c, b); | |
2031 | if (!BN_is_zero(c) && !BN_abs_is_word(c, 1)) { | |
2032 | fprintf(stderr, "Right shift one test failed!\n"); | |
2033 | return 0; | |
2034 | } | |
2035 | BN_copy(a, b); | |
2036 | } | |
2037 | BN_free(a); | |
2038 | BN_free(b); | |
2039 | BN_free(c); | |
2040 | return (1); | |
2041 | } | |
d02b48c6 | 2042 | |
6b691a5c | 2043 | int rand_neg(void) |
0f113f3e MC |
2044 | { |
2045 | static unsigned int neg = 0; | |
2046 | static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 }; | |
d02b48c6 | 2047 | |
0f113f3e MC |
2048 | return (sign[(neg++) % 8]); |
2049 | } |