prime.java

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

// $Id: Prime.java,v 1.4 1997/12/15 02:55:44 hopwood Exp $
//
// $Log: Prime.java,v $
// Revision 1.4  1997/12/15 02:55:44  hopwood
// + Committed changes below.
//
// Revision 1.3.1  1997/12/15  hopwood
// + Made prime bitmap more space-efficient (by a factor of 16 in most VMs).
// + Renamed variables in the two getSmallFactors methods for consistency.
// + Moved some more of the ElGamal parameter generation code into the
//   getElGamal method of this class. Allow any of PLAIN, STRONG or GERMAIN
//   primes to be generated.
//
// Revision 1.3  1997/12/14 23:31:56  raif
// *** empty log message ***
//
// Revision 1.2.1  1997/12/15  R. Naffah
// + added isGermain() method to test if a number is a
//   Sophie Germain prime.
// + documentation.
//
// Revision 1.2  1997/12/14 17:45:26  hopwood
// + Committed changes below.
//
// Revision 1.1.1  1997/12/14  hopwood
// + Cosmetics.
// + Use cryptix.util.core.Debug for debugging.
// + Fixed bug in getSmallFactors (BigInteger p_1, int certainty,
//   BigInteger r) where r, not t was being tested for primality.
//   Unfortunately this makes parameter generation slower.
// + Added compile-time option, USE_GORDON, to determine whether Gordon's
//   algorithm will be used.
// + Added an isProbablePrimeFast method, which uses trial division on
//   primes up to SMALL_PRIME_THRESHOLD before doing Miller-Rabin.
//
// Revision 1.1  1997/12/13 22:51:15  raif
// + Added GORDON algorithm implementation for building strong
//   primes. ElGamal parameter generation is now faster.
// + Added method to find Germain primes. Although these primes
//   are not said to offer more security with large bit-length
//   primes, it's good to have a method for building them.
// + Added new method for finding all small factors of a value
//   when an already known large prime factor is known. Useful
//   for ElGamal parameter generation when the prime is built using
//   GORDON algorithm.
// + Added [HAC] reference.
// + Original version based on prime integer routines scattered
//   in RSA and ElGamal classes.
//
// $Endlog$
/*
 * Copyright (c) 1995-97 Systemics Ltd
 * on behalf of the Cryptix Development Team. All rights reserved.
 */

package cryptix.util.math;

import cryptix.CryptixException;
import cryptix.util.core.Debug;

import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Random;
import java.util.Vector;

/**
 * A utility class to handle different algorithms for large prime
 * number generation, factorisation and tests.
 * <p>
 * <b>References:</b>
 * <ol>
 *   <li> <a name="HAC">[HAC]</a>
 *        A. J. Menezes, P. C. van Oorschot, S. A. Vanstone,
 *        <a href="http://www.dms.auburn.edu/hac/">
 *        <cite>Handbook of Applied Cryptography</cite></a>
 *        CRC Press 1997, pp 145-154.
 *        <p>
 *   <li> <a href="mailto:[e-mail]">Bruce Schneier</a>,
 *        "Section 19.6 ElGamal," and "Section 11.3 Number Theory" (heading
 *        "Generators," pages 253-254),
 *        <cite>Applied Cryptography, 2nd edition</cite>,
 *        John Wiley &amp; Sons, 1996
 *        <p>
 *   <li> S. C. Pohlig and M. E. Hellman, "An Improved Algorithm for Computing
 *        Logarithms in GF(p) and Its Cryptographic Significance,"
 *        <cite>IEEE Transactions on Information Theory</cite>,
 *        v. 24 n. 1, Jan 1978, pages 106-111.
 *        <p>
 *   <li> IEEE P1363 draft standard,
 *        <a href="http://stdsbbs.ieee.org/groups/1363/index.html">
 *        http://stdsbbs.ieee.org/groups/1363/index.html</a>
 * </ol>
 * <p>
 * <b>Copyright</b> &copy; 1997
 * <a href="http://www.systemics.com/">Systemics Ltd</a> on behalf of the
 * <a href="http://www.systemics.com/docs/cryptix/">Cryptix Development Team</a>.
 * <br>All rights reserved.
 * <p>
 * <b>$Revision: 1.4 $</b>
 * @author  Raif S. Naffah
 * @author  David Hopwood
 */
public final class Prime
{
// Debugging methods and vars.
//...........................................................................

    private static final boolean DEBUG = Debug.GLOBAL_DEBUG;
    private static final int debuglevel = DEBUG ? Debug.getLevel("Prime") : 0;
    private static final PrintWriter err = DEBUG ? Debug.getOutput() : null;
    private static void debug(String s) { err.println("Prime: " + s); }
    private static void progress(String s) { err.print(s); err.flush(); }


// Constants and vars
//...........................................................................

    private static final BigInteger ZERO = BigInteger.valueOf(0L);
    private static final BigInteger ONE = BigInteger.valueOf(1L);
    private static final BigInteger TWO = BigInteger.valueOf(2L);

    public static final int PLAIN = 0;
    public static final int STRONG = 1;
    public static final int GERMAIN = 2;


// Constructor
//...........................................................................

    /** No instantiation possible. All methods are static. */
    private Prime () {}


// Prime generation methods
//...........................................................................

    /**
     * Returns a Gordon <b>strong</b> 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>
     * A prime is said to be <b>strong</b> iff integers <i>r</i>, <i>s</i>,
     * and <i>t</i> exist such that the following three conditions are
     * satisfied:
     * <ol>
     *   <li> <i>p</i> - 1 has a large prime factor, denoted <i>r</i>,
     *   <li> <i>p</i> + 1 has a large prime factor, denoted <i>s</i>, and
     *   <li> <i>r</i> - 1 has a large prime factor, denoted <i>t</i>.
     * </ol>
     * <p>
     * GORDON's algorithm is described in [HAC] p.150 as follows:
     * <ol>
     *   <li> generate 2 random primes <i>s</i> and <i>t</i> of roughly
     *        equal bit-length.
     *   <li> select an integer i0. Find the first prime in the
     *        sequence <i>2it + 1</i>, for <i>i = i0, i0+1, i0+2,...</i>
     *        Denote this prime by <i>r = 2it + 1</i>.
     *   <li> compute <i>p0 = 2(s<sup>(r-2)</sup> mod r)s - 1</i> --See errata
     *        on [HAC] web site.
     *   <li> select an integer j0. Find the first prime in the sequence
     *        <i>p0 + 2jrs</i>, for <i>j = j0, j0 + 1, j0 + 2, ...</i>
     *        Denote this prime by <i>p = p0 + 2jrs</i>.
     *   <li> return <i>p</i>.
     * </ol>
     *
     * @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 An array whose elements are respectively p, r, s and t.
     */
    public static BigInteger[]
    getGordon (int bitlength, int certainty, Random random) {
        // 1. generate 2 random primes s and t of roughly equal bitlength
        BigInteger s = new BigInteger(bitlength / 2, certainty, random);
        BigInteger t = new BigInteger(bitlength / 2, certainty, random);
            
        // 2. select an integer i0. Find the first prime in the sequence
        //    2it + 1, for i = i0, i0+1, i0+2,... Denote this prime by
        //    r = 2it + 1
        BigInteger t2 = t.multiply(TWO);
        BigInteger r = t2.add(ONE);

if (DEBUG && debuglevel >= 3) debug("Generating a strong prime (GORDON algorithm)...");
if (DEBUG && debuglevel >= 4) progress("<r>");

        while (!isProbablePrimeFast(r, certainty)) {
            r = r.add(t2);
if (DEBUG && debuglevel >= 5) progress(".");
        }
            
        // 3. compute p0 = 2(s**(r-2) mod r)s - 1.
        // See errata on [HAC] web site.
        BigInteger p0 =
            s.modPow(r.subtract(TWO), r).multiply(s).multiply(TWO).
            subtract(ONE);

        // 4. select an integer j0. Find the first prime in the sequence
        //    p0 + 2jrs, for j = j0, j0+1, j0+2,... Denote this prime by
        //    p = p0 + 2jrs
        BigInteger rs2 = r.multiply(s).multiply(TWO);
        BigInteger p = p0.add(rs2);

if (DEBUG && debuglevel >= 4) progress("<p>");
        while (!isProbablePrimeFast(p, certainty)) {
            p = p.add(rs2);
if (DEBUG && debuglevel >= 5) progress(".");