libjava/classpath/gnu/java/security/key/dss/FIPS186.java

   1 /* FIPS186.java --
   2    Copyright 2001, 2002, 2003, 2006 Free Software Foundation, Inc.
   3
   4 This file is a part of GNU Classpath.
   5
   6 GNU Classpath is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2 of the License, or (at
   9 your option) any later version.
  10
  11 GNU Classpath is distributed in the hope that it will be useful, but
  12 WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Classpath; if not, write to the Free Software
  18 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
  19 USA
  20
  21 Linking this library statically or dynamically with other modules is
  22 making a combined work based on this library.  Thus, the terms and
  23 conditions of the GNU General Public License cover the whole
  24 combination.
  25
  26 As a special exception, the copyright holders of this library give you
  27 permission to link this library with independent modules to produce an
  28 executable, regardless of the license terms of these independent
  29 modules, and to copy and distribute the resulting executable under
  30 terms of your choice, provided that you also meet, for each linked
  31 independent module, the terms and conditions of the license of that
  32 module.  An independent module is a module which is not derived from
  33 or based on this library.  If you modify this library, you may extend
  34 this exception to your version of the library, but you are not
  35 obligated to do so.  If you do not wish to do so, delete this
  36 exception statement from your version.  */
  37
  38
  39 package gnu.java.security.key.dss;
  40
  41 import gnu.java.security.hash.Sha160;
  42 import gnu.java.security.util.PRNG;
  43
  44 import java.math.BigInteger;
  45 import java.security.SecureRandom;
  46
  47 /**
  48  * An implementation of the DSA parameters generation as described in FIPS-186.
  49  * <p>
  50  * References:
  51  * <p>
  52  * <a href="http://www.itl.nist.gov/fipspubs/fip186.htm">Digital Signature
  53  * Standard (DSS)</a>, Federal Information Processing Standards Publication
  54  * 186. National Institute of Standards and Technology.
  55  */
  56 public class FIPS186
  57 {
  58   public static final int DSA_PARAMS_SEED = 0;
  59
  60   public static final int DSA_PARAMS_COUNTER = 1;
  61
  62   public static final int DSA_PARAMS_Q = 2;
  63
  64   public static final int DSA_PARAMS_P = 3;
  65
  66   public static final int DSA_PARAMS_E = 4;
  67
  68   public static final int DSA_PARAMS_G = 5;
  69
  70   /** The BigInteger constant 2. */
  71   private static final BigInteger TWO = BigInteger.valueOf(2L);
  72
  73   private static final BigInteger TWO_POW_160 = TWO.pow(160);
  74
  75   /** The SHA instance to use. */
  76   private Sha160 sha = new Sha160();
  77
  78   /** The length of the modulus of DSS keys generated by this instance. */
  79   private int L;
  80
  81   /** The optional {@link SecureRandom} instance to use. */
  82   private SecureRandom rnd = null;
  83
  84   /** Our default source of randomness. */
  85   private PRNG prng = null;
  86
  87   public FIPS186(int L, SecureRandom rnd)
  88   {
  89     super();
  90
  91     this.L = L;
  92     this.rnd = rnd;
  93   }
  94
  95   /**
  96    * This method generates the DSS <code>p</code>, <code>q</code>, and
  97    * <code>g</code> parameters only when <code>L</code> (the modulus length)
  98    * is not one of the following: <code>512</code>, <code>768</code> and
  99    * <code>1024</code>. For those values of <code>L</code>, this
 100    * implementation uses pre-computed values of <code>p</code>,
 101    * <code>q</code>, and <code>g</code> given in the document <i>CryptoSpec</i>
 102    * included in the security guide documentation of the standard JDK
 103    * distribution.
 104    * <p>
 105    * The DSS requires two primes , <code>p</code> and <code>q</code>,
 106    * satisfying the following three conditions:
 107    * <ul>
 108    * <li><code>2<sup>159</sup> &lt; q &lt; 2<sup>160</sup></code></li>
 109    * <li><code>2<sup>L-1</sup> &lt; p &lt; 2<sup>L</sup></code> for a
 110    * specified <code>L</code>, where <code>L = 512 + 64j</code> for some
 111    * <code>0 &lt;= j &lt;= 8</code></li>
 112    * <li>q divides p - 1.</li>
 113    * </ul>
 114    * The algorithm used to find these primes is as described in FIPS-186,
 115    * section 2.2: GENERATION OF PRIMES. This prime generation scheme starts by
 116    * using the {@link Sha160} and a user supplied <i>SEED</i> to construct a
 117    * prime, <code>q</code>, in the range 2<sup>159</sup> &lt; q &lt; 2<sup>160</sup>.
 118    * Once this is accomplished, the same <i>SEED</i> value is used to construct
 119    * an <code>X</code> in the range <code>2<sup>L-1
 120    * </sup> &lt; X &lt; 2<sup>L</sup>. The prime, <code>p</code>, is then
 121    * formed by rounding <code>X</code> to a number congruent to <code>1 mod
 122    * 2q</code>. In this implementation we use the same <i>SEED</i> value given
 123    * in FIPS-186, Appendix 5.
 124    */
 125   public BigInteger[] generateParameters()
 126   {
 127     int counter, offset;
 128     BigInteger SEED, alpha, U, q, OFFSET, SEED_PLUS_OFFSET, W, X, p, c, g;
 129     byte[] a, u;
 130     byte[] kb = new byte[20]; // to hold 160 bits of randomness
 131
 132     // Let L-1 = n*160 + b, where b and n are integers and 0 <= b < 160.
 133     int b = (L - 1) % 160;
 134     int n = (L - 1 - b) / 160;
 135     BigInteger[] V = new BigInteger[n + 1];
 136     algorithm: while (true)
 137       {
 138         step1: while (true)
 139           {
 140             // 1. Choose an arbitrary sequence of at least 160 bits and
 141             // call it SEED.
 142             nextRandomBytes(kb);
 143             SEED = new BigInteger(1, kb).setBit(159).setBit(0);
 144             // Let g be the length of SEED in bits. here always 160
 145             // 2. Compute: U = SHA[SEED] XOR SHA[(SEED+1) mod 2**g]
 146             alpha = SEED.add(BigInteger.ONE).mod(TWO_POW_160);
 147             synchronized (sha)
 148               {
 149                 a = SEED.toByteArray();
 150                 sha.update(a, 0, a.length);
 151                 a = sha.digest();
 152                 u = alpha.toByteArray();
 153                 sha.update(u, 0, u.length);
 154                 u = sha.digest();
 155               }
 156             for (int i = 0; i < a.length; i++)
 157               a[i] ^= u[i];
 158
 159             U = new BigInteger(1, a);
 160             // 3. Form q from U by setting the most significant bit (the
 161             // 2**159 bit) and the least significant bit to 1. In terms of
 162             // boolean operations, q = U OR 2**159 OR 1. Note that
 163             // 2**159 < q < 2**160.
 164             q = U.setBit(159).setBit(0);
 165             // 4. Use a robust primality testing algorithm to test whether
 166             // q is prime(1). A robust primality test is one where the
 167             // probability of a non-prime number passing the test is at
 168             // most 1/2**80.
 169             // 5. If q is not prime, go to step 1.
 170             if (q.isProbablePrime(80))
 171               break step1;
 172           } // step1
 173         // 6. Let counter = 0 and offset = 2.
 174         counter = 0;
 175         offset = 2;
 176         step7: while (true)
 177           {
 178             OFFSET = BigInteger.valueOf(offset & 0xFFFFFFFFL);
 179             SEED_PLUS_OFFSET = SEED.add(OFFSET);
 180             // 7. For k = 0,...,n let V[k] = SHA[(SEED + offset + k) mod 2**g].
 181             synchronized (sha)
 182               {
 183                 for (int k = 0; k <= n; k++)
 184                   {
 185                     a = SEED_PLUS_OFFSET
 186                         .add(BigInteger.valueOf(k & 0xFFFFFFFFL))
 187                         .mod(TWO_POW_160).toByteArray();
 188                     sha.update(a, 0, a.length);
 189                     V[k] = new BigInteger(1, sha.digest());
 190                   }
 191               }
 192             // 8. Let W be the integer:
 193             // V[0]+V[1]*2**160+...+V[n-1]*2**((n-1)*160)+(V[n]mod2**b)*2**(n*160)
 194             // and let : X = W + 2**(L-1).
 195             // Note that 0 <= W < 2**(L-1) and hence 2**(L-1) <= X < 2**L.
 196             W = V[0];
 197             for (int k = 1; k < n; k++)
 198               W = W.add(V[k].multiply(TWO.pow(k * 160)));
 199
 200             W = W.add(V[n].mod(TWO.pow(b)).multiply(TWO.pow(n * 160)));
 201             X = W.add(TWO.pow(L - 1));
 202             // 9. Let c = X mod 2q and set p = X - (c - 1).
 203             // Note that p is congruent to 1 mod 2q.
 204             c = X.mod(TWO.multiply(q));
 205             p = X.subtract(c.subtract(BigInteger.ONE));
 206             // 10. If p < 2**(L-1), then go to step 13.
 207             if (p.compareTo(TWO.pow(L - 1)) >= 0)
 208               {
 209                 // 11. Perform a robust primality test on p.
 210                 // 12. If p passes the test performed in step 11, go to step 15.
 211                 if (p.isProbablePrime(80))
 212                   break algorithm;
 213               }
 214             // 13. Let counter = counter + 1 and offset = offset + n + 1.
 215             counter++;
 216             offset += n + 1;
 217             // 14. If counter >= 4096 go to step 1, otherwise go to step 7.
 218             if (counter >= 4096)
 219               continue algorithm;
 220           } // step7
 221       } // algorithm
 222     // compute g. from FIPS-186, Appendix 4:
 223     // 1. Generate p and q as specified in Appendix 2.
 224     // 2. Let e = (p - 1) / q
 225     BigInteger e = p.subtract(BigInteger.ONE).divide(q);
 226     BigInteger h = TWO;
 227     BigInteger p_minus_1 = p.subtract(BigInteger.ONE);
 228     g = TWO;
 229     // 3. Set h = any integer, where 1 < h < p - 1 and
 230     // h differs from any value previously tried
 231     for (; h.compareTo(p_minus_1) < 0; h = h.add(BigInteger.ONE))
 232       {
 233         // 4. Set g = h**e mod p
 234         g = h.modPow(e, p);
 235         // 5. If g = 1, go to step 3
 236         if (! g.equals(BigInteger.ONE))
 237           break;
 238       }
 239     return new BigInteger[] { SEED, BigInteger.valueOf(counter), q, p, e, g };
 240   }
 241
 242   /**
 243    * Fills the designated byte array with random data.
 244    *
 245    * @param buffer the byte array to fill with random data.
 246    */
 247   private void nextRandomBytes(byte[] buffer)
 248   {
 249     if (rnd != null)
 250       rnd.nextBytes(buffer);
 251     else
 252       getDefaultPRNG().nextBytes(buffer);
 253   }
 254
 255   private PRNG getDefaultPRNG()
 256   {
 257     if (prng == null)
 258       prng = PRNG.getInstance();
 259
 260     return prng;
 261   }
 262 }