bigint.c

iscsi源代码 UNH的progect 有initiator端和target端的源码

	int res;

#ifdef BIGINT_DEBUG
	if ((!bigint_check(r)) ||
	    (!bigint_check(a)) || (!bigint_check(b)) || (!bigint_check(m)))
		return 0;
#endif

	if (IS_ZERO(m) || IS_ZERO(a))
		return 0;
	if (IS_ONE(m)) {
		if (!bigint_extend(r, 1))
			return 0;
		SET_ZERO(r);
		return 1;
	}
	if (IS_ZERO(b)) {
		if (!bigint_extend(r, 1))
			return 0;
		SET_ONE(r);
	}
	if (!bigint_init(&ret, 0))
		return 0;
	memset(buffer, 0, BIGINT_TABLE_SIZE * sizeof (struct bigint_t));
	if (!bigint_init(&buffer[0], 0)) {
		res = 0;
		goto end;
	}
	if (!bigint_mod(&buffer[0], a, m)) {
		res = 0;
		goto end;
	}
	if (IS_ZERO(&buffer[0])) {
		if (!bigint_extend(r, 1)) {
			res = 0;
			goto end;
		}
		SET_ZERO(r);
		res = 1;
		goto end;
	}
	if (!bigint_init(&tmp, 0)) {
		res = 0;
		goto end;
	}
	SET_ONE(&ret);
	for (i = b->offset - 1; i >= 0; i--) {
		window = (unsigned char) ((b->data[i] & 0xFF000000) >> 24);
		// printk("step 1\n");
		if (window) {
			window--;
			if (!calculate_seed(window, buffer, m)) {
				res = 0;
				goto end;
			}
			if (!bigint_cpy(&tmp, &buffer[window])) {
				res = 0;
				goto end;
			}
			for (j = 0; j < 24 + i * 32; j++) {
				if (!bigint_mod_mul(&tmp, &tmp, &tmp, m)) {
					res = 0;
					goto end;
				}
			}
			if (!bigint_mod_mul(&ret, &ret, &tmp, m)) {
				res = 0;
				goto end;
			}
		}
		window = (unsigned char) ((b->data[i] & 0x00FF0000) >> 16);
		// printk("step 2\n");
		if (window) {
			window--;
			if (!calculate_seed(window, buffer, m)) {
				res = 0;
				goto end;
			}
			if (!bigint_cpy(&tmp, &buffer[window])) {
				res = 0;
				goto end;
			}
			for (j = 0; j < 16 + i * 32; j++) {
				if (!bigint_mod_mul(&tmp, &tmp, &tmp, m)) {
					res = 0;
					goto end;
				}
			}
			if (!bigint_mod_mul(&ret, &ret, &tmp, m)) {
				res = 0;
				goto end;
			}
		}
		window = (unsigned char) ((b->data[i] & 0x0000FF00) >> 8);
		// printk("step 3\n");
		if (window) {
			window--;
			if (!calculate_seed(window, buffer, m)) {
				res = 0;
				goto end;
			}
			if (!bigint_cpy(&tmp, &buffer[window])) {
				res = 0;
				goto end;
			}
			for (j = 0; j < 8 + i * 32; j++) {
				if (!bigint_mod_mul(&tmp, &tmp, &tmp, m)) {
					res = 0;
					goto end;
				}
			}
			if (!bigint_mod_mul(&ret, &ret, &tmp, m)) {
				res = 0;
				goto end;
			}
		}
		window = (unsigned char) (b->data[i] & 0x000000FF);
		// printk("step 4\n");
		if (window) {
			window--;
			if (!calculate_seed(window, buffer, m)) {
				res = 0;
				goto end;
			}
			if (!bigint_cpy(&tmp, &buffer[window])) {
				res = 0;
				goto end;
			}
			for (j = 0; j < i * 32; j++) {
				if (!bigint_mod_mul(&tmp, &tmp, &tmp, m)) {
					res = 0;
					goto end;
				}
			}
			if (!bigint_mod_mul(&ret, &ret, &tmp, m)) {
				res = 0;
				goto end;
			}
		}
	}
	res = 1;
      end:
	bigint_trim(&ret);
	if (!bigint_cpy(r, &ret))
		res = 0;
	for (i = 0; i < BIGINT_TABLE_SIZE; i++)
		bigint_clean(&buffer[i]);
	bigint_clean(&tmp);
	bigint_clean(&ret);
	return res;
}

/* montgomerty algorithm functions */

int
bigint_product_mont(struct bigint_t *x,
		    const struct bigint_t *a,
		    const struct bigint_t *b,
		    const struct bigint_t *np,
		    const struct bigint_t *n, const unsigned int r)
{
	struct bigint_t t;
	struct bigint_t m;
	struct bigint_t tmp;

	int ret;

#ifdef BIGINT_DEBUG
	if ((!bigint_check(x)) ||
	    (!bigint_check(a)) ||
	    (!bigint_check(b)) || (!bigint_check(np)) || (!bigint_check(n)))
		return 0;
#endif

	ret = 0;
	if (!bigint_init(&t, 0))
		goto out;

	if (!bigint_init(&m, 0))
		goto out;

	if (!bigint_init(&tmp, 0))
		goto out;

	if (!bigint_mul(&t, a, b))
		goto out;

	if (!bigint_mul(&m, &t, np))
		goto out;

	if (!bigint_chop(&m, r))
		goto out;

	if (!bigint_mul(&tmp, &m, n))
		goto out;

	if (!bigint_add(&tmp, &t, &tmp))
		goto out;

	if (!bigint_rsh(&tmp, &tmp, r))
		goto out;

	if (bigint_cmp(&tmp, n) > 0) {
		if (!bigint_sub(&tmp, &tmp, n))
			goto out;
	}

	if (!bigint_cpy(x, &tmp))
		goto out;

	ret = 1;
      out:
	bigint_clean(&t);
	bigint_clean(&m);
	bigint_clean(&tmp);
	return ret;
}

int
bigint_getbit(const struct bigint_t *n, const unsigned int offset)
{
	unsigned int na;
	unsigned int nb;

	na = offset / (8 * sizeof (unsigned int));
	nb = offset % (8 * sizeof (unsigned int));

	if (na + 1 > n->offset)
		return 0;
	else
		return ((n->data[na] & (1 << nb)) == 0) ? 0 : 1;
}

int
bigint_mod_exp_mont(struct bigint_t *r,
		    const struct bigint_t *a,
		    const struct bigint_t *b, const struct bigint_t *m)
{
	int ret;
	struct bigint_t ap;
	struct bigint_t xp;
	struct bigint_t np;
	struct bigint_t tmp;
	struct bigint_t one;
	unsigned int k;
	int i;

#ifdef BIGINT_DEBUG
	if ((!bigint_check(r)) ||
	    (!bigint_check(a)) || (!bigint_check(b)) || (!bigint_check(m)))
		return 0;
#endif
	ret = 0;
	if (!bigint_init(&ap, 0))
		goto out;

	if (!bigint_init(&xp, 0))
		goto out;

	if (!bigint_init(&np, 0))
		goto out;

	if (!bigint_init(&tmp, 0))
		goto out;

	if (!bigint_init(&one, 0))
		goto out;

	SET_ONE(&one);

	if (!bigint_round_mont(&k, m))
		goto out;

	if (!bigint_eea_mont(&np, m, k))
		goto out;

	if (!bigint_lsh(&tmp, a, k))
		goto out;

	if (!bigint_mod(&ap, &tmp, m))
		goto out;

	if (!bigint_lsh(&tmp, &one, k))
		goto out;

	if (!bigint_mod(&xp, &tmp, m))
		goto out;

	for (i = k - 1; i >= 0; i--) {
		if (!bigint_product_mont(&xp, &xp, &xp, &np, m, k))
			goto out;
		if (bigint_getbit(b, i)) {
			if (!bigint_product_mont(&xp, &ap, &xp, &np, m, k))
				goto out;
		}
	}
	if (!bigint_product_mont(r, &xp, &one, &np, m, k))
		goto out;
	ret = 1;
      out:
	bigint_clean(&ap);
	bigint_clean(&xp);
	bigint_clean(&np);
	bigint_clean(&tmp);
	bigint_clean(&one);
	return ret;
}

int
bigint_round_mont(unsigned int *r, const struct bigint_t *a)
{
#ifdef BIGINT_DEBUG
	if (!bigint_check(a))
		return 0;
#endif
	*r = bigint_bits(a);
	return 1;
}

int
bigint_mod_mul_mont(struct bigint_t *r,
		    const struct bigint_t *a,
		    const struct bigint_t *b, const struct bigint_t *m)
{
	int ret;
	struct bigint_t ap;
	struct bigint_t bp;
	struct bigint_t np;
	struct bigint_t tmp;
	struct bigint_t one;
	unsigned int k;

#ifdef BIGINT_DEBUG
	if ((!bigint_check(r)) ||
	    (!bigint_check(a)) || (!bigint_check(b)) || (!bigint_check(m)))
		return 0;
#endif

	ret = 0;

	if (!bigint_init(&ap, 0))
		goto out;

	if (!bigint_init(&bp, 0))
		goto out;

	if (!bigint_init(&np, 0))
		goto out;

	if (!bigint_init(&tmp, 0))
		goto out;

	if (!bigint_init(&one, 0))
		goto out;

	SET_ONE(&one);

	if (!bigint_round_mont(&k, m))
		goto out;

	if (!bigint_eea_mont(&np, m, k))
		goto out;

	if (!bigint_lsh(&tmp, a, k))
		goto out;

	if (!bigint_mod(&ap, &tmp, m))
		goto out;

	if (!bigint_lsh(&tmp, b, k))
		goto out;

	if (!bigint_mod(&bp, &tmp, m))
		goto out;

	if (!bigint_product_mont(r, &ap, &bp, &np, m, k))
		goto out;

	if (!bigint_product_mont(r, r, &one, &np, m, k))
		goto out;

	ret = 1;
      out:
	bigint_clean(&ap);
	bigint_clean(&bp);
	bigint_clean(&np);
	bigint_clean(&tmp);
	return ret;
}

int
bigint_eea_mont(struct bigint_t *np,
		const struct bigint_t *n, const unsigned int k)
{
	int ret;
	struct bigint_t y1;
	struct bigint_t y2;
	struct bigint_t y;
	struct bigint_t q;
	struct bigint_t a;
	struct bigint_t aa;
	struct bigint_t b;
	struct bigint_t tmp;
	struct bigint_t r;

#ifdef BIGINT_DEBUG
	if ((!bigint_check(np)) || (!bigint_check(n)))
		return 0;
#endif

	ret = 0;

	if (IS_ZERO(n))
		return 0;

	if (!bigint_init(&y1, 0))
		goto out;

	if (!bigint_init(&y2, 0))
		goto out;

	if (!bigint_init(&y, 0))
		goto out;

	if (!bigint_init(&q, 0))
		goto out;

	if (!bigint_init(&a, 0))
		goto out;

	if (!bigint_init(&b, 0))
		goto out;

	if (!bigint_init(&aa, 0))
		goto out;

	if (!bigint_init(&tmp, 0))
		goto out;

	if (!bigint_init(&r, 0))
		goto out;

	SET_ONE(&a);

	if (!bigint_lsh(&a, &a, k))
		goto out;

	if (!bigint_cpy(&aa, &a))
		goto out;

	if (!bigint_cpy(&b, n))
		goto out;

	SET_ZERO(&y2);
	SET_ONE(&y1);

	while ((!IS_ZERO(&b)) && (!IS_NEGATIVE(&b))) {
		if (!bigint_div(&q, &a, &b))
			goto out;

		if (!bigint_mod(&r, &a, &b))
			goto out;

		if (!bigint_mul(&tmp, &q, &y1))
			goto out;

		if (!bigint_sub(&y, &y2, &tmp))
			goto out;

		if (!bigint_cpy(&a, &b))
			goto out;

		if (!bigint_cpy(&b, &r))
			goto out;

		if (!bigint_cpy(&y2, &y1))
			goto out;

		if (!bigint_cpy(&y1, &y))
			goto out;

		bigint_trim(&b);
	}

	if (!IS_ONE(&a))
		goto out;

	if (IS_NEGATIVE(&y2))
		SET_POSITIVE(&y2);
	else {
		SET_NEGATIVE(&y2);
		if (!bigint_fix(&y2, &aa))
			goto out;
	}
	if (!bigint_cpy(np, &y2))
		goto out;
	ret = 1;
      out:
	bigint_clean(&y1);
	bigint_clean(&y2);
	bigint_clean(&y);
	bigint_clean(&q);
	bigint_clean(&a);
	bigint_clean(&b);
	bigint_clean(&aa);
	bigint_clean(&tmp);
	bigint_clean(&r);
	return ret;
}

int
bigint_div_mont(struct bigint_t *r,
		const struct bigint_t *a, const unsigned int b)
{
#ifdef BIGINT_DEBUG
	if ((!bigint_check(r)) || (!bigint_check(a)))
		return 0;
#endif

	if (b == 0)
		return bigint_cpy(r, a);

	if (!bigint_rsh(r, a, b))
		return 0;

	bigint_trim(r);
	return 1;
}

int
bigint_mod_mont(struct bigint_t *r,
		const struct bigint_t *a, const unsigned int b)
{
	int ret;
	struct bigint_t tmp;

#ifdef BIGINT_DEBUG
	if ((!bigint_check(r)) || (!bigint_check(a)))
		return 0;
#endif

	ret = 0;
	if (b == 0) {
		if (!bigint_extend(r, 0))
			return 0;
		SET_ZERO(r);
		return 1;
	}
	if (!bigint_init(&tmp, 0))
		return 0;

	if (!bigint_cpy(&tmp, a))
		goto out;

	if (!bigint_chop(&tmp, b))
		goto out;

	if (!bigint_cpy(r, &tmp))
		goto out;

	bigint_trim(r);
	ret = 1;
      out:
	bigint_clean(&tmp);
	return ret;
}