Back to index...

	/*
	* 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);
	}
	}
	}

Back to index...