*
*/
+
+
#include "cryptlib.h"
#include "bn_lcl.h"
/* 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 (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);
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|),
while (!BN_is_zero(B))
{
- /*
+ /*-
* 0 < B < |n|,
* 0 < A <= |n|,
* (1) -sign*X*a == B (mod |n|),
}
- /* We still have (1) and (2).
+ /*-
+ * We still have (1) and (2).
* Both A and B are odd.
* The following computations ensure that
*
{
BIGNUM *tmp;
- /*
+ /*-
* 0 < B < A,
* (*) -sign*X*a == B (mod |n|),
* sign*Y*a == A (mod |n|)
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|).
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.
}
}
- /*
+ /*-
* The while loop (Euclid's algorithm) ends when
* A == gcd(a,n);
* we have
}
else
{
- BNerr(BN_F_BN_MOD_INVERSE,BN_R_NO_INVERSE);
+ if (pnoinv)
+ *pnoinv = 1;
goto err;
}
ret=R;
/* 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;
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|),
{
BIGNUM *tmp;
- /*
+ /*-
* 0 < B < A,
* (*) -sign*X*a == B (mod |n|),
* sign*Y*a == A (mod |n|)
/* (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|).
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.
sign = -sign;
}
- /*
+ /*-
* The while loop (Euclid's algorithm) ends when
* A == gcd(a,n);
* we have
}
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;