diff options
Diffstat (limited to 'crypto/bn/bn_recp.c')
-rw-r--r-- | crypto/bn/bn_recp.c | 176 |
1 files changed, 146 insertions, 30 deletions
diff --git a/crypto/bn/bn_recp.c b/crypto/bn/bn_recp.c index 72cd69d3fc..97ca857ed1 100644 --- a/crypto/bn/bn_recp.c +++ b/crypto/bn/bn_recp.c @@ -60,66 +60,182 @@ #include "cryptlib.h" #include "bn_lcl.h" -int BN_mod_mul_reciprocal(r, x, y, m, i, nb, ctx) +void BN_RECP_CTX_init(recp) +BN_RECP_CTX *recp; + { + BN_init(&(recp->N)); + BN_init(&(recp->Nr)); + recp->num_bits=0; + recp->flags=0; + } + +BN_RECP_CTX *BN_RECP_CTX_new() + { + BN_RECP_CTX *ret; + + if ((ret=(BN_RECP_CTX *)Malloc(sizeof(BN_RECP_CTX))) == NULL) + return(NULL); + + BN_RECP_CTX_init(ret); + ret->flags=BN_FLG_MALLOCED; + return(ret); + } + +void BN_RECP_CTX_free(recp) +BN_RECP_CTX *recp; + { + BN_free(&(recp->N)); + BN_free(&(recp->Nr)); + if (recp->flags & BN_FLG_MALLOCED) + Free(recp); + } + +int BN_RECP_CTX_set(recp,d,ctx) +BN_RECP_CTX *recp; +BIGNUM *d; +BN_CTX *ctx; + { + BN_copy(&(recp->N),d); + BN_zero(&(recp->Nr)); + recp->num_bits=BN_num_bits(d); + recp->shift=0; + return(1); + } + +int BN_mod_mul_reciprocal(r, x, y, recp, ctx) BIGNUM *r; BIGNUM *x; BIGNUM *y; +BN_RECP_CTX *recp; +BN_CTX *ctx; + { + int ret=0; + BIGNUM *a; + + a= &(ctx->bn[ctx->tos++]); + if (y != NULL) + { + if (x == y) + { if (!BN_sqr(a,x,ctx)) goto err; } + else + { if (!BN_mul(a,x,y,ctx)) goto err; } + } + else + a=x; /* Just do the mod */ + + BN_div_recp(NULL,r,a,recp,ctx); + ret=1; +err: + ctx->tos--; + return(ret); + } + +int BN_div_recp(dv,rem,m,recp,ctx) +BIGNUM *dv; +BIGNUM *rem; BIGNUM *m; -BIGNUM *i; -int nb; +BN_RECP_CTX *recp; BN_CTX *ctx; { - int ret=0,j; - BIGNUM *a,*b,*c,*d; + int i,j,tos,ret=0,ex; + BIGNUM *a,*b,*d,*r; + + tos=ctx->tos; + a= &(ctx->bn[ctx->tos++]); + b= &(ctx->bn[ctx->tos++]); + if (dv != NULL) + d=dv; + else + d= &(ctx->bn[ctx->tos++]); + if (rem != NULL) + r=rem; + else + r= &(ctx->bn[ctx->tos++]); + + if (BN_ucmp(m,&(recp->N)) < 0) + { + BN_zero(d); + BN_copy(r,m); + ctx->tos=tos; + return(1); + } - a=ctx->bn[ctx->tos++]; - b=ctx->bn[ctx->tos++]; - c=ctx->bn[ctx->tos++]; - d=ctx->bn[ctx->tos++]; + /* We want the remainder + * Given input of ABCDEF / ab + * we need multiply ABCDEF by 3 digests of the reciprocal of ab + * + */ + i=BN_num_bits(m); - if (x == y) - { if (!BN_sqr(a,x,ctx)) goto err; } + j=recp->num_bits*2; + if (j > i) + { + i=j; + ex=0; + } else - { if (!BN_mul(a,x,y)) goto err; } - if (!BN_rshift(d,a,nb)) goto err; - if (!BN_mul(b,d,i)) goto err; - if (!BN_rshift(c,b,nb)) goto err; - if (!BN_mul(b,m,c)) goto err; - if (!BN_sub(r,a,b)) goto err; + { + ex=(i-j)/2; + } + + j=i/2; + + if (i != recp->shift) + recp->shift=BN_reciprocal(&(recp->Nr),&(recp->N), + i,ctx); + + if (!BN_rshift(a,m,j-ex)) goto err; + if (!BN_mul(b,a,&(recp->Nr),ctx)) goto err; + if (!BN_rshift(d,b,j+ex)) goto err; + d->neg=0; + if (!BN_mul(b,&(recp->N),d,ctx)) goto err; + if (!BN_usub(r,m,b)) goto err; + r->neg=0; + j=0; - while (BN_cmp(r,m) >= 0) +#if 1 + while (BN_ucmp(r,&(recp->N)) >= 0) { if (j++ > 2) { BNerr(BN_F_BN_MOD_MUL_RECIPROCAL,BN_R_BAD_RECIPROCAL); goto err; } - if (!BN_sub(r,r,m)) goto err; + if (!BN_usub(r,r,&(recp->N))) goto err; + if (!BN_add_word(d,1)) goto err; } +#endif + r->neg=BN_is_zero(r)?0:m->neg; + d->neg=m->neg^recp->N.neg; ret=1; err: - ctx->tos-=4; + ctx->tos=tos; return(ret); - } + } -int BN_reciprocal(r, m,ctx) +/* len is the expected size of the result + * We actually calculate with an extra word of precision, so + * we can do faster division if the remainder is not required. + */ +int BN_reciprocal(r,m,len,ctx) BIGNUM *r; BIGNUM *m; +int len; BN_CTX *ctx; { - int nm,ret= -1; - BIGNUM *t; + int ret= -1; + BIGNUM t; - t=ctx->bn[ctx->tos++]; + BN_init(&t); - nm=BN_num_bits(m); - if (!BN_lshift(t,BN_value_one(),nm*2)) goto err; + BN_zero(&t); + if (!BN_set_bit(&t,len)) goto err; - if (!BN_div(r,NULL,t,m,ctx)) goto err; - ret=nm; + if (!BN_div(r,NULL,&t,m,ctx)) goto err; + ret=len; err: - ctx->tos--; + BN_free(&t); return(ret); } |