1/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
2 * All rights reserved.
3 *
4 * This package is an SSL implementation written
5 * by Eric Young (eay@cryptsoft.com).
6 * The implementation was written so as to conform with Netscapes SSL.
7 *
8 * This library is free for commercial and non-commercial use as long as
9 * the following conditions are aheared to.  The following conditions
10 * apply to all code found in this distribution, be it the RC4, RSA,
11 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
12 * included with this distribution is covered by the same copyright terms
13 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
14 *
15 * Copyright remains Eric Young's, and as such any Copyright notices in
16 * the code are not to be removed.
17 * If this package is used in a product, Eric Young should be given attribution
18 * as the author of the parts of the library used.
19 * This can be in the form of a textual message at program startup or
20 * in documentation (online or textual) provided with the package.
21 *
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
24 * are met:
25 * 1. Redistributions of source code must retain the copyright
26 *    notice, this list of conditions and the following disclaimer.
27 * 2. Redistributions in binary form must reproduce the above copyright
28 *    notice, this list of conditions and the following disclaimer in the
29 *    documentation and/or other materials provided with the distribution.
30 * 3. All advertising materials mentioning features or use of this software
31 *    must display the following acknowledgement:
32 *    "This product includes cryptographic software written by
33 *     Eric Young (eay@cryptsoft.com)"
34 *    The word 'cryptographic' can be left out if the rouines from the library
35 *    being used are not cryptographic related :-).
36 * 4. If you include any Windows specific code (or a derivative thereof) from
37 *    the apps directory (application code) you must include an acknowledgement:
38 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
39 *
40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50 * SUCH DAMAGE.
51 *
52 * The licence and distribution terms for any publically available version or
53 * derivative of this code cannot be changed.  i.e. this code cannot simply be
54 * copied and put under another distribution licence
55 * [including the GNU Public Licence.]
56 */
57/* ====================================================================
58 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
59 *
60 * Portions of the attached software ("Contribution") are developed by
61 * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
62 *
63 * The Contribution is licensed pursuant to the Eric Young open source
64 * license provided above.
65 *
66 * The binary polynomial arithmetic software is originally written by
67 * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems
68 * Laboratories. */
69
70#include <stdio.h>
71
72#include <openssl/bio.h>
73#include <openssl/bn.h>
74#include <openssl/crypto.h>
75#include <openssl/err.h>
76#include <openssl/mem.h>
77
78#include "internal.h"
79
80static const int num0 = 100; /* number of tests */
81static const int num1 = 50;  /* additional tests for some functions */
82static const int num2 = 5;   /* number of tests for slow functions */
83
84int test_add(BIO *bp);
85int test_sub(BIO *bp);
86int test_lshift1(BIO *bp);
87int test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_);
88int test_rshift1(BIO *bp);
89int test_rshift(BIO *bp, BN_CTX *ctx);
90int test_sqr(BIO *bp, BN_CTX *ctx);
91int test_mul(BIO *bp);
92int test_div(BIO *bp, BN_CTX *ctx);
93int rand_neg(void);
94
95int test_div_word(BIO *bp);
96int test_mont(BIO *bp, BN_CTX *ctx);
97int test_mod(BIO *bp, BN_CTX *ctx);
98int test_mod_mul(BIO *bp, BN_CTX *ctx);
99int test_mod_exp(BIO *bp, BN_CTX *ctx);
100int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx);
101int test_exp(BIO *bp, BN_CTX *ctx);
102int test_mod_sqrt(BIO *bp, BN_CTX *ctx);
103static int test_exp_mod_zero(void);
104int test_small_prime(BIO *bp,BN_CTX *ctx);
105int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx);
106int test_sqrt(BIO *bp, BN_CTX *ctx);
107int test_bn2bin_padded(BIO *bp, BN_CTX *ctx);
108#if 0
109int test_gf2m_add(BIO *bp);
110int test_gf2m_mod(BIO *bp);
111int test_gf2m_mod_mul(BIO *bp, BN_CTX *ctx);
112int test_gf2m_mod_sqr(BIO *bp, BN_CTX *ctx);
113int test_gf2m_mod_inv(BIO *bp, BN_CTX *ctx);
114int test_gf2m_mod_div(BIO *bp, BN_CTX *ctx);
115int test_gf2m_mod_exp(BIO *bp, BN_CTX *ctx);
116int test_gf2m_mod_sqrt(BIO *bp, BN_CTX *ctx);
117int test_gf2m_mod_solve_quad(BIO *bp, BN_CTX *ctx);
118#endif
119static int results = 0;
120
121static unsigned char lst[] =
122    "\xC6\x4F\x43\x04\x2A\xEA\xCA\x6E\x58\x36\x80\x5B\xE8\xC9"
123    "\x9B\x04\x5D\x48\x36\xC2\xFD\x16\xC9\x64\xF0";
124
125static void ERR_print_errors_fp(FILE *out) {
126}
127
128static void message(BIO *out, char *m) {
129  BIO_puts(out, "print \"test ");
130  BIO_puts(out, m);
131  BIO_puts(out, "\\n\"\n");
132}
133
134int main(int argc, char *argv[]) {
135  BN_CTX *ctx;
136  BIO *out = NULL;
137  char *outfile = NULL;
138
139  CRYPTO_library_init();
140
141  results = 0;
142
143  argc--;
144  argv++;
145  while (argc >= 1) {
146    if (strcmp(*argv, "-results") == 0)
147      results = 1;
148    else if (strcmp(*argv, "-out") == 0) {
149      if (--argc < 1)
150        break;
151      outfile = *(++argv);
152    }
153    argc--;
154    argv++;
155  }
156
157
158  ctx = BN_CTX_new();
159  if (ctx == NULL)
160    return 1;
161
162  out = BIO_new(BIO_s_file());
163  if (out == NULL) {
164    return 1;
165  }
166
167  if (outfile == NULL) {
168    BIO_set_fp(out, stdout, BIO_NOCLOSE);
169  } else {
170    if (!BIO_write_filename(out, outfile)) {
171      perror(outfile);
172      return 1;
173    }
174  }
175
176  if (!results)
177    BIO_puts(out, "obase=16\nibase=16\n");
178
179  message(out, "BN_add");
180  if (!test_add(out))
181    goto err;
182  (void)BIO_flush(out);
183
184  message(out, "BN_sub");
185  if (!test_sub(out))
186    goto err;
187  (void)BIO_flush(out);
188
189  message(out, "BN_lshift1");
190  if (!test_lshift1(out))
191    goto err;
192  (void)BIO_flush(out);
193
194  message(out, "BN_lshift (fixed)");
195  if (!test_lshift(out, ctx, BN_bin2bn(lst, sizeof(lst) - 1, NULL)))
196    goto err;
197  (void)BIO_flush(out);
198
199  message(out, "BN_lshift");
200  if (!test_lshift(out, ctx, NULL))
201    goto err;
202  (void)BIO_flush(out);
203
204  message(out, "BN_rshift1");
205  if (!test_rshift1(out))
206    goto err;
207  (void)BIO_flush(out);
208
209  message(out, "BN_rshift");
210  if (!test_rshift(out, ctx))
211    goto err;
212  (void)BIO_flush(out);
213
214  message(out, "BN_sqr");
215  if (!test_sqr(out, ctx))
216    goto err;
217  (void)BIO_flush(out);
218
219  message(out, "BN_mul");
220  if (!test_mul(out))
221    goto err;
222  (void)BIO_flush(out);
223
224  message(out, "BN_div");
225  if (!test_div(out, ctx))
226    goto err;
227  (void)BIO_flush(out);
228
229  message(out, "BN_div_word");
230  if (!test_div_word(out))
231    goto err;
232  (void)BIO_flush(out);
233
234  message(out, "BN_mod");
235  if (!test_mod(out, ctx))
236    goto err;
237  (void)BIO_flush(out);
238
239  message(out, "BN_mod_mul");
240  if (!test_mod_mul(out, ctx))
241    goto err;
242  (void)BIO_flush(out);
243
244  message(out, "BN_mont");
245  if (!test_mont(out, ctx))
246    goto err;
247  (void)BIO_flush(out);
248
249  message(out, "BN_mod_exp");
250  if (!test_mod_exp(out, ctx))
251    goto err;
252  (void)BIO_flush(out);
253
254  message(out, "BN_mod_exp_mont_consttime");
255  if (!test_mod_exp_mont_consttime(out, ctx) ||
256      !test_mod_exp_mont5(out, ctx)) {
257    goto err;
258  }
259  (void)BIO_flush(out);
260
261  message(out, "BN_exp");
262  if (!test_exp(out, ctx) ||
263      !test_exp_mod_zero()) {
264    goto err;
265  }
266  (void)BIO_flush(out);
267
268  message(out, "BN_mod_sqrt");
269  if (!test_mod_sqrt(out, ctx))
270    goto err;
271  (void)BIO_flush(out);
272
273  message(out, "Small prime generation");
274  if (!test_small_prime(out, ctx))
275    goto err;
276  (void)BIO_flush(out);
277
278  message(out, "BN_sqrt");
279  if (!test_sqrt(out, ctx))
280    goto err;
281  (void)BIO_flush(out);
282
283  message(out, "BN_bn2bin_padded");
284  if (!test_bn2bin_padded(out, ctx))
285    goto err;
286  (void)BIO_flush(out);
287
288  BN_CTX_free(ctx);
289  BIO_free(out);
290
291  printf("PASS\n");
292  return 0;
293
294err:
295  BIO_puts(out, "1\n"); /* make sure the Perl script fed by bc notices
296                         * the failure, see test_bn in test/Makefile.ssl*/
297  (void)BIO_flush(out);
298
299  return 1;
300}
301
302int test_add(BIO *bp) {
303  BIGNUM a, b, c;
304  int i;
305
306  BN_init(&a);
307  BN_init(&b);
308  BN_init(&c);
309
310  BN_rand(&a, 512, 0, 0);
311  for (i = 0; i < num0; i++) {
312    BN_rand(&b, 450 + i, 0, 0);
313    a.neg = rand_neg();
314    b.neg = rand_neg();
315    BN_add(&c, &a, &b);
316    if (bp != NULL) {
317      if (!results) {
318        BN_print(bp, &a);
319        BIO_puts(bp, " + ");
320        BN_print(bp, &b);
321        BIO_puts(bp, " - ");
322      }
323      BN_print(bp, &c);
324      BIO_puts(bp, "\n");
325    }
326    a.neg = !a.neg;
327    b.neg = !b.neg;
328    BN_add(&c, &c, &b);
329    BN_add(&c, &c, &a);
330    if (!BN_is_zero(&c)) {
331      fprintf(stderr, "Add test failed!\n");
332      return 0;
333    }
334  }
335  BN_free(&a);
336  BN_free(&b);
337  BN_free(&c);
338  return (1);
339}
340
341int test_sub(BIO *bp) {
342  BIGNUM a, b, c;
343  int i;
344
345  BN_init(&a);
346  BN_init(&b);
347  BN_init(&c);
348
349  for (i = 0; i < num0 + num1; i++) {
350    if (i < num1) {
351      BN_rand(&a, 512, 0, 0);
352      BN_copy(&b, &a);
353      if (BN_set_bit(&a, i) == 0)
354        return (0);
355      BN_add_word(&b, i);
356    } else {
357      BN_rand(&b, 400 + i - num1, 0, 0);
358      a.neg = rand_neg();
359      b.neg = rand_neg();
360    }
361    BN_sub(&c, &a, &b);
362    if (bp != NULL) {
363      if (!results) {
364        BN_print(bp, &a);
365        BIO_puts(bp, " - ");
366        BN_print(bp, &b);
367        BIO_puts(bp, " - ");
368      }
369      BN_print(bp, &c);
370      BIO_puts(bp, "\n");
371    }
372    BN_add(&c, &c, &b);
373    BN_sub(&c, &c, &a);
374    if (!BN_is_zero(&c)) {
375      fprintf(stderr, "Subtract test failed!\n");
376      return 0;
377    }
378  }
379  BN_free(&a);
380  BN_free(&b);
381  BN_free(&c);
382  return (1);
383}
384
385int test_div(BIO *bp, BN_CTX *ctx) {
386  BIGNUM a, b, c, d, e;
387  int i;
388
389  BN_init(&a);
390  BN_init(&b);
391  BN_init(&c);
392  BN_init(&d);
393  BN_init(&e);
394
395  for (i = 0; i < num0 + num1; i++) {
396    if (i < num1) {
397      BN_rand(&a, 400, 0, 0);
398      BN_copy(&b, &a);
399      BN_lshift(&a, &a, i);
400      BN_add_word(&a, i);
401    } else
402      BN_rand(&b, 50 + 3 * (i - num1), 0, 0);
403    a.neg = rand_neg();
404    b.neg = rand_neg();
405    BN_div(&d, &c, &a, &b, ctx);
406    if (bp != NULL) {
407      if (!results) {
408        BN_print(bp, &a);
409        BIO_puts(bp, " / ");
410        BN_print(bp, &b);
411        BIO_puts(bp, " - ");
412      }
413      BN_print(bp, &d);
414      BIO_puts(bp, "\n");
415
416      if (!results) {
417        BN_print(bp, &a);
418        BIO_puts(bp, " % ");
419        BN_print(bp, &b);
420        BIO_puts(bp, " - ");
421      }
422      BN_print(bp, &c);
423      BIO_puts(bp, "\n");
424    }
425    BN_mul(&e, &d, &b, ctx);
426    BN_add(&d, &e, &c);
427    BN_sub(&d, &d, &a);
428    if (!BN_is_zero(&d)) {
429      fprintf(stderr, "Division test failed!\n");
430      return 0;
431    }
432  }
433  BN_free(&a);
434  BN_free(&b);
435  BN_free(&c);
436  BN_free(&d);
437  BN_free(&e);
438  return (1);
439}
440
441int test_lshift1(BIO *bp) {
442  BIGNUM *a, *b, *c;
443  int i;
444
445  a = BN_new();
446  b = BN_new();
447  c = BN_new();
448
449  BN_rand(a, 200, 0, 0); /**/
450  a->neg = rand_neg();
451  for (i = 0; i < num0; i++) {
452    BN_lshift1(b, a);
453    if (bp != NULL) {
454      if (!results) {
455        BN_print(bp, a);
456        BIO_puts(bp, " * 2");
457        BIO_puts(bp, " - ");
458      }
459      BN_print(bp, b);
460      BIO_puts(bp, "\n");
461    }
462    BN_add(c, a, a);
463    BN_sub(a, b, c);
464    if (!BN_is_zero(a)) {
465      fprintf(stderr, "Left shift one test failed!\n");
466      return 0;
467    }
468
469    BN_copy(a, b);
470  }
471  BN_free(a);
472  BN_free(b);
473  BN_free(c);
474  return (1);
475}
476
477int test_rshift(BIO *bp, BN_CTX *ctx) {
478  BIGNUM *a, *b, *c, *d, *e;
479  int i;
480
481  a = BN_new();
482  b = BN_new();
483  c = BN_new();
484  d = BN_new();
485  e = BN_new();
486  BN_one(c);
487
488  BN_rand(a, 200, 0, 0); /**/
489  a->neg = rand_neg();
490  for (i = 0; i < num0; i++) {
491    BN_rshift(b, a, i + 1);
492    BN_add(c, c, c);
493    if (bp != NULL) {
494      if (!results) {
495        BN_print(bp, a);
496        BIO_puts(bp, " / ");
497        BN_print(bp, c);
498        BIO_puts(bp, " - ");
499      }
500      BN_print(bp, b);
501      BIO_puts(bp, "\n");
502    }
503    BN_div(d, e, a, c, ctx);
504    BN_sub(d, d, b);
505    if (!BN_is_zero(d)) {
506      fprintf(stderr, "Right shift test failed!\n");
507      return 0;
508    }
509  }
510  BN_free(a);
511  BN_free(b);
512  BN_free(c);
513  BN_free(d);
514  BN_free(e);
515  return (1);
516}
517
518int test_rshift1(BIO *bp) {
519  BIGNUM *a, *b, *c;
520  int i;
521
522  a = BN_new();
523  b = BN_new();
524  c = BN_new();
525
526  BN_rand(a, 200, 0, 0); /**/
527  a->neg = rand_neg();
528  for (i = 0; i < num0; i++) {
529    BN_rshift1(b, a);
530    if (bp != NULL) {
531      if (!results) {
532        BN_print(bp, a);
533        BIO_puts(bp, " / 2");
534        BIO_puts(bp, " - ");
535      }
536      BN_print(bp, b);
537      BIO_puts(bp, "\n");
538    }
539    BN_sub(c, a, b);
540    BN_sub(c, c, b);
541    if (!BN_is_zero(c) && !BN_abs_is_word(c, 1)) {
542      fprintf(stderr, "Right shift one test failed!\n");
543      return 0;
544    }
545    BN_copy(a, b);
546  }
547  BN_free(a);
548  BN_free(b);
549  BN_free(c);
550  return (1);
551}
552
553int test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_) {
554  BIGNUM *a, *b, *c, *d;
555  int i;
556
557  b = BN_new();
558  c = BN_new();
559  d = BN_new();
560  BN_one(c);
561
562  if (a_)
563    a = a_;
564  else {
565    a = BN_new();
566    BN_rand(a, 200, 0, 0); /**/
567    a->neg = rand_neg();
568  }
569  for (i = 0; i < num0; i++) {
570    BN_lshift(b, a, i + 1);
571    BN_add(c, c, c);
572    if (bp != NULL) {
573      if (!results) {
574        BN_print(bp, a);
575        BIO_puts(bp, " * ");
576        BN_print(bp, c);
577        BIO_puts(bp, " - ");
578      }
579      BN_print(bp, b);
580      BIO_puts(bp, "\n");
581    }
582    BN_mul(d, a, c, ctx);
583    BN_sub(d, d, b);
584    if (!BN_is_zero(d)) {
585      fprintf(stderr, "Left shift test failed!\n");
586      fprintf(stderr, "a=");
587      BN_print_fp(stderr, a);
588      fprintf(stderr, "\nb=");
589      BN_print_fp(stderr, b);
590      fprintf(stderr, "\nc=");
591      BN_print_fp(stderr, c);
592      fprintf(stderr, "\nd=");
593      BN_print_fp(stderr, d);
594      fprintf(stderr, "\n");
595      return 0;
596    }
597  }
598  BN_free(a);
599  BN_free(b);
600  BN_free(c);
601  BN_free(d);
602  return (1);
603}
604
605int test_mul(BIO *bp) {
606  BIGNUM a, b, c, d, e;
607  int i;
608  BN_CTX *ctx;
609
610  ctx = BN_CTX_new();
611  if (ctx == NULL)
612    abort();
613
614  BN_init(&a);
615  BN_init(&b);
616  BN_init(&c);
617  BN_init(&d);
618  BN_init(&e);
619
620  for (i = 0; i < num0 + num1; i++) {
621    if (i <= num1) {
622      BN_rand(&a, 100, 0, 0);
623      BN_rand(&b, 100, 0, 0);
624    } else
625      BN_rand(&b, i - num1, 0, 0);
626    a.neg = rand_neg();
627    b.neg = rand_neg();
628    BN_mul(&c, &a, &b, ctx);
629    if (bp != NULL) {
630      if (!results) {
631        BN_print(bp, &a);
632        BIO_puts(bp, " * ");
633        BN_print(bp, &b);
634        BIO_puts(bp, " - ");
635      }
636      BN_print(bp, &c);
637      BIO_puts(bp, "\n");
638    }
639    BN_div(&d, &e, &c, &a, ctx);
640    BN_sub(&d, &d, &b);
641    if (!BN_is_zero(&d) || !BN_is_zero(&e)) {
642      fprintf(stderr, "Multiplication test failed!\n");
643      return 0;
644    }
645  }
646  BN_free(&a);
647  BN_free(&b);
648  BN_free(&c);
649  BN_free(&d);
650  BN_free(&e);
651  BN_CTX_free(ctx);
652  return (1);
653}
654
655int test_sqr(BIO *bp, BN_CTX *ctx) {
656  BIGNUM a, c, d, e;
657  int i;
658
659  BN_init(&a);
660  BN_init(&c);
661  BN_init(&d);
662  BN_init(&e);
663
664  for (i = 0; i < num0; i++) {
665    BN_rand(&a, 40 + i * 10, 0, 0);
666    a.neg = rand_neg();
667    BN_sqr(&c, &a, ctx);
668    if (bp != NULL) {
669      if (!results) {
670        BN_print(bp, &a);
671        BIO_puts(bp, " * ");
672        BN_print(bp, &a);
673        BIO_puts(bp, " - ");
674      }
675      BN_print(bp, &c);
676      BIO_puts(bp, "\n");
677    }
678    BN_div(&d, &e, &c, &a, ctx);
679    BN_sub(&d, &d, &a);
680    if (!BN_is_zero(&d) || !BN_is_zero(&e)) {
681      fprintf(stderr, "Square test failed!\n");
682      return 0;
683    }
684  }
685  BN_free(&a);
686  BN_free(&c);
687  BN_free(&d);
688  BN_free(&e);
689  return (1);
690}
691
692
693int rand_neg(void) {
694  static unsigned int neg = 0;
695  static int sign[8] = {0, 0, 0, 1, 1, 0, 1, 1};
696
697  return (sign[(neg++) % 8]);
698}
699
700static void print_word(BIO *bp, BN_ULONG w) {
701  BIO_printf(bp, BN_HEX_FMT1, w);
702}
703
704int test_div_word(BIO *bp) {
705  BIGNUM a, b;
706  BN_ULONG r, s;
707  int i;
708
709  BN_init(&a);
710  BN_init(&b);
711
712  for (i = 0; i < num0; i++) {
713    do {
714      BN_rand(&a, 512, -1, 0);
715      BN_rand(&b, BN_BITS2, -1, 0);
716      s = b.d[0];
717    } while (!s);
718
719    BN_copy(&b, &a);
720    r = BN_div_word(&b, s);
721
722    if (bp != NULL) {
723      if (!results) {
724        BN_print(bp, &a);
725        BIO_puts(bp, " / ");
726        print_word(bp, s);
727        BIO_puts(bp, " - ");
728      }
729      BN_print(bp, &b);
730      BIO_puts(bp, "\n");
731
732      if (!results) {
733        BN_print(bp, &a);
734        BIO_puts(bp, " % ");
735        print_word(bp, s);
736        BIO_puts(bp, " - ");
737      }
738      print_word(bp, r);
739      BIO_puts(bp, "\n");
740    }
741    BN_mul_word(&b, s);
742    BN_add_word(&b, r);
743    BN_sub(&b, &a, &b);
744    if (!BN_is_zero(&b)) {
745      fprintf(stderr, "Division (word) test failed!\n");
746      return 0;
747    }
748  }
749  BN_free(&a);
750  BN_free(&b);
751  return (1);
752}
753
754int test_mont(BIO *bp, BN_CTX *ctx) {
755  BIGNUM a, b, c, d, A, B;
756  BIGNUM n;
757  int i;
758  BN_MONT_CTX *mont;
759
760  BN_init(&a);
761  BN_init(&b);
762  BN_init(&c);
763  BN_init(&d);
764  BN_init(&A);
765  BN_init(&B);
766  BN_init(&n);
767
768  mont = BN_MONT_CTX_new();
769  if (mont == NULL)
770    return 0;
771
772  BN_rand(&a, 100, 0, 0); /**/
773  BN_rand(&b, 100, 0, 0); /**/
774  for (i = 0; i < num2; i++) {
775    int bits = (200 * (i + 1)) / num2;
776
777    if (bits == 0)
778      continue;
779    BN_rand(&n, bits, 0, 1);
780    BN_MONT_CTX_set(mont, &n, ctx);
781
782    BN_nnmod(&a, &a, &n, ctx);
783    BN_nnmod(&b, &b, &n, ctx);
784
785    BN_to_montgomery(&A, &a, mont, ctx);
786    BN_to_montgomery(&B, &b, mont, ctx);
787
788    BN_mod_mul_montgomery(&c, &A, &B, mont, ctx); /**/
789    BN_from_montgomery(&A, &c, mont, ctx);        /**/
790    if (bp != NULL) {
791      if (!results) {
792#ifdef undef
793        fprintf(stderr, "%d * %d %% %d\n", BN_num_bits(&a), BN_num_bits(&b),
794                BN_num_bits(mont->N));
795#endif
796        BN_print(bp, &a);
797        BIO_puts(bp, " * ");
798        BN_print(bp, &b);
799        BIO_puts(bp, " % ");
800        BN_print(bp, &(mont->N));
801        BIO_puts(bp, " - ");
802      }
803      BN_print(bp, &A);
804      BIO_puts(bp, "\n");
805    }
806    BN_mod_mul(&d, &a, &b, &n, ctx);
807    BN_sub(&d, &d, &A);
808    if (!BN_is_zero(&d)) {
809      fprintf(stderr, "Montgomery multiplication test failed!\n");
810      return 0;
811    }
812  }
813  BN_MONT_CTX_free(mont);
814  BN_free(&a);
815  BN_free(&b);
816  BN_free(&c);
817  BN_free(&d);
818  BN_free(&A);
819  BN_free(&B);
820  BN_free(&n);
821  return (1);
822}
823
824int test_mod(BIO *bp, BN_CTX *ctx) {
825  BIGNUM *a, *b, *c, *d, *e;
826  int i;
827
828  a = BN_new();
829  b = BN_new();
830  c = BN_new();
831  d = BN_new();
832  e = BN_new();
833
834  BN_rand(a, 1024, 0, 0); /**/
835  for (i = 0; i < num0; i++) {
836    BN_rand(b, 450 + i * 10, 0, 0); /**/
837    a->neg = rand_neg();
838    b->neg = rand_neg();
839    BN_mod(c, a, b, ctx); /**/
840    if (bp != NULL) {
841      if (!results) {
842        BN_print(bp, a);
843        BIO_puts(bp, " % ");
844        BN_print(bp, b);
845        BIO_puts(bp, " - ");
846      }
847      BN_print(bp, c);
848      BIO_puts(bp, "\n");
849    }
850    BN_div(d, e, a, b, ctx);
851    BN_sub(e, e, c);
852    if (!BN_is_zero(e)) {
853      fprintf(stderr, "Modulo test failed!\n");
854      return 0;
855    }
856  }
857  BN_free(a);
858  BN_free(b);
859  BN_free(c);
860  BN_free(d);
861  BN_free(e);
862  return (1);
863}
864
865int test_mod_mul(BIO *bp, BN_CTX *ctx) {
866  BIGNUM *a, *b, *c, *d, *e;
867  int i, j;
868
869  a = BN_new();
870  b = BN_new();
871  c = BN_new();
872  d = BN_new();
873  e = BN_new();
874
875  for (j = 0; j < 3; j++) {
876    BN_rand(c, 1024, 0, 0); /**/
877    for (i = 0; i < num0; i++) {
878      BN_rand(a, 475 + i * 10, 0, 0); /**/
879      BN_rand(b, 425 + i * 11, 0, 0); /**/
880      a->neg = rand_neg();
881      b->neg = rand_neg();
882      if (!BN_mod_mul(e, a, b, c, ctx)) {
883        unsigned long l;
884
885        while ((l = ERR_get_error()))
886          fprintf(stderr, "ERROR:%s\n", ERR_error_string(l, NULL));
887        abort();
888      }
889      if (bp != NULL) {
890        if (!results) {
891          BN_print(bp, a);
892          BIO_puts(bp, " * ");
893          BN_print(bp, b);
894          BIO_puts(bp, " % ");
895          BN_print(bp, c);
896          if ((a->neg ^ b->neg) && !BN_is_zero(e)) {
897            /* If  (a*b) % c  is negative,  c  must be added
898             * in order to obtain the normalized remainder
899             * (new with OpenSSL 0.9.7, previous versions of
900             * BN_mod_mul could generate negative results)
901             */
902            BIO_puts(bp, " + ");
903            BN_print(bp, c);
904          }
905          BIO_puts(bp, " - ");
906        }
907        BN_print(bp, e);
908        BIO_puts(bp, "\n");
909      }
910      BN_mul(d, a, b, ctx);
911      BN_sub(d, d, e);
912      BN_div(a, b, d, c, ctx);
913      if (!BN_is_zero(b)) {
914        fprintf(stderr, "Modulo multiply test failed!\n");
915        ERR_print_errors_fp(stderr);
916        return 0;
917      }
918    }
919  }
920  BN_free(a);
921  BN_free(b);
922  BN_free(c);
923  BN_free(d);
924  BN_free(e);
925  return (1);
926}
927
928int test_mod_exp(BIO *bp, BN_CTX *ctx) {
929  BIGNUM *a, *b, *c, *d, *e;
930  int i;
931
932  a = BN_new();
933  b = BN_new();
934  c = BN_new();
935  d = BN_new();
936  e = BN_new();
937
938  BN_rand(c, 30, 0, 1); /* must be odd for montgomery */
939  for (i = 0; i < num2; i++) {
940    BN_rand(a, 20 + i * 5, 0, 0); /**/
941    BN_rand(b, 2 + i, 0, 0);      /**/
942
943    if (!BN_mod_exp(d, a, b, c, ctx))
944      return (0);
945
946    if (bp != NULL) {
947      if (!results) {
948        BN_print(bp, a);
949        BIO_puts(bp, " ^ ");
950        BN_print(bp, b);
951        BIO_puts(bp, " % ");
952        BN_print(bp, c);
953        BIO_puts(bp, " - ");
954      }
955      BN_print(bp, d);
956      BIO_puts(bp, "\n");
957    }
958    BN_exp(e, a, b, ctx);
959    BN_sub(e, e, d);
960    BN_div(a, b, e, c, ctx);
961    if (!BN_is_zero(b)) {
962      fprintf(stderr, "Modulo exponentiation test failed!\n");
963      return 0;
964    }
965  }
966  BN_free(a);
967  BN_free(b);
968  BN_free(c);
969  BN_free(d);
970  BN_free(e);
971  return (1);
972}
973
974int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx) {
975  BIGNUM *a, *b, *c, *d, *e;
976  int i;
977
978  a = BN_new();
979  b = BN_new();
980  c = BN_new();
981  d = BN_new();
982  e = BN_new();
983
984  BN_rand(c, 30, 0, 1); /* must be odd for montgomery */
985  for (i = 0; i < num2; i++) {
986    BN_rand(a, 20 + i * 5, 0, 0); /**/
987    BN_rand(b, 2 + i, 0, 0);      /**/
988
989    if (!BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL))
990      return (00);
991
992    if (bp != NULL) {
993      if (!results) {
994        BN_print(bp, a);
995        BIO_puts(bp, " ^ ");
996        BN_print(bp, b);
997        BIO_puts(bp, " % ");
998        BN_print(bp, c);
999        BIO_puts(bp, " - ");
1000      }
1001      BN_print(bp, d);
1002      BIO_puts(bp, "\n");
1003    }
1004    BN_exp(e, a, b, ctx);
1005    BN_sub(e, e, d);
1006    BN_div(a, b, e, c, ctx);
1007    if (!BN_is_zero(b)) {
1008      fprintf(stderr, "Modulo exponentiation test failed!\n");
1009      return 0;
1010    }
1011  }
1012  BN_free(a);
1013  BN_free(b);
1014  BN_free(c);
1015  BN_free(d);
1016  BN_free(e);
1017  return (1);
1018}
1019
1020/* Test constant-time modular exponentiation with 1024-bit inputs,
1021 * which on x86_64 cause a different code branch to be taken. */
1022int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx) {
1023  BIGNUM *a, *p, *m, *d, *e;
1024
1025  BN_MONT_CTX *mont;
1026
1027  a = BN_new();
1028  p = BN_new();
1029  m = BN_new();
1030  d = BN_new();
1031  e = BN_new();
1032
1033  mont = BN_MONT_CTX_new();
1034
1035  BN_rand(m, 1024, 0, 1); /* must be odd for montgomery */
1036  /* Zero exponent */
1037  BN_rand(a, 1024, 0, 0);
1038  BN_zero(p);
1039  if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
1040    return 0;
1041  if (!BN_is_one(d)) {
1042    fprintf(stderr, "Modular exponentiation test failed!\n");
1043    return 0;
1044  }
1045  /* Zero input */
1046  BN_rand(p, 1024, 0, 0);
1047  BN_zero(a);
1048  if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
1049    return 0;
1050  if (!BN_is_zero(d)) {
1051    fprintf(stderr, "Modular exponentiation test failed!\n");
1052    return 0;
1053  }
1054  /* Craft an input whose Montgomery representation is 1,
1055   * i.e., shorter than the modulus m, in order to test
1056   * the const time precomputation scattering/gathering.
1057   */
1058  BN_one(a);
1059  BN_MONT_CTX_set(mont, m, ctx);
1060  if (!BN_from_montgomery(e, a, mont, ctx) ||
1061      !BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL) ||
1062      !BN_mod_exp(a, e, p, m, ctx)) {
1063    return 0;
1064  }
1065  if (BN_cmp(a, d) != 0) {
1066    fprintf(stderr, "Modular exponentiation test failed!\n");
1067    return 0;
1068  }
1069  /* Finally, some regular test vectors. */
1070  BN_rand(e, 1024, 0, 0);
1071  if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
1072    return 0;
1073  if (!BN_mod_exp(a, e, p, m, ctx))
1074    return 0;
1075  if (BN_cmp(a, d) != 0) {
1076    fprintf(stderr, "Modular exponentiation test failed!\n");
1077    return 0;
1078  }
1079
1080  BN_MONT_CTX_free(mont);
1081  BN_free(a);
1082  BN_free(p);
1083  BN_free(m);
1084  BN_free(d);
1085  BN_free(e);
1086  return (1);
1087}
1088
1089int test_exp(BIO *bp, BN_CTX *ctx) {
1090  BIGNUM *a, *b, *d, *e, *one;
1091  int i;
1092
1093  a = BN_new();
1094  b = BN_new();
1095  d = BN_new();
1096  e = BN_new();
1097  one = BN_new();
1098  BN_one(one);
1099
1100  for (i = 0; i < num2; i++) {
1101    BN_rand(a, 20 + i * 5, 0, 0); /**/
1102    BN_rand(b, 2 + i, 0, 0);      /**/
1103
1104    if (BN_exp(d, a, b, ctx) <= 0)
1105      return (0);
1106
1107    if (bp != NULL) {
1108      if (!results) {
1109        BN_print(bp, a);
1110        BIO_puts(bp, " ^ ");
1111        BN_print(bp, b);
1112        BIO_puts(bp, " - ");
1113      }
1114      BN_print(bp, d);
1115      BIO_puts(bp, "\n");
1116    }
1117    BN_one(e);
1118    for (; !BN_is_zero(b); BN_sub(b, b, one))
1119      BN_mul(e, e, a, ctx);
1120    BN_sub(e, e, d);
1121    if (!BN_is_zero(e)) {
1122      fprintf(stderr, "Exponentiation test failed!\n");
1123      return 0;
1124    }
1125  }
1126  BN_free(a);
1127  BN_free(b);
1128  BN_free(d);
1129  BN_free(e);
1130  BN_free(one);
1131  return (1);
1132}
1133
1134/* test_exp_mod_zero tests that x**0 mod 1 == 0. */
1135static int test_exp_mod_zero(void) {
1136  BIGNUM a, p, m;
1137  BIGNUM r;
1138  BN_CTX *ctx = BN_CTX_new();
1139  int ret = 0;
1140
1141  BN_init(&m);
1142  BN_one(&m);
1143
1144  BN_init(&a);
1145  BN_one(&a);
1146
1147  BN_init(&p);
1148  BN_zero(&p);
1149
1150  BN_init(&r);
1151  BN_mod_exp(&r, &a, &p, &m, ctx);
1152  BN_CTX_free(ctx);
1153
1154  if (BN_is_zero(&r)) {
1155    ret = 1;
1156  } else {
1157    printf("1**0 mod 1 = ");
1158    BN_print_fp(stdout, &r);
1159    printf(", should be 0\n");
1160  }
1161
1162  BN_free(&r);
1163  BN_free(&a);
1164  BN_free(&p);
1165  BN_free(&m);
1166
1167  return ret;
1168}
1169
1170static int genprime_cb(int p, int n, BN_GENCB *arg) {
1171  char c = '*';
1172
1173  if (p == 0)
1174    c = '.';
1175  if (p == 1)
1176    c = '+';
1177  if (p == 2)
1178    c = '*';
1179  if (p == 3)
1180    c = '\n';
1181  putc(c, stdout);
1182  fflush(stdout);
1183  return 1;
1184}
1185
1186int test_mod_sqrt(BIO *bp, BN_CTX *ctx) {
1187  BN_GENCB cb;
1188  BIGNUM *a, *p, *r;
1189  int i, j;
1190  int ret = 0;
1191
1192  a = BN_new();
1193  p = BN_new();
1194  r = BN_new();
1195  if (a == NULL || p == NULL || r == NULL)
1196    goto err;
1197
1198  BN_GENCB_set(&cb, genprime_cb, NULL);
1199
1200  for (i = 0; i < 16; i++) {
1201    if (i < 8) {
1202      unsigned primes[8] = {2, 3, 5, 7, 11, 13, 17, 19};
1203
1204      if (!BN_set_word(p, primes[i]))
1205        goto err;
1206    } else {
1207      if (!BN_set_word(a, 32))
1208        goto err;
1209      if (!BN_set_word(r, 2 * i + 1))
1210        goto err;
1211
1212      if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb))
1213        goto err;
1214      putc('\n', stdout);
1215    }
1216    p->neg = rand_neg();
1217
1218    for (j = 0; j < num2; j++) {
1219      /* construct 'a' such that it is a square modulo p,
1220       * but in general not a proper square and not reduced modulo p */
1221      if (!BN_rand(r, 256, 0, 3))
1222        goto err;
1223      if (!BN_nnmod(r, r, p, ctx))
1224        goto err;
1225      if (!BN_mod_sqr(r, r, p, ctx))
1226        goto err;
1227      if (!BN_rand(a, 256, 0, 3))
1228        goto err;
1229      if (!BN_nnmod(a, a, p, ctx))
1230        goto err;
1231      if (!BN_mod_sqr(a, a, p, ctx))
1232        goto err;
1233      if (!BN_mul(a, a, r, ctx))
1234        goto err;
1235      if (rand_neg())
1236        if (!BN_sub(a, a, p))
1237          goto err;
1238
1239      if (!BN_mod_sqrt(r, a, p, ctx))
1240        goto err;
1241      if (!BN_mod_sqr(r, r, p, ctx))
1242        goto err;
1243
1244      if (!BN_nnmod(a, a, p, ctx))
1245        goto err;
1246
1247      if (BN_cmp(a, r) != 0) {
1248        fprintf(stderr, "BN_mod_sqrt failed: a = ");
1249        BN_print_fp(stderr, a);
1250        fprintf(stderr, ", r = ");
1251        BN_print_fp(stderr, r);
1252        fprintf(stderr, ", p = ");
1253        BN_print_fp(stderr, p);
1254        fprintf(stderr, "\n");
1255        goto err;
1256      }
1257
1258      putc('.', stdout);
1259      fflush(stdout);
1260    }
1261
1262    putc('\n', stdout);
1263    fflush(stderr);
1264  }
1265  ret = 1;
1266err:
1267  if (a != NULL)
1268    BN_free(a);
1269  if (p != NULL)
1270    BN_free(p);
1271  if (r != NULL)
1272    BN_free(r);
1273  return ret;
1274}
1275
1276int test_small_prime(BIO *bp, BN_CTX *ctx) {
1277  static const int bits = 10;
1278  int ret = 0;
1279  BIGNUM r;
1280
1281  BN_init(&r);
1282  if (!BN_generate_prime_ex(&r, bits, 0, NULL, NULL, NULL)) {
1283    goto err;
1284  }
1285  if (BN_num_bits(&r) != bits) {
1286    BIO_printf(bp, "Expected %d bit prime, got %d bit number\n", bits,
1287               BN_num_bits(&r));
1288    goto err;
1289  }
1290
1291  ret = 1;
1292
1293err:
1294  BN_free(&r);
1295  return ret;
1296}
1297
1298int test_sqrt(BIO *bp, BN_CTX *ctx) {
1299  BIGNUM *n = BN_new(), *nn = BN_new(), *sqrt = BN_new();
1300  unsigned i;
1301
1302  /* Test some random squares. */
1303  for (i = 0; i < 100; i++) {
1304    if (!BN_rand(n, 1024 /* bit length */, -1 /* no modification of top bits */,
1305                 0 /* don't modify bottom bit */) ||
1306        !BN_mul(nn, n, n, ctx) ||
1307        !BN_sqrt(sqrt, nn, ctx)) {
1308      BIO_print_errors_fp(stderr);
1309      return 0;
1310    }
1311    if (BN_cmp(n, sqrt) != 0) {
1312      fprintf(stderr, "Bad result from BN_sqrt.\n");
1313      return 0;
1314    }
1315  }
1316
1317  /* Test some non-squares */
1318  for (i = 0; i < 100; i++) {
1319    if (!BN_rand(n, 1024 /* bit length */, -1 /* no modification of top bits */,
1320                 0 /* don't modify bottom bit */) ||
1321        !BN_mul(nn, n, n, ctx) ||
1322        !BN_add(nn, nn, BN_value_one())) {
1323      BIO_print_errors_fp(stderr);
1324      return 0;
1325    }
1326
1327    if (BN_sqrt(sqrt, nn, ctx)) {
1328      char *nn_str = BN_bn2dec(nn);
1329      fprintf(stderr, "BIO_sqrt didn't fail on a non-square: %s\n", nn_str);
1330      OPENSSL_free(nn_str);
1331    }
1332  }
1333
1334  BN_free(n);
1335  BN_free(sqrt);
1336  BN_free(nn);
1337
1338  return 1;
1339}
1340
1341int test_bn2bin_padded(BIO *bp, BN_CTX *ctx) {
1342  BIGNUM *n = BN_new();
1343  uint8_t zeros[256], out[256], reference[128];
1344  size_t bytes;
1345
1346  memset(zeros, 0, sizeof(zeros));
1347
1348  /* Test edge case at 0. */
1349  if (!BN_bn2bin_padded(NULL, 0, n)) {
1350    fprintf(stderr,
1351            "BN_bn2bin_padded failed to encode 0 in an empty buffer.\n");
1352    return 0;
1353  }
1354  memset(out, -1, sizeof(out));
1355  if (!BN_bn2bin_padded(out, sizeof(out), n)) {
1356    fprintf(stderr,
1357            "BN_bn2bin_padded failed to encode 0 in a non-empty buffer.\n");
1358    return 0;
1359  }
1360  if (memcmp(zeros, out, sizeof(out))) {
1361    fprintf(stderr, "BN_bn2bin_padded did not zero buffer.\n");
1362    return 0;
1363  }
1364
1365  /* Test a random numbers at various byte lengths. */
1366  for (bytes = 128 - 7; bytes <= 128; bytes++) {
1367    if (!BN_rand(n, bytes * 8, 0 /* make sure top bit is 1 */,
1368                 0 /* don't modify bottom bit */)) {
1369      BIO_print_errors_fp(stderr);
1370      return 0;
1371    }
1372    if (BN_num_bytes(n) != bytes || BN_bn2bin(n, reference) != bytes) {
1373      fprintf(stderr, "Bad result from BN_rand; bytes.\n");
1374      return 0;
1375    }
1376    /* Empty buffer should fail. */
1377    if (BN_bn2bin_padded(NULL, 0, n)) {
1378      fprintf(stderr,
1379              "BN_bn2bin_padded incorrectly succeeded on empty buffer.\n");
1380      return 0;
1381    }
1382    /* One byte short should fail. */
1383    if (BN_bn2bin_padded(out, bytes - 1, n)) {
1384      fprintf(stderr, "BN_bn2bin_padded incorrectly succeeded on short.\n");
1385      return 0;
1386    }
1387    /* Exactly right size should encode. */
1388    if (!BN_bn2bin_padded(out, bytes, n) ||
1389        memcmp(out, reference, bytes) != 0) {
1390      fprintf(stderr, "BN_bn2bin_padded gave a bad result.\n");
1391      return 0;
1392    }
1393    /* Pad up one byte extra. */
1394    if (!BN_bn2bin_padded(out, bytes + 1, n) ||
1395        memcmp(out + 1, reference, bytes) || memcmp(out, zeros, 1)) {
1396      fprintf(stderr, "BN_bn2bin_padded gave a bad result.\n");
1397      return 0;
1398    }
1399    /* Pad up to 256. */
1400    if (!BN_bn2bin_padded(out, sizeof(out), n) ||
1401        memcmp(out + sizeof(out) - bytes, reference, bytes) ||
1402        memcmp(out, zeros, sizeof(out) - bytes)) {
1403      fprintf(stderr, "BN_bn2bin_padded gave a bad result.\n");
1404      return 0;
1405    }
1406  }
1407
1408  BN_free(n);
1409
1410  return 1;
1411}
1412