mark all block comments that need format preserving so that
[openssl.git] / crypto / bn / bn_gcd.c
index 9787a65..233e3f5 100644 (file)
  *
  */
 
+
+
 #include "cryptlib.h"
 #include "bn_lcl.h"
 
@@ -203,14 +205,31 @@ err:
 
 
 /* solves ax == 1 (mod n) */
+static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
+        const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx);
+
 BIGNUM *BN_mod_inverse(BIGNUM *in,
        const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)
        {
+       BIGNUM *rv;
+       int noinv;
+       rv = int_bn_mod_inverse(in, a, n, ctx, &noinv);
+       if (noinv)
+               BNerr(BN_F_BN_MOD_INVERSE,BN_R_NO_INVERSE);
+       return rv;
+       }
+
+BIGNUM *int_bn_mod_inverse(BIGNUM *in,
+       const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx, int *pnoinv)
+       {
        BIGNUM *A,*B,*X,*Y,*M,*D,*T,*R=NULL;
        BIGNUM *ret=NULL;
        int sign;
 
-       if (BN_get_flags(n, BN_FLG_CONSTTIME) != 0)
+       if (pnoinv)
+               *pnoinv = 0;
+
+       if ((BN_get_flags(a, BN_FLG_CONSTTIME) != 0) || (BN_get_flags(n, BN_FLG_CONSTTIME) != 0))
                {
                return BN_mod_inverse_no_branch(in, a, n, ctx);
                }
@@ -244,7 +263,8 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
                if (!BN_nnmod(B, B, A, ctx)) goto err;
                }
        sign = -1;
-       /* From  B = a mod |n|,  A = |n|  it follows that
+       /*-
+        * From  B = a mod |n|,  A = |n|  it follows that
         *
         *      0 <= B < A,
         *     -sign*X*a  ==  B   (mod |n|),
@@ -261,7 +281,7 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
                
                while (!BN_is_zero(B))
                        {
-                       /*
+                       /*-
                         *      0 < B < |n|,
                         *      0 < A <= |n|,
                         * (1) -sign*X*a  ==  B   (mod |n|),
@@ -308,7 +328,8 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
                                }
 
                        
-                       /* We still have (1) and (2).
+                       /*-
+                        * We still have (1) and (2).
                         * Both  A  and  B  are odd.
                         * The following computations ensure that
                         *
@@ -344,7 +365,7 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
                        {
                        BIGNUM *tmp;
                        
-                       /*
+                       /*-
                         *      0 < B < A,
                         * (*) -sign*X*a  ==  B   (mod |n|),
                         *      sign*Y*a  ==  A   (mod |n|)
@@ -391,7 +412,8 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
                                if (!BN_div(D,M,A,B,ctx)) goto err;
                                }
                        
-                       /* Now
+                       /*-
+                        * Now
                         *      A = D*B + M;
                         * thus we have
                         * (**)  sign*Y*a  ==  D*B + M   (mod |n|).
@@ -404,7 +426,8 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
                        B=M;
                        /* ... so we have  0 <= B < A  again */
                        
-                       /* Since the former  M  is now  B  and the former  B  is now  A,
+                       /*-
+                        * Since the former  M  is now  B  and the former  B  is now  A,
                         * (**) translates into
                         *       sign*Y*a  ==  D*A + B    (mod |n|),
                         * i.e.
@@ -457,7 +480,7 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
                        }
                }
                
-       /*
+       /*-
         * The while loop (Euclid's algorithm) ends when
         *      A == gcd(a,n);
         * we have
@@ -486,7 +509,8 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
                }
        else
                {
-               BNerr(BN_F_BN_MOD_INVERSE,BN_R_NO_INVERSE);
+               if (pnoinv)
+                       *pnoinv = 1;
                goto err;
                }
        ret=R;
@@ -501,7 +525,7 @@ err:
 /* BN_mod_inverse_no_branch is a special version of BN_mod_inverse. 
  * It does not contain branches that may leak sensitive information.
  */
-BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
+static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
        const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)
        {
        BIGNUM *A,*B,*X,*Y,*M,*D,*T,*R=NULL;
@@ -545,7 +569,8 @@ BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
                if (!BN_nnmod(B, pB, A, ctx)) goto err;
                }
        sign = -1;
-       /* From  B = a mod |n|,  A = |n|  it follows that
+       /*-
+        * From  B = a mod |n|,  A = |n|  it follows that
         *
         *      0 <= B < A,
         *     -sign*X*a  ==  B   (mod |n|),
@@ -556,7 +581,7 @@ BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
                {
                BIGNUM *tmp;
                
-               /*
+               /*-
                 *      0 < B < A,
                 * (*) -sign*X*a  ==  B   (mod |n|),
                 *      sign*Y*a  ==  A   (mod |n|)
@@ -571,7 +596,8 @@ BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
                /* (D, M) := (A/B, A%B) ... */          
                if (!BN_div(D,M,pA,B,ctx)) goto err;
                
-               /* Now
+               /*-
+                * Now
                 *      A = D*B + M;
                 * thus we have
                 * (**)  sign*Y*a  ==  D*B + M   (mod |n|).
@@ -584,7 +610,8 @@ BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
                B=M;
                /* ... so we have  0 <= B < A  again */
                
-               /* Since the former  M  is now  B  and the former  B  is now  A,
+               /*-
+                * Since the former  M  is now  B  and the former  B  is now  A,
                 * (**) translates into
                 *       sign*Y*a  ==  D*A + B    (mod |n|),
                 * i.e.
@@ -612,7 +639,7 @@ BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
                sign = -sign;
                }
                
-       /*
+       /*-
         * The while loop (Euclid's algorithm) ends when
         *      A == gcd(a,n);
         * we have
@@ -640,7 +667,7 @@ BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
                }
        else
                {
-               BNerr(BN_F_BN_MOD_INVERSE,BN_R_NO_INVERSE);
+               BNerr(BN_F_BN_MOD_INVERSE_NO_BRANCH,BN_R_NO_INVERSE);
                goto err;
                }
        ret=R;