biginteger.cs

JAVA实现的RSA公钥加密方法

				if(dividendNeg)
					return -remainder;

				return remainder;
			}
		}


		//***********************************************************************
		// Overloading of bitwise AND operator
		//***********************************************************************

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

			int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;

			for(int i = 0; i < len; i++)
			{
				uint sum = (uint)(bi1.data[i] & bi2.data[i]);
				result.data[i] = sum;
			}

			result.dataLength = maxLength;

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

			return result;
		}


		//***********************************************************************
		// Overloading of bitwise OR operator
		//***********************************************************************

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

			int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;

			for(int i = 0; i < len; i++)
			{
				uint sum = (uint)(bi1.data[i] | bi2.data[i]);
				result.data[i] = sum;
			}

			result.dataLength = maxLength;

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

			return result;
		}


		//***********************************************************************
		// Overloading of bitwise XOR operator
		//***********************************************************************

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

			int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;

			for(int i = 0; i < len; i++)
			{
				uint sum = (uint)(bi1.data[i] ^ bi2.data[i]);
				result.data[i] = sum;
			}

			result.dataLength = maxLength;

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

			return result;
		}


		//***********************************************************************
		// Returns max(this, bi)
		//***********************************************************************

		public BigInteger max(BigInteger bi)
		{
			if(this > bi)
				return (new BigInteger(this));
			else
				return (new BigInteger(bi));
		}


		//***********************************************************************
		// Returns min(this, bi)
		//***********************************************************************

		public BigInteger min(BigInteger bi)
		{
			if(this < bi)
				return (new BigInteger(this));
			else
				return (new BigInteger(bi));

		}


		//***********************************************************************
		// Returns the absolute value
		//***********************************************************************

		public BigInteger abs()
		{
			if((this.data[maxLength - 1] & 0x80000000) != 0)
				return (-this);
			else
				return (new BigInteger(this));
		}


		//***********************************************************************
		// Returns a string representing the BigInteger in base 10.
		//***********************************************************************

		public override string ToString()
		{
			return ToString(10);
		}


		//***********************************************************************
		// Returns a string representing the BigInteger in sign-and-magnitude
		// format in the specified radix.
		//
		// Example
		// -------
		// If the value of BigInteger is -255 in base 10, then
		// ToString(16) returns "-FF"
		//
		//***********************************************************************

		public string ToString(int radix)
		{
			// if(radix < 2 || radix > 36)
			// throw (new ArgumentException("Radix must be >= 2 and <= 36"));
			//
			// string charSet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

			if(radix < 2 || radix > 95)
				throw (new ArgumentException("Radix must be >= 2 and <= 95"));

			string charSet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_=!@#$%^&*()[]{}|;:,.<>/?`~ \\\'\"+-";
			string result = "";

			BigInteger a = this;

			bool negative = false;
			if((a.data[maxLength-1] & 0x80000000) != 0)
			{
				negative = true;
				try
				{
					a = -a;
				}
				catch(Exception) {}
			}

			BigInteger quotient = new BigInteger();
			BigInteger remainder = new BigInteger();
			BigInteger biRadix = new BigInteger(radix);

			if(a.dataLength == 1 && a.data[0] == 0)
				result = "0";
			else
			{
				while(a.dataLength > 1 || (a.dataLength == 1 && a.data[0] != 0))
				{
					singleByteDivide(a, biRadix, quotient, remainder);

					// if(remainder.data[0] < 10)
					// result = remainder.data[0] + result;
					// else
					// result = charSet[(int)remainder.data[0] - 10] + result;

					result = charSet[(int)remainder.data[0]] + result;

					a = quotient;
				}
				if(negative)
					result = "-" + result;
			}

			return result;
		}



		//***********************************************************************
		// Returns a hex string showing the contains of the BigInteger
		//
		// Examples
		// -------
		// 1) If the value of BigInteger is 255 in base 10, then
		//    ToHexString() returns "FF"
		//
		// 2) If the value of BigInteger is -255 in base 10, then
		//    ToHexString() returns ".....FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF01",
		//    which is the 2's complement representation of -255.
		//
		//***********************************************************************

		public string ToHexString()
		{
			string result = data[dataLength - 1].ToString("X");

			for(int i = dataLength - 2; i >= 0; i--)
			{
				result += data[i].ToString("X8");
			}

			return result;
		}



		//***********************************************************************
		// Modulo Exponentiation
		//***********************************************************************

		public BigInteger modPow(BigInteger exp, BigInteger n)
		{
			if((exp.data[maxLength-1] & 0x80000000) != 0)
				throw (new ArithmeticException("Positive exponents only."));

			BigInteger resultNum = 1;
			BigInteger tempNum;
			bool thisNegative = false;

			if((this.data[maxLength-1] & 0x80000000) != 0)   // negative this
			{
				tempNum = -this % n;
				thisNegative = true;
			}
			else
				tempNum = this % n;  // ensures (tempNum * tempNum) < b^(2k)

			if((n.data[maxLength-1] & 0x80000000) != 0)   // negative n
				n = -n;

			// calculate constant = b^(2k) / m
			BigInteger constant = new BigInteger();

			int i = n.dataLength << 1;
			constant.data[i] = 0x00000001;
			constant.dataLength = i + 1;

			constant = constant / n;
			int totalBits = exp.bitCount();
			int count = 0;

			// perform squaring and multiply exponentiation
			for(int pos = 0; pos < exp.dataLength; pos++)
			{
				uint mask = 0x01;
				//Console.WriteLine("pos = " + pos);

				for(int index = 0; index < 32; index++)
				{
					if((exp.data[pos] & mask) != 0)
						resultNum = BarrettReduction(resultNum * tempNum, n, constant);

					mask <<= 1;

					tempNum = BarrettReduction(tempNum * tempNum, n, constant);


					if(tempNum.dataLength == 1 && tempNum.data[0] == 1)
					{
						if(thisNegative && (exp.data[0] & 0x1) != 0)    //odd exp
							return -resultNum;
						return resultNum;
					}
					count++;
					if(count == totalBits)
						break;
				}
			}

			if(thisNegative && (exp.data[0] & 0x1) != 0)    //odd exp
				return -resultNum;

			return resultNum;
		}



		//***********************************************************************
		// Fast calculation of modular reduction using Barrett's reduction.
		// Requires x < b^(2k), where b is the base.  In this case, base is
		// 2^32 (uint).
		//
		// Reference [4]
		//***********************************************************************

		private BigInteger BarrettReduction(BigInteger x, BigInteger n, BigInteger constant)
		{
			int k = n.dataLength,
				kPlusOne = k+1,
				kMinusOne = k-1;

			BigInteger q1 = new BigInteger();

			// q1 = x / b^(k-1)
			for(int i = kMinusOne, j = 0; i < x.dataLength; i++, j++)
				q1.data[j] = x.data[i];
			q1.dataLength = x.dataLength - kMinusOne;
			if(q1.dataLength <= 0)
				q1.dataLength = 1;


			BigInteger q2 = q1 * constant;
			BigInteger q3 = new BigInteger();

			// q3 = q2 / b^(k+1)
			for(int i = kPlusOne, j = 0; i < q2.dataLength; i++, j++)
				q3.data[j] = q2.data[i];
			q3.dataLength = q2.dataLength - kPlusOne;
			if(q3.dataLength <= 0)
				q3.dataLength = 1;


			// r1 = x mod b^(k+1)
			// i.e. keep the lowest (k+1) words
			BigInteger r1 = new BigInteger();
			int lengthToCopy = (x.dataLength > kPlusOne) ? kPlusOne : x.dataLength;
			for(int i = 0; i < lengthToCopy; i++)
				r1.data[i] = x.data[i];
			r1.dataLength = lengthToCopy;


			// r2 = (q3 * n) mod b^(k+1)
			// partial multiplication of q3 and n

			BigInteger r2 = new BigInteger();
			for(int i = 0; i < q3.dataLength; i++)
			{
				if(q3.data[i] == 0)     continue;

				ulong mcarry = 0;
				int t = i;
				for(int j = 0; j < n.dataLength && t < kPlusOne; j++, t++)
				{
					// t = i + j
					ulong val = ((ulong)q3.data[i] * (ulong)n.data[j]) +
						(ulong)r2.data[t] + mcarry;

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

				if(t < kPlusOne)
					r2.data[t] = (uint)mcarry;
			}
			r2.dataLength = kPlusOne;
			while(r2.dataLength > 1 && r2.data[r2.dataLength-1] == 0)
				r2.dataLength--;

			r1 -= r2;
			if((r1.data[maxLength-1] & 0x80000000) != 0)        // negative
			{
				BigInteger val = new BigInteger();
				val.data[kPlusOne] = 0x00000001;
				val.dataLength = kPlusOne + 1;
				r1 += val;
			}

			while(r1 >= n)
				r1 -= n;

			return r1;
		}


		//***********************************************************************
		// Returns gcd(this, bi)
		//***********************************************************************

		public BigInteger gcd(BigInteger bi)
		{
			BigInteger x;
			BigInteger y;

			if((data[maxLength-1] & 0x80000000) != 0)     // negative
				x = -this;
			else
				x = this;

			if((bi.data[maxLength-1] & 0x80000000) != 0)     // negative
				y = -bi;
			else
				y = bi;

			BigInteger g = y;

			while(x.dataLength > 1 || (x.dataLength == 1 && x.data[0] != 0))
			{
				g = x;
				x = y % x;
				y = g;
			}

			return g;
		}


		//***********************************************************************
		// Populates "this" with the specified amount of random bits
		//***********************************************************************

		public void genRandomBits(int bits, Random rand)
		{
			int dwords = bits >> 5;
			int remBits = bits & 0x1F;

			if(remBits != 0)
				dwords++;

			if(dwords > maxLength)
				throw (new ArithmeticException("Number of required bits > maxLength."));

			for(int i = 0; i < dwords; i++)
				data[i] = (uint)(rand.NextDouble() * 0x100000000);

			for(int i = dwords; i < maxLength; i++)
				data[i] = 0;

			if(remBits != 0)
			{
				uint mask = (uint)(0x01 << (remBits-1));
				data[dwords-1] |= mask;

				mask = (uint)(0xFFFFFFFF >> (32 - remBits));
				data[dwords-1] &= mask;
			}
			else
				data[dwords-1] |= 0x80000000;

			dataLength = dwords;

			if(dataLength == 0)
				dataLength = 1;
		}


		//***********************************************************************
		// Returns the position of the most significant bit in the BigInteger.
		//
		// Eg.  The result is 0, if the value of BigInteger is 0...0000 0000
		//      The result is 1, if the value of BigInteger is 0...0000 0001
		//      The result is 2, if the value of BigInteger is 0...0000 0010
		//      The result is 2, if the value of BigInteger is 0...0000 0011