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