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: 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: 
  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: 
  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,"%lX",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: