biginteger.cs

JAVA实现的RSA公钥加密方法

				ulong carry = 0;
				for(int i = bufLen - 1; i >= 0; i--)
				{
					ulong val = ((ulong)buffer[i]) >> shiftAmount;
					val |= carry;

					carry = ((ulong)buffer[i]) << invShift;
					buffer[i] = (uint)(val);
				}

				count -= shiftAmount;
			}

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

			return bufLen;
		}


		//***********************************************************************
		// Overloading of the NOT operator (1's complement)
		//***********************************************************************

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

			for(int i = 0; i < maxLength; i++)
				result.data[i] = (uint)(~(bi1.data[i]));

			result.dataLength = maxLength;

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

			return result;
		}


		//***********************************************************************
		// Overloading of the NEGATE operator (2's complement)
		//***********************************************************************

		public static BigInteger operator -(BigInteger bi1)
		{
			// handle neg of zero separately since it'll cause an overflow
			// if we proceed.

			if(bi1.dataLength == 1 && bi1.data[0] == 0)
				return (new BigInteger());

			BigInteger result = new BigInteger(bi1);

			// 1's complement
			for(int i = 0; i < maxLength; i++)
				result.data[i] = (uint)(~(bi1.data[i]));

			// add one to result of 1's complement
			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((bi1.data[maxLength-1] & 0x80000000) == (result.data[maxLength-1] & 0x80000000))
				throw (new ArithmeticException("Overflow in negation.\n"));

			result.dataLength = maxLength;

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


		//***********************************************************************
		// Overloading of equality operator
		//***********************************************************************

		public static bool operator ==(BigInteger bi1, BigInteger bi2)
		{
			return bi1.Equals(bi2);
		}


		public static bool operator !=(BigInteger bi1, BigInteger bi2)
		{
			return !(bi1.Equals(bi2));
		}


		public override bool Equals(object o)
		{
			BigInteger bi = (BigInteger)o;

			if(this.dataLength != bi.dataLength)
				return false;

			for(int i = 0; i < this.dataLength; i++)
			{
				if(this.data[i] != bi.data[i])
					return false;
			}
			return true;
		}


		public override int GetHashCode()
		{
			return this.ToString().GetHashCode();
		}


		//***********************************************************************
		// Overloading of inequality operator
		//***********************************************************************

		public static bool operator >(BigInteger bi1, BigInteger bi2)
		{
			int pos = maxLength - 1;

			// bi1 is negative, bi2 is positive
			if((bi1.data[pos] & 0x80000000) != 0 && (bi2.data[pos] & 0x80000000) == 0)
				return false;

				// bi1 is positive, bi2 is negative
			else if((bi1.data[pos] & 0x80000000) == 0 && (bi2.data[pos] & 0x80000000) != 0)
				return true;

			// same sign
			int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
			for(pos = len - 1; pos >= 0 && bi1.data[pos] == bi2.data[pos]; pos--);

			if(pos >= 0)
			{
				if(bi1.data[pos] > bi2.data[pos])
					return true;
				return false;
			}
			return false;
		}


		public static bool operator <(BigInteger bi1, BigInteger bi2)
		{
			int pos = maxLength - 1;

			// bi1 is negative, bi2 is positive
			if((bi1.data[pos] & 0x80000000) != 0 && (bi2.data[pos] & 0x80000000) == 0)
				return true;

				// bi1 is positive, bi2 is negative
			else if((bi1.data[pos] & 0x80000000) == 0 && (bi2.data[pos] & 0x80000000) != 0)
				return false;

			// same sign
			int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
			for(pos = len - 1; pos >= 0 && bi1.data[pos] == bi2.data[pos]; pos--);

			if(pos >= 0)
			{
				if(bi1.data[pos] < bi2.data[pos])
					return true;
				return false;
			}
			return false;
		}


		public static bool operator >=(BigInteger bi1, BigInteger bi2)
		{
			return (bi1 == bi2 || bi1 > bi2);
		}


		public static bool operator <=(BigInteger bi1, BigInteger bi2)
		{
			return (bi1 == bi2 || bi1 < bi2);
		}


		//***********************************************************************
		// Private function that supports the division of two numbers with
		// a divisor that has more than 1 digit.
		//
		// Algorithm taken from [1]
		//***********************************************************************

		private static void multiByteDivide(BigInteger bi1, BigInteger bi2,
			BigInteger outQuotient, BigInteger outRemainder)
		{
			uint[] result = new uint[maxLength];

			int remainderLen = bi1.dataLength + 1;
			uint[] remainder = new uint[remainderLen];

			uint mask = 0x80000000;
			uint val = bi2.data[bi2.dataLength - 1];
			int shift = 0, resultPos = 0;

			while(mask != 0 && (val & mask) == 0)
			{
				shift++; mask >>= 1;
			}

			//Console.WriteLine("shift = {0}", shift);
			//Console.WriteLine("Before bi1 Len = {0}, bi2 Len = {1}", bi1.dataLength, bi2.dataLength);

			for(int i = 0; i < bi1.dataLength; i++)
				remainder[i] = bi1.data[i];
			shiftLeft(remainder, shift);
			bi2 = bi2 << shift;

			/*
				Console.WriteLine("bi1 Len = {0}, bi2 Len = {1}", bi1.dataLength, bi2.dataLength);
				Console.WriteLine("dividend = " + bi1 + "\ndivisor = " + bi2);
				for(int q = remainderLen - 1; q >= 0; q--)
						Console.Write("{0:x2}", remainder[q]);
				Console.WriteLine();
				*/

			int j = remainderLen - bi2.dataLength;
			int pos = remainderLen - 1;

			ulong firstDivisorByte = bi2.data[bi2.dataLength-1];
			ulong secondDivisorByte = bi2.data[bi2.dataLength-2];

			int divisorLen = bi2.dataLength + 1;
			uint[] dividendPart = new uint[divisorLen];

			while(j > 0)
			{
				ulong dividend = ((ulong)remainder[pos] << 32) + (ulong)remainder[pos-1];
				//Console.WriteLine("dividend = {0}", dividend);

				ulong q_hat = dividend / firstDivisorByte;
				ulong r_hat = dividend % firstDivisorByte;

				//Console.WriteLine("q_hat = {0:X}, r_hat = {1:X}", q_hat, r_hat);

				bool done = false;
				while(!done)
				{
					done = true;

					if(q_hat == 0x100000000 ||
						(q_hat * secondDivisorByte) > ((r_hat << 32) + remainder[pos-2]))
					{
						q_hat--;
						r_hat += firstDivisorByte;

						if(r_hat < 0x100000000)
							done = false;
					}
				}

				for(int h = 0; h < divisorLen; h++)
					dividendPart[h] = remainder[pos-h];

				BigInteger kk = new BigInteger(dividendPart);
				BigInteger ss = bi2 * (long)q_hat;

				//Console.WriteLine("ss before = " + ss);
				while(ss > kk)
				{
					q_hat--;
					ss -= bi2;
					//Console.WriteLine(ss);
				}
				BigInteger yy = kk - ss;

				//Console.WriteLine("ss = " + ss);
				//Console.WriteLine("kk = " + kk);
				//Console.WriteLine("yy = " + yy);

				for(int h = 0; h < divisorLen; h++)
					remainder[pos-h] = yy.data[bi2.dataLength-h];

				/*
						Console.WriteLine("dividend = ");
						for(int q = remainderLen - 1; q >= 0; q--)
								Console.Write("{0:x2}", remainder[q]);
						Console.WriteLine("\n************ q_hat = {0:X}\n", q_hat);
						*/

				result[resultPos++] = (uint)q_hat;

				pos--;
				j--;
			}

			outQuotient.dataLength = resultPos;
			int y = 0;
			for(int x = outQuotient.dataLength - 1; x >= 0; x--, y++)
				outQuotient.data[y] = result[x];
			for(; y < maxLength; y++)
				outQuotient.data[y] = 0;

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

			if(outQuotient.dataLength == 0)
				outQuotient.dataLength = 1;

			outRemainder.dataLength = shiftRight(remainder, shift);

			for(y = 0; y < outRemainder.dataLength; y++)
				outRemainder.data[y] = remainder[y];
			for(; y < maxLength; y++)
				outRemainder.data[y] = 0;
		}


		//***********************************************************************
		// Private function that supports the division of two numbers with
		// a divisor that has only 1 digit.
		//***********************************************************************

		private static void singleByteDivide(BigInteger bi1, BigInteger bi2,
			BigInteger outQuotient, BigInteger outRemainder)
		{
			uint[] result = new uint[maxLength];
			int resultPos = 0;

			// copy dividend to reminder
			for(int i = 0; i < maxLength; i++)
				outRemainder.data[i] = bi1.data[i];
			outRemainder.dataLength = bi1.dataLength;

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

			ulong divisor = (ulong)bi2.data[0];
			int pos = outRemainder.dataLength - 1;
			ulong dividend = (ulong)outRemainder.data[pos];

			//Console.WriteLine("divisor = " + divisor + " dividend = " + dividend);
			//Console.WriteLine("divisor = " + bi2 + "\ndividend = " + bi1);

			if(dividend >= divisor)
			{
				ulong quotient = dividend / divisor;
				result[resultPos++] = (uint)quotient;

				outRemainder.data[pos] = (uint)(dividend % divisor);
			}
			pos--;

			while(pos >= 0)
			{
				//Console.WriteLine(pos);

				dividend = ((ulong)outRemainder.data[pos+1] << 32) + (ulong)outRemainder.data[pos];
				ulong quotient = dividend / divisor;
				result[resultPos++] = (uint)quotient;

				outRemainder.data[pos+1] = 0;
				outRemainder.data[pos--] = (uint)(dividend % divisor);
				//Console.WriteLine(">>>> " + bi1);
			}

			outQuotient.dataLength = resultPos;
			int j = 0;
			for(int i = outQuotient.dataLength - 1; i >= 0; i--, j++)
				outQuotient.data[j] = result[i];
			for(; j < maxLength; j++)
				outQuotient.data[j] = 0;

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

			if(outQuotient.dataLength == 0)
				outQuotient.dataLength = 1;

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


		//***********************************************************************
		// Overloading of division operator
		//***********************************************************************

		public static BigInteger operator /(BigInteger bi1, BigInteger bi2)
		{
			BigInteger quotient = new BigInteger();
			BigInteger remainder = new BigInteger();

			int lastPos = maxLength-1;
			bool divisorNeg = false, dividendNeg = false;

			if((bi1.data[lastPos] & 0x80000000) != 0)     // bi1 negative
			{
				bi1 = -bi1;
				dividendNeg = true;
			}
			if((bi2.data[lastPos] & 0x80000000) != 0)     // bi2 negative
			{
				bi2 = -bi2;
				divisorNeg = true;
			}

			if(bi1 < bi2)
			{
				return quotient;
			}

			else
			{
				if(bi2.dataLength == 1)
					singleByteDivide(bi1, bi2, quotient, remainder);
				else
					multiByteDivide(bi1, bi2, quotient, remainder);

				if(dividendNeg != divisorNeg)
					return -quotient;

				return quotient;
			}
		}


		//***********************************************************************
		// Overloading of modulus operator
		//***********************************************************************

		public static BigInteger operator %(BigInteger bi1, BigInteger bi2)
		{
			BigInteger quotient = new BigInteger();
			BigInteger remainder = new BigInteger(bi1);

			int lastPos = maxLength-1;
			bool dividendNeg = false;

			if((bi1.data[lastPos] & 0x80000000) != 0)     // bi1 negative
			{
				bi1 = -bi1;
				dividendNeg = true;
			}
			if((bi2.data[lastPos] & 0x80000000) != 0)     // bi2 negative
				bi2 = -bi2;

			if(bi1 < bi2)
			{
				return remainder;
			}

			else
			{
				if(bi2.dataLength == 1)
					singleByteDivide(bi1, bi2, quotient, remainder);
				else
					multiByteDivide(bi1, bi2, quotient, remainder);