path: root/crypto/rsa/rsa_sp800_56b_gen.c

/*
 * Copyright 2018-2020 The OpenSSL Project Authors. All Rights Reserved.
 * Copyright (c) 2018-2019, Oracle and/or its affiliates.  All rights reserved.
 *
 * Licensed under the Apache License 2.0 (the "License").  You may not use
 * this file except in compliance with the License.  You can obtain a copy
 * in the file LICENSE in the source distribution or at
 * https://www.openssl.org/source/license.html
 */

#include <openssl/err.h>
#include <openssl/bn.h>
#include <openssl/core.h>
#include "crypto/bn.h"
#include "crypto/security_bits.h"
#include "rsa_local.h"

#define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048
#define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112
#define RSA_FIPS1864_MAX_KEYGEN_STRENGTH 256

/*
 * Generate probable primes 'p' & 'q'. See FIPS 186-4 Section B.3.6
 * "Generation of Probable Primes with Conditions Based on Auxiliary Probable
 * Primes".
 *
 * Params:
 *     rsa  Object used to store primes p & q.
 *     test Object used for CAVS testing only.that contains..
 *       p1, p2 The returned auxiliary primes for p.
 *              If NULL they are not returned.
 *       Xpout An optionally returned random number used during generation of p.
 *       Xp An optional passed in value (that is random number used during
 *          generation of p).
 *       Xp1, Xp2 Optionally passed in randomly generated numbers from which
 *                auxiliary primes p1 & p2 are calculated. If NULL these values
 *                are generated internally.
 *       q1, q2 The returned auxiliary primes for q.
 *              If NULL they are not returned.
 *       Xqout An optionally returned random number used during generation of q.
 *       Xq An optional passed in value (that is random number used during
 *          generation of q).
 *       Xq1, Xq2 Optionally passed in randomly generated numbers from which
 *                auxiliary primes q1 & q2 are calculated. If NULL these values
 *                are generated internally.
 *     nbits The key size in bits (The size of the modulus n).
 *     e The public exponent.
 *     ctx A BN_CTX object.
 *     cb An optional BIGNUM callback.
 * Returns: 1 if successful, or  0 otherwise.
 * Notes:
 *     p1, p2, q1, q2, Xpout, Xqout are returned if they are not NULL.
 *     Xp, Xp1, Xp2, Xq, Xq1, Xq2 are optionally passed in.
 *     (Required for CAVS testing).
 */
int ossl_rsa_fips186_4_gen_prob_primes(RSA *rsa, RSA_ACVP_TEST *test,
                                       int nbits, const BIGNUM *e, BN_CTX *ctx,
                                       BN_GENCB *cb)
{
    int ret = 0, ok;
    /* Temp allocated BIGNUMS */
    BIGNUM *Xpo = NULL, *Xqo = NULL, *tmp = NULL;
    /* Intermediate BIGNUMS that can be returned for testing */
    BIGNUM *p1 = NULL, *p2 = NULL;
    BIGNUM *q1 = NULL, *q2 = NULL;
    /* Intermediate BIGNUMS that can be input for testing */
    BIGNUM *Xpout = NULL, *Xqout = NULL;
    BIGNUM *Xp = NULL, *Xp1 = NULL, *Xp2 = NULL;
    BIGNUM *Xq = NULL, *Xq1 = NULL, *Xq2 = NULL;

#if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS)
    if (test != NULL) {
        Xp1 = test->Xp1;
        Xp2 = test->Xp2;
        Xq1 = test->Xq1;
        Xq2 = test->Xq2;
        Xp = test->Xp;
        Xq = test->Xq;
        p1 = test->p1;
        p2 = test->p2;
        q1 = test->q1;
        q2 = test->q2;
    }
#endif

    /* (Step 1) Check key length
     * NOTE: SP800-131A Rev1 Disallows key lengths of < 2048 bits for RSA
     * Signature Generation and Key Agree/Transport.
     */
    if (nbits < RSA_FIPS1864_MIN_KEYGEN_KEYSIZE) {
        ERR_raise(ERR_LIB_RSA, RSA_R_KEY_SIZE_TOO_SMALL);
        return 0;
    }

    if (!ossl_rsa_check_public_exponent(e)) {
        ERR_raise(ERR_LIB_RSA, RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
        return 0;
    }

    /* (Step 3) Determine strength and check rand generator strength is ok -
     * this step is redundant because the generator always returns a higher
     * strength than is required.
     */

    BN_CTX_start(ctx);
    tmp = BN_CTX_get(ctx);
    Xpo = (Xpout != NULL) ? Xpout : BN_CTX_get(ctx);
    Xqo = (Xqout != NULL) ? Xqout : BN_CTX_get(ctx);
    if (tmp == NULL || Xpo == NULL || Xqo == NULL)
        goto err;
    BN_set_flags(Xpo, BN_FLG_CONSTTIME);
    BN_set_flags(Xqo, BN_FLG_CONSTTIME);

    if (rsa->p == NULL)
        rsa->p = BN_secure_new();
    if (rsa->q == NULL)
        rsa->q = BN_secure_new();
    if (rsa->p == NULL || rsa->q == NULL)
        goto err;
    BN_set_flags(rsa->p, BN_FLG_CONSTTIME);
    BN_set_flags(rsa->q, BN_FLG_CONSTTIME);

    /* (Step 4) Generate p, Xp */
    if (!bn_rsa_fips186_4_gen_prob_primes(rsa->p, Xpo, p1, p2, Xp, Xp1, Xp2,
                                          nbits, e, ctx, cb))
        goto err;
    for(;;) {
        /* (Step 5) Generate q, Xq*/
        if (!bn_rsa_fips186_4_gen_prob_primes(rsa->q, Xqo, q1, q2, Xq, Xq1,
                                              Xq2, nbits, e, ctx, cb))
            goto err;

        /* (Step 6) |Xp - Xq| > 2^(nbitlen/2 - 100) */
        ok = ossl_rsa_check_pminusq_diff(tmp, Xpo, Xqo, nbits);
        if (ok < 0)
            goto err;
        if (ok == 0)
            continue;

        /* (Step 6) |p - q| > 2^(nbitlen/2 - 100) */
        ok = ossl_rsa_check_pminusq_diff(tmp, rsa->p, rsa->q, nbits);
        if (ok < 0)
            goto err;
        if (ok == 0)
            continue;
        break; /* successfully finished */
    }
    rsa->dirty_cnt++;
    ret = 1;
err:
    /* Zeroize any internally generated values that are not returned */
    if (Xpo != Xpout)
        BN_clear(Xpo);
    if (Xqo != Xqout)
        BN_clear(Xqo);
    BN_clear(tmp);

    BN_CTX_end(ctx);
    return ret;
}

/*
 * Validates the RSA key size based on the target strength.
 * See SP800-56Br1 6.3.1.1 (Steps 1a-1b)
 *
 * Params:
 *     nbits The key size in bits.
 *     strength The target strength in bits. -1 means the target
 *              strength is unknown.
 * Returns: 1 if the key size matches the target strength, or 0 otherwise.
 */
int ossl_rsa_sp800_56b_validate_strength(int nbits, int strength)
{
    int s = (int)ifc_ffc_compute_security_bits(nbits);
#ifdef FIPS_MODULE
    if (s < RSA_FIPS1864_MIN_KEYGEN_STRENGTH
            || s > RSA_FIPS1864_MAX_KEYGEN_STRENGTH) {
        ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_MODULUS);
        return 0;
    }
#endif
    if (strength != -1 && s != strength) {
        ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_STRENGTH);
        return 0;
    }
    return 1;
}

/*
 *
 * Using p & q, calculate other required parameters such as n, d.
 * as well as the CRT parameters dP, dQ, qInv.
 *
 * See SP800-56Br1
 *   6.3.1.1 rsakpg1 - basic (Steps 3-4)
 *   6.3.1.3 rsakpg1 - crt   (Step 5)
 *
 * Params:
 *     rsa An rsa object.
 *     nbits The key size.
 *     e The public exponent.
 *     ctx A BN_CTX object.
 * Notes:
 *   There is a small chance that the generated d will be too small.
 * Returns: -1 = error,
 *           0 = d is too small,
 *           1 = success.
 */
int ossl_rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
                                             const BIGNUM *e, BN_CTX *ctx)
{
    int ret = -1;
    BIGNUM *p1, *q1, *lcm, *p1q1, *gcd;

    BN_CTX_start(ctx);
    p1 = BN_CTX_get(ctx);
    q1 = BN_CTX_get(ctx);
    lcm = BN_CTX_get(ctx);
    p1q1 = BN_CTX_get(ctx);
    gcd = BN_CTX_get(ctx);
    if (gcd == NULL)
        goto err;

    BN_set_flags(p1, BN_FLG_CONSTTIME);
    BN_set_flags(q1, BN_FLG_CONSTTIME);
    BN_set_flags(lcm, BN_FLG_CONSTTIME);
    BN_set_flags(p1q1, BN_FLG_CONSTTIME);
    BN_set_flags(gcd, BN_FLG_CONSTTIME);

    /* LCM((p-1, q-1)) */
    if (ossl_rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) != 1)
        goto err;

    /* copy e */
    BN_free(rsa->e);
    rsa->e = BN_dup(e);
    if (rsa->e == NULL)
        goto err;

    BN_clear_free(rsa->d);
    /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
    rsa->d = BN_secure_new();
    if (rsa->d == NULL)
        goto err;
    BN_set_flags(rsa->d, BN_FLG_CONSTTIME);
    if (BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL)
        goto err;

    /* (Step 3) return an error if d is too small */
    if (BN_num_bits(rsa->d) <= (nbits >> 1)) {
        ret = 0;
        goto err;
    }

    /* (Step 4) n = pq */
    if (rsa->n == NULL)
        rsa->n = BN_new();
    if (rsa->