RSAPadding.java revision 12745:f068a4ffddd2
1/* 2 * Copyright (c) 2003, 2013, 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.util.*; 29 30import java.security.*; 31import java.security.spec.*; 32 33import javax.crypto.BadPaddingException; 34import javax.crypto.spec.PSource; 35import javax.crypto.spec.OAEPParameterSpec; 36 37import sun.security.jca.JCAUtil; 38 39/** 40 * RSA padding and unpadding. 41 * 42 * The various PKCS#1 versions can be found in the EMC/RSA Labs 43 * web site, which is currently: 44 * 45 * http://www.emc.com/emc-plus/rsa-labs/index.htm 46 * 47 * or in the IETF RFCs derived from the above PKCS#1 standards. 48 * 49 * RFC 2313: v1.5 50 * RFC 2437: v2.0 51 * RFC 3447: v2.1 52 * 53 * The format of PKCS#1 v1.5 padding is: 54 * 55 * 0x00 | BT | PS...PS | 0x00 | data...data 56 * 57 * where BT is the blocktype (1 or 2). The length of the entire string 58 * must be the same as the size of the modulus (i.e. 128 byte for a 1024 bit 59 * key). Per spec, the padding string must be at least 8 bytes long. That 60 * leaves up to (length of key in bytes) - 11 bytes for the data. 61 * 62 * OAEP padding was introduced in PKCS#1 v2.0 and is a bit more complicated 63 * and has a number of options. We support: 64 * 65 * . arbitrary hash functions ('Hash' in the specification), MessageDigest 66 * implementation must be available 67 * . MGF1 as the mask generation function 68 * . the empty string as the default value for label L and whatever 69 * specified in javax.crypto.spec.OAEPParameterSpec 70 * 71 * The algorithms (representations) are forwards-compatible: that is, 72 * the algorithm described in previous releases are in later releases. 73 * However, additional comments/checks/clarifications were added to the 74 * later versions based on real-world experience (e.g. stricter v1.5 75 * format checking.) 76 * 77 * Note: RSA keys should be at least 512 bits long 78 * 79 * @since 1.5 80 * @author Andreas Sterbenz 81 */ 82public final class RSAPadding { 83 84 // NOTE: the constants below are embedded in the JCE RSACipher class 85 // file. Do not change without coordinating the update 86 87 // PKCS#1 v1.5 padding, blocktype 1 (signing) 88 public static final int PAD_BLOCKTYPE_1 = 1; 89 // PKCS#1 v1.5 padding, blocktype 2 (encryption) 90 public static final int PAD_BLOCKTYPE_2 = 2; 91 // nopadding. Does not do anything, but allows simpler RSACipher code 92 public static final int PAD_NONE = 3; 93 // PKCS#1 v2.1 OAEP padding 94 public static final int PAD_OAEP_MGF1 = 4; 95 96 // type, one of PAD_* 97 private final int type; 98 99 // size of the padded block (i.e. size of the modulus) 100 private final int paddedSize; 101 102 // PRNG used to generate padding bytes (PAD_BLOCKTYPE_2, PAD_OAEP_MGF1) 103 private SecureRandom random; 104 105 // maximum size of the data 106 private final int maxDataSize; 107 108 // OAEP: main messagedigest 109 private MessageDigest md; 110 111 // OAEP: message digest for MGF1 112 private MessageDigest mgfMd; 113 114 // OAEP: value of digest of data (user-supplied or zero-length) using md 115 private byte[] lHash; 116 117 /** 118 * Get a RSAPadding instance of the specified type. 119 * Keys used with this padding must be paddedSize bytes long. 120 */ 121 public static RSAPadding getInstance(int type, int paddedSize) 122 throws InvalidKeyException, InvalidAlgorithmParameterException { 123 return new RSAPadding(type, paddedSize, null, null); 124 } 125 126 /** 127 * Get a RSAPadding instance of the specified type. 128 * Keys used with this padding must be paddedSize bytes long. 129 */ 130 public static RSAPadding getInstance(int type, int paddedSize, 131 SecureRandom random) throws InvalidKeyException, 132 InvalidAlgorithmParameterException { 133 return new RSAPadding(type, paddedSize, random, null); 134 } 135 136 /** 137 * Get a RSAPadding instance of the specified type, which must be 138 * OAEP. Keys used with this padding must be paddedSize bytes long. 139 */ 140 public static RSAPadding getInstance(int type, int paddedSize, 141 SecureRandom random, OAEPParameterSpec spec) 142 throws InvalidKeyException, InvalidAlgorithmParameterException { 143 return new RSAPadding(type, paddedSize, random, spec); 144 } 145 146 // internal constructor 147 private RSAPadding(int type, int paddedSize, SecureRandom random, 148 OAEPParameterSpec spec) throws InvalidKeyException, 149 InvalidAlgorithmParameterException { 150 this.type = type; 151 this.paddedSize = paddedSize; 152 this.random = random; 153 if (paddedSize < 64) { 154 // sanity check, already verified in RSASignature/RSACipher 155 throw new InvalidKeyException("Padded size must be at least 64"); 156 } 157 switch (type) { 158 case PAD_BLOCKTYPE_1: 159 case PAD_BLOCKTYPE_2: 160 maxDataSize = paddedSize - 11; 161 break; 162 case PAD_NONE: 163 maxDataSize = paddedSize; 164 break; 165 case PAD_OAEP_MGF1: 166 String mdName = "SHA-1"; 167 String mgfMdName = "SHA-1"; 168 byte[] digestInput = null; 169 try { 170 if (spec != null) { 171 mdName = spec.getDigestAlgorithm(); 172 String mgfName = spec.getMGFAlgorithm(); 173 if (!mgfName.equalsIgnoreCase("MGF1")) { 174 throw new InvalidAlgorithmParameterException 175 ("Unsupported MGF algo: " + mgfName); 176 } 177 mgfMdName = ((MGF1ParameterSpec)spec.getMGFParameters()) 178 .getDigestAlgorithm(); 179 PSource pSrc = spec.getPSource(); 180 String pSrcAlgo = pSrc.getAlgorithm(); 181 if (!pSrcAlgo.equalsIgnoreCase("PSpecified")) { 182 throw new InvalidAlgorithmParameterException 183 ("Unsupported pSource algo: " + pSrcAlgo); 184 } 185 digestInput = ((PSource.PSpecified) pSrc).getValue(); 186 } 187 md = MessageDigest.getInstance(mdName); 188 mgfMd = MessageDigest.getInstance(mgfMdName); 189 } catch (NoSuchAlgorithmException e) { 190 throw new InvalidKeyException 191 ("Digest " + mdName + " not available", e); 192 } 193 lHash = getInitialHash(md, digestInput); 194 int digestLen = lHash.length; 195 maxDataSize = paddedSize - 2 - 2 * digestLen; 196 if (maxDataSize <= 0) { 197 throw new InvalidKeyException 198 ("Key is too short for encryption using OAEPPadding" + 199 " with " + mdName + " and MGF1" + mgfMdName); 200 } 201 break; 202 default: 203 throw new InvalidKeyException("Invalid padding: " + type); 204 } 205 } 206 207 // cache of hashes of zero length data 208 private static final Map<String,byte[]> emptyHashes = 209 Collections.synchronizedMap(new HashMap<String,byte[]>()); 210 211 /** 212 * Return the value of the digest using the specified message digest 213 * <code>md</code> and the digest input <code>digestInput</code>. 214 * if <code>digestInput</code> is null or 0-length, zero length 215 * is used to generate the initial digest. 216 * Note: the md object must be in reset state 217 */ 218 private static byte[] getInitialHash(MessageDigest md, 219 byte[] digestInput) { 220 byte[] result; 221 if ((digestInput == null) || (digestInput.length == 0)) { 222 String digestName = md.getAlgorithm(); 223 result = emptyHashes.get(digestName); 224 if (result == null) { 225 result = md.digest(); 226 emptyHashes.put(digestName, result); 227 } 228 } else { 229 result = md.digest(digestInput); 230 } 231 return result; 232 } 233 234 /** 235 * Return the maximum size of the plaintext data that can be processed 236 * using this object. 237 */ 238 public int getMaxDataSize() { 239 return maxDataSize; 240 } 241 242 /** 243 * Pad the data and return the padded block. 244 */ 245 public byte[] pad(byte[] data, int ofs, int len) 246 throws BadPaddingException { 247 return pad(RSACore.convert(data, ofs, len)); 248 } 249 250 /** 251 * Pad the data and return the padded block. 252 */ 253 public byte[] pad(byte[] data) throws BadPaddingException { 254 if (data.length > maxDataSize) { 255 throw new BadPaddingException("Data must be shorter than " 256 + (maxDataSize + 1) + " bytes"); 257 } 258 switch (type) { 259 case PAD_NONE: 260 return data; 261 case PAD_BLOCKTYPE_1: 262 case PAD_BLOCKTYPE_2: 263 return padV15(data); 264 case PAD_OAEP_MGF1: 265 return padOAEP(data); 266 default: 267 throw new AssertionError(); 268 } 269 } 270 271 /** 272 * Unpad the padded block and return the data. 273 */ 274 public byte[] unpad(byte[] padded, int ofs, int len) 275 throws BadPaddingException { 276 return unpad(RSACore.convert(padded, ofs, len)); 277 } 278 279 /** 280 * Unpad the padded block and return the data. 281 */ 282 public byte[] unpad(byte[] padded) throws BadPaddingException { 283 if (padded.length != paddedSize) { 284 throw new BadPaddingException("Decryption error"); 285 } 286 switch (type) { 287 case PAD_NONE: 288 return padded; 289 case PAD_BLOCKTYPE_1: 290 case PAD_BLOCKTYPE_2: 291 return unpadV15(padded); 292 case PAD_OAEP_MGF1: 293 return unpadOAEP(padded); 294 default: 295 throw new AssertionError(); 296 } 297 } 298 299 /** 300 * PKCS#1 v1.5 padding (blocktype 1 and 2). 301 */ 302 private byte[] padV15(byte[] data) throws BadPaddingException { 303 byte[] padded = new byte[paddedSize]; 304 System.arraycopy(data, 0, padded, paddedSize - data.length, 305 data.length); 306 int psSize = paddedSize - 3 - data.length; 307 int k = 0; 308 padded[k++] = 0; 309 padded[k++] = (byte)type; 310 if (type == PAD_BLOCKTYPE_1) { 311 // blocktype 1: all padding bytes are 0xff 312 while (psSize-- > 0) { 313 padded[k++] = (byte)0xff; 314 } 315 } else { 316 // blocktype 2: padding bytes are random non-zero bytes 317 if (random == null) { 318 random = JCAUtil.getSecureRandom(); 319 } 320 // generate non-zero padding bytes 321 // use a buffer to reduce calls to SecureRandom 322 while (psSize > 0) { 323 // extra bytes to avoid zero bytes, 324 // number of zero bytes <= 4 in 98% cases 325 byte[] r = new byte[psSize + 4]; 326 random.nextBytes(r); 327 for (int i = 0; i < r.length && psSize > 0; i++) { 328 if (r[i] != 0) { 329 padded[k++] = r[i]; 330 psSize--; 331 } 332 } 333 } 334 } 335 return padded; 336 } 337 338 /** 339 * PKCS#1 v1.5 unpadding (blocktype 1 (signature) and 2 (encryption)). 340 * 341 * Note that we want to make it a constant-time operation 342 */ 343 private byte[] unpadV15(byte[] padded) throws BadPaddingException { 344 int k = 0; 345 boolean bp = false; 346 347 if (padded[k++] != 0) { 348 bp = true; 349 } 350 if (padded[k++] != type) { 351 bp = true; 352 } 353 int p = 0; 354 while (k < padded.length) { 355 int b = padded[k++] & 0xff; 356 if ((b == 0) && (p == 0)) { 357 p = k; 358 } 359 if ((k == padded.length) && (p == 0)) { 360 bp = true; 361 } 362 if ((type == PAD_BLOCKTYPE_1) && (b != 0xff) && 363 (p == 0)) { 364 bp = true; 365 } 366 } 367 int n = padded.length - p; 368 if (n > maxDataSize) { 369 bp = true; 370 } 371 372 // copy useless padding array for a constant-time method 373 byte[] padding = new byte[p]; 374 System.arraycopy(padded, 0, padding, 0, p); 375 376 byte[] data = new byte[n]; 377 System.arraycopy(padded, p, data, 0, n); 378 379 BadPaddingException bpe = new BadPaddingException("Decryption error"); 380 381 if (bp) { 382 throw bpe; 383 } else { 384 return data; 385 } 386 } 387 388 /** 389 * PKCS#1 v2.0 OAEP padding (MGF1). 390 * Paragraph references refer to PKCS#1 v2.1 (June 14, 2002) 391 */ 392 private byte[] padOAEP(byte[] M) throws BadPaddingException { 393 if (random == null) { 394 random = JCAUtil.getSecureRandom(); 395 } 396 int hLen = lHash.length; 397 398 // 2.d: generate a random octet string seed of length hLen 399 // if necessary 400 byte[] seed = new byte[hLen]; 401 random.nextBytes(seed); 402 403 // buffer for encoded message EM 404 byte[] EM = new byte[paddedSize]; 405 406 // start and length of seed (as index into EM) 407 int seedStart = 1; 408 int seedLen = hLen; 409 410 // copy seed into EM 411 System.arraycopy(seed, 0, EM, seedStart, seedLen); 412 413 // start and length of data block DB in EM 414 // we place it inside of EM to reduce copying 415 int dbStart = hLen + 1; 416 int dbLen = EM.length - dbStart; 417 418 // start of message M in EM 419 int mStart = paddedSize - M.length; 420 421 // build DB 422 // 2.b: Concatenate lHash, PS, a single octet with hexadecimal value 423 // 0x01, and the message M to form a data block DB of length 424 // k - hLen -1 octets as DB = lHash || PS || 0x01 || M 425 // (note that PS is all zeros) 426 System.arraycopy(lHash, 0, EM, dbStart, hLen); 427 EM[mStart - 1] = 1; 428 System.arraycopy(M, 0, EM, mStart, M.length); 429 430 // produce maskedDB 431 mgf1(EM, seedStart, seedLen, EM, dbStart, dbLen); 432 433 // produce maskSeed 434 mgf1(EM, dbStart, dbLen, EM, seedStart, seedLen); 435 436 return EM; 437 } 438 439 /** 440 * PKCS#1 v2.1 OAEP unpadding (MGF1). 441 */ 442 private byte[] unpadOAEP(byte[] padded) throws BadPaddingException { 443 byte[] EM = padded; 444 boolean bp = false; 445 int hLen = lHash.length; 446 447 if (EM[0] != 0) { 448 bp = true; 449 } 450 451 int seedStart = 1; 452 int seedLen = hLen; 453 454 int dbStart = hLen + 1; 455 int dbLen = EM.length - dbStart; 456 457 mgf1(EM, dbStart, dbLen, EM, seedStart, seedLen); 458 mgf1(EM, seedStart, seedLen, EM, dbStart, dbLen); 459 460 // verify lHash == lHash' 461 for (int i = 0; i < hLen; i++) { 462 if (lHash[i] != EM[dbStart + i]) { 463 bp = true; 464 } 465 } 466 467 int padStart = dbStart + hLen; 468 int onePos = -1; 469 470 for (int i = padStart; i < EM.length; i++) { 471 int value = EM[i]; 472 if (onePos == -1) { 473 if (value == 0x00) { 474 // continue; 475 } else if (value == 0x01) { 476 onePos = i; 477 } else { // Anything other than {0,1} is bad. 478 bp = true; 479 } 480 } 481 } 482 483 // We either ran off the rails or found something other than 0/1. 484 if (onePos == -1) { 485 bp = true; 486 onePos = EM.length - 1; // Don't inadvertently return any data. 487 } 488 489 int mStart = onePos + 1; 490 491 // copy useless padding array for a constant-time method 492 byte [] tmp = new byte[mStart - padStart]; 493 System.arraycopy(EM, padStart, tmp, 0, tmp.length); 494 495 byte [] m = new byte[EM.length - mStart]; 496 System.arraycopy(EM, mStart, m, 0, m.length); 497 498 BadPaddingException bpe = new BadPaddingException("Decryption error"); 499 500 if (bp) { 501 throw bpe; 502 } else { 503 return m; 504 } 505 } 506 507 /** 508 * Compute MGF1 using mgfMD as the message digest. 509 * Note that we combine MGF1 with the XOR operation to reduce data 510 * copying. 511 * 512 * We generate maskLen bytes of MGF1 from the seed and XOR it into 513 * out[] starting at outOfs; 514 */ 515 private void mgf1(byte[] seed, int seedOfs, int seedLen, 516 byte[] out, int outOfs, int maskLen) throws BadPaddingException { 517 byte[] C = new byte[4]; // 32 bit counter 518 byte[] digest = new byte[mgfMd.getDigestLength()]; 519 while (maskLen > 0) { 520 mgfMd.update(seed, seedOfs, seedLen); 521 mgfMd.update(C); 522 try { 523 mgfMd.digest(digest, 0, digest.length); 524 } catch (DigestException e) { 525 // should never happen 526 throw new BadPaddingException(e.toString()); 527 } 528 for (int i = 0; (i < digest.length) && (maskLen > 0); maskLen--) { 529 out[outOfs++] ^= digest[i++]; 530 } 531 if (maskLen > 0) { 532 // increment counter 533 for (int i = C.length - 1; (++C[i] == 0) && (i > 0); i--) { 534 // empty 535 } 536 } 537 } 538 } 539} 540