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