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