|
RSAKeyPairGeneratorImpl |
|
1 /* $RCSfile: RSAKeyPairGeneratorImpl.java,v $
2 * $Revision: 1.4 $
3 * $Date: 2002/11/23 11:09:56 $
4 * $Author: uwe_guenther $
5 * $State: Exp $
6 *
7 * Created on November 8, 2001 11:25 AM
8 *
9 * Copyright (C) 2001 Uwe Guenther <uwe@cscc.de >
10 *
11 * This file is part of the jhbci JCE-ServiceProvider. The jhbci JCE-
12 * ServiceProvider is a library, written in JavaTM, that should be
13 * used in HBCI banking applications (clients and may be servers),
14 * to do cryptographic operations.
15 *
16 * The jhbci library is free software; you can redistribute it and/or
17 * modify it under the terms of the GNU Lesser General Public
18 * License as published by the Free Software Foundation; either
19 * version 2.1 of the License, or (at your option) any later version.
20 *
21 * The jhbci library is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
24 * Lesser General Public License for more details.
25 *
26 * You should have received a copy of the GNU Lesser General Public
27 * License along with this library; if not, write to the Free Software
28 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
29 *
30 */
31
32 package de.cscc.crypto.provider;
33
34 import java.math.BigInteger;
35 import java.security.InvalidAlgorithmParameterException;
36 import java.security.InvalidParameterException;
37 import java.security.KeyPair;
38 import java.security.SecureRandom;
39 import java.security.interfaces.RSAPrivateCrtKey;
40 import java.security.interfaces.RSAPublicKey;
41 import java.security.spec.AlgorithmParameterSpec;
42 import java.security.spec.RSAKeyGenParameterSpec;
43 import java.util.logging.Level;
44 import java.util.logging.Logger;
45
46 /**
47 * RSAKeyPairGeneratorImpl Class.
48 *
49 * <p>Defaults are:
50 * <ol>
51 * <li>public Exponent = F4 (Forth Fermat number (2^2^4)+1 = 65537 or
52 * 0x00010001)
53 * <li><code>keysize</code> (modulus length) = 768 bit
54 * <br><b>Note:</b> The keysize must be a positive multiple of
55 * 256 and equals or greater than 768.</li>
56 * <li><code>random = new java.security.SecureRandom()</code></li>
57 * </ol>
58 *
59 * @author <a href=mailto:uwe@cscc.de >Uwe Günther </a>
60 *
61 * @version $Revision: 1.4 $
62 */
63 final class RSAKeyPairGeneratorImpl {
64
65 /*
66 * First we declare all Stuff needed for logging with
67 * java.util.logging.*
68 */
69
70 /** The logger for this class.*/
71 private static final Logger log =
72 Logger.getLogger(RSAKeyPairGeneratorImpl.class.getName());
73
74 /** BigInteger.ZERO constant value. */
75 private static final BigInteger ZERO = BigInteger.ZERO;
76
77 /** BigInteger.ONE constant value. */
78 private static final BigInteger ONE = BigInteger.ONE;
79
80 /** BigInteger.TWO constant value. */
81 private static final BigInteger TWO = BigInteger.valueOf(2L);
82
83 /** Zero-th Fermat number (2^2^0)+1 = 3 or 0x00000011. */
84 private static final BigInteger F0 = BigInteger.valueOf(3L);
85
86 /** Forth Fermat number (2^2^4)+1 = 65537 or 0x00010001. */
87 private static final BigInteger F4 = BigInteger.valueOf(65537L);
88
89 /**
90 * Default keysize if {@link #initialize(int, SecureRandom)}
91 * or {@link #initialize(AlgorithmParameterSpec, SecureRandom)}
92 * will not be invoked.
93 */
94 private int keysize = 768;
95
96 /**
97 * Public Exponent. Forth Fermat number (2^2^4)+1 = 65537 or 0x00010001.
98 */
99 private BigInteger e = F4;
100
101 /**
102 * Default for the certainty.
103 *
104 * This value tells a BigInteger constructor the probability of errors
105 * for the constructor internal prime test in the form 2^-certainty,
106 * or you can say the probability a prime number exceeds 1-1/2^certainty.
107 *
108 * @see #generateStrongPrime(int)
109 * @see #generateKeyPair()
110 */
111 private int certainty = 101;
112
113 /**
114 * Default PRNG if {@link #initialize(int, SecureRandom)}
115 * or {@link #initialize(AlgorithmParameterSpec, SecureRandom)}
116 * will not be invoked.
117 */
118 private SecureRandom random = new SecureRandom();
119
120 /** Creates new RSAKeyPairGeneratorImpl*/
121 RSAKeyPairGeneratorImpl() {}
122
123 /**
124 * Returns a string representation of the object.
125 *
126 * @return a string representation of the object.
127 */
128 public String toString() {
129 StringBuffer sb = new StringBuffer();
130 sb.append("[Keysize: ");
131 sb.append(this.keysize);
132 sb.append(", Public-Exponent: ");
133 sb.append(this.e);
134 sb.append(", Certainty: ");
135 sb.append(this.certainty);
136 sb.append(']');
137 return sb.toString();
138 }
139
140 /**
141 * Initializes the key pair generator for a certain keysize, using
142 * the default parameter set. If random is <code>null</code> we use
143 * the <code>SecureRandom</code> implementation of the
144 * highest-priority installed provider as the source of randomness.
145 * (If none of the installed providers supply an implementation of
146 * <code>SecureRandom</code>, a system-provided source of randomness
147 * is used.)
148 * <p><b>Note:</b> If there a reinitialization with a <code>null</code>
149 * reference for <code>random</code> we use the existing random object,
150 * that was valid before reinitialization.
151 *
152 * @param keysize the keysize. The keysize must be a positive multiple of
153 * 256 and equals or greater than 768.
154 * @param random the source of randomness for this generator. If random is
155 * <code>null</code> we use the the <code>SecureRandom</code> implementation
156 * of the highest-priority installed provider as the source of randomness.
157 * (If none of the installed providers supply an implementation of
158 * <code>SecureRandom</code>, a system-provided source of randomness
159 * is used.)
160 * @throws InvalidParameterException if the <code>keysize</code> is not
161 * equals or geater than 768 and a multible of 256. Where the unit is bit.
162 */
163 void initialize(int keysize, SecureRandom random) {
164 if ((keysize >= 768) && ((keysize % 256) == 0)) {
165 this.keysize = keysize;
166 } else {
167 throw new InvalidParameterException("Parameter keysize must be a " +
168 "positive multiple of 256 and equals or greater than 768.");
169 }
170 if (random != null) {
171 this.random = random;
172 }
173 }
174
175 /**
176 * Initializes the key pair generator using the specified parameter
177 * set and user-provided source of randomness.
178 *
179 * You have to use {@link java.security.spec.RSAKeyGenParameterSpec} as
180 * <code>AlgorithmParamterSpec</code>. <code>RSAKeyGenParameterSpec</code>
181 * does support <code>int keysize</code> and
182 * <code>BigInteger publicExponent</code>. The <code>keysize</code> must be
183 * 768 or greater and a multible of 256.
184 *
185 * <p>So that <code>keysize</code> satisfies the equation:
186 * <ul>
187 * <li><code>keysize = x * 256, where x = 3, 4, 5, 6, ...</code></li>
188 * </ul>
189 * The possible values for <code>publicExponent</code> are:
190 * <ul>
191 * <li><code>publicExponent = </code>
192 * {@link java.security.spec.RSAKeyGenParameterSpec#F0} = 3</li>
193 * <li><code>publicExponent = </code>
194 * {@link java.security.spec.RSAKeyGenParameterSpec#F4} = 65537</li>
195 * </ul>
196 *
197 * <p><b>Note:</b> If there a reinitialization with a <code>null</code>
198 * reference for <code>random</code> we use the existing random object,
199 * that was valid before reinitialization.
200 *
201 * @param params the parameter set used to generate the keys.
202 * @param random the source of randomness for this generator.
203 * @throws InvalidAlgorithmParameterException if the <code>keysize</code>
204 * is not equals or geater than 768 and a multible of 256. Where the unit
205 * is bit. Or if the <code>publicExponent</code> isn't F0 or F4.
206 * @see java.security.spec.RSAKeyGenParameterSpec
207 */
208 void initialize(AlgorithmParameterSpec params, SecureRandom random)
209 throws InvalidAlgorithmParameterException {
210 //Check for type.
211 RSAKeyGenParameterSpec RSAParams = null;
212 if (params instanceof RSAKeyGenParameterSpec) {
213 RSAParams = (RSAKeyGenParameterSpec) params;
214 } else {
215 throw new InvalidAlgorithmParameterException("Inappropriate " +
216 "AlgorithmParameterSpec, RSAKeyGenParameterSpec expected.");
217 }
218
219 //Check keysize.
220 int keysize = RSAParams.getKeysize();
221 if ((keysize < 768) || ((keysize % 256) != 0)) {
222 throw new InvalidAlgorithmParameterException("Parameter keysize " +
223 "must be a positive multiple of 256 and equals or greater" +
224 "than 768.");
225 }
226
227 //Check publicExponent e.
228 BigInteger e = RSAParams.getPublicExponent();
229 if (e != null) {
230 if (e.getClass() != BigInteger.class) {
231 e = new BigInteger(e.toByteArray());
232 }
233 if ((e.equals(F0) == false) &&
234 (e.equals(F4) == false) ){
235 throw new InvalidAlgorithmParameterException("Parameter " +
236 "publicExponent must be " + F0 + " or " + F4 + ".");
237 }
238
239 }
240
241 //We are right with all invariants!
242
243 //Set keysize
244 this.keysize = RSAParams.getKeysize();
245 //If publicExponent isn't null we set the value.
246 if (e != null) {
247 this.e = e;
248 }
249 }
250
251 /**
252 * Generates random strong primes.
253 *
254 * <p>This method is a private helper method of <code>generateKeyPair()</code>
255 * to generate random strong primes with a given <code>bitLength</code>.
256 *
257 * @param bitLength The bit length that the returned strong prime should
258 * have.
259 * @return the strong prime with the given <code>bitLength</code>.
260 */
261 private BigInteger generateStrongPrime(int bitLength) {
262 /*
263 * We use the following member in this method:
264 *
265 * 1. <code>random</code> the PRNG
266 * 2. <code>certainty</code> the default for the certainty.
267 *
268 * Note: We use no expliziet this reference in this method.
269 * That makes the code clear and readable.
270 *
271 * The method is a private helper method of
272 * <code>generateKeyPair()</code> to generate random strong primes
273 * with a given <code>bitLength</code>.
274 *
275 * This method uses DEBUG and INFO log4j statements.
276 * DEBUG means a lot of messages.
277 * INFO means less highlevel infos.
278 * Use log4j.properties file to enable logging.
279 *
280 * This method should never hang up. It should always be finite.
281 */
282
283 if (log.isLoggable(Level.FINER)) {
284 log.finer("Enter generateStrongPrime(<bitLength="+bitLength+">).");
285 log.finer("Will use member <random=" + random + ">.");
286 log.finer("Will use member <certainty=" + certainty + ">.");
287 }
288
289 //////
290 // If bit lenght to small, we throw an Exception, this is important for
291 // the bit length of r, s, t and i0 and j0. This should be at least 256.
292 //////
293 if (bitLength < 256) {
294
295 IllegalArgumentException e = new IllegalArgumentException(
296 "You should only generate " +
297 "strong primes with order >= 256 bit. " +
298 "Lesser Primes are insecure.");
299
300 if (log.isLoggable(Level.FINER)) {
301 log.finer("Leave generateStrongPrime(<bitLength="+bitLength+">)" +
302 " through Exception. Exception: " + e);
303 }
304
305 throw e;
306 }
307
308 ////////////////////////////////////////////////////////////////////////
309 //
310 // Gordon's Algorithm for generating strong primes.
311 //
312 // see:
313 //
314 // Strong Primes Are Easy to Find
315 // John A. Gordon
316 // Lecture Notes in Computer Science 0209, p. 216 ff.
317 // http://link.springer.de/link/service/series/0558/bibs/0209/02090216.htm
318 //
319 //
320 // The algorithm is also described in:
321 //
322 // Handbook of Applied Cryptography by A. Menezes, P. van Oorschot,
323 // and S. Vanstone, CRC Press, 1996, chapter 4, page 150.
324 // http://www.cacr.math.uwaterloo.ca/hac/
325 //
326 // We use the steps described in hac for algorithm 4.53. For finer
327 // granularity, we split the steps in sub steps such as 1.1, 1.2, ...
328 // Also we use the notation used in hac as follows:
329 //
330 // p-1 has a large prime factor, denoted r.
331 // p+1 has a large prime factor, denoted s.
332 // r-1 has a large prime factor, denoted t.
333 //
334 // Ronald R. Rivest and Robert D. Silverman use in:
335 //
336 // Are 'Strong' Primes Needed for RSA?
337 // you can find it at ftp://ftp.rsasecurity.com/pub/pdfs/sp2.pdf
338 //
339 // the following notation:
340 //
341 // p-1 has a large prime factor, denoted p^-.
342 // p+1 has a large prime factor, denoted p^+.
343 // (p^-)-1 has a large prime factor, denoted p^--.
344 //
345 // These paper contains a very usefull description for the english words
346 // "large prime factor" and how can you interpret large.
347 //
348 ////////////////////////////////////////////////////////////////////////
349
350 ////////////////////////////////////////////////////////////////////////
351 //
352 // Step 1 from Gordon's algorithm
353 //
354 ////////////////////////////////////////////////////////////////////////
355
356
357 //////
358 // 1.1 Setup the target value for i0.
359 // This is the start value where search for prime r with respect in t
360 // will start.
361 // For details see ftp://ftp.rsasecurity.com/pub/pdfs/sp2.pdf
362 //////
363 int i0BitLengthTargetValue = 12;
364 if (log.isLoggable(Level.FINEST)){
365 log.finest("Have set <i0BitLengthTargetValue="+i0BitLengthTargetValue+">.");
366 }
367
368 //////
369 // 1.2 Setup the target value for j0
370 // This is the start value where search for prime p with respect
371 // in p0, r, s will start.
372 // For details see ftp://ftp.rsasecurity.com/pub/pdfs/sp2.pdf
373 //////
374 int j0BitLengthTargetValue = 12;
375 if (log.isLoggable(Level.FINEST)) {
376 log.finest("Have set <j0BitLengthTargetValue="+j0BitLengthTargetValue+">.");
377 }
378
379 //////
380 // 1.3 Setup the bit length for t -- in depence on
381 // ftp://ftp.rsasecurity.com/pub/pdfs/sp2.pdf
382 // t.bitLength() should be >= 130
383 //////
384 int tBitLength = bitLength/2 - i0BitLengthTargetValue;
385 if (log.isLoggable(Level.FINEST)) {
386 log.finest("Have calculated <tBitLength="+tBitLength+"> = <bitLength="+bitLength+
387 ">/2 - <i0BitLengthTargetValue="+i0BitLengthTargetValue+">.");
388 }
389
390 //////
391 // 1.4 Generate new BigInteger t -- the large prime factor t
392 // of the large primefactor r of p-1. Rivest denotes t in his
393 // paper ftp://ftp.rsasecurity.com/pub/pdfs/sp2.pdf as p^-- and
394 // r as p^- .
395 //////
396 BigInteger t = new BigInteger(tBitLength, certainty, random);
397 if (log.isLoggable(Level.FINER)) {
398 log.finer("Have generated large prime factor <t> with bit length <t.bitLength()="+
399 t.bitLength()+">, <t="+t+">.");
400 }
401
402 ////////////////////////////////////////////////////////////////////////
403 //
404 // Step 2 from Gordon's algorithm
405 //
406 ////////////////////////////////////////////////////////////////////////
407
408 //////
409 // 2.1 Setup the bit length for i0. i0BitLength should be equal or very
410 // close to i0BitLengthTargetValue.
411 //////
412 int i0BitLength = bitLength/2 - t.bitLength();
413 if (log.isLoggable(Level.FINEST)) {
414 log.finest("Have calculated <i0BitLength="+i0BitLength+"> = <bitLength="+bitLength+
415 ">/2 - <t.bitLength()="+t.bitLength()+">.");
416 }
417
418 //////
419 // 2.2 Setup i0 as a "i0BitLength" bit value. Say the rightmost bit will
420 // be denoted as bit 1, the left neighbor of bit 1 as bit 2 and so on...
421 // Then all bits will be 0 and the i0bitLength bit will be 1. So
422 // we have aBigInteger that will be "i0BitLength" bits long.
423 //////
424 BigInteger i0 = new BigInteger("0").setBit(i0BitLength-1);
425 if (log.isLoggable(Level.FINEST)) {
426 log.finest("Have set <i0> with <i0.bitLength()="+i0.bitLength()+
427 ">, <i0=" + i0 + ">.");
428 }
429
430 //////
431 // 2.3 References that are used for provisional results.
432 //////
433 BigInteger a;
434 BigInteger b;
435 BigInteger c;
436 BigInteger d;
437
438 //////
439 // 2.4 a is the intermediate result for (t * 2). Now we can use a in the
440 // loop. Instead we are calculating 2 * i * t + 1, we use a * i + 1.
441 //////
442 a = t.multiply(TWO); // a = t * 2
443
444 //////
445 // 2.5 Declare reference that will be used to hold the result for r.
446 //////
447 BigInteger r;
448
449 //////
450 // 2.6 Setup i with the start value i0.
451 //////
452 BigInteger i = i0;
453 if (log.isLoggable(Level.FINEST)) {
454 log.finest("Have set <i="+i+"> with <i0> as start value for loop 1.");
455 }
456
457 //////
458 // 2.7 Loop 1
459 // Find r in the sequence 2 * i * t + 1, for i = i0, i0+1, i0+2, ...
460 // r = 2 * i * t + 1
461 //////
462 do{
463 b = a.multiply(i); // b = a * i --> b = 2 * i * t
464 r = b.add(ONE); // r = b + 1 --> r = 2 * i * t + 1
465 i = i.add(ONE); // increment i --> i = i + 1
466 if (log.isLoggable(Level.FINEST)) {
467 log.finest("Try to find <r> in <2 * "+i+" * t + 1> in loop 1, with bit length <r.bitLength()="+
468 r.bitLength()+">, where <r="+r+">.");
469 }
470 } while(r.isProbablePrime(certainty) == false); // if r is prime we leave the loop
471
472 if (log.isLoggable(Level.FINER)) {
473 log.finer("Have found <r> as probable prime in <2 * "+i+" * t + 1> in " +
474 "loop 1, with bit length <r.bitLength()="+r.bitLength()+
475 ">, where <r="+r+">.");
476 }
477
478 ////////////////////////////////////////////////////////////////////////
479 //
480 // Step 3 from Gordon's algorithm
481 //
482 ////////////////////////////////////////////////////////////////////////
483
484 //////
485 // 3.1 Declare reference that will be used to hold the result for p.
486 //////
487 BigInteger p =null;
488
489 //////
490 // 3.2 Loop 2
491 // We loop this outerloop until we have found a matching p
492 // depend on random s with respect to random t. For further details see
493 // step 4.8.
494 //////
495 outerloop:
496 do{
497 //////
498 // 3.3 Setup the bit length for s -- in depence on
499 // ftp://ftp.rsasecurity.com/pub/pdfs/sp2.pdf
500 // s.bitLength() should be >= 130
501 //////
502 int sBitLength = bitLength - r.bitLength() - j0BitLengthTargetValue;
503 if (log.isLoggable(Level.FINEST)) {
504 log.finest("Have set <sBitLength=bitLength-r.bitLength()-j0BitLengthTargetValue>, "+
505 "where <sBitLength="+sBitLength+">.");
506 }
507
508 //////
509 // 3.4 Generate new BigInteger s -- the large prime factor s of p+1.
510 // Rivest denotes s in his paper
511 // ftp://ftp.rsasecurity.com/pub/pdfs/sp2.pdf as p^+ .
512 //////
513 BigInteger s = new BigInteger(sBitLength, certainty, random);
514 if (log.isLoggable(Level.FINER)) {
515 log.finer("Have generated large prime factor <s> with bit length <s.bitLength()="+
516 s.bitLength()+">, <s="+s+">.");
517 }
518
519 //////
520 // 3.5 Declare reference that will be used to hold the result for p0.
521 //////
522 BigInteger p0;
523
524 //////
525 // 3.6 Compute p0 = 2 * (s^(r-2) mod r) * s - 1
526 //////
527 a = s.multiply(TWO); // a = s * 2
528 b = r.subtract(TWO); // b = r - 2
529 c = s.modPow(b, r); // c = s^b mod r --> s^(r-2) mod r
530 d = c.multiply(a); // d = c * a --> 2 * (s^(r-2) mod r) * s
531 p0 = d.subtract(ONE); // p0 = d - 1 --> 2 * (s^(r-2) mod r) * s - 1
532 if (log.isLoggable(Level.FINEST)) {
533 log.finest("Have calculated <p0=(s^(r-2) mod r) * s - 1>, with bit length <p0.bitLength()="+
534 p0.bitLength()+">, where <p0="+p0+">.");
535 }
536
537
538 ////////////////////////////////////////////////////////////////////////
539 //
540 // Step 4 from Gordon's algorithm
541 //
542 ////////////////////////////////////////////////////////////////////////
543
544 //////
545 // 4.1 b is the intermediate result for (2 * r * s). Now we can use "a"
546 // in loop 3. Instead we are calculating p0 + 2 * j * r * s,
547 // we use p0 + a * j
548 //////
549 a = TWO.multiply(r).multiply(s); // a = 2 * r * s
550
551 //////
552 // 4.2 What we are doing here? We calculate an optimal value for j0,
553 // so that we can start searching p
554 // at 2^(bitLength-1) to (2^bitLength)-1. This means we search the
555 // whole range for the target value p. For a example say the target
556 // bit length for p should be 6. We set the bit six count from right
557 // to left, starting at 1 to 1 like this -> 100000 we reconvert the
558 // formula:
559 //
560 // p = p0 + 2*j*r*s
561 //
562 // to
563 //
564 // j = (p-p0) / (2*r*s)
565 //
566 // now we set p = 2^(bitLength-1) and calculate j with our special p,
567 // and the already calculated values p0, r, s. Now we add 1 to j to
568 // compensate the integer division. So that j will be:
569 //
570 // j = (2^(bitLength-1) - p0) / (2*r*s) + 1
571 //
572 // So now we can start searching p starting with a usefull value,
573 // means 2^(bitLength-1). This algorithm was my idea!!! ;-)
574 //////
575 b = BigInteger.valueOf(0L).setBit(bitLength-1).subtract(p0); // b = 2^(bitLength-1) - p0
576 c = TWO.multiply(r).multiply(s); // c = 2*r*s
577 BigInteger j0 = b.divide(c); // j0 = b/c --> p - p0 / 2*r*s
578
579 //////
580 // 4.4 Test if (2^(bitLength-1)-p0) isn't a multiple of (2*r*s).
581 // If it is, do nothing.
582 // If it isn't add one to j0, so that j0 will be the first usefull
583 // value to calculate a p that will be bitLength bits long.
584 //////
585 if(b.mod(c).equals(ZERO) == false) {
586
587 j0 = j0.add(BigInteger.ONE); // (p-p0 / 2*r*s) + 1 --> j0++
588 if (log.isLoggable(Level.FINEST)) {
589 log.finest("Have incremented <j0>, " +
590 "because <BigInteger.valueOf(0L).setBit(bitLength-1).subtract(p0)> " +
591 "was not a multiple of <TWO.multiply(r).multiply(s)>, " +
592 "where <bitLength="+bitLength+">.");
593 }
594 }
595 if (log.isLoggable(Level.FINEST)) {
596 log.finest("Have calculated the the first useful value for "+
597 "<j0.bitLength()="+j0.bitLength()+">, <j0="+j0+">.");
598 }
599
600 //////
601 // 4.6 Setup j with the start value j0.
602 //////
603 BigInteger j = j0;
604 if (log.isLoggable(Level.FINEST)) {
605 log.finest("Have set <j="+j+"> with <j0> as start value for loop 3.");
606 }
607
608 //////
609 // 4.7 Loop 3
610 // The innerloop serches for valid p in the range between
611 // 2^(bitLength-1) to (2^bitLength)-1. If we walk behind the upper
612 // boarder (2^bitLength)-1, we will break the innerloop and
613 // continues with the outerloop.
614 //////
615 innerloop:
616 do{
617 p = a.multiply(j).add(p0); // p = a * j + p0 --> p = p0 + 2 * j * r * s
618 if (log.isLoggable(Level.FINEST)) {
619 log.finest("Try to find <p> in <p0 + 2 * "+j+" * r * s> in loop 3, "+
620 "with bit length <p.bitLength()="+p.bitLength()+">, "+
621 "where <p="+p+">.");
622 }
623
624 j = j.add(BigInteger.ONE); // increment j --> j = j + 1
625
626 //////
627 // 4.8. If we walk through the whole range between 2^(bitLength-1)
628 // to (2^bitLength)-1. We are going to create new random s, than
629 // calc a new p0 from the new random s, and try it again to find
630 // a p that matches to the first generated random t. We do this
631 // until we find a valid bit in the range between 2^(bitLength-1)
632 // to (2^bitLength)-1, in the hope there will be a p at any
633 // time. ;-). If there never a valid p will come we run in to a
634 // infinite loop. :( , but this should not happend.
635 //////
636 if (p.bitLength() > bitLength) {
637 if (log.isLoggable(Level.FINEST)) {
638 log.finest("Bit length <p.bitLength()="+p.bitLength()+"> > <bitLength="+
639 bitLength+">, therefore we continue with loop 2.");
640 }
641 continue outerloop;
642 }
643
644 //////
645 // Break condition for our innerloop.
646 //////
647 } while (p.isProbablePrime(certainty) == false);
648
649 if (log.isLoggable(Level.FINER)) {
650 log.finer("Have found <p> as probable strong prime <p0 + 2 * "+j+
651 " * r * s> in loop 3, with bit length <p.bitLength()="+
652 p.bitLength()+">, where <p="+p+">.");
653 }
654
655 //////
656 // Break condition for our outer loop.
657 //////
658 } while(p.bitLength() != bitLength);
659
660 if (log.isLoggable(Level.FINEST)) {
661 log.finest("Have left loop 2, because <p.bitLength()="+p.bitLength()+
662 "> == <bitLength="+bitLength+">");
663 }
664
665 if (log.isLoggable(Level.FINER)) {
666 log.finer("Return from generateStrongPrime(<bitLength=.....>) " +
667 "with bit length <p.bitLength()="+p.bitLength()+">, <p=" +
668 p + ">.");
669 }
670 //////
671 // At this point p has a valid bit length.
672 //////
673 return p;
674 }
675
676
677 /**
678 * Generates a <code>KeyPair</code>. Unless an initialization method is
679 * called using a KeyPairGenerator interface, algorithm-specific defaults
680 * will be used. This will generate a new key pair every time it
681 * is called. The defaults are <code>keysize</code> = 768 bit and
682 * random with the <code>SecureRandom</code> implementation of the
683 * highest-priority installed provider as the source of randomness.
684 * (If none of the installed providers supply an implementation of
685 * <code>SecureRandom</code>, a system-provided source of randomness
686 * is used.)
687 *
688 * @return the newly generated <code>KeyPair</code>
689 */
690 KeyPair generateKeyPair() {
691 /*
692 * We use the following members in this method:
693 *
694 * 1. <code>random</code> the PRNG
695 * 2. <code>keysize</code> the modulus size in bit
696 * 3. <code>e</code> the public exponent
697 *
698 * Note: We use no expliziet this reference in this method.
699 * That makes the code clear and readable.
700 *
701 * The method uses the private helper method
702 * <code>generateStrongPrime(int bitLength)</code>
703 * to generate random strong primes with a given
704 * <code>bitLength</code>.
705 *
706 * This method uses DEBUG and INFO log4j statements.
707 * DEBUG means a lot of messages.
708 * INFO means less highlevel infos.
709 * Use log4j.properties file to enable logging.
710 *
711 * This method should never hang up. It should always be finite.
712 */
713
714 if (log.isLoggable(Level.FINER)) {
715 log.finer("Enter generateKeyPair().");
716 log.finer("Will use member <random=" + random + ">.");
717 log.finer("Will use member <keysize=" + keysize + ">.");
718 log.finer("Will use member <e=" + e + ">.");
719 }
720
721 //////
722 // Declare reference p, q and n, both are used in the following
723 // outerloop, middleloop and innerloop, and after that loop.
724 //////
725 BigInteger p;
726 BigInteger q;
727 BigInteger n;
728
729 //////
730 // This is the initial value in bits for that can the bit length for p
731 // and q differently. HBCI 2.2 says length of p and q should be at most
732 // 12 bits. This value should always greater than 0(zero).
733 //////
734 int maxBitLengthDifference = 12;
735
736 //////
737 // Initialize the bitLengthDifference with it's start value
738 // maxBitLengthDifference.
739 //////
740 int bitLengthDifference = maxBitLengthDifference;
741
742 //////
743 // Loop 1:
744 // Loop until the bitLengthDifference between p length and q length are
745 // less than or equal to maxBitLengthDifference.
746 //////
747 outerloop:
748 do{
749 if (log.isLoggable(Level.FINEST)) {
750 log.finest("Enter loop 1.");
751 }
752
753 //////
754 // Checks if bitLengthDifference lesser than 1, if it is, we adjust
755 // it to maxBitLengthDifference. bitLengthDifference will be
756 // decremented at the end of these loop if the difference between
757 // p length and q length is more than maxBitLengthDifference.
758 //////
759 if (bitLengthDifference < 1) {
760
761 if (log.isLoggable(Level.FINEST)) {
762 log.finest("Adjust <bitLengthDifference=" +
763 bitLengthDifference + "> to " +
764 "<maxBitLengthDifference=" +
765 maxBitLengthDifference + ">."
766 );
767 }
768 bitLengthDifference = maxBitLengthDifference;
769 }
770
771 //////
772 // Now we generate a random value for the bit length difference between
773 // p and q. This statement creates values in the range between 0 an
774 // bitLengthDifference inclusively. For example value 12 , this means
775 // the range between 0 - 12 inclusively.
776 //////
777 int distribution = random.nextInt(bitLengthDifference+1);
778 if (log.isLoggable(Level.FINEST)) {
779 log.finest("Have generated random value <distribution=" + distribution + ">.");
780 }
781
782 //////
783 // Calculate the target bit length for p.
784 //////
785 int pBitLength = (keysize + distribution) / 2;
786 if (log.isLoggable(Level.FINEST)) {
787 log.finest("Have calculated the target bit length for <p> as <pBitLength=" +
788 pBitLength + ">.");
789 }
790
791 //////
792 // Calculate the target bit length for q.
793 //////
794 int qBitLength = keysize - pBitLength + 1;
795 if (log.isLoggable(Level.FINEST)) {
796 log.finest("Have calculated the target bit length for <q> as " +
797 "<qBitLength="+qBitLength+">.");
798 }
799
800 //////
801 // Loop 2
802 // Loop until p-1 is relatively prime to e.
803 //
804 // Reason:
805 // =======
806 // phi(n) = (p-1) * (q-1);
807 // Special case of the Euler formula, that calculates the count of
808 // numbers that are relatively prime to n in the Ring Zn.
809 //
810 // (e * d) mod phi(n) = 1;
811 // That means e*d is relatively prime to phi(n). Only a number that
812 // is relatively prime to phi(n) has a multipliacative inverse
813 // number d. So taht follows we need a number that is relatively
814 // prime to phi(n).
815 //
816 // If e satifies the equations "gcd(e, p-1) == 1" and "gcd(e, q-1) == 1"
817 // it will also satisfy the equatation "gcd(e, phi(n))" because
818 // every number is unique composition of prime numbers. If e is
819 // relatively prime to p-1, the set of primes of the two numbers are
820 // different, and if e also relatively prime to q-1 the set of the
821 // primes of the these two numbers are different. If you now
822 // multiply p-1 and q-1 you put it prime sets together and e will
823 // also relatively prime to (p-1)*(q-1) and also to phi(n), which is
824 // the same as (p-1) * (q-1), if p and q are primes.
825 //
826 // See some lines of code below there will be a check for
827 // gcd(e, q-1), if we generate q.
828 //
829 // Genreal Problem:
830 // ================
831 // The RSAKeyGenAlgo says:
832 // 1. Genrate p and q as primes, multiply them to n.
833 // 2. Find a public exponent e that is relatively prime to phi(n).
834 // 3. Find the multiplicative inverse number to e with the extended
835 // euclidian algorithm.. This number will be the private
836 // exponent d.
837 //
838 // How works our RSAKeyGenAlgo:
839 // 1. We have a preconfigured default e, where e will be F0 or F4.
840 // 2. we have to find p and q so that (p-1) * (q-1) will be
841 // relatively prime to e or reverse. Also p and q must be
842 // "strong primes".
843 // 3. Find the multiplicative inverse number to e with the extended
844 // euclidian algorithm.. This number will be the private
845 // exponent d.
846 //////
847 do{
848 if (log.isLoggable(Level.FINEST)) {
849 log.finest("Enter loop 2.");
850 }
851
852 //////
853 // Generate a random strong prime p with pBitLength.
854 //////
855 p = generateStrongPrime(pBitLength);
856 if (log.isLoggable(Level.FINEST)) {
857 log.finest("Have generated a random strong prime <p> with bit length "+
858 "<p.bitLength()=" + p.bitLength() + ">, <p=" + p + ">.");
859 }
860
861 //////
862 // Loop until p-1 is relatively prime to e.
863 //////
864 } while (e.gcd(p.subtract(ONE)).equals(ONE) == false);
865 if (log.isLoggable(Level.FINER)) {
866 log.finer("Value <p-1> is relatively prime to <e>, this means <p> is valid," +
867 "so we left loop 2.");
868 }
869
870 //////
871 // At these point we calc the the first usefull value for q, that will
872 // produce the smallest value for p for a given keysize. The algo works
873 // as follows:
874 //
875 // 1. Create a new instance of BigInteger with the value 0 (zero).
876 // Set bit at position "keysize" to 1 and all other bits to
877 // zero, where the rightmost bit is denoted as bit 1 and is
878 // the least significant bit at the same time, such as:
879 //
880 // qLowerBound = 2^(keysize-1)
881 //
882 //
883 // 2. Divide the BigInteger from step one with p, such as:
884 //
885 // qLowerBound = qLowerBound / p
886 //
887 //
888 // 3. If the BigInteger, created in step one, is not a multiple of
889 // p, add one to the value calculated in step two, such as:
890 //
891 // qLowerBound = qLowerBound + 1
892 //
893 //
894 // We do this to balance the remainder, if there any, that is
895 // unnoted to the preceded inteder division.
896 //
897 // Now qLowerBound is the smallest usefull value for q.
898 //////
899 BigInteger qLowerBound = ZERO.setBit(keysize-1).divide(p);
900
901 if(ZERO.setBit(keysize-1).mod(p).equals(ZERO) == false) {
902
903 qLowerBound = qLowerBound.add(ONE);
904 if (log.isLoggable(Level.FINEST)) {
905 log.finest("Have incremented <qLowerBound>, " +
906 "because qLowerBound isn't a multiple of " +
907 "<BigInteger.valueOf(0).setBit(keysize-1)>, " +
908 "where <keysize=" + keysize + ">.");
909 }
910
911 }
912 if (log.isLoggable(Level.FINEST)) {
913 log.finest("Have calculated the the first usefull value for <q>, " +
914 "<qLowerBound.bitLength()=" + qLowerBound.bitLength() + ">.");
915 }
916
917 //////
918 // At these point we calc the the last usefull value for q, that will
919 // produce the largest value for p for a given keysize. The algo works
920 // as follows:
921 //
922 // 1. Create a new instance of BigInteger with the value 0 (zero).
923 // Set bit at position "keysize+1" to 1 and all other bits to
924 // zero, where the rightmost bit is denoted as bit 1 and is
925 // the least significant bit at the same time, such as:
926 //
927 // qUpperBound = (2^keysize)
928 //
929 //
930 // 2. Subtract the BigInteger from step one with one, such as:
931 //
932 // qUpperBound = qUpperBound - 1
933 //
934 //
935 // 3. Divide the BigInteger from step two with p, such as:
936 //
937 // qUpperBound = qUpperBound / p
938 //
939 //
940 // Now qUpperBound is the largest usefull value for q.
941 //////
942 BigInteger qUpperBound = ZERO.setBit(keysize).subtract(ONE).divide(p);
943 if (log.isLoggable(Level.FINEST)) {
944 log.finest("Have calculated the the last usefull value for <q>, " +
945 "<qUpperBound.bitLength()="+qUpperBound.bitLength()+">.");
946 }
947
948 //////
949 // Loop 3
950 // Loop until n is "keysize" bits long.
951 //////
952 middleloop:
953 do{
954
955 if (log.isLoggable(Level.FINEST)) {
956 log.finest("Enter loop 3.");
957 }
958
959 //////
960 // Setup the initial bitLength for q. We use once more, because the
961 // probability to find a right value in this range is very high. If
962 // we don't find a strong prime q in the range of
963 // qLowerBound.bitLength() + 1 and qUpperBound.bitLength(), we
964 // adjust the bit length of q to qLowerBound.bitLength() in the
965 // innerloop.
966 // So this statement is not harmfull, it's only for performance.
967 //////
968 qBitLength = qLowerBound.bitLength() + 1;
969
970 //////
971 // Loop 4
972 // Loop until q is in the right range between qLowerBound and
973 // qUpperBound, so that n=p*q will be "keysize" bits long, and q-1
974 // is relatively prime to e, and q isn't equal to p, and the max
975 // bit length differenc between p and q will be at most
976 // "bitLengthDifference".
977 //////
978 innerloop:
979 while(true) {
980
981 if (log.isLoggable(Level.FINEST)) {
982 log.finest("Enter loop 4.");
983 }
984
985 //////
986 // If qBitLength out of the upper range, we will adjust it
987 // to the bit length of qLowerBound. This can be happen if we
988 // increment qBitLength so often at the end of this loop with
989 // qBitLength++ while we didn't found a q that matches to our
990 // conditions.
991 //////
992 if (qBitLength > qUpperBound.bitLength()) {
993 qBitLength = qLowerBound.bitLength();
994 }
995
996 //////
997 // Generate a random strong prime q with qBitLength.
998 //////
999 q = generateStrongPrime(qBitLength);
1000 if (log.isLoggable(Level.FINEST)) {
1001 log.finest("Have generated a random strong prime with bit " +
1002 "length <q.bitLength()="+q.bitLength()+">, <q=" +
1003 q + ">.");
1004 }
1005
1006 //////
1007 // Check if q is in the right range between qLowerBound and
1008 // qUpperBound inclusively, so that n=p*q will be "keysize"
1009 // bits long, as follows:
1010 //
1011 // qLowerBound =< q =< qUpperBound
1012 //
1013 //////
1014 if((q.compareTo(qLowerBound) >= 0) && // q >= qLowerBound
1015 (q.compareTo(qUpperBound) <= 0) ) // q <= qUpperBound
1016 {
1017 if (log.isLoggable(Level.FINEST)) {
1018 log.finest("Value <q> is in the range between <qLowerBound> " +
1019 "and <qUpperBound> inclusively.");
1020 }
1021
1022 //////
1023 // Check if q-1 is relatively prime to e, and q isn't equal
1024 // to p, and the max bit length difference between p and q
1025 // will be at most "bitLengthDifference".
1026 //////
1027 if (e.gcd(q.subtract(ONE)).equals(ONE)
1028 && p.equals(q) == false) {
1029 if (log.isLoggable(Level.FINER)) {
1030 log.finer("Value <q-1> is relatively prime to <e>, " +
1031 "this means <q> is valid, so we break loop 4.");
1032 }
1033
1034 //////
1035 // At this point we got a q that is in the right range,
1036 // between qLowerBound and qUpperBound and is relatively
1037 // prime to e.
1038 //////
1039 break innerloop;
1040 }
1041
1042 if (log.isLoggable(Level.FINEST)) {
1043 log.finest("Value <q-1> isn't relatively prime to <e>, " +
1044 "so we continue loop 4.");
1045 }
1046
1047 //////
1048 // If q isn't relatively prime to e, but it matches to our
1049 // range between qLowerBound and qUpperBound, we don't change
1050 // qBitLength and continues immediately with innerloop
1051 // to generate a new strong prime for q with the same
1052 // bit length (qBitLength) as this one.
1053 //////
1054 continue innerloop;
1055 }
1056
1057 //////
1058 // If q isn't in the right range between qLowerBound and
1059 // qUpperBound, so that n=p*q will be "keysize" bits long,
1060 // we increment it. Further if we run out of range, we will
1061 // adjust it at the next reentry to the innerloop to bit length
1062 // of qLowerBound. See above.
1063 //////
1064 qBitLength++;
1065 if (log.isLoggable(Level.FINEST)) {
1066 log.finest("Have incremented <qBitLength=" + (qBitLength-1) +
1067 "> to " + "<qBitLength=" + qBitLength + ">.");
1068 }
1069 }
1070
1071 //////
1072 // Calculate the modulus n = p * q.
1073 //////
1074 n = p.multiply(q);
1075 if (log.isLoggable(Level.FINEST)) {
1076 log.finest("Have calculated modulus with bit length <n.bitLength()=" +
1077 n.bitLength() + ">, <n=" + n + ">.");
1078 }
1079
1080 //////
1081 // This condition is a little bit redundant, because n has to "keysize"
1082 // bits long. But we use it for security if any q range calculation
1083 // fails, now we are sure that n has the right keysize.
1084 //////
1085 } while (n.bitLength() != keysize);
1086 if (log.isLoggable(Level.FINEST)) {
1087 log.finest("Bit length <n.bitLength()=" + n.bitLength() + "> == " +
1088 "<keysize=" + keysize + ">, so we left loop 3.");
1089 }
1090
1091 //////
1092 // If the bitLengthDifference between p length and q length
1093 // more than maxBitLengthDifference, decrement to bitLengthDifference.
1094 // There is a condition at the beginning of the outerloop that checks
1095 // if bitLengthDifference lesser than 1, if it is, we adjust it at
1096 // the beginning of the loop to maxBitLengthDifference.
1097 //////
1098 if (Math.abs(p.bitLength() - q.bitLength()) > maxBitLengthDifference) {
1099
1100 bitLengthDifference--;
1101
1102 if (log.isLoggable(Level.FINEST)) {
1103 log.finest("Have adjusted <bitLengthDifference=" + (bitLengthDifference+1) +
1104 "> to <bitLengthDifference=" + bitLengthDifference + ">.");
1105 }
1106 }
1107
1108 if (log.isLoggable(Level.FINEST)) {
1109 log.finest("Final bit length difference between <p> and <q> is " +
1110 "<abs(p.bitLength()-q.bitLength())=" +
1111 Math.abs( p.bitLength() - q.bitLength() ) + ">.");
1112 }
1113
1114 //////
1115 // Loop until the bitLengthDifference between p length and q length are
1116 // less than or equal to maxBitLengthDifference.
1117 //////
1118 } while (Math.abs(p.bitLength() - q.bitLength()) > maxBitLengthDifference);
1119
1120 if (log.isLoggable(Level.FINER)) {
1121 log.finer("Final bit length difference between <p> and <q> is " +
1122 "<abs(p.bitLength()-q.bitLength())=" +
1123 Math.abs(p.bitLength() - q.bitLength()) + ">" +
1124 " <= <maxBitLengthDifference=" + maxBitLengthDifference +
1125 ">, so we left loop 1.");
1126 }
1127
1128 //////
1129 // Calculate p-1 and q-1, phi and the private exponent d.
1130 //////
1131 BigInteger pSub1 = p.subtract(ONE);
1132 BigInteger qSub1 = q.subtract(ONE);
1133 BigInteger phi = pSub1.multiply(qSub1);
1134 BigInteger d = e.modInverse(phi);
1135
1136 if (log.isLoggable(Level.FINER)) {
1137 log.finer("n: " + n + " nBitLength: " + n.bitLength());
1138 log.finer("e: " + e + " eBitLength: " + e.bitLength());
1139 log.finer("d: " + d + " dBitLength: " + d.bitLength());
1140 log.finer("p: " + p + " pBitLength: " + p.bitLength());
1141 log.finer("q: " + q + " qBitLength: " + q.bitLength());
1142 }
1143
1144
1145 //////
1146 // Calculate the CRT values.
1147 //////
1148 BigInteger dP = d.mod(pSub1);
1149 BigInteger dQ = d.mod(qSub1);
1150 BigInteger qInv = q.modInverse(p);
1151
1152 if (log.isLoggable(Level.FINER)) {
1153 log.finer("dP: " + dP);
1154 log.finer("dQ: " + dQ);
1155 log.finer("qInv: " + qInv);
1156 }
1157
1158 //////
1159 // Construct the public Key.
1160 //////
1161 RSAPublicKey publicKey = new RSAPublicKeyImpl(n, e);
1162
1163 //////
1164 // Construct the private CRT key
1165 //////
1166 RSAPrivateCrtKey privateCrtKey =
1167 new RSAPrivateCrtKeyImpl(n, e, d, p, q, dP, dQ, qInv);
1168
1169 if (log.isLoggable(Level.FINER)) {
1170 log.finer("Leave generateKeyPair() and return the new generated KeyPair.");
1171 }
1172
1173 //////
1174 // Construct and return the new generated KeyPair.
1175 //////
1176 return new KeyPair(publicKey, privateCrtKey);
1177 }
1178}
1179
|
RSAKeyPairGeneratorImpl |
|