| Frames | No Frames |
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> < q < 2<sup>160</sup></code></li> 109: * <li><code>2<sup>L-1</sup> < p < 2<sup>L</sup></code> for a 110: * specified <code>L</code>, where <code>L = 512 + 64j</code> for some 111: * <code>0 <= j <= 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> < q < 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> < X < 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: 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: }