int dsa_internal_paramgen()

in crypto/dsa/dsa.c [239:500]
201 lines of code
62 McCabe index (conditional complexity)

int dsa_internal_paramgen(DSA *dsa, size_t bits, const EVP_MD *evpmd,
                          const unsigned char *seed_in, size_t seed_len,
                          int *out_counter, unsigned long *out_h,
                          BN_GENCB *cb)
{
  if (bits > OPENSSL_DSA_MAX_MODULUS_BITS) {
    OPENSSL_PUT_ERROR(DSA, DSA_R_INVALID_PARAMETERS);
    return 0;
  }

  int ok = 0;
  unsigned char seed[SHA256_DIGEST_LENGTH];
  unsigned char md[SHA256_DIGEST_LENGTH];
  unsigned char buf[SHA256_DIGEST_LENGTH], buf2[SHA256_DIGEST_LENGTH];
  BIGNUM *r0, *W, *X, *c, *test;
  BIGNUM *g = NULL, *q = NULL, *p = NULL;
  BN_MONT_CTX *mont = NULL;
  int k, n = 0, m = 0;
  int counter = 0;
  int r = 0;
  BN_CTX *ctx = NULL;
  unsigned int h = 2;
  const size_t qsize = EVP_MD_size(evpmd);

  if (bits < 512) {
    bits = 512;
  }

  bits = (bits + 63) / 64 * 64;

  if (seed_in != NULL) {
    if (seed_len < qsize) {
      return 0;
    }
    if (seed_len > qsize) {
      // Only consume as much seed as is expected.
      seed_len = qsize;
    }
    OPENSSL_memcpy(seed, seed_in, seed_len);
  }

  ctx = BN_CTX_new();
  if (ctx == NULL) {
    goto err;
  }
  BN_CTX_start(ctx);

  r0 = BN_CTX_get(ctx);
  g = BN_CTX_get(ctx);
  W = BN_CTX_get(ctx);
  q = BN_CTX_get(ctx);
  X = BN_CTX_get(ctx);
  c = BN_CTX_get(ctx);
  p = BN_CTX_get(ctx);
  test = BN_CTX_get(ctx);

  if (test == NULL || !BN_lshift(test, BN_value_one(), bits - 1)) {
    goto err;
  }

  for (;;) {
    // Find q.
    for (;;) {
      // step 1
      if (!BN_GENCB_call(cb, BN_GENCB_GENERATED, m++)) {
        goto err;
      }

      int use_random_seed = (seed_in == NULL);
      if (use_random_seed) {
        if (!RAND_bytes(seed, qsize)) {
          goto err;
        }
        // DSA parameters are public.
        CONSTTIME_DECLASSIFY(seed, qsize);
      } else {
        // If we come back through, use random seed next time.
        seed_in = NULL;
      }
      OPENSSL_memcpy(buf, seed, qsize);
      OPENSSL_memcpy(buf2, seed, qsize);
      // precompute "SEED + 1" for step 7:
      for (size_t i = qsize - 1; i < qsize; i--) {
        buf[i]++;
        if (buf[i] != 0) {
          break;
        }
      }

      // step 2
      if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL) ||
          !EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL)) {
        goto err;
      }
      for (size_t i = 0; i < qsize; i++) {
        md[i] ^= buf2[i];
      }

      // step 3
      md[0] |= 0x80;
      md[qsize - 1] |= 0x01;
      if (!BN_bin2bn(md, qsize, q)) {
        goto err;
      }

      // step 4
      r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx, use_random_seed, cb);
      if (r > 0) {
        break;
      }
      if (r != 0) {
        goto err;
      }

      // do a callback call
      // step 5
    }

    if (!BN_GENCB_call(cb, 2, 0) || !BN_GENCB_call(cb, 3, 0)) {
      goto err;
    }

    // step 6
    counter = 0;
    // "offset = 2"

    n = (bits - 1) / 160;

    for (;;) {
      if ((counter != 0) && !BN_GENCB_call(cb, BN_GENCB_GENERATED, counter)) {
        goto err;
      }

      // step 7
      BN_zero(W);
      // now 'buf' contains "SEED + offset - 1"
      for (k = 0; k <= n; k++) {
        // obtain "SEED + offset + k" by incrementing:
        for (size_t i = qsize - 1; i < qsize; i--) {
          buf[i]++;
          if (buf[i] != 0) {
            break;
          }
        }

        if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL)) {
          goto err;
        }

        // step 8
        if (!BN_bin2bn(md, qsize, r0) ||
            !BN_lshift(r0, r0, (qsize << 3) * k) ||
            !BN_add(W, W, r0)) {
          goto err;
        }
      }

      // more of step 8
      if (!BN_mask_bits(W, bits - 1) ||
          !BN_copy(X, W) ||
          !BN_add(X, X, test)) {
        goto err;
      }

      // step 9
      if (!BN_lshift1(r0, q) ||
          !BN_mod(c, X, r0, ctx) ||
          !BN_sub(r0, c, BN_value_one()) ||
          !BN_sub(p, X, r0)) {
        goto err;
      }

      // step 10
      if (BN_cmp(p, test) >= 0) {
        // step 11
        r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
        if (r > 0) {
          goto end;  // found it
        }
        if (r != 0) {
          goto err;
        }
      }

      // step 13
      counter++;
      // "offset = offset + n + 1"

      // step 14
      if (counter >= 4096) {
        break;
      }
    }
  }
end:
  if (!BN_GENCB_call(cb, 2, 1)) {
    goto err;
  }

  // We now need to generate g
  // Set r0=(p-1)/q
  if (!BN_sub(test, p, BN_value_one()) ||
      !BN_div(r0, NULL, test, q, ctx)) {
    goto err;
  }

  mont = BN_MONT_CTX_new_for_modulus(p, ctx);
  if (mont == NULL ||
      !BN_set_word(test, h)) {
    goto err;
  }

  for (;;) {
    // g=test^r0%p
    if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont)) {
      goto err;
    }
    if (!BN_is_one(g)) {
      break;
    }
    if (!BN_add(test, test, BN_value_one())) {
      goto err;
    }
    h++;
  }

  if (!BN_GENCB_call(cb, 3, 1)) {
    goto err;
  }

  ok = 1;

err:
  if (ok) {
    BN_free(dsa->p);
    BN_free(dsa->q);
    BN_free(dsa->g);
    dsa->p = BN_dup(p);
    dsa->q = BN_dup(q);
    dsa->g = BN_dup(g);
    if (dsa->p == NULL || dsa->q == NULL || dsa->g == NULL) {
      ok = 0;
      goto err;
    }
    if (out_counter != NULL) {
      *out_counter = counter;
    }
    if (out_h != NULL) {
      *out_h = h;
    }
  }

  if (ctx) {
    BN_CTX_end(ctx);
    BN_CTX_free(ctx);
  }

  BN_MONT_CTX_free(mont);
  OPENSSL_cleanse(seed, SHA256_DIGEST_LENGTH);

  return ok;
}