_gcry_dsa_gen_rfc6979_k (gcry_mpi_t *r_k,
                         gcry_mpi_t dsa_q, gcry_mpi_t dsa_x,
                         const unsigned char *h1, unsigned int hlen,
                         int halgo, unsigned int extraloops)
{
  gpg_err_code_t rc;
  unsigned char *V = NULL;
  unsigned char *K = NULL;
  unsigned char *x_buf = NULL;
  unsigned char *h1_buf = NULL;
  gcry_md_hd_t hd = NULL;
  unsigned char *t = NULL;
  gcry_mpi_t k = NULL;
  unsigned int tbits, qbits;
  int i;

  qbits = mpi_get_nbits (dsa_q);

  if (!qbits || !h1 || !hlen)
    return GPG_ERR_EINVAL;

  if (_gcry_md_get_algo_dlen (halgo) != hlen)
    return GPG_ERR_DIGEST_ALGO;

  /* Step b:  V = 0x01 0x01 0x01 ... 0x01 */
  V = xtrymalloc (hlen);
  if (!V)
    {
      rc = gpg_err_code_from_syserror ();
      goto leave;
    }
  for (i=0; i < hlen; i++)
    V[i] = 1;

  /* Step c:  K = 0x00 0x00 0x00 ... 0x00 */
  K = xtrycalloc (1, hlen);
  if (!K)
    {
      rc = gpg_err_code_from_syserror ();
      goto leave;
    }

  rc = int2octets (&x_buf, dsa_x, (qbits+7)/8);
  if (rc)
    goto leave;

  rc = bits2octets (&h1_buf, h1, hlen*8, dsa_q, qbits);
  if (rc)
    goto leave;

  /* Create a handle to compute the HMACs.  */
  rc = _gcry_md_open (&hd, halgo, (GCRY_MD_FLAG_SECURE | GCRY_MD_FLAG_HMAC));
  if (rc)
    goto leave;

  /* Step d:  K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1) */
  rc = _gcry_md_setkey (hd, K, hlen);
  if (rc)
    goto leave;
  _gcry_md_write (hd, V, hlen);
  _gcry_md_write (hd, "", 1);
  _gcry_md_write (hd, x_buf, (qbits+7)/8);
  _gcry_md_write (hd, h1_buf, (qbits+7)/8);
  memcpy (K, _gcry_md_read (hd, 0), hlen);

  /* Step e:  V = HMAC_K(V) */
  rc = _gcry_md_setkey (hd, K, hlen);
  if (rc)
    goto leave;
  _gcry_md_write (hd, V, hlen);
  memcpy (V, _gcry_md_read (hd, 0), hlen);

  /* Step f:  K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1) */
  rc = _gcry_md_setkey (hd, K, hlen);
  if (rc)
    goto leave;
  _gcry_md_write (hd, V, hlen);
  _gcry_md_write (hd, "\x01", 1);
  _gcry_md_write (hd, x_buf, (qbits+7)/8);
  _gcry_md_write (hd, h1_buf, (qbits+7)/8);
  memcpy (K, _gcry_md_read (hd, 0), hlen);

  /* Step g:  V = HMAC_K(V) */
  rc = _gcry_md_setkey (hd, K, hlen);
  if (rc)
    goto leave;
  _gcry_md_write (hd, V, hlen);
  memcpy (V, _gcry_md_read (hd, 0), hlen);

  /* Step h. */
  t = xtrymalloc_secure ((qbits+7)/8+hlen);
  if (!t)
    {
      rc = gpg_err_code_from_syserror ();
      goto leave;
    }

 again:
  for (tbits = 0; tbits < qbits;)
    {
      /* V = HMAC_K(V) */
      rc = _gcry_md_setkey (hd, K, hlen);
      if (rc)
        goto leave;
      _gcry_md_write (hd, V, hlen);
      memcpy (V, _gcry_md_read (hd, 0), hlen);

      /* T = T || V */
      memcpy (t+(tbits+7)/8, V, hlen);
      tbits += 8*hlen;
    }

  /* k = bits2int (T) */
  mpi_free (k);
  k = NULL;
  rc = _gcry_mpi_scan (&k, GCRYMPI_FMT_USG, t, (tbits+7)/8, NULL);
  if (rc)
    goto leave;
  if (tbits > qbits)
    mpi_rshift (k, k, tbits - qbits);

  /* Check: k < q and k > 1 */
  if (!(mpi_cmp (k, dsa_q) < 0 && mpi_cmp_ui (k, 0) > 0))
    {
      /* K = HMAC_K(V || 0x00) */
      rc = _gcry_md_setkey (hd, K, hlen);
      if (rc)
        goto leave;
      _gcry_md_write (hd, V, hlen);
      _gcry_md_write (hd, "", 1);
      memcpy (K, _gcry_md_read (hd, 0), hlen);

      /* V = HMAC_K(V) */
      rc = _gcry_md_setkey (hd, K, hlen);
      if (rc)
        goto leave;
      _gcry_md_write (hd, V, hlen);
      memcpy (V, _gcry_md_read (hd, 0), hlen);

      goto again;
    }

  /* The caller may have requested that we introduce some extra loops.
     This is for example useful if the caller wants another value for
     K because the last returned one yielded an R of 0.  Because this
     is very unlikely we implement it in a straightforward way.  */
  if (extraloops)
    {
      extraloops--;

      /* K = HMAC_K(V || 0x00) */
      rc = _gcry_md_setkey (hd, K, hlen);
      if (rc)
        goto leave;
      _gcry_md_write (hd, V, hlen);
      _gcry_md_write (hd, "", 1);
      memcpy (K, _gcry_md_read (hd, 0), hlen);

      /* V = HMAC_K(V) */
      rc = _gcry_md_setkey (hd, K, hlen);
      if (rc)
        goto leave;
      _gcry_md_write (hd, V, hlen);
      memcpy (V, _gcry_md_read (hd, 0), hlen);

      goto again;
    }

  /* log_mpidump ("  k", k); */

 leave:
  xfree (t);
  _gcry_md_close (hd);
  xfree (h1_buf);
  xfree (x_buf);
  xfree (K);
  xfree (V);

  if (rc)
    mpi_free (k);
  else
    *r_k = k;
  return rc;
}