xref: /external/bouncycastle/bcprov/src/main/java/org/bouncycastle/crypto/generators/RSAKeyPairGenerator.java

package org.bouncycastle.crypto.generators;

import java.math.BigInteger;

import org.bouncycastle.crypto.AsymmetricCipherKeyPair;
import org.bouncycastle.crypto.AsymmetricCipherKeyPairGenerator;
import org.bouncycastle.crypto.KeyGenerationParameters;
import org.bouncycastle.crypto.params.RSAKeyGenerationParameters;
import org.bouncycastle.crypto.params.RSAKeyParameters;
import org.bouncycastle.crypto.params.RSAPrivateCrtKeyParameters;
import org.bouncycastle.math.Primes;
import org.bouncycastle.math.ec.WNafUtil;

/**
 * an RSA key pair generator.
 */
public class RSAKeyPairGenerator
    implements AsymmetricCipherKeyPairGenerator
{
    private static final BigInteger ONE = BigInteger.valueOf(1);

    private RSAKeyGenerationParameters param;
    private int iterations;

    public void init(KeyGenerationParameters param)
    {
        this.param = (RSAKeyGenerationParameters)param;
        this.iterations = getNumberOfIterations(this.param.getStrength(), this.param.getCertainty());
    }

    public AsymmetricCipherKeyPair generateKeyPair()
    {
        AsymmetricCipherKeyPair result = null;
        boolean done = false;

        //
        // p and q values should have a length of half the strength in bits
        //
        int strength = param.getStrength();
        int pbitlength = (strength + 1) / 2;
        int qbitlength = strength - pbitlength;
        int mindiffbits = (strength / 2) - 100;

        if (mindiffbits < strength / 3)
        {
            mindiffbits = strength / 3;
        }

        int minWeight = strength >> 2;

        // d lower bound is 2^(strength / 2)
        BigInteger dLowerBound = BigInteger.valueOf(2).pow(strength / 2);
        // squared bound (sqrt(2)*2^(nlen/2-1))^2
        BigInteger squaredBound = ONE.shiftLeft(strength - 1);
        // 2^(nlen/2 - 100)
        BigInteger minDiff = ONE.shiftLeft(mindiffbits);

        while (!done)
        {
            BigInteger p, q, n, d, e, pSub1, qSub1, gcd, lcm;

            e = param.getPublicExponent();

            p = chooseRandomPrime(pbitlength, e, squaredBound);

            //
            // generate a modulus of the required length
            //
            for (; ; )
            {
                q = chooseRandomPrime(qbitlength, e, squaredBound);

                // p and q should not be too close together (or equal!)
                BigInteger diff = q.subtract(p).abs();
                if (diff.bitLength() < mindiffbits || diff.compareTo(minDiff) <= 0)
                {
                    continue;
                }

                //
                // calculate the modulus
                //
                n = p.multiply(q);

                if (n.bitLength() != strength)
                {
                    //
                    // if we get here our primes aren't big enough, make the largest
                    // of the two p and try again
                    //
                    p = p.max(q);
                    continue;
                }

	            /*
                 * Require a minimum weight of the NAF representation, since low-weight composites may
	             * be weak against a version of the number-field-sieve for factoring.
	             *
	             * See "The number field sieve for integers of low weight", Oliver Schirokauer.
	             */
                if (WNafUtil.getNafWeight(n) < minWeight)
                {
                    p = chooseRandomPrime(pbitlength, e, squaredBound);
                    continue;
                }

                break;
            }

            if (p.compareTo(q) < 0)
            {
                gcd = p;
                p = q;
                q = gcd;
            }

            pSub1 = p.subtract(ONE);
            qSub1 = q.subtract(ONE);
            gcd = pSub1.gcd(qSub1);
            lcm = pSub1.divide(gcd).multiply(qSub1);

            //
            // calculate the private exponent
            //
            d = e.modInverse(lcm);

            if (d.compareTo(dLowerBound) <= 0)
            {
                continue;
            }
            else
            {
                done = true;
            }

            //
            // calculate the CRT factors
            //
            BigInteger dP, dQ, qInv;

            dP = d.remainder(pSub1);
            dQ = d.remainder(qSub1);
            qInv = q.modInverse(p);

            result = new AsymmetricCipherKeyPair(
                new RSAKeyParameters(false, n, e),
                new RSAPrivateCrtKeyParameters(n, e, d, p, q, dP, dQ, qInv));
        }

        return result;
    }

    /**
     * Choose a random prime value for use with RSA
     *
     * @param bitlength the bit-length of the returned prime
     * @param e         the RSA public exponent
     * @return A prime p, with (p-1) relatively prime to e
     */
    protected BigInteger chooseRandomPrime(int bitlength, BigInteger e, BigInteger sqrdBound)
    {
        for (int i = 0; i != 5 * bitlength; i++)
        {
            BigInteger p = new BigInteger(bitlength, 1, param.getRandom());

            if (p.mod(e).equals(ONE))
            {
                continue;
            }

            if (p.multiply(p).compareTo(sqrdBound) < 0)
            {
                continue;
            }

            if (!isProbablePrime(p))
            {
                continue;
            }

            if (!e.gcd(p.subtract(ONE)).equals(ONE))
            {
                continue;
            }

            return p;
        }

        throw new IllegalStateException("unable to generate prime number for RSA key");
    }

    protected boolean isProbablePrime(BigInteger x)
    {
        /*
         * Primes class for FIPS 186-4 C.3 primality checking
         */
        return !Primes.hasAnySmallFactors(x) && Primes.isMRProbablePrime(x, param.getRandom(), iterations);
    }

    private static int getNumberOfIterations(int bits, int certainty)
    {
        /*
         * NOTE: We enforce a minimum 'certainty' of 100 for bits >= 1024 (else 80). Where the
         * certainty is higher than the FIPS 186-4 tables (C.2/C.3) cater to, extra iterations
         * are added at the "worst case rate" for the excess.
         */
        if (bits >= 1536)
        {
            return  certainty <= 100 ? 3
                :   certainty <= 128 ? 4
                :   4 + (certainty - 128 + 1) / 2;
        }
        else if (bits >= 1024)
        {
            return  certainty <= 100 ? 4
                :   certainty <= 112 ? 5
                :   5 + (certainty - 112 + 1) / 2;
        }
        else if (bits >= 512)
        {
            return  certainty <= 80  ? 5
                :   certainty <= 100 ? 7
                :   7 + (certainty - 100 + 1) / 2;
        }
        else
        {
            return  certainty <= 80  ? 40
                :   40 + (certainty - 80 + 1) / 2;
        }
    }
}