/*
 * 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
Author:
 Andreas Sterbenz
Since:
  1.5/**
 * 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 final static 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 final static 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.
/**
     * 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.
/**
     * 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.
/**
     * 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.
/**
     * 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.
/**
     * 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().
/**
     * 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.
/**
     * 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.
/**
     * 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.
/**
     * 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
/**
     * 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.
/**
     * 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 final static 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 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. /**
     * 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 final static class BlindingParameters {
        private final static 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;
    }

}