Binary field arithmetic contributed by Sun Microsystems. The 'OPENSSL_NO_SUN_DIV' default is still subject to change, so I didn't bother to finish the CHANGES entry yet. Submitted by: Douglas Stebila <douglas.stebila@sun.com>, Sheueling Chang <sheueling.chang@sun.com> (CHANGES entry by Bodo Moeller)
diff --git a/crypto/bn/bntest.c b/crypto/bn/bntest.c index 8158a67..377b5ba 100644 --- a/crypto/bn/bntest.c +++ b/crypto/bn/bntest.c
@@ -55,6 +55,32 @@ * copied and put under another distribution licence * [including the GNU Public Licence.] */ +/* ==================================================================== + * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. + * + * Portions of the attached software ("Contribution") are developed by + * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. + * + * The Contribution is licensed pursuant to the Eric Young open source + * license provided above. + * + * In addition, Sun covenants to all licensees who provide a reciprocal + * covenant with respect to their own patents if any, not to sue under + * current and future patent claims necessarily infringed by the making, + * using, practicing, selling, offering for sale and/or otherwise + * disposing of the Contribution as delivered hereunder + * (or portions thereof), provided that such covenant shall not apply: + * 1) for code that a licensee deletes from the Contribution; + * 2) separates from the Contribution; or + * 3) for infringements caused by: + * i) the modification of the Contribution or + * ii) the combination of the Contribution with other software or + * devices where such combination causes the infringement. + * + * The binary polynomial arithmetic software is originally written by + * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems Laboratories. + * + */ #include <stdio.h> #include <stdlib.h> @@ -91,6 +117,15 @@ int test_mod_mul(BIO *bp,BN_CTX *ctx); int test_mod_exp(BIO *bp,BN_CTX *ctx); int test_exp(BIO *bp,BN_CTX *ctx); +int test_gf2m_add(BIO *bp); +int test_gf2m_mod(BIO *bp); +int test_gf2m_mod_mul(BIO *bp,BN_CTX *ctx); +int test_gf2m_mod_sqr(BIO *bp,BN_CTX *ctx); +int test_gf2m_mod_inv(BIO *bp,BN_CTX *ctx); +int test_gf2m_mod_div(BIO *bp,BN_CTX *ctx); +int test_gf2m_mod_exp(BIO *bp,BN_CTX *ctx); +int test_gf2m_mod_sqrt(BIO *bp,BN_CTX *ctx); +int test_gf2m_mod_solve_quad(BIO *bp,BN_CTX *ctx); int test_kron(BIO *bp,BN_CTX *ctx); int test_sqrt(BIO *bp,BN_CTX *ctx); int rand_neg(void); @@ -226,6 +261,42 @@ if (!test_exp(out,ctx)) goto err; BIO_flush(out); + message(out,"BN_GF2m_add"); + if (!test_gf2m_add(out)) goto err; + BIO_flush(out); + + message(out,"BN_GF2m_mod"); + if (!test_gf2m_mod(out)) goto err; + BIO_flush(out); + + message(out,"BN_GF2m_mod_mul"); + if (!test_gf2m_mod_mul(out,ctx)) goto err; + BIO_flush(out); + + message(out,"BN_GF2m_mod_sqr"); + if (!test_gf2m_mod_sqr(out,ctx)) goto err; + BIO_flush(out); + + message(out,"BN_GF2m_mod_inv"); + if (!test_gf2m_mod_inv(out,ctx)) goto err; + BIO_flush(out); + + message(out,"BN_GF2m_mod_div"); + if (!test_gf2m_mod_div(out,ctx)) goto err; + BIO_flush(out); + + message(out,"BN_GF2m_mod_exp"); + if (!test_gf2m_mod_exp(out,ctx)) goto err; + BIO_flush(out); + + message(out,"BN_GF2m_mod_sqrt"); + if (!test_gf2m_mod_sqrt(out,ctx)) goto err; + BIO_flush(out); + + message(out,"BN_GF2m_mod_solve_quad"); + if (!test_gf2m_mod_solve_quad(out,ctx)) goto err; + BIO_flush(out); + message(out,"BN_kronecker"); if (!test_kron(out,ctx)) goto err; BIO_flush(out); @@ -872,6 +943,581 @@ return(1); } +int test_gf2m_add(BIO *bp) + { + BIGNUM a,b,c; + int i, ret = 0; + + BN_init(&a); + BN_init(&b); + BN_init(&c); + + for (i=0; i<num0; i++) + { + BN_rand(&a,512,0,0); + BN_copy(&b, BN_value_one()); + a.neg=rand_neg(); + b.neg=rand_neg(); + BN_GF2m_add(&c,&a,&b); +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ + if (bp != NULL) + { + if (!results) + { + BN_print(bp,&a); + BIO_puts(bp," ^ "); + BN_print(bp,&b); + BIO_puts(bp," = "); + } + BN_print(bp,&c); + BIO_puts(bp,"\n"); + } +#endif + /* Test that two added values have the correct parity. */ + if((BN_is_odd(&a) && BN_is_odd(&c)) || (!BN_is_odd(&a) && !BN_is_odd(&c))) + { + fprintf(stderr,"GF(2^m) addition test (a) failed!\n"); + goto err; + } + BN_GF2m_add(&c,&c,&c); + /* Test that c + c = 0. */ + if(!BN_is_zero(&c)) + { + fprintf(stderr,"GF(2^m) addition test (b) failed!\n"); + goto err; + } + } + ret = 1; + err: + BN_free(&a); + BN_free(&b); + BN_free(&c); + return ret; + } + +int test_gf2m_mod(BIO *bp) + { + BIGNUM *a,*b[2],*c,*d,*e; + int i, j, ret = 0; + unsigned int p0[] = {163,7,6,3,0}; + unsigned int p1[] = {193,15,0}; + + a=BN_new(); + b[0]=BN_new(); + b[1]=BN_new(); + c=BN_new(); + d=BN_new(); + e=BN_new(); + + BN_GF2m_arr2poly(p0, b[0]); + BN_GF2m_arr2poly(p1, b[1]); + + for (i=0; i<num0; i++) + { + BN_bntest_rand(a, 1024, 0, 0); + for (j=0; j < 2; j++) + { + BN_GF2m_mod(c, a, b[j]); +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ + if (bp != NULL) + { + if (!results) + { + BN_print(bp,a); + BIO_puts(bp," % "); + BN_print(bp,b[j]); + BIO_puts(bp," - "); + BN_print(bp,c); + BIO_puts(bp,"\n"); + } + } +#endif + BN_GF2m_add(d, a, c); + BN_GF2m_mod(e, d, b[j]); + /* Test that a + (a mod p) mod p == 0. */ + if(!BN_is_zero(e)) + { + fprintf(stderr,"GF(2^m) modulo test failed!\n"); + goto err; + } + } + } + ret = 1; + err: + BN_free(a); + BN_free(b[0]); + BN_free(b[1]); + BN_free(c); + BN_free(d); + BN_free(e); + return ret; + } + +int test_gf2m_mod_mul(BIO *bp,BN_CTX *ctx) + { + BIGNUM *a,*b[2],*c,*d,*e,*f,*g,*h; + int i, j, ret = 0; + unsigned int p0[] = {163,7,6,3,0}; + unsigned int p1[] = {193,15,0}; + + a=BN_new(); + b[0]=BN_new(); + b[1]=BN_new(); + c=BN_new(); + d=BN_new(); + e=BN_new(); + f=BN_new(); + g=BN_new(); + h=BN_new(); + + BN_GF2m_arr2poly(p0, b[0]); + BN_GF2m_arr2poly(p1, b[1]); + + for (i=0; i<num0; i++) + { + BN_bntest_rand(a, 1024, 0, 0); + BN_bntest_rand(c, 1024, 0, 0); + BN_bntest_rand(d, 1024, 0, 0); + for (j=0; j < 2; j++) + { + BN_GF2m_mod_mul(e, a, c, b[j], ctx); +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ + if (bp != NULL) + { + if (!results) + { + BN_print(bp,a); + BIO_puts(bp," * "); + BN_print(bp,c); + BIO_puts(bp," % "); + BN_print(bp,b[j]); + BIO_puts(bp," - "); + BN_print(bp,e); + BIO_puts(bp,"\n"); + } + } +#endif + BN_GF2m_add(f, a, d); + BN_GF2m_mod_mul(g, f, c, b[j], ctx); + BN_GF2m_mod_mul(h, d, c, b[j], ctx); + BN_GF2m_add(f, e, g); + BN_GF2m_add(f, f, h); + /* Test that (a+d)*c = a*c + d*c. */ + if(!BN_is_zero(f)) + { + fprintf(stderr,"GF(2^m) modular multiplication test failed!\n"); + goto err; + } + } + } + ret = 1; + err: + BN_free(a); + BN_free(b[0]); + BN_free(b[1]); + BN_free(c); + BN_free(d); + BN_free(e); + BN_free(f); + BN_free(g); + BN_free(h); + return ret; + } + +int test_gf2m_mod_sqr(BIO *bp,BN_CTX *ctx) + { + BIGNUM *a,*b[2],*c,*d; + int i, j, ret = 0; + unsigned int p0[] = {163,7,6,3,0}; + unsigned int p1[] = {193,15,0}; + + a=BN_new(); + b[0]=BN_new(); + b[1]=BN_new(); + c=BN_new(); + d=BN_new(); + + BN_GF2m_arr2poly(p0, b[0]); + BN_GF2m_arr2poly(p1, b[1]); + + for (i=0; i<num0; i++) + { + BN_bntest_rand(a, 1024, 0, 0); + for (j=0; j < 2; j++) + { + BN_GF2m_mod_sqr(c, a, b[j], ctx); + BN_copy(d, a); + BN_GF2m_mod_mul(d, a, d, b[j], ctx); +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ + if (bp != NULL) + { + if (!results) + { + BN_print(bp,a); + BIO_puts(bp," ^ 2 % "); + BN_print(bp,b[j]); + BIO_puts(bp, " = "); + BN_print(bp,c); + BIO_puts(bp,"; a * a = "); + BN_print(bp,d); + BIO_puts(bp,"\n"); + } + } +#endif + BN_GF2m_add(d, c, d); + /* Test that a*a = a^2. */ + if(!BN_is_zero(d)) + { + fprintf(stderr,"GF(2^m) modular squaring test failed!\n"); + goto err; + } + } + } + ret = 1; + err: + BN_free(a); + BN_free(b[0]); + BN_free(b[1]); + BN_free(c); + BN_free(d); + return ret; + } + +int test_gf2m_mod_inv(BIO *bp,BN_CTX *ctx) + { + BIGNUM *a,*b[2],*c,*d; + int i, j, ret = 0; + unsigned int p0[] = {163,7,6,3,0}; + unsigned int p1[] = {193,15,0}; + + a=BN_new(); + b[0]=BN_new(); + b[1]=BN_new(); + c=BN_new(); + d=BN_new(); + + BN_GF2m_arr2poly(p0, b[0]); + BN_GF2m_arr2poly(p1, b[1]); + + for (i=0; i<num0; i++) + { + BN_bntest_rand(a, 512, 0, 0); + for (j=0; j < 2; j++) + { + BN_GF2m_mod_inv(c, a, b[j], ctx); + BN_GF2m_mod_mul(d, a, c, b[j], ctx); +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ + if (bp != NULL) + { + if (!results) + { + BN_print(bp,a); + BIO_puts(bp, " * "); + BN_print(bp,c); + BIO_puts(bp," - 1 % "); + BN_print(bp,b[j]); + BIO_puts(bp,"\n"); + } + } +#endif + /* Test that ((1/a)*a) = 1. */ + if(!BN_is_one(d)) + { + fprintf(stderr,"GF(2^m) modular inversion test failed!\n"); + goto err; + } + } + } + ret = 1; + err: + BN_free(a); + BN_free(b[0]); + BN_free(b[1]); + BN_free(c); + BN_free(d); + return ret; + } + +int test_gf2m_mod_div(BIO *bp,BN_CTX *ctx) + { + BIGNUM *a,*b[2],*c,*d,*e,*f; + int i, j, ret = 0; + unsigned int p0[] = {163,7,6,3,0}; + unsigned int p1[] = {193,15,0}; + + a=BN_new(); + b[0]=BN_new(); + b[1]=BN_new(); + c=BN_new(); + d=BN_new(); + e=BN_new(); + f=BN_new(); + + BN_GF2m_arr2poly(p0, b[0]); + BN_GF2m_arr2poly(p1, b[1]); + + for (i=0; i<num0; i++) + { + BN_bntest_rand(a, 512, 0, 0); + BN_bntest_rand(c, 512, 0, 0); + for (j=0; j < 2; j++) + { + BN_GF2m_mod_div(d, a, c, b[j], ctx); + BN_GF2m_mod_mul(e, d, c, b[j], ctx); + BN_GF2m_mod_div(f, a, e, b[j], ctx); +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ + if (bp != NULL) + { + if (!results) + { + BN_print(bp,a); + BIO_puts(bp, " = "); + BN_print(bp,c); + BIO_puts(bp," * "); + BN_print(bp,d); + BIO_puts(bp, " % "); + BN_print(bp,b[j]); + BIO_puts(bp,"\n"); + } + } +#endif + /* Test that ((a/c)*c)/a = 1. */ + if(!BN_is_one(f)) + { + fprintf(stderr,"GF(2^m) modular division test failed!\n"); + goto err; + } + } + } + ret = 1; + err: + BN_free(a); + BN_free(b[0]); + BN_free(b[1]); + BN_free(c); + BN_free(d); + BN_free(e); + BN_free(f); + return ret; + } + +int test_gf2m_mod_exp(BIO *bp,BN_CTX *ctx) + { + BIGNUM *a,*b[2],*c,*d,*e,*f; + int i, j, ret = 0; + unsigned int p0[] = {163,7,6,3,0}; + unsigned int p1[] = {193,15,0}; + + a=BN_new(); + b[0]=BN_new(); + b[1]=BN_new(); + c=BN_new(); + d=BN_new(); + e=BN_new(); + f=BN_new(); + + BN_GF2m_arr2poly(p0, b[0]); + BN_GF2m_arr2poly(p1, b[1]); + + for (i=0; i<num0; i++) + { + BN_bntest_rand(a, 512, 0, 0); + BN_bntest_rand(c, 512, 0, 0); + BN_bntest_rand(d, 512, 0, 0); + for (j=0; j < 2; j++) + { + BN_GF2m_mod_exp(e, a, c, b[j], ctx); + BN_GF2m_mod_exp(f, a, d, b[j], ctx); + BN_GF2m_mod_mul(e, e, f, b[j], ctx); + BN_add(f, c, d); + BN_GF2m_mod_exp(f, a, f, b[j], ctx); +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ + if (bp != NULL) + { + if (!results) + { + BN_print(bp,a); + BIO_puts(bp, " ^ ("); + BN_print(bp,c); + BIO_puts(bp," + "); + BN_print(bp,d); + BIO_puts(bp, ") = "); + BN_print(bp,e); + BIO_puts(bp, "; - "); + BN_print(bp,f); + BIO_puts(bp, " % "); + BN_print(bp,b[j]); + BIO_puts(bp,"\n"); + } + } +#endif + BN_GF2m_add(f, e, f); + /* Test that a^(c+d)=a^c*a^d. */ + if(!BN_is_zero(f)) + { + fprintf(stderr,"GF(2^m) modular exponentiation test failed!\n"); + goto err; + } + } + } + ret = 1; + err: + BN_free(a); + BN_free(b[0]); + BN_free(b[1]); + BN_free(c); + BN_free(d); + BN_free(e); + BN_free(f); + return ret; + } + +int test_gf2m_mod_sqrt(BIO *bp,BN_CTX *ctx) + { + BIGNUM *a,*b[2],*c,*d,*e,*f; + int i, j, ret = 0; + unsigned int p0[] = {163,7,6,3,0}; + unsigned int p1[] = {193,15,0}; + + a=BN_new(); + b[0]=BN_new(); + b[1]=BN_new(); + c=BN_new(); + d=BN_new(); + e=BN_new(); + f=BN_new(); + + BN_GF2m_arr2poly(p0, b[0]); + BN_GF2m_arr2poly(p1, b[1]); + + for (i=0; i<num0; i++) + { + BN_bntest_rand(a, 512, 0, 0); + for (j=0; j < 2; j++) + { + BN_GF2m_mod(c, a, b[j]); + BN_GF2m_mod_sqrt(d, a, b[j], ctx); + BN_GF2m_mod_sqr(e, d, b[j], ctx); +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ + if (bp != NULL) + { + if (!results) + { + BN_print(bp,d); + BIO_puts(bp, " ^ 2 - "); + BN_print(bp,a); + BIO_puts(bp,"\n"); + } + } +#endif + BN_GF2m_add(f, c, e); + /* Test that d^2 = a, where d = sqrt(a). */ + if(!BN_is_zero(f)) + { + fprintf(stderr,"GF(2^m) modular square root test failed!\n"); + goto err; + } + } + } + ret = 1; + err: + BN_free(a); + BN_free(b[0]); + BN_free(b[1]); + BN_free(c); + BN_free(d); + BN_free(e); + BN_free(f); + return ret; + } + +int test_gf2m_mod_solve_quad(BIO *bp,BN_CTX *ctx) + { + BIGNUM *a,*b[2],*c,*d,*e; + int i, j, s = 0, t, ret = 0; + unsigned int p0[] = {163,7,6,3,0}; + unsigned int p1[] = {193,15,0}; + + a=BN_new(); + b[0]=BN_new(); + b[1]=BN_new(); + c=BN_new(); + d=BN_new(); + e=BN_new(); + + BN_GF2m_arr2poly(p0, b[0]); + BN_GF2m_arr2poly(p1, b[1]); + + for (i=0; i<num0; i++) + { + BN_bntest_rand(a, 512, 0, 0); + for (j=0; j < 2; j++) + { + t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx); + if (t) + { + s++; + BN_GF2m_mod_sqr(d, c, b[j], ctx); + BN_GF2m_add(d, c, d); + BN_GF2m_mod(e, a, b[j]); +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ + if (bp != NULL) + { + if (!results) + { + BN_print(bp,c); + BIO_puts(bp, " is root of z^2 + z = "); + BN_print(bp,a); + BIO_puts(bp, " % "); + BN_print(bp,b[j]); + BIO_puts(bp, "\n"); + } + } +#endif + BN_GF2m_add(e, e, d); + /* Test that solution of quadratic c satisfies c^2 + c = a. */ + if(!BN_is_zero(e)) + { + fprintf(stderr,"GF(2^m) modular solve quadratic test failed!\n"); + goto err; + } + + } + else + { +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */ + if (bp != NULL) + { + if (!results) + { + BIO_puts(bp, "There are no roots of z^2 + z = "); + BN_print(bp,a); + BIO_puts(bp, " % "); + BN_print(bp,b[j]); + BIO_puts(bp, "\n"); + } + } +#endif + } + } + } + if (s == 0) + { + fprintf(stderr,"All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n", num0); + fprintf(stderr,"this is very unlikely and probably indicates an error.\n"); + goto err; + } + ret = 1; + err: + BN_free(a); + BN_free(b[0]); + BN_free(b[1]); + BN_free(c); + BN_free(d); + BN_free(e); + return ret; + } + static void genprime_cb(int p, int n, void *arg) { char c='*';