Back to index...

	/*
	* Copyright (c) 2003, 2015, 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.util.*;

	import java.security.SecureRandom;
	import java.security.interfaces.*;

	import javax.crypto.BadPaddingException;

	import sun.security.jca.JCAUtil;

	/**
	* Core of the RSA implementation. Has code to perform public and private key
	* RSA operations (with and without CRT for private key ops). Private CRT ops
	* also support blinding to twart timing attacks.
	*
	* The code in this class only does the core RSA operation. Padding and
	* unpadding must be done externally.
	*
	* Note: RSA keys should be at least 512 bits long
	*
	* @since 1.5
	* @author Andreas Sterbenz
	*/
	public final class RSACore {

	// globally enable/disable use of blinding
	private static final boolean ENABLE_BLINDING = true;

	// cache for blinding parameters. Map<BigInteger, BlindingParameters>
	// use a weak hashmap so that cached values are automatically cleared
	// when the modulus is GC'ed
	private static final Map<BigInteger, BlindingParameters>
	blindingCache = new WeakHashMap<>();

	private RSACore() {
	// empty
	}

	/**
	* Return the number of bytes required to store the magnitude byte[] of
	* this BigInteger. Do not count a 0x00 byte toByteArray() would
	* prefix for 2's complement form.
	*/
	public static int getByteLength(BigInteger b) {
	int n = b.bitLength();
	return (n + 7) >> 3;
	}

	/**
	* Return the number of bytes required to store the modulus of this
	* RSA key.
	*/
	public static int getByteLength(RSAKey key) {
	return getByteLength(key.getModulus());
	}

	// temporary, used by RSACipher and RSAPadding. Move this somewhere else
	public static byte[] convert(byte[] b, int ofs, int len) {
	if ((ofs == 0) && (len == b.length)) {
	return b;
	} else {
	byte[] t = new byte[len];
	System.arraycopy(b, ofs, t, 0, len);
	return t;
	}
	}

	/**
	* Perform an RSA public key operation.
	*/
	public static byte[] rsa(byte[] msg, RSAPublicKey key)
	throws BadPaddingException {
	return crypt(msg, key.getModulus(), key.getPublicExponent());
	}

	/**
	* Perform an RSA private key operation. Uses CRT if the key is a
	* CRT key with additional verification check after the signature
	* is computed.
	*/
	@Deprecated
	public static byte[] rsa(byte[] msg, RSAPrivateKey key)
	throws BadPaddingException {
	return rsa(msg, key, true);
	}

	/**
	* Perform an RSA private key operation. Uses CRT if the key is a
	* CRT key. Set 'verify' to true if this function is used for
	* generating a signature.
	*/
	public static byte[] rsa(byte[] msg, RSAPrivateKey key, boolean verify)
	throws BadPaddingException {
	if (key instanceof RSAPrivateCrtKey) {
	return crtCrypt(msg, (RSAPrivateCrtKey)key, verify);
	} else {
	return priCrypt(msg, key.getModulus(), key.getPrivateExponent());
	}
	}

	/**
	* RSA public key ops. Simple modPow().
	*/
	private static byte[] crypt(byte[] msg, BigInteger n, BigInteger exp)
	throws BadPaddingException {
	BigInteger m = parseMsg(msg, n);
	BigInteger c = m.modPow(exp, n);
	return toByteArray(c, getByteLength(n));
	}

	/**
	* RSA non-CRT private key operations.
	*/
	private static byte[] priCrypt(byte[] msg, BigInteger n, BigInteger exp)
	throws BadPaddingException {

	BigInteger c = parseMsg(msg, n);
	BlindingRandomPair brp = null;
	BigInteger m;
	if (ENABLE_BLINDING) {
	brp = getBlindingRandomPair(null, exp, n);
	c = c.multiply(brp.u).mod(n);
	m = c.modPow(exp, n);
	m = m.multiply(brp.v).mod(n);
	} else {
	m = c.modPow(exp, n);
	}

	return toByteArray(m, getByteLength(n));
	}

	/**
	* RSA private key operations with CRT. Algorithm and variable naming
	* are taken from PKCS#1 v2.1, section 5.1.2.
	*/
	private static byte[] crtCrypt(byte[] msg, RSAPrivateCrtKey key,
	boolean verify) throws BadPaddingException {
	BigInteger n = key.getModulus();
	BigInteger c0 = parseMsg(msg, n);
	BigInteger c = c0;
	BigInteger p = key.getPrimeP();
	BigInteger q = key.getPrimeQ();
	BigInteger dP = key.getPrimeExponentP();
	BigInteger dQ = key.getPrimeExponentQ();
	BigInteger qInv = key.getCrtCoefficient();
	BigInteger e = key.getPublicExponent();
	BigInteger d = key.getPrivateExponent();

	BlindingRandomPair brp;
	if (ENABLE_BLINDING) {
	brp = getBlindingRandomPair(e, d, n);
	c = c.multiply(brp.u).mod(n);
	}

	// m1 = c ^ dP mod p
	BigInteger m1 = c.modPow(dP, p);
	// m2 = c ^ dQ mod q
	BigInteger m2 = c.modPow(dQ, q);

	// h = (m1 - m2) * qInv mod p
	BigInteger mtmp = m1.subtract(m2);
	if (mtmp.signum() < 0) {
	mtmp = mtmp.add(p);
	}
	BigInteger h = mtmp.multiply(qInv).mod(p);

	// m = m2 + q * h
	BigInteger m = h.multiply(q).add(m2);

	if (ENABLE_BLINDING) {
	m = m.multiply(brp.v).mod(n);
	}
	if (verify && !c0.equals(m.modPow(e, n))) {
	throw new BadPaddingException("RSA private key operation failed");
	}

	return toByteArray(m, getByteLength(n));
	}

	/**
	* Parse the msg into a BigInteger and check against the modulus n.
	*/
	private static BigInteger parseMsg(byte[] msg, BigInteger n)
	throws BadPaddingException {
	BigInteger m = new BigInteger(1, msg);
	if (m.compareTo(n) >= 0) {
	throw new BadPaddingException("Message is larger than modulus");
	}
	return m;
	}

	/**
	* Return the encoding of this BigInteger that is exactly len bytes long.
	* Prefix/strip off leading 0x00 bytes if necessary.
	* Precondition: bi must fit into len bytes
	*/
	private static byte[] toByteArray(BigInteger bi, int len) {
	byte[] b = bi.toByteArray();
	int n = b.length;
	if (n == len) {
	return b;
	}
	// BigInteger prefixed a 0x00 byte for 2's complement form, remove it
	if ((n == len + 1) && (b[0] == 0)) {
	byte[] t = new byte[len];
	System.arraycopy(b, 1, t, 0, len);
	return t;
	}
	// must be smaller
	assert (n < len);
	byte[] t = new byte[len];
	System.arraycopy(b, 0, t, (len - n), n);
	return t;
	}

	/**
	* Parameters (u,v) for RSA Blinding. This is described in the RSA
	* Bulletin#2 (Jan 96) and other places:
	*
	* ftp://ftp.rsa.com/pub/pdfs/bull-2.pdf
	*
	* The standard RSA Blinding decryption requires the public key exponent
	* (e) and modulus (n), and converts ciphertext (c) to plaintext (p).
	*
	* Before the modular exponentiation operation, the input message should
	* be multiplied by (u (mod n)), and afterward the result is corrected
	* by multiplying with (v (mod n)). The system should reject messages
	* equal to (0 (mod n)). That is:
	*
	* 1. Generate r between 0 and n-1, relatively prime to n.
	* 2. Compute x = (c*u) mod n
	* 3. Compute y = (x^d) mod n
	* 4. Compute p = (y*v) mod n
	*
	* The Java APIs allows for either standard RSAPrivateKey or
	* RSAPrivateCrtKey RSA keys.
	*
	* If the public exponent is available to us (e.g. RSAPrivateCrtKey),
	* choose a random r, then let (u, v):
	*
	* u = r ^ e mod n
	* v = r ^ (-1) mod n
	*
	* The proof follows:
	*
	* p = (((c * u) ^ d mod n) * v) mod n
	* = ((c ^ d) * (u ^ d) * v) mod n
	* = ((c ^ d) * (r ^ e) ^ d) * (r ^ (-1))) mod n
	* = ((c ^ d) * (r ^ (e * d)) * (r ^ (-1))) mod n
	* = ((c ^ d) * (r ^ 1) * (r ^ (-1))) mod n (see below)
	* = (c ^ d) mod n
	*
	* because in RSA cryptosystem, d is the multiplicative inverse of e:
	*
	* (r^(e * d)) mod n
	* = (r ^ 1) mod n
	* = r mod n
	*
	* However, if the public exponent is not available (e.g. RSAPrivateKey),
	* we mitigate the timing issue by using a similar random number blinding
	* approach using the private key:
	*
	* u = r
	* v = ((r ^ (-1)) ^ d) mod n
	*
	* This returns the same plaintext because:
	*
	* p = (((c * u) ^ d mod n) * v) mod n
	* = ((c ^ d) * (u ^ d) * v) mod n
	* = ((c ^ d) * (u ^ d) * ((u ^ (-1)) ^d)) mod n
	* = (c ^ d) mod n
	*
	* Computing inverses mod n and random number generation is slow, so
	* it is often not practical to generate a new random (u, v) pair for
	* each new exponentiation. The calculation of parameters might even be
	* subject to timing attacks. However, (u, v) pairs should not be
	* reused since they themselves might be compromised by timing attacks,
	* leaving the private exponent vulnerable. An efficient solution to
	* this problem is update u and v before each modular exponentiation
	* step by computing:
	*
	* u = u ^ 2
	* v = v ^ 2
	*
	* The total performance cost is small.
	*/
	private static final class BlindingRandomPair {
	final BigInteger u;
	final BigInteger v;

	BlindingRandomPair(BigInteger u, BigInteger v) {
	this.u = u;
	this.v = v;
	}
	}

	/**
	* Set of blinding parameters for a given RSA key.
	*
	* The RSA modulus is usually unique, so we index by modulus in
	* {@code blindingCache}. However, to protect against the unlikely
	* case of two keys sharing the same modulus, we also store the public
	* or the private exponent. This means we cannot cache blinding
	* parameters for multiple keys that share the same modulus, but
	* since sharing moduli is fundamentally broken and insecure, this
	* does not matter.
	*/
	private static final class BlindingParameters {
	private static final BigInteger BIG_TWO = BigInteger.valueOf(2L);

	// RSA public exponent
	private final BigInteger e;

	// hash code of RSA private exponent
	private final BigInteger d;

	// r ^ e mod n (CRT), or r mod n (Non-CRT)
	private BigInteger u;

	// r ^ (-1) mod n (CRT) , or ((r ^ (-1)) ^ d) mod n (Non-CRT)
	private BigInteger v;

	// e: the public exponent
	// d: the private exponent
	// n: the modulus
	BlindingParameters(BigInteger e, BigInteger d, BigInteger n) {
	this.u = null;
	this.v = null;
	this.e = e;
	this.d = d;

	int len = n.bitLength();
	SecureRandom random = JCAUtil.getSecureRandom();
	u = new BigInteger(len, random).mod(n);
	// Although the possibility is very much limited that u is zero
	// or is not relatively prime to n, we still want to be careful
	// about the special value.
	//
	// Secure random generation is expensive, try to use BigInteger.ONE
	// this time if this new generated random number is zero or is not
	// relatively prime to n. Next time, new generated secure random
	// number will be used instead.
	if (u.equals(BigInteger.ZERO)) {
	u = BigInteger.ONE; // use 1 this time
	}

	try {
	// The call to BigInteger.modInverse() checks that u is
	// relatively prime to n. Otherwise, ArithmeticException is
	// thrown.
	v = u.modInverse(n);
	} catch (ArithmeticException ae) {
	// if u is not relatively prime to n, use 1 this time
	u = BigInteger.ONE;
	v = BigInteger.ONE;
	}

	if (e != null) {
	u = u.modPow(e, n); // e: the public exponent
	// u: random ^ e
	// v: random ^ (-1)
	} else {
	v = v.modPow(d, n); // d: the private exponent
	// u: random
	// v: random ^ (-d)
	}
	}

	// return null if need to reset the parameters
	BlindingRandomPair getBlindingRandomPair(
	BigInteger e, BigInteger d, BigInteger n) {

	if ((this.e != null && this.e.equals(e)) \|\|
	(this.d != null && this.d.equals(d))) {

	BlindingRandomPair brp = null;
	synchronized (this) {
	if (!u.equals(BigInteger.ZERO) &&
	!v.equals(BigInteger.ZERO)) {

	brp = new BlindingRandomPair(u, v);
	if (u.compareTo(BigInteger.ONE) <= 0 \|\|
	v.compareTo(BigInteger.ONE) <= 0) {

	// need to reset the random pair next time
	u = BigInteger.ZERO;
	v = BigInteger.ZERO;
	} else {
	u = u.modPow(BIG_TWO, n);
	v = v.modPow(BIG_TWO, n);
	}
	} // Otherwise, need to reset the random pair.
	}
	return brp;
	}

	return null;
	}
	}

	private static BlindingRandomPair getBlindingRandomPair(
	BigInteger e, BigInteger d, BigInteger n) {

	BlindingParameters bps = null;
	synchronized (blindingCache) {
	bps = blindingCache.get(n);
	}

	if (bps == null) {
	bps = new BlindingParameters(e, d, n);
	synchronized (blindingCache) {
	blindingCache.putIfAbsent(n, bps);
	}
	}

	BlindingRandomPair brp = bps.getBlindingRandomPair(e, d, n);
	if (brp == null) {
	// need to reset the blinding parameters
	bps = new BlindingParameters(e, d, n);
	synchronized (blindingCache) {
	blindingCache.replace(n, bps);
	}
	brp = bps.getBlindingRandomPair(e, d, n);
	}

	return brp;
	}

	}

Back to index...