001: package org.bouncycastle.crypto.generators;
002:
003: import org.bouncycastle.crypto.params.GOST3410Parameters;
004: import org.bouncycastle.crypto.params.GOST3410ValidationParameters;
005:
006: import java.math.BigInteger;
007: import java.security.SecureRandom;
008:
009: /**
010: * generate suitable parameters for GOST3410.
011: */
012: public class GOST3410ParametersGenerator {
013: private int size;
014: private int typeproc;
015: private SecureRandom init_random;
016:
017: private static final BigInteger ONE = BigInteger.valueOf(1);
018: private static final BigInteger TWO = BigInteger.valueOf(2);
019:
020: /**
021: * initialise the key generator.
022: *
023: * @param size size of the key
024: * @param typeproc type procedure A,B = 1; A',B' - else
025: * @param random random byte source.
026: */
027: public void init(int size, int typeproc, SecureRandom random) {
028: this .size = size;
029: this .typeproc = typeproc;
030: this .init_random = random;
031: }
032:
033: //Procedure A
034: private int procedure_A(int x0, int c, BigInteger[] pq, int size) {
035: //Verify and perform condition: 0<x<2^16; 0<c<2^16; c - odd.
036: while (x0 < 0 || x0 > 65536) {
037: x0 = init_random.nextInt() / 32768;
038: }
039:
040: while ((c < 0 || c > 65536) || (c / 2 == 0)) {
041: c = init_random.nextInt() / 32768 + 1;
042: }
043:
044: BigInteger C = new BigInteger(Integer.toString(c));
045: BigInteger constA16 = new BigInteger("19381");
046:
047: //step1
048: BigInteger[] y = new BigInteger[1]; // begin length = 1
049: y[0] = new BigInteger(Integer.toString(x0));
050:
051: //step 2
052: int[] t = new int[1]; // t - orders; begin length = 1
053: t[0] = size;
054: int s = 0;
055: for (int i = 0; t[i] >= 17; i++) {
056: // extension array t
057: int tmp_t[] = new int[t.length + 1]; ///////////////
058: System.arraycopy(t, 0, tmp_t, 0, t.length); // extension
059: t = new int[tmp_t.length]; // array t
060: System.arraycopy(tmp_t, 0, t, 0, tmp_t.length); ///////////////
061:
062: t[i + 1] = t[i] / 2;
063: s = i + 1;
064: }
065:
066: //step3
067: BigInteger p[] = new BigInteger[s + 1];
068: p[s] = new BigInteger("8003", 16); //set min prime number length 16 bit
069:
070: int m = s - 1; //step4
071:
072: for (int i = 0; i < s; i++) {
073: int rm = t[m] / 16; //step5
074:
075: step6: for (;;) {
076: //step 6
077: BigInteger tmp_y[] = new BigInteger[y.length]; ////////////////
078: System.arraycopy(y, 0, tmp_y, 0, y.length); // extension
079: y = new BigInteger[rm + 1]; // array y
080: System.arraycopy(tmp_y, 0, y, 0, tmp_y.length); ////////////////
081:
082: for (int j = 0; j < rm; j++) {
083: y[j + 1] = (y[j].multiply(constA16).add(C)).mod(TWO
084: .pow(16));
085: }
086:
087: //step 7
088: BigInteger Ym = new BigInteger("0");
089: for (int j = 0; j < rm; j++) {
090: Ym = Ym.add(y[j].multiply(TWO.pow(16 * j)));
091: }
092:
093: y[0] = y[rm]; //step 8
094:
095: //step 9
096: BigInteger N = TWO.pow(t[m] - 1).divide(p[m + 1]).add(
097: (TWO.pow(t[m] - 1).multiply(Ym))
098: .divide(p[m + 1].multiply(TWO
099: .pow(16 * rm))));
100:
101: if (N.mod(TWO).compareTo(ONE) == 0) {
102: N = N.add(ONE);
103: }
104:
105: int k = 0; //step 10
106:
107: step11: for (;;) {
108: //step 11
109: p[m] = p[m + 1].multiply(
110: N.add(BigInteger.valueOf(k))).add(ONE);
111:
112: if (p[m].compareTo(TWO.pow(t[m])) == 1) {
113: continue step6; //step 12
114: }
115:
116: //step13
117: if ((TWO.modPow(
118: p[m + 1].multiply(N.add(BigInteger
119: .valueOf(k))), p[m]).compareTo(ONE) == 0)
120: && (TWO.modPow(
121: N.add(BigInteger.valueOf(k)), p[m])
122: .compareTo(ONE) != 0)) {
123: m -= 1;
124: break;
125: } else {
126: k += 2;
127: continue step11;
128: }
129: }
130:
131: if (m >= 0) {
132: break; //step 14
133: } else {
134: pq[0] = p[0];
135: pq[1] = p[1];
136: return y[0].intValue(); //return for procedure B step 2
137: }
138: }
139: }
140: return y[0].intValue();
141: }
142:
143: //Procedure A'
144: private long procedure_Aa(long x0, long c, BigInteger[] pq, int size) {
145: //Verify and perform condition: 0<x<2^32; 0<c<2^32; c - odd.
146: while (x0 < 0 || x0 > 4294967296L) {
147: x0 = init_random.nextInt() * 2;
148: }
149:
150: while ((c < 0 || c > 4294967296L) || (c / 2 == 0)) {
151: c = init_random.nextInt() * 2 + 1;
152: }
153:
154: BigInteger C = new BigInteger(Long.toString(c));
155: BigInteger constA32 = new BigInteger("97781173");
156:
157: //step1
158: BigInteger[] y = new BigInteger[1]; // begin length = 1
159: y[0] = new BigInteger(Long.toString(x0));
160:
161: //step 2
162: int[] t = new int[1]; // t - orders; begin length = 1
163: t[0] = size;
164: int s = 0;
165: for (int i = 0; t[i] >= 33; i++) {
166: // extension array t
167: int tmp_t[] = new int[t.length + 1]; ///////////////
168: System.arraycopy(t, 0, tmp_t, 0, t.length); // extension
169: t = new int[tmp_t.length]; // array t
170: System.arraycopy(tmp_t, 0, t, 0, tmp_t.length); ///////////////
171:
172: t[i + 1] = t[i] / 2;
173: s = i + 1;
174: }
175:
176: //step3
177: BigInteger p[] = new BigInteger[s + 1];
178: p[s] = new BigInteger("8000000B", 16); //set min prime number length 32 bit
179:
180: int m = s - 1; //step4
181:
182: for (int i = 0; i < s; i++) {
183: int rm = t[m] / 32; //step5
184:
185: step6: for (;;) {
186: //step 6
187: BigInteger tmp_y[] = new BigInteger[y.length]; ////////////////
188: System.arraycopy(y, 0, tmp_y, 0, y.length); // extension
189: y = new BigInteger[rm + 1]; // array y
190: System.arraycopy(tmp_y, 0, y, 0, tmp_y.length); ////////////////
191:
192: for (int j = 0; j < rm; j++) {
193: y[j + 1] = (y[j].multiply(constA32).add(C)).mod(TWO
194: .pow(32));
195: }
196:
197: //step 7
198: BigInteger Ym = new BigInteger("0");
199: for (int j = 0; j < rm; j++) {
200: Ym = Ym.add(y[j].multiply(TWO.pow(32 * j)));
201: }
202:
203: y[0] = y[rm]; //step 8
204:
205: //step 9
206: BigInteger N = TWO.pow(t[m] - 1).divide(p[m + 1]).add(
207: (TWO.pow(t[m] - 1).multiply(Ym))
208: .divide(p[m + 1].multiply(TWO
209: .pow(32 * rm))));
210:
211: if (N.mod(TWO).compareTo(ONE) == 0) {
212: N = N.add(ONE);
213: }
214:
215: int k = 0; //step 10
216:
217: step11: for (;;) {
218: //step 11
219: p[m] = p[m + 1].multiply(
220: N.add(BigInteger.valueOf(k))).add(ONE);
221:
222: if (p[m].compareTo(TWO.pow(t[m])) == 1) {
223: continue step6; //step 12
224: }
225:
226: //step13
227: if ((TWO.modPow(
228: p[m + 1].multiply(N.add(BigInteger
229: .valueOf(k))), p[m]).compareTo(ONE) == 0)
230: && (TWO.modPow(
231: N.add(BigInteger.valueOf(k)), p[m])
232: .compareTo(ONE) != 0)) {
233: m -= 1;
234: break;
235: } else {
236: k += 2;
237: continue step11;
238: }
239: }
240:
241: if (m >= 0) {
242: break; //step 14
243: } else {
244: pq[0] = p[0];
245: pq[1] = p[1];
246: return y[0].longValue(); //return for procedure B' step 2
247: }
248: }
249: }
250: return y[0].longValue();
251: }
252:
253: //Procedure B
254: private void procedure_B(int x0, int c, BigInteger[] pq) {
255: //Verify and perform condition: 0<x<2^16; 0<c<2^16; c - odd.
256: while (x0 < 0 || x0 > 65536) {
257: x0 = init_random.nextInt() / 32768;
258: }
259:
260: while ((c < 0 || c > 65536) || (c / 2 == 0)) {
261: c = init_random.nextInt() / 32768 + 1;
262: }
263:
264: BigInteger[] qp = new BigInteger[2];
265: BigInteger q = null, Q = null, p = null;
266: BigInteger C = new BigInteger(Integer.toString(c));
267: BigInteger constA16 = new BigInteger("19381");
268:
269: //step1
270: x0 = procedure_A(x0, c, qp, 256);
271: q = qp[0];
272:
273: //step2
274: x0 = procedure_A(x0, c, qp, 512);
275: Q = qp[0];
276:
277: BigInteger[] y = new BigInteger[65];
278: y[0] = new BigInteger(Integer.toString(x0));
279:
280: int tp = 1024;
281:
282: step3: for (;;) {
283: //step 3
284: for (int j = 0; j < 64; j++) {
285: y[j + 1] = (y[j].multiply(constA16).add(C)).mod(TWO
286: .pow(16));
287: }
288:
289: //step 4
290: BigInteger Y = new BigInteger("0");
291:
292: for (int j = 0; j < 64; j++) {
293: Y = Y.add(y[j].multiply(TWO.pow(16 * j)));
294: }
295:
296: y[0] = y[64]; //step 5
297:
298: //step 6
299: BigInteger N = TWO.pow(tp - 1).divide(q.multiply(Q)).add(
300: (TWO.pow(tp - 1).multiply(Y)).divide(q.multiply(Q)
301: .multiply(TWO.pow(1024))));
302:
303: if (N.mod(TWO).compareTo(ONE) == 0) {
304: N = N.add(ONE);
305: }
306:
307: int k = 0; //step 7
308:
309: step8: for (;;) {
310: //step 11
311: p = q.multiply(Q)
312: .multiply(N.add(BigInteger.valueOf(k)))
313: .add(ONE);
314:
315: if (p.compareTo(TWO.pow(tp)) == 1) {
316: continue step3; //step 9
317: }
318:
319: //step10
320: if ((TWO.modPow(
321: q.multiply(Q).multiply(
322: N.add(BigInteger.valueOf(k))), p)
323: .compareTo(ONE) == 0)
324: && (TWO.modPow(
325: q
326: .multiply(N.add(BigInteger
327: .valueOf(k))), p)
328: .compareTo(ONE) != 0)) {
329: pq[0] = p;
330: pq[1] = q;
331: return;
332: } else {
333: k += 2;
334: continue step8;
335: }
336: }
337: }
338: }
339:
340: //Procedure B'
341: private void procedure_Bb(long x0, long c, BigInteger[] pq) {
342: //Verify and perform condition: 0<x<2^32; 0<c<2^32; c - odd.
343: while (x0 < 0 || x0 > 4294967296L) {
344: x0 = init_random.nextInt() * 2;
345: }
346:
347: while ((c < 0 || c > 4294967296L) || (c / 2 == 0)) {
348: c = init_random.nextInt() * 2 + 1;
349: }
350:
351: BigInteger[] qp = new BigInteger[2];
352: BigInteger q = null, Q = null, p = null;
353: BigInteger C = new BigInteger(Long.toString(c));
354: BigInteger constA32 = new BigInteger("97781173");
355:
356: //step1
357: x0 = procedure_Aa(x0, c, qp, 256);
358: q = qp[0];
359:
360: //step2
361: x0 = procedure_Aa(x0, c, qp, 512);
362: Q = qp[0];
363:
364: BigInteger[] y = new BigInteger[33];
365: y[0] = new BigInteger(Long.toString(x0));
366:
367: int tp = 1024;
368:
369: step3: for (;;) {
370: //step 3
371: for (int j = 0; j < 32; j++) {
372: y[j + 1] = (y[j].multiply(constA32).add(C)).mod(TWO
373: .pow(32));
374: }
375:
376: //step 4
377: BigInteger Y = new BigInteger("0");
378: for (int j = 0; j < 32; j++) {
379: Y = Y.add(y[j].multiply(TWO.pow(32 * j)));
380: }
381:
382: y[0] = y[32]; //step 5
383:
384: //step 6
385: BigInteger N = TWO.pow(tp - 1).divide(q.multiply(Q)).add(
386: (TWO.pow(tp - 1).multiply(Y)).divide(q.multiply(Q)
387: .multiply(TWO.pow(1024))));
388:
389: if (N.mod(TWO).compareTo(ONE) == 0) {
390: N = N.add(ONE);
391: }
392:
393: int k = 0; //step 7
394:
395: step8: for (;;) {
396: //step 11
397: p = q.multiply(Q)
398: .multiply(N.add(BigInteger.valueOf(k)))
399: .add(ONE);
400:
401: if (p.compareTo(TWO.pow(tp)) == 1) {
402: continue step3; //step 9
403: }
404:
405: //step10
406: if ((TWO.modPow(
407: q.multiply(Q).multiply(
408: N.add(BigInteger.valueOf(k))), p)
409: .compareTo(ONE) == 0)
410: && (TWO.modPow(
411: q
412: .multiply(N.add(BigInteger
413: .valueOf(k))), p)
414: .compareTo(ONE) != 0)) {
415: pq[0] = p;
416: pq[1] = q;
417: return;
418: } else {
419: k += 2;
420: continue step8;
421: }
422: }
423: }
424: }
425:
426: /**
427: * Procedure C
428: * procedure generates the a value from the given p,q,
429: * returning the a value.
430: */
431: private BigInteger procedure_C(BigInteger p, BigInteger q) {
432: BigInteger pSub1 = p.subtract(ONE);
433: BigInteger pSub1DivQ = pSub1.divide(q);
434: int length = p.bitLength();
435:
436: for (;;) {
437: BigInteger d = new BigInteger(length, init_random);
438:
439: // 1 < d < p-1
440: if (d.compareTo(ONE) > 0 && d.compareTo(pSub1) < 0) {
441: BigInteger a = d.modPow(pSub1DivQ, p);
442:
443: if (a.compareTo(ONE) != 0) {
444: return a;
445: }
446: }
447: }
448: }
449:
450: /**
451: * which generates the p , q and a values from the given parameters,
452: * returning the GOST3410Parameters object.
453: */
454: public GOST3410Parameters generateParameters() {
455: BigInteger[] pq = new BigInteger[2];
456: BigInteger q = null, p = null, a = null;
457:
458: int x0, c;
459: long x0L, cL;
460:
461: if (typeproc == 1) {
462: x0 = init_random.nextInt();
463: c = init_random.nextInt();
464:
465: switch (size) {
466: case 512:
467: procedure_A(x0, c, pq, 512);
468: break;
469: case 1024:
470: procedure_B(x0, c, pq);
471: break;
472: default:
473: throw new IllegalArgumentException(
474: "Ooops! key size 512 or 1024 bit.");
475: }
476: p = pq[0];
477: q = pq[1];
478: a = procedure_C(p, q);
479: //System.out.println("p:"+p.toString(16)+"\n"+"q:"+q.toString(16)+"\n"+"a:"+a.toString(16));
480: //System.out.println("p:"+p+"\n"+"q:"+q+"\n"+"a:"+a);
481: return new GOST3410Parameters(p, q, a,
482: new GOST3410ValidationParameters(x0, c));
483: } else {
484: x0L = init_random.nextLong();
485: cL = init_random.nextLong();
486:
487: switch (size) {
488: case 512:
489: procedure_Aa(x0L, cL, pq, 512);
490: break;
491: case 1024:
492: procedure_Bb(x0L, cL, pq);
493: break;
494: default:
495: throw new IllegalStateException(
496: "Ooops! key size 512 or 1024 bit.");
497: }
498: p = pq[0];
499: q = pq[1];
500: a = procedure_C(p, q);
501: //System.out.println("p:"+p.toString(16)+"\n"+"q:"+q.toString(16)+"\n"+"a:"+a.toString(16));
502: //System.out.println("p:"+p+"\n"+"q:"+q+"\n"+"a:"+a);
503: return new GOST3410Parameters(p, q, a,
504: new GOST3410ValidationParameters(x0L, cL));
505: }
506: }
507: }
|