apps/dh.c:228: error: BUFFER_OVERRUN_L3
  Offset: [3, +oo] (⇐ [0, +oo] + 3) Size: [2, +oo] by call to `DH_check`.
Showing all 23 steps of the trace


apps/dh.c:214:3: Call
212.   	if (text)
213.   		{
214.   		DHparams_print(out,dh);
         ^
215.   #ifdef undef
216.   		printf("p=");

crypto/asn1/t_pkey.c:281:1: Parameter `x->p->top`
  279.   #endif
  280.   
  281. > int DHparams_print(BIO *bp, DH *x)
  282.   	{
  283.   	unsigned char *m=NULL;

crypto/asn1/t_pkey.c:286:4: Call
  284.   	int reason=ERR_R_BUF_LIB,i,ret=0;
  285.   
  286.   	i=BN_num_bytes(x->p);
            ^
  287.   	m=(unsigned char *)Malloc((unsigned int)i+10);
  288.   	if (m == NULL)

crypto/bn/bn_lib.c:238:1: Parameter `a->top`
    236.   	}
    237.   
    238. > int BN_num_bits(BIGNUM *a)
    239.   	{
    240.   	BN_ULONG l;

apps/dh.c:228:8: Call
226.   	if (check)
227.   		{
228.   		if (!DH_check(dh,&i))
              ^
229.   			{
230.   			ERR_print_errors(bio_err);

crypto/dh/dh_check.c:73:1: Parameter `dh->p->top`
  71.    */
  72.   
  73. > int DH_check(DH *dh, int *ret)
  74.   	{
  75.   	int ok=0;

crypto/dh/dh_check.c:105:7: Call
  103.   		*ret|=DH_UNABLE_TO_CHECK_GENERATOR;
  104.   
  105.   	if (!BN_is_prime(dh->p,BN_prime_checks,NULL,ctx,NULL))
               ^
  106.   		*ret|=DH_CHECK_P_NOT_PRIME;
  107.   	else

crypto/bn/bn_prime.c:154:1: Parameter `a->top`
    152.   	}
    153.   
    154. > int BN_is_prime(BIGNUM *a, int checks, void (*callback)(int,int,void *),
    155.   	     BN_CTX *ctx_passed, void *cb_arg)
    156.   	{

crypto/bn/bn_prime.c:175:7: Call
    173.   
    174.   	/* Setup the montgomery structure */
    175.   	if (!BN_MONT_CTX_set(mont,a,ctx2)) goto err;
                 ^
    176.   
    177.   	for (i=0; i<checks; i++)

crypto/bn/bn_mont.c:301:1: Parameter `*mont->N.d`
      299.   	}
      300.   
      301. > int BN_MONT_CTX_set(BN_MONT_CTX *mont, BIGNUM *mod, BN_CTX *ctx)
      302.   	{
      303.   	BIGNUM Ri,*R;

crypto/bn/bn_mont.c:307:2: Call
      305.   	BN_init(&Ri);
      306.   	R= &(mont->RR);					/* grab RR as a temp */
      307.   	BN_copy(&(mont->N),mod);			/* Set N */
              ^
      308.   
      309.   #ifdef BN_RECURSION_MONT

crypto/bn/bn_lib.c:499:1: Parameter `*a->d`
        497.   	}
        498.   
        499. > BIGNUM *BN_copy(BIGNUM *a, BIGNUM *b)
        500.   	{
        501.   	int i;

crypto/bn/bn_prime.c:180:5: Call
    178.   		{
    179.   		if (!BN_rand(check,BN_num_bits(a)-1,0,0)) goto err;
    180.   		j=witness(check,a,ctx,ctx2,mont);
               ^
    181.   		if (j == -1) goto err;
    182.   		if (j)

crypto/bn/bn_prime.c:203:1: Parameter `*mont->N.d`
      201.   #define RECP_MUL_MOD
      202.   
      203. > static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx, BN_CTX *ctx2,
      204.   	     BN_MONT_CTX *mont)
      205.   	{

crypto/bn/bn_prime.c:226:7: Call
      224.   	k=BN_num_bits(n1);
      225.   
      226.   	if (!BN_to_montgomery(mont_one,BN_value_one(),mont,ctx2)) goto err;
                   ^
      227.   	if (!BN_to_montgomery(mont_n1,n1,mont,ctx2)) goto err;
      228.   	if (!BN_to_montgomery(mont_a,a,mont,ctx2)) goto err;

crypto/bn/bn_mont.c:71:1: Parameter `*mont->N.d`
        69.   #define MONT_WORD
        70.   
        71. > int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_MONT_CTX *mont,
        72.   	     BN_CTX *ctx)
        73.   	{

crypto/bn/bn_mont.c:101:7: Call
        99.   		}
        100.   	/* reduce from aRR to aR */
        101.   	if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err;
                     ^
        102.   	ctx->tos-=2;
        103.   	return(1);

crypto/bn/bn_mont.c:108:1: Parameter `*mont->N.d`
          106.   	}
          107.   
          108. > int BN_from_montgomery(BIGNUM *ret, BIGNUM *a, BN_MONT_CTX *mont,
          109.   	     BN_CTX *ctx)
          110.   	{

crypto/bn/bn_mont.c:137:3: Assignment
          135.   
          136.   		r->neg=a->neg^n->neg;
          137.   		np=n->d;
                   ^
          138.   		rp=r->d;
          139.   		nrp= &(r->d[nl]);

crypto/bn/bn_mont.c:157:6: Call
          155.   		for (i=0; i<nl; i++)
          156.   			{
          157.   			v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2);
                      ^
          158.   			nrp++;
          159.   			rp++;

crypto/bn/bn_asm.c:144:1: <Length trace>
142.   #else
143.   
144. > BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w)
145.   	{
146.   	BN_ULONG c=0;

crypto/bn/bn_asm.c:144:1: Parameter `*ap`
            142.   #else
            143.   
            144. > BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w)
            145.   	{
            146.   	BN_ULONG c=0;

crypto/bn/bn_asm.c:163:3: Array access: Offset: [3, +oo] (⇐ [0, +oo] + 3) Size: [2, +oo] by call to `DH_check` 
            161.   		mul_add(rp[2],ap[2],bl,bh,c);
            162.   		if (--num == 0) break;
            163.   		mul_add(rp[3],ap[3],bl,bh,c);
                     ^
            164.   		if (--num == 0) break;
            165.   		ap+=4;

BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w)
	{
	BN_ULONG c=0;
	BN_ULONG bl,bh;
	bn_check_num(num);
	if (num <= 0) return((BN_ULONG)0);
	bl=LBITS(w);
	bh=HBITS(w);
	for (;;)
		{
		mul_add(rp[0],ap[0],bl,bh,c);
		if (--num == 0) break;
		mul_add(rp[1],ap[1],bl,bh,c);
		if (--num == 0) break;
		mul_add(rp[2],ap[2],bl,bh,c);
		if (--num == 0) break;
		mul_add(rp[3],ap[3],bl,bh,c);
		if (--num == 0) break;
		ap+=4;
		rp+=4;
		}
	return(c);
	}
['int MAIN(int argc, char **argv)\n\t{\n\tDH *dh=NULL;\n\tint i,badops=0,text=0;\n\tBIO *in=NULL,*out=NULL;\n\tint informat,outformat,check=0,noout=0,C=0,ret=1;\n\tchar *infile,*outfile,*prog;\n\tapps_startup();\n\tif (bio_err == NULL)\n\t\tif ((bio_err=BIO_new(BIO_s_file())) != NULL)\n\t\t\tBIO_set_fp(bio_err,stderr,BIO_NOCLOSE|BIO_FP_TEXT);\n\tinfile=NULL;\n\toutfile=NULL;\n\tinformat=FORMAT_PEM;\n\toutformat=FORMAT_PEM;\n\tprog=argv[0];\n\targc--;\n\targv++;\n\twhile (argc >= 1)\n\t\t{\n\t\tif \t(strcmp(*argv,"-inform") == 0)\n\t\t\t{\n\t\t\tif (--argc < 1) goto bad;\n\t\t\tinformat=str2fmt(*(++argv));\n\t\t\t}\n\t\telse if (strcmp(*argv,"-outform") == 0)\n\t\t\t{\n\t\t\tif (--argc < 1) goto bad;\n\t\t\toutformat=str2fmt(*(++argv));\n\t\t\t}\n\t\telse if (strcmp(*argv,"-in") == 0)\n\t\t\t{\n\t\t\tif (--argc < 1) goto bad;\n\t\t\tinfile= *(++argv);\n\t\t\t}\n\t\telse if (strcmp(*argv,"-out") == 0)\n\t\t\t{\n\t\t\tif (--argc < 1) goto bad;\n\t\t\toutfile= *(++argv);\n\t\t\t}\n\t\telse if (strcmp(*argv,"-check") == 0)\n\t\t\tcheck=1;\n\t\telse if (strcmp(*argv,"-text") == 0)\n\t\t\ttext=1;\n\t\telse if (strcmp(*argv,"-C") == 0)\n\t\t\tC=1;\n\t\telse if (strcmp(*argv,"-noout") == 0)\n\t\t\tnoout=1;\n\t\telse\n\t\t\t{\n\t\t\tBIO_printf(bio_err,"unknown option %s\\n",*argv);\n\t\t\tbadops=1;\n\t\t\tbreak;\n\t\t\t}\n\t\targc--;\n\t\targv++;\n\t\t}\n\tif (badops)\n\t\t{\nbad:\n\t\tBIO_printf(bio_err,"%s [options] <infile >outfile\\n",prog);\n\t\tBIO_printf(bio_err,"where options are\\n");\n\t\tBIO_printf(bio_err," -inform arg   input format - one of DER TXT PEM\\n");\n\t\tBIO_printf(bio_err," -outform arg  output format - one of DER TXT PEM\\n");\n\t\tBIO_printf(bio_err," -in arg       input file\\n");\n\t\tBIO_printf(bio_err," -out arg      output file\\n");\n\t\tBIO_printf(bio_err," -check        check the DH parameters\\n");\n\t\tBIO_printf(bio_err," -text         print a text form of the DH parameters\\n");\n\t\tBIO_printf(bio_err," -C            Output C code\\n");\n\t\tBIO_printf(bio_err," -noout        no output\\n");\n\t\tgoto end;\n\t\t}\n\tERR_load_crypto_strings();\n\tin=BIO_new(BIO_s_file());\n\tout=BIO_new(BIO_s_file());\n\tif ((in == NULL) || (out == NULL))\n\t\t{\n\t\tERR_print_errors(bio_err);\n\t\tgoto end;\n\t\t}\n\tif (infile == NULL)\n\t\tBIO_set_fp(in,stdin,BIO_NOCLOSE);\n\telse\n\t\t{\n\t\tif (BIO_read_filename(in,infile) <= 0)\n\t\t\t{\n\t\t\tperror(infile);\n\t\t\tgoto end;\n\t\t\t}\n\t\t}\n\tif (outfile == NULL)\n\t\tBIO_set_fp(out,stdout,BIO_NOCLOSE);\n\telse\n\t\t{\n\t\tif (BIO_write_filename(out,outfile) <= 0)\n\t\t\t{\n\t\t\tperror(outfile);\n\t\t\tgoto end;\n\t\t\t}\n\t\t}\n\tif\t(informat == FORMAT_ASN1)\n\t\tdh=d2i_DHparams_bio(in,NULL);\n\telse if (informat == FORMAT_PEM)\n\t\tdh=PEM_read_bio_DHparams(in,NULL,NULL);\n\telse\n\t\t{\n\t\tBIO_printf(bio_err,"bad input format specified\\n");\n\t\tgoto end;\n\t\t}\n\tif (dh == NULL)\n\t\t{\n\t\tBIO_printf(bio_err,"unable to load DH parameters\\n");\n\t\tERR_print_errors(bio_err);\n\t\tgoto end;\n\t\t}\n\tif (text)\n\t\t{\n\t\tDHparams_print(out,dh);\n#ifdef undef\n\t\tprintf("p=");\n\t\tBN_print(stdout,dh->p);\n\t\tprintf("\\ng=");\n\t\tBN_print(stdout,dh->g);\n\t\tprintf("\\n");\n\t\tif (dh->length != 0)\n\t\t\tprintf("recomented private length=%ld\\n",dh->length);\n#endif\n\t\t}\n\tif (check)\n\t\t{\n\t\tif (!DH_check(dh,&i))\n\t\t\t{\n\t\t\tERR_print_errors(bio_err);\n\t\t\tgoto end;\n\t\t\t}\n\t\tif (i & DH_CHECK_P_NOT_PRIME)\n\t\t\tprintf("p value is not prime\\n");\n\t\tif (i & DH_CHECK_P_NOT_STRONG_PRIME)\n\t\t\tprintf("p value is not a strong prime\\n");\n\t\tif (i & DH_UNABLE_TO_CHECK_GENERATOR)\n\t\t\tprintf("unable to check the generator value\\n");\n\t\tif (i & DH_NOT_SUITABLE_GENERATOR)\n\t\t\tprintf("the g value is not a generator\\n");\n\t\tif (i == 0)\n\t\t\tprintf("DH parameters appear to be ok.\\n");\n\t\t}\n\tif (C)\n\t\t{\n\t\tunsigned char *data;\n\t\tint len,l,bits;\n\t\tlen=BN_num_bytes(dh->p);\n\t\tbits=BN_num_bits(dh->p);\n\t\tdata=(unsigned char *)Malloc(len);\n\t\tif (data == NULL)\n\t\t\t{\n\t\t\tperror("Malloc");\n\t\t\tgoto end;\n\t\t\t}\n\t\tl=BN_bn2bin(dh->p,data);\n\t\tprintf("static unsigned char dh%d_p[]={",bits);\n\t\tfor (i=0; i<l; i++)\n\t\t\t{\n\t\t\tif ((i%12) == 0) printf("\\n\\t");\n\t\t\tprintf("0x%02X,",data[i]);\n\t\t\t}\n\t\tprintf("\\n\\t};\\n");\n\t\tl=BN_bn2bin(dh->g,data);\n\t\tprintf("static unsigned char dh%d_g[]={",bits);\n\t\tfor (i=0; i<l; i++)\n\t\t\t{\n\t\t\tif ((i%12) == 0) printf("\\n\\t");\n\t\t\tprintf("0x%02X,",data[i]);\n\t\t\t}\n\t\tprintf("\\n\\t};\\n\\n");\n\t\tprintf("DH *get_dh%d()\\n\\t{\\n",bits);\n\t\tprintf("\\tDH *dh;\\n\\n");\n\t\tprintf("\\tif ((dh=DH_new()) == NULL) return(NULL);\\n");\n\t\tprintf("\\tdh->p=BN_bin2bn(dh%d_p,sizeof(dh%d_p),NULL);\\n",\n\t\t\tbits,bits);\n\t\tprintf("\\tdh->g=BN_bin2bn(dh%d_g,sizeof(dh%d_g),NULL);\\n",\n\t\t\tbits,bits);\n\t\tprintf("\\tif ((dh->p == NULL) || (dh->g == NULL))\\n");\n\t\tprintf("\\t\\treturn(NULL);\\n");\n\t\tprintf("\\treturn(dh);\\n\\t}\\n");\n\t\t}\n\tif (!noout)\n\t\t{\n\t\tif \t(outformat == FORMAT_ASN1)\n\t\t\ti=i2d_DHparams_bio(out,dh);\n\t\telse if (outformat == FORMAT_PEM)\n\t\t\ti=PEM_write_bio_DHparams(out,dh);\n\t\telse\t{\n\t\t\tBIO_printf(bio_err,"bad output format specified for outfile\\n");\n\t\t\tgoto end;\n\t\t\t}\n\t\tif (!i)\n\t\t\t{\n\t\t\tBIO_printf(bio_err,"unable to write DH paramaters\\n");\n\t\t\tERR_print_errors(bio_err);\n\t\t\tgoto end;\n\t\t\t}\n\t\t}\n\tret=0;\nend:\n\tif (in != NULL) BIO_free(in);\n\tif (out != NULL) BIO_free(out);\n\tif (dh != NULL) DH_free(dh);\n\tEXIT(ret);\n\t}', 'int DHparams_print(BIO *bp, DH *x)\n\t{\n\tunsigned char *m=NULL;\n\tint reason=ERR_R_BUF_LIB,i,ret=0;\n\ti=BN_num_bytes(x->p);\n\tm=(unsigned char *)Malloc((unsigned int)i+10);\n\tif (m == NULL)\n\t\t{\n\t\treason=ERR_R_MALLOC_FAILURE;\n\t\tgoto err;\n\t\t}\n\tif (BIO_printf(bp,"Diffie-Hellman-Parameters: (%d bit)\\n",\n\t\tBN_num_bits(x->p)) <= 0)\n\t\tgoto err;\n\tif (!print(bp,"prime:",x->p,m,4)) goto err;\n\tif (!print(bp,"generator:",x->g,m,4)) goto err;\n\tif (x->length != 0)\n\t\t{\n\t\tif (BIO_printf(bp,"    recomented-private-length: %d bits\\n",\n\t\t\t(int)x->length) <= 0) goto err;\n\t\t}\n\tret=1;\n\tif (0)\n\t\t{\nerr:\n\t\tDHerr(DH_F_DHPARAMS_PRINT,reason);\n\t\t}\n\tif (m != NULL) Free((char *)m);\n\treturn(ret);\n\t}', 'int BN_num_bits(BIGNUM *a)\n\t{\n\tBN_ULONG l;\n\tint i;\n\tbn_check_top(a);\n\tif (a->top == 0) return(0);\n\tl=a->d[a->top-1];\n\ti=(a->top-1)*BN_BITS2;\n\tif (l == 0)\n\t\t{\n#if !defined(NO_STDIO) && !defined(WIN16)\n\t\tfprintf(stderr,"BAD TOP VALUE\\n");\n#endif\n\t\tabort();\n\t\t}\n\treturn(i+BN_num_bits_word(l));\n\t}', 'int DH_check(DH *dh, int *ret)\n\t{\n\tint ok=0;\n\tBN_CTX *ctx=NULL;\n\tBN_ULONG l;\n\tBIGNUM *q=NULL;\n\t*ret=0;\n\tctx=BN_CTX_new();\n\tif (ctx == NULL) goto err;\n\tq=BN_new();\n\tif (q == NULL) goto err;\n\tif (BN_is_word(dh->g,DH_GENERATOR_2))\n\t\t{\n\t\tl=BN_mod_word(dh->p,24);\n\t\tif (l != 11) *ret|=DH_NOT_SUITABLE_GENERATOR;\n\t\t}\n\telse if (BN_is_word(dh->g,DH_GENERATOR_5))\n\t\t{\n\t\tl=BN_mod_word(dh->p,10);\n\t\tif ((l != 3) && (l != 7))\n\t\t\t*ret|=DH_NOT_SUITABLE_GENERATOR;\n\t\t}\n\telse\n\t\t*ret|=DH_UNABLE_TO_CHECK_GENERATOR;\n\tif (!BN_is_prime(dh->p,BN_prime_checks,NULL,ctx,NULL))\n\t\t*ret|=DH_CHECK_P_NOT_PRIME;\n\telse\n\t\t{\n\t\tif (!BN_rshift1(q,dh->p)) goto err;\n\t\tif (!BN_is_prime(q,BN_prime_checks,NULL,ctx,NULL))\n\t\t\t*ret|=DH_CHECK_P_NOT_STRONG_PRIME;\n\t\t}\n\tok=1;\nerr:\n\tif (ctx != NULL) BN_CTX_free(ctx);\n\tif (q != NULL) BN_free(q);\n\treturn(ok);\n\t}', 'int BN_is_prime(BIGNUM *a, int checks, void (*callback)(int,int,void *),\n\t     BN_CTX *ctx_passed, void *cb_arg)\n\t{\n\tint i,j,c2=0,ret= -1;\n\tBIGNUM *check;\n\tBN_CTX *ctx=NULL,*ctx2=NULL;\n\tBN_MONT_CTX *mont=NULL;\n\tif (!BN_is_odd(a))\n\t\treturn(0);\n\tif (ctx_passed != NULL)\n\t\tctx=ctx_passed;\n\telse\n\t\tif ((ctx=BN_CTX_new()) == NULL) goto err;\n\tif ((ctx2=BN_CTX_new()) == NULL) goto err;\n\tif ((mont=BN_MONT_CTX_new()) == NULL) goto err;\n\tcheck= &(ctx->bn[ctx->tos++]);\n\tif (!BN_MONT_CTX_set(mont,a,ctx2)) goto err;\n\tfor (i=0; i<checks; i++)\n\t\t{\n\t\tif (!BN_rand(check,BN_num_bits(a)-1,0,0)) goto err;\n\t\tj=witness(check,a,ctx,ctx2,mont);\n\t\tif (j == -1) goto err;\n\t\tif (j)\n\t\t\t{\n\t\t\tret=0;\n\t\t\tgoto err;\n\t\t\t}\n\t\tif (callback != NULL) callback(1,c2++,cb_arg);\n\t\t}\n\tret=1;\nerr:\n\tctx->tos--;\n\tif ((ctx_passed == NULL) && (ctx != NULL))\n\t\tBN_CTX_free(ctx);\n\tif (ctx2 != NULL)\n\t\tBN_CTX_free(ctx2);\n\tif (mont != NULL) BN_MONT_CTX_free(mont);\n\treturn(ret);\n\t}', 'int BN_MONT_CTX_set(BN_MONT_CTX *mont, BIGNUM *mod, BN_CTX *ctx)\n\t{\n\tBIGNUM Ri,*R;\n\tBN_init(&Ri);\n\tR= &(mont->RR);\n\tBN_copy(&(mont->N),mod);\n#ifdef BN_RECURSION_MONT\n\tif (mont->N.top < BN_MONT_CTX_SET_SIZE_WORD)\n#endif\n\t\t{\n\t\tBIGNUM tmod;\n\t\tBN_ULONG buf[2];\n\t\tmont->use_word=1;\n\t\tmont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;\n\t\tBN_zero(R);\n\t\tBN_set_bit(R,BN_BITS2);\n\t\tbuf[0]=mod->d[0];\n\t\tbuf[1]=0;\n\t\ttmod.d=buf;\n\t\ttmod.top=1;\n\t\ttmod.max=mod->max;\n\t\ttmod.neg=mod->neg;\n\t\tif ((BN_mod_inverse(&Ri,R,&tmod,ctx)) == NULL)\n\t\t\tgoto err;\n\t\tBN_lshift(&Ri,&Ri,BN_BITS2);\n\t\tif (!BN_is_zero(&Ri))\n\t\t\t{\n#if 1\n\t\t\tBN_sub_word(&Ri,1);\n#else\n\t\t\tBN_usub(&Ri,&Ri,BN_value_one());\n#endif\n\t\t\t}\n\t\telse\n\t\t\t{\n\t\t\tBN_set_word(&Ri,BN_MASK2);\n\t\t\t}\n\t\tBN_div(&Ri,NULL,&Ri,&tmod,ctx);\n\t\tmont->n0=Ri.d[0];\n\t\tBN_free(&Ri);\n\t\t}\n#ifdef BN_RECURSION_MONT\n\telse\n\t\t{\n\t\tmont->use_word=0;\n\t\tmont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;\n#if 1\n\t\tBN_zero(R);\n\t\tBN_set_bit(R,mont->ri);\n#else\n\t\tBN_lshift(R,BN_value_one(),mont->ri);\n#endif\n\t\tif ((BN_mod_inverse(&Ri,R,mod,ctx)) == NULL)\n\t\t\tgoto err;\n\t\tBN_lshift(&Ri,&Ri,mont->ri);\n#if 1\n\t\tBN_sub_word(&Ri,1);\n#else\n\t\tBN_usub(&Ri,&Ri,BN_value_one());\n#endif\n\t\tBN_div(&(mont->Ni),NULL,&Ri,mod,ctx);\n\t\tBN_free(&Ri);\n\t\t}\n#endif\n#if 1\n\tBN_zero(&(mont->RR));\n\tBN_set_bit(&(mont->RR),mont->ri*2);\n#else\n\tBN_lshift(mont->RR,BN_value_one(),mont->ri*2);\n#endif\n\tBN_mod(&(mont->RR),&(mont->RR),&(mont->N),ctx);\n\treturn(1);\nerr:\n\treturn(0);\n\t}', 'BIGNUM *BN_copy(BIGNUM *a, BIGNUM *b)\n\t{\n\tint i;\n\tBN_ULONG *A;\n\tconst BN_ULONG *B;\n\tbn_check_top(b);\n\tif (a == b) return(a);\n\tif (bn_wexpand(a,b->top) == NULL) return(NULL);\n#if 1\n\tA=a->d;\n\tB=b->d;\n\tfor (i=b->top>>2; i>0; i--,A+=4,B+=4)\n\t\t{\n\t\tBN_ULONG a0,a1,a2,a3;\n\t\ta0=B[0]; a1=B[1]; a2=B[2]; a3=B[3];\n\t\tA[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3;\n\t\t}\n\tswitch (b->top&3)\n\t\t{\n\t\tcase 3: A[2]=B[2];\n\t\tcase 2: A[1]=B[1];\n\t\tcase 1: A[0]=B[0];\n\t\tcase 0: ;\n\t\t}\n#else\n\tmemcpy(a->d,b->d,sizeof(b->d[0])*b->top);\n#endif\n\ta->top=b->top;\n\tif ((a->top == 0) && (a->d != NULL))\n\t\ta->d[0]=0;\n\ta->neg=b->neg;\n\treturn(a);\n\t}', 'static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx, BN_CTX *ctx2,\n\t     BN_MONT_CTX *mont)\n\t{\n\tint k,i,ret= -1,good;\n\tBIGNUM *d,*dd,*tmp,*d1,*d2,*n1;\n\tBIGNUM *mont_one,*mont_n1,*mont_a;\n\td1= &(ctx->bn[ctx->tos]);\n\td2= &(ctx->bn[ctx->tos+1]);\n\tn1= &(ctx->bn[ctx->tos+2]);\n\tctx->tos+=3;\n\tmont_one= &(ctx2->bn[ctx2->tos]);\n\tmont_n1= &(ctx2->bn[ctx2->tos+1]);\n\tmont_a= &(ctx2->bn[ctx2->tos+2]);\n\tctx2->tos+=3;\n\td=d1;\n\tdd=d2;\n\tif (!BN_one(d)) goto err;\n\tif (!BN_sub(n1,n,d)) goto err;\n\tk=BN_num_bits(n1);\n\tif (!BN_to_montgomery(mont_one,BN_value_one(),mont,ctx2)) goto err;\n\tif (!BN_to_montgomery(mont_n1,n1,mont,ctx2)) goto err;\n\tif (!BN_to_montgomery(mont_a,a,mont,ctx2)) goto err;\n\tBN_copy(d,mont_one);\n\tfor (i=k-1; i>=0; i--)\n\t\t{\n\t\tif (\t(BN_cmp(d,mont_one) != 0) &&\n\t\t\t(BN_cmp(d,mont_n1) != 0))\n\t\t\tgood=1;\n\t\telse\n\t\t\tgood=0;\n\t\tBN_mod_mul_montgomery(dd,d,d,mont,ctx2);\n\t\tif (good && (BN_cmp(dd,mont_one) == 0))\n\t\t\t{\n\t\t\tret=1;\n\t\t\tgoto err;\n\t\t\t}\n\t\tif (BN_is_bit_set(n1,i))\n\t\t\t{\n\t\t\tBN_mod_mul_montgomery(d,dd,mont_a,mont,ctx2);\n\t\t\t}\n\t\telse\n\t\t\t{\n\t\t\ttmp=d;\n\t\t\td=dd;\n\t\t\tdd=tmp;\n\t\t\t}\n\t\t}\n\tif (BN_cmp(d,mont_one) == 0)\n\t\ti=0;\n\telse\ti=1;\n\tret=i;\nerr:\n\tctx->tos-=3;\n\tctx2->tos-=3;\n\treturn(ret);\n\t}', 'int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_MONT_CTX *mont,\n\t     BN_CTX *ctx)\n\t{\n\tBIGNUM *tmp,*tmp2;\n        tmp= &(ctx->bn[ctx->tos]);\n        tmp2= &(ctx->bn[ctx->tos]);\n\tctx->tos+=2;\n\tbn_check_top(tmp);\n\tbn_check_top(tmp2);\n\tif (a == b)\n\t\t{\n#if 0\n\t\tbn_wexpand(tmp,a->top*2);\n\t\tbn_wexpand(tmp2,a->top*4);\n\t\tbn_sqr_recursive(tmp->d,a->d,a->top,tmp2->d);\n\t\ttmp->top=a->top*2;\n\t\tif (tmp->d[tmp->top-1] == 0)\n\t\t\ttmp->top--;\n#else\n\t\tif (!BN_sqr(tmp,a,ctx)) goto err;\n#endif\n\t\t}\n\telse\n\t\t{\n\t\tif (!BN_mul(tmp,a,b,ctx)) goto err;\n\t\t}\n\tif (!BN_from_montgomery(r,tmp,mont,ctx)) goto err;\n\tctx->tos-=2;\n\treturn(1);\nerr:\n\treturn(0);\n\t}', 'int BN_from_montgomery(BIGNUM *ret, BIGNUM *a, BN_MONT_CTX *mont,\n\t     BN_CTX *ctx)\n\t{\n#ifdef BN_RECURSION_MONT\n\tif (mont->use_word)\n#endif\n\t\t{\n\t\tBIGNUM *n,*r;\n\t\tBN_ULONG *ap,*np,*rp,n0,v,*nrp;\n\t\tint al,nl,max,i,x,ri;\n\t\tint retn=0;\n\t\tr= &(ctx->bn[ctx->tos]);\n\t\tif (!BN_copy(r,a)) goto err1;\n\t\tn= &(mont->N);\n\t\tap=a->d;\n\t\tal=ri=mont->ri/BN_BITS2;\n\t\tnl=n->top;\n\t\tif ((al == 0) || (nl == 0)) { r->top=0; return(1); }\n\t\tmax=(nl+al+1);\n\t\tif (bn_wexpand(r,max) == NULL) goto err1;\n\t\tif (bn_wexpand(ret,max) == NULL) goto err1;\n\t\tr->neg=a->neg^n->neg;\n\t\tnp=n->d;\n\t\trp=r->d;\n\t\tnrp= &(r->d[nl]);\n#if 1\n\t\tfor (i=r->top; i<max; i++)\n\t\t\tr->d[i]=0;\n#else\n\t\tmemset(&(r->d[r->top]),0,(max-r->top)*sizeof(BN_ULONG));\n#endif\n\t\tr->top=max;\n\t\tn0=mont->n0;\n#ifdef BN_COUNT\nprintf("word BN_from_montgomery %d * %d\\n",nl,nl);\n#endif\n\t\tfor (i=0; i<nl; i++)\n\t\t\t{\n\t\t\tv=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2);\n\t\t\tnrp++;\n\t\t\trp++;\n\t\t\tif (((nrp[-1]+=v)&BN_MASK2) >= v)\n\t\t\t\tcontinue;\n\t\t\telse\n\t\t\t\t{\n\t\t\t\tif (((++nrp[0])&BN_MASK2) != 0) continue;\n\t\t\t\tif (((++nrp[1])&BN_MASK2) != 0) continue;\n\t\t\t\tfor (x=2; (((++nrp[x])&BN_MASK2) == 0); x++) ;\n\t\t\t\t}\n\t\t\t}\n\t\tbn_fix_top(r);\n#if 0\n\t\tBN_rshift(ret,r,mont->ri);\n#else\n\t\tx=ri;\n\t\trp=ret->d;\n\t\tap= &(r->d[x]);\n\t\tif (r->top < x)\n\t\t\tal=0;\n\t\telse\n\t\t\tal=r->top-x;\n\t\tret->top=al;\n\t\tal-=4;\n\t\tfor (i=0; i<al; i+=4)\n\t\t\t{\n\t\t\tBN_ULONG t1,t2,t3,t4;\n\t\t\tt1=ap[i+0];\n\t\t\tt2=ap[i+1];\n\t\t\tt3=ap[i+2];\n\t\t\tt4=ap[i+3];\n\t\t\trp[i+0]=t1;\n\t\t\trp[i+1]=t2;\n\t\t\trp[i+2]=t3;\n\t\t\trp[i+3]=t4;\n\t\t\t}\n\t\tal+=4;\n\t\tfor (; i<al; i++)\n\t\t\trp[i]=ap[i];\n#endif\n\t\tif (BN_ucmp(ret, &(mont->N)) >= 0)\n\t\t\t{\n\t\t\tBN_usub(ret,ret,&(mont->N));\n\t\t\t}\n\t\tretn=1;\nerr1:\n\t\treturn(retn);\n\t\t}\n#ifdef BN_RECURSION_MONT\n\telse\n\t\t{\n\t\tBIGNUM *t1,*t2,*t3;\n\t\tint j,i;\n#ifdef BN_COUNT\nprintf("number BN_from_montgomery\\n");\n#endif\n\t\tt1= &(ctx->bn[ctx->tos]);\n\t\tt2= &(ctx->bn[ctx->tos+1]);\n\t\tt3= &(ctx->bn[ctx->tos+2]);\n\t\ti=mont->Ni.top;\n\t\tbn_wexpand(ret,i);\n\t\tbn_wexpand(t1,i*4);\n\t\tbn_wexpand(t2,i*2);\n\t\tbn_mul_low_recursive(t2->d,a->d,mont->Ni.d,i,t1->d);\n\t\tBN_zero(t3);\n\t\tBN_set_bit(t3,mont->N.top*BN_BITS2);\n\t\tbn_sub_words(t3->d,t3->d,a->d,i);\n\t\tbn_mul_high(ret->d,t2->d,mont->N.d,t3->d,i,t1->d);\n\t\tif (a->top > i)\n\t\t\t{\n\t\t\tj=(int)(bn_add_words(ret->d,ret->d,&(a->d[i]),i));\n\t\t\tif (j)\n\t\t\t\tbn_sub_words(ret->d,ret->d,mont->N.d,i);\n\t\t\t}\n\t\tret->top=i;\n\t\tbn_fix_top(ret);\n\t\tif (a->d[0])\n\t\t\tBN_add_word(ret,1);\n\t\telse\n\t\t\t{\n\t\t\tfor (i=1; i<mont->N.top-1; i++)\n\t\t\t\t{\n\t\t\t\tif (a->d[i])\n\t\t\t\t\t{\n\t\t\t\t\tBN_add_word(ret,1);\n\t\t\t\t\tbreak;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\tif (BN_ucmp(ret,&(mont->N)) >= 0)\n\t\t\tBN_usub(ret,ret,&(mont->N));\n\t\treturn(1);\n\t\t}\n#endif\n\t}', 'BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w)\n\t{\n\tBN_ULONG c=0;\n\tBN_ULONG bl,bh;\n\tbn_check_num(num);\n\tif (num <= 0) return((BN_ULONG)0);\n\tbl=LBITS(w);\n\tbh=HBITS(w);\n\tfor (;;)\n\t\t{\n\t\tmul_add(rp[0],ap[0],bl,bh,c);\n\t\tif (--num == 0) break;\n\t\tmul_add(rp[1],ap[1],bl,bh,c);\n\t\tif (--num == 0) break;\n\t\tmul_add(rp[2],ap[2],bl,bh,c);\n\t\tif (--num == 0) break;\n\t\tmul_add(rp[3],ap[3],bl,bh,c);\n\t\tif (--num == 0) break;\n\t\tap+=4;\n\t\trp+=4;\n\t\t}\n\treturn(c);\n\t}']