ubiginteger.cs

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

			{
				for(i=0; i<nDigits2Pow32; i++)
				{
					result.values[i] = ((uint)random.Next(0x10000) << 16) + (uint)random.Next(0x10000);
				}
				result.values[nDigits2Pow32 - 1] |= 1;		// 转变为奇数

				for(i=0; i<nDigits2Pow32 - 1; i++)			// 左移一位
				{
					result.values[i] <<= 1;
					result.values[i] |= result.values[i + 1] >> 31;
				}
				result.values[i] <<= 1;		// 最后一个
				result.values[i] ++;

				fNotReady = false;
				for(i=0; i<PrimeTable.Length; i++)
				{
					if((result % PrimeTable[i]) == 0)
					{
						fNotReady = true;
						break;
					}
				}

				if(fNotReady)
					continue;

				k.Item = result;
				k.values[k.nCapacity - 1] --;

				fNotReady = false;
				for(i=0; i<5; i++)
				{
					a.Assign((uint)(random.Next(0x10000) * random.Next(0x10000)));

					s.Item = k;
					// 右移一bit,即除以2 s = k / 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 --;

					UBigInteger inv = a.RSATranslate(s, result);

					if((inv != 1) &&  (inv != k))
					{
						fNotReady = true;
						break;
					}
				}
			}

			return result;
		}

		/// <summary>
		/// 获取一个位数相同但比自身小的随机素数，不影响实例本身
		/// </summary>
		/// <returns>返回与实例位数（0x100000000进制）相同但比实例小的素数</returns>
		public UBigInteger SmallerRandomPrime()
		{
			while(true)
			{
				UBigInteger prime = RandomPrime(nLength);
				if(prime < this)
					return prime;
			}
		}

		#endregion

		#region RSA 运算
		/// <summary>
		/// 进行RSA运算，data = num ^ amp % mod
		/// </summary>
		/// <param name="num">乘方的底数</param>
		/// <param name="amp">乘方的指数</param>
		/// <param name="mod">取模的除数</param>
		/// <returns>返回乘方的模</returns>
		public static UBigInteger RSATranslate(UBigInteger num, UBigInteger amp, UBigInteger mod)
		{
			UBigInteger result = new UBigInteger(num);

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

			UBigInteger y = new UBigInteger(result);
			UBigInteger temp = new UBigInteger(y.nCapacity);

			for(int i=k-2; i>=0; i--)
			{
				int nStart = result.nCapacity - result.nLength;

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

				y.Multiply(result.values[nStart]);
				y.Modulus(mod);

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

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

				result.Item = y;

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

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

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

			return result;
		}

		/// <summary>
		/// 求不定方程ax-by=1的最小整数解, 返回值：x,满足：(n * x % mod) = 1
		/// </summary>
		/// <param name="n">已知的乘积系数</param>
		/// <param name="mod">模除数mod</param>
		/// <returns></returns>
		public static UBigInteger Euclidean(UBigInteger n, UBigInteger mod)
		{
			UBigInteger m = new UBigInteger(mod);
			UBigInteger e = new UBigInteger(n);

			UBigInteger x = new UBigInteger();
			x.Assign(0);
			UBigInteger y = new UBigInteger();
			y.Assign(1);

			int k = 1, g = 1;
			while(e != 0)
			{
				UBigInteger i = m / e;
				UBigInteger j = m % e;
				m.Item = e;
				e.Item = j;
				j.Item = y;
				y.Item = y * i;

				if(k == g)
				{
					if( x >= y)
					{
						y.Item = x - y;
					}
					else
					{
						y.Item = y -x;
						g = 0;
					}
				}
				else
				{
					y.Item = x + y;
					k = 1 - k;
					g = 1 - g;
				}
				x.Item = j;
			}
			if(k == 0)
				x.Item = mod - x;
			return x;
		}

		#endregion

		#region 数据转换
		/// <summary>
		/// 从字符串解析大数，如果字符串的格式形如0x...则解释为16进制字符串，否则解析为10进制字符串
		/// </summary>
		/// <param name="s">要解析的字符串</param>
		/// <returns>返回字符串所代表的大整数</returns>
		public static UBigInteger Parse(string s)
		{
			if(s == null)
				throw new ArgumentNullException();

			String sNumber = s.Trim().ToUpper();

			if(sNumber.Length < 2)
				return ParseDecimal(sNumber);

			String sys = sNumber.Substring(0, 2);
			if(sys == "0X")
			{
				return ParseHex(sNumber.Substring(2));
			}
			else
			{
				return ParseDecimal(sNumber);
			}
		}

		/// <summary>
		/// 解析十六进制字符串
		/// </summary>
		/// <param name="s"></param>
		/// <returns></returns>
		private static UBigInteger ParseHex(string s)
		{
			for(int i=0; i<s.Length; i++)
			{
				char aChar = s[i];
				if(!(aChar >= '0' && aChar <='9' || aChar>= 'A' && aChar <= 'F'))
				{
					throw new FormatException();
				}
			}

//			int bitLength = s.Length << 2;		// 字符串所代表的二进制位数
//			bitLength >>= 5;
//			bitLength += 1;
			int number = (s.Length + 7) >> 3;	// 每个十六进制字符代表4bit

			Char[] charArray = s.ToCharArray();
			UBigInteger result = new UBigInteger(number);

			int nChars = s.Length - 1;	// 从最后一个字符开始
			int nEnd = result.nCapacity;
			while(nChars >= 0)
			{
				int nShift = 0;
				uint val = 0;
				do
				{
					Char aChar = s[nChars];//charArray[nChars];
					if(aChar >= '0' && aChar <= '9')
					{
						val |= (uint)(aChar - '0') << nShift;
					}
					else
					{
						val |= (uint)(aChar - 'A' + 10) << nShift;
					}
					nShift += 4;
					nChars --;
				}while(nShift < 32 && nChars >= 0);

				result.values[--nEnd] = val;
			}
			result.nLength = result.nCapacity - nEnd;
			return result;
		}
		/// <summary>
		/// 解析10进制字符串
		/// </summary>
		/// <param name="s"></param>
		/// <returns></returns>
		private static UBigInteger ParseDecimal(string s)
		{
			for(int i=0; i<s.Length; i++)
			{
				char aChar = s[i];
				if(aChar < '0' || aChar > '9')
				{
					throw new FormatException();
				}
			}

			int bitLength = s.Length * 333 / 100;		// 十进制转换之后所代表的位数
			bitLength += 31;
			bitLength >>= 5;

			UBigInteger result = new UBigInteger(bitLength);

			int nEnd = result.nCapacity;
			int nChars = 0;
			while(nChars < s.Length)
			{
				result.Multiply(10u);
				char aChar = s[nChars ++];
				result.Addition((uint)(aChar - '0'));
			}
			return result;
		}

		/// <summary>
		/// 从字节数组转换为大数
		/// </summary>
		/// <param name="byteArray">字节数组</param>
		/// <returns>返回字节数组所代表的大整数</returns>
		public static UBigInteger Parse(byte[] byteArray)
		{
			return Parse(byteArray, 0, byteArray.Length);
		}

		/// <summary>
		/// 从字节数组的一部分转换为大数
		/// </summary>
		/// <param name="byteArray">字节数组</param>
		/// <param name="index">字节数组起始索引位置</param>
		/// <param name="count">所使用的字节数组字节数</param>
		/// <returns>字节流代表的大整数</returns>
		public static UBigInteger Parse(byte[] byteArray, int index, int count)
		{
			if(byteArray == null)
				throw new ArgumentNullException();

			if(index < 0 || count < 0)
				throw new ArgumentOutOfRangeException();

			if(index + count > byteArray.Length)
				throw new ArgumentOutOfRangeException();

			if(count == 0)
			{
				UBigInteger result = new UBigInteger();
				for(int i=0; i<result.nCapacity; i++)
				{
					result.values[i] = 0;
				}
				return result;
			}
			else
			{
				UBigInteger result = new UBigInteger((count + 3) >> 2);		// 四个字节一位

				int nStart = 0;
				while(nStart < result.nCapacity)
					result.values[nStart++] = 0;

				nStart = (((count + 3) >> 2) << 2) - count;
				while(count > 0)
				{
					uint data = byteArray[index++];
					result.values[nStart >> 2] |= data << ((3 - (nStart & 0x3)) * 8);
					nStart ++;
					count --;
				}

				result.nLength = result.nCapacity;
				return result;
			}
		}

		/// <summary>
		/// 将大整数转化为字节数组
		/// </summary>
		/// <returns>返回代表大整数的字节数足</returns>
		public byte[] ToByteArray()
		{
			int nStart = nCapacity - nLength;

			// 最高位特别处理
			uint highest = values[nStart];
			int i = 0;
			uint mask = 0xFF000000;
			while(mask > 0 && (mask & highest) == 0)
			{
				mask >>= 8;
				i ++;
			}

			Byte[] byteArray = new Byte[nLength * 4 - i];	// 排除左零
			if(i > 0)
			{
				int j = 4 - i;
				for(i=0; i<j; i++)
				{
					byteArray[i] = (byte)(highest >> ((j - i - 1) * 8));
				}
				nStart ++;
			}

			while(nStart < nCapacity)
			{
				uint data = values[nStart++];
				byteArray[i++] = (Byte)(data >> 24);
				byteArray[i++] = (Byte)(data >> 16);
				byteArray[i++] = (Byte)(data >> 8);
				byteArray[i++] = (Byte)(data);
			}
			return byteArray;
		}

		/// <summary>
		/// 转换成十进制字符串
		/// </summary>
		/// <returns>返回大整数的10进制字符串表示</returns>
		public override string ToString()
		{
			if(nLength == 0)
				return "0";

			// 1位10进制数可以表示3.3219280948873623478703194294894 Bit
			int nString = (nLength * 32 * 100 + 331) / 332;		// 表示一个2^32进制的数据所需要的字符串长度

			Char[] charArray = new Char[nString];
			UBigInteger temp = new UBigInteger(this);
			uint mod = 0;
			while(temp.nLength > 0)
			{
				temp.Division(10, ref mod);
				charArray[--nString] = (Char)('0' + mod);
			}

			return new String(charArray, nString, charArray.Length - nString);
		}

		/// <summary>
		/// 根据格式化字符串将大数转换为字符串，格式化字符串"X"、"x"表示16进制表示，"d","D"表示10进制表示
		/// </summary>
		/// <param name="s">格式化字符串</param>
		/// <returns>根据格式指定的大数字符串</returns>
		public String ToString(String s)
		{
			if(s.Equals("x") || s.Equals("X"))
			{
				if(nLength == 0)
					return "0";

				Char[] mapping;
				if(s.Equals("x"))
				{
					mapping = LowerHexCharMapping;
				}
				else
				{
					mapping = UpperHexCharMapping;
				}

				System.Text.StringBuilder sb = new System.Text.StringBuilder();
				int nStart = nCapacity - nLength;
				bool fLeftZero = true;
				while(nStart < nCapacity)
				{
					uint number = values[nStart ++];
					int shift = 32;
					while(shift > 0)
					{
						shift -= 4;
						int index = (int)((number >> shift) & 0xf);
						if(index != 0 || !fLeftZero)
						{
							sb.Append(mapping[index]);
							fLeftZero = false;
						}
					}
				}
				return sb.ToString();
			}
			else if(s.Equals("d") || s.Equals("D"))
			{
				return ToString();
			}
			else
			{
				throw new System.FormatException();
			}
		}

		/// <summary>
		/// 实用程序：转换字节数组为16进制数字字符串
		/// </summary>
		/// <param name="byteArray">字节数组</param>
		/// <returns>16进制字符串</returns>
		public static string ConvertByteArrayToString(byte[] byteArray)
		{
			System.Text.StringBuilder sb = new System.Text.StringBuilder();
			for(int i=0; i<byteArray.Length; i++)
			{
				sb.AppendFormat("{0:X2}", byteArray[i]);
			}
			return sb.ToString();
		}

		/// <summary>
		/// 从十六进制数据字符串转换为字节数组
		/// </summary>
		/// <param name="s">代表16进制数（从0-9,A-F或者0-9,a-f)的字符串</param>
		/// <returns>转化之后的字节数组</returns>
		public static byte[] ConvertStringToByteArray(string s)
		{
			string upper = s.ToUpper();

			int nLength = (s.Length + 1) >> 1;
			byte[] byteArray = new byte[nLength];
			int nStart = (nLength << 1)- s.Length;
			nLength = 0;
			while(nLength < s.Length)
			{
				char aChar = upper[nLength ++];
				byte val;
				if(aChar >= '0' && aChar <= '9')
				{
					val = (byte)(aChar - '0');
				}
				else if(aChar >= 'A' && aChar <='F')
				{
					val = (byte)(aChar - 'A' + 10);
				}
				else
				{
					throw new FormatException();
				}
				byteArray[nStart >> 1] |= (byte)(val << (4 *(1 - nStart & 1)));
				nStart ++;
			}
			return byteArray;
		}

		#endregion
	}
}