+ /* 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) {
+ /* x**0 mod 1 is still zero. */
+ if (BN_is_one(m)) {
+ ret = 1;
+ BN_zero(rr);
+ } else {
+ 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
+
+/*
+ * BN_mod_exp_mont_consttime() stores the precomputed powers in a specific
+ * layout so that accessing any of these table values shows the same access
+ * pattern as far as cache lines are concerned. The following functions are
+ * used to transfer a BIGNUM from/to that table.
+ */
+
+static int MOD_EXP_CTIME_COPY_TO_PREBUF(const BIGNUM *b, int top,
+ unsigned char *buf, int idx,
+ int window)
+{
+ int i, j;
+ int width = 1 << window;
+ BN_ULONG *table = (BN_ULONG *)buf;
+
+ if (top > b->top)
+ top = b->top; /* this works because 'buf' is explicitly
+ * zeroed */
+ for (i = 0, j = idx; i < top; i++, j += width) {
+ table[j] = b->d[i];
+ }
+
+ return 1;
+}
+
+static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top,
+ unsigned char *buf, int idx,
+ int window)
+{
+ int i, j;
+ int width = 1 << window;
+ /*
+ * We declare table 'volatile' in order to discourage compiler
+ * from reordering loads from the table. Concern is that if
+ * reordered in specific manner loads might give away the
+ * information we are trying to conceal. Some would argue that
+ * compiler can reorder them anyway, but it can as well be
+ * argued that doing so would be violation of standard...
+ */
+ volatile BN_ULONG *table = (volatile BN_ULONG *)buf;
+
+ if (bn_wexpand(b, top) == NULL)
+ return 0;
+
+ if (window <= 3) {
+ for (i = 0; i < top; i++, table += width) {
+ BN_ULONG acc = 0;
+
+ for (j = 0; j < width; j++) {
+ acc |= table[j] &
+ ((BN_ULONG)0 - (constant_time_eq_int(j,idx)&1));
+ }
+
+ b->d[i] = acc;
+ }
+ } else {
+ int xstride = 1 << (window - 2);
+ BN_ULONG y0, y1, y2, y3;
+
+ i = idx >> (window - 2); /* equivalent of idx / xstride */
+ idx &= xstride - 1; /* equivalent of idx % xstride */
+
+ y0 = (BN_ULONG)0 - (constant_time_eq_int(i,0)&1);
+ y1 = (BN_ULONG)0 - (constant_time_eq_int(i,1)&1);
+ y2 = (BN_ULONG)0 - (constant_time_eq_int(i,2)&1);
+ y3 = (BN_ULONG)0 - (constant_time_eq_int(i,3)&1);
+
+ for (i = 0; i < top; i++, table += width) {
+ BN_ULONG acc = 0;
+
+ for (j = 0; j < xstride; j++) {
+ acc |= ( (table[j + 0 * xstride] & y0) |
+ (table[j + 1 * xstride] & y1) |
+ (table[j + 2 * xstride] & y2) |
+ (table[j + 3 * xstride] & y3) )
+ & ((BN_ULONG)0 - (constant_time_eq_int(j,idx)&1));
+ }
+
+ b->d[i] = acc;
+ }
+ }
+
+ b->top = top;
+ bn_correct_top(b);
+ return 1;
+}
+
+/*
+ * Given a pointer value, compute the next address that is a cache line
+ * multiple.
+ */
+#define MOD_EXP_CTIME_ALIGN(x_) \
+ ((unsigned char*)(x_) + (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - (((size_t)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK))))