


#include <stdio.h>
#include <openssl/bn.h>
#include "bn_local.h"
#include "crypto/bn.h"
#include "internal/nelem.h"

#if BN_BITS2 == 64
# define BN_DEF(lo, hi) (BN_ULONG)hi<<32|lo
#else
# define BN_DEF(lo, hi) lo, hi
#endif


static const BN_ULONG inv_sqrt_2_val[] = {
    BN_DEF(0x83339916UL, 0xED17AC85UL), BN_DEF(0x893BA84CUL, 0x1D6F60BAUL),
    BN_DEF(0x754ABE9FUL, 0x597D89B3UL), BN_DEF(0xF9DE6484UL, 0xB504F333UL)
};

const BIGNUM ossl_bn_inv_sqrt_2 = {
    (BN_ULONG *)inv_sqrt_2_val,
    OSSL_NELEM(inv_sqrt_2_val),
    OSSL_NELEM(inv_sqrt_2_val),
    0,
    BN_FLG_STATIC_DATA
};


static int bn_rsa_fips186_5_aux_prime_MR_rounds(int nbits)
{
    if (nbits >= 4096)
        return 44;
    if (nbits >= 3072)
        return 41;
    if (nbits >= 2048)
        return 38;
    return 0; 
}


static int bn_rsa_fips186_5_prime_MR_rounds(int nbits)
{
    if (nbits >= 3072)
        return 4;
    if (nbits >= 2048)
        return 5;
    return 0; 
}


static int bn_rsa_fips186_5_aux_prime_min_size(int nbits)
{
    if (nbits >= 4096)
        return 201;
    if (nbits >= 3072)
        return 171;
    if (nbits >= 2048)
        return 141;
    return 0;
}


static int bn_rsa_fips186_5_aux_prime_max_sum_size_for_prob_primes(int nbits)
{
    if (nbits >= 4096)
        return 2030;
    if (nbits >= 3072)
        return 1518;
    if (nbits >= 2048)
        return 1007;
    return 0;
}


static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1,
                                                BIGNUM *p1, BN_CTX *ctx,
                                                int rounds,
                                                BN_GENCB *cb)
{
    int ret = 0;
    int i = 0;
    int tmp = 0;

    if (BN_copy(p1, Xp1) == NULL)
        return 0;
    BN_set_flags(p1, BN_FLG_CONSTTIME);

    
    for (;;) {
        i++;
        BN_GENCB_call(cb, 0, i);
        
        tmp = ossl_bn_check_generated_prime(p1, rounds, ctx, cb);
        if (tmp > 0)
            break;
        if (tmp < 0)
            goto err;
        
        if (!BN_add_word(p1, 2))
            goto err;
    }
    BN_GENCB_call(cb, 2, i);
    ret = 1;
err:
    return ret;
}


int ossl_bn_rsa_fips186_4_gen_prob_primes(BIGNUM *p, BIGNUM *Xpout,
                                          BIGNUM *p1, BIGNUM *p2,
                                          const BIGNUM *Xp, const BIGNUM *Xp1,
                                          const BIGNUM *Xp2, int nlen,
                                          const BIGNUM *e, BN_CTX *ctx,
                                          BN_GENCB *cb)
{
    int ret = 0;
    BIGNUM *p1i = NULL, *p2i = NULL, *Xp1i = NULL, *Xp2i = NULL;
    int bitlen, rounds;

    if (p == NULL || Xpout == NULL)
        return 0;

    BN_CTX_start(ctx);

    p1i = (p1 != NULL) ? p1 : BN_CTX_get(ctx);
    p2i = (p2 != NULL) ? p2 : BN_CTX_get(ctx);
    Xp1i = (Xp1 != NULL) ? (BIGNUM *)Xp1 : BN_CTX_get(ctx);
    Xp2i = (Xp2 != NULL) ? (BIGNUM *)Xp2 : BN_CTX_get(ctx);
    if (p1i == NULL || p2i == NULL || Xp1i == NULL || Xp2i == NULL)
        goto err;

    bitlen = bn_rsa_fips186_5_aux_prime_min_size(nlen);
    if (bitlen == 0)
        goto err;
    rounds = bn_rsa_fips186_5_aux_prime_MR_rounds(nlen);

    
    if (Xp1 == NULL) {
        
        if (!BN_priv_rand_ex(Xp1i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
                             0, ctx))
            goto err;
    }
    
    if (Xp2 == NULL) {
        
        if (!BN_priv_rand_ex(Xp2i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
                             0, ctx))
            goto err;
    }

    
    if (!bn_rsa_fips186_4_find_aux_prob_prime(Xp1i, p1i, ctx, rounds, cb)
            || !bn_rsa_fips186_4_find_aux_prob_prime(Xp2i, p2i, ctx, rounds, cb))
        goto err;
    
    if ((BN_num_bits(p1i) + BN_num_bits(p2i)) >=
            bn_rsa_fips186_5_aux_prime_max_sum_size_for_prob_primes(nlen))
        goto err;
    
    if (!ossl_bn_rsa_fips186_4_derive_prime(p, Xpout, Xp, p1i, p2i, nlen, e,
                                            ctx, cb))
        goto err;
    ret = 1;
err:
    
    if (p1 == NULL)
        BN_clear(p1i);
    if (p2 == NULL)
        BN_clear(p2i);
    if (Xp1 == NULL)
        BN_clear(Xp1i);
    if (Xp2 == NULL)
        BN_clear(Xp2i);
    BN_CTX_end(ctx);
    return ret;
}


int ossl_bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin,
                                       const BIGNUM *r1, const BIGNUM *r2,
                                       int nlen, const BIGNUM *e,
                                       BN_CTX *ctx, BN_GENCB *cb)
{
    int ret = 0;
    int i, imax, rounds;
    int bits = nlen >> 1;
    BIGNUM *tmp, *R, *r1r2x2, *y1, *r1x2;
    BIGNUM *base, *range;

    BN_CTX_start(ctx);

    base = BN_CTX_get(ctx);
    range = BN_CTX_get(ctx);
    R = BN_CTX_get(ctx);
    tmp = BN_CTX_get(ctx);
    r1r2x2 = BN_CTX_get(ctx);
    y1 = BN_CTX_get(ctx);
    r1x2 = BN_CTX_get(ctx);
    if (r1x2 == NULL)
        goto err;

    if (Xin != NULL && BN_copy(X, Xin) == NULL)
        goto err;

    
    if (Xin == NULL) {
        if (bits < BN_num_bits(&ossl_bn_inv_sqrt_2))
            goto err;
        if (!BN_lshift(base, &ossl_bn_inv_sqrt_2,
                       bits - BN_num_bits(&ossl_bn_inv_sqrt_2))
            || !BN_lshift(range, BN_value_one(), bits)
            || !BN_sub(range, range, base))
            goto err;
    }

    
    if (!(BN_lshift1(r1x2, r1)
            && (BN_mod_inverse(tmp, r1x2, r2, ctx) != NULL)
            
            && (BN_mod_inverse(R, r2, r1x2, ctx) != NULL)
            && BN_mul(R, R, r2, ctx) 
            && BN_mul(tmp, tmp, r1x2, ctx) 
            && BN_sub(R, R, tmp)
            
            && BN_mul(r1r2x2, r1x2, r2, ctx)))
        goto err;
    
    if (BN_is_negative(R) && !BN_add(R, R, r1r2x2))
        goto err;

    
    rounds = bn_rsa_fips186_5_prime_MR_rounds(nlen);
    imax = 20 * bits; 
    for (;;) {
        if (Xin == NULL) {
            
            if (!BN_priv_rand_range_ex(X, range, 0, ctx) || !BN_add(X, X, base))
                goto err;
        }
        
        if (!BN_mod_sub(Y, R, X, r1r2x2, ctx) || !BN_add(Y, Y, X))
            goto err;
        
        i = 0;
        for (;;) {
            
            if (BN_num_bits(Y) > bits) {
                if (Xin == NULL)
                    break; 
                else
                    goto err; 
            }
            BN_GENCB_call(cb, 0, 2);

            
            if (BN_copy(y1, Y) == NULL
                    || !BN_sub_word(y1, 1))
                goto err;

            if (BN_are_coprime(y1, e, ctx)) {
                int rv = ossl_bn_check_generated_prime(Y, rounds, ctx, cb);

                if (rv > 0)
                    goto end;
                if (rv < 0)
                    goto err;
            }
            
            if (++i >= imax) {
                ERR_raise(ERR_LIB_BN, BN_R_NO_PRIME_CANDIDATE);
                goto err;
            }
            if (!BN_add(Y, Y, r1r2x2))
                goto err;
        }
    }
end:
    ret = 1;
    BN_GENCB_call(cb, 3, 0);
err:
    BN_clear(y1);
    BN_CTX_end(ctx);
    return ret;
}
