rsatools.java

非常完整的rsa加密解密软件 有多完整？自己看吧

/******************************************************
 *COPYRIGHT@author YIMINGHE , 创建日期 : 2005-12-10
 *
 *         @FUDAN UNIVERSITY
 *
 *Email : [e-mail],[e-mail]
 *
 *MSN   : [e-mail] 
 *
 *TODO
 ******************************************************/

package tool;

public class RsaTools {
	BinaryInteger test;

	public static String brandom() {
		return Math.random() > 0.5 ? "1" : "0";

	}

	public static boolean check(String num) {
		if (num.length() == 0)
			return false;
		for (int i = 0; i < num.length(); i++) {
			if (!Character.isDigit(num.charAt(i)))
				return false;
		}
		return true;
	}
}

/*
 * 引用java类库 Copyright 2004 Sun Microsystems, Inc. All rights reserved. SUN
 * PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

/*
 * @(#)BitSieve.java 1.10 03/12/19
 */

/**
 * A simple bit sieve used for finding prime number candidates. Allows setting
 * and clearing of bits in a storage array. The size of the sieve is assumed to
 * be constant to reduce overhead. All the bits of a new bitSieve are zero, and
 * bits are removed from it by setting them.
 * 
 * To reduce storage space and increase efficiency, no even numbers are
 * represented in the sieve (each bit in the sieve represents an odd number).
 * The relationship between the index of a bit and the number it represents is
 * given by N = offset + (2*index + 1); Where N is the integer represented by a
 * bit in the sieve, offset is some even integer offset indicating where the
 * sieve begins, and index is the index of a bit in the sieve array.
 * 
 * @see BinaryInteger
 * @version 1.10, 12/19/03
 * @author Michael McCloskey
 * @since 1.3
 */
class BitSieve {
	/**
	 * Stores the bits in this bitSieve.
	 */
	private long bits[];

	/**
	 * Length is how many bits this sieve holds.
	 */
	private int length;

	/**
	 * A small sieve used to filter out multiples of small primes in a search
	 * sieve.
	 */
	private static BitSieve smallSieve = new BitSieve();

	/**
	 * Construct a "small sieve" with a base of 0. This constructor is used
	 * internally to generate the set of "small primes" whose multiples are
	 * excluded from sieves generated by the main (package private) constructor,
	 * BitSieve(BinaryInteger base, int searchLen). The length of the sieve
	 * generated by this constructor was chosen for performance; it controls a
	 * tradeoff between how much time is spent constructing other sieves, and
	 * how much time is wasted testing composite candidates for primality. The
	 * length was chosen experimentally to yield good performance.
	 */
	private BitSieve() {
		length = 150 * 64;
		bits = new long[(unitIndex(length - 1) + 1)];

		// Mark 1 as composite
		set(0);
		int nextIndex = 1;
		int nextPrime = 3;

		// Find primes and remove their multiples from sieve
		do {
			sieveSingle(length, nextIndex + nextPrime, nextPrime);
			nextIndex = sieveSearch(length, nextIndex + 1);
			nextPrime = 2 * nextIndex + 1;
		} while ((nextIndex > 0) && (nextPrime < length));
	}

	/**
	 * Construct a bit sieve of searchLen bits used for finding prime number
	 * candidates. The new sieve begins at the specified base, which must be
	 * even.
	 */
	BitSieve(BinaryInteger base, int searchLen) {
		/*
		 * Candidates are indicated by clear bits in the sieve. As a candidates
		 * nonprimality is calculated, a bit is set in the sieve to eliminate
		 * it. To reduce storage space and increase efficiency, no even numbers
		 * are represented in the sieve (each bit in the sieve represents an odd
		 * number).
		 */
		bits = new long[(unitIndex(searchLen - 1) + 1)];
		length = searchLen;
		int start = 0;

		int step = smallSieve.sieveSearch(smallSieve.length, start);
		int convertedStep = (step * 2) + 1;

		// Construct the large sieve at an even offset specified by base
		MutableBigInteger r = new MutableBigInteger();
		MutableBigInteger q = new MutableBigInteger();
		do {
			// Calculate base mod convertedStep
			r.copyValue(base.mag);
			r.divideOneWord(convertedStep, q);
			start = r.value[r.offset];

			// Take each multiple of step out of sieve
			start = convertedStep - start;
			if (start % 2 == 0)
				start += convertedStep;
			sieveSingle(searchLen, (start - 1) / 2, convertedStep);

			// Find next prime from small sieve
			step = smallSieve.sieveSearch(smallSieve.length, step + 1);
			convertedStep = (step * 2) + 1;
		} while (step > 0);
	}

	/**
	 * Given a bit index return unit index containing it.
	 */
	private static int unitIndex(int bitIndex) {
		return bitIndex >>> 6;
	}

	/**
	 * Return a unit that masks the specified bit in its unit.
	 */
	private static long bit(int bitIndex) {
		return 1L << (bitIndex & ((1 << 6) - 1));
	}

	/**
	 * Get the value of the bit at the specified index.
	 */
	private boolean get(int bitIndex) {
		int unitIndex = unitIndex(bitIndex);
		return ((bits[unitIndex] & bit(bitIndex)) != 0);
	}

	/**
	 * Set the bit at the specified index.
	 */
	private void set(int bitIndex) {
		int unitIndex = unitIndex(bitIndex);
		bits[unitIndex] |= bit(bitIndex);
	}

	/**
	 * This method returns the index of the first clear bit in the search array
	 * that occurs at or after start. It will not search past the specified
	 * limit. It returns -1 if there is no such clear bit.
	 */
	private int sieveSearch(int limit, int start) {
		if (start >= limit)
			return -1;

		int index = start;
		do {
			if (!get(index))
				return index;
			index++;
		} while (index < limit - 1);
		return -1;
	}

	/**
	 * Sieve a single set of multiples out of the sieve. Begin to remove
	 * multiples of the specified step starting at the specified start index, up
	 * to the specified limit.
	 */
	private void sieveSingle(int limit, int start, int step) {
		while (start < limit) {
			set(start);
			start += step;
		}
	}

	/**
	 * Test probable primes in the sieve and return successful candidates.
	 */
	BinaryInteger retrieve(BinaryInteger initValue, int certainty) {
		// Examine the sieve one long at a time to find possible primes
		int offset = 1;
		for (int i = 0; i < bits.length; i++) {
			long nextLong = ~bits[i];
			for (int j = 0; j < 64; j++) {
				if ((nextLong & 1) == 1) {
					BinaryInteger candidate = initValue.add(BinaryInteger
							.valueOf(offset));
					if (candidate.primeToCertainty(certainty))
						return candidate;
				}
				nextLong >>>= 1;
				offset += 2;
			}
		}
		return null;
	}
}

/*
 * 引用java类库 Copyright 2004 Sun Microsystems, Inc. All rights reserved. SUN
 * PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

/*
 * @(#)MutableBigInteger.java 1.12 03/12/19
 */

/**
 * A class used to represent multiprecision integers that makes efficient use of
 * allocated space by allowing a number to occupy only part of an array so that
 * the arrays do not have to be reallocated as often. When performing an
 * operation with many iterations the array used to hold a number is only
 * reallocated when necessary and does not have to be the same size as the
 * number it represents. A mutable number allows calculations to occur on the
 * same number without having to create a new number for every step of the
 * calculation as occurs with BigIntegers.
 * 
 * @see BinaryInteger
 * @version 1.12, 12/19/03
 * @author Michael McCloskey
 * @since 1.3
 */

class MutableBigInteger {
	/**
	 * Holds the magnitude of this MutableBigInteger in big endian order. The
	 * magnitude may start at an offset into the value array, and it may end
	 * before the length of the value array.
	 */
	int[] value;

	/**
	 * The number of ints of the value array that are currently used to hold the
	 * magnitude of this MutableBigInteger. The magnitude starts at an offset
	 * and offset + intLen may be less than value.length.
	 */
	int intLen;

	/**
	 * The offset into the value array where the magnitude of this
	 * MutableBigInteger begins.
	 */
	int offset = 0;

	/**
	 * This mask is used to obtain the value of an int as if it were unsigned.
	 */
	private final static long LONG_MASK = 0xffffffffL;

	// Constructors

	/**
	 * The default constructor. An empty MutableBigInteger is created with a one
	 * word capacity.
	 */
	MutableBigInteger() {
		value = new int[1];
		intLen = 0;
	}

	/**
	 * Construct a new MutableBigInteger with a magnitude specified by the int
	 * val.
	 */
	MutableBigInteger(int val) {
		value = new int[1];
		intLen = 1;
		value[0] = val;
	}

	/**
	 * Construct a new MutableBigInteger with the specified value array up to
	 * the specified length.
	 */
	MutableBigInteger(int[] val, int len) {
		value = val;
		intLen = len;
	}

	/**
	 * Construct a new MutableBigInteger with the specified value array up to
	 * the length of the array supplied.
	 */
	MutableBigInteger(int[] val) {
		value = val;
		intLen = val.length;
	}

	/**
	 * Construct a new MutableBigInteger with a magnitude equal to the specified
	 * BinaryInteger.
	 */
	MutableBigInteger(BinaryInteger b) {
		value = (int[]) b.mag.clone();
		intLen = value.length;
	}

	/**
	 * Construct a new MutableBigInteger with a magnitude equal to the specified
	 * MutableBigInteger.
	 */
	MutableBigInteger(MutableBigInteger val) {
		intLen = val.intLen;
		value = new int[intLen];

		for (int i = 0; i < intLen; i++)
			value[i] = val.value[val.offset + i];
	}

	/**
	 * Clear out a MutableBigInteger for reuse.
	 */
	void clear() {
		offset = intLen = 0;
		for (int index = 0, n = value.length; index < n; index++)
			value[index] = 0;
	}

	/**
	 * Set a MutableBigInteger to zero, removing its offset.
	 */
	void reset() {
		offset = intLen = 0;
	}

	/**
	 * Compare the magnitude of two MutableBigIntegers. Returns -1, 0 or 1 as
	 * this MutableBigInteger is numerically less than, equal to, or greater
	 * than <tt>b</tt>.
	 */
	final int compare(MutableBigInteger b) {
		if (intLen < b.intLen)
			return -1;
		if (intLen > b.intLen)
			return 1;

		for (int i = 0; i < intLen; i++) {
			int b1 = value[offset + i] + 0x80000000;
			int b2 = b.value[b.offset + i] + 0x80000000;
			if (b1 < b2)
				return -1;
			if (b1 > b2)
				return 1;
		}
		return 0;
	}

	/**
	 * Return the index of the lowest set bit in this MutableBigInteger. If the
	 * magnitude of this MutableBigInteger is zero, -1 is returned.
	 */
	private final int getLowestSetBit() {
		if (intLen == 0)
			return -1;
		int j, b;
		for (j = intLen - 1; (j > 0) && (value[j + offset] == 0); j--)
			;
		b = value[j + offset];
		if (b == 0)
			return -1;
		return ((intLen - 1 - j) << 5) + BinaryInteger.trailingZeroCnt(b);
	}

	/**
	 * Return the int in use in this MutableBigInteger at the specified index.
	 * This method is not used because it is not inlined on all platforms.
	 */
	private final int getInt(int index) {
		return value[offset + index];
	}

	/**
	 * Return a long which is equal to the unsigned value of the int in use in
	 * this MutableBigInteger at the specified index. This method is not used
	 * because it is not inlined on all platforms.
	 */
	private final long getLong(int index) {
		return value[offset + index] & LONG_MASK;
	}

	/**
	 * Ensure that the MutableBigInteger is in normal form, specifically making
	 * sure that there are no leading zeros, and that if the magnitude is zero,
	 * then intLen is zero.
	 */
	final void normalize() {
		if (intLen == 0) {
			offset = 0;
			return;
		}

		int index = offset;
		if (value[index] != 0)
			return;

		int indexBound = index + intLen;
		do {
			index++;
		} while (index < indexBound && value[index] == 0);

		int numZeros = index - offset;
		intLen -= numZeros;
		offset = (intLen == 0 ? 0 : offset + numZeros);
	}

	/**
	 * If this MutableBigInteger cannot hold len words, increase the size of the
	 * value array to len words.
	 */
	private final void ensureCapacity(int len) {
		if (value.length < len) {
			value = new int[len];
			offset = 0;
			intLen = len;
		}
	}

	/**
	 * Convert this MutableBigInteger into an int array with no leading zeros,
	 * of a length that is equal to this MutableBigInteger's intLen.
	 */
	int[] toIntArray() {
		int[] result = new int[intLen];
		for (int i = 0; i < intLen; i++)
			result[i] = value[offset + i];
		return result;
	}

	/**
	 * Sets the int at index+offset in this MutableBigInteger to val. This does
	 * not get inlined on all platforms so it is not used as often as originally
	 * intended.
	 */
	void setInt(int index, int val) {
		value[offset + index] = val;
	}

	/**
	 * Sets this MutableBigInteger's value array to the specified array. The
	 * intLen is set to the specified length.
	 */
	void setValue(int[] val, int length) {
		value = val;
		intLen = length;
		offset = 0;
	}

	/**
	 * Sets this MutableBigInteger's value array to a copy of the specified
	 * array. The intLen is set to the length of the new array.
	 */
	void copyValue(MutableBigInteger val) {
		int len = val.intLen;
		if (value.length < len)
			value = new int[len];

		for (int i = 0; i < len; i++)
			value[i] = val.value[val.offset + i];
		intLen = len;
		offset = 0;
	}

	/**
	 * Sets this MutableBigInteger's value array to a copy of the specified
	 * array. The intLen is set to the length of the specified array.
	 */
	void copyValue(int[] val) {
		int len = val.length;
		if (value.length < len)
			value = new int[len];
		for (int i = 0; i < len; i++)
			value[i] = val[i];
		intLen = len;
		offset = 0;
	}

	/**
	 * Returns true iff this MutableBigInteger has a value of one.
	 */
	boolean isOne() {
		return (intLen == 1) && (value[offset] == 1);
	}

	/**
	 * Returns true iff this MutableBigInteger has a value of zero.
	 */
	boolean isZero() {
		return (intLen == 0);
	}

	/**
	 * Returns true iff this MutableBigInteger is even.
	 */
	boolean isEven() {
		return (intLen == 0) || ((value[offset + intLen - 1] & 1) == 0);
	}

	/**
	 * Returns true iff this MutableBigInteger is odd.
	 */
	boolean isOdd() {
		return ((value[offset + intLen - 1] & 1) == 1);
	}

	/**
	 * Returns true iff this MutableBigInteger is in normal form. A
	 * MutableBigInteger is in normal form if it has no leading zeros after the
	 * offset, and intLen + offset <= value.length.
	 */
	boolean isNormal() {
		if (intLen + offset > value.length)
			return false;
		if (intLen == 0)
			return true;
		return (value[offset] != 0);
	}

	/**
	 * Returns a String representation of this MutableBigInteger in radix 10.
	 */
	public String toString() {
		BinaryInteger b = new BinaryInteger(this, 1);
		return b.toString();
	}

	/**
	 * Right shift this MutableBigInteger n bits. The MutableBigInteger is left
	 * in normal form.
	 */
	void rightShift(int n) {
		if (intLen == 0)
			return;