generate (DSA_secret_key *sk, unsigned int nbits, unsigned int qbits,
          int transient_key, dsa_domain_t *domain, gcry_mpi_t **ret_factors )
{
  gpg_err_code_t rc;
  gcry_mpi_t p;    /* the prime */
  gcry_mpi_t q;    /* the 160 bit prime factor */
  gcry_mpi_t g;    /* the generator */
  gcry_mpi_t y;    /* g^x mod p */
  gcry_mpi_t x;    /* the secret exponent */
  gcry_mpi_t h, e;  /* helper */
  unsigned char *rndbuf;
  gcry_random_level_t random_level;

  if (qbits)
    ; /* Caller supplied qbits.  Use this value.  */
  else if ( nbits >= 512 && nbits <= 1024 )
    qbits = 160;
  else if ( nbits == 2048 )
    qbits = 224;
  else if ( nbits == 3072 )
    qbits = 256;
  else if ( nbits == 7680 )
    qbits = 384;
  else if ( nbits == 15360 )
    qbits = 512;
  else
    return GPG_ERR_INV_VALUE;

  if (qbits < 160 || qbits > 512 || (qbits%8) )
    return GPG_ERR_INV_VALUE;
  if (nbits < 2*qbits || nbits > 15360)
    return GPG_ERR_INV_VALUE;

  if (fips_mode ())
    {
      if (nbits < 1024)
        return GPG_ERR_INV_VALUE;
      if (transient_key)
        return GPG_ERR_INV_VALUE;
    }

  if (domain->p && domain->q && domain->g)
    {
      /* Domain parameters are given; use them.  */
      p = mpi_copy (domain->p);
      q = mpi_copy (domain->q);
      g = mpi_copy (domain->g);
      gcry_assert (mpi_get_nbits (p) == nbits);
      gcry_assert (mpi_get_nbits (q) == qbits);
      h = mpi_alloc (0);
      e = NULL;
    }
  else
    {
      /* Generate new domain parameters.  */
      rc = _gcry_generate_elg_prime (1, nbits, qbits, NULL, &p, ret_factors);
      if (rc)
        return rc;

      /* Get q out of factors.  */
      q = mpi_copy ((*ret_factors)[0]);
      gcry_assert (mpi_get_nbits (q) == qbits);

      /* Find a generator g (h and e are helpers).
         e = (p-1)/q */
      e = mpi_alloc (mpi_get_nlimbs (p));
      mpi_sub_ui (e, p, 1);
      mpi_fdiv_q (e, e, q);
      g = mpi_alloc (mpi_get_nlimbs (p));
      h = mpi_alloc_set_ui (1); /* (We start with 2.) */
      do
        {
          mpi_add_ui (h, h, 1);
          /* g = h^e mod p */
          mpi_powm (g, h, e, p);
        }
      while (!mpi_cmp_ui (g, 1));  /* Continue until g != 1. */
    }

  /* Select a random number X with the property:
   *	 0 < x < q-1
   *
   * FIXME: Why do we use the requirement x < q-1 ? It should be
   * sufficient to test for x < q.  FIPS-186-3 check x < q-1 but it
   * does not check for 0 < x because it makes sure that Q is unsigned
   * and finally adds one to the result so that 0 will never be
   * returned.  We should replace the code below with _gcry_dsa_gen_k.
   *
   * This must be a very good random number because this is the secret
   * part.  The random quality depends on the transient_key flag.  */
  random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
  if (DBG_CIPHER)
    log_debug("choosing a random x%s\n", transient_key? " (transient-key)":"");
  gcry_assert( qbits >= 160 );
  x = mpi_alloc_secure( mpi_get_nlimbs(q) );
  mpi_sub_ui( h, q, 1 );  /* put q-1 into h */
  rndbuf = NULL;
  do
    {
      if( DBG_CIPHER )
        progress('.');
      if( !rndbuf )
        rndbuf = _gcry_random_bytes_secure ((qbits+7)/8, random_level);
      else
        { /* Change only some of the higher bits (= 2 bytes)*/
          char *r = _gcry_random_bytes_secure (2, random_level);
          memcpy(rndbuf, r, 2 );
          xfree(r);
        }

      _gcry_mpi_set_buffer( x, rndbuf, (qbits+7)/8, 0 );
      mpi_clear_highbit( x, qbits+1 );
    }
  while ( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, h )<0 ) );
  xfree(rndbuf);
  mpi_free( e );
  mpi_free( h );

  /* y = g^x mod p */
  y = mpi_alloc( mpi_get_nlimbs(p) );
  mpi_powm (y, g, x, p);

  if( DBG_CIPHER )
    {
      progress('\n');
      log_mpidump("dsa  p", p );
      log_mpidump("dsa  q", q );
      log_mpidump("dsa  g", g );
      log_mpidump("dsa  y", y );
      log_mpidump("dsa  x", x );
    }

  /* Copy the stuff to the key structures. */
  sk->p = p;
  sk->q = q;
  sk->g = g;
  sk->y = y;
  sk->x = x;

  /* Now we can test our keys (this should never fail!). */
  if ( test_keys (sk, qbits) )
    {
      _gcry_mpi_release (sk->p); sk->p = NULL;
      _gcry_mpi_release (sk->q); sk->q = NULL;
      _gcry_mpi_release (sk->g); sk->g = NULL;
      _gcry_mpi_release (sk->y); sk->y = NULL;
      _gcry_mpi_release (sk->x); sk->x = NULL;
      fips_signal_error ("self-test after key generation failed");
      return GPG_ERR_SELFTEST_FAILED;
    }
  return 0;
}