+int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
+ const BIGNUM *m, BN_CTX *ctx)
+{
+ int i, j, bits, ret = 0, wstart, wend, window, wvalue;
+ int start = 1;
+ BIGNUM *aa;
+ /* Table of variables obtained from 'ctx' */
+ BIGNUM *val[TABLE_SIZE];
+ BN_RECP_CTX recp;
+
+ if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) {
+ /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */
+ BNerr(BN_F_BN_MOD_EXP_RECP, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
+ return -1;
+ }
+
+ bits = BN_num_bits(p);
+
+ if (bits == 0) {
+ ret = BN_one(r);
+ return ret;
+ }
+
+ BN_CTX_start(ctx);
+ aa = BN_CTX_get(ctx);
+ val[0] = BN_CTX_get(ctx);
+ if (!aa || !val[0])
+ goto err;
+
+ BN_RECP_CTX_init(&recp);
+ if (m->neg) {
+ /* ignore sign of 'm' */
+ if (!BN_copy(aa, m))
+ goto err;
+ aa->neg = 0;
+ if (BN_RECP_CTX_set(&recp, aa, ctx) <= 0)
+ goto err;
+ } else {
+ if (BN_RECP_CTX_set(&recp, m, ctx) <= 0)
+ goto err;
+ }
+
+ if (!BN_nnmod(val[0], a, m, ctx))
+ goto err; /* 1 */
+ if (BN_is_zero(val[0])) {
+ BN_zero(r);
+ ret = 1;
+ goto err;
+ }
+
+ window = BN_window_bits_for_exponent_size(bits);
+ if (window > 1) {
+ if (!BN_mod_mul_reciprocal(aa, val[0], val[0], &recp, ctx))
+ goto err; /* 2 */
+ j = 1 << (window - 1);
+ for (i = 1; i < j; i++) {
+ if (((val[i] = BN_CTX_get(ctx)) == NULL) ||
+ !BN_mod_mul_reciprocal(val[i], val[i - 1], aa, &recp, ctx))
+ goto err;
+ }
+ }
+
+ start = 1; /* This is used to avoid multiplication etc
+ * when there is only the value '1' in the
+ * buffer. */
+ wvalue = 0; /* The 'value' of the window */
+ wstart = bits - 1; /* The top bit of the window */
+ wend = 0; /* The bottom bit of the window */
+
+ if (!BN_one(r))
+ goto err;
+
+ for (;;) {
+ if (BN_is_bit_set(p, wstart) == 0) {
+ if (!start)
+ if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx))
+ goto err;
+ if (wstart == 0)
+ break;
+ wstart--;
+ continue;
+ }
+ /*
+ * We now have wstart on a 'set' bit, we now need to work out how bit
+ * a window to do. To do this we need to scan forward until the last
+ * set bit before the end of the window
+ */
+ j = wstart;
+ wvalue = 1;
+ wend = 0;
+ for (i = 1; i < window; i++) {
+ if (wstart - i < 0)
+ break;
+ if (BN_is_bit_set(p, wstart - i)) {
+ wvalue <<= (i - wend);
+ wvalue |= 1;
+ wend = i;
+ }
+ }
+
+ /* wend is the size of the current window */
+ j = wend + 1;
+ /* add the 'bytes above' */
+ if (!start)
+ for (i = 0; i < j; i++) {
+ if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx))
+ goto err;
+ }
+
+ /* wvalue will be an odd number < 2^window */
+ if (!BN_mod_mul_reciprocal(r, r, val[wvalue >> 1], &recp, ctx))
+ goto err;
+
+ /* move the 'window' down further */
+ wstart -= wend + 1;
+ wvalue = 0;
+ start = 0;
+ if (wstart < 0)
+ break;
+ }
+ ret = 1;
+ err:
+ BN_CTX_end(ctx);
+ BN_RECP_CTX_free(&recp);
+ bn_check_top(r);
+ return (ret);
+}
+
+int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
+ const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
+{
+ int i, j, bits, ret = 0, wstart, wend, window, wvalue;
+ int start = 1;
+ BIGNUM *d, *r;
+ const BIGNUM *aa;
+ /* Table of variables obtained from 'ctx' */
+ BIGNUM *val[TABLE_SIZE];
+ BN_MONT_CTX *mont = NULL;
+
+ if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) {
+ return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont);
+ }
+
+ bn_check_top(a);
+ bn_check_top(p);
+ bn_check_top(m);
+
+ if (!BN_is_odd(m)) {
+ BNerr(BN_F_BN_MOD_EXP_MONT, BN_R_CALLED_WITH_EVEN_MODULUS);
+ return (0);
+ }
+ bits = BN_num_bits(p);
+ if (bits == 0) {
+ ret = BN_one(rr);
+ return ret;
+ }
+
+ BN_CTX_start(ctx);
+ d = BN_CTX_get(ctx);
+ r = BN_CTX_get(ctx);
+ val[0] = BN_CTX_get(ctx);
+ if (!d || !r || !val[0])
+ goto err;
+
+ /*
+ * If this is not done, things will break in the montgomery part
+ */
+
+ if (in_mont != NULL)
+ mont = in_mont;
+ else {
+ if ((mont = BN_MONT_CTX_new()) == NULL)
+ goto err;
+ if (!BN_MONT_CTX_set(mont, m, ctx))
+ goto err;
+ }
+
+ if (a->neg || BN_ucmp(a, m) >= 0) {
+ if (!BN_nnmod(val[0], a, m, ctx))
+ goto err;
+ aa = val[0];
+ } else
+ aa = a;
+ if (BN_is_zero(aa)) {
+ BN_zero(rr);
+ ret = 1;
+ goto err;
+ }
+ if (!BN_to_montgomery(val[0], aa, mont, ctx))
+ goto err; /* 1 */
+
+ window = BN_window_bits_for_exponent_size(bits);
+ if (window > 1) {
+ if (!BN_mod_mul_montgomery(d, val[0], val[0], mont, ctx))
+ goto err; /* 2 */
+ j = 1 << (window - 1);
+ for (i = 1; i < j; i++) {
+ if (((val[i] = BN_CTX_get(ctx)) == NULL) ||
+ !BN_mod_mul_montgomery(val[i], val[i - 1], d, mont, ctx))
+ goto err;
+ }
+ }
+
+ start = 1; /* This is used to avoid multiplication etc
+ * when there is only the value '1' in the
+ * buffer. */
+ wvalue = 0; /* The 'value' of the window */
+ wstart = bits - 1; /* The top bit of the window */
+ wend = 0; /* The bottom bit of the window */
+
+#if 1 /* by Shay Gueron's suggestion */
+ j = m->top; /* borrow j */
+ if (m->d[j - 1] & (((BN_ULONG)1) << (BN_BITS2 - 1))) {
+ if (bn_wexpand(r, j) == NULL)
+ goto err;
+ /* 2^(top*BN_BITS2) - m */
+ r->d[0] = (0 - m->d[0]) & BN_MASK2;
+ for (i = 1; i < j; i++)
+ r->d[i] = (~m->d[i]) & BN_MASK2;
+ r->top = j;
+ /*
+ * Upper words will be zero if the corresponding words of 'm' were
+ * 0xfff[...], so decrement r->top accordingly.
+ */
+ bn_correct_top(r);
+ } else
+#endif
+ if (!BN_to_montgomery(r, BN_value_one(), mont, ctx))
+ goto err;
+ for (;;) {
+ if (BN_is_bit_set(p, wstart) == 0) {
+ if (!start) {
+ if (!BN_mod_mul_montgomery(r, r, r, mont, ctx))
+ goto err;
+ }
+ if (wstart == 0)
+ break;
+ wstart--;
+ continue;
+ }
+ /*
+ * We now have wstart on a 'set' bit, we now need to work out how bit
+ * a window to do. To do this we need to scan forward until the last
+ * set bit before the end of the window
+ */
+ j = wstart;
+ wvalue = 1;
+ wend = 0;
+ for (i = 1; i < window; i++) {
+ if (wstart - i < 0)
+ break;
+ if (BN_is_bit_set(p, wstart - i)) {
+ wvalue <<= (i - wend);
+ wvalue |= 1;
+ wend = i;
+ }
+ }
+
+ /* wend is the size of the current window */
+ j = wend + 1;
+ /* add the 'bytes above' */
+ if (!start)
+ for (i = 0; i < j; i++) {
+ if (!BN_mod_mul_montgomery(r, r, r, mont, ctx))
+ goto err;
+ }
+
+ /* wvalue will be an odd number < 2^window */
+ if (!BN_mod_mul_montgomery(r, r, val[wvalue >> 1], mont, ctx))
+ goto err;
+
+ /* move the 'window' down further */
+ wstart -= wend + 1;
+ wvalue = 0;
+ start = 0;
+ if (wstart < 0)
+ break;
+ }
+#if defined(SPARC_T4_MONT)
+ if (OPENSSL_sparcv9cap_P[0] & (SPARCV9_VIS3 | SPARCV9_PREFER_FPU)) {
+ j = mont->N.top; /* borrow j */
+ val[0]->d[0] = 1; /* borrow val[0] */
+ for (i = 1; i < j; i++)
+ val[0]->d[i] = 0;
+ val[0]->top = j;
+ if (!BN_mod_mul_montgomery(rr, r, val[0], mont, ctx))
+ goto err;
+ } else
+#endif
+ if (!BN_from_montgomery(rr, r, mont, ctx))
+ goto err;
+ ret = 1;
+ err:
+ if (in_mont == NULL)
+ BN_MONT_CTX_free(mont);
+ BN_CTX_end(ctx);
+ bn_check_top(rr);
+ return (ret);
+}
+
+#if defined(SPARC_T4_MONT)
+static BN_ULONG bn_get_bits(const BIGNUM *a, int bitpos)
+{
+ BN_ULONG ret = 0;
+ int wordpos;
+
+ wordpos = bitpos / BN_BITS2;
+ bitpos %= BN_BITS2;
+ if (wordpos >= 0 && wordpos < a->top) {
+ ret = a->d[wordpos] & BN_MASK2;
+ if (bitpos) {
+ ret >>= bitpos;
+ if (++wordpos < a->top)
+ ret |= a->d[wordpos] << (BN_BITS2 - bitpos);
+ }
+ }
+
+ return ret & BN_MASK2;
+}
+#endif