0N/A/*
3909N/A * Copyright (c) 2003, 2011, Oracle and/or its affiliates. All rights reserved.
0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0N/A *
0N/A * This code is free software; you can redistribute it and/or modify it
0N/A * under the terms of the GNU General Public License version 2 only, as
2362N/A * published by the Free Software Foundation. Oracle designates this
0N/A * particular file as subject to the "Classpath" exception as provided
2362N/A * by Oracle in the LICENSE file that accompanied this code.
0N/A *
0N/A * This code is distributed in the hope that it will be useful, but WITHOUT
0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0N/A * version 2 for more details (a copy is included in the LICENSE file that
0N/A * accompanied this code).
0N/A *
0N/A * You should have received a copy of the GNU General Public License version
0N/A * 2 along with this work; if not, write to the Free Software Foundation,
0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0N/A *
2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
2362N/A * or visit www.oracle.com if you need additional information or have any
2362N/A * questions.
0N/A */
0N/A
0N/Apackage sun.security.rsa;
0N/A
0N/Aimport java.math.BigInteger;
0N/Aimport java.util.*;
0N/A
0N/Aimport java.security.SecureRandom;
0N/Aimport java.security.interfaces.*;
0N/A
0N/Aimport javax.crypto.BadPaddingException;
0N/A
0N/Aimport sun.security.jca.JCAUtil;
0N/A
0N/A/**
0N/A * Core of the RSA implementation. Has code to perform public and private key
0N/A * RSA operations (with and without CRT for private key ops). Private CRT ops
0N/A * also support blinding to twart timing attacks.
0N/A *
0N/A * The code in this class only does the core RSA operation. Padding and
0N/A * unpadding must be done externally.
0N/A *
0N/A * Note: RSA keys should be at least 512 bits long
0N/A *
0N/A * @since 1.5
0N/A * @author Andreas Sterbenz
0N/A */
0N/Apublic final class RSACore {
0N/A
0N/A private RSACore() {
0N/A // empty
0N/A }
0N/A
0N/A /**
0N/A * Return the number of bytes required to store the magnitude byte[] of
0N/A * this BigInteger. Do not count a 0x00 byte toByteArray() would
0N/A * prefix for 2's complement form.
0N/A */
0N/A public static int getByteLength(BigInteger b) {
0N/A int n = b.bitLength();
0N/A return (n + 7) >> 3;
0N/A }
0N/A
0N/A /**
0N/A * Return the number of bytes required to store the modulus of this
0N/A * RSA key.
0N/A */
0N/A public static int getByteLength(RSAKey key) {
0N/A return getByteLength(key.getModulus());
0N/A }
0N/A
0N/A // temporary, used by RSACipher and RSAPadding. Move this somewhere else
0N/A public static byte[] convert(byte[] b, int ofs, int len) {
0N/A if ((ofs == 0) && (len == b.length)) {
0N/A return b;
0N/A } else {
0N/A byte[] t = new byte[len];
0N/A System.arraycopy(b, ofs, t, 0, len);
0N/A return t;
0N/A }
0N/A }
0N/A
0N/A /**
0N/A * Perform an RSA public key operation.
0N/A */
0N/A public static byte[] rsa(byte[] msg, RSAPublicKey key)
0N/A throws BadPaddingException {
0N/A return crypt(msg, key.getModulus(), key.getPublicExponent());
0N/A }
0N/A
0N/A /**
0N/A * Perform an RSA private key operation. Uses CRT if the key is a
0N/A * CRT key.
0N/A */
0N/A public static byte[] rsa(byte[] msg, RSAPrivateKey key)
0N/A throws BadPaddingException {
0N/A if (key instanceof RSAPrivateCrtKey) {
0N/A return crtCrypt(msg, (RSAPrivateCrtKey)key);
0N/A } else {
0N/A return crypt(msg, key.getModulus(), key.getPrivateExponent());
0N/A }
0N/A }
0N/A
0N/A /**
0N/A * RSA public key ops and non-CRT private key ops. Simple modPow().
0N/A */
0N/A private static byte[] crypt(byte[] msg, BigInteger n, BigInteger exp)
0N/A throws BadPaddingException {
0N/A BigInteger m = parseMsg(msg, n);
0N/A BigInteger c = m.modPow(exp, n);
0N/A return toByteArray(c, getByteLength(n));
0N/A }
0N/A
0N/A /**
0N/A * RSA private key operations with CRT. Algorithm and variable naming
0N/A * are taken from PKCS#1 v2.1, section 5.1.2.
0N/A *
0N/A * The only difference is the addition of blinding to twart timing attacks.
0N/A * This is described in the RSA Bulletin#2 (Jan 96) among other places.
0N/A * This means instead of implementing RSA as
0N/A * m = c ^ d mod n (or RSA in CRT variant)
0N/A * we do
0N/A * r = random(0, n-1)
0N/A * c' = c * r^e mod n
0N/A * m' = c' ^ d mod n (or RSA in CRT variant)
0N/A * m = m' * r^-1 mod n (where r^-1 is the modular inverse of r mod n)
0N/A * This works because r^(e*d) * r^-1 = r * r^-1 = 1 (all mod n)
0N/A *
0N/A * We do not generate new blinding parameters for each operation but reuse
0N/A * them BLINDING_MAX_REUSE times (see definition below).
0N/A */
0N/A private static byte[] crtCrypt(byte[] msg, RSAPrivateCrtKey key)
0N/A throws BadPaddingException {
0N/A BigInteger n = key.getModulus();
0N/A BigInteger c = parseMsg(msg, n);
0N/A BigInteger p = key.getPrimeP();
0N/A BigInteger q = key.getPrimeQ();
0N/A BigInteger dP = key.getPrimeExponentP();
0N/A BigInteger dQ = key.getPrimeExponentQ();
0N/A BigInteger qInv = key.getCrtCoefficient();
0N/A
0N/A BlindingParameters params;
0N/A if (ENABLE_BLINDING) {
0N/A params = getBlindingParameters(key);
0N/A c = c.multiply(params.re).mod(n);
0N/A } else {
0N/A params = null;
0N/A }
0N/A
0N/A // m1 = c ^ dP mod p
0N/A BigInteger m1 = c.modPow(dP, p);
0N/A // m2 = c ^ dQ mod q
0N/A BigInteger m2 = c.modPow(dQ, q);
0N/A
0N/A // h = (m1 - m2) * qInv mod p
0N/A BigInteger mtmp = m1.subtract(m2);
0N/A if (mtmp.signum() < 0) {
0N/A mtmp = mtmp.add(p);
0N/A }
0N/A BigInteger h = mtmp.multiply(qInv).mod(p);
0N/A
0N/A // m = m2 + q * h
0N/A BigInteger m = h.multiply(q).add(m2);
0N/A
0N/A if (params != null) {
0N/A m = m.multiply(params.rInv).mod(n);
0N/A }
0N/A
0N/A return toByteArray(m, getByteLength(n));
0N/A }
0N/A
0N/A /**
0N/A * Parse the msg into a BigInteger and check against the modulus n.
0N/A */
0N/A private static BigInteger parseMsg(byte[] msg, BigInteger n)
0N/A throws BadPaddingException {
0N/A BigInteger m = new BigInteger(1, msg);
0N/A if (m.compareTo(n) >= 0) {
0N/A throw new BadPaddingException("Message is larger than modulus");
0N/A }
0N/A return m;
0N/A }
0N/A
0N/A /**
0N/A * Return the encoding of this BigInteger that is exactly len bytes long.
0N/A * Prefix/strip off leading 0x00 bytes if necessary.
0N/A * Precondition: bi must fit into len bytes
0N/A */
0N/A private static byte[] toByteArray(BigInteger bi, int len) {
0N/A byte[] b = bi.toByteArray();
0N/A int n = b.length;
0N/A if (n == len) {
0N/A return b;
0N/A }
0N/A // BigInteger prefixed a 0x00 byte for 2's complement form, remove it
0N/A if ((n == len + 1) && (b[0] == 0)) {
0N/A byte[] t = new byte[len];
0N/A System.arraycopy(b, 1, t, 0, len);
0N/A return t;
0N/A }
0N/A // must be smaller
0N/A assert (n < len);
0N/A byte[] t = new byte[len];
0N/A System.arraycopy(b, 0, t, (len - n), n);
0N/A return t;
0N/A }
0N/A
0N/A // globally enable/disable use of blinding
0N/A private final static boolean ENABLE_BLINDING = true;
0N/A
0N/A // maximum number of times that we will use a set of blinding parameters
0N/A // value suggested by Paul Kocher (quoted by NSS)
0N/A private final static int BLINDING_MAX_REUSE = 50;
0N/A
3384N/A // cache for blinding parameters. Map<BigInteger, BlindingParameters>
0N/A // use a weak hashmap so that cached values are automatically cleared
0N/A // when the modulus is GC'ed
3384N/A private final static Map<BigInteger, BlindingParameters> blindingCache =
3384N/A new WeakHashMap<>();
0N/A
0N/A /**
0N/A * Set of blinding parameters for a given RSA key.
0N/A *
0N/A * The RSA modulus is usually unique, so we index by modulus in
0N/A * blindingCache. However, to protect against the unlikely case of two
0N/A * keys sharing the same modulus, we also store the public exponent.
0N/A * This means we cannot cache blinding parameters for multiple keys that
0N/A * share the same modulus, but since sharing moduli is fundamentally broken
0N/A * an insecure, this does not matter.
0N/A */
0N/A private static final class BlindingParameters {
0N/A // e (RSA public exponent)
0N/A final BigInteger e;
0N/A // r ^ e mod n
0N/A final BigInteger re;
0N/A // inverse of r mod n
0N/A final BigInteger rInv;
0N/A // how many more times this parameter object can be used
0N/A private volatile int remainingUses;
0N/A BlindingParameters(BigInteger e, BigInteger re, BigInteger rInv) {
0N/A this.e = e;
0N/A this.re = re;
0N/A this.rInv = rInv;
0N/A // initialize remaining uses, subtract current use now
0N/A remainingUses = BLINDING_MAX_REUSE - 1;
0N/A }
0N/A boolean valid(BigInteger e) {
0N/A int k = remainingUses--;
0N/A return (k > 0) && this.e.equals(e);
0N/A }
0N/A }
0N/A
0N/A /**
0N/A * Return valid RSA blinding parameters for the given private key.
0N/A * Use cached parameters if available. If not, generate new parameters
0N/A * and cache.
0N/A */
0N/A private static BlindingParameters getBlindingParameters
0N/A (RSAPrivateCrtKey key) {
0N/A BigInteger modulus = key.getModulus();
0N/A BigInteger e = key.getPublicExponent();
0N/A BlindingParameters params;
0N/A // we release the lock between get() and put()
0N/A // that means threads might concurrently generate new blinding
0N/A // parameters for the same modulus. this is only a slight waste
0N/A // of cycles and seems preferable in terms of scalability
0N/A // to locking out all threads while generating new parameters
0N/A synchronized (blindingCache) {
0N/A params = blindingCache.get(modulus);
0N/A }
0N/A if ((params != null) && params.valid(e)) {
0N/A return params;
0N/A }
0N/A int len = modulus.bitLength();
0N/A SecureRandom random = JCAUtil.getSecureRandom();
0N/A BigInteger r = new BigInteger(len, random).mod(modulus);
0N/A BigInteger re = r.modPow(e, modulus);
0N/A BigInteger rInv = r.modInverse(modulus);
0N/A params = new BlindingParameters(e, re, rInv);
0N/A synchronized (blindingCache) {
0N/A blindingCache.put(modulus, params);
0N/A }
0N/A return params;
0N/A }
0N/A
0N/A}