| Frames | No Frames |
1: /* RFC2631.java -- 2: Copyright (C) 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.javax.crypto.key.dh; 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 Diffie-Hellman parameter generation as defined in 49: * RFC-2631. 50: * <p> 51: * Reference: 52: * <ol> 53: * <li><a href="http://www.ietf.org/rfc/rfc2631.txt">Diffie-Hellman Key 54: * Agreement Method</a><br> 55: * Eric Rescorla.</li> 56: * </ol> 57: */ 58: public class RFC2631 59: { 60: public static final int DH_PARAMS_SEED = 0; 61: public static final int DH_PARAMS_COUNTER = 1; 62: public static final int DH_PARAMS_Q = 2; 63: public static final int DH_PARAMS_P = 3; 64: public static final int DH_PARAMS_J = 4; 65: public static final int DH_PARAMS_G = 5; 66: private static final BigInteger TWO = BigInteger.valueOf(2L); 67: /** The SHA instance to use. */ 68: private Sha160 sha = new Sha160(); 69: /** Length of private modulus and of q. */ 70: private int m; 71: /** Length of public modulus p. */ 72: private int L; 73: /** The optional {@link SecureRandom} instance to use. */ 74: private SecureRandom rnd = null; 75: /** Our default source of randomness. */ 76: private PRNG prng = null; 77: 78: public RFC2631(int m, int L, SecureRandom rnd) 79: { 80: super(); 81: 82: this.m = m; 83: this.L = L; 84: this.rnd = rnd; 85: } 86: 87: public BigInteger[] generateParameters() 88: { 89: int i, j, counter; 90: byte[] u1, u2, v; 91: byte[] seedBytes = new byte[m / 8]; 92: BigInteger SEED, U, q, R, V, W, X, p, g; 93: // start by genrating p and q, where q is of length m and p is of length L 94: // 1. Set m' = m/160 where / represents integer division with rounding 95: // upwards. I.e. 200/160 = 2. 96: int m_ = (m + 159) / 160; 97: // 2. Set L'= L/160 98: int L_ = (L + 159) / 160; 99: // 3. Set N'= L/1024 100: int N_ = (L + 1023) / 1024; 101: algorithm: while (true) 102: { 103: step4: while (true) 104: { 105: // 4. Select an arbitrary bit string SEED such that length of 106: // SEED >= m 107: nextRandomBytes(seedBytes); 108: SEED = new BigInteger(1, seedBytes).setBit(m - 1).setBit(0); 109: // 5. Set U = 0 110: U = BigInteger.ZERO; 111: // 6. For i = 0 to m' - 1 112: // U = U + (SHA1[SEED + i] XOR SHA1[(SEED + m' + i)) * 2^(160 * i) 113: // Note that for m=160, this reduces to the algorithm of FIPS-186 114: // U = SHA1[SEED] XOR SHA1[(SEED+1) mod 2^160 ]. 115: for (i = 0; i < m_; i++) 116: { 117: u1 = SEED.add(BigInteger.valueOf(i)).toByteArray(); 118: u2 = SEED.add(BigInteger.valueOf(m_ + i)).toByteArray(); 119: sha.update(u1, 0, u1.length); 120: u1 = sha.digest(); 121: sha.update(u2, 0, u2.length); 122: u2 = sha.digest(); 123: for (j = 0; j < u1.length; j++) 124: u1[j] ^= u2[j]; 125: U = U.add(new BigInteger(1, u1).multiply(TWO.pow(160 * i))); 126: } 127: // 5. Form q from U by computing U mod (2^m) and setting the most 128: // significant bit (the 2^(m-1) bit) and the least significant 129: // bit to 1. In terms of boolean operations, q = U OR 2^(m-1) OR 130: // 1. Note that 2^(m-1) < q < 2^m 131: q = U.setBit(m - 1).setBit(0); 132: // 6. Use a robust primality algorithm to test whether q is prime. 133: // 7. If q is not prime then go to 4. 134: if (q.isProbablePrime(80)) 135: break step4; 136: } 137: // 8. Let counter = 0 138: counter = 0; 139: while (true) 140: { 141: // 9. Set R = seed + 2*m' + (L' * counter) 142: R = SEED 143: .add(BigInteger.valueOf(2 * m_)) 144: .add(BigInteger.valueOf(L_ * counter)); 145: // 10. Set V = 0 146: V = BigInteger.ZERO; 147: // 12. For i = 0 to L'-1 do: V = V + SHA1(R + i) * 2^(160 * i) 148: for (i = 0; i < L_; i++) 149: { 150: v = R.toByteArray(); 151: sha.update(v, 0, v.length); 152: v = sha.digest(); 153: V = V.add(new BigInteger(1, v).multiply(TWO.pow(160 * i))); 154: } 155: // 13. Set W = V mod 2^L 156: W = V.mod(TWO.pow(L)); 157: // 14. Set X = W OR 2^(L-1) 158: // Note that 0 <= W < 2^(L-1) and hence X >= 2^(L-1) 159: X = W.setBit(L - 1); 160: // 15. Set p = X - (X mod (2*q)) + 1 161: p = X.add(BigInteger.ONE).subtract(X.mod(TWO.multiply(q))); 162: // 16. If p > 2^(L-1) use a robust primality test to test whether p 163: // is prime. Else go to 18. 164: // 17. If p is prime output p, q, seed, counter and stop. 165: if (p.isProbablePrime(80)) 166: { 167: break algorithm; 168: } 169: // 18. Set counter = counter + 1 170: counter++; 171: // 19. If counter < (4096 * N) then go to 8. 172: // 20. Output "failure" 173: if (counter >= 4096 * N_) 174: continue algorithm; 175: } 176: } 177: // compute g. from FIPS-186, Appendix 4: 178: // 1. Generate p and q as specified in Appendix 2. 179: // 2. Let e = (p - 1) / q 180: BigInteger e = p.subtract(BigInteger.ONE).divide(q); 181: BigInteger h = TWO; 182: BigInteger p_minus_1 = p.subtract(BigInteger.ONE); 183: g = TWO; 184: // 3. Set h = any integer, where 1 < h < p - 1 and h differs from any 185: // value previously tried 186: for (; h.compareTo(p_minus_1) < 0; h = h.add(BigInteger.ONE)) 187: { 188: // 4. Set g = h**e mod p 189: g = h.modPow(e, p); 190: // 5. If g = 1, go to step 3 191: if (! g.equals(BigInteger.ONE)) 192: break; 193: } 194: return new BigInteger[] { SEED, BigInteger.valueOf(counter), q, p, e, g }; 195: } 196: 197: /** 198: * Fills the designated byte array with random data. 199: * 200: * @param buffer the byte array to fill with random data. 201: */ 202: private void nextRandomBytes(byte[] buffer) 203: { 204: if (rnd != null) 205: rnd.nextBytes(buffer); 206: else 207: getDefaultPRNG().nextBytes(buffer); 208: } 209: 210: private PRNG getDefaultPRNG() 211: { 212: if (prng == null) 213: prng = PRNG.getInstance(); 214: 215: return prng; 216: } 217: }