1/* 2 * Copyright (c) 2003, 2015, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26package sun.security.rsa; 27 28import java.math.BigInteger; 29import java.util.*; 30 31import java.security.SecureRandom; 32import java.security.interfaces.*; 33 34import javax.crypto.BadPaddingException; 35 36import sun.security.jca.JCAUtil; 37 38/** 39 * Core of the RSA implementation. Has code to perform public and private key 40 * RSA operations (with and without CRT for private key ops). Private CRT ops 41 * also support blinding to twart timing attacks. 42 * 43 * The code in this class only does the core RSA operation. Padding and 44 * unpadding must be done externally. 45 * 46 * Note: RSA keys should be at least 512 bits long 47 * 48 * @since 1.5 49 * @author Andreas Sterbenz 50 */ 51public final class RSACore { 52 53 // globally enable/disable use of blinding 54 private static final boolean ENABLE_BLINDING = true; 55 56 // cache for blinding parameters. Map<BigInteger, BlindingParameters> 57 // use a weak hashmap so that cached values are automatically cleared 58 // when the modulus is GC'ed 59 private static final Map<BigInteger, BlindingParameters> 60 blindingCache = new WeakHashMap<>(); 61 62 private RSACore() { 63 // empty 64 } 65 66 /** 67 * Return the number of bytes required to store the magnitude byte[] of 68 * this BigInteger. Do not count a 0x00 byte toByteArray() would 69 * prefix for 2's complement form. 70 */ 71 public static int getByteLength(BigInteger b) { 72 int n = b.bitLength(); 73 return (n + 7) >> 3; 74 } 75 76 /** 77 * Return the number of bytes required to store the modulus of this 78 * RSA key. 79 */ 80 public static int getByteLength(RSAKey key) { 81 return getByteLength(key.getModulus()); 82 } 83 84 // temporary, used by RSACipher and RSAPadding. Move this somewhere else 85 public static byte[] convert(byte[] b, int ofs, int len) { 86 if ((ofs == 0) && (len == b.length)) { 87 return b; 88 } else { 89 byte[] t = new byte[len]; 90 System.arraycopy(b, ofs, t, 0, len); 91 return t; 92 } 93 } 94 95 /** 96 * Perform an RSA public key operation. 97 */ 98 public static byte[] rsa(byte[] msg, RSAPublicKey key) 99 throws BadPaddingException { 100 return crypt(msg, key.getModulus(), key.getPublicExponent()); 101 } 102 103 /** 104 * Perform an RSA private key operation. Uses CRT if the key is a 105 * CRT key with additional verification check after the signature 106 * is computed. 107 */ 108 @Deprecated 109 public static byte[] rsa(byte[] msg, RSAPrivateKey key) 110 throws BadPaddingException { 111 return rsa(msg, key, true); 112 } 113 114 /** 115 * Perform an RSA private key operation. Uses CRT if the key is a 116 * CRT key. Set 'verify' to true if this function is used for 117 * generating a signature. 118 */ 119 public static byte[] rsa(byte[] msg, RSAPrivateKey key, boolean verify) 120 throws BadPaddingException { 121 if (key instanceof RSAPrivateCrtKey) { 122 return crtCrypt(msg, (RSAPrivateCrtKey)key, verify); 123 } else { 124 return priCrypt(msg, key.getModulus(), key.getPrivateExponent()); 125 } 126 } 127 128 /** 129 * RSA public key ops. Simple modPow(). 130 */ 131 private static byte[] crypt(byte[] msg, BigInteger n, BigInteger exp) 132 throws BadPaddingException { 133 BigInteger m = parseMsg(msg, n); 134 BigInteger c = m.modPow(exp, n); 135 return toByteArray(c, getByteLength(n)); 136 } 137 138 /** 139 * RSA non-CRT private key operations. 140 */ 141 private static byte[] priCrypt(byte[] msg, BigInteger n, BigInteger exp) 142 throws BadPaddingException { 143 144 BigInteger c = parseMsg(msg, n); 145 BlindingRandomPair brp = null; 146 BigInteger m; 147 if (ENABLE_BLINDING) { 148 brp = getBlindingRandomPair(null, exp, n); 149 c = c.multiply(brp.u).mod(n); 150 m = c.modPow(exp, n); 151 m = m.multiply(brp.v).mod(n); 152 } else { 153 m = c.modPow(exp, n); 154 } 155 156 return toByteArray(m, getByteLength(n)); 157 } 158 159 /** 160 * RSA private key operations with CRT. Algorithm and variable naming 161 * are taken from PKCS#1 v2.1, section 5.1.2. 162 */ 163 private static byte[] crtCrypt(byte[] msg, RSAPrivateCrtKey key, 164 boolean verify) throws BadPaddingException { 165 BigInteger n = key.getModulus(); 166 BigInteger c0 = parseMsg(msg, n); 167 BigInteger c = c0; 168 BigInteger p = key.getPrimeP(); 169 BigInteger q = key.getPrimeQ(); 170 BigInteger dP = key.getPrimeExponentP(); 171 BigInteger dQ = key.getPrimeExponentQ(); 172 BigInteger qInv = key.getCrtCoefficient(); 173 BigInteger e = key.getPublicExponent(); 174 BigInteger d = key.getPrivateExponent(); 175 176 BlindingRandomPair brp; 177 if (ENABLE_BLINDING) { 178 brp = getBlindingRandomPair(e, d, n); 179 c = c.multiply(brp.u).mod(n); 180 } 181 182 // m1 = c ^ dP mod p 183 BigInteger m1 = c.modPow(dP, p); 184 // m2 = c ^ dQ mod q 185 BigInteger m2 = c.modPow(dQ, q); 186 187 // h = (m1 - m2) * qInv mod p 188 BigInteger mtmp = m1.subtract(m2); 189 if (mtmp.signum() < 0) { 190 mtmp = mtmp.add(p); 191 } 192 BigInteger h = mtmp.multiply(qInv).mod(p); 193 194 // m = m2 + q * h 195 BigInteger m = h.multiply(q).add(m2); 196 197 if (ENABLE_BLINDING) { 198 m = m.multiply(brp.v).mod(n); 199 } 200 if (verify && !c0.equals(m.modPow(e, n))) { 201 throw new BadPaddingException("RSA private key operation failed"); 202 } 203 204 return toByteArray(m, getByteLength(n)); 205 } 206 207 /** 208 * Parse the msg into a BigInteger and check against the modulus n. 209 */ 210 private static BigInteger parseMsg(byte[] msg, BigInteger n) 211 throws BadPaddingException { 212 BigInteger m = new BigInteger(1, msg); 213 if (m.compareTo(n) >= 0) { 214 throw new BadPaddingException("Message is larger than modulus"); 215 } 216 return m; 217 } 218 219 /** 220 * Return the encoding of this BigInteger that is exactly len bytes long. 221 * Prefix/strip off leading 0x00 bytes if necessary. 222 * Precondition: bi must fit into len bytes 223 */ 224 private static byte[] toByteArray(BigInteger bi, int len) { 225 byte[] b = bi.toByteArray(); 226 int n = b.length; 227 if (n == len) { 228 return b; 229 } 230 // BigInteger prefixed a 0x00 byte for 2's complement form, remove it 231 if ((n == len + 1) && (b[0] == 0)) { 232 byte[] t = new byte[len]; 233 System.arraycopy(b, 1, t, 0, len); 234 return t; 235 } 236 // must be smaller 237 assert (n < len); 238 byte[] t = new byte[len]; 239 System.arraycopy(b, 0, t, (len - n), n); 240 return t; 241 } 242 243 /** 244 * Parameters (u,v) for RSA Blinding. This is described in the RSA 245 * Bulletin#2 (Jan 96) and other places: 246 * 247 * ftp://ftp.rsa.com/pub/pdfs/bull-2.pdf 248 * 249 * The standard RSA Blinding decryption requires the public key exponent 250 * (e) and modulus (n), and converts ciphertext (c) to plaintext (p). 251 * 252 * Before the modular exponentiation operation, the input message should 253 * be multiplied by (u (mod n)), and afterward the result is corrected 254 * by multiplying with (v (mod n)). The system should reject messages 255 * equal to (0 (mod n)). That is: 256 * 257 * 1. Generate r between 0 and n-1, relatively prime to n. 258 * 2. Compute x = (c*u) mod n 259 * 3. Compute y = (x^d) mod n 260 * 4. Compute p = (y*v) mod n 261 * 262 * The Java APIs allows for either standard RSAPrivateKey or 263 * RSAPrivateCrtKey RSA keys. 264 * 265 * If the public exponent is available to us (e.g. RSAPrivateCrtKey), 266 * choose a random r, then let (u, v): 267 * 268 * u = r ^ e mod n 269 * v = r ^ (-1) mod n 270 * 271 * The proof follows: 272 * 273 * p = (((c * u) ^ d mod n) * v) mod n 274 * = ((c ^ d) * (u ^ d) * v) mod n 275 * = ((c ^ d) * (r ^ e) ^ d) * (r ^ (-1))) mod n 276 * = ((c ^ d) * (r ^ (e * d)) * (r ^ (-1))) mod n 277 * = ((c ^ d) * (r ^ 1) * (r ^ (-1))) mod n (see below) 278 * = (c ^ d) mod n 279 * 280 * because in RSA cryptosystem, d is the multiplicative inverse of e: 281 * 282 * (r^(e * d)) mod n 283 * = (r ^ 1) mod n 284 * = r mod n 285 * 286 * However, if the public exponent is not available (e.g. RSAPrivateKey), 287 * we mitigate the timing issue by using a similar random number blinding 288 * approach using the private key: 289 * 290 * u = r 291 * v = ((r ^ (-1)) ^ d) mod n 292 * 293 * This returns the same plaintext because: 294 * 295 * p = (((c * u) ^ d mod n) * v) mod n 296 * = ((c ^ d) * (u ^ d) * v) mod n 297 * = ((c ^ d) * (u ^ d) * ((u ^ (-1)) ^d)) mod n 298 * = (c ^ d) mod n 299 * 300 * Computing inverses mod n and random number generation is slow, so 301 * it is often not practical to generate a new random (u, v) pair for 302 * each new exponentiation. The calculation of parameters might even be 303 * subject to timing attacks. However, (u, v) pairs should not be 304 * reused since they themselves might be compromised by timing attacks, 305 * leaving the private exponent vulnerable. An efficient solution to 306 * this problem is update u and v before each modular exponentiation 307 * step by computing: 308 * 309 * u = u ^ 2 310 * v = v ^ 2 311 * 312 * The total performance cost is small. 313 */ 314 private static final class BlindingRandomPair { 315 final BigInteger u; 316 final BigInteger v; 317 318 BlindingRandomPair(BigInteger u, BigInteger v) { 319 this.u = u; 320 this.v = v; 321 } 322 } 323 324 /** 325 * Set of blinding parameters for a given RSA key. 326 * 327 * The RSA modulus is usually unique, so we index by modulus in 328 * {@code blindingCache}. However, to protect against the unlikely 329 * case of two keys sharing the same modulus, we also store the public 330 * or the private exponent. This means we cannot cache blinding 331 * parameters for multiple keys that share the same modulus, but 332 * since sharing moduli is fundamentally broken and insecure, this 333 * does not matter. 334 */ 335 private static final class BlindingParameters { 336 private static final BigInteger BIG_TWO = BigInteger.valueOf(2L); 337 338 // RSA public exponent 339 private final BigInteger e; 340 341 // hash code of RSA private exponent 342 private final BigInteger d; 343 344 // r ^ e mod n (CRT), or r mod n (Non-CRT) 345 private BigInteger u; 346 347 // r ^ (-1) mod n (CRT) , or ((r ^ (-1)) ^ d) mod n (Non-CRT) 348 private BigInteger v; 349 350 // e: the public exponent 351 // d: the private exponent 352 // n: the modulus 353 BlindingParameters(BigInteger e, BigInteger d, BigInteger n) { 354 this.u = null; 355 this.v = null; 356 this.e = e; 357 this.d = d; 358 359 int len = n.bitLength(); 360 SecureRandom random = JCAUtil.getSecureRandom(); 361 u = new BigInteger(len, random).mod(n); 362 // Although the possibility is very much limited that u is zero 363 // or is not relatively prime to n, we still want to be careful 364 // about the special value. 365 // 366 // Secure random generation is expensive, try to use BigInteger.ONE 367 // this time if this new generated random number is zero or is not 368 // relatively prime to n. Next time, new generated secure random 369 // number will be used instead. 370 if (u.equals(BigInteger.ZERO)) { 371 u = BigInteger.ONE; // use 1 this time 372 } 373 374 try { 375 // The call to BigInteger.modInverse() checks that u is 376 // relatively prime to n. Otherwise, ArithmeticException is 377 // thrown. 378 v = u.modInverse(n); 379 } catch (ArithmeticException ae) { 380 // if u is not relatively prime to n, use 1 this time 381 u = BigInteger.ONE; 382 v = BigInteger.ONE; 383 } 384 385 if (e != null) { 386 u = u.modPow(e, n); // e: the public exponent 387 // u: random ^ e 388 // v: random ^ (-1) 389 } else { 390 v = v.modPow(d, n); // d: the private exponent 391 // u: random 392 // v: random ^ (-d) 393 } 394 } 395 396 // return null if need to reset the parameters 397 BlindingRandomPair getBlindingRandomPair( 398 BigInteger e, BigInteger d, BigInteger n) { 399 400 if ((this.e != null && this.e.equals(e)) || 401 (this.d != null && this.d.equals(d))) { 402 403 BlindingRandomPair brp = null; 404 synchronized (this) { 405 if (!u.equals(BigInteger.ZERO) && 406 !v.equals(BigInteger.ZERO)) { 407 408 brp = new BlindingRandomPair(u, v); 409 if (u.compareTo(BigInteger.ONE) <= 0 || 410 v.compareTo(BigInteger.ONE) <= 0) { 411 412 // need to reset the random pair next time 413 u = BigInteger.ZERO; 414 v = BigInteger.ZERO; 415 } else { 416 u = u.modPow(BIG_TWO, n); 417 v = v.modPow(BIG_TWO, n); 418 } 419 } // Otherwise, need to reset the random pair. 420 } 421 return brp; 422 } 423 424 return null; 425 } 426 } 427 428 private static BlindingRandomPair getBlindingRandomPair( 429 BigInteger e, BigInteger d, BigInteger n) { 430 431 BlindingParameters bps = null; 432 synchronized (blindingCache) { 433 bps = blindingCache.get(n); 434 } 435 436 if (bps == null) { 437 bps = new BlindingParameters(e, d, n); 438 synchronized (blindingCache) { 439 blindingCache.putIfAbsent(n, bps); 440 } 441 } 442 443 BlindingRandomPair brp = bps.getBlindingRandomPair(e, d, n); 444 if (brp == null) { 445 // need to reset the blinding parameters 446 bps = new BlindingParameters(e, d, n); 447 synchronized (blindingCache) { 448 blindingCache.replace(n, bps); 449 } 450 brp = bps.getBlindingRandomPair(e, d, n); 451 } 452 453 return brp; 454 } 455 456} 457