1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
package org.bouncycastle.crypto.generators;
import java.math.BigInteger;
import java.security.SecureRandom;
// BEGIN android-added
import java.util.logging.Logger;
// END android-added
import org.bouncycastle.math.ec.WNafUtil;
import org.bouncycastle.util.BigIntegers;
class DHParametersHelper
{
// BEGIN android-added
private static final Logger logger = Logger.getLogger(DHParametersHelper.class.getName());
// END android-added
private static final BigInteger ONE = BigInteger.valueOf(1);
private static final BigInteger TWO = BigInteger.valueOf(2);
/*
* Finds a pair of prime BigInteger's {p, q: p = 2q + 1}
*
* (see: Handbook of Applied Cryptography 4.86)
*/
static BigInteger[] generateSafePrimes(int size, int certainty, SecureRandom random)
{
// BEGIN android-added
logger.info("Generating safe primes. This may take a long time.");
long start = System.currentTimeMillis();
int tries = 0;
// END android-added
BigInteger p, q;
int qLength = size - 1;
int minWeight = size >>> 2;
for (;;)
{
// BEGIN android-added
tries++;
// END android-added
q = new BigInteger(qLength, 2, random);
// p <- 2q + 1
p = q.shiftLeft(1).add(ONE);
if (!p.isProbablePrime(certainty))
{
continue;
}
if (certainty > 2 && !q.isProbablePrime(certainty - 2))
{
continue;
}
/*
* Require a minimum weight of the NAF representation, since low-weight primes may be
* weak against a version of the number-field-sieve for the discrete-logarithm-problem.
*
* See "The number field sieve for integers of low weight", Oliver Schirokauer.
*/
if (WNafUtil.getNafWeight(p) < minWeight)
{
continue;
}
break;
}
// BEGIN android-added
long end = System.currentTimeMillis();
long duration = end - start;
logger.info("Generated safe primes: " + tries + " tries took " + duration + "ms");
// END android-added
return new BigInteger[] { p, q };
}
/*
* Select a high order element of the multiplicative group Zp*
*
* p and q must be s.t. p = 2*q + 1, where p and q are prime (see generateSafePrimes)
*/
static BigInteger selectGenerator(BigInteger p, BigInteger q, SecureRandom random)
{
BigInteger pMinusTwo = p.subtract(TWO);
BigInteger g;
/*
* (see: Handbook of Applied Cryptography 4.80)
*/
// do
// {
// g = BigIntegers.createRandomInRange(TWO, pMinusTwo, random);
// }
// while (g.modPow(TWO, p).equals(ONE) || g.modPow(q, p).equals(ONE));
/*
* RFC 2631 2.2.1.2 (and see: Handbook of Applied Cryptography 4.81)
*/
do
{
BigInteger h = BigIntegers.createRandomInRange(TWO, pMinusTwo, random);
g = h.modPow(TWO, p);
}
while (g.equals(ONE));
return g;
}
}
|
