1 /*
2 * Copyright (c) 2003, 2006, 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
26 package sun.security.rsa;
27
28 import java.math.BigInteger;
29 import java.util.*;
30
31 import java.security.SecureRandom;
32 import java.security.interfaces.*;
33
34 import javax.crypto.BadPaddingException;
35
36 import 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 */
51 public final class RSACore {
52
53 private RSACore() {
54 // empty
55 }
56
57 /**
58 * Return the number of bytes required to store the magnitude byte[] of
59 * this BigInteger. Do not count a 0x00 byte toByteArray() would
60 * prefix for 2's complement form.
61 */
62 public static int getByteLength(BigInteger b) {
63 int n = b.bitLength();
64 return (n + 7) >> 3;
65 }
66
67 /**
68 * Return the number of bytes required to store the modulus of this
69 * RSA key.
70 */
71 public static int getByteLength(RSAKey key) {
72 return getByteLength(key.getModulus());
73 }
74
75 // temporary, used by RSACipher and RSAPadding. Move this somewhere else
76 public static byte[] convert(byte[] b, int ofs, int len) {
77 if ((ofs == 0) && (len == b.length)) {
78 return b;
79 } else {
80 byte[] t = new byte[len];
81 System.arraycopy(b, ofs, t, 0, len);
82 return t;
83 }
84 }
85
86 /**
87 * Perform an RSA public key operation.
88 */
89 public static byte[] rsa(byte[] msg, RSAPublicKey key)
90 throws BadPaddingException {
91 return crypt(msg, key.getModulus(), key.getPublicExponent());
92 }
93
94 /**
95 * Perform an RSA private key operation. Uses CRT if the key is a
96 * CRT key.
97 */
98 public static byte[] rsa(byte[] msg, RSAPrivateKey key)
99 throws BadPaddingException {
100 if (key instanceof RSAPrivateCrtKey) {
101 return crtCrypt(msg, (RSAPrivateCrtKey)key);
102 } else {
103 return crypt(msg, key.getModulus(), key.getPrivateExponent());
104 }
105 }
106
107 /**
108 * RSA public key ops and non-CRT private key ops. Simple modPow().
109 */
110 private static byte[] crypt(byte[] msg, BigInteger n, BigInteger exp)
111 throws BadPaddingException {
112 BigInteger m = parseMsg(msg, n);
113 BigInteger c = m.modPow(exp, n);
114 return toByteArray(c, getByteLength(n));
115 }
116
117 /**
118 * RSA private key operations with CRT. Algorithm and variable naming
119 * are taken from PKCS#1 v2.1, section 5.1.2.
120 *
121 * The only difference is the addition of blinding to twart timing attacks.
122 * This is described in the RSA Bulletin#2 (Jan 96) among other places.
123 * This means instead of implementing RSA as
124 * m = c ^ d mod n (or RSA in CRT variant)
125 * we do
126 * r = random(0, n-1)
127 * c' = c * r^e mod n
128 * m' = c' ^ d mod n (or RSA in CRT variant)
129 * m = m' * r^-1 mod n (where r^-1 is the modular inverse of r mod n)
130 * This works because r^(e*d) * r^-1 = r * r^-1 = 1 (all mod n)
131 *
132 * We do not generate new blinding parameters for each operation but reuse
133 * them BLINDING_MAX_REUSE times (see definition below).
134 */
135 private static byte[] crtCrypt(byte[] msg, RSAPrivateCrtKey key)
136 throws BadPaddingException {
137 BigInteger n = key.getModulus();
138 BigInteger c = parseMsg(msg, n);
139 BigInteger p = key.getPrimeP();
140 BigInteger q = key.getPrimeQ();
141 BigInteger dP = key.getPrimeExponentP();
142 BigInteger dQ = key.getPrimeExponentQ();
143 BigInteger qInv = key.getCrtCoefficient();
144
145 BlindingParameters params;
146 if (ENABLE_BLINDING) {
147 params = getBlindingParameters(key);
148 c = c.multiply(params.re).mod(n);
149 } else {
150 params = null;
151 }
152
153 // m1 = c ^ dP mod p
154 BigInteger m1 = c.modPow(dP, p);
155 // m2 = c ^ dQ mod q
156 BigInteger m2 = c.modPow(dQ, q);
157
158 // h = (m1 - m2) * qInv mod p
159 BigInteger mtmp = m1.subtract(m2);
160 if (mtmp.signum() < 0) {
161 mtmp = mtmp.add(p);
162 }
163 BigInteger h = mtmp.multiply(qInv).mod(p);
164
165 // m = m2 + q * h
166 BigInteger m = h.multiply(q).add(m2);
167
168 if (params != null) {
169 m = m.multiply(params.rInv).mod(n);
170 }
171
172 return toByteArray(m, getByteLength(n));
173 }
174
175 /**
176 * Parse the msg into a BigInteger and check against the modulus n.
177 */
178 private static BigInteger parseMsg(byte[] msg, BigInteger n)
179 throws BadPaddingException {
180 BigInteger m = new BigInteger(1, msg);
181 if (m.compareTo(n) >= 0) {
182 throw new BadPaddingException("Message is larger than modulus");
183 }
184 return m;
185 }
186
187 /**
188 * Return the encoding of this BigInteger that is exactly len bytes long.
189 * Prefix/strip off leading 0x00 bytes if necessary.
190 * Precondition: bi must fit into len bytes
191 */
192 private static byte[] toByteArray(BigInteger bi, int len) {
193 byte[] b = bi.toByteArray();
194 int n = b.length;
195 if (n == len) {
196 return b;
197 }
198 // BigInteger prefixed a 0x00 byte for 2's complement form, remove it
199 if ((n == len + 1) && (b[0] == 0)) {
200 byte[] t = new byte[len];
201 System.arraycopy(b, 1, t, 0, len);
202 return t;
203 }
204 // must be smaller
205 assert (n < len);
206 byte[] t = new byte[len];
207 System.arraycopy(b, 0, t, (len - n), n);
208 return t;
209 }
210
211 // globally enable/disable use of blinding
212 private final static boolean ENABLE_BLINDING = true;
213
214 // maximum number of times that we will use a set of blinding parameters
215 // value suggested by Paul Kocher (quoted by NSS)
216 private final static int BLINDING_MAX_REUSE = 50;
217
218 // cache for blinding parameters. Map<BigInteger, BlindingParameters>
219 // use a weak hashmap so that cached values are automatically cleared
220 // when the modulus is GC'ed
221 private final static Map<BigInteger, BlindingParameters> blindingCache =
222 new WeakHashMap<>();
223
224 /**
225 * Set of blinding parameters for a given RSA key.
226 *
227 * The RSA modulus is usually unique, so we index by modulus in
228 * blindingCache. However, to protect against the unlikely case of two
229 * keys sharing the same modulus, we also store the public exponent.
230 * This means we cannot cache blinding parameters for multiple keys that
231 * share the same modulus, but since sharing moduli is fundamentally broken
232 * an insecure, this does not matter.
233 */
234 private static final class BlindingParameters {
235 // e (RSA public exponent)
236 final BigInteger e;
237 // r ^ e mod n
238 final BigInteger re;
239 // inverse of r mod n
240 final BigInteger rInv;
241 // how many more times this parameter object can be used
242 private volatile int remainingUses;
243 BlindingParameters(BigInteger e, BigInteger re, BigInteger rInv) {
244 this.e = e;
245 this.re = re;
246 this.rInv = rInv;
247 // initialize remaining uses, subtract current use now
248 remainingUses = BLINDING_MAX_REUSE - 1;
249 }
250 boolean valid(BigInteger e) {
251 int k = remainingUses--;
252 return (k > 0) && this.e.equals(e);
253 }
254 }
255
256 /**
257 * Return valid RSA blinding parameters for the given private key.
258 * Use cached parameters if available. If not, generate new parameters
259 * and cache.
260 */
261 private static BlindingParameters getBlindingParameters
262 (RSAPrivateCrtKey key) {
263 BigInteger modulus = key.getModulus();
264 BigInteger e = key.getPublicExponent();
265 BlindingParameters params;
266 // we release the lock between get() and put()
267 // that means threads might concurrently generate new blinding
268 // parameters for the same modulus. this is only a slight waste
269 // of cycles and seems preferable in terms of scalability
270 // to locking out all threads while generating new parameters
271 synchronized (blindingCache) {
272 params = blindingCache.get(modulus);
273 }
274 if ((params != null) && params.valid(e)) {
275 return params;
276 }
277 int len = modulus.bitLength();
278 SecureRandom random = JCAUtil.getSecureRandom();
279 BigInteger r = new BigInteger(len, random).mod(modulus);
280 BigInteger re = r.modPow(e, modulus);
281 BigInteger rInv = r.modInverse(modulus);
282 params = new BlindingParameters(e, re, rInv);
283 synchronized (blindingCache) {
284 blindingCache.put(modulus, params);
285 }
286 return params;
287 }
288
289 }