bndsaprime.c

vc环境下的pgp源码

	 * Now, e = (bn-1)/2^k is odd.  k >= 1, and has a given value
	 * with probability 2^-k, so its expected value is 2.
	 * j = 1 in the usual case when the previous test was as good as
	 * a strong prime test, but 1/8 of the time, j = 0 because
	 * the strong prime test to the base 2 needs to be re-done.
	 */
	for (i = j; i < sizeof(primes)/sizeof(*primes); i++) {
		if (f && (err = f(arg, '*')) < 0)
			return err;
		(void)bnSetQ(a, primes[i]);
		if (bnExpMod(a, a, e, bn) < 0)
			return -1;
		if (bnBits(a) == 1)
			continue;	/* Passed this test */

		l = k;
		for (;;) {
			if (bnAddQ(a, 1) < 0)
				return -1;
			if (bnCmp(a, bn) == 0)	/* Was result bn-1? */
				break;	/* Prime */
			if (!--l)	/* Reached end, not -1? luck? */
				return i+2-j;	/* Failed, not prime */
			/* This portion is executed, on average, once. */
			(void)bnSubQ(a, 1);	/* Put a back where it was. */
			if (bnSquare(a, a) < 0 || bnMod(a, a, bn) < 0)
				return -1;
			if (bnBits(a) == 1)
				return i+2-j;	/* Failed, not prime */
		}
		/* It worked (to the base primes[i]) */
	}
	
	/* Yes, we've decided that it's prime. */
	if (f && (err = f(arg, '*')) < 0)
		return err;

	return 0;	/* Prime! */
}

/*
 * Modifies the given bnq to return a prime slightly larger, and then
 * modifies the given bnp to be a prime which is == 1 (mod bnq).
 * This is done by decreasing bnp until it is == 1 (mod 2*bnq), and
 * then searching forward in steps of 2*bnq.
 * Returns >=0 on success or -1 on failure (out of memory).  On
 * success, the return value is the number of modular exponentiations
 * performed (excluding the final confirmation).
 * This never gives up searching.
 *
 * int (*f)(void *arg, int c), void *arg
 * The function f argument, if non-NULL, is called with progress indicator
 * characters for printing.  A dot (.) is written every time a primality test
 * is failed, a star (*) every time one is passed, and a slash (/) in the
 * case that the sieve was emptied without finding a prime and is being
 * refilled.  f is also passed the void *arg argument for private
 * context storage.  If f returns < 0, the test aborts and returns
 * that value immediately.
 *
 * Apologies to structured programmers for all the GOTOs.
 */
int
dsaPrimeGen(BigNum *bnq, BigNum *bnp,
	int (*f)(void *arg, int c), void *arg)
{
	int retval;
	unsigned p, prev;
	BigNum a, e;
	int modexps = 0;
#ifdef MSDOS
	unsigned char *sieve;
#else
	unsigned char sieve[SIEVE];
#endif

#ifdef MSDOS
	sieve = bniMemAlloc(SIEVE);
	if (!sieve)
		return -1;
#endif

	bnBegin(&a);
	bnBegin(&e);

	/* Phase 1: Search forwards from bnq for a suitable prime. */

	/* First, make sure that bnq is odd. */
	(void)bnAddQ(bnq, ~bnLSWord(bnq) & 1);

	for (;;) {
		if (sieveBuild(sieve, SIEVE, bnq, 2, 1) < 0)
			goto failed;

		p = prev = 0;
		if (sieve[0] & 1 || (p = sieveSearch(sieve, SIEVE, p)) != 0) {
			do {
				/*
				 * Adjust bn to have the right value,
				 * incrementing in steps of < 65536.
				 * 32767 = 65535/2.
				 */
				pgpAssert(p >= prev);
				prev = p-prev;	/* Delta - add 2*prev to bn */
#if SIEVE*8*2 >= 65536
				while (prev > 32767) {
					if (bnAddQ(bnq, 2*32767) < 0)
						goto failed;
					prev -= 32767;
				}
#endif
				if (bnAddQ(bnq, 2*prev) < 0)
					goto failed;
				prev = p;

				retval = primeTest(bnq, &e, &a, f, arg);
				if (retval <= 0)
					goto phase2;	/* Success! */
				modexps += retval;
				if (f && (retval = f(arg, '.')) < 0)
					goto done;

				/* And try again */
				p = sieveSearch(sieve, SIEVE, p);
			} while (p);
		}

		/* Ran out of sieve space - increase bn and keep trying. */
#if SIEVE*8*2 >= 65536
		p = ((SIEVE-1)*8+7) - prev;	/* Number of steps (of 2) */
		while (p >= 32737) {
			if (bnAddQ(bnq, 2*32767) < 0)
				goto failed;
			p -= 32767;
		}
		if (bnAddQ(bnq, 2*(p+1)) < 0)
			goto failed;
#else
		if (bnAddQ(bnq, SIEVE*8*2 - prev) < 0)
			goto failed;
#endif
		if (f && (retval = f(arg, '/')) < 0)
			goto done;
	} /* for (;;) */

	/*
	 * Phase 2: find a suitable prime bnp == 1 (mod bnq).
	 */

	/*
	 * Since bnp will be, and bnq is, odd, bnp-1 must be a multiple
	 * of 2*bnq.  So start by subtracting the excess.
	 */

phase2:
	/* Double bnq until end of bnp search. */
	if (bnAdd(bnq, bnq) < 0)
		goto failed;

	bnMod(&a, bnp, bnq);
	if (bnBits(&a)) {	/* Will always be true, but... */
		(void)bnSubQ(&a, 1);
		if (bnSub(bnp, &a)) 	/* Also error on underflow */
			goto failed;
	}

	/* Okay, now we're ready. */

	for (;;) {
		if (sieveBuildBig(sieve, SIEVE, bnp, bnq, 0) < 0)
			goto failed;
		if (f && (retval = f(arg, '/')) < 0)
			goto done;

		p = prev = 0;
		if (sieve[0] & 1 || (p = sieveSearch(sieve, SIEVE, p)) != 0) {
			do {
				/*
				 * Adjust bn to have the right value,
				 * adding (p-prev) * 2*bnq.
				 */
				pgpAssert(p >= prev);
				/* Compute delta into a */
				if (bnMulQ(&a, bnq, p-prev) < 0)
					goto failed;
				if (bnAdd(bnp, &a) < 0)
					goto failed;
				prev = p;

				retval = primeTest(bnp, &e, &a, f, arg);
				if (retval <= 0)
					goto done;	/* Success! */
				modexps += retval;
				if (f && (retval = f(arg, '.')) < 0)
					goto done;

				/* And try again */
				p = sieveSearch(sieve, SIEVE, p);
			} while (p);
		}

		/* Ran out of sieve space - increase bn and keep trying. */
#if SIEVE*8 == 65536
		if (prev) {
			p = (unsigned)(SIEVE*8ul - prev);
		} else {
			/* Corner case that will never actually happen */
			if (bnAdd(bnp, bnq) < 0)
				goto failed;
			p = 65535;
		}
#else
		p = SIEVE*8 - prev;
#endif
		/* Add p * bnq to bnp */
		if (bnMulQ(&a, bnq, p) < 0)
			goto failed;
		if (bnAdd(bnp, &a) < 0)
			goto failed;
	} /* for (;;) */

failed:
	retval = -1;

done:
	/* Shift bnq back down by the extra bit again. */
	bnRShift(bnq, 1);	/* Harmless even if bnq is random */

	bnEnd(&e);
	bnEnd(&a);
#ifdef MSDOS
	bniMemFree(sieve, SIEVE);
#else
	bniMemWipe(sieve, sizeof(sieve));
#endif
	return retval < 0 ? retval : modexps + 2*CONFIRMTESTS;
}