2
|
1 |
/*
|
5506
|
2 |
* Copyright (c) 2003, 2006, Oracle and/or its affiliates. All rights reserved.
|
2
|
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
|
5506
|
7 |
* published by the Free Software Foundation. Oracle designates this
|
2
|
8 |
* particular file as subject to the "Classpath" exception as provided
|
5506
|
9 |
* by Oracle in the LICENSE file that accompanied this code.
|
2
|
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 |
*
|
5506
|
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.
|
2
|
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<BigInteger,BlindingParameters>();
|
|
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 |
}
|