security/rsa/RSACore.java

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

}