bn_exp.c

LINUX AU12XX BOOTLADER

	j = 1 << (window - 1);
	for (i = 1; i < j; i++) {
	    BN_init(&val[i]);
	    if (!BN_mod_mul_reciprocal
		(&(val[i]), &(val[i - 1]), aa, &recp, ctx))
		goto err;
	}
	ts = i;
    }

    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);
    for (i = 0; i < ts; i++)
	BN_clear_free(&(val[i]));
    BN_RECP_CTX_free(&recp);
    return (ret);
}


int BN_mod_exp_mont(BIGNUM * rr, 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, ts = 0;
    BIGNUM *d, *r;
    BIGNUM *aa;
    BN_MONT_CTX *mont = NULL;

#ifdef ORIGINAL_SSL_CODE
    BIGNUM val[TABLE_SIZE];
#else
    BIGNUM *val =
	(BIGNUM *) sps_dve_get_valbuf(sizeof(BIGNUM) * TABLE_SIZE);
#endif

    bn_check_top(a);
    bn_check_top(p);
    bn_check_top(m);

#ifdef ATALLA
    if (!tried_atalla && BN_mod_exp_atalla(rr, a, p, m))
	return 1;
/* If it fails, try the other methods */
#endif

    if (!(m->d[0] & 1)) {
	BNerr(BN_F_BN_MOD_EXP_MONT, BN_R_CALLED_WITH_EVEN_MODULUS);
	return (0);
    }
    bits = BN_num_bits(p);
    if (bits == 0) {
	BN_one(rr);
	return (1);
    }
    BN_CTX_start(ctx);
    d = BN_CTX_get(ctx);
    r = BN_CTX_get(ctx);
    if (d == NULL || r == NULL)
	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;
    }

    BN_init(&val[0]);
    ts = 1;
    if (BN_ucmp(a, m) >= 0) {
	if (!BN_mod(&(val[0]), a, m, ctx))
	    goto err;
	aa = &(val[0]);
    } else
	aa = a;
    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++) {
	    BN_init(&(val[i]));
	    if (!BN_mod_mul_montgomery
		(&(val[i]), &(val[i - 1]), d, mont, ctx))
		goto err;
	}
	ts = i;
    }

    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_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 (!BN_from_montgomery(rr, r, mont, ctx))
	goto err;
    ret = 1;
  err:
    if ((in_mont == NULL) && (mont != NULL))
	BN_MONT_CTX_free(mont);
    BN_CTX_end(ctx);
    for (i = 0; i < ts; i++)
	BN_clear_free(&(val[i]));
    return (ret);
}

int BN_mod_exp_mont_word(BIGNUM * rr, BN_ULONG a, const BIGNUM * p,
			 const BIGNUM * m, BN_CTX * ctx,
			 BN_MONT_CTX * in_mont)
{
    BN_MONT_CTX *mont = NULL;
    int b, bits, ret = 0;
    int r_is_one;
    BN_ULONG w, next_w;
    BIGNUM *d, *r, *t;
    BIGNUM *swap_tmp;
#define BN_MOD_MUL_WORD(r, w, m) \
		(BN_mul_word(r, (w)) && \
		(/* BN_ucmp(r, (m)) < 0 ? 1 :*/  \
			(BN_mod(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1))))
    /* BN_MOD_MUL_WORD is only used with 'w' large,
     * so the BN_ucmp test is probably more overhead
     * than always using BN_mod (which uses BN_copy if
     * a similar test returns true). */
#define BN_TO_MONTGOMERY_WORD(r, w, mont) \
		(BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx))

    bn_check_top(p);
    bn_check_top(m);

    if (!(m->d[0] & 1)) {
	BNerr(BN_F_BN_MOD_EXP_MONT_WORD, BN_R_CALLED_WITH_EVEN_MODULUS);
	return (0);
    }
    bits = BN_num_bits(p);
    if (bits == 0) {
	BN_one(rr);
	return (1);
    }
    BN_CTX_start(ctx);
    d = BN_CTX_get(ctx);
    r = BN_CTX_get(ctx);
    t = BN_CTX_get(ctx);
    if (d == NULL || r == NULL || t == NULL)
	goto err;

#ifdef ATALLA
    if (!tried_atalla) {
	BN_set_word(t, a);
	if (BN_mod_exp_atalla(rr, t, p, m)) {
	    BN_CTX_end(ctx);
	    return 1;
	}
    }
/* If it fails, try the other methods */
#endif

    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;
    }

    r_is_one = 1;		/* except for Montgomery factor */

    /* bits-1 >= 0 */

    /* The result is accumulated in the product r*w. */
    w = a;			/* bit 'bits-1' of 'p' is always set */
    for (b = bits - 2; b >= 0; b--) {
	/* First, square r*w. */
	next_w = w * w;
	if ((next_w / w) != w) {	/* overflow */
	    if (r_is_one) {
		if (!BN_TO_MONTGOMERY_WORD(r, w, mont))
		    goto err;
		r_is_one = 0;
	    } else {
		if (!BN_MOD_MUL_WORD(r, w, m))
		    goto err;
	    }
	    next_w = 1;
	}
	w = next_w;
	if (!r_is_one) {
	    if (!BN_mod_mul_montgomery(r, r, r, mont, ctx))
		goto err;
	}

	/* Second, multiply r*w by 'a' if exponent bit is set. */
	if (BN_is_bit_set(p, b)) {
	    next_w = w * a;
	    if ((next_w / a) != w) {	/* overflow */
		if (r_is_one) {
		    if (!BN_TO_MONTGOMERY_WORD(r, w, mont))
			goto err;
		    r_is_one = 0;
		} else {
		    if (!BN_MOD_MUL_WORD(r, w, m))
			goto err;
		}
		next_w = a;
	    }
	    w = next_w;
	}
    }

    /* Finally, set r:=r*w. */
    if (w != 1) {
	if (r_is_one) {
	    if (!BN_TO_MONTGOMERY_WORD(r, w, mont))
		goto err;
	    r_is_one = 0;
	} else {
	    if (!BN_MOD_MUL_WORD(r, w, m))
		goto err;
	}
    }

    if (r_is_one) {		/* can happen only if a == 1 */
	if (!BN_one(rr))
	    goto err;
    } else {
	if (!BN_from_montgomery(rr, r, mont, ctx))
	    goto err;
    }
    ret = 1;
  err:
    if ((in_mont == NULL) && (mont != NULL))
	BN_MONT_CTX_free(mont);
    BN_CTX_end(ctx);
    return (ret);
}


/* The old fallback, simple version :-) */
int BN_mod_exp_simple(BIGNUM * r, BIGNUM * a, BIGNUM * p, BIGNUM * m,
		      BN_CTX * ctx)
{
    int i, j, bits, ret = 0, wstart, wend, window, wvalue, ts = 0;
    int start = 1;
    BIGNUM *d;

#ifdef ORIGINAL_SSL_CODE
    BIGNUM val[TABLE_SIZE];
#else
    BIGNUM *val =
	(BIGNUM *) sps_dve_get_valbuf(sizeof(BIGNUM) * TABLE_SIZE);
#endif

    bits = BN_num_bits(p);

    if (bits == 0) {
	BN_one(r);
	return (1);
    }

    BN_CTX_start(ctx);
    if ((d = BN_CTX_get(ctx)) == NULL)
	goto err;

    BN_init(&(val[0]));
    ts = 1;
    if (!BN_mod(&(val[0]), a, m, ctx))
	goto err;		/* 1 */

    window = BN_window_bits_for_exponent_size(bits);
    if (window > 1) {
	if (!BN_mod_mul(d, &(val[0]), &(val[0]), m, ctx))
	    goto err;		/* 2 */
	j = 1 << (window - 1);
	for (i = 1; i < j; i++) {
	    BN_init(&(val[i]));
	    if (!BN_mod_mul(&(val[i]), &(val[i - 1]), d, m, ctx))
		goto err;
	}
	ts = i;
    }

    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(r, r, r, m, 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(r, r, r, m, ctx))
		    goto err;
	    }

	/* wvalue will be an odd number < 2^window */
	if (!BN_mod_mul(r, r, &(val[wvalue >> 1]), m, 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);
    for (i = 0; i < ts; i++)
	BN_clear_free(&(val[i]));
    return (ret);
}