+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 int genprime_cb(int p, int n, BN_GENCB *arg)