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&uuml;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