Symaptic: os/ossrv/ssl/libcrypto/src/crypto/bn/bntest.c@260cb5ec6c19 (annotated)

sl@0	1	/* crypto/bn/bntest.c */
sl@0	2	/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
sl@0	3	* All rights reserved.
sl@0	4	*
sl@0	5	* This package is an SSL implementation written
sl@0	6	* by Eric Young (eay@cryptsoft.com).
sl@0	7	* The implementation was written so as to conform with Netscapes SSL.
sl@0	8	*
sl@0	9	* This library is free for commercial and non-commercial use as long as
sl@0	10	* the following conditions are aheared to. The following conditions
sl@0	11	* apply to all code found in this distribution, be it the RC4, RSA,
sl@0	12	* lhash, DES, etc., code; not just the SSL code. The SSL documentation
sl@0	13	* included with this distribution is covered by the same copyright terms
sl@0	14	* except that the holder is Tim Hudson (tjh@cryptsoft.com).
sl@0	15	*
sl@0	16	* Copyright remains Eric Young's, and as such any Copyright notices in
sl@0	17	* the code are not to be removed.
sl@0	18	* If this package is used in a product, Eric Young should be given attribution
sl@0	19	* as the author of the parts of the library used.
sl@0	20	* This can be in the form of a textual message at program startup or
sl@0	21	* in documentation (online or textual) provided with the package.
sl@0	22	*
sl@0	23	* Redistribution and use in source and binary forms, with or without
sl@0	24	* modification, are permitted provided that the following conditions
sl@0	25	* are met:
sl@0	26	* 1. Redistributions of source code must retain the copyright
sl@0	27	* notice, this list of conditions and the following disclaimer.
sl@0	28	* 2. Redistributions in binary form must reproduce the above copyright
sl@0	29	* notice, this list of conditions and the following disclaimer in the
sl@0	30	* documentation and/or other materials provided with the distribution.
sl@0	31	* 3. All advertising materials mentioning features or use of this software
sl@0	32	* must display the following acknowledgement:
sl@0	33	* "This product includes cryptographic software written by
sl@0	34	* Eric Young (eay@cryptsoft.com)"
sl@0	35	* The word 'cryptographic' can be left out if the rouines from the library
sl@0	36	* being used are not cryptographic related :-).
sl@0	37	* 4. If you include any Windows specific code (or a derivative thereof) from
sl@0	38	* the apps directory (application code) you must include an acknowledgement:
sl@0	39	* "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
sl@0	40	*
sl@0	41	* THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
sl@0	42	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
sl@0	43	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
sl@0	44	* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
sl@0	45	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
sl@0	46	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
sl@0	47	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
sl@0	48	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
sl@0	49	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
sl@0	50	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
sl@0	51	* SUCH DAMAGE.
sl@0	52	*
sl@0	53	* The licence and distribution terms for any publically available version or
sl@0	54	* derivative of this code cannot be changed. i.e. this code cannot simply be
sl@0	55	* copied and put under another distribution licence
sl@0	56	* [including the GNU Public Licence.]
sl@0	57	*/
sl@0	58	/* ====================================================================
sl@0	59	* Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
sl@0	60	*
sl@0	61	* Portions of the attached software ("Contribution") are developed by
sl@0	62	* SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
sl@0	63	*
sl@0	64	* The Contribution is licensed pursuant to the Eric Young open source
sl@0	65	* license provided above.
sl@0	66	*
sl@0	67	* The binary polynomial arithmetic software is originally written by
sl@0	68	* Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems Laboratories.
sl@0	69	*
sl@0	70	*/
sl@0	71
sl@0	72	/* Until the key-gen callbacks are modified to use newer prototypes, we allow
sl@0	73	* deprecated functions for openssl-internal code */
sl@0	74	#ifdef OPENSSL_NO_DEPRECATED
sl@0	75	#undef OPENSSL_NO_DEPRECATED
sl@0	76	#endif
sl@0	77
sl@0	78	#include <stdio.h>
sl@0	79	#include <stdlib.h>
sl@0	80	#include <string.h>
sl@0	81
sl@0	82	#include "e_os.h"
sl@0	83
sl@0	84	#include <openssl/bio.h>
sl@0	85	#include <openssl/bn.h>
sl@0	86	#include <openssl/rand.h>
sl@0	87	#include <openssl/x509.h>
sl@0	88	#include <openssl/err.h>
sl@0	89
sl@0	90	const int num0 = 100; /* number of tests */
sl@0	91	const int num1 = 50; /* additional tests for some functions */
sl@0	92	const int num2 = 5; /* number of tests for slow functions */
sl@0	93
sl@0	94	int test_add(BIO *bp);
sl@0	95	int test_sub(BIO *bp);
sl@0	96	int test_lshift1(BIO *bp);
sl@0	97	int test_lshift(BIO bp,BN_CTX ctx,BIGNUM *a_);
sl@0	98	int test_rshift1(BIO *bp);
sl@0	99	int test_rshift(BIO bp,BN_CTX ctx);
sl@0	100	int test_div(BIO bp,BN_CTX ctx);
sl@0	101	int test_div_word(BIO *bp);
sl@0	102	int test_div_recp(BIO bp,BN_CTX ctx);
sl@0	103	int test_mul(BIO *bp);
sl@0	104	int test_sqr(BIO bp,BN_CTX ctx);
sl@0	105	int test_mont(BIO bp,BN_CTX ctx);
sl@0	106	int test_mod(BIO bp,BN_CTX ctx);
sl@0	107	int test_mod_mul(BIO bp,BN_CTX ctx);
sl@0	108	int test_mod_exp(BIO bp,BN_CTX ctx);
sl@0	109	int test_mod_exp_mont_consttime(BIO bp,BN_CTX ctx);
sl@0	110	int test_exp(BIO bp,BN_CTX ctx);
sl@0	111	int test_gf2m_add(BIO *bp);
sl@0	112	int test_gf2m_mod(BIO *bp);
sl@0	113	int test_gf2m_mod_mul(BIO bp,BN_CTX ctx);
sl@0	114	int test_gf2m_mod_sqr(BIO bp,BN_CTX ctx);
sl@0	115	int test_gf2m_mod_inv(BIO bp,BN_CTX ctx);
sl@0	116	int test_gf2m_mod_div(BIO bp,BN_CTX ctx);
sl@0	117	int test_gf2m_mod_exp(BIO bp,BN_CTX ctx);
sl@0	118	int test_gf2m_mod_sqrt(BIO bp,BN_CTX ctx);
sl@0	119	int test_gf2m_mod_solve_quad(BIO bp,BN_CTX ctx);
sl@0	120	int test_kron(BIO bp,BN_CTX ctx);
sl@0	121	int test_sqrt(BIO bp,BN_CTX ctx);
sl@0	122	int rand_neg(void);
sl@0	123	static int results=0;
sl@0	124
sl@0	125	static unsigned char lst[]="\xC6\x4F\x43\x04\x2A\xEA\xCA\x6E\x58\x36\x80\x5B\xE8\xC9"
sl@0	126	"\x9B\x04\x5D\x48\x36\xC2\xFD\x16\xC9\x64\xF0";
sl@0	127
sl@0	128	static const char rnd_seed[] = "string to make the random number generator think it has entropy";
sl@0	129
sl@0	130	static void message(BIO out, char m)
sl@0	131	{
sl@0	132	fprintf(stderr, "test %s\n", m);
sl@0	133	BIO_puts(out, "print \"test ");
sl@0	134	BIO_puts(out, m);
sl@0	135	BIO_puts(out, "\\n\"\n");
sl@0	136	}
sl@0	137
sl@0	138	int main(int argc, char *argv[])
sl@0	139	{
sl@0	140	BN_CTX *ctx;
sl@0	141	BIO *out;
sl@0	142	char *outfile=NULL;
sl@0	143
sl@0	144	results = 0;
sl@0	145
sl@0	146	RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_generate_prime may fail */
sl@0	147
sl@0	148	argc--;
sl@0	149	argv++;
sl@0	150	while (argc >= 1)
sl@0	151	{
sl@0	152	if (strcmp(*argv,"-results") == 0)
sl@0	153	results=1;
sl@0	154	else if (strcmp(*argv,"-out") == 0)
sl@0	155	{
sl@0	156	if (--argc < 1) break;
sl@0	157	outfile= *(++argv);
sl@0	158	}
sl@0	159	argc--;
sl@0	160	argv++;
sl@0	161	}
sl@0	162
sl@0	163
sl@0	164	ctx=BN_CTX_new();
sl@0	165	if (ctx == NULL) EXIT(1);
sl@0	166
sl@0	167	out=BIO_new(BIO_s_file());
sl@0	168	if (out == NULL) EXIT(1);
sl@0	169	if (outfile == NULL)
sl@0	170	{
sl@0	171	BIO_set_fp(out,stdout,BIO_NOCLOSE);
sl@0	172	}
sl@0	173	else
sl@0	174	{
sl@0	175	if (!BIO_write_filename(out,outfile))
sl@0	176	{
sl@0	177	perror(outfile);
sl@0	178	EXIT(1);
sl@0	179	}
sl@0	180	}
sl@0	181
sl@0	182	if (!results)
sl@0	183	BIO_puts(out,"obase=16\nibase=16\n");
sl@0	184
sl@0	185	message(out,"BN_add");
sl@0	186	if (!test_add(out)) goto err;
sl@0	187	(void)BIO_flush(out);
sl@0	188
sl@0	189	message(out,"BN_sub");
sl@0	190	if (!test_sub(out)) goto err;
sl@0	191	(void)BIO_flush(out);
sl@0	192
sl@0	193	message(out,"BN_lshift1");
sl@0	194	if (!test_lshift1(out)) goto err;
sl@0	195	(void)BIO_flush(out);
sl@0	196
sl@0	197	message(out,"BN_lshift (fixed)");
sl@0	198	if (!test_lshift(out,ctx,BN_bin2bn(lst,sizeof(lst)-1,NULL)))
sl@0	199	goto err;
sl@0	200	(void)BIO_flush(out);
sl@0	201
sl@0	202	message(out,"BN_lshift");
sl@0	203	if (!test_lshift(out,ctx,NULL)) goto err;
sl@0	204	(void)BIO_flush(out);
sl@0	205
sl@0	206	message(out,"BN_rshift1");
sl@0	207	if (!test_rshift1(out)) goto err;
sl@0	208	(void)BIO_flush(out);
sl@0	209
sl@0	210	message(out,"BN_rshift");
sl@0	211	if (!test_rshift(out,ctx)) goto err;
sl@0	212	(void)BIO_flush(out);
sl@0	213
sl@0	214	message(out,"BN_sqr");
sl@0	215	if (!test_sqr(out,ctx)) goto err;
sl@0	216	(void)BIO_flush(out);
sl@0	217
sl@0	218	message(out,"BN_mul");
sl@0	219	if (!test_mul(out)) goto err;
sl@0	220	(void)BIO_flush(out);
sl@0	221
sl@0	222	message(out,"BN_div");
sl@0	223	if (!test_div(out,ctx)) goto err;
sl@0	224	(void)BIO_flush(out);
sl@0	225
sl@0	226	message(out,"BN_div_word");
sl@0	227	if (!test_div_word(out)) goto err;
sl@0	228	(void)BIO_flush(out);
sl@0	229
sl@0	230	message(out,"BN_div_recp");
sl@0	231	if (!test_div_recp(out,ctx)) goto err;
sl@0	232	(void)BIO_flush(out);
sl@0	233
sl@0	234	message(out,"BN_mod");
sl@0	235	if (!test_mod(out,ctx)) goto err;
sl@0	236	(void)BIO_flush(out);
sl@0	237
sl@0	238	message(out,"BN_mod_mul");
sl@0	239	if (!test_mod_mul(out,ctx)) goto err;
sl@0	240	(void)BIO_flush(out);
sl@0	241
sl@0	242	message(out,"BN_mont");
sl@0	243	if (!test_mont(out,ctx)) goto err;
sl@0	244	(void)BIO_flush(out);
sl@0	245
sl@0	246	message(out,"BN_mod_exp");
sl@0	247	if (!test_mod_exp(out,ctx)) goto err;
sl@0	248	(void)BIO_flush(out);
sl@0	249
sl@0	250	message(out,"BN_mod_exp_mont_consttime");
sl@0	251	if (!test_mod_exp_mont_consttime(out,ctx)) goto err;
sl@0	252	(void)BIO_flush(out);
sl@0	253
sl@0	254	message(out,"BN_exp");
sl@0	255	if (!test_exp(out,ctx)) goto err;
sl@0	256	(void)BIO_flush(out);
sl@0	257
sl@0	258	message(out,"BN_kronecker");
sl@0	259	if (!test_kron(out,ctx)) goto err;
sl@0	260	(void)BIO_flush(out);
sl@0	261
sl@0	262	message(out,"BN_mod_sqrt");
sl@0	263	if (!test_sqrt(out,ctx)) goto err;
sl@0	264	(void)BIO_flush(out);
sl@0	265
sl@0	266	message(out,"BN_GF2m_add");
sl@0	267	if (!test_gf2m_add(out)) goto err;
sl@0	268	(void)BIO_flush(out);
sl@0	269
sl@0	270	message(out,"BN_GF2m_mod");
sl@0	271	if (!test_gf2m_mod(out)) goto err;
sl@0	272	(void)BIO_flush(out);
sl@0	273
sl@0	274	message(out,"BN_GF2m_mod_mul");
sl@0	275	if (!test_gf2m_mod_mul(out,ctx)) goto err;
sl@0	276	(void)BIO_flush(out);
sl@0	277
sl@0	278	message(out,"BN_GF2m_mod_sqr");
sl@0	279	if (!test_gf2m_mod_sqr(out,ctx)) goto err;
sl@0	280	(void)BIO_flush(out);
sl@0	281
sl@0	282	message(out,"BN_GF2m_mod_inv");
sl@0	283	if (!test_gf2m_mod_inv(out,ctx)) goto err;
sl@0	284	(void)BIO_flush(out);
sl@0	285
sl@0	286	message(out,"BN_GF2m_mod_div");
sl@0	287	if (!test_gf2m_mod_div(out,ctx)) goto err;
sl@0	288	(void)BIO_flush(out);
sl@0	289
sl@0	290	message(out,"BN_GF2m_mod_exp");
sl@0	291	if (!test_gf2m_mod_exp(out,ctx)) goto err;
sl@0	292	(void)BIO_flush(out);
sl@0	293
sl@0	294	message(out,"BN_GF2m_mod_sqrt");
sl@0	295	if (!test_gf2m_mod_sqrt(out,ctx)) goto err;
sl@0	296	(void)BIO_flush(out);
sl@0	297
sl@0	298	message(out,"BN_GF2m_mod_solve_quad");
sl@0	299	if (!test_gf2m_mod_solve_quad(out,ctx)) goto err;
sl@0	300	(void)BIO_flush(out);
sl@0	301
sl@0	302	BN_CTX_free(ctx);
sl@0	303	BIO_free(out);
sl@0	304
sl@0	305	/**/
sl@0	306	EXIT(0);
sl@0	307	err:
sl@0	308	BIO_puts(out,"1\n"); /* make sure the Perl script fed by bc notices
sl@0	309	* the failure, see test_bn in test/Makefile.ssl*/
sl@0	310	(void)BIO_flush(out);
sl@0	311	ERR_load_crypto_strings();
sl@0	312	ERR_print_errors_fp(stderr);
sl@0	313	EXIT(1);
sl@0	314	return(1);
sl@0	315	}
sl@0	316
sl@0	317	int test_add(BIO *bp)
sl@0	318	{
sl@0	319	BIGNUM a,b,c;
sl@0	320	int i;
sl@0	321
sl@0	322	BN_init(&a);
sl@0	323	BN_init(&b);
sl@0	324	BN_init(&c);
sl@0	325
sl@0	326	BN_bntest_rand(&a,512,0,0);
sl@0	327	for (i=0; i<num0; i++)
sl@0	328	{
sl@0	329	BN_bntest_rand(&b,450+i,0,0);
sl@0	330	a.neg=rand_neg();
sl@0	331	b.neg=rand_neg();
sl@0	332	BN_add(&c,&a,&b);
sl@0	333	if (bp != NULL)
sl@0	334	{
sl@0	335	if (!results)
sl@0	336	{
sl@0	337	BN_print(bp,&a);
sl@0	338	BIO_puts(bp," + ");
sl@0	339	BN_print(bp,&b);
sl@0	340	BIO_puts(bp," - ");
sl@0	341	}
sl@0	342	BN_print(bp,&c);
sl@0	343	BIO_puts(bp,"\n");
sl@0	344	}
sl@0	345	a.neg=!a.neg;
sl@0	346	b.neg=!b.neg;
sl@0	347	BN_add(&c,&c,&b);
sl@0	348	BN_add(&c,&c,&a);
sl@0	349	if(!BN_is_zero(&c))
sl@0	350	{
sl@0	351	fprintf(stderr,"Add test failed!\n");
sl@0	352	return 0;
sl@0	353	}
sl@0	354	}
sl@0	355	BN_free(&a);
sl@0	356	BN_free(&b);
sl@0	357	BN_free(&c);
sl@0	358	return(1);
sl@0	359	}
sl@0	360
sl@0	361	int test_sub(BIO *bp)
sl@0	362	{
sl@0	363	BIGNUM a,b,c;
sl@0	364	int i;
sl@0	365
sl@0	366	BN_init(&a);
sl@0	367	BN_init(&b);
sl@0	368	BN_init(&c);
sl@0	369
sl@0	370	for (i=0; i<num0+num1; i++)
sl@0	371	{
sl@0	372	if (i < num1)
sl@0	373	{
sl@0	374	BN_bntest_rand(&a,512,0,0);
sl@0	375	BN_copy(&b,&a);
sl@0	376	if (BN_set_bit(&a,i)==0) return(0);
sl@0	377	BN_add_word(&b,i);
sl@0	378	}
sl@0	379	else
sl@0	380	{
sl@0	381	BN_bntest_rand(&b,400+i-num1,0,0);
sl@0	382	a.neg=rand_neg();
sl@0	383	b.neg=rand_neg();
sl@0	384	}
sl@0	385	BN_sub(&c,&a,&b);
sl@0	386	if (bp != NULL)
sl@0	387	{
sl@0	388	if (!results)
sl@0	389	{
sl@0	390	BN_print(bp,&a);
sl@0	391	BIO_puts(bp," - ");
sl@0	392	BN_print(bp,&b);
sl@0	393	BIO_puts(bp," - ");
sl@0	394	}
sl@0	395	BN_print(bp,&c);
sl@0	396	BIO_puts(bp,"\n");
sl@0	397	}
sl@0	398	BN_add(&c,&c,&b);
sl@0	399	BN_sub(&c,&c,&a);
sl@0	400	if(!BN_is_zero(&c))
sl@0	401	{
sl@0	402	fprintf(stderr,"Subtract test failed!\n");
sl@0	403	return 0;
sl@0	404	}
sl@0	405	}
sl@0	406	BN_free(&a);
sl@0	407	BN_free(&b);
sl@0	408	BN_free(&c);
sl@0	409	return(1);
sl@0	410	}
sl@0	411
sl@0	412	int test_div(BIO bp, BN_CTX ctx)
sl@0	413	{
sl@0	414	BIGNUM a,b,c,d,e;
sl@0	415	int i;
sl@0	416
sl@0	417	BN_init(&a);
sl@0	418	BN_init(&b);
sl@0	419	BN_init(&c);
sl@0	420	BN_init(&d);
sl@0	421	BN_init(&e);
sl@0	422
sl@0	423	for (i=0; i<num0+num1; i++)
sl@0	424	{
sl@0	425	if (i < num1)
sl@0	426	{
sl@0	427	BN_bntest_rand(&a,400,0,0);
sl@0	428	BN_copy(&b,&a);
sl@0	429	BN_lshift(&a,&a,i);
sl@0	430	BN_add_word(&a,i);
sl@0	431	}
sl@0	432	else
sl@0	433	BN_bntest_rand(&b,50+3*(i-num1),0,0);
sl@0	434	a.neg=rand_neg();
sl@0	435	b.neg=rand_neg();
sl@0	436	BN_div(&d,&c,&a,&b,ctx);
sl@0	437	if (bp != NULL)
sl@0	438	{
sl@0	439	if (!results)
sl@0	440	{
sl@0	441	BN_print(bp,&a);
sl@0	442	BIO_puts(bp," / ");
sl@0	443	BN_print(bp,&b);
sl@0	444	BIO_puts(bp," - ");
sl@0	445	}
sl@0	446	BN_print(bp,&d);
sl@0	447	BIO_puts(bp,"\n");
sl@0	448
sl@0	449	if (!results)
sl@0	450	{
sl@0	451	BN_print(bp,&a);
sl@0	452	BIO_puts(bp," % ");
sl@0	453	BN_print(bp,&b);
sl@0	454	BIO_puts(bp," - ");
sl@0	455	}
sl@0	456	BN_print(bp,&c);
sl@0	457	BIO_puts(bp,"\n");
sl@0	458	}
sl@0	459	BN_mul(&e,&d,&b,ctx);
sl@0	460	BN_add(&d,&e,&c);
sl@0	461	BN_sub(&d,&d,&a);
sl@0	462	if(!BN_is_zero(&d))
sl@0	463	{
sl@0	464	fprintf(stderr,"Division test failed!\n");
sl@0	465	return 0;
sl@0	466	}
sl@0	467	}
sl@0	468	BN_free(&a);
sl@0	469	BN_free(&b);
sl@0	470	BN_free(&c);
sl@0	471	BN_free(&d);
sl@0	472	BN_free(&e);
sl@0	473	return(1);
sl@0	474	}
sl@0	475
sl@0	476	static void print_word(BIO *bp,BN_ULONG w)
sl@0	477	{
sl@0	478	#ifdef SIXTY_FOUR_BIT
sl@0	479	if (sizeof(w) > sizeof(unsigned long))
sl@0	480	{
sl@0	481	unsigned long h=(unsigned long)(w>>32),
sl@0	482	l=(unsigned long)(w);
sl@0	483
sl@0	484	if (h) BIO_printf(bp,"%lX%08lX",h,l);
sl@0	485	else BIO_printf(bp,"%lX",l);
sl@0	486	return;
sl@0	487	}
sl@0	488	#endif
sl@0	489	BIO_printf(bp,"%lX",w);
sl@0	490	}
sl@0	491
sl@0	492	int test_div_word(BIO *bp)
sl@0	493	{
sl@0	494	BIGNUM a,b;
sl@0	495	BN_ULONG r,s;
sl@0	496	int i;
sl@0	497
sl@0	498	BN_init(&a);
sl@0	499	BN_init(&b);
sl@0	500
sl@0	501	for (i=0; i<num0; i++)
sl@0	502	{
sl@0	503	do {
sl@0	504	BN_bntest_rand(&a,512,-1,0);
sl@0	505	BN_bntest_rand(&b,BN_BITS2,-1,0);
sl@0	506	s = b.d[0];
sl@0	507	} while (!s);
sl@0	508
sl@0	509	BN_copy(&b, &a);
sl@0	510	r = BN_div_word(&b, s);
sl@0	511
sl@0	512	if (bp != NULL)
sl@0	513	{
sl@0	514	if (!results)
sl@0	515	{
sl@0	516	BN_print(bp,&a);
sl@0	517	BIO_puts(bp," / ");
sl@0	518	print_word(bp,s);
sl@0	519	BIO_puts(bp," - ");
sl@0	520	}
sl@0	521	BN_print(bp,&b);
sl@0	522	BIO_puts(bp,"\n");
sl@0	523
sl@0	524	if (!results)
sl@0	525	{
sl@0	526	BN_print(bp,&a);
sl@0	527	BIO_puts(bp," % ");
sl@0	528	print_word(bp,s);
sl@0	529	BIO_puts(bp," - ");
sl@0	530	}
sl@0	531	print_word(bp,r);
sl@0	532	BIO_puts(bp,"\n");
sl@0	533	}
sl@0	534	BN_mul_word(&b,s);
sl@0	535	BN_add_word(&b,r);
sl@0	536	BN_sub(&b,&a,&b);
sl@0	537	if(!BN_is_zero(&b))
sl@0	538	{
sl@0	539	fprintf(stderr,"Division (word) test failed!\n");
sl@0	540	return 0;
sl@0	541	}
sl@0	542	}
sl@0	543	BN_free(&a);
sl@0	544	BN_free(&b);
sl@0	545	return(1);
sl@0	546	}
sl@0	547
sl@0	548	int test_div_recp(BIO bp, BN_CTX ctx)
sl@0	549	{
sl@0	550	BIGNUM a,b,c,d,e;
sl@0	551	BN_RECP_CTX recp;
sl@0	552	int i;
sl@0	553
sl@0	554	BN_RECP_CTX_init(&recp);
sl@0	555	BN_init(&a);
sl@0	556	BN_init(&b);
sl@0	557	BN_init(&c);
sl@0	558	BN_init(&d);
sl@0	559	BN_init(&e);
sl@0	560
sl@0	561	for (i=0; i<num0+num1; i++)
sl@0	562	{
sl@0	563	if (i < num1)
sl@0	564	{
sl@0	565	BN_bntest_rand(&a,400,0,0);
sl@0	566	BN_copy(&b,&a);
sl@0	567	BN_lshift(&a,&a,i);
sl@0	568	BN_add_word(&a,i);
sl@0	569	}
sl@0	570	else
sl@0	571	BN_bntest_rand(&b,50+3*(i-num1),0,0);
sl@0	572	a.neg=rand_neg();
sl@0	573	b.neg=rand_neg();
sl@0	574	BN_RECP_CTX_set(&recp,&b,ctx);
sl@0	575	BN_div_recp(&d,&c,&a,&recp,ctx);
sl@0	576	if (bp != NULL)
sl@0	577	{
sl@0	578	if (!results)
sl@0	579	{
sl@0	580	BN_print(bp,&a);
sl@0	581	BIO_puts(bp," / ");
sl@0	582	BN_print(bp,&b);
sl@0	583	BIO_puts(bp," - ");
sl@0	584	}
sl@0	585	BN_print(bp,&d);
sl@0	586	BIO_puts(bp,"\n");
sl@0	587
sl@0	588	if (!results)
sl@0	589	{
sl@0	590	BN_print(bp,&a);
sl@0	591	BIO_puts(bp," % ");
sl@0	592	BN_print(bp,&b);
sl@0	593	BIO_puts(bp," - ");
sl@0	594	}
sl@0	595	BN_print(bp,&c);
sl@0	596	BIO_puts(bp,"\n");
sl@0	597	}
sl@0	598	BN_mul(&e,&d,&b,ctx);
sl@0	599	BN_add(&d,&e,&c);
sl@0	600	BN_sub(&d,&d,&a);
sl@0	601	if(!BN_is_zero(&d))
sl@0	602	{
sl@0	603	fprintf(stderr,"Reciprocal division test failed!\n");
sl@0	604	fprintf(stderr,"a=");
sl@0	605	BN_print_fp(stderr,&a);
sl@0	606	fprintf(stderr,"\nb=");
sl@0	607	BN_print_fp(stderr,&b);
sl@0	608	fprintf(stderr,"\n");
sl@0	609	return 0;
sl@0	610	}
sl@0	611	}
sl@0	612	BN_free(&a);
sl@0	613	BN_free(&b);
sl@0	614	BN_free(&c);
sl@0	615	BN_free(&d);
sl@0	616	BN_free(&e);
sl@0	617	BN_RECP_CTX_free(&recp);
sl@0	618	return(1);
sl@0	619	}
sl@0	620
sl@0	621	int test_mul(BIO *bp)
sl@0	622	{
sl@0	623	BIGNUM a,b,c,d,e;
sl@0	624	int i;
sl@0	625	BN_CTX *ctx;
sl@0	626
sl@0	627	ctx = BN_CTX_new();
sl@0	628	if (ctx == NULL) EXIT(1);
sl@0	629
sl@0	630	BN_init(&a);
sl@0	631	BN_init(&b);
sl@0	632	BN_init(&c);
sl@0	633	BN_init(&d);
sl@0	634	BN_init(&e);
sl@0	635
sl@0	636	for (i=0; i<num0+num1; i++)
sl@0	637	{
sl@0	638	if (i <= num1)
sl@0	639	{
sl@0	640	BN_bntest_rand(&a,100,0,0);
sl@0	641	BN_bntest_rand(&b,100,0,0);
sl@0	642	}
sl@0	643	else
sl@0	644	BN_bntest_rand(&b,i-num1,0,0);
sl@0	645	a.neg=rand_neg();
sl@0	646	b.neg=rand_neg();
sl@0	647	BN_mul(&c,&a,&b,ctx);
sl@0	648	if (bp != NULL)
sl@0	649	{
sl@0	650	if (!results)
sl@0	651	{
sl@0	652	BN_print(bp,&a);
sl@0	653	BIO_puts(bp," * ");
sl@0	654	BN_print(bp,&b);
sl@0	655	BIO_puts(bp," - ");
sl@0	656	}
sl@0	657	BN_print(bp,&c);
sl@0	658	BIO_puts(bp,"\n");
sl@0	659	}
sl@0	660	BN_div(&d,&e,&c,&a,ctx);
sl@0	661	BN_sub(&d,&d,&b);
sl@0	662	if(!BN_is_zero(&d) \|\| !BN_is_zero(&e))
sl@0	663	{
sl@0	664	fprintf(stderr,"Multiplication test failed!\n");
sl@0	665	return 0;
sl@0	666	}
sl@0	667	}
sl@0	668	BN_free(&a);
sl@0	669	BN_free(&b);
sl@0	670	BN_free(&c);
sl@0	671	BN_free(&d);
sl@0	672	BN_free(&e);
sl@0	673	BN_CTX_free(ctx);
sl@0	674	return(1);
sl@0	675	}
sl@0	676
sl@0	677	int test_sqr(BIO bp, BN_CTX ctx)
sl@0	678	{
sl@0	679	BIGNUM a,c,d,e;
sl@0	680	int i;
sl@0	681
sl@0	682	BN_init(&a);
sl@0	683	BN_init(&c);
sl@0	684	BN_init(&d);
sl@0	685	BN_init(&e);
sl@0	686
sl@0	687	for (i=0; i<num0; i++)
sl@0	688	{
sl@0	689	BN_bntest_rand(&a,40+i*10,0,0);
sl@0	690	a.neg=rand_neg();
sl@0	691	BN_sqr(&c,&a,ctx);
sl@0	692	if (bp != NULL)
sl@0	693	{
sl@0	694	if (!results)
sl@0	695	{
sl@0	696	BN_print(bp,&a);
sl@0	697	BIO_puts(bp," * ");
sl@0	698	BN_print(bp,&a);
sl@0	699	BIO_puts(bp," - ");
sl@0	700	}
sl@0	701	BN_print(bp,&c);
sl@0	702	BIO_puts(bp,"\n");
sl@0	703	}
sl@0	704	BN_div(&d,&e,&c,&a,ctx);
sl@0	705	BN_sub(&d,&d,&a);
sl@0	706	if(!BN_is_zero(&d) \|\| !BN_is_zero(&e))
sl@0	707	{
sl@0	708	fprintf(stderr,"Square test failed!\n");
sl@0	709	return 0;
sl@0	710	}
sl@0	711	}
sl@0	712	BN_free(&a);
sl@0	713	BN_free(&c);
sl@0	714	BN_free(&d);
sl@0	715	BN_free(&e);
sl@0	716	return(1);
sl@0	717	}
sl@0	718
sl@0	719	int test_mont(BIO bp, BN_CTX ctx)
sl@0	720	{
sl@0	721	BIGNUM a,b,c,d,A,B;
sl@0	722	BIGNUM n;
sl@0	723	int i;
sl@0	724	BN_MONT_CTX *mont;
sl@0	725
sl@0	726	BN_init(&a);
sl@0	727	BN_init(&b);
sl@0	728	BN_init(&c);
sl@0	729	BN_init(&d);
sl@0	730	BN_init(&A);
sl@0	731	BN_init(&B);
sl@0	732	BN_init(&n);
sl@0	733
sl@0	734	mont=BN_MONT_CTX_new();
sl@0	735
sl@0	736	BN_bntest_rand(&a,100,0,0); /**/
sl@0	737	BN_bntest_rand(&b,100,0,0); /**/
sl@0	738	for (i=0; i<num2; i++)
sl@0	739	{
sl@0	740	int bits = (200*(i+1))/num2;
sl@0	741
sl@0	742	if (bits == 0)
sl@0	743	continue;
sl@0	744	BN_bntest_rand(&n,bits,0,1);
sl@0	745	BN_MONT_CTX_set(mont,&n,ctx);
sl@0	746
sl@0	747	BN_nnmod(&a,&a,&n,ctx);
sl@0	748	BN_nnmod(&b,&b,&n,ctx);
sl@0	749
sl@0	750	BN_to_montgomery(&A,&a,mont,ctx);
sl@0	751	BN_to_montgomery(&B,&b,mont,ctx);
sl@0	752
sl@0	753	BN_mod_mul_montgomery(&c,&A,&B,mont,ctx);/**/
sl@0	754	BN_from_montgomery(&A,&c,mont,ctx);/**/
sl@0	755	if (bp != NULL)
sl@0	756	{
sl@0	757	if (!results)
sl@0	758	{
sl@0	759	#ifdef undef
sl@0	760	fprintf(stderr,"%d * %d %% %d\n",
sl@0	761	BN_num_bits(&a),
sl@0	762	BN_num_bits(&b),
sl@0	763	BN_num_bits(mont->N));
sl@0	764	#endif
sl@0	765	BN_print(bp,&a);
sl@0	766	BIO_puts(bp," * ");
sl@0	767	BN_print(bp,&b);
sl@0	768	BIO_puts(bp," % ");
sl@0	769	BN_print(bp,&(mont->N));
sl@0	770	BIO_puts(bp," - ");
sl@0	771	}
sl@0	772	BN_print(bp,&A);
sl@0	773	BIO_puts(bp,"\n");
sl@0	774	}
sl@0	775	BN_mod_mul(&d,&a,&b,&n,ctx);
sl@0	776	BN_sub(&d,&d,&A);
sl@0	777	if(!BN_is_zero(&d))
sl@0	778	{
sl@0	779	fprintf(stderr,"Montgomery multiplication test failed!\n");
sl@0	780	return 0;
sl@0	781	}
sl@0	782	}
sl@0	783	BN_MONT_CTX_free(mont);
sl@0	784	BN_free(&a);
sl@0	785	BN_free(&b);
sl@0	786	BN_free(&c);
sl@0	787	BN_free(&d);
sl@0	788	BN_free(&A);
sl@0	789	BN_free(&B);
sl@0	790	BN_free(&n);
sl@0	791	return(1);
sl@0	792	}
sl@0	793
sl@0	794	int test_mod(BIO bp, BN_CTX ctx)
sl@0	795	{
sl@0	796	BIGNUM a,b,c,d,*e;
sl@0	797	int i;
sl@0	798
sl@0	799	a=BN_new();
sl@0	800	b=BN_new();
sl@0	801	c=BN_new();
sl@0	802	d=BN_new();
sl@0	803	e=BN_new();
sl@0	804
sl@0	805	BN_bntest_rand(a,1024,0,0); /**/
sl@0	806	for (i=0; i<num0; i++)
sl@0	807	{
sl@0	808	BN_bntest_rand(b,450+i10,0,0); /*/
sl@0	809	a->neg=rand_neg();
sl@0	810	b->neg=rand_neg();
sl@0	811	BN_mod(c,a,b,ctx);/**/
sl@0	812	if (bp != NULL)
sl@0	813	{
sl@0	814	if (!results)
sl@0	815	{
sl@0	816	BN_print(bp,a);
sl@0	817	BIO_puts(bp," % ");
sl@0	818	BN_print(bp,b);
sl@0	819	BIO_puts(bp," - ");
sl@0	820	}
sl@0	821	BN_print(bp,c);
sl@0	822	BIO_puts(bp,"\n");
sl@0	823	}
sl@0	824	BN_div(d,e,a,b,ctx);
sl@0	825	BN_sub(e,e,c);
sl@0	826	if(!BN_is_zero(e))
sl@0	827	{
sl@0	828	fprintf(stderr,"Modulo test failed!\n");
sl@0	829	return 0;
sl@0	830	}
sl@0	831	}
sl@0	832	BN_free(a);
sl@0	833	BN_free(b);
sl@0	834	BN_free(c);
sl@0	835	BN_free(d);
sl@0	836	BN_free(e);
sl@0	837	return(1);
sl@0	838	}
sl@0	839
sl@0	840	int test_mod_mul(BIO bp, BN_CTX ctx)
sl@0	841	{
sl@0	842	BIGNUM a,b,c,d,*e;
sl@0	843	int i,j;
sl@0	844
sl@0	845	a=BN_new();
sl@0	846	b=BN_new();
sl@0	847	c=BN_new();
sl@0	848	d=BN_new();
sl@0	849	e=BN_new();
sl@0	850
sl@0	851	for (j=0; j<3; j++) {
sl@0	852	BN_bntest_rand(c,1024,0,0); /**/
sl@0	853	for (i=0; i<num0; i++)
sl@0	854	{
sl@0	855	BN_bntest_rand(a,475+i10,0,0); /*/
sl@0	856	BN_bntest_rand(b,425+i11,0,0); /*/
sl@0	857	a->neg=rand_neg();
sl@0	858	b->neg=rand_neg();
sl@0	859	if (!BN_mod_mul(e,a,b,c,ctx))
sl@0	860	{
sl@0	861	unsigned long l;
sl@0	862
sl@0	863	while ((l=ERR_get_error()))
sl@0	864	fprintf(stderr,"ERROR:%s\n",
sl@0	865	ERR_error_string(l,NULL));
sl@0	866	EXIT(1);
sl@0	867	}
sl@0	868	if (bp != NULL)
sl@0	869	{
sl@0	870	if (!results)
sl@0	871	{
sl@0	872	BN_print(bp,a);
sl@0	873	BIO_puts(bp," * ");
sl@0	874	BN_print(bp,b);
sl@0	875	BIO_puts(bp," % ");
sl@0	876	BN_print(bp,c);
sl@0	877	if ((a->neg ^ b->neg) && !BN_is_zero(e))
sl@0	878	{
sl@0	879	/* If (a*b) % c is negative, c must be added
sl@0	880	* in order to obtain the normalized remainder
sl@0	881	* (new with OpenSSL 0.9.7, previous versions of
sl@0	882	* BN_mod_mul could generate negative results)
sl@0	883	*/
sl@0	884	BIO_puts(bp," + ");
sl@0	885	BN_print(bp,c);
sl@0	886	}
sl@0	887	BIO_puts(bp," - ");
sl@0	888	}
sl@0	889	BN_print(bp,e);
sl@0	890	BIO_puts(bp,"\n");
sl@0	891	}
sl@0	892	BN_mul(d,a,b,ctx);
sl@0	893	BN_sub(d,d,e);
sl@0	894	BN_div(a,b,d,c,ctx);
sl@0	895	if(!BN_is_zero(b))
sl@0	896	{
sl@0	897	fprintf(stderr,"Modulo multiply test failed!\n");
sl@0	898	ERR_print_errors_fp(stderr);
sl@0	899	return 0;
sl@0	900	}
sl@0	901	}
sl@0	902	}
sl@0	903	BN_free(a);
sl@0	904	BN_free(b);
sl@0	905	BN_free(c);
sl@0	906	BN_free(d);
sl@0	907	BN_free(e);
sl@0	908	return(1);
sl@0	909	}
sl@0	910
sl@0	911	int test_mod_exp(BIO bp, BN_CTX ctx)
sl@0	912	{
sl@0	913	BIGNUM a,b,c,d,*e;
sl@0	914	int i;
sl@0	915
sl@0	916	a=BN_new();
sl@0	917	b=BN_new();
sl@0	918	c=BN_new();
sl@0	919	d=BN_new();
sl@0	920	e=BN_new();
sl@0	921
sl@0	922	BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */
sl@0	923	for (i=0; i<num2; i++)
sl@0	924	{
sl@0	925	BN_bntest_rand(a,20+i5,0,0); /*/
sl@0	926	BN_bntest_rand(b,2+i,0,0); /**/
sl@0	927
sl@0	928	if (!BN_mod_exp(d,a,b,c,ctx))
sl@0	929	return(00);
sl@0	930
sl@0	931	if (bp != NULL)
sl@0	932	{
sl@0	933	if (!results)
sl@0	934	{
sl@0	935	BN_print(bp,a);
sl@0	936	BIO_puts(bp," ^ ");
sl@0	937	BN_print(bp,b);
sl@0	938	BIO_puts(bp," % ");
sl@0	939	BN_print(bp,c);
sl@0	940	BIO_puts(bp," - ");
sl@0	941	}
sl@0	942	BN_print(bp,d);
sl@0	943	BIO_puts(bp,"\n");
sl@0	944	}
sl@0	945	BN_exp(e,a,b,ctx);
sl@0	946	BN_sub(e,e,d);
sl@0	947	BN_div(a,b,e,c,ctx);
sl@0	948	if(!BN_is_zero(b))
sl@0	949	{
sl@0	950	fprintf(stderr,"Modulo exponentiation test failed!\n");
sl@0	951	return 0;
sl@0	952	}
sl@0	953	}
sl@0	954	BN_free(a);
sl@0	955	BN_free(b);
sl@0	956	BN_free(c);
sl@0	957	BN_free(d);
sl@0	958	BN_free(e);
sl@0	959	return(1);
sl@0	960	}
sl@0	961
sl@0	962	int test_mod_exp_mont_consttime(BIO bp, BN_CTX ctx)
sl@0	963	{
sl@0	964	BIGNUM a,b,c,d,*e;
sl@0	965	int i;
sl@0	966
sl@0	967	a=BN_new();
sl@0	968	b=BN_new();
sl@0	969	c=BN_new();
sl@0	970	d=BN_new();
sl@0	971	e=BN_new();
sl@0	972
sl@0	973	BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */
sl@0	974	for (i=0; i<num2; i++)
sl@0	975	{
sl@0	976	BN_bntest_rand(a,20+i5,0,0); /*/
sl@0	977	BN_bntest_rand(b,2+i,0,0); /**/
sl@0	978
sl@0	979	if (!BN_mod_exp_mont_consttime(d,a,b,c,ctx,NULL))
sl@0	980	return(00);
sl@0	981
sl@0	982	if (bp != NULL)
sl@0	983	{
sl@0	984	if (!results)
sl@0	985	{
sl@0	986	BN_print(bp,a);
sl@0	987	BIO_puts(bp," ^ ");
sl@0	988	BN_print(bp,b);
sl@0	989	BIO_puts(bp," % ");
sl@0	990	BN_print(bp,c);
sl@0	991	BIO_puts(bp," - ");
sl@0	992	}
sl@0	993	BN_print(bp,d);
sl@0	994	BIO_puts(bp,"\n");
sl@0	995	}
sl@0	996	BN_exp(e,a,b,ctx);
sl@0	997	BN_sub(e,e,d);
sl@0	998	BN_div(a,b,e,c,ctx);
sl@0	999	if(!BN_is_zero(b))
sl@0	1000	{
sl@0	1001	fprintf(stderr,"Modulo exponentiation test failed!\n");
sl@0	1002	return 0;
sl@0	1003	}
sl@0	1004	}
sl@0	1005	BN_free(a);
sl@0	1006	BN_free(b);
sl@0	1007	BN_free(c);
sl@0	1008	BN_free(d);
sl@0	1009	BN_free(e);
sl@0	1010	return(1);
sl@0	1011	}
sl@0	1012
sl@0	1013	int test_exp(BIO bp, BN_CTX ctx)
sl@0	1014	{
sl@0	1015	BIGNUM a,b,d,e,*one;
sl@0	1016	int i;
sl@0	1017
sl@0	1018	a=BN_new();
sl@0	1019	b=BN_new();
sl@0	1020	d=BN_new();
sl@0	1021	e=BN_new();
sl@0	1022	one=BN_new();
sl@0	1023	BN_one(one);
sl@0	1024
sl@0	1025	for (i=0; i<num2; i++)
sl@0	1026	{
sl@0	1027	BN_bntest_rand(a,20+i5,0,0); /*/
sl@0	1028	BN_bntest_rand(b,2+i,0,0); /**/
sl@0	1029
sl@0	1030	if (!BN_exp(d,a,b,ctx))
sl@0	1031	return(00);
sl@0	1032
sl@0	1033	if (bp != NULL)
sl@0	1034	{
sl@0	1035	if (!results)
sl@0	1036	{
sl@0	1037	BN_print(bp,a);
sl@0	1038	BIO_puts(bp," ^ ");
sl@0	1039	BN_print(bp,b);
sl@0	1040	BIO_puts(bp," - ");
sl@0	1041	}
sl@0	1042	BN_print(bp,d);
sl@0	1043	BIO_puts(bp,"\n");
sl@0	1044	}
sl@0	1045	BN_one(e);
sl@0	1046	for( ; !BN_is_zero(b) ; BN_sub(b,b,one))
sl@0	1047	BN_mul(e,e,a,ctx);
sl@0	1048	BN_sub(e,e,d);
sl@0	1049	if(!BN_is_zero(e))
sl@0	1050	{
sl@0	1051	fprintf(stderr,"Exponentiation test failed!\n");
sl@0	1052	return 0;
sl@0	1053	}
sl@0	1054	}
sl@0	1055	BN_free(a);
sl@0	1056	BN_free(b);
sl@0	1057	BN_free(d);
sl@0	1058	BN_free(e);
sl@0	1059	BN_free(one);
sl@0	1060	return(1);
sl@0	1061	}
sl@0	1062
sl@0	1063	int test_gf2m_add(BIO *bp)
sl@0	1064	{
sl@0	1065	BIGNUM a,b,c;
sl@0	1066	int i, ret = 0;
sl@0	1067
sl@0	1068	BN_init(&a);
sl@0	1069	BN_init(&b);
sl@0	1070	BN_init(&c);
sl@0	1071
sl@0	1072	for (i=0; i<num0; i++)
sl@0	1073	{
sl@0	1074	BN_rand(&a,512,0,0);
sl@0	1075	BN_copy(&b, BN_value_one());
sl@0	1076	a.neg=rand_neg();
sl@0	1077	b.neg=rand_neg();
sl@0	1078	BN_GF2m_add(&c,&a,&b);
sl@0	1079	#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
sl@0	1080	if (bp != NULL)
sl@0	1081	{
sl@0	1082	if (!results)
sl@0	1083	{
sl@0	1084	BN_print(bp,&a);
sl@0	1085	BIO_puts(bp," ^ ");
sl@0	1086	BN_print(bp,&b);
sl@0	1087	BIO_puts(bp," = ");
sl@0	1088	}
sl@0	1089	BN_print(bp,&c);
sl@0	1090	BIO_puts(bp,"\n");
sl@0	1091	}
sl@0	1092	#endif
sl@0	1093	/* Test that two added values have the correct parity. */
sl@0	1094	if((BN_is_odd(&a) && BN_is_odd(&c)) \|\| (!BN_is_odd(&a) && !BN_is_odd(&c)))
sl@0	1095	{
sl@0	1096	fprintf(stderr,"GF(2^m) addition test (a) failed!\n");
sl@0	1097	goto err;
sl@0	1098	}
sl@0	1099	BN_GF2m_add(&c,&c,&c);
sl@0	1100	/* Test that c + c = 0. */
sl@0	1101	if(!BN_is_zero(&c))
sl@0	1102	{
sl@0	1103	fprintf(stderr,"GF(2^m) addition test (b) failed!\n");
sl@0	1104	goto err;
sl@0	1105	}
sl@0	1106	}
sl@0	1107	ret = 1;
sl@0	1108	err:
sl@0	1109	BN_free(&a);
sl@0	1110	BN_free(&b);
sl@0	1111	BN_free(&c);
sl@0	1112	return ret;
sl@0	1113	}
sl@0	1114
sl@0	1115	int test_gf2m_mod(BIO *bp)
sl@0	1116	{
sl@0	1117	BIGNUM a,b[2],c,d,*e;
sl@0	1118	int i, j, ret = 0;
sl@0	1119	unsigned int p0[] = {163,7,6,3,0};
sl@0	1120	unsigned int p1[] = {193,15,0};
sl@0	1121
sl@0	1122	a=BN_new();
sl@0	1123	b[0]=BN_new();
sl@0	1124	b[1]=BN_new();
sl@0	1125	c=BN_new();
sl@0	1126	d=BN_new();
sl@0	1127	e=BN_new();
sl@0	1128
sl@0	1129	BN_GF2m_arr2poly(p0, b[0]);
sl@0	1130	BN_GF2m_arr2poly(p1, b[1]);
sl@0	1131
sl@0	1132	for (i=0; i<num0; i++)
sl@0	1133	{
sl@0	1134	BN_bntest_rand(a, 1024, 0, 0);
sl@0	1135	for (j=0; j < 2; j++)
sl@0	1136	{
sl@0	1137	BN_GF2m_mod(c, a, b[j]);
sl@0	1138	#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
sl@0	1139	if (bp != NULL)
sl@0	1140	{
sl@0	1141	if (!results)
sl@0	1142	{
sl@0	1143	BN_print(bp,a);
sl@0	1144	BIO_puts(bp," % ");
sl@0	1145	BN_print(bp,b[j]);
sl@0	1146	BIO_puts(bp," - ");
sl@0	1147	BN_print(bp,c);
sl@0	1148	BIO_puts(bp,"\n");
sl@0	1149	}
sl@0	1150	}
sl@0	1151	#endif
sl@0	1152	BN_GF2m_add(d, a, c);
sl@0	1153	BN_GF2m_mod(e, d, b[j]);
sl@0	1154	/* Test that a + (a mod p) mod p == 0. */
sl@0	1155	if(!BN_is_zero(e))
sl@0	1156	{
sl@0	1157	fprintf(stderr,"GF(2^m) modulo test failed!\n");
sl@0	1158	goto err;
sl@0	1159	}
sl@0	1160	}
sl@0	1161	}
sl@0	1162	ret = 1;
sl@0	1163	err:
sl@0	1164	BN_free(a);
sl@0	1165	BN_free(b[0]);
sl@0	1166	BN_free(b[1]);
sl@0	1167	BN_free(c);
sl@0	1168	BN_free(d);
sl@0	1169	BN_free(e);
sl@0	1170	return ret;
sl@0	1171	}
sl@0	1172
sl@0	1173	int test_gf2m_mod_mul(BIO bp,BN_CTX ctx)
sl@0	1174	{
sl@0	1175	BIGNUM a,b[2],c,d,e,f,g,h;
sl@0	1176	int i, j, ret = 0;
sl@0	1177	unsigned int p0[] = {163,7,6,3,0};
sl@0	1178	unsigned int p1[] = {193,15,0};
sl@0	1179
sl@0	1180	a=BN_new();
sl@0	1181	b[0]=BN_new();
sl@0	1182	b[1]=BN_new();
sl@0	1183	c=BN_new();
sl@0	1184	d=BN_new();
sl@0	1185	e=BN_new();
sl@0	1186	f=BN_new();
sl@0	1187	g=BN_new();
sl@0	1188	h=BN_new();
sl@0	1189
sl@0	1190	BN_GF2m_arr2poly(p0, b[0]);
sl@0	1191	BN_GF2m_arr2poly(p1, b[1]);
sl@0	1192
sl@0	1193	for (i=0; i<num0; i++)
sl@0	1194	{
sl@0	1195	BN_bntest_rand(a, 1024, 0, 0);
sl@0	1196	BN_bntest_rand(c, 1024, 0, 0);
sl@0	1197	BN_bntest_rand(d, 1024, 0, 0);
sl@0	1198	for (j=0; j < 2; j++)
sl@0	1199	{
sl@0	1200	BN_GF2m_mod_mul(e, a, c, b[j], ctx);
sl@0	1201	#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
sl@0	1202	if (bp != NULL)
sl@0	1203	{
sl@0	1204	if (!results)
sl@0	1205	{
sl@0	1206	BN_print(bp,a);
sl@0	1207	BIO_puts(bp," * ");
sl@0	1208	BN_print(bp,c);
sl@0	1209	BIO_puts(bp," % ");
sl@0	1210	BN_print(bp,b[j]);
sl@0	1211	BIO_puts(bp," - ");
sl@0	1212	BN_print(bp,e);
sl@0	1213	BIO_puts(bp,"\n");
sl@0	1214	}
sl@0	1215	}
sl@0	1216	#endif
sl@0	1217	BN_GF2m_add(f, a, d);
sl@0	1218	BN_GF2m_mod_mul(g, f, c, b[j], ctx);
sl@0	1219	BN_GF2m_mod_mul(h, d, c, b[j], ctx);
sl@0	1220	BN_GF2m_add(f, e, g);
sl@0	1221	BN_GF2m_add(f, f, h);
sl@0	1222	/* Test that (a+d)c = ac + dc. /
sl@0	1223	if(!BN_is_zero(f))
sl@0	1224	{
sl@0	1225	fprintf(stderr,"GF(2^m) modular multiplication test failed!\n");
sl@0	1226	goto err;
sl@0	1227	}
sl@0	1228	}
sl@0	1229	}
sl@0	1230	ret = 1;
sl@0	1231	err:
sl@0	1232	BN_free(a);
sl@0	1233	BN_free(b[0]);
sl@0	1234	BN_free(b[1]);
sl@0	1235	BN_free(c);
sl@0	1236	BN_free(d);
sl@0	1237	BN_free(e);
sl@0	1238	BN_free(f);
sl@0	1239	BN_free(g);
sl@0	1240	BN_free(h);
sl@0	1241	return ret;
sl@0	1242	}
sl@0	1243
sl@0	1244	int test_gf2m_mod_sqr(BIO bp,BN_CTX ctx)
sl@0	1245	{
sl@0	1246	BIGNUM a,b[2],c,d;
sl@0	1247	int i, j, ret = 0;
sl@0	1248	unsigned int p0[] = {163,7,6,3,0};
sl@0	1249	unsigned int p1[] = {193,15,0};
sl@0	1250
sl@0	1251	a=BN_new();
sl@0	1252	b[0]=BN_new();
sl@0	1253	b[1]=BN_new();
sl@0	1254	c=BN_new();
sl@0	1255	d=BN_new();
sl@0	1256
sl@0	1257	BN_GF2m_arr2poly(p0, b[0]);
sl@0	1258	BN_GF2m_arr2poly(p1, b[1]);
sl@0	1259
sl@0	1260	for (i=0; i<num0; i++)
sl@0	1261	{
sl@0	1262	BN_bntest_rand(a, 1024, 0, 0);
sl@0	1263	for (j=0; j < 2; j++)
sl@0	1264	{
sl@0	1265	BN_GF2m_mod_sqr(c, a, b[j], ctx);
sl@0	1266	BN_copy(d, a);
sl@0	1267	BN_GF2m_mod_mul(d, a, d, b[j], ctx);
sl@0	1268	#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
sl@0	1269	if (bp != NULL)
sl@0	1270	{
sl@0	1271	if (!results)
sl@0	1272	{
sl@0	1273	BN_print(bp,a);
sl@0	1274	BIO_puts(bp," ^ 2 % ");
sl@0	1275	BN_print(bp,b[j]);
sl@0	1276	BIO_puts(bp, " = ");
sl@0	1277	BN_print(bp,c);
sl@0	1278	BIO_puts(bp,"; a * a = ");
sl@0	1279	BN_print(bp,d);
sl@0	1280	BIO_puts(bp,"\n");
sl@0	1281	}
sl@0	1282	}
sl@0	1283	#endif
sl@0	1284	BN_GF2m_add(d, c, d);
sl@0	1285	/* Test that aa = a^2. /
sl@0	1286	if(!BN_is_zero(d))
sl@0	1287	{
sl@0	1288	fprintf(stderr,"GF(2^m) modular squaring test failed!\n");
sl@0	1289	goto err;
sl@0	1290	}
sl@0	1291	}
sl@0	1292	}
sl@0	1293	ret = 1;
sl@0	1294	err:
sl@0	1295	BN_free(a);
sl@0	1296	BN_free(b[0]);
sl@0	1297	BN_free(b[1]);
sl@0	1298	BN_free(c);
sl@0	1299	BN_free(d);
sl@0	1300	return ret;
sl@0	1301	}
sl@0	1302
sl@0	1303	int test_gf2m_mod_inv(BIO bp,BN_CTX ctx)
sl@0	1304	{
sl@0	1305	BIGNUM a,b[2],c,d;
sl@0	1306	int i, j, ret = 0;
sl@0	1307	unsigned int p0[] = {163,7,6,3,0};
sl@0	1308	unsigned int p1[] = {193,15,0};
sl@0	1309
sl@0	1310	a=BN_new();
sl@0	1311	b[0]=BN_new();
sl@0	1312	b[1]=BN_new();
sl@0	1313	c=BN_new();
sl@0	1314	d=BN_new();
sl@0	1315
sl@0	1316	BN_GF2m_arr2poly(p0, b[0]);
sl@0	1317	BN_GF2m_arr2poly(p1, b[1]);
sl@0	1318
sl@0	1319	for (i=0; i<num0; i++)
sl@0	1320	{
sl@0	1321	BN_bntest_rand(a, 512, 0, 0);
sl@0	1322	for (j=0; j < 2; j++)
sl@0	1323	{
sl@0	1324	BN_GF2m_mod_inv(c, a, b[j], ctx);
sl@0	1325	BN_GF2m_mod_mul(d, a, c, b[j], ctx);
sl@0	1326	#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
sl@0	1327	if (bp != NULL)
sl@0	1328	{
sl@0	1329	if (!results)
sl@0	1330	{
sl@0	1331	BN_print(bp,a);
sl@0	1332	BIO_puts(bp, " * ");
sl@0	1333	BN_print(bp,c);
sl@0	1334	BIO_puts(bp," - 1 % ");
sl@0	1335	BN_print(bp,b[j]);
sl@0	1336	BIO_puts(bp,"\n");
sl@0	1337	}
sl@0	1338	}
sl@0	1339	#endif
sl@0	1340	/* Test that ((1/a)a) = 1. /
sl@0	1341	if(!BN_is_one(d))
sl@0	1342	{
sl@0	1343	fprintf(stderr,"GF(2^m) modular inversion test failed!\n");
sl@0	1344	goto err;
sl@0	1345	}
sl@0	1346	}
sl@0	1347	}
sl@0	1348	ret = 1;
sl@0	1349	err:
sl@0	1350	BN_free(a);
sl@0	1351	BN_free(b[0]);
sl@0	1352	BN_free(b[1]);
sl@0	1353	BN_free(c);
sl@0	1354	BN_free(d);
sl@0	1355	return ret;
sl@0	1356	}
sl@0	1357
sl@0	1358	int test_gf2m_mod_div(BIO bp,BN_CTX ctx)
sl@0	1359	{
sl@0	1360	BIGNUM a,b[2],c,d,e,f;
sl@0	1361	int i, j, ret = 0;
sl@0	1362	unsigned int p0[] = {163,7,6,3,0};
sl@0	1363	unsigned int p1[] = {193,15,0};
sl@0	1364
sl@0	1365	a=BN_new();
sl@0	1366	b[0]=BN_new();
sl@0	1367	b[1]=BN_new();
sl@0	1368	c=BN_new();
sl@0	1369	d=BN_new();
sl@0	1370	e=BN_new();
sl@0	1371	f=BN_new();
sl@0	1372
sl@0	1373	BN_GF2m_arr2poly(p0, b[0]);
sl@0	1374	BN_GF2m_arr2poly(p1, b[1]);
sl@0	1375
sl@0	1376	for (i=0; i<num0; i++)
sl@0	1377	{
sl@0	1378	BN_bntest_rand(a, 512, 0, 0);
sl@0	1379	BN_bntest_rand(c, 512, 0, 0);
sl@0	1380	for (j=0; j < 2; j++)
sl@0	1381	{
sl@0	1382	BN_GF2m_mod_div(d, a, c, b[j], ctx);
sl@0	1383	BN_GF2m_mod_mul(e, d, c, b[j], ctx);
sl@0	1384	BN_GF2m_mod_div(f, a, e, b[j], ctx);
sl@0	1385	#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
sl@0	1386	if (bp != NULL)
sl@0	1387	{
sl@0	1388	if (!results)
sl@0	1389	{
sl@0	1390	BN_print(bp,a);
sl@0	1391	BIO_puts(bp, " = ");
sl@0	1392	BN_print(bp,c);
sl@0	1393	BIO_puts(bp," * ");
sl@0	1394	BN_print(bp,d);
sl@0	1395	BIO_puts(bp, " % ");
sl@0	1396	BN_print(bp,b[j]);
sl@0	1397	BIO_puts(bp,"\n");
sl@0	1398	}
sl@0	1399	}
sl@0	1400	#endif
sl@0	1401	/* Test that ((a/c)c)/a = 1. /
sl@0	1402	if(!BN_is_one(f))
sl@0	1403	{
sl@0	1404	fprintf(stderr,"GF(2^m) modular division test failed!\n");
sl@0	1405	goto err;
sl@0	1406	}
sl@0	1407	}
sl@0	1408	}
sl@0	1409	ret = 1;
sl@0	1410	err:
sl@0	1411	BN_free(a);
sl@0	1412	BN_free(b[0]);
sl@0	1413	BN_free(b[1]);
sl@0	1414	BN_free(c);
sl@0	1415	BN_free(d);
sl@0	1416	BN_free(e);
sl@0	1417	BN_free(f);
sl@0	1418	return ret;
sl@0	1419	}
sl@0	1420
sl@0	1421	int test_gf2m_mod_exp(BIO bp,BN_CTX ctx)
sl@0	1422	{
sl@0	1423	BIGNUM a,b[2],c,d,e,f;
sl@0	1424	int i, j, ret = 0;
sl@0	1425	unsigned int p0[] = {163,7,6,3,0};
sl@0	1426	unsigned int p1[] = {193,15,0};
sl@0	1427
sl@0	1428	a=BN_new();
sl@0	1429	b[0]=BN_new();
sl@0	1430	b[1]=BN_new();
sl@0	1431	c=BN_new();
sl@0	1432	d=BN_new();
sl@0	1433	e=BN_new();
sl@0	1434	f=BN_new();
sl@0	1435
sl@0	1436	BN_GF2m_arr2poly(p0, b[0]);
sl@0	1437	BN_GF2m_arr2poly(p1, b[1]);
sl@0	1438
sl@0	1439	for (i=0; i<num0; i++)
sl@0	1440	{
sl@0	1441	BN_bntest_rand(a, 512, 0, 0);
sl@0	1442	BN_bntest_rand(c, 512, 0, 0);
sl@0	1443	BN_bntest_rand(d, 512, 0, 0);
sl@0	1444	for (j=0; j < 2; j++)
sl@0	1445	{
sl@0	1446	BN_GF2m_mod_exp(e, a, c, b[j], ctx);
sl@0	1447	BN_GF2m_mod_exp(f, a, d, b[j], ctx);
sl@0	1448	BN_GF2m_mod_mul(e, e, f, b[j], ctx);
sl@0	1449	BN_add(f, c, d);
sl@0	1450	BN_GF2m_mod_exp(f, a, f, b[j], ctx);
sl@0	1451	#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
sl@0	1452	if (bp != NULL)
sl@0	1453	{
sl@0	1454	if (!results)
sl@0	1455	{
sl@0	1456	BN_print(bp,a);
sl@0	1457	BIO_puts(bp, " ^ (");
sl@0	1458	BN_print(bp,c);
sl@0	1459	BIO_puts(bp," + ");
sl@0	1460	BN_print(bp,d);
sl@0	1461	BIO_puts(bp, ") = ");
sl@0	1462	BN_print(bp,e);
sl@0	1463	BIO_puts(bp, "; - ");
sl@0	1464	BN_print(bp,f);
sl@0	1465	BIO_puts(bp, " % ");
sl@0	1466	BN_print(bp,b[j]);
sl@0	1467	BIO_puts(bp,"\n");
sl@0	1468	}
sl@0	1469	}
sl@0	1470	#endif
sl@0	1471	BN_GF2m_add(f, e, f);
sl@0	1472	/* Test that a^(c+d)=a^ca^d. /
sl@0	1473	if(!BN_is_zero(f))
sl@0	1474	{
sl@0	1475	fprintf(stderr,"GF(2^m) modular exponentiation test failed!\n");
sl@0	1476	goto err;
sl@0	1477	}
sl@0	1478	}
sl@0	1479	}
sl@0	1480	ret = 1;
sl@0	1481	err:
sl@0	1482	BN_free(a);
sl@0	1483	BN_free(b[0]);
sl@0	1484	BN_free(b[1]);
sl@0	1485	BN_free(c);
sl@0	1486	BN_free(d);
sl@0	1487	BN_free(e);
sl@0	1488	BN_free(f);
sl@0	1489	return ret;
sl@0	1490	}
sl@0	1491
sl@0	1492	int test_gf2m_mod_sqrt(BIO bp,BN_CTX ctx)
sl@0	1493	{
sl@0	1494	BIGNUM a,b[2],c,d,e,f;
sl@0	1495	int i, j, ret = 0;
sl@0	1496	unsigned int p0[] = {163,7,6,3,0};
sl@0	1497	unsigned int p1[] = {193,15,0};
sl@0	1498
sl@0	1499	a=BN_new();
sl@0	1500	b[0]=BN_new();
sl@0	1501	b[1]=BN_new();
sl@0	1502	c=BN_new();
sl@0	1503	d=BN_new();
sl@0	1504	e=BN_new();
sl@0	1505	f=BN_new();
sl@0	1506
sl@0	1507	BN_GF2m_arr2poly(p0, b[0]);
sl@0	1508	BN_GF2m_arr2poly(p1, b[1]);
sl@0	1509
sl@0	1510	for (i=0; i<num0; i++)
sl@0	1511	{
sl@0	1512	BN_bntest_rand(a, 512, 0, 0);
sl@0	1513	for (j=0; j < 2; j++)
sl@0	1514	{
sl@0	1515	BN_GF2m_mod(c, a, b[j]);
sl@0	1516	BN_GF2m_mod_sqrt(d, a, b[j], ctx);
sl@0	1517	BN_GF2m_mod_sqr(e, d, b[j], ctx);
sl@0	1518	#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
sl@0	1519	if (bp != NULL)
sl@0	1520	{
sl@0	1521	if (!results)
sl@0	1522	{
sl@0	1523	BN_print(bp,d);
sl@0	1524	BIO_puts(bp, " ^ 2 - ");
sl@0	1525	BN_print(bp,a);
sl@0	1526	BIO_puts(bp,"\n");
sl@0	1527	}
sl@0	1528	}
sl@0	1529	#endif
sl@0	1530	BN_GF2m_add(f, c, e);
sl@0	1531	/* Test that d^2 = a, where d = sqrt(a). */
sl@0	1532	if(!BN_is_zero(f))
sl@0	1533	{
sl@0	1534	fprintf(stderr,"GF(2^m) modular square root test failed!\n");
sl@0	1535	goto err;
sl@0	1536	}
sl@0	1537	}
sl@0	1538	}
sl@0	1539	ret = 1;
sl@0	1540	err:
sl@0	1541	BN_free(a);
sl@0	1542	BN_free(b[0]);
sl@0	1543	BN_free(b[1]);
sl@0	1544	BN_free(c);
sl@0	1545	BN_free(d);
sl@0	1546	BN_free(e);
sl@0	1547	BN_free(f);
sl@0	1548	return ret;
sl@0	1549	}
sl@0	1550
sl@0	1551	int test_gf2m_mod_solve_quad(BIO bp,BN_CTX ctx)
sl@0	1552	{
sl@0	1553	BIGNUM a,b[2],c,d,*e;
sl@0	1554	int i, j, s = 0, t, ret = 0;
sl@0	1555	unsigned int p0[] = {163,7,6,3,0};
sl@0	1556	unsigned int p1[] = {193,15,0};
sl@0	1557
sl@0	1558	a=BN_new();
sl@0	1559	b[0]=BN_new();
sl@0	1560	b[1]=BN_new();
sl@0	1561	c=BN_new();
sl@0	1562	d=BN_new();
sl@0	1563	e=BN_new();
sl@0	1564
sl@0	1565	BN_GF2m_arr2poly(p0, b[0]);
sl@0	1566	BN_GF2m_arr2poly(p1, b[1]);
sl@0	1567
sl@0	1568	for (i=0; i<num0; i++)
sl@0	1569	{
sl@0	1570	BN_bntest_rand(a, 512, 0, 0);
sl@0	1571	for (j=0; j < 2; j++)
sl@0	1572	{
sl@0	1573	t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
sl@0	1574	if (t)
sl@0	1575	{
sl@0	1576	s++;
sl@0	1577	BN_GF2m_mod_sqr(d, c, b[j], ctx);
sl@0	1578	BN_GF2m_add(d, c, d);
sl@0	1579	BN_GF2m_mod(e, a, b[j]);
sl@0	1580	#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
sl@0	1581	if (bp != NULL)
sl@0	1582	{
sl@0	1583	if (!results)
sl@0	1584	{
sl@0	1585	BN_print(bp,c);
sl@0	1586	BIO_puts(bp, " is root of z^2 + z = ");
sl@0	1587	BN_print(bp,a);
sl@0	1588	BIO_puts(bp, " % ");
sl@0	1589	BN_print(bp,b[j]);
sl@0	1590	BIO_puts(bp, "\n");
sl@0	1591	}
sl@0	1592	}
sl@0	1593	#endif
sl@0	1594	BN_GF2m_add(e, e, d);
sl@0	1595	/* Test that solution of quadratic c satisfies c^2 + c = a. */
sl@0	1596	if(!BN_is_zero(e))
sl@0	1597	{
sl@0	1598	fprintf(stderr,"GF(2^m) modular solve quadratic test failed!\n");
sl@0	1599	goto err;
sl@0	1600	}
sl@0	1601
sl@0	1602	}
sl@0	1603	else
sl@0	1604	{
sl@0	1605	#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
sl@0	1606	if (bp != NULL)
sl@0	1607	{
sl@0	1608	if (!results)
sl@0	1609	{
sl@0	1610	BIO_puts(bp, "There are no roots of z^2 + z = ");
sl@0	1611	BN_print(bp,a);
sl@0	1612	BIO_puts(bp, " % ");
sl@0	1613	BN_print(bp,b[j]);
sl@0	1614	BIO_puts(bp, "\n");
sl@0	1615	}
sl@0	1616	}
sl@0	1617	#endif
sl@0	1618	}
sl@0	1619	}
sl@0	1620	}
sl@0	1621	if (s == 0)
sl@0	1622	{
sl@0	1623	fprintf(stderr,"All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n", num0);
sl@0	1624	fprintf(stderr,"this is very unlikely and probably indicates an error.\n");
sl@0	1625	goto err;
sl@0	1626	}
sl@0	1627	ret = 1;
sl@0	1628	err:
sl@0	1629	BN_free(a);
sl@0	1630	BN_free(b[0]);
sl@0	1631	BN_free(b[1]);
sl@0	1632	BN_free(c);
sl@0	1633	BN_free(d);
sl@0	1634	BN_free(e);
sl@0	1635	return ret;
sl@0	1636	}
sl@0	1637
sl@0	1638	static int genprime_cb(int p, int n, BN_GENCB *arg)
sl@0	1639	{
sl@0	1640	char c='*';
sl@0	1641
sl@0	1642	if (p == 0) c='.';
sl@0	1643	if (p == 1) c='+';
sl@0	1644	if (p == 2) c='*';
sl@0	1645	if (p == 3) c='\n';
sl@0	1646	putc(c, stderr);
sl@0	1647	fflush(stderr);
sl@0	1648	return 1;
sl@0	1649	}
sl@0	1650
sl@0	1651	int test_kron(BIO bp, BN_CTX ctx)
sl@0	1652	{
sl@0	1653	BN_GENCB cb;
sl@0	1654	BIGNUM a,b,r,t;
sl@0	1655	int i;
sl@0	1656	int legendre, kronecker;
sl@0	1657	int ret = 0;
sl@0	1658
sl@0	1659	a = BN_new();
sl@0	1660	b = BN_new();
sl@0	1661	r = BN_new();
sl@0	1662	t = BN_new();
sl@0	1663	if (a == NULL \|\| b == NULL \|\| r == NULL \|\| t == NULL) goto err;
sl@0	1664
sl@0	1665	BN_GENCB_set(&cb, genprime_cb, NULL);
sl@0	1666
sl@0	1667	/* We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol).
sl@0	1668	* In this case we know that if b is prime, then BN_kronecker(a, b, ctx)
sl@0	1669	* is congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol).
sl@0	1670	* So we generate a random prime b and compare these values
sl@0	1671	* for a number of random a's. (That is, we run the Solovay-Strassen
sl@0	1672	* primality test to confirm that b is prime, except that we
sl@0	1673	* don't want to test whether b is prime but whether BN_kronecker
sl@0	1674	* works.) */
sl@0	1675
sl@0	1676	if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, &cb)) goto err;
sl@0	1677	b->neg = rand_neg();
sl@0	1678	putc('\n', stderr);
sl@0	1679
sl@0	1680	for (i = 0; i < num0; i++)
sl@0	1681	{
sl@0	1682	if (!BN_bntest_rand(a, 512, 0, 0)) goto err;
sl@0	1683	a->neg = rand_neg();
sl@0	1684
sl@0	1685	/* t := (\|b\|-1)/2 (note that b is odd) */
sl@0	1686	if (!BN_copy(t, b)) goto err;
sl@0	1687	t->neg = 0;
sl@0	1688	if (!BN_sub_word(t, 1)) goto err;
sl@0	1689	if (!BN_rshift1(t, t)) goto err;
sl@0	1690	/* r := a^t mod b */
sl@0	1691	b->neg=0;
sl@0	1692
sl@0	1693	if (!BN_mod_exp_recp(r, a, t, b, ctx)) goto err;
sl@0	1694	b->neg=1;
sl@0	1695
sl@0	1696	if (BN_is_word(r, 1))
sl@0	1697	legendre = 1;
sl@0	1698	else if (BN_is_zero(r))
sl@0	1699	legendre = 0;
sl@0	1700	else
sl@0	1701	{
sl@0	1702	if (!BN_add_word(r, 1)) goto err;
sl@0	1703	if (0 != BN_ucmp(r, b))
sl@0	1704	{
sl@0	1705	fprintf(stderr, "Legendre symbol computation failed\n");
sl@0	1706	goto err;
sl@0	1707	}
sl@0	1708	legendre = -1;
sl@0	1709	}
sl@0	1710
sl@0	1711	kronecker = BN_kronecker(a, b, ctx);
sl@0	1712	if (kronecker < -1) goto err;
sl@0	1713	/* we actually need BN_kronecker(a, \|b\|) */
sl@0	1714	if (a->neg && b->neg)
sl@0	1715	kronecker = -kronecker;
sl@0	1716
sl@0	1717	if (legendre != kronecker)
sl@0	1718	{
sl@0	1719	fprintf(stderr, "legendre != kronecker; a = ");
sl@0	1720	BN_print_fp(stderr, a);
sl@0	1721	fprintf(stderr, ", b = ");
sl@0	1722	BN_print_fp(stderr, b);
sl@0	1723	fprintf(stderr, "\n");
sl@0	1724	goto err;
sl@0	1725	}
sl@0	1726
sl@0	1727	putc('.', stderr);
sl@0	1728	fflush(stderr);
sl@0	1729	}
sl@0	1730
sl@0	1731	putc('\n', stderr);
sl@0	1732	fflush(stderr);
sl@0	1733	ret = 1;
sl@0	1734	err:
sl@0	1735	if (a != NULL) BN_free(a);
sl@0	1736	if (b != NULL) BN_free(b);
sl@0	1737	if (r != NULL) BN_free(r);
sl@0	1738	if (t != NULL) BN_free(t);
sl@0	1739	return ret;
sl@0	1740	}
sl@0	1741
sl@0	1742	int test_sqrt(BIO bp, BN_CTX ctx)
sl@0	1743	{
sl@0	1744	BN_GENCB cb;
sl@0	1745	BIGNUM a,p,*r;
sl@0	1746	int i, j;
sl@0	1747	int ret = 0;
sl@0	1748
sl@0	1749	a = BN_new();
sl@0	1750	p = BN_new();
sl@0	1751	r = BN_new();
sl@0	1752	if (a == NULL \|\| p == NULL \|\| r == NULL) goto err;
sl@0	1753
sl@0	1754	BN_GENCB_set(&cb, genprime_cb, NULL);
sl@0	1755
sl@0	1756	for (i = 0; i < 16; i++)
sl@0	1757	{
sl@0	1758	if (i < 8)
sl@0	1759	{
sl@0	1760	unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
sl@0	1761
sl@0	1762	if (!BN_set_word(p, primes[i])) goto err;
sl@0	1763	}
sl@0	1764	else
sl@0	1765	{
sl@0	1766	if (!BN_set_word(a, 32)) goto err;
sl@0	1767	if (!BN_set_word(r, 2*i + 1)) goto err;
sl@0	1768
sl@0	1769	if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb)) goto err;
sl@0	1770	putc('\n', stderr);
sl@0	1771	}
sl@0	1772	p->neg = rand_neg();
sl@0	1773
sl@0	1774	for (j = 0; j < num2; j++)
sl@0	1775	{
sl@0	1776	/* construct 'a' such that it is a square modulo p,
sl@0	1777	* but in general not a proper square and not reduced modulo p */
sl@0	1778	if (!BN_bntest_rand(r, 256, 0, 3)) goto err;
sl@0	1779	if (!BN_nnmod(r, r, p, ctx)) goto err;
sl@0	1780	if (!BN_mod_sqr(r, r, p, ctx)) goto err;
sl@0	1781	if (!BN_bntest_rand(a, 256, 0, 3)) goto err;
sl@0	1782	if (!BN_nnmod(a, a, p, ctx)) goto err;
sl@0	1783	if (!BN_mod_sqr(a, a, p, ctx)) goto err;
sl@0	1784	if (!BN_mul(a, a, r, ctx)) goto err;
sl@0	1785	if (rand_neg())
sl@0	1786	if (!BN_sub(a, a, p)) goto err;
sl@0	1787
sl@0	1788	if (!BN_mod_sqrt(r, a, p, ctx)) goto err;
sl@0	1789	if (!BN_mod_sqr(r, r, p, ctx)) goto err;
sl@0	1790
sl@0	1791	if (!BN_nnmod(a, a, p, ctx)) goto err;
sl@0	1792
sl@0	1793	if (BN_cmp(a, r) != 0)
sl@0	1794	{
sl@0	1795	fprintf(stderr, "BN_mod_sqrt failed: a = ");
sl@0	1796	BN_print_fp(stderr, a);
sl@0	1797	fprintf(stderr, ", r = ");
sl@0	1798	BN_print_fp(stderr, r);
sl@0	1799	fprintf(stderr, ", p = ");
sl@0	1800	BN_print_fp(stderr, p);
sl@0	1801	fprintf(stderr, "\n");
sl@0	1802	goto err;
sl@0	1803	}
sl@0	1804
sl@0	1805	putc('.', stderr);
sl@0	1806	fflush(stderr);
sl@0	1807	}
sl@0	1808
sl@0	1809	putc('\n', stderr);
sl@0	1810	fflush(stderr);
sl@0	1811	}
sl@0	1812	ret = 1;
sl@0	1813	err:
sl@0	1814	if (a != NULL) BN_free(a);
sl@0	1815	if (p != NULL) BN_free(p);
sl@0	1816	if (r != NULL) BN_free(r);
sl@0	1817	return ret;
sl@0	1818	}
sl@0	1819
sl@0	1820	int test_lshift(BIO bp,BN_CTX ctx,BIGNUM *a_)
sl@0	1821	{
sl@0	1822	BIGNUM a,b,c,d;
sl@0	1823	int i;
sl@0	1824
sl@0	1825	b=BN_new();
sl@0	1826	c=BN_new();
sl@0	1827	d=BN_new();
sl@0	1828	BN_one(c);
sl@0	1829
sl@0	1830	if(a_)
sl@0	1831	a=a_;
sl@0	1832	else
sl@0	1833	{
sl@0	1834	a=BN_new();
sl@0	1835	BN_bntest_rand(a,200,0,0); /**/
sl@0	1836	a->neg=rand_neg();
sl@0	1837	}
sl@0	1838	for (i=0; i<num0; i++)
sl@0	1839	{
sl@0	1840	BN_lshift(b,a,i+1);
sl@0	1841	BN_add(c,c,c);
sl@0	1842	if (bp != NULL)
sl@0	1843	{
sl@0	1844	if (!results)
sl@0	1845	{
sl@0	1846	BN_print(bp,a);
sl@0	1847	BIO_puts(bp," * ");
sl@0	1848	BN_print(bp,c);
sl@0	1849	BIO_puts(bp," - ");
sl@0	1850	}
sl@0	1851	BN_print(bp,b);
sl@0	1852	BIO_puts(bp,"\n");
sl@0	1853	}
sl@0	1854	BN_mul(d,a,c,ctx);
sl@0	1855	BN_sub(d,d,b);
sl@0	1856	if(!BN_is_zero(d))
sl@0	1857	{
sl@0	1858	fprintf(stderr,"Left shift test failed!\n");
sl@0	1859	fprintf(stderr,"a=");
sl@0	1860	BN_print_fp(stderr,a);
sl@0	1861	fprintf(stderr,"\nb=");
sl@0	1862	BN_print_fp(stderr,b);
sl@0	1863	fprintf(stderr,"\nc=");
sl@0	1864	BN_print_fp(stderr,c);
sl@0	1865	fprintf(stderr,"\nd=");
sl@0	1866	BN_print_fp(stderr,d);
sl@0	1867	fprintf(stderr,"\n");
sl@0	1868	return 0;
sl@0	1869	}
sl@0	1870	}
sl@0	1871	BN_free(a);
sl@0	1872	BN_free(b);
sl@0	1873	BN_free(c);
sl@0	1874	BN_free(d);
sl@0	1875	return(1);
sl@0	1876	}
sl@0	1877
sl@0	1878	int test_lshift1(BIO *bp)
sl@0	1879	{
sl@0	1880	BIGNUM a,b,*c;
sl@0	1881	int i;
sl@0	1882
sl@0	1883	a=BN_new();
sl@0	1884	b=BN_new();
sl@0	1885	c=BN_new();
sl@0	1886
sl@0	1887	BN_bntest_rand(a,200,0,0); /**/
sl@0	1888	a->neg=rand_neg();
sl@0	1889	for (i=0; i<num0; i++)
sl@0	1890	{
sl@0	1891	BN_lshift1(b,a);
sl@0	1892	if (bp != NULL)
sl@0	1893	{
sl@0	1894	if (!results)
sl@0	1895	{
sl@0	1896	BN_print(bp,a);
sl@0	1897	BIO_puts(bp," * 2");
sl@0	1898	BIO_puts(bp," - ");
sl@0	1899	}
sl@0	1900	BN_print(bp,b);
sl@0	1901	BIO_puts(bp,"\n");
sl@0	1902	}
sl@0	1903	BN_add(c,a,a);
sl@0	1904	BN_sub(a,b,c);
sl@0	1905	if(!BN_is_zero(a))
sl@0	1906	{
sl@0	1907	fprintf(stderr,"Left shift one test failed!\n");
sl@0	1908	return 0;
sl@0	1909	}
sl@0	1910
sl@0	1911	BN_copy(a,b);
sl@0	1912	}
sl@0	1913	BN_free(a);
sl@0	1914	BN_free(b);
sl@0	1915	BN_free(c);
sl@0	1916	return(1);
sl@0	1917	}
sl@0	1918
sl@0	1919	int test_rshift(BIO bp,BN_CTX ctx)
sl@0	1920	{
sl@0	1921	BIGNUM a,b,c,d,*e;
sl@0	1922	int i;
sl@0	1923
sl@0	1924	a=BN_new();
sl@0	1925	b=BN_new();
sl@0	1926	c=BN_new();
sl@0	1927	d=BN_new();
sl@0	1928	e=BN_new();
sl@0	1929	BN_one(c);
sl@0	1930
sl@0	1931	BN_bntest_rand(a,200,0,0); /**/
sl@0	1932	a->neg=rand_neg();
sl@0	1933	for (i=0; i<num0; i++)
sl@0	1934	{
sl@0	1935	BN_rshift(b,a,i+1);
sl@0	1936	BN_add(c,c,c);
sl@0	1937	if (bp != NULL)
sl@0	1938	{
sl@0	1939	if (!results)
sl@0	1940	{
sl@0	1941	BN_print(bp,a);
sl@0	1942	BIO_puts(bp," / ");
sl@0	1943	BN_print(bp,c);
sl@0	1944	BIO_puts(bp," - ");
sl@0	1945	}
sl@0	1946	BN_print(bp,b);
sl@0	1947	BIO_puts(bp,"\n");
sl@0	1948	}
sl@0	1949	BN_div(d,e,a,c,ctx);
sl@0	1950	BN_sub(d,d,b);
sl@0	1951	if(!BN_is_zero(d))
sl@0	1952	{
sl@0	1953	fprintf(stderr,"Right shift test failed!\n");
sl@0	1954	return 0;
sl@0	1955	}
sl@0	1956	}
sl@0	1957	BN_free(a);
sl@0	1958	BN_free(b);
sl@0	1959	BN_free(c);
sl@0	1960	BN_free(d);
sl@0	1961	BN_free(e);
sl@0	1962	return(1);
sl@0	1963	}
sl@0	1964
sl@0	1965	int test_rshift1(BIO *bp)
sl@0	1966	{
sl@0	1967	BIGNUM a,b,*c;
sl@0	1968	int i;
sl@0	1969
sl@0	1970	a=BN_new();
sl@0	1971	b=BN_new();
sl@0	1972	c=BN_new();
sl@0	1973
sl@0	1974	BN_bntest_rand(a,200,0,0); /**/
sl@0	1975	a->neg=rand_neg();
sl@0	1976	for (i=0; i<num0; i++)
sl@0	1977	{
sl@0	1978	BN_rshift1(b,a);
sl@0	1979	if (bp != NULL)
sl@0	1980	{
sl@0	1981	if (!results)
sl@0	1982	{
sl@0	1983	BN_print(bp,a);
sl@0	1984	BIO_puts(bp," / 2");
sl@0	1985	BIO_puts(bp," - ");
sl@0	1986	}
sl@0	1987	BN_print(bp,b);
sl@0	1988	BIO_puts(bp,"\n");
sl@0	1989	}
sl@0	1990	BN_sub(c,a,b);
sl@0	1991	BN_sub(c,c,b);
sl@0	1992	if(!BN_is_zero(c) && !BN_abs_is_word(c, 1))
sl@0	1993	{
sl@0	1994	fprintf(stderr,"Right shift one test failed!\n");
sl@0	1995	return 0;
sl@0	1996	}
sl@0	1997	BN_copy(a,b);
sl@0	1998	}
sl@0	1999	BN_free(a);
sl@0	2000	BN_free(b);
sl@0	2001	BN_free(c);
sl@0	2002	return(1);
sl@0	2003	}
sl@0	2004
sl@0	2005	int rand_neg(void)
sl@0	2006	{
sl@0	2007	static unsigned int neg=0;
sl@0	2008	static int sign[8]={0,0,0,1,1,0,1,1};
sl@0	2009
sl@0	2010	return(sign[(neg++)%8]);
sl@0	2011	}

author	sl
	Tue, 10 Jun 2014 14:32:02 +0200
changeset 1	260cb5ec6c19
permissions	-rw-r--r--