001: package org.bouncycastle.crypto.generators;
002:
003: import org.bouncycastle.crypto.AsymmetricCipherKeyPair;
004: import org.bouncycastle.crypto.AsymmetricCipherKeyPairGenerator;
005: import org.bouncycastle.crypto.KeyGenerationParameters;
006: import org.bouncycastle.crypto.params.NaccacheSternKeyGenerationParameters;
007: import org.bouncycastle.crypto.params.NaccacheSternKeyParameters;
008: import org.bouncycastle.crypto.params.NaccacheSternPrivateKeyParameters;
009:
010: import java.math.BigInteger;
011: import java.security.SecureRandom;
012: import java.util.Vector;
013:
014: /**
015: * Key generation parameters for NaccacheStern cipher. For details on this cipher, please see
016: *
017: * http://www.gemplus.com/smart/rd/publications/pdf/NS98pkcs.pdf
018: */
019: public class NaccacheSternKeyPairGenerator implements
020: AsymmetricCipherKeyPairGenerator {
021:
022: private static int[] smallPrimes = { 3, 5, 7, 11, 13, 17, 19, 23,
023: 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,
024: 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
025: 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
026: 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
027: 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359,
028: 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433,
029: 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
030: 509, 521, 523, 541, 547, 557 };
031:
032: private NaccacheSternKeyGenerationParameters param;
033:
034: private static final BigInteger ONE = BigInteger.valueOf(1); // JDK 1.1 compatibility
035:
036: /*
037: * (non-Javadoc)
038: *
039: * @see org.bouncycastle.crypto.AsymmetricCipherKeyPairGenerator#init(org.bouncycastle.crypto.KeyGenerationParameters)
040: */
041: public void init(KeyGenerationParameters param) {
042: this .param = (NaccacheSternKeyGenerationParameters) param;
043: }
044:
045: /*
046: * (non-Javadoc)
047: *
048: * @see org.bouncycastle.crypto.AsymmetricCipherKeyPairGenerator#generateKeyPair()
049: */
050: public AsymmetricCipherKeyPair generateKeyPair() {
051: int strength = param.getStrength();
052: SecureRandom rand = param.getRandom();
053: int certainty = param.getCertainty();
054: boolean debug = param.isDebug();
055:
056: if (debug) {
057: System.out.println("Fetching first "
058: + param.getCntSmallPrimes() + " primes.");
059: }
060:
061: Vector smallPrimes = findFirstPrimes(param.getCntSmallPrimes());
062: smallPrimes = permuteList(smallPrimes, rand);
063:
064: BigInteger u = ONE;
065: BigInteger v = ONE;
066:
067: for (int i = 0; i < smallPrimes.size() / 2; i++) {
068: u = u.multiply((BigInteger) smallPrimes.elementAt(i));
069: }
070: for (int i = smallPrimes.size() / 2; i < smallPrimes.size(); i++) {
071: v = v.multiply((BigInteger) smallPrimes.elementAt(i));
072: }
073:
074: BigInteger sigma = u.multiply(v);
075:
076: // n = (2 a u p_ + 1 ) ( 2 b v q_ + 1)
077: // -> |n| = strength
078: // |2| = 1 in bits
079: // -> |a| * |b| = |n| - |u| - |v| - |p_| - |q_| - |2| -|2|
080: // remainingStrength = strength - sigma.bitLength() - p_.bitLength() -
081: // q_.bitLength() - 1 -1
082: int remainingStrength = strength - sigma.bitLength() - 48;
083: BigInteger a = generatePrime(remainingStrength / 2 + 1,
084: certainty, rand);
085: BigInteger b = generatePrime(remainingStrength / 2 + 1,
086: certainty, rand);
087:
088: BigInteger p_;
089: BigInteger q_;
090: BigInteger p;
091: BigInteger q;
092: long tries = 0;
093: if (debug) {
094: System.out.println("generating p and q");
095: }
096:
097: BigInteger _2au = a.multiply(u).shiftLeft(1);
098: BigInteger _2bv = b.multiply(v).shiftLeft(1);
099:
100: for (;;) {
101: tries++;
102:
103: p_ = generatePrime(24, certainty, rand);
104:
105: p = p_.multiply(_2au).add(ONE);
106:
107: if (!p.isProbablePrime(certainty)) {
108: continue;
109: }
110:
111: for (;;) {
112: q_ = generatePrime(24, certainty, rand);
113:
114: if (p_.equals(q_)) {
115: continue;
116: }
117:
118: q = q_.multiply(_2bv).add(ONE);
119:
120: if (q.isProbablePrime(certainty)) {
121: break;
122: }
123: }
124:
125: if (!sigma.gcd(p_.multiply(q_)).equals(ONE)) {
126: // System.out.println("sigma.gcd(p_.mult(q_)) != 1!\n p_: " + p_
127: // +"\n q_: "+ q_ );
128: continue;
129: }
130:
131: if (p.multiply(q).bitLength() < strength) {
132: if (debug) {
133: System.out.println("key size too small. Should be "
134: + strength + " but is actually "
135: + p.multiply(q).bitLength());
136: }
137: continue;
138: }
139: break;
140: }
141:
142: if (debug) {
143: System.out.println("needed " + tries
144: + " tries to generate p and q.");
145: }
146:
147: BigInteger n = p.multiply(q);
148: BigInteger phi_n = p.subtract(ONE).multiply(q.subtract(ONE));
149: BigInteger g;
150: tries = 0;
151: if (debug) {
152: System.out.println("generating g");
153: }
154: for (;;) {
155:
156: Vector gParts = new Vector();
157: for (int ind = 0; ind != smallPrimes.size(); ind++) {
158: BigInteger i = (BigInteger) smallPrimes.elementAt(ind);
159: BigInteger e = phi_n.divide(i);
160:
161: for (;;) {
162: tries++;
163: g = new BigInteger(strength, certainty, rand);
164: if (g.modPow(e, n).equals(ONE)) {
165: continue;
166: }
167: gParts.addElement(g);
168: break;
169: }
170: }
171: g = ONE;
172: for (int i = 0; i < smallPrimes.size(); i++) {
173: g = g.multiply(
174: ((BigInteger) gParts.elementAt(i)).modPow(sigma
175: .divide((BigInteger) smallPrimes
176: .elementAt(i)), n)).mod(n);
177: }
178:
179: // make sure that g is not divisible by p_i or q_i
180: boolean divisible = false;
181: for (int i = 0; i < smallPrimes.size(); i++) {
182: if (g.modPow(
183: phi_n.divide((BigInteger) smallPrimes
184: .elementAt(i)), n).equals(ONE)) {
185: if (debug) {
186: System.out.println("g has order phi(n)/"
187: + smallPrimes.elementAt(i) + "\n g: "
188: + g);
189: }
190: divisible = true;
191: break;
192: }
193: }
194:
195: if (divisible) {
196: continue;
197: }
198:
199: // make sure that g has order > phi_n/4
200:
201: if (g.modPow(phi_n.divide(BigInteger.valueOf(4)), n)
202: .equals(ONE)) {
203: if (debug) {
204: System.out.println("g has order phi(n)/4\n g:" + g);
205: }
206: continue;
207: }
208:
209: if (g.modPow(phi_n.divide(p_), n).equals(ONE)) {
210: if (debug) {
211: System.out.println("g has order phi(n)/p'\n g: "
212: + g);
213: }
214: continue;
215: }
216: if (g.modPow(phi_n.divide(q_), n).equals(ONE)) {
217: if (debug) {
218: System.out.println("g has order phi(n)/q'\n g: "
219: + g);
220: }
221: continue;
222: }
223: if (g.modPow(phi_n.divide(a), n).equals(ONE)) {
224: if (debug) {
225: System.out
226: .println("g has order phi(n)/a\n g: " + g);
227: }
228: continue;
229: }
230: if (g.modPow(phi_n.divide(b), n).equals(ONE)) {
231: if (debug) {
232: System.out
233: .println("g has order phi(n)/b\n g: " + g);
234: }
235: continue;
236: }
237: break;
238: }
239: if (debug) {
240: System.out.println("needed " + tries
241: + " tries to generate g");
242: System.out.println();
243: System.out
244: .println("found new NaccacheStern cipher variables:");
245: System.out.println("smallPrimes: " + smallPrimes);
246: System.out.println("sigma:...... " + sigma + " ("
247: + sigma.bitLength() + " bits)");
248: System.out.println("a:.......... " + a);
249: System.out.println("b:.......... " + b);
250: System.out.println("p':......... " + p_);
251: System.out.println("q':......... " + q_);
252: System.out.println("p:.......... " + p);
253: System.out.println("q:.......... " + q);
254: System.out.println("n:.......... " + n);
255: System.out.println("phi(n):..... " + phi_n);
256: System.out.println("g:.......... " + g);
257: System.out.println();
258: }
259:
260: return new AsymmetricCipherKeyPair(
261: new NaccacheSternKeyParameters(false, g, n, sigma
262: .bitLength()),
263: new NaccacheSternPrivateKeyParameters(g, n, sigma
264: .bitLength(), smallPrimes, phi_n));
265: }
266:
267: private static BigInteger generatePrime(int bitLength,
268: int certainty, SecureRandom rand) {
269: BigInteger p_ = new BigInteger(bitLength, certainty, rand);
270: while (p_.bitLength() != bitLength) {
271: p_ = new BigInteger(bitLength, certainty, rand);
272: }
273: return p_;
274: }
275:
276: /**
277: * Generates a permuted ArrayList from the original one. The original List
278: * is not modified
279: *
280: * @param arr
281: * the ArrayList to be permuted
282: * @param rand
283: * the source of Randomness for permutation
284: * @return a new ArrayList with the permuted elements.
285: */
286: private static Vector permuteList(Vector arr, SecureRandom rand) {
287: Vector retval = new Vector();
288: Vector tmp = new Vector();
289: for (int i = 0; i < arr.size(); i++) {
290: tmp.addElement(arr.elementAt(i));
291: }
292: retval.addElement(tmp.elementAt(0));
293: tmp.removeElementAt(0);
294: while (tmp.size() != 0) {
295: retval.insertElementAt(tmp.elementAt(0), getInt(rand,
296: retval.size() + 1));
297: tmp.removeElementAt(0);
298: }
299: return retval;
300: }
301:
302: private static int getInt(SecureRandom rand, int n) {
303: if ((n & -n) == n) {
304: return (int) ((n * (long) (rand.nextInt() & 0x7fffffff)) >> 31);
305: }
306:
307: int bits, val;
308: do {
309: bits = rand.nextInt() & 0x7fffffff;
310: val = bits % n;
311: } while (bits - val + (n - 1) < 0);
312:
313: return val;
314: }
315:
316: /**
317: * Finds the first 'count' primes starting with 3
318: *
319: * @param count
320: * the number of primes to find
321: * @return a vector containing the found primes as Integer
322: */
323: private static Vector findFirstPrimes(int count) {
324: Vector primes = new Vector(count);
325:
326: for (int i = 0; i != count; i++) {
327: primes.addElement(BigInteger.valueOf(smallPrimes[i]));
328: }
329:
330: return primes;
331: }
332:
333: }
|