/* 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;

}