RSAKeyPairGenerator.java

/*
 * Copyright (c) 2003, 2020, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package sun.security.rsa;

import java.math.BigInteger;

import java.security.*;
import java.security.spec.AlgorithmParameterSpec;
import java.security.spec.RSAKeyGenParameterSpec;

import static java.math.BigInteger.*;
import sun.security.jca.JCAUtil;
import sun.security.rsa.RSAUtil.KeyType;

import static sun.security.util.SecurityProviderConstants.DEF_RSA_KEY_SIZE;
import static sun.security.util.SecurityProviderConstants.DEF_RSASSA_PSS_KEY_SIZE;

/**
 * RSA keypair generation. Standard algorithm, minimum key length 512 bit.
 * We generate two random primes until we find two where phi is relative
 * prime to the public exponent. Default exponent is 65537. It has only bit 0
 * and bit 4 set, which makes it particularly efficient.
 *
 * @since   1.5
 * @author  Andreas Sterbenz
 */
public abstract class RSAKeyPairGenerator extends KeyPairGeneratorSpi {

    private static final BigInteger SQRT_2048;
    private static final BigInteger SQRT_3072;
    private static final BigInteger SQRT_4096;

    static {
        SQRT_2048 = TWO.pow(2047).sqrt();
        SQRT_3072 = TWO.pow(3071).sqrt();
        SQRT_4096 = TWO.pow(4095).sqrt();
    }

    // public exponent to use
    private BigInteger publicExponent;

    // size of the key to generate, >= RSAKeyFactory.MIN_MODLEN
    private int keySize;

    private final KeyType type;
    private AlgorithmParameterSpec keyParams;

    // PRNG to use
    private SecureRandom random;

    // whether to generate key pairs following the new guidelines from
    // FIPS 186-4 and later
    private boolean useNew;

    RSAKeyPairGenerator(KeyType type, int defKeySize) {
        this.type = type;
        // initialize to default in case the app does not call initialize()
        initialize(defKeySize, null);
    }

    // initialize the generator. See JCA doc
    public void initialize(int keySize, SecureRandom random) {
        try {
            initialize(new RSAKeyGenParameterSpec(keySize,
                    RSAKeyGenParameterSpec.F4), random);
        } catch (InvalidAlgorithmParameterException iape) {
            throw new InvalidParameterException(iape.getMessage());
        }
    }

    // second initialize method. See JCA doc.
    public void initialize(AlgorithmParameterSpec params, SecureRandom random)
            throws InvalidAlgorithmParameterException {
        if (params instanceof RSAKeyGenParameterSpec == false) {
            throw new InvalidAlgorithmParameterException
                ("Params must be instance of RSAKeyGenParameterSpec");
        }

        RSAKeyGenParameterSpec rsaSpec = (RSAKeyGenParameterSpec)params;
        int tmpKeySize = rsaSpec.getKeysize();
        BigInteger tmpPubExp = rsaSpec.getPublicExponent();
        AlgorithmParameterSpec tmpParams = rsaSpec.getKeyParams();

        // use the new approach for even key sizes >= 2048 AND when the
        // public exponent is within FIPS valid range
        boolean useNew = (tmpKeySize >= 2048 && ((tmpKeySize & 1) == 0));

        if (tmpPubExp == null) {
            tmpPubExp = RSAKeyGenParameterSpec.F4;
        } else {
            if (!tmpPubExp.testBit(0)) {
                throw new InvalidAlgorithmParameterException
                    ("Public exponent must be an odd number");
            }
            // current impl checks that  F0 <= e < 2^keysize
            // vs FIPS 186-4 checks that F4 <= e < 2^256
            // for backward compatibility, we keep the same checks
            BigInteger minValue = RSAKeyGenParameterSpec.F0;
            int maxBitLength = tmpKeySize;
            if (tmpPubExp.compareTo(RSAKeyGenParameterSpec.F0) < 0) {
                throw new InvalidAlgorithmParameterException
                        ("Public exponent must be " + minValue + " or larger");
            }
            if (tmpPubExp.bitLength() > maxBitLength) {
                throw new InvalidAlgorithmParameterException
                        ("Public exponent must be no longer than " +
                        maxBitLength + " bits");
            }
            useNew &= ((tmpPubExp.compareTo(RSAKeyGenParameterSpec.F4) >= 0) &&
                    (tmpPubExp.bitLength() < 256));
        }

        // do not allow unreasonably large key sizes, probably user error
        try {
            RSAKeyFactory.checkKeyLengths(tmpKeySize, tmpPubExp, 512,
                    64 * 1024);
        } catch (InvalidKeyException e) {
            throw new InvalidAlgorithmParameterException(
                "Invalid key sizes", e);
        }

        try {
            this.keyParams = RSAUtil.checkParamsAgainstType(type, tmpParams);
        } catch (ProviderException e) {
            throw new InvalidAlgorithmParameterException(
                "Invalid key parameters", e);
        }

        this.keySize = tmpKeySize;
        this.publicExponent = tmpPubExp;
        this.random = (random == null? JCAUtil.getSecureRandom() : random);
        this.useNew = useNew;
    }

    // FIPS 186-4 B.3.3 / FIPS 186-5 A.1.3
    // Generation of Random Primes that are Probably Prime
    public KeyPair generateKeyPair() {
        BigInteger e = publicExponent;
        BigInteger minValue = (useNew? getSqrt(keySize) : ZERO);
        int lp = (keySize + 1) >> 1;;
        int lq = keySize - lp;
        int pqDiffSize = lp - 100;

        while (true) {
            BigInteger p = null;
            BigInteger q = null;

            int i = 0;
            while (i++ < 10*lp) {
                BigInteger tmpP = BigInteger.probablePrime(lp, random);
                if ((!useNew || tmpP.compareTo(minValue) == 1) &&
                        isRelativePrime(e, tmpP.subtract(ONE))) {
                    p = tmpP;
                    break;
                }
            }
            if (p == null) {
                throw new ProviderException("Cannot find prime P");
            }

            i = 0;

            while (i++ < 20*lq) {
                BigInteger tmpQ = BigInteger.probablePrime(lq, random);

                if ((!useNew || tmpQ.compareTo(minValue) == 1) &&
                        (p.subtract(tmpQ).abs().compareTo
                                (TWO.pow(pqDiffSize)) == 1) &&
                        isRelativePrime(e, tmpQ.subtract(ONE))) {
                    q = tmpQ;
                    break;
                }
            }
            if (q == null) {
                throw new ProviderException("Cannot find prime Q");
            }

            BigInteger n = p.multiply(q);
            if (n.bitLength() != keySize) {
                // regenerate P, Q if n is not the right length; should
                // never happen for the new case but check it anyway
                continue;
            }

            KeyPair kp = createKeyPair(type, keyParams, n, e, p, q);
            // done, return the generated keypair;
            if (kp != null) return kp;
        }
    }

    private static BigInteger getSqrt(int keySize) {
        BigInteger sqrt = null;
        switch (keySize) {
            case 2048:
                sqrt = SQRT_2048;
                break;
            case 3072:
                sqrt = SQRT_3072;
                break;
            case 4096:
                sqrt = SQRT_4096;
                break;
            default:
                sqrt = TWO.pow(keySize-1).sqrt();
        }
        return sqrt;
    }

    private static boolean isRelativePrime(BigInteger e, BigInteger bi) {
        // optimize for common known public exponent prime values
        if (e.compareTo(RSAKeyGenParameterSpec.F4) == 0 ||
                e.compareTo(RSAKeyGenParameterSpec.F0) == 0) {
            return !bi.mod(e).equals(ZERO);
        } else {
            return e.gcd(bi).equals(ONE);
        }
    }

    private static KeyPair createKeyPair(KeyType type,
            AlgorithmParameterSpec keyParams,
            BigInteger n, BigInteger e, BigInteger p, BigInteger q) {
        // phi = (p - 1) * (q - 1) must be relative prime to e
        // otherwise RSA just won't work ;-)
        BigInteger p1 = p.subtract(ONE);
        BigInteger q1 = q.subtract(ONE);
        BigInteger phi = p1.multiply(q1);

        BigInteger gcd = p1.gcd(q1);
        BigInteger lcm = (gcd.equals(ONE)?  phi : phi.divide(gcd));

        BigInteger d = e.modInverse(lcm);

        if (d.compareTo(TWO.pow(p.bitLength())) != 1) {
            return null;
        }

        // 1st prime exponent pe = d mod (p - 1)
        BigInteger pe = d.mod(p1);
        // 2nd prime exponent qe = d mod (q - 1)
        BigInteger qe = d.mod(q1);
        // crt coefficient coeff is the inverse of q mod p
        BigInteger coeff = q.modInverse(p);

        try {
            PublicKey publicKey = new RSAPublicKeyImpl(type, keyParams, n, e);
            PrivateKey privateKey = new RSAPrivateCrtKeyImpl(
                type, keyParams, n, e, d, p, q, pe, qe, coeff);
            return new KeyPair(publicKey, privateKey);
        } catch (InvalidKeyException exc) {
            // invalid key exception only thrown for keys < 512 bit,
            // will not happen here
            throw new RuntimeException(exc);
        }
    }

    public static final class Legacy extends RSAKeyPairGenerator {
        public Legacy() {
            super(KeyType.RSA, DEF_RSA_KEY_SIZE);
        }
    }

    public static final class PSS extends RSAKeyPairGenerator {
        public PSS() {
            super(KeyType.PSS, DEF_RSASSA_PSS_KEY_SIZE);
        }
    }
}