| Frames | No Frames |
1: /* RSA.java -- 2: Copyright (C) 2001, 2002, 2003, 2006 Free Software Foundation, Inc. 3: 4: This file is a part of GNU Classpath. 5: 6: GNU Classpath is free software; you can redistribute it and/or modify 7: it under the terms of the GNU General Public License as published by 8: the Free Software Foundation; either version 2 of the License, or (at 9: your option) any later version. 10: 11: GNU Classpath is distributed in the hope that it will be useful, but 12: WITHOUT ANY WARRANTY; without even the implied warranty of 13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14: General Public License for more details. 15: 16: You should have received a copy of the GNU General Public License 17: along with GNU Classpath; if not, write to the Free Software 18: Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 19: USA 20: 21: Linking this library statically or dynamically with other modules is 22: making a combined work based on this library. Thus, the terms and 23: conditions of the GNU General Public License cover the whole 24: combination. 25: 26: As a special exception, the copyright holders of this library give you 27: permission to link this library with independent modules to produce an 28: executable, regardless of the license terms of these independent 29: modules, and to copy and distribute the resulting executable under 30: terms of your choice, provided that you also meet, for each linked 31: independent module, the terms and conditions of the license of that 32: module. An independent module is a module which is not derived from 33: or based on this library. If you modify this library, you may extend 34: this exception to your version of the library, but you are not 35: obligated to do so. If you do not wish to do so, delete this 36: exception statement from your version. */ 37: 38: 39: package gnu.java.security.sig.rsa; 40: 41: import gnu.java.security.Properties; 42: import gnu.java.security.util.PRNG; 43: 44: import java.math.BigInteger; 45: import java.security.PrivateKey; 46: import java.security.PublicKey; 47: import java.security.interfaces.RSAPrivateCrtKey; 48: import java.security.interfaces.RSAPrivateKey; 49: import java.security.interfaces.RSAPublicKey; 50: 51: /** 52: * Utility methods related to the RSA algorithm. 53: * <p> 54: * References: 55: * <ol> 56: * <li><a 57: * href="http://www.cosic.esat.kuleuven.ac.be/nessie/workshop/submissions/rsa-pss.zip"> 58: * RSA-PSS Signature Scheme with Appendix, part B.</a><br> 59: * Primitive specification and supporting documentation.<br> 60: * Jakob Jonsson and Burt Kaliski.</li> 61: * <li><a href="http://www.ietf.org/rfc/rfc3447.txt">Public-Key Cryptography 62: * Standards (PKCS) #1:</a><br> 63: * RSA Cryptography Specifications Version 2.1.<br> 64: * Jakob Jonsson and Burt Kaliski.</li> 65: * <li><a href="http://crypto.stanford.edu/~dabo/abstracts/ssl-timing.html"> 66: * Remote timing attacks are practical</a><br> 67: * D. Boneh and D. Brumley.</li> 68: * </ol> 69: */ 70: public class RSA 71: { 72: private static final BigInteger ZERO = BigInteger.ZERO; 73: 74: private static final BigInteger ONE = BigInteger.ONE; 75: 76: /** Our default source of randomness. */ 77: private static final PRNG prng = PRNG.getInstance(); 78: 79: /** Trivial private constructor to enforce Singleton pattern. */ 80: private RSA() 81: { 82: super(); 83: } 84: 85: /** 86: * An implementation of the <b>RSASP</b> method: Assuming that the designated 87: * RSA private key is a valid one, this method computes a <i>signature 88: * representative</i> for a designated <i>message representative</i> signed 89: * by the holder of the designated RSA private key. 90: * 91: * @param K the RSA private key. 92: * @param m the <i>message representative</i>: an integer between 93: * <code>0</code> and <code>n - 1</code>, where <code>n</code> 94: * is the RSA <i>modulus</i>. 95: * @return the <i>signature representative</i>, an integer between 96: * <code>0</code> and <code>n - 1</code>, where <code>n</code> 97: * is the RSA <i>modulus</i>. 98: * @throws ClassCastException if <code>K</code> is not an RSA one. 99: * @throws IllegalArgumentException if <code>m</code> (the <i>message 100: * representative</i>) is out of range. 101: */ 102: public static final BigInteger sign(final PrivateKey K, final BigInteger m) 103: { 104: try 105: { 106: return RSADP((RSAPrivateKey) K, m); 107: } 108: catch (IllegalArgumentException x) 109: { 110: throw new IllegalArgumentException("message representative out of range"); 111: } 112: } 113: 114: /** 115: * An implementation of the <b>RSAVP</b> method: Assuming that the designated 116: * RSA public key is a valid one, this method computes a <i>message 117: * representative</i> for the designated <i>signature representative</i> 118: * generated by an RSA private key, for a message intended for the holder of 119: * the designated RSA public key. 120: * 121: * @param K the RSA public key. 122: * @param s the <i>signature representative</i>, an integer between 123: * <code>0</code> and <code>n - 1</code>, where <code>n</code> 124: * is the RSA <i>modulus</i>. 125: * @return a <i>message representative</i>: an integer between <code>0</code> 126: * and <code>n - 1</code>, where <code>n</code> is the RSA 127: * <i>modulus</i>. 128: * @throws ClassCastException if <code>K</code> is not an RSA one. 129: * @throws IllegalArgumentException if <code>s</code> (the <i>signature 130: * representative</i>) is out of range. 131: */ 132: public static final BigInteger verify(final PublicKey K, final BigInteger s) 133: { 134: try 135: { 136: return RSAEP((RSAPublicKey) K, s); 137: } 138: catch (IllegalArgumentException x) 139: { 140: throw new IllegalArgumentException("signature representative out of range"); 141: } 142: } 143: 144: /** 145: * An implementation of the <code>RSAEP</code> algorithm. 146: * 147: * @param K the recipient's RSA public key. 148: * @param m the message representative as an MPI. 149: * @return the resulting MPI --an MPI between <code>0</code> and 150: * <code>n - 1</code> (<code>n</code> being the public shared 151: * modulus)-- that will eventually be padded with an appropriate 152: * framing/padding scheme. 153: * @throws ClassCastException if <code>K</code> is not an RSA one. 154: * @throws IllegalArgumentException if <code>m</code>, the message 155: * representative is not between <code>0</code> and 156: * <code>n - 1</code> (<code>n</code> being the public shared 157: * modulus). 158: */ 159: public static final BigInteger encrypt(final PublicKey K, final BigInteger m) 160: { 161: try 162: { 163: return RSAEP((RSAPublicKey) K, m); 164: } 165: catch (IllegalArgumentException x) 166: { 167: throw new IllegalArgumentException("message representative out of range"); 168: } 169: } 170: 171: /** 172: * An implementation of the <code>RSADP</code> algorithm. 173: * 174: * @param K the recipient's RSA private key. 175: * @param c the ciphertext representative as an MPI. 176: * @return the message representative, an MPI between <code>0</code> and 177: * <code>n - 1</code> (<code>n</code> being the shared public 178: * modulus). 179: * @throws ClassCastException if <code>K</code> is not an RSA one. 180: * @throws IllegalArgumentException if <code>c</code>, the ciphertext 181: * representative is not between <code>0</code> and 182: * <code>n - 1</code> (<code>n</code> being the shared public 183: * modulus). 184: */ 185: public static final BigInteger decrypt(final PrivateKey K, final BigInteger c) 186: { 187: try 188: { 189: return RSADP((RSAPrivateKey) K, c); 190: } 191: catch (IllegalArgumentException x) 192: { 193: throw new IllegalArgumentException("ciphertext representative out of range"); 194: } 195: } 196: 197: /** 198: * Converts a <i>multi-precision integer</i> (MPI) <code>s</code> into an 199: * octet sequence of length <code>k</code>. 200: * 201: * @param s the multi-precision integer to convert. 202: * @param k the length of the output. 203: * @return the result of the transform. 204: * @exception IllegalArgumentException if the length in octets of meaningful 205: * bytes of <code>s</code> is greater than <code>k</code>. 206: */ 207: public static final byte[] I2OSP(final BigInteger s, final int k) 208: { 209: byte[] result = s.toByteArray(); 210: if (result.length < k) 211: { 212: final byte[] newResult = new byte[k]; 213: System.arraycopy(result, 0, newResult, k - result.length, result.length); 214: result = newResult; 215: } 216: else if (result.length > k) 217: { // leftmost extra bytes should all be 0 218: final int limit = result.length - k; 219: for (int i = 0; i < limit; i++) 220: { 221: if (result[i] != 0x00) 222: throw new IllegalArgumentException("integer too large"); 223: } 224: final byte[] newResult = new byte[k]; 225: System.arraycopy(result, limit, newResult, 0, k); 226: result = newResult; 227: } 228: return result; 229: } 230: 231: private static final BigInteger RSAEP(final RSAPublicKey K, final BigInteger m) 232: { 233: // 1. If the representative m is not between 0 and n - 1, output 234: // "representative out of range" and stop. 235: final BigInteger n = K.getModulus(); 236: if (m.compareTo(ZERO) < 0 || m.compareTo(n.subtract(ONE)) > 0) 237: throw new IllegalArgumentException(); 238: // 2. Let c = m^e mod n. 239: final BigInteger e = K.getPublicExponent(); 240: final BigInteger result = m.modPow(e, n); 241: // 3. Output c. 242: return result; 243: } 244: 245: private static final BigInteger RSADP(final RSAPrivateKey K, BigInteger c) 246: { 247: // 1. If the representative c is not between 0 and n - 1, output 248: // "representative out of range" and stop. 249: final BigInteger n = K.getModulus(); 250: if (c.compareTo(ZERO) < 0 || c.compareTo(n.subtract(ONE)) > 0) 251: throw new IllegalArgumentException(); 252: // 2. The representative m is computed as follows. 253: BigInteger result; 254: if (! (K instanceof RSAPrivateCrtKey)) 255: { 256: // a. If the first form (n, d) of K is used, let m = c^d mod n. 257: final BigInteger d = K.getPrivateExponent(); 258: result = c.modPow(d, n); 259: } 260: else 261: { 262: // from [3] p.13 --see class docs: 263: // The RSA blinding operation calculates x = (r^e) * g mod n before 264: // decryption, where r is random, e is the RSA encryption exponent, and 265: // g is the ciphertext to be decrypted. x is then decrypted as normal, 266: // followed by division by r, i.e. (x^e) / r mod n. Since r is random, 267: // x is random and timing the decryption should not reveal information 268: // about the key. Note that r should be a new random number for every 269: // decryption. 270: final boolean rsaBlinding = Properties.doRSABlinding(); 271: BigInteger r = null; 272: BigInteger e = null; 273: if (rsaBlinding) 274: { // pre-decryption 275: r = newR(n); 276: e = ((RSAPrivateCrtKey) K).getPublicExponent(); 277: final BigInteger x = r.modPow(e, n).multiply(c).mod(n); 278: c = x; 279: } 280: // b. If the second form (p, q, dP, dQ, qInv) and (r_i, d_i, t_i) 281: // of K is used, proceed as follows: 282: final BigInteger p = ((RSAPrivateCrtKey) K).getPrimeP(); 283: final BigInteger q = ((RSAPrivateCrtKey) K).getPrimeQ(); 284: final BigInteger dP = ((RSAPrivateCrtKey) K).getPrimeExponentP(); 285: final BigInteger dQ = ((RSAPrivateCrtKey) K).getPrimeExponentQ(); 286: final BigInteger qInv = ((RSAPrivateCrtKey) K).getCrtCoefficient(); 287: // i. Let m_1 = c^dP mod p and m_2 = c^dQ mod q. 288: final BigInteger m_1 = c.modPow(dP, p); 289: final BigInteger m_2 = c.modPow(dQ, q); 290: // ii. If u > 2, let m_i = c^(d_i) mod r_i, i = 3, ..., u. 291: // iii. Let h = (m_1 - m_2) * qInv mod p. 292: final BigInteger h = m_1.subtract(m_2).multiply(qInv).mod(p); 293: // iv. Let m = m_2 + q * h. 294: result = m_2.add(q.multiply(h)); 295: if (rsaBlinding) // post-decryption 296: result = result.multiply(r.modInverse(n)).mod(n); 297: } 298: // 3. Output m 299: return result; 300: } 301: 302: /** 303: * Returns a random MPI with a random bit-length of the form <code>8b</code>, 304: * where <code>b</code> is in the range <code>[32..64]</code>. 305: * 306: * @return a random MPI whose length in bytes is between 32 and 64 inclusive. 307: */ 308: private static final BigInteger newR(final BigInteger N) 309: { 310: final int upper = (N.bitLength() + 7) / 8; 311: final int lower = upper / 2; 312: final byte[] bl = new byte[1]; 313: int b; 314: do 315: { 316: prng.nextBytes(bl); 317: b = bl[0] & 0xFF; 318: } 319: while (b < lower || b > upper); 320: final byte[] buffer = new byte[b]; // 256-bit MPI 321: prng.nextBytes(buffer); 322: return new BigInteger(1, buffer); 323: } 324: }