bndsaprime.c

著名的加密软件的应用于电子邮件中

/*
* 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(struct BigNum *bnq, struct BigNum *bnp,
			int (*f)(void *arg, int c), void *arg)
	{
			int retval;
			unsigned p, prev;
			struct 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;
	}