ntp-keygen.c

网络时间协议NTP 源码 版本v4.2.0b 该源码用于linux平台下

	BN_rand(k, BN_num_bits(dsa->q), -1, 0);	/* k, 0 < k < q  */
	BN_mod(k, k, dsa->q, ctx);
	BN_mod_mul(v, dsa->priv_key, r, dsa->q, ctx); /* b r mod q */
	BN_add(v, v, k);
	BN_mod(v, v, dsa->q, ctx);		/* y = k + b r mod q */
	BN_mod_exp(u, dsa->g, k, dsa->p, ctx);	/* x = g^k mod p */

	/*
	 * Alice computes g^y v^r and verifies the result is equal to x.
	 * She needs modulus p, generator g, and the public key v, as
	 * well as her original r.
	 */
	BN_mod_exp(v, dsa->g, v, dsa->p, ctx); /* g^y mod p */
	BN_mod_exp(w, dsa->pub_key, r, dsa->p, ctx); /* v^r */
	BN_mod_mul(v, w, v, dsa->p, ctx);	/* product mod p */
	temp = BN_cmp(u, v);
	fprintf(stderr,
	    "Confirm g^k = g^(k + b r) g^(q - b) r: %s\n", temp ==
	    0 ? "yes" : "no");
	BN_free(b); BN_free(r);	BN_free(k);
	BN_free(u); BN_free(v); BN_free(w); BN_CTX_free(ctx);
	if (temp != 0) {
		DSA_free(dsa);
		rval = -1;
		return (NULL);
	}

	/*
	 * Write the IFF server parameters and keys as a DSA private key
	 * encoded in PEM.
	 *
	 * p	modulus p
	 * q	modulus q
	 * g	generator g
	 * priv_key b
	 * public_key v
	 */
	str = fheader("IFFpar", trustname);
	pkey = EVP_PKEY_new();
	EVP_PKEY_assign_DSA(pkey, dsa);
	PEM_write_PrivateKey(str, pkey, passwd2 ? EVP_des_cbc() : NULL,
	    NULL, 0, NULL, passwd2);
	fclose(str);
	if (debug)
		DSA_print_fp(stdout, dsa, 0);
	fslink(id, trustname);
	return (pkey);
}


/*
 * Generate Guillou-Quisquater (GQ) parameters and keys
 *
 * The Guillou-Quisquater (GQ) identity scheme is intended for use when
 * the parameters, keys and certificates are generated by this program.
 * The scheme uses a certificate extension field do convey the public
 * key of a particular group identified by a group key known only to
 * members of the group. The scheme is self contained and independent of
 * new generations of host keys and sign keys.
 *
 * The GQ parameters hide in a RSA cuckoo structure which uses the same
 * parameters. The values are used by an identity scheme based on RSA
 * cryptography and described in Stimson p. 300 (with errors). The 512-
 * bit public modulus is n = p q, where p and q are secret large primes.
 * The TA rolls private random group key b as RSA exponent. These values
 * are known to all group members.
 *
 * When rolling new certificates, a member recomputes the private and
 * public keys. The private key u is a random roll, while the public key
 * is the inverse obscured by the group key v = (u^-1)^b. These values
 * replace the private and public keys normally generated by the RSA
 * scheme. Alice challenges Bob to confirm identity using the protocol
 * described below.
 */
EVP_PKEY *			/* RSA cuckoo nest */
gen_gqpar(
	char	*id		/* file name id */
	)
{
	EVP_PKEY *pkey;		/* private key */
	RSA	*rsa;		/* GQ parameters */
	BN_CTX	*ctx;		/* BN working space */
	FILE	*str;

	/*
	 * Generate RSA parameters for use as GQ parameters.
	 */
	fprintf(stderr,
	    "Generating GQ parameters (%d bits)...\n", modulus);
	rsa = RSA_generate_key(modulus, 3, cb, "GQ");
	fprintf(stderr, "\n");
	if (rsa == NULL) {
		fprintf(stderr, "RSA generate keys fails\n%s\n",
		    ERR_error_string(ERR_get_error(), NULL));
		rval = -1;
		return (NULL);
	}

	/*
	 * Generate the group key b, which is saved in the e member of
	 * the RSA structure. These values are distributed to all
	 * members of the group, but shielded from all other groups. We
	 * don't use all the parameters, but set the unused ones to a
	 * small number to minimize the file size.
	 */
	ctx = BN_CTX_new();
	BN_rand(rsa->e, BN_num_bits(rsa->n), -1, 0); /* b */
	BN_mod(rsa->e, rsa->e, rsa->n, ctx);
	BN_copy(rsa->d, BN_value_one());
	BN_copy(rsa->p, BN_value_one());
	BN_copy(rsa->q, BN_value_one());
	BN_copy(rsa->dmp1, BN_value_one());
	BN_copy(rsa->dmq1, BN_value_one());
	BN_copy(rsa->iqmp, BN_value_one());

	/*
	 * Write the GQ parameters as a RSA private key encoded in PEM.
	 * The public and private keys are filled in later.
	 *
	 * n	modulus n
	 * e	group key b
	 * (remaining values are not used)
	 */
	str = fheader("GQpar", trustname);
	pkey = EVP_PKEY_new();
	EVP_PKEY_assign_RSA(pkey, rsa);
	PEM_write_PrivateKey(str, pkey, passwd2 ? EVP_des_cbc() : NULL,
	    NULL, 0, NULL, passwd2);
	fclose(str);
	if (debug)
		RSA_print_fp(stdout, rsa, 0);
	fslink(id, trustname);
	return (pkey);
}


/*
 * Update Guillou-Quisquater (GQ) parameters
 */
EVP_PKEY *			/* RSA cuckoo nest */
gen_gqkey(
	char	*id,		/* file name id */
	EVP_PKEY *gqpar		/* GQ parameters */
	)
{
	EVP_PKEY *pkey;		/* private key */
	RSA	*rsa;		/* RSA parameters */
	BN_CTX	*ctx;		/* BN working space */
	BIGNUM	*u, *v, *g, *k, *r, *y; /* BN temps */
	FILE	*str;
	u_int	temp;

	/*
	 * Generate GQ keys. Note that the group key b is the e member
	 * of
	 * the GQ parameters.
	 */
	fprintf(stderr, "Updating GQ keys (%d bits)...\n", modulus);
	ctx = BN_CTX_new(); u = BN_new(); v = BN_new();
	g = BN_new(); k = BN_new(); r = BN_new(); y = BN_new();

	/*
	 * When generating his certificate, Bob rolls random private key
	 * u. 
	 */
	rsa = gqpar->pkey.rsa;
	BN_rand(u, BN_num_bits(rsa->n), -1, 0); /* u */
	BN_mod(u, u, rsa->n, ctx);
	BN_mod_inverse(v, u, rsa->n, ctx);	/* u^-1 mod n */
	BN_mod_mul(k, v, u, rsa->n, ctx);

	/*
	 * Bob computes public key v = (u^-1)^b, which is saved in an
	 * extension field on his certificate. We check that u^b v =
	 * 1 mod n.
	 */
	BN_mod_exp(v, v, rsa->e, rsa->n, ctx);
	BN_mod_exp(g, u, rsa->e, rsa->n, ctx); /* u^b */
	BN_mod_mul(g, g, v, rsa->n, ctx); /* u^b (u^-1)^b */
	temp = BN_is_one(g);
	fprintf(stderr,
	    "Confirm u^b (u^-1)^b = 1 mod n: %s\n", temp ? "yes" :
	    "no");
	if (!temp) {
		BN_free(u); BN_free(v);
		BN_free(g); BN_free(k); BN_free(r); BN_free(y);
		BN_CTX_free(ctx);
		RSA_free(rsa);
		rval = -1;
		return (NULL);
	}
	BN_copy(rsa->p, u);			/* private key */
	BN_copy(rsa->q, v);			/* public key */

	/*
	 * Here is a trial run of the protocol. First, Alice rolls
	 * random r (0 < r < n) and sends it to Bob. She needs only
	 * modulus n from the parameters.
	 */
	BN_rand(r, BN_num_bits(rsa->n), -1, 0);	/* r */
	BN_mod(r, r, rsa->n, ctx);

	/*
	 * Bob rolls random k (0 < k < n), computes y = k u^r mod n and
	 * g = k^b mod n, then sends (y, g) to Alice. He needs modulus n
	 * from the parameters and his private key u. 
	 */
	BN_rand(k, BN_num_bits(rsa->n), -1, 0);	/* k */
	BN_mod(k, k, rsa->n, ctx);
	BN_mod_exp(y, rsa->p, r, rsa->n, ctx);	/* u^r mod n */
	BN_mod_mul(y, k, y, rsa->n, ctx);	/* y = k u^r mod n */
	BN_mod_exp(g, k, rsa->e, rsa->n, ctx); /* g = k^b mod n */

	/*
	 * Alice computes v^r y^b mod n and verifies the result is equal
	 * to g. She needs modulus n, generator g and group key b from
	 * the parameters and Bob's public key v = (u^-1)^b from his
	 * certificate.
	 */
	BN_mod_exp(v, rsa->q, r, rsa->n, ctx);	/* v^r mod n */
	BN_mod_exp(y, y, rsa->e, rsa->n, ctx); /* y^b mod n */
	BN_mod_mul(y, v, y, rsa->n, ctx);	/* v^r y^b mod n */
	temp = BN_cmp(y, g);
	fprintf(stderr, "Confirm g^k = v^r y^b mod n: %s\n", temp == 0 ?
	    "yes" : "no");
	BN_CTX_free(ctx); BN_free(u); BN_free(v);
	BN_free(g); BN_free(k); BN_free(r); BN_free(y);
	if (temp != 0) {
		RSA_free(rsa);
		rval = -1;
		return (NULL);
	}

	/*
	 * Write the GQ parameters and keys as a RSA private key encoded
	 * in PEM.
	 *
	 * n	modulus n
	 * e	group key b
	 * p	private key u
	 * q	public key (u^-1)^b
	 * (remaining values are not used)
	 */
	str = fheader("GQpar", trustname);
	pkey = EVP_PKEY_new();
	EVP_PKEY_assign_RSA(pkey, rsa);
	PEM_write_PrivateKey(str, pkey, passwd2 ? EVP_des_cbc() : NULL,
	    NULL, 0, NULL, passwd2);
	fclose(str);
	if (debug)
		RSA_print_fp(stdout, rsa, 0);
	fslink(id, trustname);
	return (pkey);
}


/*
 * Generate Mu-Varadharajan (MV) parameters and keys
 *
 * The Mu-Varadharajan (MV) cryptosystem is useful when servers
 * broadcast messages to clients, but clients never send messages to
 * servers. There is one encryption key for the server and a separate
 * decryption key for each client. It operates something like a
 * pay-per-view satellite broadcasting system where the session key is
 * encrypted by the broadcaster and the decryption keys are held in a
 * tamperproof set-top box. We don't use it this way, but read on.
 *
 * The MV parameters and private encryption key hide in a DSA cuckoo
 * structure which uses the same parameters, but generated in a
 * different way. The values are used in an encryption scheme similar to
 * El Gamal cryptography and a polynomial formed from the expansion of
 * product terms (x - x[j]), as described in Mu, Y., and V.
 * Varadharajan: Robust and Secure Broadcasting, Proc. Indocrypt 2001,
 * 223-231. The paper has significant errors and serious omissions.
 *
 * Let q be the product of n distinct primes s'[j] (j = 1...n), where
 * each s'[j] has m significant bits. Let p be a prime p = 2 * q + 1, so
 * that q and each s'[j] divide p - 1 and p has M = n * m + 1
 * significant bits. Let g be a generator of Zp; that is, gcd(g, p - 1)
 * = 1 and g^q = 1 mod p. We do modular arithmetic over Zq and then
 * project into Zp* as exponents of g. Sometimes we have to compute an
 * inverse b^-1 of random b in Zq, but for that purpose we require
 * gcd(b, q) = 1. We expect M to be in the 500-bit range and n
 * relatively small, like 30. Associated with each s'[j] is an element
 * s[j] such that s[j] s'[j] = s'[j] mod q. We find s[j] as the quotient
 * (q + s'[j]) / s'[j]. These are the parameters of the scheme and they
 * are expensive to compute.
 *
 * We set up an instance of the scheme as follows. A set of random
 * values x[j] mod q (j = 1...n), are generated as the zeros of a
 * polynomial of order n. The product terms (x - x[j]) are expanded to
 * form coefficients a[i] mod q (i = 0...n) in powers of x. These are
 * used as exponents of the generator g mod p to generate the private
 * encryption key A. The pair (gbar, ghat) of public server keys and the
 * pairs (xbar[j], xhat[j]) (j = 1...n) of private client keys are used
 * to construct the decryption keys. The devil is in the details.
 *
 * This routine generates a private encryption file including the
 * private encryption key E and public key (gbar, ghat). It then
 * generates decryption files including the private key (xbar[j],
 * xhat[j]) for each client. E is a permutation that encrypts a block
 * y = E x. The jth client computes the inverse permutation E^-1 =
 * gbar^xhat[j] ghat^xbar[j] and decrypts the block x = E^-1 y.
 *
 * The distinguishing characteristic of this scheme is the capability to
 * revoke keys. Included in the calculation of E, gbar and ghat is the
 * product s = prod(s'[j]) (j = 1...n) above. If the factor s'[j] is
 * subsequently removed from the product and E, gbar and ghat
 * recomputed, the jth client will no longer be able to compute E^-1 and
 * thus unable to decrypt the block.
 */
EVP_PKEY *			/* DSA cuckoo nest */
gen_mv(
	char	*id		/* file name id */
	)
{
	EVP_PKEY *pkey, *pkey1;	/* private key */
	DSA	*dsa;		/* DSA parameters */
	DSA	*sdsa;		/* DSA parameters */
	BN_CTX	*ctx;		/* BN working space */
	BIGNUM	**x;		/* polynomial zeros vector */
	BIGNUM	**a;		/* polynomial coefficient vector */
	BIGNUM	**g;		/* public key vector */
	BIGNUM	**s, **s1;	/* private enabling keys */
	BIGNUM	**xbar, **xhat;	/* private keys vector */
	BIGNUM	*b;		/* group key */
	BIGNUM	*b1;		/* inverse group key */
	BIGNUM	*ss;		/* enabling key */
	BIGNUM	*biga;		/* master encryption key */
	BIGNUM	*bige;		/* session encryption key */
	BIGNUM	*gbar, *ghat;	/* public key */
	BIGNUM	*u, *v, *w;	/* BN scratch */
	int	i, j, n;
	FILE	*str;
	u_int	temp;
	char	ident[20];

	/*
	 * Generate MV parameters.
	 *
	 * The object is to generate a multiplicative group Zp* modulo a
	 * prime p and a subset Zq mod q, where q is the product of n
	 * distinct primes s'[j] (j = 1...n) and q divides p - 1. We
	 * first generate n distinct primes, which may have to be
	 * regenerated later. As a practical matter, it is tough to find
	 * more than 31 distinct primes for modulus 512 or 61 primes for
	 * modulus 1024. The latter can take several hundred iterations
	 * and several minutes on a Sun Blade 1000.
	 */
	n = nkeys;
	fprintf(stderr,
	    "Generating MV parameters for %d keys (%d bits)...\n", n,
	    modulus / n);
	ctx = BN_CTX_new(); u = BN_new(); v = BN_new(); w = BN_new();
	b = BN_new(); b1 = BN_new();
	dsa = DSA_new();
	dsa->p = BN_new();
	dsa->q = BN_new();
	dsa->g = BN_new();
	s = malloc((n + 1) * sizeof(BIGNUM));
	s1 = malloc((n + 1) * sizeof(BIGNUM));
	for (j = 1; j <= n; j++)
		s1[j] = BN_new();
	temp = 0;
	for (j = 1; j <= n; j++) {
		while (1) {
			fprintf(stderr, "Birthdays %d\r", temp);
			BN_generate_prime(s1[j], modulus / n, 0, NULL,
			    NULL, NULL, NULL);
			for (i = 1; i < j; i++) {
				if (BN_cmp(s1[i], s1[j]) == 0)
					break;
			}
			if (i == j)
				break;
			temp++;
		}
	}
	fprintf(stderr, "Birthday keys rejected %d\n", temp);

	/*
	 * Compute the modulus q as the product of the primes. Compute
	 * the modulus p as 2 * q + 1 and test p for primality. If p
	 * is composite, replace one of the primes with a new distinct
	 * one and try again. Note that q will hardly be a secret since
	 * we have to reveal p to servers and clients. However,
	 * factoring q to find the primes should be adequately hard, as
	 * this is the same problem considered hard in RSA. Question: is
	 * it as hard to find n small prime factors totalling n bits as
	 * it is to find two large prime factors totalling n bits?
	 * Remember, the bad guy doesn't know n.
	 */
	temp = 0;
	while (1) {
		fprintf(stderr, "Duplicate keys rejected %d\r", ++temp);
		BN_one(dsa->q);
		for (j = 1; j <= n; j++)
			BN_mul(dsa->q, dsa->q, s1[j], ctx);
		BN_copy(dsa->p, dsa->q);
		BN_add(dsa->p, dsa->p, dsa->p);
		BN_add_word(dsa->p, 1);
		if (BN_is_prime(dsa->p, BN_prime_checks, NULL, ctx,
		    NULL))
			break;

		j = temp % n + 1;
		while (1) {
			BN_generate_prime(u, modulus / n, 0, 0, NULL,
			    NULL, NULL);
			for (i = 1; i <= n; i++) {
				if (BN_cmp(u, s1[i]) == 0)
					break;
			}
			if (i > n)
				break;
		}
		BN_copy(s1[j], u);
	}
	fprintf(stderr, "Duplicate keys rejected %d\n", temp);

	/*
	 * Compute the generator g using a random roll such that
	 * gcd(g, p - 1) = 1 and g^q = 1. This is a generator of p, not
	 * q.
	 */
	BN_copy(v, dsa->p);
	BN_sub_word(v, 1);
	while (1) {
		BN_rand(dsa->g, BN_num_bits(dsa->p) - 1, 0, 0);
		BN_mod(dsa->g, dsa->g, dsa->p, ctx);
		BN_gcd(u, dsa->g, v, ctx);
		if (!BN_is_one(u))
			continue;

		BN_mod_exp(u, dsa->g, dsa->q, dsa->p, ctx);
		if (BN_is_one(u))
			break;
	}

	/*
	 * Compute s[j] such that s[j] * s'[j] = s'[j] for all j. The
	 * easy way to do this is to compute q + s'[j] and divide the
	 * result by s'[j]. Exercise for the student: prove the
	 * remainder is always zero.
	 */
	for (j = 1; j <= n; j++) {
		s[j] = BN_new();
		BN_add(s[j], dsa->q, s1[j]);
		BN_div(s[j], u, s[j], s1[j], ctx);
	}

	/*
	 * Setup is now complete. Roll random polynomial roots x[j]
	 * (0 < x[j] < q) for all j. While it may not be strictly
	 * necessary, Make sure each root has no factors in common with
	 * q.
	 */
	fprintf(stderr,
	    "Generating polynomial coefficients for %d roots (%d bits)\n",
	    n, BN_num_bits(dsa->q)); 
	x = malloc((n + 1) * sizeof(BIGNUM));
	for (j = 1; j <= n; j++) {
		x[j] = BN_new();
		while (1) {
			BN_rand(x[j], BN_num_bits(dsa->q), 0, 0);
			BN_mod(x[j], x[j], dsa->q, ctx);
			BN_gcd(u, x[j], dsa->q, ctx);
			if (BN_is_one(u))
				break;
		}
	}

	/*
	 * Generate polynomial coefficients a[i] (i = 0...n) from the
	 * expansion of root products (x - x[j]) mod q for all j. The
	 * method is a present from Charlie Boncelet.
	 */
	a = malloc((n + 1) * sizeof(BIGNUM));
	for (i = 0; i <= n; i++) {
		a[i] = BN_new();
		BN_one(a[i]);
	}
	for (j = 1; j <= n; j++) {
		BN_zero(w);
		for (i = 0; i < j; i++) {
			BN_copy(u, dsa->q);
			BN_mod_mul(v, a[i], x[j], dsa->q, ctx);
			BN_sub(u, u, v);
			BN_add(u, u, w);
			BN_copy(w, a[i]);
			BN_mod(a[i], u, dsa->q, ctx);
		}
	}

	/*
	 * Generate g[i] = g^a[i] mod p for all i and the generator g.
	 */
	fprintf(stderr, "Generating g[i] parameters\n");
	g = malloc((n + 1) * sizeof(BIGNUM));
	for (i = 0; i <= n; i++) {
		g[i] = BN_new();
		BN_mod_exp(g[i], dsa->g, a[i], dsa->p, ctx);
	}

	/*
	 * Verify prod(g[i]^(a[i] x[j]^i)) = 1 for all i, j; otherwise,
	 * exit. Note the a[i] x[j]^i exponent is computed mod q, but
	 * the g[i] is computed mod p. also note the expression given in
	 * the paper is incorrect.
	 */
	temp = 1;
	for (j = 1; j <= n; j++) {