biginteger.cs

JAVA实现的RSA公钥加密方法

			if(leftOver != 0)         // length not multiples of 4
				dataLength++;

			if(dataLength > maxLength || inLen > inData.Length)
				throw(new ArithmeticException("Byte overflow in constructor."));


			data = new uint[maxLength];

			for(int i = inLen - 1, j = 0; i >= 3; i -= 4, j++)
			{
				data[j] = (uint)((inData[i-3] << 24) + (inData[i-2] << 16) +
					(inData[i-1] <<  8) + inData[i]);
			}

			if(leftOver == 1)
				data[dataLength-1] = (uint)inData[0];
			else if(leftOver == 2)
				data[dataLength-1] = (uint)((inData[0] << 8) + inData[1]);
			else if(leftOver == 3)
				data[dataLength-1] = (uint)((inData[0] << 16) + (inData[1] << 8) + inData[2]);


			if(dataLength == 0)
				dataLength = 1;

			while(dataLength > 1 && data[dataLength-1] == 0)
				dataLength--;

			//Console.WriteLine("Len = " + dataLength);
		}


		//***********************************************************************
		// Constructor (Default value provided by an array of unsigned integers)
		//*********************************************************************

		public BigInteger(uint[] inData)
		{
			dataLength = inData.Length;

			if(dataLength > maxLength)
				throw(new ArithmeticException("Byte overflow in constructor."));

			data = new uint[maxLength];

			for(int i = dataLength - 1, j = 0; i >= 0; i--, j++)
				data[j] = inData[i];

			while(dataLength > 1 && data[dataLength-1] == 0)
				dataLength--;

			//Console.WriteLine("Len = " + dataLength);
		}


		//***********************************************************************
		// Overloading of the typecast operator.
		// For BigInteger bi = 10;
		//***********************************************************************

		public static implicit operator BigInteger(long value)
		{
			return (new BigInteger(value));
		}

		public static implicit operator BigInteger(ulong value)
		{
			return (new BigInteger(value));
		}

		public static implicit operator BigInteger(int value)
		{
			return (new BigInteger((long)value));
		}

		public static implicit operator BigInteger(uint value)
		{
			return (new BigInteger((ulong)value));
		}


		//***********************************************************************
		// Overloading of addition operator
		//***********************************************************************

		public static BigInteger operator +(BigInteger bi1, BigInteger bi2)
		{
			BigInteger result = new BigInteger();

			result.dataLength = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;

			long carry = 0;
			for(int i = 0; i < result.dataLength; i++)
			{
				long sum = (long)bi1.data[i] + (long)bi2.data[i] + carry;
				carry  = sum >> 32;
				result.data[i] = (uint)(sum & 0xFFFFFFFF);
			}

			if(carry != 0 && result.dataLength < maxLength)
			{
				result.data[result.dataLength] = (uint)(carry);
				result.dataLength++;
			}

			while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
				result.dataLength--;


			// overflow check
			int lastPos = maxLength - 1;
			if((bi1.data[lastPos] & 0x80000000) == (bi2.data[lastPos] & 0x80000000) &&
				(result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000))
			{
				throw (new ArithmeticException());
			}

			return result;
		}


		//***********************************************************************
		// Overloading of the unary ++ operator
		//***********************************************************************

		public static BigInteger operator ++(BigInteger bi1)
		{
			BigInteger result = new BigInteger(bi1);

			long val, carry = 1;
			int index = 0;

			while(carry != 0 && index < maxLength)
			{
				val = (long)(result.data[index]);
				val++;

				result.data[index] = (uint)(val & 0xFFFFFFFF);
				carry = val >> 32;

				index++;
			}

			if(index > result.dataLength)
				result.dataLength = index;
			else
			{
				while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
					result.dataLength--;
			}

			// overflow check
			int lastPos = maxLength - 1;

			// overflow if initial value was +ve but ++ caused a sign
			// change to negative.

			if((bi1.data[lastPos] & 0x80000000) == 0 &&
				(result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000))
			{
				throw (new ArithmeticException("Overflow in ++."));
			}
			return result;
		}


		//***********************************************************************
		// Overloading of subtraction operator
		//***********************************************************************

		public static BigInteger operator -(BigInteger bi1, BigInteger bi2)
		{
			BigInteger result = new BigInteger();

			result.dataLength = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;

			long carryIn = 0;
			for(int i = 0; i < result.dataLength; i++)
			{
				long diff;

				diff = (long)bi1.data[i] - (long)bi2.data[i] - carryIn;
				result.data[i] = (uint)(diff & 0xFFFFFFFF);

				if(diff < 0)
					carryIn = 1;
				else
					carryIn = 0;
			}

			// roll over to negative
			if(carryIn != 0)
			{
				for(int i = result.dataLength; i < maxLength; i++)
					result.data[i] = 0xFFFFFFFF;
				result.dataLength = maxLength;
			}

			// fixed in v1.03 to give correct datalength for a - (-b)
			while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
				result.dataLength--;

			// overflow check

			int lastPos = maxLength - 1;
			if((bi1.data[lastPos] & 0x80000000) != (bi2.data[lastPos] & 0x80000000) &&
				(result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000))
			{
				throw (new ArithmeticException());
			}

			return result;
		}


		//***********************************************************************
		// Overloading of the unary -- operator
		//***********************************************************************

		public static BigInteger operator --(BigInteger bi1)
		{
			BigInteger result = new BigInteger(bi1);

			long val;
			bool carryIn = true;
			int index = 0;

			while(carryIn && index < maxLength)
			{
				val = (long)(result.data[index]);
				val--;

				result.data[index] = (uint)(val & 0xFFFFFFFF);

				if(val >= 0)
					carryIn = false;

				index++;
			}

			if(index > result.dataLength)
				result.dataLength = index;

			while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
				result.dataLength--;

			// overflow check
			int lastPos = maxLength - 1;

			// overflow if initial value was -ve but -- caused a sign
			// change to positive.

			if((bi1.data[lastPos] & 0x80000000) != 0 &&
				(result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000))
			{
				throw (new ArithmeticException("Underflow in --."));
			}

			return result;
		}


		//***********************************************************************
		// Overloading of multiplication operator
		//***********************************************************************

		public static BigInteger operator *(BigInteger bi1, BigInteger bi2)
		{
			int lastPos = maxLength-1;
			bool bi1Neg = false, bi2Neg = false;

			// take the absolute value of the inputs
			try
			{
				if((bi1.data[lastPos] & 0x80000000) != 0)     // bi1 negative
				{
					bi1Neg = true; bi1 = -bi1;
				}
				if((bi2.data[lastPos] & 0x80000000) != 0)     // bi2 negative
				{
					bi2Neg = true; bi2 = -bi2;
				}
			}
			catch(Exception) {}

			BigInteger result = new BigInteger();

			// multiply the absolute values
			try
			{
				for(int i = 0; i < bi1.dataLength; i++)
				{
					if(bi1.data[i] == 0)    continue;

					ulong mcarry = 0;
					for(int j = 0, k = i; j < bi2.dataLength; j++, k++)
					{
						// k = i + j
						ulong val = ((ulong)bi1.data[i] * (ulong)bi2.data[j]) +
							(ulong)result.data[k] + mcarry;

						result.data[k] = (uint)(val & 0xFFFFFFFF);
						mcarry = (val >> 32);
					}

					if(mcarry != 0)
						result.data[i+bi2.dataLength] = (uint)mcarry;
				}
			}
			catch(Exception)
			{
				throw(new ArithmeticException("Multiplication overflow."));
			}


			result.dataLength = bi1.dataLength + bi2.dataLength;
			if(result.dataLength > maxLength)
				result.dataLength = maxLength;

			while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
				result.dataLength--;

			// overflow check (result is -ve)
			if((result.data[lastPos] & 0x80000000) != 0)
			{
				if(bi1Neg != bi2Neg && result.data[lastPos] == 0x80000000)    // different sign
				{
					// handle the special case where multiplication produces
					// a max negative number in 2's complement.

					if(result.dataLength == 1)
						return result;
					else
					{
						bool isMaxNeg = true;
						for(int i = 0; i < result.dataLength - 1 && isMaxNeg; i++)
						{
							if(result.data[i] != 0)
								isMaxNeg = false;
						}

						if(isMaxNeg)
							return result;
					}
				}

				throw(new ArithmeticException("Multiplication overflow."));
			}

			// if input has different signs, then result is -ve
			if(bi1Neg != bi2Neg)
				return -result;

			return result;
		}



		//***********************************************************************
		// Overloading of unary << operators
		//***********************************************************************

		public static BigInteger operator <<(BigInteger bi1, int shiftVal)
		{
			BigInteger result = new BigInteger(bi1);
			result.dataLength = shiftLeft(result.data, shiftVal);

			return result;
		}


		// least significant bits at lower part of buffer

		private static int shiftLeft(uint[] buffer, int shiftVal)
		{
			int shiftAmount = 32;
			int bufLen = buffer.Length;

			while(bufLen > 1 && buffer[bufLen-1] == 0)
				bufLen--;

			for(int count = shiftVal; count > 0;)
			{
				if(count < shiftAmount)
					shiftAmount = count;

				//Console.WriteLine("shiftAmount = {0}", shiftAmount);

				ulong carry = 0;
				for(int i = 0; i < bufLen; i++)
				{
					ulong val = ((ulong)buffer[i]) << shiftAmount;
					val |= carry;

					buffer[i] = (uint)(val & 0xFFFFFFFF);
					carry = val >> 32;
				}

				if(carry != 0)
				{
					if(bufLen + 1 <= buffer.Length)
					{
						buffer[bufLen] = (uint)carry;
						bufLen++;
					}
				}
				count -= shiftAmount;
			}
			return bufLen;
		}


		//***********************************************************************
		// Overloading of unary >> operators
		//***********************************************************************

		public static BigInteger operator >>(BigInteger bi1, int shiftVal)
		{
			BigInteger result = new BigInteger(bi1);
			result.dataLength = shiftRight(result.data, shiftVal);


			if((bi1.data[maxLength-1] & 0x80000000) != 0) // negative
			{
				for(int i = maxLength - 1; i >= result.dataLength; i--)
					result.data[i] = 0xFFFFFFFF;

				uint mask = 0x80000000;
				for(int i = 0; i < 32; i++)
				{
					if((result.data[result.dataLength-1] & mask) != 0)
						break;

					result.data[result.dataLength-1] |= mask;
					mask >>= 1;
				}
				result.dataLength = maxLength;
			}

			return result;
		}


		private static int shiftRight(uint[] buffer, int shiftVal)
		{
			int shiftAmount = 32;
			int invShift = 0;
			int bufLen = buffer.Length;

			while(bufLen > 1 && buffer[bufLen-1] == 0)
				bufLen--;

			//Console.WriteLine("bufLen = " + bufLen + " buffer.Length = " + buffer.Length);

			for(int count = shiftVal; count > 0;)
			{
				if(count < shiftAmount)
				{
					shiftAmount = count;
					invShift = 32 - shiftAmount;
				}

				//Console.WriteLine("shiftAmount = {0}", shiftAmount);