rsatools.java

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

		int nInts = n >>> 5;
		int nBits = n & 0x1F;
		this.intLen -= nInts;
		if (nBits == 0)
			return;
		int bitsInHighWord = BinaryInteger.bitLen(value[offset]);
		if (nBits >= bitsInHighWord) {
			this.primitiveLeftShift(32 - nBits);
			this.intLen--;
		} else {
			primitiveRightShift(nBits);
		}
	}

	/**
	 * Left shift this MutableBigInteger n bits.
	 */
	void leftShift(int n) {
		/*
		 * If there is enough storage space in this MutableBigInteger already
		 * the available space will be used. Space to the right of the used ints
		 * in the value array is faster to utilize, so the extra space will be
		 * taken from the right if possible.
		 */
		if (intLen == 0)
			return;
		int nInts = n >>> 5;
		int nBits = n & 0x1F;
		int bitsInHighWord = BinaryInteger.bitLen(value[offset]);

		// If shift can be done without moving words, do so
		if (n <= (32 - bitsInHighWord)) {
			primitiveLeftShift(nBits);
			return;
		}

		int newLen = intLen + nInts + 1;
		if (nBits <= (32 - bitsInHighWord))
			newLen--;
		if (value.length < newLen) {
			// The array must grow
			int[] result = new int[newLen];
			for (int i = 0; i < intLen; i++)
				result[i] = value[offset + i];
			setValue(result, newLen);
		} else if (value.length - offset >= newLen) {
			// Use space on right
			for (int i = 0; i < newLen - intLen; i++)
				value[offset + intLen + i] = 0;
		} else {
			// Must use space on left
			for (int i = 0; i < intLen; i++)
				value[i] = value[offset + i];
			for (int i = intLen; i < newLen; i++)
				value[i] = 0;
			offset = 0;
		}
		intLen = newLen;
		if (nBits == 0)
			return;
		if (nBits <= (32 - bitsInHighWord))
			primitiveLeftShift(nBits);
		else
			primitiveRightShift(32 - nBits);
	}

	/**
	 * A primitive used for division. This method adds in one multiple of the
	 * divisor a back to the dividend result at a specified offset. It is used
	 * when qhat was estimated too large, and must be adjusted.
	 */
	private int divadd(int[] a, int[] result, int offset) {
		long carry = 0;

		for (int j = a.length - 1; j >= 0; j--) {
			long sum = (a[j] & LONG_MASK) + (result[j + offset] & LONG_MASK)
					+ carry;
			result[j + offset] = (int) sum;
			carry = sum >>> 32;
		}
		return (int) carry;
	}

	/**
	 * This method is used for division. It multiplies an n word input a by one
	 * word input x, and subtracts the n word product from q. This is needed
	 * when subtracting qhat*divisor from dividend.
	 */
	private int mulsub(int[] q, int[] a, int x, int len, int offset) {
		long xLong = x & LONG_MASK;
		long carry = 0;
		offset += len;

		for (int j = len - 1; j >= 0; j--) {
			long product = (a[j] & LONG_MASK) * xLong + carry;
			long difference = q[offset] - product;
			q[offset--] = (int) difference;
			carry = (product >>> 32)
					+ (((difference & LONG_MASK) > (((~(int) product) & LONG_MASK))) ? 1
							: 0);
		}
		return (int) carry;
	}

	/**
	 * Right shift this MutableBigInteger n bits, where n is less than 32.
	 * Assumes that intLen > 0, n > 0 for speed
	 */
	private final void primitiveRightShift(int n) {
		int[] val = value;
		int n2 = 32 - n;
		for (int i = offset + intLen - 1, c = val[i]; i > offset; i--) {
			int b = c;
			c = val[i - 1];
			val[i] = (c << n2) | (b >>> n);
		}
		val[offset] >>>= n;
	}

	/**
	 * Left shift this MutableBigInteger n bits, where n is less than 32.
	 * Assumes that intLen > 0, n > 0 for speed
	 */
	private final void primitiveLeftShift(int n) {
		int[] val = value;
		int n2 = 32 - n;
		for (int i = offset, c = val[i], m = i + intLen - 1; i < m; i++) {
			int b = c;
			c = val[i + 1];
			val[i] = (b << n) | (c >>> n2);
		}
		val[offset + intLen - 1] <<= n;
	}

	/**
	 * Adds the contents of two MutableBigInteger objects.The result is placed
	 * within this MutableBigInteger. The contents of the addend are not
	 * changed.
	 */
	void add(MutableBigInteger addend) {
		int x = intLen;
		int y = addend.intLen;
		int resultLen = (intLen > addend.intLen ? intLen : addend.intLen);
		int[] result = (value.length < resultLen ? new int[resultLen] : value);

		int rstart = result.length - 1;
		long sum = 0;

		// Add common parts of both numbers
		while (x > 0 && y > 0) {
			x--;
			y--;
			sum = (value[x + offset] & LONG_MASK)
					+ (addend.value[y + addend.offset] & LONG_MASK)
					+ (sum >>> 32);
			result[rstart--] = (int) sum;
		}

		// Add remainder of the longer number
		while (x > 0) {
			x--;
			sum = (value[x + offset] & LONG_MASK) + (sum >>> 32);
			result[rstart--] = (int) sum;
		}
		while (y > 0) {
			y--;
			sum = (addend.value[y + addend.offset] & LONG_MASK) + (sum >>> 32);
			result[rstart--] = (int) sum;
		}

		if ((sum >>> 32) > 0) { // Result must grow in length
			resultLen++;
			if (result.length < resultLen) {
				int temp[] = new int[resultLen];
				for (int i = resultLen - 1; i > 0; i--)
					temp[i] = result[i - 1];
				temp[0] = 1;
				result = temp;
			} else {
				result[rstart--] = 1;
			}
		}

		value = result;
		intLen = resultLen;
		offset = result.length - resultLen;
	}

	/**
	 * Subtracts the smaller of this and b from the larger and places the result
	 * into this MutableBigInteger.
	 */
	int subtract(MutableBigInteger b) {
		MutableBigInteger a = this;

		int[] result = value;
		int sign = a.compare(b);

		if (sign == 0) {
			reset();
			return 0;
		}
		if (sign < 0) {
			MutableBigInteger tmp = a;
			a = b;
			b = tmp;
		}

		int resultLen = a.intLen;
		if (result.length < resultLen)
			result = new int[resultLen];

		long diff = 0;
		int x = a.intLen;
		int y = b.intLen;
		int rstart = result.length - 1;

		// Subtract common parts of both numbers
		while (y > 0) {
			x--;
			y--;

			diff = (a.value[x + a.offset] & LONG_MASK)
					- (b.value[y + b.offset] & LONG_MASK)
					- ((int) -(diff >> 32));
			result[rstart--] = (int) diff;
		}
		// Subtract remainder of longer number
		while (x > 0) {
			x--;
			diff = (a.value[x + a.offset] & LONG_MASK) - ((int) -(diff >> 32));
			result[rstart--] = (int) diff;
		}

		value = result;
		intLen = resultLen;
		offset = value.length - resultLen;
		normalize();
		return sign;
	}

	/**
	 * Subtracts the smaller of a and b from the larger and places the result
	 * into the larger. Returns 1 if the answer is in a, -1 if in b, 0 if no
	 * operation was performed.
	 */
	private int difference(MutableBigInteger b) {
		MutableBigInteger a = this;
		int sign = a.compare(b);
		if (sign == 0)
			return 0;
		if (sign < 0) {
			MutableBigInteger tmp = a;
			a = b;
			b = tmp;
		}

		long diff = 0;
		int x = a.intLen;
		int y = b.intLen;

		// Subtract common parts of both numbers
		while (y > 0) {
			x--;
			y--;
			diff = (a.value[a.offset + x] & LONG_MASK)
					- (b.value[b.offset + y] & LONG_MASK)
					- ((int) -(diff >> 32));
			a.value[a.offset + x] = (int) diff;
		}
		// Subtract remainder of longer number
		while (x > 0) {
			x--;
			diff = (a.value[a.offset + x] & LONG_MASK) - ((int) -(diff >> 32));
			a.value[a.offset + x] = (int) diff;
		}

		a.normalize();
		return sign;
	}

	/**
	 * Multiply the contents of two MutableBigInteger objects. The result is
	 * placed into MutableBigInteger z. The contents of y are not changed.
	 */
	void multiply(MutableBigInteger y, MutableBigInteger z) {
		int xLen = intLen;
		int yLen = y.intLen;
		int newLen = xLen + yLen;

		// Put z into an appropriate state to receive product
		if (z.value.length < newLen)
			z.value = new int[newLen];
		z.offset = 0;
		z.intLen = newLen;

		// The first iteration is hoisted out of the loop to avoid extra add
		long carry = 0;
		for (int j = yLen - 1, k = yLen + xLen - 1; j >= 0; j--, k--) {
			long product = (y.value[j + y.offset] & LONG_MASK)
					* (value[xLen - 1 + offset] & LONG_MASK) + carry;
			z.value[k] = (int) product;
			carry = product >>> 32;
		}
		z.value[xLen - 1] = (int) carry;

		// Perform the multiplication word by word
		for (int i = xLen - 2; i >= 0; i--) {
			carry = 0;
			for (int j = yLen - 1, k = yLen + i; j >= 0; j--, k--) {
				long product = (y.value[j + y.offset] & LONG_MASK)
						* (value[i + offset] & LONG_MASK)
						+ (z.value[k] & LONG_MASK) + carry;
				z.value[k] = (int) product;
				carry = product >>> 32;
			}
			z.value[i] = (int) carry;
		}

		// Remove leading zeros from product
		z.normalize();
	}

	/**
	 * Multiply the contents of this MutableBigInteger by the word y. The result
	 * is placed into z.
	 */
	void mul(int y, MutableBigInteger z) {
		if (y == 1) {
			z.copyValue(this);
			return;
		}

		if (y == 0) {
			z.clear();
			return;
		}

		// Perform the multiplication word by word
		long ylong = y & LONG_MASK;
		int[] zval = (z.value.length < intLen + 1 ? new int[intLen + 1]
				: z.value);
		long carry = 0;
		for (int i = intLen - 1; i >= 0; i--) {
			long product = ylong * (value[i + offset] & LONG_MASK) + carry;
			zval[i + 1] = (int) product;
			carry = product >>> 32;
		}

		if (carry == 0) {
			z.offset = 1;
			z.intLen = intLen;
		} else {
			z.offset = 0;
			z.intLen = intLen + 1;
			zval[0] = (int) carry;
		}
		z.value = zval;
	}

	/**
	 * This method is used for division of an n word dividend by a one word
	 * divisor. The quotient is placed into quotient. The one word divisor is
	 * specified by divisor. The value of this MutableBigInteger is the dividend
	 * at invocation but is replaced by the remainder.
	 * 
	 * NOTE: The value of this MutableBigInteger is modified by this method.
	 */
	void divideOneWord(int divisor, MutableBigInteger quotient) {
		long divLong = divisor & LONG_MASK;

		// Special case of one word dividend
		if (intLen == 1) {
			long remValue = value[offset] & LONG_MASK;
			quotient.value[0] = (int) (remValue / divLong);
			quotient.intLen = (quotient.value[0] == 0) ? 0 : 1;
			quotient.offset = 0;

			value[0] = (int) (remValue - (quotient.value[0] * divLong));
			offset = 0;
			intLen = (value[0] == 0) ? 0 : 1;

			return;
		}

		if (quotient.value.length < intLen)
			quotient.value = new int[intLen];
		quotient.offset = 0;
		quotient.intLen = intLen;

		// Normalize the divisor
		int shift = 32 - BinaryInteger.bitLen(divisor);

		int rem = value[offset];
		long remLong = rem & LONG_MASK;
		if (remLong < divLong) {
			quotient.value[0] = 0;
		} else {
			quotient.value[0] = (int) (remLong / divLong);
			rem = (int) (remLong - (quotient.value[0] * divLong));
			remLong = rem & LONG_MASK;
		}

		int xlen = intLen;
		int[] qWord = new int[2];
		while (--xlen > 0) {
			long dividendEstimate = (remLong << 32)
					| (value[offset + intLen - xlen] & LONG_MASK);
			if (dividendEstimate >= 0) {
				qWord[0] = (int) (dividendEstimate / divLong);
				qWord[1] = (int) (dividendEstimate - (qWord[0] * divLong));
			} else {
				divWord(qWord, dividendEstimate, divisor);
			}
			quotient.value[intLen - xlen] = (int) qWord[0];
			rem = (int) qWord[1];
			remLong = rem & LONG_MASK;
		}

		// Unnormalize
		if (shift > 0)
			value[0] = rem %= divisor;
		else
			value[0] = rem;
		intLen = (value[0] == 0) ? 0 : 1;

		quotient.normalize();
	}

	/**
	 * Calculates the quotient and remainder of this div b and places them in
	 * the MutableBigInteger objects provided.
	 * 
	 * Uses Algorithm D in Knuth section 4.3.1. Many optimizations to that
	 * algorithm have been adapted from the Colin Plumb C library. It special
	 * cases one word divisors for speed. The contents of a and b are not
	 * changed.
	 * 
	 */
	void divide(MutableBigInteger b, MutableBigInteger quotient,
			MutableBigInteger rem) {
		if (b.intLen == 0)
			throw new ArithmeticException("BinaryInteger divide by zero");

		// Dividend is zero
		if (intLen == 0) {
			quotient.intLen = quotient.offset = rem.intLen = rem.offset = 0;
			return;
		}

		int cmp = compare(b);

		// Dividend less than divisor
		if (cmp < 0) {
			quotient.intLen = quotient.offset = 0;
			rem.copyValue(this);
			return;
		}
		// Dividend equal to divisor
		if (cmp == 0) {
			quotient.value[0] = quotient.intLen = 1;
			quotient.offset = rem.intLen = rem.offset = 0;
			return;
		}

		quotient.clear();

		// Special case one word divisor
		if (b.intLen == 1) {
			rem.copyValue(this);
			rem.divideOneWord(b.value[b.offset], quotient);
			return;
		}

		// Copy divisor value to protect divisor
		int[] d = new int[b.intLen];
		for (int i = 0; i < b.intLen; i++)
			d[i] = b.value[b.offset + i];
		int dlen = b.intLen;

		// Remainder starts as dividend with space for a leading zero
		if (rem.value.length < intLen + 1)
			rem.value = new int[intLen + 1];

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

		int nlen = rem.intLen;

		// Set the quotient size
		int limit = nlen - dlen + 1;
		if (quotient.value.length < limit) {
			quotient.value = new int[limit];
			quotient.offset = 0;
		}
		quotient.intLen = limit;
		int[] q = quotient.value;

		// D1 normalize the divisor
		int shift = 32 - BinaryInteger.bitLen(d[0]);
		if (shift > 0) {
			// First shift will not grow array
			BinaryInteger.primitiveLeftShift(d, dlen, shift);
			// But this one might
			rem.leftShift(shift);
		}

		// Must insert leading 0 in rem if its length did not change
		if (rem.intLen == nlen) {
			rem.offset = 0;
			rem.value[0] = 0;
			rem.intLen++;
		}

		int dh = d[0];
		long dhLong = dh & LONG_MASK;
		int dl = d[1];
		int[] qWord = new int[2];

		// D2 Initialize j
		for (int j = 0; j < limit; j++) {
			// D3 Calculate qhat
			// estimate qhat
			int qhat = 0;
			int qrem = 0;
			boolean skipCorrection = false;
			int nh = rem.value[j + rem.offset];
			int nh2 = nh + 0x80000000;
			int nm = rem.value[j + 1 + rem.offset];

			if (nh == dh) {
				qhat = ~0;
				qrem = nh + nm;
				skipCorrection = qrem + 0x80000000 < nh2;
			} else {
				long nChunk = (((long) nh) << 32) | (nm & LONG_MASK);
				if (nChunk >= 0) {
					qhat = (int) (nChunk / dhLong);
					qrem = (int) (nChunk - (qhat * dhLong));
				} else {
					divWord(qWord, nChunk, dh);
					qhat = qWord[0];
					qrem = qWord[1];
				}
			}

			if (qhat == 0)
				continue;

			if (!skipCorrection) { // Correct qhat
				long nl = rem.value[j + 2 + rem.offset] & LONG_MASK;
				long rs = ((qrem & LONG_MASK) << 32) | nl;
				long estProduct = (dl & LONG_MASK) * (qhat & LONG_MASK);

				if (unsignedLongCompare(estProduct, rs)) {
					qhat--;
					qrem = (int) ((qrem & LONG_MASK) + dhLong);
					if ((qrem & LONG_MASK) >= dhLong) {
						estProduct = (dl & LONG_MASK) * (qhat & LONG_MASK);
						rs = ((qrem & LONG_MASK) << 32) | nl;