Put the first stage of my bignum debugging adventures into CVS. This code
[openssl.git] / crypto / bn / bn_mont.c
index aaf57da..22d23cc 100644 (file)
 #include "cryptlib.h"
 #include "bn_lcl.h"
 
-int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b,
+#define MONT_WORD /* use the faster word-based algorithm */
+
+int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
                          BN_MONT_CTX *mont, BN_CTX *ctx)
        {
-       BIGNUM *tmp,*tmp2;
+       BIGNUM *tmp;
+       int ret=0;
 
-        tmp= &(ctx->bn[ctx->tos]);
-        tmp2= &(ctx->bn[ctx->tos]);
-       ctx->tos+=2;
+       BN_CTX_start(ctx);
+       tmp = BN_CTX_get(ctx);
+       if (tmp == NULL) goto err;
 
        bn_check_top(tmp);
-       bn_check_top(tmp2);
-
        if (a == b)
                {
-#if 0
-               bn_wexpand(tmp,a->top*2);
-               bn_wexpand(tmp2,a->top*4);
-               bn_sqr_recursive(tmp->d,a->d,a->top,tmp2->d);
-               tmp->top=a->top*2;
-               if (tmp->d[tmp->top-1] == 0)
-                       tmp->top--;
-#else
                if (!BN_sqr(tmp,a,ctx)) goto err;
-#endif
                }
        else
                {
@@ -98,139 +90,149 @@ int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b,
                }
        /* reduce from aRR to aR */
        if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err;
-       ctx->tos-=2;
-       return(1);
+       bn_check_top(r);
+       ret=1;
 err:
-       return(0);
+       BN_CTX_end(ctx);
+       return(ret);
        }
 
-int BN_from_montgomery(BIGNUM *ret, BIGNUM *a, BN_MONT_CTX *mont,
+int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont,
             BN_CTX *ctx)
        {
        int retn=0;
-#ifdef BN_RECURSION_MONT
-       if (mont->use_word)
-#endif
-               {
-               BIGNUM *n,*r;
-               BN_ULONG *ap,*np,*rp,n0,v,*nrp;
-               int al,nl,max,i,x,ri;
 
-               r= &(ctx->bn[ctx->tos]);
+#ifdef MONT_WORD
+       BIGNUM *n,*r;
+       BN_ULONG *ap,*np,*rp,n0,v,*nrp;
+       int al,nl,max,i,x,ri;
 
-               if (!BN_copy(r,a)) goto err;
-               n= &(mont->N);
+       BN_CTX_start(ctx);
+       if ((r = BN_CTX_get(ctx)) == NULL) goto err;
 
-               ap=a->d;
-               /* mont->ri is the size of mont->N in bits (rounded up
-                   to the word size) */
-               al=ri=mont->ri/BN_BITS2;
+       if (!BN_copy(r,a)) goto err;
+       n= &(mont->N);
 
-               nl=n->top;
-               if ((al == 0) || (nl == 0)) { r->top=0; return(1); }
+       ap=a->d;
+       /* mont->ri is the size of mont->N in bits (rounded up
+          to the word size) */
+       al=ri=mont->ri/BN_BITS2;
+       
+       nl=n->top;
+       if ((al == 0) || (nl == 0)) { r->top=0; return(1); }
 
-               max=(nl+al+1); /* allow for overflow (no?) XXX */
-               if (bn_wexpand(r,max) == NULL) goto err;
-               if (bn_wexpand(ret,max) == NULL) goto err;
+       max=(nl+al+1); /* allow for overflow (no?) XXX */
+       if (bn_wexpand(r,max) == NULL) goto err;
+       if (bn_wexpand(ret,max) == NULL) goto err;
 
-               r->neg=a->neg^n->neg;
-               np=n->d;
-               rp=r->d;
-               nrp= &(r->d[nl]);
+       r->neg=a->neg^n->neg;
+       np=n->d;
+       rp=r->d;
+       nrp= &(r->d[nl]);
 
-               /* clear the top words of T */
+       /* clear the top words of T */
 #if 1
-               for (i=r->top; i<max; i++) /* memset? XXX */
-                       r->d[i]=0;
+       for (i=r->top; i<max; i++) /* memset? XXX */
+               r->d[i]=0;
 #else
-               memset(&(r->d[r->top]),0,(max-r->top)*sizeof(BN_ULONG)); 
+       memset(&(r->d[r->top]),0,(max-r->top)*sizeof(BN_ULONG)); 
 #endif
 
-               r->top=max;
-               n0=mont->n0;
+       r->top=max;
+       n0=mont->n0;
 
 #ifdef BN_COUNT
-printf("word BN_from_montgomery %d * %d\n",nl,nl);
+       fprintf(stderr,"word BN_from_montgomery %d * %d\n",nl,nl);
 #endif
-               for (i=0; i<nl; i++)
-                       {
-                       v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2);
-                       nrp++;
-                       rp++;
-                       if (((nrp[-1]+=v)&BN_MASK2) >= v)
-                               continue;
-                       else
-                               {
-                               if (((++nrp[0])&BN_MASK2) != 0) continue;
-                               if (((++nrp[1])&BN_MASK2) != 0) continue;
-                               for (x=2; (((++nrp[x])&BN_MASK2) == 0); x++) ;
-                               }
-                       }
-               bn_fix_top(r);
-
-               /* mont->ri will be a multiple of the word size */
-#if 0
-               BN_rshift(ret,r,mont->ri);
+       for (i=0; i<nl; i++)
+               {
+#ifdef __TANDEM
+                {
+                   long long t1;
+                   long long t2;
+                   long long t3;
+                   t1 = rp[0] * (n0 & 0177777);
+                   t2 = 037777600000l;
+                   t2 = n0 & t2;
+                   t3 = rp[0] & 0177777;
+                   t2 = (t3 * t2) & BN_MASK2;
+                   t1 = t1 + t2;
+                   v=bn_mul_add_words(rp,np,nl,(BN_ULONG) t1);
+                }
 #else
-               x=ri;
-               rp=ret->d;
-               ap= &(r->d[x]);
-               if (r->top < x)
-                       al=0;
-               else
-                       al=r->top-x;
-               ret->top=al;
-               al-=4;
-               for (i=0; i<al; i+=4)
-                       {
-                       BN_ULONG t1,t2,t3,t4;
-
-                       t1=ap[i+0];
-                       t2=ap[i+1];
-                       t3=ap[i+2];
-                       t4=ap[i+3];
-                       rp[i+0]=t1;
-                       rp[i+1]=t2;
-                       rp[i+2]=t3;
-                       rp[i+3]=t4;
-                       }
-               al+=4;
-               for (; i<al; i++)
-                       rp[i]=ap[i];
+               v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2);
 #endif
-
-               if (BN_ucmp(ret, &(mont->N)) >= 0)
+               nrp++;
+               rp++;
+               if (((nrp[-1]+=v)&BN_MASK2) >= v)
+                       continue;
+               else
                        {
-                       BN_usub(ret,ret,&(mont->N)); /* XXX */
+                       if (((++nrp[0])&BN_MASK2) != 0) continue;
+                       if (((++nrp[1])&BN_MASK2) != 0) continue;
+                       for (x=2; (((++nrp[x])&BN_MASK2) == 0); x++) ;
                        }
-               retn=1;
                }
-#ifdef BN_RECURSION_MONT
-       else /* bignum version */ 
+       bn_correct_top(r);
+       
+       /* mont->ri will be a multiple of the word size */
+#if 0
+       BN_rshift(ret,r,mont->ri);
+#else
+       ret->neg = r->neg;
+       x=ri;
+       rp=ret->d;
+       ap= &(r->d[x]);
+       if (r->top < x)
+               al=0;
+       else
+               al=r->top-x;
+       ret->top=al;
+       al-=4;
+       for (i=0; i<al; i+=4)
                {
-               BIGNUM *t1,*t2;
-
-               t1=&(ctx->bn[ctx->tos]);
-               t2=&(ctx->bn[ctx->tos+1]);
-               ctx->tos+=2;
-
-               if (!BN_copy(t1,a)) goto err;
-               BN_mask_bits(t1,mont->ri);
-
-               if (!BN_mul(t2,t1,&mont->Ni,ctx)) goto err;
-               BN_mask_bits(t2,mont->ri);
-
-               if (!BN_mul(t1,t2,&mont->N,ctx)) goto err;
-               if (!BN_add(t2,a,t1)) goto err;
-               BN_rshift(ret,t2,mont->ri);
-
-               if (BN_ucmp(ret,&mont->N) >= 0)
-                       BN_usub(ret,ret,&mont->N);
-               ctx->tos-=2;
-               retn=1;
+               BN_ULONG t1,t2,t3,t4;
+               
+               t1=ap[i+0];
+               t2=ap[i+1];
+               t3=ap[i+2];
+               t4=ap[i+3];
+               rp[i+0]=t1;
+               rp[i+1]=t2;
+               rp[i+2]=t3;
+               rp[i+3]=t4;
                }
+       al+=4;
+       for (; i<al; i++)
+               rp[i]=ap[i];
 #endif
+#else /* !MONT_WORD */ 
+       BIGNUM *t1,*t2;
+
+       BN_CTX_start(ctx);
+       t1 = BN_CTX_get(ctx);
+       t2 = BN_CTX_get(ctx);
+       if (t1 == NULL || t2 == NULL) goto err;
+       
+       if (!BN_copy(t1,a)) goto err;
+       BN_mask_bits(t1,mont->ri);
+
+       if (!BN_mul(t2,t1,&mont->Ni,ctx)) goto err;
+       BN_mask_bits(t2,mont->ri);
+
+       if (!BN_mul(t1,t2,&mont->N,ctx)) goto err;
+       if (!BN_add(t2,a,t1)) goto err;
+       if (!BN_rshift(ret,t2,mont->ri)) goto err;
+#endif /* MONT_WORD */
+
+       if (BN_ucmp(ret, &(mont->N)) >= 0)
+               {
+               if (!BN_usub(ret,ret,&(mont->N))) goto err;
+               }
+       retn=1;
+       bn_check_top(ret);
  err:
+       BN_CTX_end(ctx);
        return(retn);
        }
 
@@ -238,7 +240,7 @@ BN_MONT_CTX *BN_MONT_CTX_new(void)
        {
        BN_MONT_CTX *ret;
 
-       if ((ret=(BN_MONT_CTX *)Malloc(sizeof(BN_MONT_CTX))) == NULL)
+       if ((ret=(BN_MONT_CTX *)OPENSSL_malloc(sizeof(BN_MONT_CTX))) == NULL)
                return(NULL);
 
        BN_MONT_CTX_init(ret);
@@ -248,7 +250,6 @@ BN_MONT_CTX *BN_MONT_CTX_new(void)
 
 void BN_MONT_CTX_init(BN_MONT_CTX *ctx)
        {
-       ctx->use_word=0;
        ctx->ri=0;
        BN_init(&(ctx->RR));
        BN_init(&(ctx->N));
@@ -265,7 +266,7 @@ void BN_MONT_CTX_free(BN_MONT_CTX *mont)
        BN_free(&(mont->N));
        BN_free(&(mont->Ni));
        if (mont->flags & BN_FLG_MALLOCED)
-               Free(mont);
+               OPENSSL_free(mont);
        }
 
 int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
@@ -275,62 +276,61 @@ int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
        BN_init(&Ri);
        R= &(mont->RR);                                 /* grab RR as a temp */
        BN_copy(&(mont->N),mod);                        /* Set N */
+       mont->N.neg = 0;
 
-#ifdef BN_RECURSION_MONT
-       /* the word-based algorithm is faster */
-       if (mont->N.top > BN_MONT_CTX_SET_SIZE_WORD)
-#endif
+#ifdef MONT_WORD
                {
                BIGNUM tmod;
                BN_ULONG buf[2];
 
-               mont->use_word=1;
-
                mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;
-               BN_zero(R);
-               BN_set_bit(R,BN_BITS2);                 /* R = 2^ri */
+               if (!(BN_zero(R))) goto err;
+               if (!(BN_set_bit(R,BN_BITS2))) goto err;        /* R */
 
                buf[0]=mod->d[0]; /* tmod = N mod word size */
                buf[1]=0;
                tmod.d=buf;
                tmod.top=1;
-               tmod.max=2;
-               tmod.neg=mod->neg;
+               tmod.dmax=2;
+               tmod.neg=0;
                                                        /* Ri = R^-1 mod N*/
                if ((BN_mod_inverse(&Ri,R,&tmod,ctx)) == NULL)
                        goto err;
-               BN_lshift(&Ri,&Ri,BN_BITS2);            /* R*Ri */
+               if (!BN_lshift(&Ri,&Ri,BN_BITS2)) goto err; /* R*Ri */
                if (!BN_is_zero(&Ri))
-                       BN_sub_word(&Ri,1);
+                       {
+                       if (!BN_sub_word(&Ri,1)) goto err;
+                       }
                else /* if N mod word size == 1 */
-                       BN_set_word(&Ri,BN_MASK2);  /* Ri-- (mod word size) */
-               BN_div(&Ri,NULL,&Ri,&tmod,ctx); /* Ni = (R*Ri-1)/N,
-                                                * keep only least significant word: */
-               mont->n0=Ri.d[0];
+                       {
+                       if (!BN_set_word(&Ri,BN_MASK2)) goto err;  /* Ri-- (mod word size) */
+                       }
+               if (!BN_div(&Ri,NULL,&Ri,&tmod,ctx)) goto err;
+               /* Ni = (R*Ri-1)/N,
+                * keep only least significant word: */
+               mont->n0 = (Ri.top > 0) ? Ri.d[0] : 0;
                BN_free(&Ri);
                }
-#ifdef BN_RECURSION_MONT
-       else
+#else /* !MONT_WORD */
                { /* bignum version */
-               mont->use_word=0;
-               mont->ri=BN_num_bits(mod);
-               BN_zero(R);
-               BN_set_bit(R,mont->ri);                 /* R = 2^ri */
-                                                       /* Ri = R^-1 mod N*/
-               if ((BN_mod_inverse(&Ri,R,mod,ctx)) == NULL)
+               mont->ri=BN_num_bits(&mont->N);
+               if (!BN_zero(R)) goto err;
+               if (!BN_set_bit(R,mont->ri)) goto err;  /* R = 2^ri */
+                                                       /* Ri = R^-1 mod N*/
+               if ((BN_mod_inverse(&Ri,R,&mont->N,ctx)) == NULL)
                        goto err;
-               BN_lshift(&Ri,&Ri,mont->ri);            /* R*Ri */
-               BN_sub_word(&Ri,1);
+               if (!BN_lshift(&Ri,&Ri,mont->ri)) goto err; /* R*Ri */
+               if (!BN_sub_word(&Ri,1)) goto err;
                                                        /* Ni = (R*Ri-1) / N */
-               BN_div(&(mont->Ni),NULL,&Ri,mod,ctx);
+               if (!BN_div(&(mont->Ni),NULL,&Ri,&mont->N,ctx)) goto err;
                BN_free(&Ri);
                }
 #endif
 
        /* setup RR for conversions */
-       BN_zero(&(mont->RR));
-       BN_set_bit(&(mont->RR),mont->ri*2);
-       BN_mod(&(mont->RR),&(mont->RR),&(mont->N),ctx);
+       if (!BN_zero(&(mont->RR))) goto err;
+       if (!BN_set_bit(&(mont->RR),mont->ri*2)) goto err;
+       if (!BN_mod(&(mont->RR),&(mont->RR),&(mont->N),ctx)) goto err;
 
        return(1);
 err:
@@ -341,10 +341,9 @@ BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from)
        {
        if (to == from) return(to);
 
-       BN_copy(&(to->RR),&(from->RR));
-       BN_copy(&(to->N),&(from->N));
-       BN_copy(&(to->Ni),&(from->Ni));
-       to->use_word=from->use_word;
+       if (!BN_copy(&(to->RR),&(from->RR))) return NULL;
+       if (!BN_copy(&(to->N),&(from->N))) return NULL;
+       if (!BN_copy(&(to->Ni),&(from->Ni))) return NULL;
        to->ri=from->ri;
        to->n0=from->n0;
        return(to);