prime.java

另一个使用java编写的加密通用算法包

        }
if (DEBUG && debuglevel >= 4) err.println();

        BigInteger[] result = {p, r, s, t};
        return result;
    }

    /**
     * Returns a Germain (Sophie) probable-prime with an approximate
     * specified <i>bitlength</i>, that is prime with a probability exceeding
     * 1 - (1/2)<sup><i>certainty</i></sup>.
     * <p>
     * An integer <i>p</i> is a GERMAIN prime iff it is a prime, and
     * <i>p</i> = 2<i>q</i> + 1 where <i>q</i> is also a prime.
     *
     * @param  bitlength    An approximate number of bits that the returned
     *                      prime integer must have.
     * @param  certainty    A measure of the probability that the returned
     *                      integer is a prime. The Miller-Rabin test used
     *                      ensures that the returned value is a prime with a
     *                      probability that exceeds 1 - (1/2)<sup><i>certainty</i></sup>.
     * @param  random       A source of randomness for the bits to use in
     *                      building the prime.
     * @return A Germain prime: a prime of the form 2q + 1 where q is also a prime.
     */
    public static BigInteger
    getGermain (int bitlength, int certainty, Random random) {
        BigInteger q, p;

if (DEBUG && debuglevel >= 3) debug("Generating a GERMAIN prime...");
if (DEBUG && debuglevel >= 4) progress("<p>");

        while (true) {
            q = new BigInteger(bitlength, certainty, random);
if (DEBUG && debuglevel >= 5) progress(".");
            p = TWO.multiply(q).add(ONE);
            if (isProbablePrimeFast(p, certainty)) break;
        }
if (DEBUG && debuglevel >= 4) err.println();

        return p;
    }

    /**
     * Generates a random probable-prime, <i>p</i>, of the given length, such that all
     * the factors of <i>p</i> - 1 are known.
     *
     * @param  bitlength    An approximate number of bits that the returned
     *                      prime integer must have.
     * @param  certainty    A measure of the probability that the returned
     *                      integer <i>p</i>, and the largest factor of <i>p</i> - 1
     *                      are primes. The Miller-Rabin test used ensures that
     *                      these values are prime with a probability that exceeds
     *                      1 - (1/2)<sup><i>certainty</i></sup>.
     * @param  random       A source of randomness for the bits to use in
     *                      building the prime.
     * @param  prime_type   what type of prime to build: PLAIN, STRONG or GERMAIN.
     * @return An array of two Objects: the first being the found prime itself,
     *         say <i>p</i>, and the second Object is an array of the known distinct
     *         prime factors of the value (<i>p</i> - 1).
     */
    public static Object[]
    getElGamal (int bitlength, int certainty, Random random, int prime_type) {
        BigInteger p = null;
        BigInteger[] q = null;

        switch (prime_type) {
          case PLAIN:
            // alternative-1: replicate what we had before
            while (q == null) {
                p = new BigInteger(bitlength, certainty, random);
                q = getSmallFactors(p.subtract(ONE), certainty);

                // if input has only small factors it is insecure (see Pohlig
                // and Hellman reference). Make sure that the last prime factor;
                // i.e. the largest, is at least half the length of the input.
                if (q != null && q[q.length - 1].bitLength() <= p.bitLength() / 2) {
if (DEBUG && debuglevel >= 5) debug("largest factor is too short");
                    q = null;
                }
            }
            break;

          case STRONG:
            // alternative-2: use GORDON-built strong primes
            BigInteger[] result;
            BigInteger r;
            while (q == null) {
                result = getGordon(bitlength, certainty, random);
                p = result[0];
                r = result[1];
                q = Prime.getSmallFactors(p.subtract(ONE), certainty, r);
            }
            break;

          case GERMAIN:
            // alternative-3: use GERMAIN primes
            p = getGermain(bitlength, certainty, random);
            q = new BigInteger[] { TWO, p.subtract(ONE).divide(TWO) };
            break;
        }

        Object[] result = {p, q};
        return result;
    }


// Factorisation methods
//...........................................................................

    /**
     * Returns a BigInteger array whose elements are the prime factors of a
     * designated BigInteger value, or null if the value could not easily be
     * factorised.
     *
     * @param  r            A BigInteger to factor.
     * @param  certainty    A measure of the probability that the largest returned
     *                      factor is a prime. The Miller-Rabin test used ensures
     *                      that this factor is a prime with a probability that
     *                      exceeds 1 - (1/2)<sup><i>certainty</i></sup>.
     * @return A BigInteger array whose elements are the distinct prime
     * factors of <i>p</i> when the latter can be written as:
     * <pre>
     *      S_1 * S_2 * ... * S_n * L
     * </pre>
     * Where S_i are small prime factors found in SMALL_PRIMES and L is a
     * large prime factor. Return null otherwise.
     */
    public static BigInteger[] getSmallFactors (BigInteger r, int certainty) {
        BigInteger[] result;
        BigInteger s;
        Vector factors = new Vector();

if (DEBUG && debuglevel >= 5) progress("factors = ");
        for (int i = 0; i < SMALL_PRIMES.length; i++) {
            s = SMALL_PRIMES[i];
            result = r.divideAndRemainder(s);
            if (result[1].equals(ZERO)) {
if (DEBUG && debuglevel >= 5) progress(s + ".");
                factors.addElement(s); // SMALL_PRIMES[i] is a factor.
                r = result[0]; // the quotient

                // it may be a factor more than once; divide out from r.
                while (true) {
                    result = r.divideAndRemainder(s);
                    if (!result[1].equals(ZERO)) break;
if (DEBUG && debuglevel >= 5) progress(s + ".");
                    r = result[0]; // the quotient
                }
            }
        }

        if (!r.equals(ONE)) {
if (DEBUG && debuglevel >= 5) progress("(" + r.bitLength() + "-bit ");
            if (!r.isProbablePrime(certainty)) { // check that r is prime.
if (DEBUG && debuglevel >= 5) err.println("composite)");
                return null;
            }
if (DEBUG && debuglevel >= 5) err.println("prime)");
            factors.addElement(r);
        } else {
if (DEBUG && debuglevel >= 5) err.println("1");
        }

        BigInteger[] z = new BigInteger[factors.size()];
        factors.copyInto(z);
        return z;
    }

    /**
     * Return a BigInteger array whose elements are the prime factors of a
     * designated BigInteger value, for which we already have one large prime
     * factor.
     * <p>
     * The returned array conatins all the distinct factors including the one
     * we gave on input. The returned array is not guaranteed to be in any
     * specific order.
     *
     * @param  r            A BigInteger to factor.
     * @param  certainty    A measure of the probability that the returned integers
     *                      are primes. The Miller-Rabin test used ensures that
     *                      each array element is a prime with a probability that
     *                      exceeds 1 - (1/2)<sup><i>certainty</i></sup>.
     * @param  q            A known prime factor of r.
     * @return If all the prime factors, except two (one of which is <i>q</i>), can
     *         be found in the list of pre-computed small primes the method returns an
     *         array whose elements are the distinct prime factors of <i>r</i>. On the
     *         other hand if not all the prime factors, except two, can be found in the
     *         list of pre-computed small primes the method returns null.
     */
    public static BigInteger[]
    getSmallFactors (BigInteger r, int certainty, BigInteger q) {
        BigInteger[] result = r.divideAndRemainder(q);
        if (!result[1].equals(ZERO)) throw new ArithmeticException(
            "q is not a factor of r");

        BigInteger t = result[0]; // the quotient
        while (true) {
            result = t.divideAndRemainder(q);
            if (!result[1].equals(ZERO)) break;
            t = result[0]; // the quotient
        }
        BigInteger s;
        Vector factors = new Vector();
if (DEBUG && debuglevel >= 5) progress("factors = (" + q.bitLength() + "-bit prime).");

        for (int i = 0; i < SMALL_PRIMES.length; i++) {
            s = SMALL_PRIMES[i];
            result = t.divideAndRemainder(s);
            if (result[1].equals(ZERO)) {
if (DEBUG && debuglevel >= 5) progress(s + ".");