[thirdparty/openssl.git] / crypto / bn / bn_rsa_fips186_4.c

/*
 * Copyright 2018-2019 The OpenSSL Project Authors. All Rights Reserved.
 * Copyright (c) 2018-2019, Oracle and/or its affiliates.  All rights reserved.
 *
 * Licensed under the OpenSSL license (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
 */

/*
 * According to NIST SP800-131A "Transitioning the use of cryptographic
 * algorithms and key lengths" Generation of 1024 bit RSA keys are no longer
 * allowed for signatures (Table 2) or key transport (Table 5). In the code
 * below any attempt to generate 1024 bit RSA keys will result in an error (Note
 * that digital signature verification can still use deprecated 1024 bit keys).
 *
 * Also see FIPS1402IG A.14
 * FIPS 186-4 relies on the use of the auxiliary primes p1, p2, q1 and q2 that
 * must be generated before the module generates the RSA primes p and q.
 * Table B.1 in FIPS 186-4 specifies, for RSA modulus lengths of 2048 and
 * 3072 bits only, the min/max total length of the auxiliary primes.
 * When implementing the RSA signature generation algorithm
 * with other approved RSA modulus sizes, the vendor shall use the limitations
 * from Table B.1 that apply to the longest RSA modulus shown in Table B.1 of
 * FIPS 186-4 whose length does not exceed that of the implementation's RSA
 * modulus. In particular, when generating the primes for the 4096-bit RSA
 * modulus the limitations stated for the 3072-bit modulus shall apply.
 */
#include <stdio.h>
#include <openssl/bn.h>
#include "bn_local.h"
#include "crypto/bn.h"

/*
 * FIPS 186-4 Table B.1. "Min length of auxiliary primes p1, p2, q1, q2".
 *
 * Params:
 *     nbits The key size in bits.
 * Returns:
 *     The minimum size of the auxiliary primes or 0 if nbits is invalid.
 */
static int bn_rsa_fips186_4_aux_prime_min_size(int nbits)
{
    if (nbits >= 3072)
        return 171;
    if (nbits == 2048)
        return 141;
    return 0;
}

/*
 * FIPS 186-4 Table B.1 "Maximum length of len(p1) + len(p2) and
 * len(q1) + len(q2) for p,q Probable Primes".
 *
 * Params:
 *     nbits The key size in bits.
 * Returns:
 *     The maximum length or 0 if nbits is invalid.
 */
static int bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(int nbits)
{
    if (nbits >= 3072)
        return 1518;
    if (nbits == 2048)
        return 1007;
    return 0;
}

/*
 * Find the first odd integer that is a probable prime.
 *
 * See section FIPS 186-4 B.3.6 (Steps 4.2/5.2).
 *
 * Params:
 *     Xp1 The passed in starting point to find a probably prime.
 *     p1 The returned probable prime (first odd integer >= Xp1)
 *     ctx A BN_CTX object.
 *     cb An optional BIGNUM callback.
 * Returns: 1 on success otherwise it returns 0.
 */
static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1,
                                                BIGNUM *p1, BN_CTX *ctx,
                                                BN_GENCB *cb)
{
    int ret = 0;
    int i = 0;

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

    /* Find the first odd number >= Xp1 that is probably prime */
    for(;;) {
        i++;
        BN_GENCB_call(cb, 0, i);
        /* MR test with trial division */
        if (BN_check_prime(p1, ctx, cb))
            break;
        /* Get next odd number */
        if (!BN_add_word(p1, 2))
            goto err;
    }
    BN_GENCB_call(cb, 2, i);
    ret = 1;
err:
    return ret;
}

/*
 * Generate a probable prime (p or q).
 *
 * See FIPS 186-4 B.3.6 (Steps 4 & 5)
 *
 * Params:
 *     p The returned probable prime.
 *     Xpout An optionally returned random number used during generation of p.
 *     p1, p2 The returned auxiliary primes. If NULL they are not returned.
 *     Xp An optional passed in value (that is random number used during
 *        generation of p).
 *     Xp1, Xp2 Optional passed in values that are normally generated
 *              internally. Used to find p1, p2.
 *     nlen The bit length of the modulus (the key size).
 *     e The public exponent.
 *     ctx A BN_CTX object.
 *     cb An optional BIGNUM callback.
 * Returns: 1 on success otherwise it returns 0.
 */
int 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;

    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_4_aux_prime_min_size(nlen);
    if (bitlen == 0)
        goto err;

    /* (Steps 4.1/5.1): Randomly generate Xp1 if it is not passed in */
    if (Xp1 == NULL) {
        /* Set the top and bottom bits to make it odd and the correct size */
        if (!BN_priv_rand_ex(Xp1i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
                             ctx))
            goto err;
    }
    /* (Steps 4.1/5.1): Randomly generate Xp2 if it is not passed in */
    if (Xp2 == NULL) {
        /* Set the top and bottom bits to make it odd and the correct size */
        if (!BN_priv_rand_ex(Xp2i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
                             ctx))
            goto err;
    }

    /* (Steps 4.2/5.2) - find first auxiliary probable primes */
    if (!bn_rsa_fips186_4_find_aux_prob_prime(Xp1i, p1i, ctx, cb)
            || !bn_rsa_fips186_4_find_aux_prob_prime(Xp2i, p2i, ctx, cb))
        goto err;
    /* (Table B.1) auxiliary prime Max length check */
    if ((BN_num_bits(p1i) + BN_num_bits(p2i)) >=
            bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(nlen))
        goto err;
    /* (Steps 4.3/5.3) - generate prime */
    if (!bn_rsa_fips186_4_derive_prime(p, Xpout, Xp, p1i, p2i, nlen, e, ctx, cb))
        goto err;
    ret = 1;
err:
    /* Zeroize any internally generated values that are not returned */
    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;
}

/*
 * Constructs a probable prime (a candidate for p or q) using 2 auxiliary
 * prime numbers and the Chinese Remainder Theorem.
 *
 * See FIPS 186-4 C.9 "Compute a Probable Prime Factor Based on Auxiliary
 * Primes". Used by FIPS 186-4 B.3.6 Section (4.3) for p and Section (5.3) for q.
 *
 * Params:
 *     Y The returned prime factor (private_prime_factor) of the modulus n.
 *     X The returned random number used during generation of the prime factor.
 *     Xin An optional passed in value for X used for testing purposes.
 *     r1 An auxiliary prime.
 *     r2 An auxiliary prime.
 *     nlen The desired length of n (the RSA modulus).
 *     e The public exponent.
 *     ctx A BN_CTX object.
 *     cb An optional BIGNUM callback object.
 * Returns: 1 on success otherwise it returns 0.
 * Assumptions:
 *     Y, X, r1, r2, e are not NULL.
 */
int 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;
    int bits = nlen >> 1;
    BIGNUM *tmp, *R, *r1r2x2, *y1, *r1x2;

    BN_CTX_start(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 (!(BN_lshift1(r1x2, r1)
            /* (Step 1) GCD(2r1, r2) = 1 */
            && BN_gcd(tmp, r1x2, r2, ctx)
            && BN_is_one(tmp)
            /* (Step 2) R = ((r2^-1 mod 2r1) * r2) - ((2r1^-1 mod r2)*2r1) */
            && BN_mod_inverse(R, r2, r1x2, ctx)
            && BN_mul(R, R, r2, ctx) /* R = (r2^-1 mod 2r1) * r2 */
            && BN_mod_inverse(tmp, r1x2, r2, ctx)
            && BN_mul(tmp, tmp, r1x2, ctx) /* tmp = (2r1^-1 mod r2)*2r1 */
            && BN_sub(R, R, tmp)
            /* Calculate 2r1r2 */
            && BN_mul(r1r2x2, r1x2, r2, ctx)))
        goto err;
    /* Make positive by adding the modulus */
    if (BN_is_negative(R) && !BN_add(R, R, r1r2x2))
        goto err;

    imax = 5 * bits; /* max = 5/2 * nbits */
    for (;;) {
        if (Xin == NULL) {
            /*
             * (Step 3) Choose Random X such that
             *    sqrt(2) * 2^(nlen/2-1) < Random X < (2^(nlen/2)) - 1.
             *
             * For the lower bound:
             *   sqrt(2) * 2^(nlen/2 - 1) == sqrt(2)/2 * 2^(nlen/2)
             *   where sqrt(2)/2 = 0.70710678.. = 0.B504FC33F9DE...
             *   so largest number will have B5... as the top byte
             *   Setting the top 2 bits gives 0xC0.
             */
            if (!BN_priv_rand_ex(X, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ANY,
                                 ctx))
                goto end;
        }
        /* (Step 4) Y = X + ((R - X) mod 2r1r2) */
        if (!BN_mod_sub(Y, R, X, r1r2x2, ctx) || !BN_add(Y, Y, X))
            goto err;
        /* (Step 5) */
        i = 0;
        for (;;) {
            /* (Step 6) */
            if (BN_num_bits(Y) > bits) {
                if (Xin == NULL)
                    break; /* Randomly Generated X so Go back to Step 3 */
                else
                    goto err; /* X is not random so it will always fail */
            }
            BN_GENCB_call(cb, 0, 2);

            /* (Step 7) If GCD(Y-1) == 1 & Y is probably prime then return Y */
            if (BN_copy(y1, Y) == NULL
                    || !BN_sub_word(y1, 1)
                    || !BN_gcd(tmp, y1, e, ctx))
                goto err;
            if (BN_is_one(tmp) && BN_check_prime(Y, ctx, cb))
                goto end;
            /* (Step 8-10) */
            if (++i >= imax || !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;
}
Commit	Line	Data
8240d5fa SL	1	/*
	2	* Copyright 2018-2019 The OpenSSL Project Authors. All Rights Reserved.
	3	* Copyright (c) 2018-2019, Oracle and/or its affiliates. All rights reserved.
	4	*
	5	* Licensed under the OpenSSL license (the "License"). You may not use
	6	* this file except in compliance with the License. You can obtain a copy
	7	* in the file LICENSE in the source distribution or at
	8	* https://www.openssl.org/source/license.html
	9	*/
	10
	11	/*
	12	* According to NIST SP800-131A "Transitioning the use of cryptographic
	13	* algorithms and key lengths" Generation of 1024 bit RSA keys are no longer
	14	* allowed for signatures (Table 2) or key transport (Table 5). In the code
	15	* below any attempt to generate 1024 bit RSA keys will result in an error (Note
	16	* that digital signature verification can still use deprecated 1024 bit keys).
	17	*
	18	* Also see FIPS1402IG A.14
	19	* FIPS 186-4 relies on the use of the auxiliary primes p1, p2, q1 and q2 that
	20	* must be generated before the module generates the RSA primes p and q.
	21	* Table B.1 in FIPS 186-4 specifies, for RSA modulus lengths of 2048 and
	22	* 3072 bits only, the min/max total length of the auxiliary primes.
	23	* When implementing the RSA signature generation algorithm
	24	* with other approved RSA modulus sizes, the vendor shall use the limitations
	25	* from Table B.1 that apply to the longest RSA modulus shown in Table B.1 of
	26	* FIPS 186-4 whose length does not exceed that of the implementation's RSA
	27	* modulus. In particular, when generating the primes for the 4096-bit RSA
	28	* modulus the limitations stated for the 3072-bit modulus shall apply.
	29	*/
	30	#include <stdio.h>
	31	#include <openssl/bn.h>
706457b7	32	#include "bn_local.h"
25f2138b	33	#include "crypto/bn.h"
8240d5fa SL	34
	35	/*
	36	* FIPS 186-4 Table B.1. "Min length of auxiliary primes p1, p2, q1, q2".
	37	*
	38	* Params:
	39	* nbits The key size in bits.
	40	* Returns:
	41	* The minimum size of the auxiliary primes or 0 if nbits is invalid.
	42	*/
	43	static int bn_rsa_fips186_4_aux_prime_min_size(int nbits)
	44	{
	45	if (nbits >= 3072)
	46	return 171;
	47	if (nbits == 2048)
	48	return 141;
	49	return 0;
	50	}
	51
	52	/*
	53	* FIPS 186-4 Table B.1 "Maximum length of len(p1) + len(p2) and
	54	* len(q1) + len(q2) for p,q Probable Primes".
	55	*
	56	* Params:
	57	* nbits The key size in bits.
	58	* Returns:
	59	* The maximum length or 0 if nbits is invalid.
	60	*/
	61	static int bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(int nbits)
	62	{
	63	if (nbits >= 3072)
	64	return 1518;
	65	if (nbits == 2048)
	66	return 1007;
	67	return 0;
	68	}
	69
8240d5fa SL	70	/*
	71	* Find the first odd integer that is a probable prime.
	72	*
	73	* See section FIPS 186-4 B.3.6 (Steps 4.2/5.2).
	74	*
	75	* Params:
	76	* Xp1 The passed in starting point to find a probably prime.
	77	* p1 The returned probable prime (first odd integer >= Xp1)
	78	* ctx A BN_CTX object.
	79	* cb An optional BIGNUM callback.
	80	* Returns: 1 on success otherwise it returns 0.
	81	*/
	82	static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1,
	83	BIGNUM p1, BN_CTX ctx,
	84	BN_GENCB *cb)
	85	{
	86	int ret = 0;
	87	int i = 0;
8240d5fa	88
42619397	89	if (BN_copy(p1, Xp1) == NULL)
8240d5fa SL	90	return 0;
	91
	92	/* Find the first odd number >= Xp1 that is probably prime */
	93	for(;;) {
	94	i++;
	95	BN_GENCB_call(cb, 0, i);
	96	/* MR test with trial division */
42619397	97	if (BN_check_prime(p1, ctx, cb))
8240d5fa SL	98	break;
	99	/* Get next odd number */
	100	if (!BN_add_word(p1, 2))
	101	goto err;
	102	}
	103	BN_GENCB_call(cb, 2, i);
	104	ret = 1;
	105	err:
	106	return ret;
	107	}
	108
	109	/*
	110	* Generate a probable prime (p or q).
	111	*
	112	* See FIPS 186-4 B.3.6 (Steps 4 & 5)
	113	*
	114	* Params:
	115	* p The returned probable prime.
	116	* Xpout An optionally returned random number used during generation of p.
	117	* p1, p2 The returned auxiliary primes. If NULL they are not returned.
	118	* Xp An optional passed in value (that is random number used during
	119	* generation of p).
	120	* Xp1, Xp2 Optional passed in values that are normally generated
	121	* internally. Used to find p1, p2.
	122	* nlen The bit length of the modulus (the key size).
	123	* e The public exponent.
	124	* ctx A BN_CTX object.
	125	* cb An optional BIGNUM callback.
	126	* Returns: 1 on success otherwise it returns 0.
	127	*/
	128	int bn_rsa_fips186_4_gen_prob_primes(BIGNUM p, BIGNUM Xpout,
	129	BIGNUM p1, BIGNUM p2,
	130	const BIGNUM Xp, const BIGNUM Xp1,
	131	const BIGNUM *Xp2, int nlen,
	132	const BIGNUM e, BN_CTX ctx, BN_GENCB *cb)
	133	{
	134	int ret = 0;
	135	BIGNUM p1i = NULL, p2i = NULL, Xp1i = NULL, Xp2i = NULL;
	136	int bitlen;
	137
	138	if (p == NULL \|\| Xpout == NULL)
	139	return 0;
	140
	141	BN_CTX_start(ctx);
	142
	143	p1i = (p1 != NULL) ? p1 : BN_CTX_get(ctx);
	144	p2i = (p2 != NULL) ? p2 : BN_CTX_get(ctx);
	145	Xp1i = (Xp1 != NULL) ? (BIGNUM *)Xp1 : BN_CTX_get(ctx);
	146	Xp2i = (Xp2 != NULL) ? (BIGNUM *)Xp2 : BN_CTX_get(ctx);
	147	if (p1i == NULL \|\| p2i == NULL \|\| Xp1i == NULL \|\| Xp2i == NULL)
	148	goto err;
	149
	150	bitlen = bn_rsa_fips186_4_aux_prime_min_size(nlen);
	151	if (bitlen == 0)
	152	goto err;
	153
	154	/* (Steps 4.1/5.1): Randomly generate Xp1 if it is not passed in */
	155	if (Xp1 == NULL) {
	156	/* Set the top and bottom bits to make it odd and the correct size */
2934be91 MC	157	if (!BN_priv_rand_ex(Xp1i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
2934be91 MC	158	ctx))
8240d5fa SL	159	goto err;
	160	}
	161	/* (Steps 4.1/5.1): Randomly generate Xp2 if it is not passed in */
	162	if (Xp2 == NULL) {
	163	/* Set the top and bottom bits to make it odd and the correct size */
2934be91 MC	164	if (!BN_priv_rand_ex(Xp2i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
2934be91 MC	165	ctx))
8240d5fa SL	166	goto err;
	167	}
	168
	169	/* (Steps 4.2/5.2) - find first auxiliary probable primes */
	170	if (!bn_rsa_fips186_4_find_aux_prob_prime(Xp1i, p1i, ctx, cb)
	171	\|\| !bn_rsa_fips186_4_find_aux_prob_prime(Xp2i, p2i, ctx, cb))
	172	goto err;
	173	/* (Table B.1) auxiliary prime Max length check */
	174	if ((BN_num_bits(p1i) + BN_num_bits(p2i)) >=
	175	bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(nlen))
	176	goto err;
	177	/* (Steps 4.3/5.3) - generate prime */
	178	if (!bn_rsa_fips186_4_derive_prime(p, Xpout, Xp, p1i, p2i, nlen, e, ctx, cb))
	179	goto err;
	180	ret = 1;
	181	err:
	182	/* Zeroize any internally generated values that are not returned */
	183	if (p1 == NULL)
	184	BN_clear(p1i);
	185	if (p2 == NULL)
	186	BN_clear(p2i);
	187	if (Xp1 == NULL)
	188	BN_clear(Xp1i);
	189	if (Xp2 == NULL)
	190	BN_clear(Xp2i);
	191	BN_CTX_end(ctx);
	192	return ret;
	193	}
	194
	195	/*
	196	* Constructs a probable prime (a candidate for p or q) using 2 auxiliary
	197	* prime numbers and the Chinese Remainder Theorem.
	198	*
	199	* See FIPS 186-4 C.9 "Compute a Probable Prime Factor Based on Auxiliary
	200	* Primes". Used by FIPS 186-4 B.3.6 Section (4.3) for p and Section (5.3) for q.
	201	*
	202	* Params:
	203	* Y The returned prime factor (private_prime_factor) of the modulus n.
	204	* X The returned random number used during generation of the prime factor.
	205	* Xin An optional passed in value for X used for testing purposes.
	206	* r1 An auxiliary prime.
	207	* r2 An auxiliary prime.
	208	* nlen The desired length of n (the RSA modulus).
	209	* e The public exponent.
	210	* ctx A BN_CTX object.
	211	* cb An optional BIGNUM callback object.
	212	* Returns: 1 on success otherwise it returns 0.
	213	* Assumptions:
	214	* Y, X, r1, r2, e are not NULL.
	215	*/
	216	int bn_rsa_fips186_4_derive_prime(BIGNUM Y, BIGNUM X, const BIGNUM *Xin,
	217	const BIGNUM r1, const BIGNUM r2, int nlen,
	218	const BIGNUM e, BN_CTX ctx, BN_GENCB *cb)
	219	{
	220	int ret = 0;
	221	int i, imax;
	222	int bits = nlen >> 1;
8240d5fa SL	223	BIGNUM tmp, R, r1r2x2, y1, *r1x2;
8240d5fa SL	224
8240d5fa SL	225	BN_CTX_start(ctx);
	226
	227	R = BN_CTX_get(ctx);
	228	tmp = BN_CTX_get(ctx);
	229	r1r2x2 = BN_CTX_get(ctx);
	230	y1 = BN_CTX_get(ctx);
	231	r1x2 = BN_CTX_get(ctx);
	232	if (r1x2 == NULL)
	233	goto err;
	234
	235	if (Xin != NULL && BN_copy(X, Xin) == NULL)
	236	goto err;
	237
	238	if (!(BN_lshift1(r1x2, r1)
	239	/* (Step 1) GCD(2r1, r2) = 1 */
	240	&& BN_gcd(tmp, r1x2, r2, ctx)
	241	&& BN_is_one(tmp)
	242	/* (Step 2) R = ((r2^-1 mod 2r1) * r2) - ((2r1^-1 mod r2)2r1) /
	243	&& BN_mod_inverse(R, r2, r1x2, ctx)
	244	&& BN_mul(R, R, r2, ctx) /* R = (r2^-1 mod 2r1) * r2 */
	245	&& BN_mod_inverse(tmp, r1x2, r2, ctx)
	246	&& BN_mul(tmp, tmp, r1x2, ctx) /* tmp = (2r1^-1 mod r2)2r1 /
	247	&& BN_sub(R, R, tmp)
	248	/* Calculate 2r1r2 */
	249	&& BN_mul(r1r2x2, r1x2, r2, ctx)))
	250	goto err;
	251	/* Make positive by adding the modulus */
	252	if (BN_is_negative(R) && !BN_add(R, R, r1r2x2))
	253	goto err;
	254
	255	imax = 5 * bits; /* max = 5/2 * nbits */
	256	for (;;) {
	257	if (Xin == NULL) {
	258	/*
	259	* (Step 3) Choose Random X such that
	260	* sqrt(2) * 2^(nlen/2-1) < Random X < (2^(nlen/2)) - 1.
	261	*
	262	* For the lower bound:
	263	* sqrt(2) * 2^(nlen/2 - 1) == sqrt(2)/2 * 2^(nlen/2)
	264	* where sqrt(2)/2 = 0.70710678.. = 0.B504FC33F9DE...
	265	* so largest number will have B5... as the top byte
	266	* Setting the top 2 bits gives 0xC0.
	267	*/
2934be91 MC	268	if (!BN_priv_rand_ex(X, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ANY,
2934be91 MC	269	ctx))
8240d5fa SL	270	goto end;
	271	}
	272	/* (Step 4) Y = X + ((R - X) mod 2r1r2) */
	273	if (!BN_mod_sub(Y, R, X, r1r2x2, ctx) \|\| !BN_add(Y, Y, X))
	274	goto err;
	275	/* (Step 5) */
	276	i = 0;
	277	for (;;) {
	278	/* (Step 6) */
	279	if (BN_num_bits(Y) > bits) {
	280	if (Xin == NULL)
	281	break; /* Randomly Generated X so Go back to Step 3 */
	282	else
	283	goto err; /* X is not random so it will always fail */
	284	}
	285	BN_GENCB_call(cb, 0, 2);
	286
	287	/* (Step 7) If GCD(Y-1) == 1 & Y is probably prime then return Y */
	288	if (BN_copy(y1, Y) == NULL
	289	\|\| !BN_sub_word(y1, 1)
	290	\|\| !BN_gcd(tmp, y1, e, ctx))
	291	goto err;
42619397	292	if (BN_is_one(tmp) && BN_check_prime(Y, ctx, cb))
8240d5fa SL	293	goto end;
	294	/* (Step 8-10) */
	295	if (++i >= imax \|\| !BN_add(Y, Y, r1r2x2))
	296	goto err;
	297	}
	298	}
	299	end:
	300	ret = 1;
	301	BN_GENCB_call(cb, 3, 0);
	302	err:
	303	BN_clear(y1);
	304	BN_CTX_end(ctx);
	305	return ret;
	306	}