ubiginteger.cs

使用非对成RSA算法的序列号验证基础库

					if(expanded == null)
						throw new OutOfMemoryException();
					expanded[nEnd] = carry;
					while(nEnd < nCapacity)
					{
						expanded[nEnd + 1] = values[nEnd];
						nEnd ++;
					}
					values = expanded;
					nCapacity ++;
				}
				nLength ++;
			}
			return this;
		}

		/// <summary>
		/// 将指定大整数乘数:num = num.Multiply(multiplier)，相当于Num *= multiplier
		/// </summary>
		/// <param name="multiplier">乘数</param>
		/// <returns>返回被乘以乘数之后的乘积</returns>
		public UBigInteger Multiply(UBigInteger multiplier)
		{
			if(multiplier == 0)
			{
				nLength = 0;
				return this;
			}
			if(multiplier.nLength == 1)
			{
				return this.Multiply(multiplier.values[multiplier.nCapacity - 1]);
			}

			ulong sum, product = 0, carry = 0;

			int nLoop = nLength + multiplier.nLength - 1;
			int nEndThis = nCapacity - 1;
			int nMultiplier = multiplier.nCapacity - 1;

			nCapacity  = nLoop + 1;
			uint[] expanded = new uint[nCapacity];
			if(expanded == null)
				throw new OutOfMemoryException();

			for(int i=0; i<nLoop; i++)
			{
				sum = carry;
				carry = 0;

				for(int j=0; j<multiplier.nLength; j++)
				{
					if((i-j) >= 0 && (i - j) < nLength)
					{
						product = values[nEndThis + j - i];
						product *= multiplier.values[nMultiplier - j];
						carry += product >> 32;
						sum += product & 0xffffffff;
					}
				}
				carry += sum >> 32;
				expanded[nLoop - i] = (uint)sum;
			}
			if(carry > 0)
			{
				expanded[0] = (uint)carry;
				nLength = nLoop + 1;
			}
			else
			{
				expanded[0] = 0;
				nLength = nLoop;
			}
			values = expanded;
			return this;
		}

		/// <summary>
		/// 大数被减除一个大数:num = num.Subtraction(subtrahend)，相当于Num -= substrahend
		/// </summary>
		/// <param name="subtrahend">减数</param>
		/// <returns>返回减除减数之后的大整数</returns>
		public UBigInteger Subtraction(UBigInteger subtrahend)
		{
			if(this <= subtrahend)
			{
				nLength = 0;
				return this;
			}

			int nEndLeft = nCapacity;
			int nEndRight = subtrahend.nCapacity;

			int nLeftLength = nLength;
			int nRightLength = subtrahend.nLength;

			ulong minuend = 0;
			uint carry = 0;
			while(nRightLength > 0)
			{
				uint nLeft = values[--nEndLeft];
				uint nRight = subtrahend.values[--nEndRight];
				if(nLeft < nRight || (nLeft == nRight && carry > 0))
				{
					minuend = 0x100000000u + nLeft;
					values[nEndLeft] = (uint)(minuend - nRight - carry);
					carry = 1;
				}
				else
				{
					values[nEndLeft] = (uint)(nLeft - nRight - carry);
					carry = 0;
				}
				nLeftLength --;
				nRightLength --;
			}
			if(carry > 0)
			{
				while(values[--nEndLeft] == 0)
				{
					values[nEndLeft] = 0xffffffff;
					nLeftLength --;
				}
				values[nEndLeft] --;
				nLeftLength --;
			}
			while (nLeftLength > 0)	// 搜索最高位
			{
				nLeftLength --;
				nEndLeft --;
			}
			while(values[nEndLeft] == 0)
			{
				nEndLeft ++;
			}
			nLength = nCapacity - nEndLeft;
			return this;
		}

		/// <summary>
		/// 大数减除一个正整数:num = num.Subtraction(subtrahend)，相当于Num -= subtrahend
		/// </summary>
		/// <param name="subtrahend">减数</param>
		/// <returns>返回减除减数之后的剩余值</returns>
		public UBigInteger Subtraction(uint subtrahend)
		{
			if(nLength == 0)
				return this;

			int nEnd = nCapacity - 1;

			if(values[nEnd] > subtrahend)
			{
				values[nEnd] -= subtrahend;
				return this;
			}

			if(nLength == 1)
			{
				this.Assign(0);
				return this;
			}

			ulong minuend = 0x100000000u + values[nEnd];
			values[nEnd] = (uint)(minuend - subtrahend);

			while(values[--nEnd] ==0)
			{
				values[nEnd] = 0xffffffff;
			}
			values[nEnd] --;
			if(values[nEnd] == 0)
				nLength --;

			return this;
		}

		/// <summary>
		/// 大数加一个大数: num = num.Add(addend)，相当于 Num += addend
		/// </summary>
		/// <param name="addend">加数</param>
		/// <returns>返回大数加以加数之后的结果</returns>
		public UBigInteger Addition(UBigInteger addend)
		{
			uint carry = 0;
			ulong sum;

			int nEndAugend = nCapacity;
			int nMaxLength = addend.nLength > nLength ? addend.nLength : nLength;
			if(nMaxLength >= nCapacity)	// 防止溢出
			{
				nMaxLength ++;
				uint[] expanded = new uint[nMaxLength];
				if(expanded == null)
				{
					throw new OutOfMemoryException();
				}
				nCapacity = nMaxLength;

				int nNumber = nLength;
				while(nNumber -- > 0)
				{
					expanded[--nMaxLength] = values[--nEndAugend];
				}
				while(nMaxLength > 0)
				{
					expanded[--nMaxLength] = 0;
				}
				values = expanded;
			}

			int nEndAddend = addend.nCapacity;	// 加数最低位
			nEndAugend = nCapacity;				// 被加数最低位

			int nAddend = addend.nLength;
			//int nAugend = nLength;
			while(nAddend > 0)// && nEndAugend > 0)
			{
				sum = values[--nEndAugend];
				sum += addend.values[--nEndAddend];
				sum += carry;
				values[nEndAugend] = (uint)(sum);
				carry = (uint)(sum >> 32);

				//nAugend --;
				nAddend --;
			}
			while(carry > 0)
			{
				sum = values[--nEndAugend];
				sum += carry;
				values[nEndAugend] = (uint)sum;
				carry = (uint)(sum >> 32);
			}
			// 确定最后的数据位数
			nLength = 0;
			while(nLength < nCapacity && values[nLength] == 0)
				nLength ++;
			nLength = nCapacity - nLength;

			return this;
		}

		/// <summary>
		/// 大数加一个32位正整数: num = num.Add(addend)，Num += addend
		/// </summary>
		/// <param name="addend">加数</param>
		/// <returns></returns>
		public UBigInteger Addition(uint addend)
		{
			int nEnd = nCapacity;

			int nNumber = nLength;
			while(addend > 0 && nNumber > 0)
			{
				ulong sum = values[--nEnd];
				sum += addend;
				values[nEnd] = (uint)sum;
				addend = (uint)(sum >> 32);
				nNumber --;
			}

			if(addend > 0)	// 进位
			{
				if(nEnd > 0)
				{
					values[--nEnd] = addend;
				}
				else
				{
					uint[] expanded = new uint[nCapacity + 1];
					if(expanded == null)
					{
						throw new OutOfMemoryException();
					}

					expanded[0] = addend;
					// to here the nEnd must be 0
					while(nEnd < nCapacity)
					{
						expanded[nEnd + 1] = values[nEnd];
						nEnd ++;
					}
					nCapacity ++;
					values = expanded;
				}
				nLength ++;
			}
			return this;
		}

		/// <summary>
		/// 求乘方的模:调用方式Num.RSATranslate(amp, mod)，返回值： Num = Num^amp % mod
		/// </summary>
		/// <param name="amp">幂</param>
		/// <param name="mod">用于取模的除数</param>
		/// <returns>返回大整数实例，它被乘方amp次之后对mod取模</returns>
		public UBigInteger RSATranslate(UBigInteger amp, UBigInteger mod)
		{
			UBigInteger saved = new UBigInteger(this);	// 保存原始Num

			int k = amp.nLength * 32 - 32;
			uint nValue = amp.values[amp.nCapacity - amp.nLength];
			while(nValue > 0)
			{
				nValue >>= 1;
				k ++;
			}

			UBigInteger temp = new UBigInteger(nCapacity);
			UBigInteger y = new UBigInteger(nCapacity);
			for(int i=k-2; i>=0; i--)
			{
				int nStart = nCapacity - nLength;

				y.Item = this;
				y.Multiply(this.values[nStart]);
				y.Modulus(mod);

				while(nStart < this.nCapacity - 1)
				{
					//int j = 1;
					y.LeftShift(1);

					temp.Item = this;
					temp.Multiply(values[++nStart]);
					y.Addition(temp);
					y.Modulus(mod);
					//y.Item = y + (result * result.values[++ nStart]);
					//y.Item = y % mod;
				}

				this.Item = y;
//				if(nLength == 0)
//					break;
				nStart = nCapacity - nLength;
				if((((amp.values[amp.nCapacity - 1 - (i >> 5)] >> (i & 0x1f)) & 1) != 0))
				{
					y.Item = saved;
					y.Multiply(values[nStart]);
					y.Modulus(mod);

					//y.Item = (this) * result.values[nStart];
					//y.Item = y % mod;

					while(nStart < nCapacity - 1)
					{
						y.LeftShift(1);

						//y.Item = y + (this) * result.values[++nStart];
						//y.Item = y % mod;
						temp.Item = saved;
						temp.Multiply(values[++nStart]);
						y.Addition(temp);
						y.Modulus(mod);
					}
					this.Item = y;
				}
			}
			return this;
		}
		#endregion

		#region 内部操作方法
		/// <summary>
		/// 将大整数赋值为无符号32位整数
		/// </summary>
		/// <param name="value">无符号32位整数</param>
		private void Assign(uint value)
		{
			if(value > 0)
			{
				nLength = 1;
				values[nCapacity - 1] = value;
			}
			else
			{
				nLength = 0;
			}
			int nEnd = nCapacity - nLength;

			while(nEnd > 0)
			{
				values[--nEnd] = 0;
			}
		}

		/// <summary>
		/// 刷新位数
		/// </summary>
		private void RefreshLength()
		{
			int nzPosition = 0;
			while(nzPosition < nCapacity)
			{
				if(values[nzPosition] > 0)
				{
					break;
				}
				nzPosition ++;
			}
			nLength = nCapacity - nzPosition;
		}

		/// <summary>
		/// 大整数左以一位（以0x100000000进制计算）
		/// </summary>
		/// <param name="digit2Pow32">位数</param>
		private void LeftShift(int digit2Pow32)	// 按照2^32进制左移位
		{
			if(digit2Pow32 == 0)
				return;

			int nStart = nCapacity - nLength;
			int nNewLength = digit2Pow32 + nLength;
			if(nNewLength > nCapacity)
			{
				uint[] expanded = new uint[nNewLength];
				int nStartExpanded = 0;
				while(nStart < nCapacity)
				{
					expanded[nStartExpanded ++] = values[nStart++];
				}
				while(nStartExpanded < nNewLength)
				{
					expanded[nStartExpanded ++] = 0;
				}
				values = expanded;
				nCapacity = nLength = nNewLength;
			}
			else
			{
				nStart = nCapacity - nLength;
				while(nStart < nCapacity)
				{
					values[nStart - digit2Pow32] = values[nStart];
					values[nStart] = 0;
					nStart ++;
				}
				nLength += digit2Pow32;
			}
		}
		/// <summary>
		/// 大整数右移digit2Pow32位（以0x100000000进制计算）
		/// </summary>
		/// <param name="digit2Pow32">右移位数</param>
		private void RightShift(int digit2Pow32)	// 按照2^32进制右移位
		{
			if(digit2Pow32 == 0)
				return;

			int nStart = nCapacity - nLength;
			if(digit2Pow32 >= nLength)
			{
				while(nStart < nCapacity)
				{
					values[nStart ++] = 0;
				}
				nLength = 0;
				return;
			}

			int nEnd = nCapacity - digit2Pow32 - 1;
			while(nEnd >= nStart)
			{
				values[nEnd + digit2Pow32] = values[nEnd];
				values[nEnd] = 0;
				nEnd --;
			}
			nLength -= digit2Pow32;
		}
		#endregion

		#region 素数操作

		/// <summary>
		/// 拉宾米勒测试素数
		/// </summary>
		/// <returns>如果大数实例是一个素数，返回真值，否则返回假</returns>
		public bool PrimalityRabTest()
		{
			for(int i=0; i<(PrimeTable.Length); i++)
			{
				if( (this % (uint)PrimeTable[i]) == 0)
					return false;
			}

			UBigInteger k = new UBigInteger(this);
			k.values[k.nCapacity - 1] --;

			UBigInteger a = new UBigInteger(nCapacity);
			UBigInteger s = new UBigInteger(k.nCapacity);

			for(int i=0; i<5; i++)
			{
				bool fPassed = false;
				// s 赋予随机数
				a.values[a.nCapacity - 1] = (uint)((random.Next(0x10000) << 16) + random.Next(0x10000));
				a.nLength = 1;
				s.Item = k;

				UBigInteger pInv = null;
				while((s.values[s.nCapacity-1] & 1 ) == 0)
				{
					// 右移一bit,即除以2
					int nStart = s.nCapacity - s.nLength;
					uint carry = 0;
					while(nStart < s.nCapacity)
					{
						uint preSave = s.values[nStart] >> 1;
						preSave |= carry;
						carry = s.values[nStart] << 31;
						s.values[nStart] = preSave;
						nStart ++;
					}
					while(s.nLength > 0 && s.values[s.nCapacity - s.nLength] == 0)
						s.nLength --;

					pInv = RSATranslate(a, s, this);

					if(pInv == k)
					{
						fPassed = true;
						break;
					}
				}
				if(pInv == 1)
					fPassed = true;
				if(!fPassed)
					return false;
			}
			return true;
		}

		/// <summary>
		/// 产生随机素数，nDigits2Pow32表示位数（2^32进制）
		/// </summary>
		/// <param name="nDigits2Pow32">以0x100000000进制计算的位数</param>
		/// <returns>返回指定（0x100000000进制）位数的素数</returns>
		public static UBigInteger RandomPrime(int nDigits2Pow32)
		{
			UBigInteger result = new UBigInteger(nDigits2Pow32);
			result.nLength = nDigits2Pow32;
			int i;

			UBigInteger k = new UBigInteger(nDigits2Pow32);
			UBigInteger a = new UBigInteger(nDigits2Pow32);
			UBigInteger s = new UBigInteger(nDigits2Pow32);

			bool fNotReady = true;
			while(fNotReady)