OpenSSL 0.9.5 merge

*warning* this bumps shared lib minors for libssl and libcrypto from 2.1 to 2.2
if you are using the ssl26 packages for ssh and other things to work you will
need to get new ones (see ~beck/libsslsnap/<arch>) on cvs or ~beck/src-patent.tar.gz on cvs

1 files changed, 122 insertions, 191 deletions

diff --git a/src/lib/libcrypto/bn/bn_mont.c b/src/lib/libcrypto/bn/bn_mont.c
index ee0f410c22..7bb0b91223 100644
--- a/src/lib/libcrypto/bn/bn_mont.c
+++ b/src/lib/libcrypto/bn/bn_mont.c
@@ -57,25 +57,27 @@
  */
 
 /*
- * Details about Montgomery multiplication algorithms can be found at:
- * http://www.ece.orst.edu/ISL/Publications.html
- * http://www.ece.orst.edu/ISL/Koc/papers/j37acmon.pdf
+ * Details about Montgomery multiplication algorithms can be found at
+ * http://security.ece.orst.edu/publications.html, e.g.
+ * http://security.ece.orst.edu/koc/papers/j37acmon.pdf and
+ * sections 3.8 and 4.2 in http://security.ece.orst.edu/koc/papers/r01rsasw.pdf
  */
 
 #include <stdio.h>
 #include "cryptlib.h"
 #include "bn_lcl.h"
 
-#define MONT_WORD
+#define MONT_WORD /* use the faster word-based algorithm */
 
 int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b,
                           BN_MONT_CTX *mont, BN_CTX *ctx)
         {
         BIGNUM *tmp,*tmp2;
 
-        tmp= &(ctx->bn[ctx->tos]);
-        tmp2= &(ctx->bn[ctx->tos]);
-        ctx->tos+=2;
+        BN_CTX_start(ctx);
+        tmp = BN_CTX_get(ctx);
+        tmp2 = BN_CTX_get(ctx);
+        if (tmp == NULL || tmp2 == NULL) goto err;
 
         bn_check_top(tmp);
         bn_check_top(tmp2);
@@ -99,7 +101,7 @@ 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;
+        BN_CTX_end(ctx);
         return(1);
 err:
         return(0);
@@ -108,160 +110,123 @@ err:
 int BN_from_montgomery(BIGNUM *ret, BIGNUM *a, BN_MONT_CTX *mont,
              BN_CTX *ctx)
         {
-#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;
-                int retn=0;
+        int retn=0;
 
-                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 err1;
-                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/words */
-                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 err1;
-                if (bn_wexpand(ret,max) == NULL) goto err1;
+        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);
+        printf("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);
-#else
-                x=ri;
-                rp=ret->d;
-                ap= &(r->d[x]);
-                if (r->top < x)
-                        al=0;
+        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
-                        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;
+                        if (((++nrp[0])&BN_MASK2) != 0) continue;
+                        if (((++nrp[1])&BN_MASK2) != 0) continue;
+                        for (x=2; (((++nrp[x])&BN_MASK2) == 0); x++) ;
                         }
-                al+=4;
-                for (; i<al; i++)
-                        rp[i]=ap[i];
-#endif
-
-                if (BN_ucmp(ret, &(mont->N)) >= 0)
-                        {
-                        BN_usub(ret,ret,&(mont->N)); /* XXX */
-                        }
-                retn=1;
-err1:
-                return(retn);
                 }
-#ifdef BN_RECURSION_MONT
-        else /* bignum version */ 
+        bn_fix_top(r);
+        
+        /* mont->ri will be a multiple of the word size */
+#if 0
+        BN_rshift(ret,r,mont->ri);
+#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)
                 {
-                BIGNUM *t1,*t2,*t3;
-                int j,i;
-
-#ifdef BN_COUNT
-printf("number BN_from_montgomery\n");
-#endif
-
-                t1= &(ctx->bn[ctx->tos]);
-                t2= &(ctx->bn[ctx->tos+1]);
-                t3= &(ctx->bn[ctx->tos+2]);
-
-                i=mont->Ni.top;
-                bn_wexpand(ret,i); /* perhaps only i*2 */
-                bn_wexpand(t1,i*4); /* perhaps only i*2 */
-                bn_wexpand(t2,i*2); /* perhaps only i   */
-
-                bn_mul_low_recursive(t2->d,a->d,mont->Ni.d,i,t1->d);
-
-                BN_zero(t3);
-                BN_set_bit(t3,mont->N.top*BN_BITS2);
-                bn_sub_words(t3->d,t3->d,a->d,i);
-                bn_mul_high(ret->d,t2->d,mont->N.d,t3->d,i,t1->d);
-
-                /* hmm... if a is between i and 2*i, things are bad */
-                if (a->top > i)
-                        {
-                        j=(int)(bn_add_words(ret->d,ret->d,&(a->d[i]),i));
-                        if (j) /* overflow */
-                                bn_sub_words(ret->d,ret->d,mont->N.d,i);
-                        }
-                ret->top=i;
-                bn_fix_top(ret);
-                if (a->d[0])
-                        BN_add_word(ret,1); /* Always? */
-                else    /* Very very rare */
-                        {
-                        for (i=1; i<mont->N.top-1; i++)
-                                {
-                                if (a->d[i])
-                                        {
-                                        BN_add_word(ret,1); /* Always? */
-                                        break;
-                                        }
-                                }
-                        }
-
-                if (BN_ucmp(ret,&(mont->N)) >= 0)
-                        BN_usub(ret,ret,&(mont->N));
-
-                return(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;
+        BN_rshift(ret,t2,mont->ri);
+#endif /* MONT_WORD */
+
+        if (BN_ucmp(ret, &(mont->N)) >= 0)
+                {
+                BN_usub(ret,ret,&(mont->N));
+                }
+        retn=1;
+ err:
+        BN_CTX_end(ctx);
+        return(retn);
         }
 
 BN_MONT_CTX *BN_MONT_CTX_new(void)
@@ -278,7 +243,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));
@@ -306,85 +270,53 @@ int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
         R= &(mont->RR);                                 /* grab RR as a temp */
         BN_copy(&(mont->N),mod);                        /* Set N */
 
-#ifdef BN_RECURSION_MONT
-        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);
-                /* I was bad, this modification of a passed variable was
-                 * breaking the multithreaded stuff :-(
-                 * z=mod->top;
-                 * mod->top=1; */
+                BN_set_bit(R,BN_BITS2);                 /* R */
 
-                buf[0]=mod->d[0];
+                buf[0]=mod->d[0]; /* tmod = N mod word size */
                 buf[1]=0;
                 tmod.d=buf;
                 tmod.top=1;
-                tmod.max=mod->max;
+                tmod.max=2;
                 tmod.neg=mod->neg;
-
+                                                        /* Ri = R^-1 mod N*/
                 if ((BN_mod_inverse(&Ri,R,&tmod,ctx)) == NULL)
                         goto err;
-                BN_lshift(&Ri,&Ri,BN_BITS2);                    /* R*Ri */
+                BN_lshift(&Ri,&Ri,BN_BITS2);            /* R*Ri */
                 if (!BN_is_zero(&Ri))
-                        {
-#if 1
                         BN_sub_word(&Ri,1);
-#else
-                        BN_usub(&Ri,&Ri,BN_value_one());        /* R*Ri - 1 */
-#endif
-                        }
-                else
-                        {
-                        /* This is not common..., 1 in BN_MASK2,
-                         * It happens when buf[0] was == 1.  So for 8 bit,
-                         * this is 1/256, 16bit, 1 in 2^16 etc.
-                         */
-                        BN_set_word(&Ri,BN_MASK2);
-                        }
-                BN_div(&Ri,NULL,&Ri,&tmod,ctx);
+                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];
                 BN_free(&Ri);
-                /* mod->top=z; */
                 }
-#ifdef BN_RECURSION_MONT
-        else
-                {
-                mont->use_word=0;
-                mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;
-#if 1
+#else /* !MONT_WORD */
+                { /* bignum version */
+                mont->ri=BN_num_bits(mod);
                 BN_zero(R);
-                BN_set_bit(R,mont->ri);
-#else
-                BN_lshift(R,BN_value_one(),mont->ri);   /* R */
-#endif
+                BN_set_bit(R,mont->ri);                 /* R = 2^ri */
+                                                        /* Ri = R^-1 mod N*/
                 if ((BN_mod_inverse(&Ri,R,mod,ctx)) == NULL)
                         goto err;
                 BN_lshift(&Ri,&Ri,mont->ri);            /* R*Ri */
-#if 1
                 BN_sub_word(&Ri,1);
-#else
-                BN_usub(&Ri,&Ri,BN_value_one());        /* R*Ri - 1 */
-#endif
+                                                        /* Ni = (R*Ri-1) / N */
                 BN_div(&(mont->Ni),NULL,&Ri,mod,ctx);
                 BN_free(&Ri);
                 }
 #endif
 
         /* setup RR for conversions */
-#if 1
         BN_zero(&(mont->RR));
         BN_set_bit(&(mont->RR),mont->ri*2);
-#else
-        BN_lshift(mont->RR,BN_value_one(),mont->ri*2);
-#endif
         BN_mod(&(mont->RR),&(mont->RR),&(mont->N),ctx);
 
         return(1);
@@ -399,7 +331,6 @@ BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from)
         BN_copy(&(to->RR),&(from->RR));
         BN_copy(&(to->N),&(from->N));
         BN_copy(&(to->Ni),&(from->Ni));
-        to->use_word=from->use_word;
         to->ri=from->ri;
         to->n0=from->n0;
         return(to);