155714Skris/* crypto/bn/bntest.c */ 255714Skris/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 355714Skris * All rights reserved. 455714Skris * 555714Skris * This package is an SSL implementation written 655714Skris * by Eric Young (eay@cryptsoft.com). 755714Skris * The implementation was written so as to conform with Netscapes SSL. 855714Skris * 955714Skris * This library is free for commercial and non-commercial use as long as 1055714Skris * the following conditions are aheared to. The following conditions 1155714Skris * apply to all code found in this distribution, be it the RC4, RSA, 1255714Skris * lhash, DES, etc., code; not just the SSL code. The SSL documentation 1355714Skris * included with this distribution is covered by the same copyright terms 1455714Skris * except that the holder is Tim Hudson (tjh@cryptsoft.com). 1555714Skris * 1655714Skris * Copyright remains Eric Young's, and as such any Copyright notices in 1755714Skris * the code are not to be removed. 1855714Skris * If this package is used in a product, Eric Young should be given attribution 1955714Skris * as the author of the parts of the library used. 2055714Skris * This can be in the form of a textual message at program startup or 2155714Skris * in documentation (online or textual) provided with the package. 2255714Skris * 2355714Skris * Redistribution and use in source and binary forms, with or without 2455714Skris * modification, are permitted provided that the following conditions 2555714Skris * are met: 2655714Skris * 1. Redistributions of source code must retain the copyright 2755714Skris * notice, this list of conditions and the following disclaimer. 2855714Skris * 2. Redistributions in binary form must reproduce the above copyright 2955714Skris * notice, this list of conditions and the following disclaimer in the 3055714Skris * documentation and/or other materials provided with the distribution. 3155714Skris * 3. All advertising materials mentioning features or use of this software 3255714Skris * must display the following acknowledgement: 3355714Skris * "This product includes cryptographic software written by 3455714Skris * Eric Young (eay@cryptsoft.com)" 3555714Skris * The word 'cryptographic' can be left out if the rouines from the library 3655714Skris * being used are not cryptographic related :-). 3755714Skris * 4. If you include any Windows specific code (or a derivative thereof) from 3855714Skris * the apps directory (application code) you must include an acknowledgement: 3955714Skris * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 4055714Skris * 4155714Skris * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 4255714Skris * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 4355714Skris * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 4455714Skris * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 4555714Skris * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 4655714Skris * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 4755714Skris * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 4855714Skris * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 4955714Skris * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 5055714Skris * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 5155714Skris * SUCH DAMAGE. 5255714Skris * 5355714Skris * The licence and distribution terms for any publically available version or 5455714Skris * derivative of this code cannot be changed. i.e. this code cannot simply be 5555714Skris * copied and put under another distribution licence 5655714Skris * [including the GNU Public Licence.] 5755714Skris */ 58160814Ssimon/* ==================================================================== 59160814Ssimon * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 60160814Ssimon * 61160814Ssimon * Portions of the attached software ("Contribution") are developed by 62160814Ssimon * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. 63160814Ssimon * 64160814Ssimon * The Contribution is licensed pursuant to the Eric Young open source 65160814Ssimon * license provided above. 66160814Ssimon * 67160814Ssimon * The binary polynomial arithmetic software is originally written by 68160814Ssimon * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems Laboratories. 69160814Ssimon * 70160814Ssimon */ 7155714Skris 72160814Ssimon/* Until the key-gen callbacks are modified to use newer prototypes, we allow 73160814Ssimon * deprecated functions for openssl-internal code */ 74160814Ssimon#ifdef OPENSSL_NO_DEPRECATED 75160814Ssimon#undef OPENSSL_NO_DEPRECATED 76160814Ssimon#endif 77160814Ssimon 7855714Skris#include <stdio.h> 7955714Skris#include <stdlib.h> 8055714Skris#include <string.h> 8155714Skris 82109998Smarkm#include "e_os.h" 8355714Skris 8455714Skris#include <openssl/bio.h> 8555714Skris#include <openssl/bn.h> 8655714Skris#include <openssl/rand.h> 8755714Skris#include <openssl/x509.h> 8855714Skris#include <openssl/err.h> 8955714Skris 9059191Skrisconst int num0 = 100; /* number of tests */ 9159191Skrisconst int num1 = 50; /* additional tests for some functions */ 9259191Skrisconst int num2 = 5; /* number of tests for slow functions */ 9359191Skris 9455714Skrisint test_add(BIO *bp); 9555714Skrisint test_sub(BIO *bp); 9655714Skrisint test_lshift1(BIO *bp); 9755714Skrisint test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_); 9855714Skrisint test_rshift1(BIO *bp); 9955714Skrisint test_rshift(BIO *bp,BN_CTX *ctx); 10055714Skrisint test_div(BIO *bp,BN_CTX *ctx); 101160814Ssimonint test_div_word(BIO *bp); 10255714Skrisint test_div_recp(BIO *bp,BN_CTX *ctx); 10355714Skrisint test_mul(BIO *bp); 10455714Skrisint test_sqr(BIO *bp,BN_CTX *ctx); 10555714Skrisint test_mont(BIO *bp,BN_CTX *ctx); 10655714Skrisint test_mod(BIO *bp,BN_CTX *ctx); 10755714Skrisint test_mod_mul(BIO *bp,BN_CTX *ctx); 10855714Skrisint test_mod_exp(BIO *bp,BN_CTX *ctx); 109160814Ssimonint test_mod_exp_mont_consttime(BIO *bp,BN_CTX *ctx); 110279264Sdelphijint test_mod_exp_mont5(BIO *bp, BN_CTX *ctx); 11155714Skrisint test_exp(BIO *bp,BN_CTX *ctx); 112160814Ssimonint test_gf2m_add(BIO *bp); 113160814Ssimonint test_gf2m_mod(BIO *bp); 114160814Ssimonint test_gf2m_mod_mul(BIO *bp,BN_CTX *ctx); 115160814Ssimonint test_gf2m_mod_sqr(BIO *bp,BN_CTX *ctx); 116160814Ssimonint test_gf2m_mod_inv(BIO *bp,BN_CTX *ctx); 117160814Ssimonint test_gf2m_mod_div(BIO *bp,BN_CTX *ctx); 118160814Ssimonint test_gf2m_mod_exp(BIO *bp,BN_CTX *ctx); 119160814Ssimonint test_gf2m_mod_sqrt(BIO *bp,BN_CTX *ctx); 120160814Ssimonint test_gf2m_mod_solve_quad(BIO *bp,BN_CTX *ctx); 121109998Smarkmint test_kron(BIO *bp,BN_CTX *ctx); 122109998Smarkmint test_sqrt(BIO *bp,BN_CTX *ctx); 12355714Skrisint rand_neg(void); 12455714Skrisstatic int results=0; 12555714Skris 12659191Skrisstatic unsigned char lst[]="\xC6\x4F\x43\x04\x2A\xEA\xCA\x6E\x58\x36\x80\x5B\xE8\xC9" 12755714Skris"\x9B\x04\x5D\x48\x36\xC2\xFD\x16\xC9\x64\xF0"; 12855714Skris 12959191Skrisstatic const char rnd_seed[] = "string to make the random number generator think it has entropy"; 13059191Skris 13159191Skrisstatic void message(BIO *out, char *m) 13259191Skris { 13359191Skris fprintf(stderr, "test %s\n", m); 13459191Skris BIO_puts(out, "print \"test "); 13559191Skris BIO_puts(out, m); 13659191Skris BIO_puts(out, "\\n\"\n"); 13759191Skris } 13859191Skris 13955714Skrisint main(int argc, char *argv[]) 14055714Skris { 14155714Skris BN_CTX *ctx; 14255714Skris BIO *out; 14355714Skris char *outfile=NULL; 14455714Skris 14559191Skris results = 0; 14659191Skris 14776866Skris RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_generate_prime may fail */ 14859191Skris 14955714Skris argc--; 15055714Skris argv++; 15155714Skris while (argc >= 1) 15255714Skris { 15355714Skris if (strcmp(*argv,"-results") == 0) 15455714Skris results=1; 15555714Skris else if (strcmp(*argv,"-out") == 0) 15655714Skris { 15755714Skris if (--argc < 1) break; 15855714Skris outfile= *(++argv); 15955714Skris } 16055714Skris argc--; 16155714Skris argv++; 16255714Skris } 16355714Skris 16455714Skris 16555714Skris ctx=BN_CTX_new(); 166109998Smarkm if (ctx == NULL) EXIT(1); 16755714Skris 16855714Skris out=BIO_new(BIO_s_file()); 169109998Smarkm if (out == NULL) EXIT(1); 17055714Skris if (outfile == NULL) 17155714Skris { 17255714Skris BIO_set_fp(out,stdout,BIO_NOCLOSE); 17355714Skris } 17455714Skris else 17555714Skris { 17655714Skris if (!BIO_write_filename(out,outfile)) 17755714Skris { 17855714Skris perror(outfile); 179109998Smarkm EXIT(1); 18055714Skris } 18155714Skris } 18255714Skris 18355714Skris if (!results) 18455714Skris BIO_puts(out,"obase=16\nibase=16\n"); 18555714Skris 18659191Skris message(out,"BN_add"); 18755714Skris if (!test_add(out)) goto err; 188194206Ssimon (void)BIO_flush(out); 18955714Skris 19059191Skris message(out,"BN_sub"); 19155714Skris if (!test_sub(out)) goto err; 192194206Ssimon (void)BIO_flush(out); 19355714Skris 19459191Skris message(out,"BN_lshift1"); 19555714Skris if (!test_lshift1(out)) goto err; 196194206Ssimon (void)BIO_flush(out); 19755714Skris 19859191Skris message(out,"BN_lshift (fixed)"); 19959191Skris if (!test_lshift(out,ctx,BN_bin2bn(lst,sizeof(lst)-1,NULL))) 20055714Skris goto err; 201194206Ssimon (void)BIO_flush(out); 20255714Skris 20359191Skris message(out,"BN_lshift"); 20455714Skris if (!test_lshift(out,ctx,NULL)) goto err; 205194206Ssimon (void)BIO_flush(out); 20655714Skris 20759191Skris message(out,"BN_rshift1"); 20855714Skris if (!test_rshift1(out)) goto err; 209194206Ssimon (void)BIO_flush(out); 21055714Skris 21159191Skris message(out,"BN_rshift"); 21255714Skris if (!test_rshift(out,ctx)) goto err; 213194206Ssimon (void)BIO_flush(out); 21455714Skris 21559191Skris message(out,"BN_sqr"); 21655714Skris if (!test_sqr(out,ctx)) goto err; 217194206Ssimon (void)BIO_flush(out); 21855714Skris 21959191Skris message(out,"BN_mul"); 22055714Skris if (!test_mul(out)) goto err; 221194206Ssimon (void)BIO_flush(out); 22255714Skris 22359191Skris message(out,"BN_div"); 22455714Skris if (!test_div(out,ctx)) goto err; 225194206Ssimon (void)BIO_flush(out); 22655714Skris 227160814Ssimon message(out,"BN_div_word"); 228160814Ssimon if (!test_div_word(out)) goto err; 229194206Ssimon (void)BIO_flush(out); 230160814Ssimon 23159191Skris message(out,"BN_div_recp"); 23255714Skris if (!test_div_recp(out,ctx)) goto err; 233194206Ssimon (void)BIO_flush(out); 23455714Skris 23559191Skris message(out,"BN_mod"); 23655714Skris if (!test_mod(out,ctx)) goto err; 237194206Ssimon (void)BIO_flush(out); 23855714Skris 23959191Skris message(out,"BN_mod_mul"); 24055714Skris if (!test_mod_mul(out,ctx)) goto err; 241194206Ssimon (void)BIO_flush(out); 24255714Skris 24359191Skris message(out,"BN_mont"); 24455714Skris if (!test_mont(out,ctx)) goto err; 245194206Ssimon (void)BIO_flush(out); 24659191Skris 24759191Skris message(out,"BN_mod_exp"); 24855714Skris if (!test_mod_exp(out,ctx)) goto err; 249194206Ssimon (void)BIO_flush(out); 25055714Skris 251160814Ssimon message(out,"BN_mod_exp_mont_consttime"); 252160814Ssimon if (!test_mod_exp_mont_consttime(out,ctx)) goto err; 253279264Sdelphij if (!test_mod_exp_mont5(out,ctx)) goto err; 254194206Ssimon (void)BIO_flush(out); 255160814Ssimon 25659191Skris message(out,"BN_exp"); 25755714Skris if (!test_exp(out,ctx)) goto err; 258194206Ssimon (void)BIO_flush(out); 25955714Skris 260109998Smarkm message(out,"BN_kronecker"); 261109998Smarkm if (!test_kron(out,ctx)) goto err; 262194206Ssimon (void)BIO_flush(out); 263109998Smarkm 264109998Smarkm message(out,"BN_mod_sqrt"); 265109998Smarkm if (!test_sqrt(out,ctx)) goto err; 266194206Ssimon (void)BIO_flush(out); 267238405Sjkim#ifndef OPENSSL_NO_EC2M 268160814Ssimon message(out,"BN_GF2m_add"); 269160814Ssimon if (!test_gf2m_add(out)) goto err; 270194206Ssimon (void)BIO_flush(out); 271160814Ssimon 272160814Ssimon message(out,"BN_GF2m_mod"); 273160814Ssimon if (!test_gf2m_mod(out)) goto err; 274194206Ssimon (void)BIO_flush(out); 275160814Ssimon 276160814Ssimon message(out,"BN_GF2m_mod_mul"); 277160814Ssimon if (!test_gf2m_mod_mul(out,ctx)) goto err; 278194206Ssimon (void)BIO_flush(out); 279160814Ssimon 280160814Ssimon message(out,"BN_GF2m_mod_sqr"); 281160814Ssimon if (!test_gf2m_mod_sqr(out,ctx)) goto err; 282194206Ssimon (void)BIO_flush(out); 283160814Ssimon 284160814Ssimon message(out,"BN_GF2m_mod_inv"); 285160814Ssimon if (!test_gf2m_mod_inv(out,ctx)) goto err; 286194206Ssimon (void)BIO_flush(out); 287160814Ssimon 288160814Ssimon message(out,"BN_GF2m_mod_div"); 289160814Ssimon if (!test_gf2m_mod_div(out,ctx)) goto err; 290194206Ssimon (void)BIO_flush(out); 291160814Ssimon 292160814Ssimon message(out,"BN_GF2m_mod_exp"); 293160814Ssimon if (!test_gf2m_mod_exp(out,ctx)) goto err; 294194206Ssimon (void)BIO_flush(out); 295160814Ssimon 296160814Ssimon message(out,"BN_GF2m_mod_sqrt"); 297160814Ssimon if (!test_gf2m_mod_sqrt(out,ctx)) goto err; 298194206Ssimon (void)BIO_flush(out); 299160814Ssimon 300160814Ssimon message(out,"BN_GF2m_mod_solve_quad"); 301160814Ssimon if (!test_gf2m_mod_solve_quad(out,ctx)) goto err; 302194206Ssimon (void)BIO_flush(out); 303238405Sjkim#endif 30459191Skris BN_CTX_free(ctx); 30559191Skris BIO_free(out); 30659191Skris 30755714Skris/**/ 308109998Smarkm EXIT(0); 30955714Skriserr: 31059191Skris BIO_puts(out,"1\n"); /* make sure the Perl script fed by bc notices 311160814Ssimon * the failure, see test_bn in test/Makefile.ssl*/ 312194206Ssimon (void)BIO_flush(out); 31355714Skris ERR_load_crypto_strings(); 31459191Skris ERR_print_errors_fp(stderr); 315109998Smarkm EXIT(1); 31655714Skris return(1); 31755714Skris } 31855714Skris 31955714Skrisint test_add(BIO *bp) 32055714Skris { 32155714Skris BIGNUM a,b,c; 32255714Skris int i; 32355714Skris 32455714Skris BN_init(&a); 32555714Skris BN_init(&b); 32655714Skris BN_init(&c); 32755714Skris 32876866Skris BN_bntest_rand(&a,512,0,0); 32959191Skris for (i=0; i<num0; i++) 33055714Skris { 33176866Skris BN_bntest_rand(&b,450+i,0,0); 33255714Skris a.neg=rand_neg(); 33355714Skris b.neg=rand_neg(); 33455714Skris BN_add(&c,&a,&b); 33555714Skris if (bp != NULL) 33655714Skris { 33755714Skris if (!results) 33855714Skris { 33955714Skris BN_print(bp,&a); 34055714Skris BIO_puts(bp," + "); 34155714Skris BN_print(bp,&b); 34255714Skris BIO_puts(bp," - "); 34355714Skris } 34455714Skris BN_print(bp,&c); 34555714Skris BIO_puts(bp,"\n"); 34655714Skris } 34755714Skris a.neg=!a.neg; 34855714Skris b.neg=!b.neg; 34955714Skris BN_add(&c,&c,&b); 35055714Skris BN_add(&c,&c,&a); 35155714Skris if(!BN_is_zero(&c)) 35255714Skris { 35359191Skris fprintf(stderr,"Add test failed!\n"); 35455714Skris return 0; 35555714Skris } 35655714Skris } 35755714Skris BN_free(&a); 35855714Skris BN_free(&b); 35955714Skris BN_free(&c); 36055714Skris return(1); 36155714Skris } 36255714Skris 36355714Skrisint test_sub(BIO *bp) 36455714Skris { 36555714Skris BIGNUM a,b,c; 36655714Skris int i; 36755714Skris 36855714Skris BN_init(&a); 36955714Skris BN_init(&b); 37055714Skris BN_init(&c); 37155714Skris 37259191Skris for (i=0; i<num0+num1; i++) 37355714Skris { 37459191Skris if (i < num1) 37559191Skris { 37676866Skris BN_bntest_rand(&a,512,0,0); 37759191Skris BN_copy(&b,&a); 37859191Skris if (BN_set_bit(&a,i)==0) return(0); 37959191Skris BN_add_word(&b,i); 38059191Skris } 38159191Skris else 38259191Skris { 38376866Skris BN_bntest_rand(&b,400+i-num1,0,0); 38459191Skris a.neg=rand_neg(); 38559191Skris b.neg=rand_neg(); 38659191Skris } 38755714Skris BN_sub(&c,&a,&b); 38855714Skris if (bp != NULL) 38955714Skris { 39055714Skris if (!results) 39155714Skris { 39255714Skris BN_print(bp,&a); 39355714Skris BIO_puts(bp," - "); 39455714Skris BN_print(bp,&b); 39555714Skris BIO_puts(bp," - "); 39655714Skris } 39755714Skris BN_print(bp,&c); 39855714Skris BIO_puts(bp,"\n"); 39955714Skris } 40055714Skris BN_add(&c,&c,&b); 40155714Skris BN_sub(&c,&c,&a); 40255714Skris if(!BN_is_zero(&c)) 40355714Skris { 40459191Skris fprintf(stderr,"Subtract test failed!\n"); 40555714Skris return 0; 40655714Skris } 40755714Skris } 40855714Skris BN_free(&a); 40955714Skris BN_free(&b); 41055714Skris BN_free(&c); 41155714Skris return(1); 41255714Skris } 41355714Skris 41455714Skrisint test_div(BIO *bp, BN_CTX *ctx) 41555714Skris { 41655714Skris BIGNUM a,b,c,d,e; 41755714Skris int i; 41855714Skris 41955714Skris BN_init(&a); 42055714Skris BN_init(&b); 42155714Skris BN_init(&c); 42255714Skris BN_init(&d); 42355714Skris BN_init(&e); 42455714Skris 42559191Skris for (i=0; i<num0+num1; i++) 42655714Skris { 42759191Skris if (i < num1) 42859191Skris { 42976866Skris BN_bntest_rand(&a,400,0,0); 43059191Skris BN_copy(&b,&a); 43159191Skris BN_lshift(&a,&a,i); 43259191Skris BN_add_word(&a,i); 43359191Skris } 43459191Skris else 43576866Skris BN_bntest_rand(&b,50+3*(i-num1),0,0); 43655714Skris a.neg=rand_neg(); 43755714Skris b.neg=rand_neg(); 43855714Skris BN_div(&d,&c,&a,&b,ctx); 43955714Skris if (bp != NULL) 44055714Skris { 44155714Skris if (!results) 44255714Skris { 44355714Skris BN_print(bp,&a); 44455714Skris BIO_puts(bp," / "); 44555714Skris BN_print(bp,&b); 44655714Skris BIO_puts(bp," - "); 44755714Skris } 44855714Skris BN_print(bp,&d); 44955714Skris BIO_puts(bp,"\n"); 45055714Skris 45155714Skris if (!results) 45255714Skris { 45355714Skris BN_print(bp,&a); 45455714Skris BIO_puts(bp," % "); 45555714Skris BN_print(bp,&b); 45655714Skris BIO_puts(bp," - "); 45755714Skris } 45855714Skris BN_print(bp,&c); 45955714Skris BIO_puts(bp,"\n"); 46055714Skris } 46155714Skris BN_mul(&e,&d,&b,ctx); 46255714Skris BN_add(&d,&e,&c); 46355714Skris BN_sub(&d,&d,&a); 46455714Skris if(!BN_is_zero(&d)) 46555714Skris { 46659191Skris fprintf(stderr,"Division test failed!\n"); 46755714Skris return 0; 46855714Skris } 46955714Skris } 47055714Skris BN_free(&a); 47155714Skris BN_free(&b); 47255714Skris BN_free(&c); 47355714Skris BN_free(&d); 47455714Skris BN_free(&e); 47555714Skris return(1); 47655714Skris } 47755714Skris 478160814Ssimonstatic void print_word(BIO *bp,BN_ULONG w) 479160814Ssimon { 480160814Ssimon#ifdef SIXTY_FOUR_BIT 481160814Ssimon if (sizeof(w) > sizeof(unsigned long)) 482160814Ssimon { 483160814Ssimon unsigned long h=(unsigned long)(w>>32), 484160814Ssimon l=(unsigned long)(w); 485160814Ssimon 486160814Ssimon if (h) BIO_printf(bp,"%lX%08lX",h,l); 487160814Ssimon else BIO_printf(bp,"%lX",l); 488160814Ssimon return; 489160814Ssimon } 490160814Ssimon#endif 491238405Sjkim BIO_printf(bp,BN_HEX_FMT1,w); 492160814Ssimon } 493160814Ssimon 494160814Ssimonint test_div_word(BIO *bp) 495160814Ssimon { 496160814Ssimon BIGNUM a,b; 497160814Ssimon BN_ULONG r,s; 498160814Ssimon int i; 499160814Ssimon 500160814Ssimon BN_init(&a); 501160814Ssimon BN_init(&b); 502160814Ssimon 503160814Ssimon for (i=0; i<num0; i++) 504160814Ssimon { 505160814Ssimon do { 506160814Ssimon BN_bntest_rand(&a,512,-1,0); 507160814Ssimon BN_bntest_rand(&b,BN_BITS2,-1,0); 508160814Ssimon s = b.d[0]; 509160814Ssimon } while (!s); 510160814Ssimon 511160814Ssimon BN_copy(&b, &a); 512160814Ssimon r = BN_div_word(&b, s); 513160814Ssimon 514160814Ssimon if (bp != NULL) 515160814Ssimon { 516160814Ssimon if (!results) 517160814Ssimon { 518160814Ssimon BN_print(bp,&a); 519160814Ssimon BIO_puts(bp," / "); 520160814Ssimon print_word(bp,s); 521160814Ssimon BIO_puts(bp," - "); 522160814Ssimon } 523160814Ssimon BN_print(bp,&b); 524160814Ssimon BIO_puts(bp,"\n"); 525160814Ssimon 526160814Ssimon if (!results) 527160814Ssimon { 528160814Ssimon BN_print(bp,&a); 529160814Ssimon BIO_puts(bp," % "); 530160814Ssimon print_word(bp,s); 531160814Ssimon BIO_puts(bp," - "); 532160814Ssimon } 533160814Ssimon print_word(bp,r); 534160814Ssimon BIO_puts(bp,"\n"); 535160814Ssimon } 536160814Ssimon BN_mul_word(&b,s); 537160814Ssimon BN_add_word(&b,r); 538160814Ssimon BN_sub(&b,&a,&b); 539160814Ssimon if(!BN_is_zero(&b)) 540160814Ssimon { 541160814Ssimon fprintf(stderr,"Division (word) test failed!\n"); 542160814Ssimon return 0; 543160814Ssimon } 544160814Ssimon } 545160814Ssimon BN_free(&a); 546160814Ssimon BN_free(&b); 547160814Ssimon return(1); 548160814Ssimon } 549160814Ssimon 55055714Skrisint test_div_recp(BIO *bp, BN_CTX *ctx) 55155714Skris { 55255714Skris BIGNUM a,b,c,d,e; 55355714Skris BN_RECP_CTX recp; 55455714Skris int i; 55555714Skris 55655714Skris BN_RECP_CTX_init(&recp); 55755714Skris BN_init(&a); 55855714Skris BN_init(&b); 55955714Skris BN_init(&c); 56055714Skris BN_init(&d); 56155714Skris BN_init(&e); 56255714Skris 56359191Skris for (i=0; i<num0+num1; i++) 56455714Skris { 56559191Skris if (i < num1) 56659191Skris { 56776866Skris BN_bntest_rand(&a,400,0,0); 56859191Skris BN_copy(&b,&a); 56959191Skris BN_lshift(&a,&a,i); 57059191Skris BN_add_word(&a,i); 57159191Skris } 57259191Skris else 57376866Skris BN_bntest_rand(&b,50+3*(i-num1),0,0); 57455714Skris a.neg=rand_neg(); 57555714Skris b.neg=rand_neg(); 57655714Skris BN_RECP_CTX_set(&recp,&b,ctx); 57755714Skris BN_div_recp(&d,&c,&a,&recp,ctx); 57855714Skris if (bp != NULL) 57955714Skris { 58055714Skris if (!results) 58155714Skris { 58255714Skris BN_print(bp,&a); 58355714Skris BIO_puts(bp," / "); 58455714Skris BN_print(bp,&b); 58555714Skris BIO_puts(bp," - "); 58655714Skris } 58755714Skris BN_print(bp,&d); 58855714Skris BIO_puts(bp,"\n"); 58955714Skris 59055714Skris if (!results) 59155714Skris { 59255714Skris BN_print(bp,&a); 59355714Skris BIO_puts(bp," % "); 59455714Skris BN_print(bp,&b); 59555714Skris BIO_puts(bp," - "); 59655714Skris } 59755714Skris BN_print(bp,&c); 59855714Skris BIO_puts(bp,"\n"); 59955714Skris } 60055714Skris BN_mul(&e,&d,&b,ctx); 60155714Skris BN_add(&d,&e,&c); 60255714Skris BN_sub(&d,&d,&a); 60355714Skris if(!BN_is_zero(&d)) 60455714Skris { 60559191Skris fprintf(stderr,"Reciprocal division test failed!\n"); 60659191Skris fprintf(stderr,"a="); 60759191Skris BN_print_fp(stderr,&a); 60859191Skris fprintf(stderr,"\nb="); 60959191Skris BN_print_fp(stderr,&b); 61059191Skris fprintf(stderr,"\n"); 61155714Skris return 0; 61255714Skris } 61355714Skris } 61455714Skris BN_free(&a); 61555714Skris BN_free(&b); 61655714Skris BN_free(&c); 61755714Skris BN_free(&d); 61855714Skris BN_free(&e); 61955714Skris BN_RECP_CTX_free(&recp); 62055714Skris return(1); 62155714Skris } 62255714Skris 62355714Skrisint test_mul(BIO *bp) 62455714Skris { 62555714Skris BIGNUM a,b,c,d,e; 62655714Skris int i; 627109998Smarkm BN_CTX *ctx; 62855714Skris 629109998Smarkm ctx = BN_CTX_new(); 630109998Smarkm if (ctx == NULL) EXIT(1); 631109998Smarkm 63255714Skris BN_init(&a); 63355714Skris BN_init(&b); 63455714Skris BN_init(&c); 63555714Skris BN_init(&d); 63655714Skris BN_init(&e); 63755714Skris 63859191Skris for (i=0; i<num0+num1; i++) 63955714Skris { 64059191Skris if (i <= num1) 64159191Skris { 64276866Skris BN_bntest_rand(&a,100,0,0); 64376866Skris BN_bntest_rand(&b,100,0,0); 64459191Skris } 64559191Skris else 64676866Skris BN_bntest_rand(&b,i-num1,0,0); 64755714Skris a.neg=rand_neg(); 64855714Skris b.neg=rand_neg(); 649109998Smarkm BN_mul(&c,&a,&b,ctx); 65055714Skris if (bp != NULL) 65155714Skris { 65255714Skris if (!results) 65355714Skris { 65455714Skris BN_print(bp,&a); 65555714Skris BIO_puts(bp," * "); 65655714Skris BN_print(bp,&b); 65755714Skris BIO_puts(bp," - "); 65855714Skris } 65955714Skris BN_print(bp,&c); 66055714Skris BIO_puts(bp,"\n"); 66155714Skris } 662109998Smarkm BN_div(&d,&e,&c,&a,ctx); 66355714Skris BN_sub(&d,&d,&b); 66455714Skris if(!BN_is_zero(&d) || !BN_is_zero(&e)) 66555714Skris { 66659191Skris fprintf(stderr,"Multiplication test failed!\n"); 66755714Skris return 0; 66855714Skris } 66955714Skris } 67055714Skris BN_free(&a); 67155714Skris BN_free(&b); 67255714Skris BN_free(&c); 67355714Skris BN_free(&d); 67455714Skris BN_free(&e); 675109998Smarkm BN_CTX_free(ctx); 67655714Skris return(1); 67755714Skris } 67855714Skris 67955714Skrisint test_sqr(BIO *bp, BN_CTX *ctx) 68055714Skris { 681277195Sdelphij BIGNUM *a,*c,*d,*e; 682277195Sdelphij int i, ret = 0; 68355714Skris 684277195Sdelphij a = BN_new(); 685277195Sdelphij c = BN_new(); 686277195Sdelphij d = BN_new(); 687277195Sdelphij e = BN_new(); 688277195Sdelphij if (a == NULL || c == NULL || d == NULL || e == NULL) 689277195Sdelphij { 690277195Sdelphij goto err; 691277195Sdelphij } 69255714Skris 69359191Skris for (i=0; i<num0; i++) 69455714Skris { 695277195Sdelphij BN_bntest_rand(a,40+i*10,0,0); 696277195Sdelphij a->neg=rand_neg(); 697277195Sdelphij BN_sqr(c,a,ctx); 69855714Skris if (bp != NULL) 69955714Skris { 70055714Skris if (!results) 70155714Skris { 702277195Sdelphij BN_print(bp,a); 70355714Skris BIO_puts(bp," * "); 704277195Sdelphij BN_print(bp,a); 70555714Skris BIO_puts(bp," - "); 70655714Skris } 707277195Sdelphij BN_print(bp,c); 70855714Skris BIO_puts(bp,"\n"); 70955714Skris } 710277195Sdelphij BN_div(d,e,c,a,ctx); 711277195Sdelphij BN_sub(d,d,a); 712277195Sdelphij if(!BN_is_zero(d) || !BN_is_zero(e)) 713277195Sdelphij { 714277195Sdelphij fprintf(stderr,"Square test failed!\n"); 715277195Sdelphij goto err; 716277195Sdelphij } 71755714Skris } 718277195Sdelphij 719277195Sdelphij /* Regression test for a BN_sqr overflow bug. */ 720277195Sdelphij BN_hex2bn(&a, 721277195Sdelphij "80000000000000008000000000000001FFFFFFFFFFFFFFFE0000000000000000"); 722277195Sdelphij BN_sqr(c, a, ctx); 723277195Sdelphij if (bp != NULL) 724277195Sdelphij { 725277195Sdelphij if (!results) 726277195Sdelphij { 727277195Sdelphij BN_print(bp,a); 728277195Sdelphij BIO_puts(bp," * "); 729277195Sdelphij BN_print(bp,a); 730277195Sdelphij BIO_puts(bp," - "); 731277195Sdelphij } 732277195Sdelphij BN_print(bp,c); 733277195Sdelphij BIO_puts(bp,"\n"); 734277195Sdelphij } 735277195Sdelphij BN_mul(d, a, a, ctx); 736277195Sdelphij if (BN_cmp(c, d)) 737277195Sdelphij { 738277195Sdelphij fprintf(stderr, "Square test failed: BN_sqr and BN_mul produce " 739277195Sdelphij "different results!\n"); 740277195Sdelphij goto err; 741277195Sdelphij } 742277195Sdelphij 743277195Sdelphij /* Regression test for a BN_sqr overflow bug. */ 744277195Sdelphij BN_hex2bn(&a, 745277195Sdelphij "80000000000000000000000080000001FFFFFFFE000000000000000000000000"); 746277195Sdelphij BN_sqr(c, a, ctx); 747277195Sdelphij if (bp != NULL) 748277195Sdelphij { 749277195Sdelphij if (!results) 750277195Sdelphij { 751277195Sdelphij BN_print(bp,a); 752277195Sdelphij BIO_puts(bp," * "); 753277195Sdelphij BN_print(bp,a); 754277195Sdelphij BIO_puts(bp," - "); 755277195Sdelphij } 756277195Sdelphij BN_print(bp,c); 757277195Sdelphij BIO_puts(bp,"\n"); 758277195Sdelphij } 759277195Sdelphij BN_mul(d, a, a, ctx); 760277195Sdelphij if (BN_cmp(c, d)) 761277195Sdelphij { 762277195Sdelphij fprintf(stderr, "Square test failed: BN_sqr and BN_mul produce " 763277195Sdelphij "different results!\n"); 764277195Sdelphij goto err; 765277195Sdelphij } 766277195Sdelphij ret = 1; 767277195Sdelphijerr: 768277195Sdelphij if (a != NULL) BN_free(a); 769277195Sdelphij if (c != NULL) BN_free(c); 770277195Sdelphij if (d != NULL) BN_free(d); 771277195Sdelphij if (e != NULL) BN_free(e); 772277195Sdelphij return ret; 77355714Skris } 77455714Skris 77555714Skrisint test_mont(BIO *bp, BN_CTX *ctx) 77655714Skris { 77755714Skris BIGNUM a,b,c,d,A,B; 77855714Skris BIGNUM n; 77955714Skris int i; 78055714Skris BN_MONT_CTX *mont; 78155714Skris 78255714Skris BN_init(&a); 78355714Skris BN_init(&b); 78455714Skris BN_init(&c); 78555714Skris BN_init(&d); 78655714Skris BN_init(&A); 78755714Skris BN_init(&B); 78855714Skris BN_init(&n); 78955714Skris 79055714Skris mont=BN_MONT_CTX_new(); 791238405Sjkim if (mont == NULL) 792238405Sjkim return 0; 79355714Skris 79476866Skris BN_bntest_rand(&a,100,0,0); /**/ 79576866Skris BN_bntest_rand(&b,100,0,0); /**/ 79659191Skris for (i=0; i<num2; i++) 79755714Skris { 79859191Skris int bits = (200*(i+1))/num2; 79959191Skris 80059191Skris if (bits == 0) 80159191Skris continue; 80276866Skris BN_bntest_rand(&n,bits,0,1); 80355714Skris BN_MONT_CTX_set(mont,&n,ctx); 80455714Skris 805109998Smarkm BN_nnmod(&a,&a,&n,ctx); 806109998Smarkm BN_nnmod(&b,&b,&n,ctx); 807109998Smarkm 80855714Skris BN_to_montgomery(&A,&a,mont,ctx); 80955714Skris BN_to_montgomery(&B,&b,mont,ctx); 81055714Skris 81155714Skris BN_mod_mul_montgomery(&c,&A,&B,mont,ctx);/**/ 81255714Skris BN_from_montgomery(&A,&c,mont,ctx);/**/ 81355714Skris if (bp != NULL) 81455714Skris { 81555714Skris if (!results) 81655714Skris { 81755714Skris#ifdef undef 81855714Skrisfprintf(stderr,"%d * %d %% %d\n", 81955714SkrisBN_num_bits(&a), 82055714SkrisBN_num_bits(&b), 82155714SkrisBN_num_bits(mont->N)); 82255714Skris#endif 82355714Skris BN_print(bp,&a); 82455714Skris BIO_puts(bp," * "); 82555714Skris BN_print(bp,&b); 82655714Skris BIO_puts(bp," % "); 82755714Skris BN_print(bp,&(mont->N)); 82855714Skris BIO_puts(bp," - "); 82955714Skris } 83055714Skris BN_print(bp,&A); 83155714Skris BIO_puts(bp,"\n"); 83255714Skris } 83355714Skris BN_mod_mul(&d,&a,&b,&n,ctx); 83455714Skris BN_sub(&d,&d,&A); 83555714Skris if(!BN_is_zero(&d)) 83655714Skris { 83759191Skris fprintf(stderr,"Montgomery multiplication test failed!\n"); 83855714Skris return 0; 83955714Skris } 84055714Skris } 84155714Skris BN_MONT_CTX_free(mont); 84255714Skris BN_free(&a); 84355714Skris BN_free(&b); 84455714Skris BN_free(&c); 84555714Skris BN_free(&d); 84655714Skris BN_free(&A); 84755714Skris BN_free(&B); 84855714Skris BN_free(&n); 84955714Skris return(1); 85055714Skris } 85155714Skris 85255714Skrisint test_mod(BIO *bp, BN_CTX *ctx) 85355714Skris { 85455714Skris BIGNUM *a,*b,*c,*d,*e; 85555714Skris int i; 85655714Skris 85755714Skris a=BN_new(); 85855714Skris b=BN_new(); 85955714Skris c=BN_new(); 86055714Skris d=BN_new(); 86155714Skris e=BN_new(); 86255714Skris 86376866Skris BN_bntest_rand(a,1024,0,0); /**/ 86459191Skris for (i=0; i<num0; i++) 86555714Skris { 86676866Skris BN_bntest_rand(b,450+i*10,0,0); /**/ 86755714Skris a->neg=rand_neg(); 86855714Skris b->neg=rand_neg(); 86955714Skris BN_mod(c,a,b,ctx);/**/ 87055714Skris if (bp != NULL) 87155714Skris { 87255714Skris if (!results) 87355714Skris { 87455714Skris BN_print(bp,a); 87555714Skris BIO_puts(bp," % "); 87655714Skris BN_print(bp,b); 87755714Skris BIO_puts(bp," - "); 87855714Skris } 87955714Skris BN_print(bp,c); 88055714Skris BIO_puts(bp,"\n"); 88155714Skris } 88255714Skris BN_div(d,e,a,b,ctx); 88355714Skris BN_sub(e,e,c); 88455714Skris if(!BN_is_zero(e)) 88555714Skris { 88659191Skris fprintf(stderr,"Modulo test failed!\n"); 88755714Skris return 0; 88855714Skris } 88955714Skris } 89055714Skris BN_free(a); 89155714Skris BN_free(b); 89255714Skris BN_free(c); 89355714Skris BN_free(d); 89455714Skris BN_free(e); 89555714Skris return(1); 89655714Skris } 89755714Skris 89855714Skrisint test_mod_mul(BIO *bp, BN_CTX *ctx) 89955714Skris { 90055714Skris BIGNUM *a,*b,*c,*d,*e; 901109998Smarkm int i,j; 90255714Skris 90355714Skris a=BN_new(); 90455714Skris b=BN_new(); 90555714Skris c=BN_new(); 90655714Skris d=BN_new(); 90755714Skris e=BN_new(); 90855714Skris 909109998Smarkm for (j=0; j<3; j++) { 91076866Skris BN_bntest_rand(c,1024,0,0); /**/ 91159191Skris for (i=0; i<num0; i++) 91255714Skris { 91376866Skris BN_bntest_rand(a,475+i*10,0,0); /**/ 91476866Skris BN_bntest_rand(b,425+i*11,0,0); /**/ 91555714Skris a->neg=rand_neg(); 91655714Skris b->neg=rand_neg(); 91755714Skris if (!BN_mod_mul(e,a,b,c,ctx)) 91855714Skris { 91955714Skris unsigned long l; 92055714Skris 92155714Skris while ((l=ERR_get_error())) 92255714Skris fprintf(stderr,"ERROR:%s\n", 92355714Skris ERR_error_string(l,NULL)); 924109998Smarkm EXIT(1); 92555714Skris } 92655714Skris if (bp != NULL) 92755714Skris { 92855714Skris if (!results) 92955714Skris { 93055714Skris BN_print(bp,a); 93155714Skris BIO_puts(bp," * "); 93255714Skris BN_print(bp,b); 93355714Skris BIO_puts(bp," % "); 93455714Skris BN_print(bp,c); 935109998Smarkm if ((a->neg ^ b->neg) && !BN_is_zero(e)) 936109998Smarkm { 937109998Smarkm /* If (a*b) % c is negative, c must be added 938109998Smarkm * in order to obtain the normalized remainder 939109998Smarkm * (new with OpenSSL 0.9.7, previous versions of 940109998Smarkm * BN_mod_mul could generate negative results) 941109998Smarkm */ 942109998Smarkm BIO_puts(bp," + "); 943109998Smarkm BN_print(bp,c); 944109998Smarkm } 94555714Skris BIO_puts(bp," - "); 94655714Skris } 94755714Skris BN_print(bp,e); 94855714Skris BIO_puts(bp,"\n"); 94955714Skris } 95055714Skris BN_mul(d,a,b,ctx); 95155714Skris BN_sub(d,d,e); 95255714Skris BN_div(a,b,d,c,ctx); 95355714Skris if(!BN_is_zero(b)) 95455714Skris { 95559191Skris fprintf(stderr,"Modulo multiply test failed!\n"); 956109998Smarkm ERR_print_errors_fp(stderr); 95755714Skris return 0; 95855714Skris } 95955714Skris } 960109998Smarkm } 96155714Skris BN_free(a); 96255714Skris BN_free(b); 96355714Skris BN_free(c); 96455714Skris BN_free(d); 96555714Skris BN_free(e); 96655714Skris return(1); 96755714Skris } 96855714Skris 96955714Skrisint test_mod_exp(BIO *bp, BN_CTX *ctx) 97055714Skris { 97155714Skris BIGNUM *a,*b,*c,*d,*e; 97255714Skris int i; 97355714Skris 97455714Skris a=BN_new(); 97555714Skris b=BN_new(); 97655714Skris c=BN_new(); 97755714Skris d=BN_new(); 97855714Skris e=BN_new(); 97955714Skris 98076866Skris BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */ 98159191Skris for (i=0; i<num2; i++) 98255714Skris { 98376866Skris BN_bntest_rand(a,20+i*5,0,0); /**/ 98476866Skris BN_bntest_rand(b,2+i,0,0); /**/ 98555714Skris 98655714Skris if (!BN_mod_exp(d,a,b,c,ctx)) 987194206Ssimon return(0); 98855714Skris 98955714Skris if (bp != NULL) 99055714Skris { 99155714Skris if (!results) 99255714Skris { 99355714Skris BN_print(bp,a); 99455714Skris BIO_puts(bp," ^ "); 99555714Skris BN_print(bp,b); 99655714Skris BIO_puts(bp," % "); 99755714Skris BN_print(bp,c); 99855714Skris BIO_puts(bp," - "); 99955714Skris } 100055714Skris BN_print(bp,d); 100155714Skris BIO_puts(bp,"\n"); 100255714Skris } 100355714Skris BN_exp(e,a,b,ctx); 100455714Skris BN_sub(e,e,d); 100555714Skris BN_div(a,b,e,c,ctx); 100655714Skris if(!BN_is_zero(b)) 100755714Skris { 100859191Skris fprintf(stderr,"Modulo exponentiation test failed!\n"); 100955714Skris return 0; 101055714Skris } 101155714Skris } 101255714Skris BN_free(a); 101355714Skris BN_free(b); 101455714Skris BN_free(c); 101555714Skris BN_free(d); 101655714Skris BN_free(e); 101755714Skris return(1); 101855714Skris } 101955714Skris 1020160814Ssimonint test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx) 1021160814Ssimon { 1022160814Ssimon BIGNUM *a,*b,*c,*d,*e; 1023160814Ssimon int i; 1024160814Ssimon 1025160814Ssimon a=BN_new(); 1026160814Ssimon b=BN_new(); 1027160814Ssimon c=BN_new(); 1028160814Ssimon d=BN_new(); 1029160814Ssimon e=BN_new(); 1030160814Ssimon 1031160814Ssimon BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */ 1032160814Ssimon for (i=0; i<num2; i++) 1033160814Ssimon { 1034160814Ssimon BN_bntest_rand(a,20+i*5,0,0); /**/ 1035160814Ssimon BN_bntest_rand(b,2+i,0,0); /**/ 1036160814Ssimon 1037160814Ssimon if (!BN_mod_exp_mont_consttime(d,a,b,c,ctx,NULL)) 1038160814Ssimon return(00); 1039160814Ssimon 1040160814Ssimon if (bp != NULL) 1041160814Ssimon { 1042160814Ssimon if (!results) 1043160814Ssimon { 1044160814Ssimon BN_print(bp,a); 1045160814Ssimon BIO_puts(bp," ^ "); 1046160814Ssimon BN_print(bp,b); 1047160814Ssimon BIO_puts(bp," % "); 1048160814Ssimon BN_print(bp,c); 1049160814Ssimon BIO_puts(bp," - "); 1050160814Ssimon } 1051160814Ssimon BN_print(bp,d); 1052160814Ssimon BIO_puts(bp,"\n"); 1053160814Ssimon } 1054160814Ssimon BN_exp(e,a,b,ctx); 1055160814Ssimon BN_sub(e,e,d); 1056160814Ssimon BN_div(a,b,e,c,ctx); 1057160814Ssimon if(!BN_is_zero(b)) 1058160814Ssimon { 1059160814Ssimon fprintf(stderr,"Modulo exponentiation test failed!\n"); 1060160814Ssimon return 0; 1061160814Ssimon } 1062160814Ssimon } 1063160814Ssimon BN_free(a); 1064160814Ssimon BN_free(b); 1065160814Ssimon BN_free(c); 1066160814Ssimon BN_free(d); 1067160814Ssimon BN_free(e); 1068160814Ssimon return(1); 1069160814Ssimon } 1070160814Ssimon 1071279264Sdelphij/* Test constant-time modular exponentiation with 1024-bit inputs, 1072279264Sdelphij * which on x86_64 cause a different code branch to be taken. 1073279264Sdelphij */ 1074279264Sdelphijint test_mod_exp_mont5(BIO *bp, BN_CTX *ctx) 1075279264Sdelphij { 1076279264Sdelphij BIGNUM *a,*p,*m,*d,*e; 1077279264Sdelphij 1078279264Sdelphij BN_MONT_CTX *mont; 1079279264Sdelphij 1080279264Sdelphij a=BN_new(); 1081279264Sdelphij p=BN_new(); 1082279264Sdelphij m=BN_new(); 1083279264Sdelphij d=BN_new(); 1084279264Sdelphij e=BN_new(); 1085279264Sdelphij 1086279264Sdelphij mont = BN_MONT_CTX_new(); 1087279264Sdelphij 1088279264Sdelphij BN_bntest_rand(m,1024,0,1); /* must be odd for montgomery */ 1089279264Sdelphij /* Zero exponent */ 1090279264Sdelphij BN_bntest_rand(a,1024,0,0); 1091279264Sdelphij BN_zero(p); 1092279264Sdelphij if(!BN_mod_exp_mont_consttime(d,a,p,m,ctx,NULL)) 1093279264Sdelphij return 0; 1094279264Sdelphij if(!BN_is_one(d)) 1095279264Sdelphij { 1096279264Sdelphij fprintf(stderr, "Modular exponentiation test failed!\n"); 1097279264Sdelphij return 0; 1098279264Sdelphij } 1099279264Sdelphij /* Zero input */ 1100279264Sdelphij BN_bntest_rand(p,1024,0,0); 1101279264Sdelphij BN_zero(a); 1102279264Sdelphij if(!BN_mod_exp_mont_consttime(d,a,p,m,ctx,NULL)) 1103279264Sdelphij return 0; 1104279264Sdelphij if(!BN_is_zero(d)) 1105279264Sdelphij { 1106279264Sdelphij fprintf(stderr, "Modular exponentiation test failed!\n"); 1107279264Sdelphij return 0; 1108279264Sdelphij } 1109279264Sdelphij /* Craft an input whose Montgomery representation is 1, 1110279264Sdelphij * i.e., shorter than the modulus m, in order to test 1111279264Sdelphij * the const time precomputation scattering/gathering. 1112279264Sdelphij */ 1113279264Sdelphij BN_one(a); 1114279264Sdelphij BN_MONT_CTX_set(mont,m,ctx); 1115279264Sdelphij if(!BN_from_montgomery(e,a,mont,ctx)) 1116279264Sdelphij return 0; 1117279264Sdelphij if(!BN_mod_exp_mont_consttime(d,e,p,m,ctx,NULL)) 1118279264Sdelphij return 0; 1119279264Sdelphij if(!BN_mod_exp_simple(a,e,p,m,ctx)) 1120279264Sdelphij return 0; 1121279264Sdelphij if(BN_cmp(a,d) != 0) 1122279264Sdelphij { 1123279264Sdelphij fprintf(stderr,"Modular exponentiation test failed!\n"); 1124279264Sdelphij return 0; 1125279264Sdelphij } 1126279264Sdelphij /* Finally, some regular test vectors. */ 1127279264Sdelphij BN_bntest_rand(e,1024,0,0); 1128279264Sdelphij if(!BN_mod_exp_mont_consttime(d,e,p,m,ctx,NULL)) 1129279264Sdelphij return 0; 1130279264Sdelphij if(!BN_mod_exp_simple(a,e,p,m,ctx)) 1131279264Sdelphij return 0; 1132279264Sdelphij if(BN_cmp(a,d) != 0) 1133279264Sdelphij { 1134279264Sdelphij fprintf(stderr,"Modular exponentiation test failed!\n"); 1135279264Sdelphij return 0; 1136279264Sdelphij } 1137279264Sdelphij BN_free(a); 1138279264Sdelphij BN_free(p); 1139279264Sdelphij BN_free(m); 1140279264Sdelphij BN_free(d); 1141279264Sdelphij BN_free(e); 1142279264Sdelphij return(1); 1143279264Sdelphij } 1144279264Sdelphij 114555714Skrisint test_exp(BIO *bp, BN_CTX *ctx) 114655714Skris { 114755714Skris BIGNUM *a,*b,*d,*e,*one; 114855714Skris int i; 114955714Skris 115055714Skris a=BN_new(); 115155714Skris b=BN_new(); 115255714Skris d=BN_new(); 115355714Skris e=BN_new(); 115455714Skris one=BN_new(); 115555714Skris BN_one(one); 115655714Skris 115759191Skris for (i=0; i<num2; i++) 115855714Skris { 115976866Skris BN_bntest_rand(a,20+i*5,0,0); /**/ 116076866Skris BN_bntest_rand(b,2+i,0,0); /**/ 116155714Skris 1162205128Ssimon if (BN_exp(d,a,b,ctx) <= 0) 1163194206Ssimon return(0); 116455714Skris 116555714Skris if (bp != NULL) 116655714Skris { 116755714Skris if (!results) 116855714Skris { 116955714Skris BN_print(bp,a); 117055714Skris BIO_puts(bp," ^ "); 117155714Skris BN_print(bp,b); 117255714Skris BIO_puts(bp," - "); 117355714Skris } 117455714Skris BN_print(bp,d); 117555714Skris BIO_puts(bp,"\n"); 117655714Skris } 117755714Skris BN_one(e); 117855714Skris for( ; !BN_is_zero(b) ; BN_sub(b,b,one)) 117955714Skris BN_mul(e,e,a,ctx); 118055714Skris BN_sub(e,e,d); 118155714Skris if(!BN_is_zero(e)) 118255714Skris { 118359191Skris fprintf(stderr,"Exponentiation test failed!\n"); 118455714Skris return 0; 118555714Skris } 118655714Skris } 118755714Skris BN_free(a); 118855714Skris BN_free(b); 118955714Skris BN_free(d); 119055714Skris BN_free(e); 119155714Skris BN_free(one); 119255714Skris return(1); 119355714Skris } 1194238405Sjkim#ifndef OPENSSL_NO_EC2M 1195160814Ssimonint test_gf2m_add(BIO *bp) 1196109998Smarkm { 1197160814Ssimon BIGNUM a,b,c; 1198160814Ssimon int i, ret = 0; 1199160814Ssimon 1200160814Ssimon BN_init(&a); 1201160814Ssimon BN_init(&b); 1202160814Ssimon BN_init(&c); 1203160814Ssimon 1204160814Ssimon for (i=0; i<num0; i++) 1205160814Ssimon { 1206160814Ssimon BN_rand(&a,512,0,0); 1207160814Ssimon BN_copy(&b, BN_value_one()); 1208160814Ssimon a.neg=rand_neg(); 1209160814Ssimon b.neg=rand_neg(); 1210160814Ssimon BN_GF2m_add(&c,&a,&b); 1211160814Ssimon#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ 1212160814Ssimon if (bp != NULL) 1213160814Ssimon { 1214160814Ssimon if (!results) 1215160814Ssimon { 1216160814Ssimon BN_print(bp,&a); 1217160814Ssimon BIO_puts(bp," ^ "); 1218160814Ssimon BN_print(bp,&b); 1219160814Ssimon BIO_puts(bp," = "); 1220160814Ssimon } 1221160814Ssimon BN_print(bp,&c); 1222160814Ssimon BIO_puts(bp,"\n"); 1223160814Ssimon } 1224160814Ssimon#endif 1225160814Ssimon /* Test that two added values have the correct parity. */ 1226160814Ssimon if((BN_is_odd(&a) && BN_is_odd(&c)) || (!BN_is_odd(&a) && !BN_is_odd(&c))) 1227160814Ssimon { 1228160814Ssimon fprintf(stderr,"GF(2^m) addition test (a) failed!\n"); 1229160814Ssimon goto err; 1230160814Ssimon } 1231160814Ssimon BN_GF2m_add(&c,&c,&c); 1232160814Ssimon /* Test that c + c = 0. */ 1233160814Ssimon if(!BN_is_zero(&c)) 1234160814Ssimon { 1235160814Ssimon fprintf(stderr,"GF(2^m) addition test (b) failed!\n"); 1236160814Ssimon goto err; 1237160814Ssimon } 1238160814Ssimon } 1239160814Ssimon ret = 1; 1240160814Ssimon err: 1241160814Ssimon BN_free(&a); 1242160814Ssimon BN_free(&b); 1243160814Ssimon BN_free(&c); 1244160814Ssimon return ret; 1245160814Ssimon } 1246160814Ssimon 1247160814Ssimonint test_gf2m_mod(BIO *bp) 1248160814Ssimon { 1249160814Ssimon BIGNUM *a,*b[2],*c,*d,*e; 1250160814Ssimon int i, j, ret = 0; 1251238405Sjkim int p0[] = {163,7,6,3,0,-1}; 1252238405Sjkim int p1[] = {193,15,0,-1}; 1253160814Ssimon 1254160814Ssimon a=BN_new(); 1255160814Ssimon b[0]=BN_new(); 1256160814Ssimon b[1]=BN_new(); 1257160814Ssimon c=BN_new(); 1258160814Ssimon d=BN_new(); 1259160814Ssimon e=BN_new(); 1260160814Ssimon 1261160814Ssimon BN_GF2m_arr2poly(p0, b[0]); 1262160814Ssimon BN_GF2m_arr2poly(p1, b[1]); 1263160814Ssimon 1264160814Ssimon for (i=0; i<num0; i++) 1265160814Ssimon { 1266160814Ssimon BN_bntest_rand(a, 1024, 0, 0); 1267160814Ssimon for (j=0; j < 2; j++) 1268160814Ssimon { 1269160814Ssimon BN_GF2m_mod(c, a, b[j]); 1270160814Ssimon#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ 1271160814Ssimon if (bp != NULL) 1272160814Ssimon { 1273160814Ssimon if (!results) 1274160814Ssimon { 1275160814Ssimon BN_print(bp,a); 1276160814Ssimon BIO_puts(bp," % "); 1277160814Ssimon BN_print(bp,b[j]); 1278160814Ssimon BIO_puts(bp," - "); 1279160814Ssimon BN_print(bp,c); 1280160814Ssimon BIO_puts(bp,"\n"); 1281160814Ssimon } 1282160814Ssimon } 1283160814Ssimon#endif 1284160814Ssimon BN_GF2m_add(d, a, c); 1285160814Ssimon BN_GF2m_mod(e, d, b[j]); 1286160814Ssimon /* Test that a + (a mod p) mod p == 0. */ 1287160814Ssimon if(!BN_is_zero(e)) 1288160814Ssimon { 1289160814Ssimon fprintf(stderr,"GF(2^m) modulo test failed!\n"); 1290160814Ssimon goto err; 1291160814Ssimon } 1292160814Ssimon } 1293160814Ssimon } 1294160814Ssimon ret = 1; 1295160814Ssimon err: 1296160814Ssimon BN_free(a); 1297160814Ssimon BN_free(b[0]); 1298160814Ssimon BN_free(b[1]); 1299160814Ssimon BN_free(c); 1300160814Ssimon BN_free(d); 1301160814Ssimon BN_free(e); 1302160814Ssimon return ret; 1303160814Ssimon } 1304160814Ssimon 1305160814Ssimonint test_gf2m_mod_mul(BIO *bp,BN_CTX *ctx) 1306160814Ssimon { 1307160814Ssimon BIGNUM *a,*b[2],*c,*d,*e,*f,*g,*h; 1308160814Ssimon int i, j, ret = 0; 1309238405Sjkim int p0[] = {163,7,6,3,0,-1}; 1310238405Sjkim int p1[] = {193,15,0,-1}; 1311160814Ssimon 1312160814Ssimon a=BN_new(); 1313160814Ssimon b[0]=BN_new(); 1314160814Ssimon b[1]=BN_new(); 1315160814Ssimon c=BN_new(); 1316160814Ssimon d=BN_new(); 1317160814Ssimon e=BN_new(); 1318160814Ssimon f=BN_new(); 1319160814Ssimon g=BN_new(); 1320160814Ssimon h=BN_new(); 1321160814Ssimon 1322160814Ssimon BN_GF2m_arr2poly(p0, b[0]); 1323160814Ssimon BN_GF2m_arr2poly(p1, b[1]); 1324160814Ssimon 1325160814Ssimon for (i=0; i<num0; i++) 1326160814Ssimon { 1327160814Ssimon BN_bntest_rand(a, 1024, 0, 0); 1328160814Ssimon BN_bntest_rand(c, 1024, 0, 0); 1329160814Ssimon BN_bntest_rand(d, 1024, 0, 0); 1330160814Ssimon for (j=0; j < 2; j++) 1331160814Ssimon { 1332160814Ssimon BN_GF2m_mod_mul(e, a, c, b[j], ctx); 1333160814Ssimon#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ 1334160814Ssimon if (bp != NULL) 1335160814Ssimon { 1336160814Ssimon if (!results) 1337160814Ssimon { 1338160814Ssimon BN_print(bp,a); 1339160814Ssimon BIO_puts(bp," * "); 1340160814Ssimon BN_print(bp,c); 1341160814Ssimon BIO_puts(bp," % "); 1342160814Ssimon BN_print(bp,b[j]); 1343160814Ssimon BIO_puts(bp," - "); 1344160814Ssimon BN_print(bp,e); 1345160814Ssimon BIO_puts(bp,"\n"); 1346160814Ssimon } 1347160814Ssimon } 1348160814Ssimon#endif 1349160814Ssimon BN_GF2m_add(f, a, d); 1350160814Ssimon BN_GF2m_mod_mul(g, f, c, b[j], ctx); 1351160814Ssimon BN_GF2m_mod_mul(h, d, c, b[j], ctx); 1352160814Ssimon BN_GF2m_add(f, e, g); 1353160814Ssimon BN_GF2m_add(f, f, h); 1354160814Ssimon /* Test that (a+d)*c = a*c + d*c. */ 1355160814Ssimon if(!BN_is_zero(f)) 1356160814Ssimon { 1357160814Ssimon fprintf(stderr,"GF(2^m) modular multiplication test failed!\n"); 1358160814Ssimon goto err; 1359160814Ssimon } 1360160814Ssimon } 1361160814Ssimon } 1362160814Ssimon ret = 1; 1363160814Ssimon err: 1364160814Ssimon BN_free(a); 1365160814Ssimon BN_free(b[0]); 1366160814Ssimon BN_free(b[1]); 1367160814Ssimon BN_free(c); 1368160814Ssimon BN_free(d); 1369160814Ssimon BN_free(e); 1370160814Ssimon BN_free(f); 1371160814Ssimon BN_free(g); 1372160814Ssimon BN_free(h); 1373160814Ssimon return ret; 1374160814Ssimon } 1375160814Ssimon 1376160814Ssimonint test_gf2m_mod_sqr(BIO *bp,BN_CTX *ctx) 1377160814Ssimon { 1378160814Ssimon BIGNUM *a,*b[2],*c,*d; 1379160814Ssimon int i, j, ret = 0; 1380238405Sjkim int p0[] = {163,7,6,3,0,-1}; 1381238405Sjkim int p1[] = {193,15,0,-1}; 1382160814Ssimon 1383160814Ssimon a=BN_new(); 1384160814Ssimon b[0]=BN_new(); 1385160814Ssimon b[1]=BN_new(); 1386160814Ssimon c=BN_new(); 1387160814Ssimon d=BN_new(); 1388160814Ssimon 1389160814Ssimon BN_GF2m_arr2poly(p0, b[0]); 1390160814Ssimon BN_GF2m_arr2poly(p1, b[1]); 1391160814Ssimon 1392160814Ssimon for (i=0; i<num0; i++) 1393160814Ssimon { 1394160814Ssimon BN_bntest_rand(a, 1024, 0, 0); 1395160814Ssimon for (j=0; j < 2; j++) 1396160814Ssimon { 1397160814Ssimon BN_GF2m_mod_sqr(c, a, b[j], ctx); 1398160814Ssimon BN_copy(d, a); 1399160814Ssimon BN_GF2m_mod_mul(d, a, d, b[j], ctx); 1400160814Ssimon#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ 1401160814Ssimon if (bp != NULL) 1402160814Ssimon { 1403160814Ssimon if (!results) 1404160814Ssimon { 1405160814Ssimon BN_print(bp,a); 1406160814Ssimon BIO_puts(bp," ^ 2 % "); 1407160814Ssimon BN_print(bp,b[j]); 1408160814Ssimon BIO_puts(bp, " = "); 1409160814Ssimon BN_print(bp,c); 1410160814Ssimon BIO_puts(bp,"; a * a = "); 1411160814Ssimon BN_print(bp,d); 1412160814Ssimon BIO_puts(bp,"\n"); 1413160814Ssimon } 1414160814Ssimon } 1415160814Ssimon#endif 1416160814Ssimon BN_GF2m_add(d, c, d); 1417160814Ssimon /* Test that a*a = a^2. */ 1418160814Ssimon if(!BN_is_zero(d)) 1419160814Ssimon { 1420160814Ssimon fprintf(stderr,"GF(2^m) modular squaring test failed!\n"); 1421160814Ssimon goto err; 1422160814Ssimon } 1423160814Ssimon } 1424160814Ssimon } 1425160814Ssimon ret = 1; 1426160814Ssimon err: 1427160814Ssimon BN_free(a); 1428160814Ssimon BN_free(b[0]); 1429160814Ssimon BN_free(b[1]); 1430160814Ssimon BN_free(c); 1431160814Ssimon BN_free(d); 1432160814Ssimon return ret; 1433160814Ssimon } 1434160814Ssimon 1435160814Ssimonint test_gf2m_mod_inv(BIO *bp,BN_CTX *ctx) 1436160814Ssimon { 1437160814Ssimon BIGNUM *a,*b[2],*c,*d; 1438160814Ssimon int i, j, ret = 0; 1439238405Sjkim int p0[] = {163,7,6,3,0,-1}; 1440238405Sjkim int p1[] = {193,15,0,-1}; 1441160814Ssimon 1442160814Ssimon a=BN_new(); 1443160814Ssimon b[0]=BN_new(); 1444160814Ssimon b[1]=BN_new(); 1445160814Ssimon c=BN_new(); 1446160814Ssimon d=BN_new(); 1447160814Ssimon 1448160814Ssimon BN_GF2m_arr2poly(p0, b[0]); 1449160814Ssimon BN_GF2m_arr2poly(p1, b[1]); 1450160814Ssimon 1451160814Ssimon for (i=0; i<num0; i++) 1452160814Ssimon { 1453160814Ssimon BN_bntest_rand(a, 512, 0, 0); 1454160814Ssimon for (j=0; j < 2; j++) 1455160814Ssimon { 1456160814Ssimon BN_GF2m_mod_inv(c, a, b[j], ctx); 1457160814Ssimon BN_GF2m_mod_mul(d, a, c, b[j], ctx); 1458160814Ssimon#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ 1459160814Ssimon if (bp != NULL) 1460160814Ssimon { 1461160814Ssimon if (!results) 1462160814Ssimon { 1463160814Ssimon BN_print(bp,a); 1464160814Ssimon BIO_puts(bp, " * "); 1465160814Ssimon BN_print(bp,c); 1466160814Ssimon BIO_puts(bp," - 1 % "); 1467160814Ssimon BN_print(bp,b[j]); 1468160814Ssimon BIO_puts(bp,"\n"); 1469160814Ssimon } 1470160814Ssimon } 1471160814Ssimon#endif 1472160814Ssimon /* Test that ((1/a)*a) = 1. */ 1473160814Ssimon if(!BN_is_one(d)) 1474160814Ssimon { 1475160814Ssimon fprintf(stderr,"GF(2^m) modular inversion test failed!\n"); 1476160814Ssimon goto err; 1477160814Ssimon } 1478160814Ssimon } 1479160814Ssimon } 1480160814Ssimon ret = 1; 1481160814Ssimon err: 1482160814Ssimon BN_free(a); 1483160814Ssimon BN_free(b[0]); 1484160814Ssimon BN_free(b[1]); 1485160814Ssimon BN_free(c); 1486160814Ssimon BN_free(d); 1487160814Ssimon return ret; 1488160814Ssimon } 1489160814Ssimon 1490160814Ssimonint test_gf2m_mod_div(BIO *bp,BN_CTX *ctx) 1491160814Ssimon { 1492160814Ssimon BIGNUM *a,*b[2],*c,*d,*e,*f; 1493160814Ssimon int i, j, ret = 0; 1494238405Sjkim int p0[] = {163,7,6,3,0,-1}; 1495238405Sjkim int p1[] = {193,15,0,-1}; 1496160814Ssimon 1497160814Ssimon a=BN_new(); 1498160814Ssimon b[0]=BN_new(); 1499160814Ssimon b[1]=BN_new(); 1500160814Ssimon c=BN_new(); 1501160814Ssimon d=BN_new(); 1502160814Ssimon e=BN_new(); 1503160814Ssimon f=BN_new(); 1504160814Ssimon 1505160814Ssimon BN_GF2m_arr2poly(p0, b[0]); 1506160814Ssimon BN_GF2m_arr2poly(p1, b[1]); 1507160814Ssimon 1508160814Ssimon for (i=0; i<num0; i++) 1509160814Ssimon { 1510160814Ssimon BN_bntest_rand(a, 512, 0, 0); 1511160814Ssimon BN_bntest_rand(c, 512, 0, 0); 1512160814Ssimon for (j=0; j < 2; j++) 1513160814Ssimon { 1514160814Ssimon BN_GF2m_mod_div(d, a, c, b[j], ctx); 1515160814Ssimon BN_GF2m_mod_mul(e, d, c, b[j], ctx); 1516160814Ssimon BN_GF2m_mod_div(f, a, e, b[j], ctx); 1517160814Ssimon#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ 1518160814Ssimon if (bp != NULL) 1519160814Ssimon { 1520160814Ssimon if (!results) 1521160814Ssimon { 1522160814Ssimon BN_print(bp,a); 1523160814Ssimon BIO_puts(bp, " = "); 1524160814Ssimon BN_print(bp,c); 1525160814Ssimon BIO_puts(bp," * "); 1526160814Ssimon BN_print(bp,d); 1527160814Ssimon BIO_puts(bp, " % "); 1528160814Ssimon BN_print(bp,b[j]); 1529160814Ssimon BIO_puts(bp,"\n"); 1530160814Ssimon } 1531160814Ssimon } 1532160814Ssimon#endif 1533160814Ssimon /* Test that ((a/c)*c)/a = 1. */ 1534160814Ssimon if(!BN_is_one(f)) 1535160814Ssimon { 1536160814Ssimon fprintf(stderr,"GF(2^m) modular division test failed!\n"); 1537160814Ssimon goto err; 1538160814Ssimon } 1539160814Ssimon } 1540160814Ssimon } 1541160814Ssimon ret = 1; 1542160814Ssimon err: 1543160814Ssimon BN_free(a); 1544160814Ssimon BN_free(b[0]); 1545160814Ssimon BN_free(b[1]); 1546160814Ssimon BN_free(c); 1547160814Ssimon BN_free(d); 1548160814Ssimon BN_free(e); 1549160814Ssimon BN_free(f); 1550160814Ssimon return ret; 1551160814Ssimon } 1552160814Ssimon 1553160814Ssimonint test_gf2m_mod_exp(BIO *bp,BN_CTX *ctx) 1554160814Ssimon { 1555160814Ssimon BIGNUM *a,*b[2],*c,*d,*e,*f; 1556160814Ssimon int i, j, ret = 0; 1557238405Sjkim int p0[] = {163,7,6,3,0,-1}; 1558238405Sjkim int p1[] = {193,15,0,-1}; 1559160814Ssimon 1560160814Ssimon a=BN_new(); 1561160814Ssimon b[0]=BN_new(); 1562160814Ssimon b[1]=BN_new(); 1563160814Ssimon c=BN_new(); 1564160814Ssimon d=BN_new(); 1565160814Ssimon e=BN_new(); 1566160814Ssimon f=BN_new(); 1567160814Ssimon 1568160814Ssimon BN_GF2m_arr2poly(p0, b[0]); 1569160814Ssimon BN_GF2m_arr2poly(p1, b[1]); 1570160814Ssimon 1571160814Ssimon for (i=0; i<num0; i++) 1572160814Ssimon { 1573160814Ssimon BN_bntest_rand(a, 512, 0, 0); 1574160814Ssimon BN_bntest_rand(c, 512, 0, 0); 1575160814Ssimon BN_bntest_rand(d, 512, 0, 0); 1576160814Ssimon for (j=0; j < 2; j++) 1577160814Ssimon { 1578160814Ssimon BN_GF2m_mod_exp(e, a, c, b[j], ctx); 1579160814Ssimon BN_GF2m_mod_exp(f, a, d, b[j], ctx); 1580160814Ssimon BN_GF2m_mod_mul(e, e, f, b[j], ctx); 1581160814Ssimon BN_add(f, c, d); 1582160814Ssimon BN_GF2m_mod_exp(f, a, f, b[j], ctx); 1583160814Ssimon#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ 1584160814Ssimon if (bp != NULL) 1585160814Ssimon { 1586160814Ssimon if (!results) 1587160814Ssimon { 1588160814Ssimon BN_print(bp,a); 1589160814Ssimon BIO_puts(bp, " ^ ("); 1590160814Ssimon BN_print(bp,c); 1591160814Ssimon BIO_puts(bp," + "); 1592160814Ssimon BN_print(bp,d); 1593160814Ssimon BIO_puts(bp, ") = "); 1594160814Ssimon BN_print(bp,e); 1595160814Ssimon BIO_puts(bp, "; - "); 1596160814Ssimon BN_print(bp,f); 1597160814Ssimon BIO_puts(bp, " % "); 1598160814Ssimon BN_print(bp,b[j]); 1599160814Ssimon BIO_puts(bp,"\n"); 1600160814Ssimon } 1601160814Ssimon } 1602160814Ssimon#endif 1603160814Ssimon BN_GF2m_add(f, e, f); 1604160814Ssimon /* Test that a^(c+d)=a^c*a^d. */ 1605160814Ssimon if(!BN_is_zero(f)) 1606160814Ssimon { 1607160814Ssimon fprintf(stderr,"GF(2^m) modular exponentiation test failed!\n"); 1608160814Ssimon goto err; 1609160814Ssimon } 1610160814Ssimon } 1611160814Ssimon } 1612160814Ssimon ret = 1; 1613160814Ssimon err: 1614160814Ssimon BN_free(a); 1615160814Ssimon BN_free(b[0]); 1616160814Ssimon BN_free(b[1]); 1617160814Ssimon BN_free(c); 1618160814Ssimon BN_free(d); 1619160814Ssimon BN_free(e); 1620160814Ssimon BN_free(f); 1621160814Ssimon return ret; 1622160814Ssimon } 1623160814Ssimon 1624160814Ssimonint test_gf2m_mod_sqrt(BIO *bp,BN_CTX *ctx) 1625160814Ssimon { 1626160814Ssimon BIGNUM *a,*b[2],*c,*d,*e,*f; 1627160814Ssimon int i, j, ret = 0; 1628238405Sjkim int p0[] = {163,7,6,3,0,-1}; 1629238405Sjkim int p1[] = {193,15,0,-1}; 1630160814Ssimon 1631160814Ssimon a=BN_new(); 1632160814Ssimon b[0]=BN_new(); 1633160814Ssimon b[1]=BN_new(); 1634160814Ssimon c=BN_new(); 1635160814Ssimon d=BN_new(); 1636160814Ssimon e=BN_new(); 1637160814Ssimon f=BN_new(); 1638160814Ssimon 1639160814Ssimon BN_GF2m_arr2poly(p0, b[0]); 1640160814Ssimon BN_GF2m_arr2poly(p1, b[1]); 1641160814Ssimon 1642160814Ssimon for (i=0; i<num0; i++) 1643160814Ssimon { 1644160814Ssimon BN_bntest_rand(a, 512, 0, 0); 1645160814Ssimon for (j=0; j < 2; j++) 1646160814Ssimon { 1647160814Ssimon BN_GF2m_mod(c, a, b[j]); 1648160814Ssimon BN_GF2m_mod_sqrt(d, a, b[j], ctx); 1649160814Ssimon BN_GF2m_mod_sqr(e, d, b[j], ctx); 1650160814Ssimon#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ 1651160814Ssimon if (bp != NULL) 1652160814Ssimon { 1653160814Ssimon if (!results) 1654160814Ssimon { 1655160814Ssimon BN_print(bp,d); 1656160814Ssimon BIO_puts(bp, " ^ 2 - "); 1657160814Ssimon BN_print(bp,a); 1658160814Ssimon BIO_puts(bp,"\n"); 1659160814Ssimon } 1660160814Ssimon } 1661160814Ssimon#endif 1662160814Ssimon BN_GF2m_add(f, c, e); 1663160814Ssimon /* Test that d^2 = a, where d = sqrt(a). */ 1664160814Ssimon if(!BN_is_zero(f)) 1665160814Ssimon { 1666160814Ssimon fprintf(stderr,"GF(2^m) modular square root test failed!\n"); 1667160814Ssimon goto err; 1668160814Ssimon } 1669160814Ssimon } 1670160814Ssimon } 1671160814Ssimon ret = 1; 1672160814Ssimon err: 1673160814Ssimon BN_free(a); 1674160814Ssimon BN_free(b[0]); 1675160814Ssimon BN_free(b[1]); 1676160814Ssimon BN_free(c); 1677160814Ssimon BN_free(d); 1678160814Ssimon BN_free(e); 1679160814Ssimon BN_free(f); 1680160814Ssimon return ret; 1681160814Ssimon } 1682160814Ssimon 1683160814Ssimonint test_gf2m_mod_solve_quad(BIO *bp,BN_CTX *ctx) 1684160814Ssimon { 1685160814Ssimon BIGNUM *a,*b[2],*c,*d,*e; 1686160814Ssimon int i, j, s = 0, t, ret = 0; 1687238405Sjkim int p0[] = {163,7,6,3,0,-1}; 1688238405Sjkim int p1[] = {193,15,0,-1}; 1689160814Ssimon 1690160814Ssimon a=BN_new(); 1691160814Ssimon b[0]=BN_new(); 1692160814Ssimon b[1]=BN_new(); 1693160814Ssimon c=BN_new(); 1694160814Ssimon d=BN_new(); 1695160814Ssimon e=BN_new(); 1696160814Ssimon 1697160814Ssimon BN_GF2m_arr2poly(p0, b[0]); 1698160814Ssimon BN_GF2m_arr2poly(p1, b[1]); 1699160814Ssimon 1700160814Ssimon for (i=0; i<num0; i++) 1701160814Ssimon { 1702160814Ssimon BN_bntest_rand(a, 512, 0, 0); 1703160814Ssimon for (j=0; j < 2; j++) 1704160814Ssimon { 1705160814Ssimon t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx); 1706160814Ssimon if (t) 1707160814Ssimon { 1708160814Ssimon s++; 1709160814Ssimon BN_GF2m_mod_sqr(d, c, b[j], ctx); 1710160814Ssimon BN_GF2m_add(d, c, d); 1711160814Ssimon BN_GF2m_mod(e, a, b[j]); 1712160814Ssimon#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ 1713160814Ssimon if (bp != NULL) 1714160814Ssimon { 1715160814Ssimon if (!results) 1716160814Ssimon { 1717160814Ssimon BN_print(bp,c); 1718160814Ssimon BIO_puts(bp, " is root of z^2 + z = "); 1719160814Ssimon BN_print(bp,a); 1720160814Ssimon BIO_puts(bp, " % "); 1721160814Ssimon BN_print(bp,b[j]); 1722160814Ssimon BIO_puts(bp, "\n"); 1723160814Ssimon } 1724160814Ssimon } 1725160814Ssimon#endif 1726160814Ssimon BN_GF2m_add(e, e, d); 1727160814Ssimon /* Test that solution of quadratic c satisfies c^2 + c = a. */ 1728160814Ssimon if(!BN_is_zero(e)) 1729160814Ssimon { 1730160814Ssimon fprintf(stderr,"GF(2^m) modular solve quadratic test failed!\n"); 1731160814Ssimon goto err; 1732160814Ssimon } 1733160814Ssimon 1734160814Ssimon } 1735160814Ssimon else 1736160814Ssimon { 1737160814Ssimon#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ 1738160814Ssimon if (bp != NULL) 1739160814Ssimon { 1740160814Ssimon if (!results) 1741160814Ssimon { 1742160814Ssimon BIO_puts(bp, "There are no roots of z^2 + z = "); 1743160814Ssimon BN_print(bp,a); 1744160814Ssimon BIO_puts(bp, " % "); 1745160814Ssimon BN_print(bp,b[j]); 1746160814Ssimon BIO_puts(bp, "\n"); 1747160814Ssimon } 1748160814Ssimon } 1749160814Ssimon#endif 1750160814Ssimon } 1751160814Ssimon } 1752160814Ssimon } 1753160814Ssimon if (s == 0) 1754160814Ssimon { 1755160814Ssimon fprintf(stderr,"All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n", num0); 1756160814Ssimon fprintf(stderr,"this is very unlikely and probably indicates an error.\n"); 1757160814Ssimon goto err; 1758160814Ssimon } 1759160814Ssimon ret = 1; 1760160814Ssimon err: 1761160814Ssimon BN_free(a); 1762160814Ssimon BN_free(b[0]); 1763160814Ssimon BN_free(b[1]); 1764160814Ssimon BN_free(c); 1765160814Ssimon BN_free(d); 1766160814Ssimon BN_free(e); 1767160814Ssimon return ret; 1768160814Ssimon } 1769238405Sjkim#endif 1770160814Ssimonstatic int genprime_cb(int p, int n, BN_GENCB *arg) 1771160814Ssimon { 1772109998Smarkm char c='*'; 1773109998Smarkm 1774109998Smarkm if (p == 0) c='.'; 1775109998Smarkm if (p == 1) c='+'; 1776109998Smarkm if (p == 2) c='*'; 1777109998Smarkm if (p == 3) c='\n'; 1778109998Smarkm putc(c, stderr); 1779109998Smarkm fflush(stderr); 1780160814Ssimon return 1; 1781109998Smarkm } 1782109998Smarkm 1783109998Smarkmint test_kron(BIO *bp, BN_CTX *ctx) 1784109998Smarkm { 1785160814Ssimon BN_GENCB cb; 1786109998Smarkm BIGNUM *a,*b,*r,*t; 1787109998Smarkm int i; 1788109998Smarkm int legendre, kronecker; 1789109998Smarkm int ret = 0; 1790109998Smarkm 1791109998Smarkm a = BN_new(); 1792109998Smarkm b = BN_new(); 1793109998Smarkm r = BN_new(); 1794109998Smarkm t = BN_new(); 1795109998Smarkm if (a == NULL || b == NULL || r == NULL || t == NULL) goto err; 1796160814Ssimon 1797160814Ssimon BN_GENCB_set(&cb, genprime_cb, NULL); 1798109998Smarkm 1799109998Smarkm /* We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). 1800109998Smarkm * In this case we know that if b is prime, then BN_kronecker(a, b, ctx) 1801109998Smarkm * is congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). 1802109998Smarkm * So we generate a random prime b and compare these values 1803109998Smarkm * for a number of random a's. (That is, we run the Solovay-Strassen 1804109998Smarkm * primality test to confirm that b is prime, except that we 1805109998Smarkm * don't want to test whether b is prime but whether BN_kronecker 1806109998Smarkm * works.) */ 1807109998Smarkm 1808160814Ssimon if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, &cb)) goto err; 1809109998Smarkm b->neg = rand_neg(); 1810109998Smarkm putc('\n', stderr); 1811109998Smarkm 1812109998Smarkm for (i = 0; i < num0; i++) 1813109998Smarkm { 1814109998Smarkm if (!BN_bntest_rand(a, 512, 0, 0)) goto err; 1815109998Smarkm a->neg = rand_neg(); 1816109998Smarkm 1817109998Smarkm /* t := (|b|-1)/2 (note that b is odd) */ 1818109998Smarkm if (!BN_copy(t, b)) goto err; 1819109998Smarkm t->neg = 0; 1820109998Smarkm if (!BN_sub_word(t, 1)) goto err; 1821109998Smarkm if (!BN_rshift1(t, t)) goto err; 1822109998Smarkm /* r := a^t mod b */ 1823109998Smarkm b->neg=0; 1824109998Smarkm 1825109998Smarkm if (!BN_mod_exp_recp(r, a, t, b, ctx)) goto err; 1826109998Smarkm b->neg=1; 1827109998Smarkm 1828109998Smarkm if (BN_is_word(r, 1)) 1829109998Smarkm legendre = 1; 1830109998Smarkm else if (BN_is_zero(r)) 1831109998Smarkm legendre = 0; 1832109998Smarkm else 1833109998Smarkm { 1834109998Smarkm if (!BN_add_word(r, 1)) goto err; 1835109998Smarkm if (0 != BN_ucmp(r, b)) 1836109998Smarkm { 1837109998Smarkm fprintf(stderr, "Legendre symbol computation failed\n"); 1838109998Smarkm goto err; 1839109998Smarkm } 1840109998Smarkm legendre = -1; 1841109998Smarkm } 1842109998Smarkm 1843109998Smarkm kronecker = BN_kronecker(a, b, ctx); 1844109998Smarkm if (kronecker < -1) goto err; 1845109998Smarkm /* we actually need BN_kronecker(a, |b|) */ 1846109998Smarkm if (a->neg && b->neg) 1847109998Smarkm kronecker = -kronecker; 1848109998Smarkm 1849109998Smarkm if (legendre != kronecker) 1850109998Smarkm { 1851109998Smarkm fprintf(stderr, "legendre != kronecker; a = "); 1852109998Smarkm BN_print_fp(stderr, a); 1853109998Smarkm fprintf(stderr, ", b = "); 1854109998Smarkm BN_print_fp(stderr, b); 1855109998Smarkm fprintf(stderr, "\n"); 1856109998Smarkm goto err; 1857109998Smarkm } 1858109998Smarkm 1859109998Smarkm putc('.', stderr); 1860109998Smarkm fflush(stderr); 1861109998Smarkm } 1862109998Smarkm 1863109998Smarkm putc('\n', stderr); 1864109998Smarkm fflush(stderr); 1865109998Smarkm ret = 1; 1866109998Smarkm err: 1867109998Smarkm if (a != NULL) BN_free(a); 1868109998Smarkm if (b != NULL) BN_free(b); 1869109998Smarkm if (r != NULL) BN_free(r); 1870109998Smarkm if (t != NULL) BN_free(t); 1871109998Smarkm return ret; 1872109998Smarkm } 1873109998Smarkm 1874109998Smarkmint test_sqrt(BIO *bp, BN_CTX *ctx) 1875109998Smarkm { 1876160814Ssimon BN_GENCB cb; 1877109998Smarkm BIGNUM *a,*p,*r; 1878109998Smarkm int i, j; 1879109998Smarkm int ret = 0; 1880109998Smarkm 1881109998Smarkm a = BN_new(); 1882109998Smarkm p = BN_new(); 1883109998Smarkm r = BN_new(); 1884109998Smarkm if (a == NULL || p == NULL || r == NULL) goto err; 1885160814Ssimon 1886160814Ssimon BN_GENCB_set(&cb, genprime_cb, NULL); 1887160814Ssimon 1888109998Smarkm for (i = 0; i < 16; i++) 1889109998Smarkm { 1890109998Smarkm if (i < 8) 1891109998Smarkm { 1892109998Smarkm unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 }; 1893109998Smarkm 1894109998Smarkm if (!BN_set_word(p, primes[i])) goto err; 1895109998Smarkm } 1896109998Smarkm else 1897109998Smarkm { 1898109998Smarkm if (!BN_set_word(a, 32)) goto err; 1899109998Smarkm if (!BN_set_word(r, 2*i + 1)) goto err; 1900109998Smarkm 1901160814Ssimon if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb)) goto err; 1902109998Smarkm putc('\n', stderr); 1903109998Smarkm } 1904109998Smarkm p->neg = rand_neg(); 1905109998Smarkm 1906109998Smarkm for (j = 0; j < num2; j++) 1907109998Smarkm { 1908109998Smarkm /* construct 'a' such that it is a square modulo p, 1909109998Smarkm * but in general not a proper square and not reduced modulo p */ 1910109998Smarkm if (!BN_bntest_rand(r, 256, 0, 3)) goto err; 1911109998Smarkm if (!BN_nnmod(r, r, p, ctx)) goto err; 1912109998Smarkm if (!BN_mod_sqr(r, r, p, ctx)) goto err; 1913109998Smarkm if (!BN_bntest_rand(a, 256, 0, 3)) goto err; 1914109998Smarkm if (!BN_nnmod(a, a, p, ctx)) goto err; 1915109998Smarkm if (!BN_mod_sqr(a, a, p, ctx)) goto err; 1916109998Smarkm if (!BN_mul(a, a, r, ctx)) goto err; 1917109998Smarkm if (rand_neg()) 1918109998Smarkm if (!BN_sub(a, a, p)) goto err; 1919109998Smarkm 1920109998Smarkm if (!BN_mod_sqrt(r, a, p, ctx)) goto err; 1921109998Smarkm if (!BN_mod_sqr(r, r, p, ctx)) goto err; 1922109998Smarkm 1923109998Smarkm if (!BN_nnmod(a, a, p, ctx)) goto err; 1924109998Smarkm 1925109998Smarkm if (BN_cmp(a, r) != 0) 1926109998Smarkm { 1927109998Smarkm fprintf(stderr, "BN_mod_sqrt failed: a = "); 1928109998Smarkm BN_print_fp(stderr, a); 1929109998Smarkm fprintf(stderr, ", r = "); 1930109998Smarkm BN_print_fp(stderr, r); 1931109998Smarkm fprintf(stderr, ", p = "); 1932109998Smarkm BN_print_fp(stderr, p); 1933109998Smarkm fprintf(stderr, "\n"); 1934109998Smarkm goto err; 1935109998Smarkm } 1936109998Smarkm 1937109998Smarkm putc('.', stderr); 1938109998Smarkm fflush(stderr); 1939109998Smarkm } 1940109998Smarkm 1941109998Smarkm putc('\n', stderr); 1942109998Smarkm fflush(stderr); 1943109998Smarkm } 1944109998Smarkm ret = 1; 1945109998Smarkm err: 1946109998Smarkm if (a != NULL) BN_free(a); 1947109998Smarkm if (p != NULL) BN_free(p); 1948109998Smarkm if (r != NULL) BN_free(r); 1949109998Smarkm return ret; 1950109998Smarkm } 1951109998Smarkm 195255714Skrisint test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_) 195355714Skris { 195455714Skris BIGNUM *a,*b,*c,*d; 195555714Skris int i; 195655714Skris 195755714Skris b=BN_new(); 195855714Skris c=BN_new(); 195955714Skris d=BN_new(); 196055714Skris BN_one(c); 196155714Skris 196255714Skris if(a_) 196355714Skris a=a_; 196455714Skris else 196555714Skris { 196655714Skris a=BN_new(); 196776866Skris BN_bntest_rand(a,200,0,0); /**/ 196855714Skris a->neg=rand_neg(); 196955714Skris } 197059191Skris for (i=0; i<num0; i++) 197155714Skris { 197255714Skris BN_lshift(b,a,i+1); 197355714Skris BN_add(c,c,c); 197455714Skris if (bp != NULL) 197555714Skris { 197655714Skris if (!results) 197755714Skris { 197855714Skris BN_print(bp,a); 197955714Skris BIO_puts(bp," * "); 198055714Skris BN_print(bp,c); 198155714Skris BIO_puts(bp," - "); 198255714Skris } 198355714Skris BN_print(bp,b); 198455714Skris BIO_puts(bp,"\n"); 198555714Skris } 198655714Skris BN_mul(d,a,c,ctx); 198755714Skris BN_sub(d,d,b); 198855714Skris if(!BN_is_zero(d)) 198955714Skris { 199059191Skris fprintf(stderr,"Left shift test failed!\n"); 199159191Skris fprintf(stderr,"a="); 199259191Skris BN_print_fp(stderr,a); 199359191Skris fprintf(stderr,"\nb="); 199459191Skris BN_print_fp(stderr,b); 199559191Skris fprintf(stderr,"\nc="); 199659191Skris BN_print_fp(stderr,c); 199759191Skris fprintf(stderr,"\nd="); 199859191Skris BN_print_fp(stderr,d); 199959191Skris fprintf(stderr,"\n"); 200055714Skris return 0; 200155714Skris } 200255714Skris } 200355714Skris BN_free(a); 200455714Skris BN_free(b); 200555714Skris BN_free(c); 200655714Skris BN_free(d); 200755714Skris return(1); 200855714Skris } 200955714Skris 201055714Skrisint test_lshift1(BIO *bp) 201155714Skris { 201255714Skris BIGNUM *a,*b,*c; 201355714Skris int i; 201455714Skris 201555714Skris a=BN_new(); 201655714Skris b=BN_new(); 201755714Skris c=BN_new(); 201855714Skris 201976866Skris BN_bntest_rand(a,200,0,0); /**/ 202055714Skris a->neg=rand_neg(); 202159191Skris for (i=0; i<num0; i++) 202255714Skris { 202355714Skris BN_lshift1(b,a); 202455714Skris if (bp != NULL) 202555714Skris { 202655714Skris if (!results) 202755714Skris { 202855714Skris BN_print(bp,a); 202955714Skris BIO_puts(bp," * 2"); 203055714Skris BIO_puts(bp," - "); 203155714Skris } 203255714Skris BN_print(bp,b); 203355714Skris BIO_puts(bp,"\n"); 203455714Skris } 203555714Skris BN_add(c,a,a); 203655714Skris BN_sub(a,b,c); 203755714Skris if(!BN_is_zero(a)) 203855714Skris { 203959191Skris fprintf(stderr,"Left shift one test failed!\n"); 204055714Skris return 0; 204155714Skris } 204255714Skris 204355714Skris BN_copy(a,b); 204455714Skris } 204555714Skris BN_free(a); 204655714Skris BN_free(b); 204755714Skris BN_free(c); 204855714Skris return(1); 204955714Skris } 205055714Skris 205155714Skrisint test_rshift(BIO *bp,BN_CTX *ctx) 205255714Skris { 205355714Skris BIGNUM *a,*b,*c,*d,*e; 205455714Skris int i; 205555714Skris 205655714Skris a=BN_new(); 205755714Skris b=BN_new(); 205855714Skris c=BN_new(); 205955714Skris d=BN_new(); 206055714Skris e=BN_new(); 206155714Skris BN_one(c); 206255714Skris 206376866Skris BN_bntest_rand(a,200,0,0); /**/ 206455714Skris a->neg=rand_neg(); 206559191Skris for (i=0; i<num0; i++) 206655714Skris { 206755714Skris BN_rshift(b,a,i+1); 206855714Skris BN_add(c,c,c); 206955714Skris if (bp != NULL) 207055714Skris { 207155714Skris if (!results) 207255714Skris { 207355714Skris BN_print(bp,a); 207455714Skris BIO_puts(bp," / "); 207555714Skris BN_print(bp,c); 207655714Skris BIO_puts(bp," - "); 207755714Skris } 207855714Skris BN_print(bp,b); 207955714Skris BIO_puts(bp,"\n"); 208055714Skris } 208155714Skris BN_div(d,e,a,c,ctx); 208255714Skris BN_sub(d,d,b); 208355714Skris if(!BN_is_zero(d)) 208455714Skris { 208559191Skris fprintf(stderr,"Right shift test failed!\n"); 208655714Skris return 0; 208755714Skris } 208855714Skris } 208955714Skris BN_free(a); 209055714Skris BN_free(b); 209155714Skris BN_free(c); 209255714Skris BN_free(d); 209355714Skris BN_free(e); 209455714Skris return(1); 209555714Skris } 209655714Skris 209755714Skrisint test_rshift1(BIO *bp) 209855714Skris { 209955714Skris BIGNUM *a,*b,*c; 210055714Skris int i; 210155714Skris 210255714Skris a=BN_new(); 210355714Skris b=BN_new(); 210455714Skris c=BN_new(); 210555714Skris 210676866Skris BN_bntest_rand(a,200,0,0); /**/ 210755714Skris a->neg=rand_neg(); 210859191Skris for (i=0; i<num0; i++) 210955714Skris { 211055714Skris BN_rshift1(b,a); 211155714Skris if (bp != NULL) 211255714Skris { 211355714Skris if (!results) 211455714Skris { 211555714Skris BN_print(bp,a); 211655714Skris BIO_puts(bp," / 2"); 211755714Skris BIO_puts(bp," - "); 211855714Skris } 211955714Skris BN_print(bp,b); 212055714Skris BIO_puts(bp,"\n"); 212155714Skris } 212255714Skris BN_sub(c,a,b); 212355714Skris BN_sub(c,c,b); 2124109998Smarkm if(!BN_is_zero(c) && !BN_abs_is_word(c, 1)) 212555714Skris { 212659191Skris fprintf(stderr,"Right shift one test failed!\n"); 212755714Skris return 0; 212855714Skris } 212955714Skris BN_copy(a,b); 213055714Skris } 213155714Skris BN_free(a); 213255714Skris BN_free(b); 213355714Skris BN_free(c); 213455714Skris return(1); 213555714Skris } 213655714Skris 213755714Skrisint rand_neg(void) 213855714Skris { 213955714Skris static unsigned int neg=0; 214055714Skris static int sign[8]={0,0,0,1,1,0,1,1}; 214155714Skris 214255714Skris return(sign[(neg++)%8]); 214355714Skris } 2144