/src/gnutls/lib/nettle/int/dsa-keygen-fips186.c

Source (jump to first uncovered line)
/* dsa-keygen.c
 *
 * Generation of DSA keypairs
 */

/* nettle, low-level cryptographics library
 *
 * Copyright (C) 2013, 2014 Red Hat
 *  
 * The nettle library is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version.
 * 
 * The nettle library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
 * License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with the nettle library.  If not, see <https://www.gnu.org/licenses/>.
 */

#if HAVE_CONFIG_H
# include "config.h"
#endif

#include <stdlib.h>
#include <string.h>

#include <nettle/dsa.h>
#include <dsa-fips.h>

#include <nettle/bignum.h>

unsigned _dsa_check_qp_sizes(unsigned q_bits, unsigned p_bits,
           unsigned generate)
{
  switch (q_bits) {
  case 160:
    FIPS_RULE(generate != 0, 0, "DSA 160-bit generation\n");

    if (p_bits != 1024)
      return 0;
    break;
  case 224:
    if (p_bits != 2048)
      return 0;
    break;
  case 256:
    if (p_bits != 2048 && p_bits != 3072)
      return 0;
    break;
  default:
    return 0;
  }
  return 1;
}

/* This generates p,q params using the A.1.2.1 algorithm in FIPS 186-4.
 * 
 * The hash function used is SHA384.
 */
int
_dsa_generate_dss_pq(struct dsa_params *params,
         struct dss_params_validation_seeds *cert,
         unsigned seed_length, void *seed,
         void *progress_ctx, nettle_progress_func * progress,
         unsigned p_bits /* = L */ , unsigned q_bits /* = N */ )
{
  mpz_t r, p0, t, z, s, tmp, dp0;
  int ret;
  unsigned iterations, old_counter, i;
  uint8_t *storage = NULL;
  unsigned storage_length = 0;

  ret = _dsa_check_qp_sizes(q_bits, p_bits, 1);
  if (ret == 0) {
    return 0;
  }

  if (seed_length < q_bits / 8) {
    _gnutls_debug_log
        ("Seed length must be larger than %d bytes (it is %d)\n",
         q_bits / 8, seed_length);
    return 0;
  }

  mpz_init(p0);
  mpz_init(dp0);
  mpz_init(r);
  mpz_init(t);
  mpz_init(z);
  mpz_init(s);
  mpz_init(tmp);

  /* firstseed < 2^(N-1) */
  mpz_set_ui(r, 1);
  mpz_mul_2exp(r, r, q_bits - 1);

  nettle_mpz_set_str_256_u(s, seed_length, seed);
  if (mpz_cmp(s, r) < 0) {
    goto fail;
  }

  cert->qseed_length = sizeof(cert->qseed);
  cert->pseed_length = sizeof(cert->pseed);

  ret = st_provable_prime(params->q,
        &cert->qseed_length, cert->qseed,
        &cert->qgen_counter,
        q_bits,
        seed_length, seed, progress_ctx, progress);
  if (ret == 0) {
    goto fail;
  }

  if (progress)
    progress(progress_ctx, 'q');

  ret = st_provable_prime(p0,
        &cert->pseed_length, cert->pseed,
        &cert->pgen_counter,
        1 + div_ceil(p_bits, 2),
        cert->qseed_length, cert->qseed,
        progress_ctx, progress);
  if (ret == 0) {
    goto fail;
  }

  iterations = div_ceil(p_bits, DIGEST_SIZE * 8);
  old_counter = cert->pgen_counter;

  if (iterations > 0) {
    storage_length = iterations * DIGEST_SIZE;
    storage = malloc(storage_length);
    if (storage == NULL) {
      goto fail;
    }

    nettle_mpz_set_str_256_u(s, cert->pseed_length, cert->pseed);
    for (i = 0; i < iterations; i++) {
      cert->pseed_length = nettle_mpz_sizeinbase_256_u(s);
      nettle_mpz_get_str_256(cert->pseed_length, cert->pseed,
                 s);

      hash(&storage[(iterations - i - 1) * DIGEST_SIZE],
           cert->pseed_length, cert->pseed);
      mpz_add_ui(s, s, 1);
    }

    /* x = 2^(p_bits-1) + (x mod 2^(p_bits-1)) */
    nettle_mpz_set_str_256_u(tmp, storage_length, storage);
  }

  mpz_set_ui(r, 1);
  mpz_mul_2exp(r, r, p_bits - 1);

  mpz_fdiv_r_2exp(tmp, tmp, p_bits - 1);
  mpz_add(tmp, tmp, r);

  /* Generate candidate prime p in [2^(bits-1), 2^bits] */

  /* t = u[x/2c0] */
  mpz_mul_2exp(dp0, p0, 1); /* dp0 = 2*p0 */
  mpz_mul(dp0, dp0, params->q); /* dp0 = 2*p0*q */

  mpz_cdiv_q(t, tmp, dp0);

 retry:
  /* c = 2p0*q*t + 1 */
  mpz_mul(params->p, dp0, t);
  mpz_add_ui(params->p, params->p, 1);

  if (mpz_sizeinbase(params->p, 2) > p_bits) {
    /* t = 2^(bits-1)/2qp0 */
    mpz_set_ui(tmp, 1);
    mpz_mul_2exp(tmp, tmp, p_bits - 1);
    mpz_cdiv_q(t, tmp, dp0);

    /* p = t* 2tq p0 + 1 */
    mpz_mul(params->p, dp0, t);
    mpz_add_ui(params->p, params->p, 1);
  }

  cert->pgen_counter++;

  mpz_set_ui(r, 0);

  if (iterations > 0) {
    for (i = 0; i < iterations; i++) {
      cert->pseed_length = nettle_mpz_sizeinbase_256_u(s);
      nettle_mpz_get_str_256(cert->pseed_length, cert->pseed,
                 s);

      hash(&storage[(iterations - i - 1) * DIGEST_SIZE],
           cert->pseed_length, cert->pseed);
      mpz_add_ui(s, s, 1);
    }

    /* r = a */
    nettle_mpz_set_str_256_u(r, storage_length, storage);
  }

  cert->pseed_length = nettle_mpz_sizeinbase_256_u(s);
  nettle_mpz_get_str_256(cert->pseed_length, cert->pseed, s);

  /* a = 2 + (a mod (p-3)) */
  mpz_sub_ui(tmp, params->p, 3);  /* c is too large to worry about negatives */
  mpz_mod(r, r, tmp);
  mpz_add_ui(r, r, 2);

  /* z = a^(2tq) mod p */
  mpz_mul_2exp(tmp, t, 1);  /* tmp = 2t */
  mpz_mul(tmp, tmp, params->q); /* tmp = 2tq */
  mpz_powm(z, r, tmp, params->p);

  mpz_sub_ui(tmp, z, 1);

  mpz_gcd(tmp, tmp, params->p);
  if (mpz_cmp_ui(tmp, 1) == 0) {
    mpz_powm(tmp, z, p0, params->p);
    if (mpz_cmp_ui(tmp, 1) == 0) {
      goto success;
    }
  }

  if (progress)
    progress(progress_ctx, 'x');

  if (cert->pgen_counter >= (4 * p_bits + old_counter))
    return 0;

  mpz_add_ui(t, t, 1);
  goto retry;

 success:
  if (progress)
    progress(progress_ctx, 'p');

  ret = 1;
  goto finish;

 fail:
  ret = 0;

 finish:
  mpz_clear(dp0);
  mpz_clear(p0);
  mpz_clear(tmp);
  mpz_clear(t);
  mpz_clear(z);
  mpz_clear(s);
  mpz_clear(r);
  free(storage);
  return ret;
}

int
_dsa_generate_dss_g(struct dsa_params *params,
        unsigned domain_seed_size, const uint8_t * domain_seed,
        void *progress_ctx, nettle_progress_func * progress,
        unsigned index)
{
  mpz_t e, w;
  uint16_t count;
  uint8_t *dseed = NULL;
  unsigned dseed_size;
  unsigned pos;
  uint8_t digest[DIGEST_SIZE];
  int ret;

  if (index > 255 || domain_seed_size == 0)
    return 0;

  dseed_size = domain_seed_size + 4 + 1 + 2;
  dseed = malloc(dseed_size);
  if (dseed == NULL)
    return 0;

  mpz_init(e);
  mpz_init(w);

  memcpy(dseed, domain_seed, domain_seed_size);
  pos = domain_seed_size;

  memcpy(dseed + pos, "\x67\x67\x65\x6e", 4);
  pos += 4;

  *(dseed + pos) = (uint8_t) index;
  pos += 1;

  mpz_sub_ui(e, params->p, 1);
  mpz_fdiv_q(e, e, params->q);

  for (count = 1; count < 65535; count++) {
    *(dseed + pos) = (count >> 8) & 0xff;
    *(dseed + pos + 1) = count & 0xff;

    hash(digest, dseed_size, dseed);

    nettle_mpz_set_str_256_u(w, DIGEST_SIZE, digest);

    mpz_powm(params->g, w, e, params->p);

    if (mpz_cmp_ui(params->g, 2) >= 0) {
      /* found */
      goto success;
    }
    if (progress)
      progress(progress_ctx, 'x');
  }

  /* if we're here we failed */
  if (progress)
    progress(progress_ctx, 'X');
  ret = 0;
  goto finish;

 success:
  if (progress)
    progress(progress_ctx, 'g');

  ret = 1;

 finish:
  free(dseed);
  mpz_clear(e);
  mpz_clear(w);
  return ret;

}

/* Generates the public and private DSA (or DH) keys
 */
void
_dsa_generate_dss_xy(struct dsa_params *params,
         mpz_t y, mpz_t x,
         void *random_ctx, nettle_random_func * random)
{
  mpz_t r;

  mpz_init(r);
  mpz_set(r, params->q);
  mpz_sub_ui(r, r, 2);
  nettle_mpz_random(x, random_ctx, random, r);
  mpz_add_ui(x, x, 1);

  mpz_powm(y, params->g, x, params->p);

  mpz_clear(r);
}

/* This generates p, q, g params using the algorithms from FIPS 186-4.
 * For p, q, the Shawe-Taylor algorithm is used.
 * For g, the verifiable canonical generation of the generator is used.
 * 
 * The hash function used is SHA384.
 * 
 * pub: The output public key
 * key: The output private key
 * cert: A certificate that can be used to verify the generated parameters
 * index: 1 for digital signatures (DSA), 2 for key establishment (DH)
 * p_bits: The requested size of p
 * q_bits: The requested size of q
 * 
 */
int
dsa_generate_dss_pqg(struct dsa_params *params,
         struct dss_params_validation_seeds *cert,
         unsigned index,
         void *random_ctx, nettle_random_func * random,
         void *progress_ctx, nettle_progress_func * progress,
         unsigned p_bits /* = L */ , unsigned q_bits /* = N */ )
{
  int ret;
  uint8_t domain_seed[MAX_PVP_SEED_SIZE * 3];
  unsigned domain_seed_size = 0;

  ret = _dsa_check_qp_sizes(q_bits, p_bits, 1);
  if (ret == 0)
    return 0;

  cert->seed_length = 2 * (q_bits / 8) + 1;

  if (cert->seed_length > sizeof(cert->seed))
    return 0;

  random(random_ctx, cert->seed_length, cert->seed);

  ret = _dsa_generate_dss_pq(params, cert, cert->seed_length, cert->seed,
           progress_ctx, progress, p_bits, q_bits);
  if (ret == 0)
    return 0;

  domain_seed_size =
      cert->seed_length + cert->qseed_length + cert->pseed_length;
  memcpy(domain_seed, cert->seed, cert->seed_length);
  memcpy(&domain_seed[cert->seed_length], cert->pseed,
         cert->pseed_length);
  memcpy(&domain_seed[cert->seed_length + cert->pseed_length],
         cert->qseed, cert->qseed_length);
  ret =
      _dsa_generate_dss_g(params, domain_seed_size, domain_seed,
        progress_ctx, progress, index);
  if (ret == 0)
    return 0;

  return 1;
}

int
_dsa_generate_dss_pqg(struct dsa_params *params,
          struct dss_params_validation_seeds *cert,
          unsigned index,
          unsigned seed_size, void *seed,
          void *progress_ctx, nettle_progress_func * progress,
          unsigned p_bits /* = L */ , unsigned q_bits /* = N */ )
{
  int ret;
  uint8_t domain_seed[MAX_PVP_SEED_SIZE * 3];
  unsigned domain_seed_size = 0;

  ret = _dsa_check_qp_sizes(q_bits, p_bits, 1);
  if (ret == 0)
    return 0;

  if (_gnutls_fips_mode_enabled() != 0) {
    cert->seed_length = 2 * (q_bits / 8) + 1;

    FIPS_RULE(cert->seed_length != seed_size, 0,
        "unsupported DSA seed length (is %d, should be %d)\n",
        seed_size, cert->seed_length);
  } else {
    cert->seed_length = seed_size;
  }

  if (cert->seed_length > sizeof(cert->seed))
    return 0;

  memcpy(cert->seed, seed, cert->seed_length);

  ret = _dsa_generate_dss_pq(params, cert, cert->seed_length, cert->seed,
           progress_ctx, progress, p_bits, q_bits);
  if (ret == 0)
    return 0;

  domain_seed_size =
      cert->seed_length + cert->qseed_length + cert->pseed_length;
  memcpy(domain_seed, cert->seed, cert->seed_length);
  memcpy(&domain_seed[cert->seed_length], cert->pseed,
         cert->pseed_length);
  memcpy(&domain_seed[cert->seed_length + cert->pseed_length],
         cert->qseed, cert->qseed_length);
  ret =
      _dsa_generate_dss_g(params, domain_seed_size, domain_seed,
        progress_ctx, progress, index);
  if (ret == 0)
    return 0;

  return 1;
}

int
dsa_generate_dss_keypair(struct dsa_params *params,
       mpz_t y,
       mpz_t x,
       void *random_ctx, nettle_random_func * random,
       void *progress_ctx, nettle_progress_func * progress)
{
  _dsa_generate_dss_xy(params, y, x, random_ctx, random);

  if (progress)
    progress(progress_ctx, '\n');

  return 1;

}

Coverage Report

Created: 2023-03-26 08:33

Line	Count	Source (jump to first uncovered line)
1		/* dsa-keygen.c
2		*
3		* Generation of DSA keypairs
4		*/
5
6		/* nettle, low-level cryptographics library
7		*
8		* Copyright (C) 2013, 2014 Red Hat
9		*
10		* The nettle library is free software; you can redistribute it and/or modify
11		* it under the terms of the GNU Lesser General Public License as published by
12		* the Free Software Foundation; either version 2.1 of the License, or (at your
13		* option) any later version.
14		*
15		* The nettle library is distributed in the hope that it will be useful, but
16		* WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17		* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18		* License for more details.
19		*
20		* You should have received a copy of the GNU Lesser General Public License
21		* along with the nettle library. If not, see <https://www.gnu.org/licenses/>.
22		*/
23
24		#if HAVE_CONFIG_H
25		# include "config.h"
26		#endif
27
28		#include <stdlib.h>
29		#include <string.h>
30
31		#include <nettle/dsa.h>
32		#include <dsa-fips.h>
33
34		#include <nettle/bignum.h>
35
36		unsigned _dsa_check_qp_sizes(unsigned q_bits, unsigned p_bits,
37		unsigned generate)
38	0	{
39	0	switch (q_bits) {
40	0	case 160:
41	0	FIPS_RULE(generate != 0, 0, "DSA 160-bit generation\n");
42
43	0	if (p_bits != 1024)
44	0	return 0;
45	0	break;
46	0	case 224:
47	0	if (p_bits != 2048)
48	0	return 0;
49	0	break;
50	0	case 256:
51	0	if (p_bits != 2048 && p_bits != 3072)
52	0	return 0;
53	0	break;
54	0	default:
55	0	return 0;
56	0	}
57	0	return 1;
58	0	}
59
60		/* This generates p,q params using the A.1.2.1 algorithm in FIPS 186-4.
61		*
62		* The hash function used is SHA384.
63		*/
64		int
65		_dsa_generate_dss_pq(struct dsa_params *params,
66		struct dss_params_validation_seeds *cert,
67		unsigned seed_length, void *seed,
68		void progress_ctx, nettle_progress_func progress,
69		unsigned p_bits /* = L / , unsigned q_bits / = N */ )
70	0	{
71	0	mpz_t r, p0, t, z, s, tmp, dp0;
72	0	int ret;
73	0	unsigned iterations, old_counter, i;
74	0	uint8_t *storage = NULL;
75	0	unsigned storage_length = 0;
76
77	0	ret = _dsa_check_qp_sizes(q_bits, p_bits, 1);
78	0	if (ret == 0) {
79	0	return 0;
80	0	}
81
82	0	if (seed_length < q_bits / 8) {
83	0	_gnutls_debug_log
84	0	("Seed length must be larger than %d bytes (it is %d)\n",
85	0	q_bits / 8, seed_length);
86	0	return 0;
87	0	}
88
89	0	mpz_init(p0);
90	0	mpz_init(dp0);
91	0	mpz_init(r);
92	0	mpz_init(t);
93	0	mpz_init(z);
94	0	mpz_init(s);
95	0	mpz_init(tmp);
96
97		/* firstseed < 2^(N-1) */
98	0	mpz_set_ui(r, 1);
99	0	mpz_mul_2exp(r, r, q_bits - 1);
100
101	0	nettle_mpz_set_str_256_u(s, seed_length, seed);
102	0	if (mpz_cmp(s, r) < 0) {
103	0	goto fail;
104	0	}
105
106	0	cert->qseed_length = sizeof(cert->qseed);
107	0	cert->pseed_length = sizeof(cert->pseed);
108
109	0	ret = st_provable_prime(params->q,
110	0	&cert->qseed_length, cert->qseed,
111	0	&cert->qgen_counter,
112	0	q_bits,
113	0	seed_length, seed, progress_ctx, progress);
114	0	if (ret == 0) {
115	0	goto fail;
116	0	}
117
118	0	if (progress)
119	0	progress(progress_ctx, 'q');
120
121	0	ret = st_provable_prime(p0,
122	0	&cert->pseed_length, cert->pseed,
123	0	&cert->pgen_counter,
124	0	1 + div_ceil(p_bits, 2),
125	0	cert->qseed_length, cert->qseed,
126	0	progress_ctx, progress);
127	0	if (ret == 0) {
128	0	goto fail;
129	0	}
130
131	0	iterations = div_ceil(p_bits, DIGEST_SIZE * 8);
132	0	old_counter = cert->pgen_counter;
133
134	0	if (iterations > 0) {
135	0	storage_length = iterations * DIGEST_SIZE;
136	0	storage = malloc(storage_length);
137	0	if (storage == NULL) {
138	0	goto fail;
139	0	}
140
141	0	nettle_mpz_set_str_256_u(s, cert->pseed_length, cert->pseed);
142	0	for (i = 0; i < iterations; i++) {
143	0	cert->pseed_length = nettle_mpz_sizeinbase_256_u(s);
144	0	nettle_mpz_get_str_256(cert->pseed_length, cert->pseed,
145	0	s);
146
147	0	hash(&storage[(iterations - i - 1) * DIGEST_SIZE],
148	0	cert->pseed_length, cert->pseed);
149	0	mpz_add_ui(s, s, 1);
150	0	}
151
152		/* x = 2^(p_bits-1) + (x mod 2^(p_bits-1)) */
153	0	nettle_mpz_set_str_256_u(tmp, storage_length, storage);
154	0	}
155
156	0	mpz_set_ui(r, 1);
157	0	mpz_mul_2exp(r, r, p_bits - 1);
158
159	0	mpz_fdiv_r_2exp(tmp, tmp, p_bits - 1);
160	0	mpz_add(tmp, tmp, r);
161
162		/* Generate candidate prime p in [2^(bits-1), 2^bits] */
163
164		/* t = u[x/2c0] */
165	0	mpz_mul_2exp(dp0, p0, 1); /* dp0 = 2p0 /
166	0	mpz_mul(dp0, dp0, params->q); /* dp0 = 2p0q */
167
168	0	mpz_cdiv_q(t, tmp, dp0);
169
170	0	retry:
171		/* c = 2p0qt + 1 */
172	0	mpz_mul(params->p, dp0, t);
173	0	mpz_add_ui(params->p, params->p, 1);
174
175	0	if (mpz_sizeinbase(params->p, 2) > p_bits) {
176		/* t = 2^(bits-1)/2qp0 */
177	0	mpz_set_ui(tmp, 1);
178	0	mpz_mul_2exp(tmp, tmp, p_bits - 1);
179	0	mpz_cdiv_q(t, tmp, dp0);
180
181		/* p = t* 2tq p0 + 1 */
182	0	mpz_mul(params->p, dp0, t);
183	0	mpz_add_ui(params->p, params->p, 1);
184	0	}
185
186	0	cert->pgen_counter++;
187
188	0	mpz_set_ui(r, 0);
189
190	0	if (iterations > 0) {
191	0	for (i = 0; i < iterations; i++) {
192	0	cert->pseed_length = nettle_mpz_sizeinbase_256_u(s);
193	0	nettle_mpz_get_str_256(cert->pseed_length, cert->pseed,
194	0	s);
195
196	0	hash(&storage[(iterations - i - 1) * DIGEST_SIZE],
197	0	cert->pseed_length, cert->pseed);
198	0	mpz_add_ui(s, s, 1);
199	0	}
200
201		/* r = a */
202	0	nettle_mpz_set_str_256_u(r, storage_length, storage);
203	0	}
204
205	0	cert->pseed_length = nettle_mpz_sizeinbase_256_u(s);
206	0	nettle_mpz_get_str_256(cert->pseed_length, cert->pseed, s);
207
208		/* a = 2 + (a mod (p-3)) */
209	0	mpz_sub_ui(tmp, params->p, 3); /* c is too large to worry about negatives */
210	0	mpz_mod(r, r, tmp);
211	0	mpz_add_ui(r, r, 2);
212
213		/* z = a^(2tq) mod p */
214	0	mpz_mul_2exp(tmp, t, 1); /* tmp = 2t */
215	0	mpz_mul(tmp, tmp, params->q); /* tmp = 2tq */
216	0	mpz_powm(z, r, tmp, params->p);
217
218	0	mpz_sub_ui(tmp, z, 1);
219
220	0	mpz_gcd(tmp, tmp, params->p);
221	0	if (mpz_cmp_ui(tmp, 1) == 0) {
222	0	mpz_powm(tmp, z, p0, params->p);
223	0	if (mpz_cmp_ui(tmp, 1) == 0) {
224	0	goto success;
225	0	}
226	0	}
227
228	0	if (progress)
229	0	progress(progress_ctx, 'x');
230
231	0	if (cert->pgen_counter >= (4 * p_bits + old_counter))
232	0	return 0;
233
234	0	mpz_add_ui(t, t, 1);
235	0	goto retry;
236
237	0	success:
238	0	if (progress)
239	0	progress(progress_ctx, 'p');
240
241	0	ret = 1;
242	0	goto finish;
243
244	0	fail:
245	0	ret = 0;
246
247	0	finish:
248	0	mpz_clear(dp0);
249	0	mpz_clear(p0);
250	0	mpz_clear(tmp);
251	0	mpz_clear(t);
252	0	mpz_clear(z);
253	0	mpz_clear(s);
254	0	mpz_clear(r);
255	0	free(storage);
256	0	return ret;
257	0	}
258
259		int
260		_dsa_generate_dss_g(struct dsa_params *params,
261		unsigned domain_seed_size, const uint8_t * domain_seed,
262		void progress_ctx, nettle_progress_func progress,
263		unsigned index)
264	0	{
265	0	mpz_t e, w;
266	0	uint16_t count;
267	0	uint8_t *dseed = NULL;
268	0	unsigned dseed_size;
269	0	unsigned pos;
270	0	uint8_t digest[DIGEST_SIZE];
271	0	int ret;
272
273	0	if (index > 255 \|\| domain_seed_size == 0)
274	0	return 0;
275
276	0	dseed_size = domain_seed_size + 4 + 1 + 2;
277	0	dseed = malloc(dseed_size);
278	0	if (dseed == NULL)
279	0	return 0;
280
281	0	mpz_init(e);
282	0	mpz_init(w);
283
284	0	memcpy(dseed, domain_seed, domain_seed_size);
285	0	pos = domain_seed_size;
286
287	0	memcpy(dseed + pos, "\x67\x67\x65\x6e", 4);
288	0	pos += 4;
289
290	0	*(dseed + pos) = (uint8_t) index;
291	0	pos += 1;
292
293	0	mpz_sub_ui(e, params->p, 1);
294	0	mpz_fdiv_q(e, e, params->q);
295
296	0	for (count = 1; count < 65535; count++) {
297	0	*(dseed + pos) = (count >> 8) & 0xff;
298	0	*(dseed + pos + 1) = count & 0xff;
299
300	0	hash(digest, dseed_size, dseed);
301
302	0	nettle_mpz_set_str_256_u(w, DIGEST_SIZE, digest);
303
304	0	mpz_powm(params->g, w, e, params->p);
305
306	0	if (mpz_cmp_ui(params->g, 2) >= 0) {
307		/* found */
308	0	goto success;
309	0	}
310	0	if (progress)
311	0	progress(progress_ctx, 'x');
312	0	}
313
314		/* if we're here we failed */
315	0	if (progress)
316	0	progress(progress_ctx, 'X');
317	0	ret = 0;
318	0	goto finish;
319
320	0	success:
321	0	if (progress)
322	0	progress(progress_ctx, 'g');
323
324	0	ret = 1;
325
326	0	finish:
327	0	free(dseed);
328	0	mpz_clear(e);
329	0	mpz_clear(w);
330	0	return ret;
331
332	0	}
333
334		/* Generates the public and private DSA (or DH) keys
335		*/
336		void
337		_dsa_generate_dss_xy(struct dsa_params *params,
338		mpz_t y, mpz_t x,
339		void random_ctx, nettle_random_func random)
340	0	{
341	0	mpz_t r;
342
343	0	mpz_init(r);
344	0	mpz_set(r, params->q);
345	0	mpz_sub_ui(r, r, 2);
346	0	nettle_mpz_random(x, random_ctx, random, r);
347	0	mpz_add_ui(x, x, 1);
348
349	0	mpz_powm(y, params->g, x, params->p);
350
351	0	mpz_clear(r);
352	0	}
353
354		/* This generates p, q, g params using the algorithms from FIPS 186-4.
355		* For p, q, the Shawe-Taylor algorithm is used.
356		* For g, the verifiable canonical generation of the generator is used.
357		*
358		* The hash function used is SHA384.
359		*
360		* pub: The output public key
361		* key: The output private key
362		* cert: A certificate that can be used to verify the generated parameters
363		* index: 1 for digital signatures (DSA), 2 for key establishment (DH)
364		* p_bits: The requested size of p
365		* q_bits: The requested size of q
366		*
367		*/
368		int
369		dsa_generate_dss_pqg(struct dsa_params *params,
370		struct dss_params_validation_seeds *cert,
371		unsigned index,
372		void random_ctx, nettle_random_func random,
373		void progress_ctx, nettle_progress_func progress,
374		unsigned p_bits /* = L / , unsigned q_bits / = N */ )
375	0	{
376	0	int ret;
377	0	uint8_t domain_seed[MAX_PVP_SEED_SIZE * 3];
378	0	unsigned domain_seed_size = 0;
379
380	0	ret = _dsa_check_qp_sizes(q_bits, p_bits, 1);
381	0	if (ret == 0)
382	0	return 0;
383
384	0	cert->seed_length = 2 * (q_bits / 8) + 1;
385
386	0	if (cert->seed_length > sizeof(cert->seed))
387	0	return 0;
388
389	0	random(random_ctx, cert->seed_length, cert->seed);
390
391	0	ret = _dsa_generate_dss_pq(params, cert, cert->seed_length, cert->seed,
392	0	progress_ctx, progress, p_bits, q_bits);
393	0	if (ret == 0)
394	0	return 0;
395
396	0	domain_seed_size =
397	0	cert->seed_length + cert->qseed_length + cert->pseed_length;
398	0	memcpy(domain_seed, cert->seed, cert->seed_length);
399	0	memcpy(&domain_seed[cert->seed_length], cert->pseed,
400	0	cert->pseed_length);
401	0	memcpy(&domain_seed[cert->seed_length + cert->pseed_length],
402	0	cert->qseed, cert->qseed_length);
403	0	ret =
404	0	_dsa_generate_dss_g(params, domain_seed_size, domain_seed,
405	0	progress_ctx, progress, index);
406	0	if (ret == 0)
407	0	return 0;
408
409	0	return 1;
410	0	}
411
412		int
413		_dsa_generate_dss_pqg(struct dsa_params *params,
414		struct dss_params_validation_seeds *cert,
415		unsigned index,
416		unsigned seed_size, void *seed,
417		void progress_ctx, nettle_progress_func progress,
418		unsigned p_bits /* = L / , unsigned q_bits / = N */ )
419	0	{
420	0	int ret;
421	0	uint8_t domain_seed[MAX_PVP_SEED_SIZE * 3];
422	0	unsigned domain_seed_size = 0;
423
424	0	ret = _dsa_check_qp_sizes(q_bits, p_bits, 1);
425	0	if (ret == 0)
426	0	return 0;
427
428	0	if (_gnutls_fips_mode_enabled() != 0) {
429	0	cert->seed_length = 2 * (q_bits / 8) + 1;
430
431	0	FIPS_RULE(cert->seed_length != seed_size, 0,
432	0	"unsupported DSA seed length (is %d, should be %d)\n",
433	0	seed_size, cert->seed_length);
434	0	} else {
435	0	cert->seed_length = seed_size;
436	0	}
437
438	0	if (cert->seed_length > sizeof(cert->seed))
439	0	return 0;
440
441	0	memcpy(cert->seed, seed, cert->seed_length);
442
443	0	ret = _dsa_generate_dss_pq(params, cert, cert->seed_length, cert->seed,
444	0	progress_ctx, progress, p_bits, q_bits);
445	0	if (ret == 0)
446	0	return 0;
447
448	0	domain_seed_size =
449	0	cert->seed_length + cert->qseed_length + cert->pseed_length;
450	0	memcpy(domain_seed, cert->seed, cert->seed_length);
451	0	memcpy(&domain_seed[cert->seed_length], cert->pseed,
452	0	cert->pseed_length);
453	0	memcpy(&domain_seed[cert->seed_length + cert->pseed_length],
454	0	cert->qseed, cert->qseed_length);
455	0	ret =
456	0	_dsa_generate_dss_g(params, domain_seed_size, domain_seed,
457	0	progress_ctx, progress, index);
458	0	if (ret == 0)
459	0	return 0;
460
461	0	return 1;
462	0	}
463
464		int
465		dsa_generate_dss_keypair(struct dsa_params *params,
466		mpz_t y,
467		mpz_t x,
468		void random_ctx, nettle_random_func random,
469		void progress_ctx, nettle_progress_func progress)
470	0	{
471	0	_dsa_generate_dss_xy(params, y, x, random_ctx, random);
472
473	0	if (progress)
474	0	progress(progress_ctx, '\n');
475
476	0	return 1;
477
478	0	}