catsicrsa.cs

RSA加密解密算法

using System;
using System.Security.Cryptography;
using  System.Runtime.InteropServices;
namespace CatsicRSA
{
	/// <summary>
	/// CatsicRSA 的摘要说明。
	/// </summary>
	/// 
	struct RSA_PARAM
	{
	public 	UInt64 p, q; //两个素数，不参与加密解密运算
	public 		UInt64 f; //f=(p-1)*(q-1)，不参与加密解密运算
	public 		UInt64 n, e; //公匙，n=p*q，gcd(e,f)=1
	public 		UInt64 d; //私匙，e*d=1 (mod f)，gcd(n,d)=1
	public 		UInt64 s; //块长，满足2^s<=n的最大的s，即log2(n)
	} ;

	
	public class CatsicRSA
	{

		public string endl="\n";


	//小素数表
 ulong[] g_PrimeTable=new ulong[]
{
	3,	5,	7,	11,	13,	17,
	19,	23,	29,	31,	37,	41,
	43,	47,	53,	59,	61,	67,
	71,	73,	79,	83,	89,	97
};
	private	long g_PrimeCount;
	const UInt64 multiplier=12747293821;
	const UInt64 adder=1343545677842234541;

//随机数类

	private	class cRandNumber
		{
			/* */
		private		UInt64 randSeed;
			/* */

		public void	RandNumber(UInt64 s)
{
	if(s == 0)
{
		string sss;
		sss="0";
		RNGCryptoServiceProvider.Create(  sss );
	randSeed= Convert.ToUInt64( sss);//(UInt64)time(NULL);
}
	else
{
	randSeed=s;
}
}

			/* */
	public UInt64 Random(UInt64 n)
		{
			randSeed=multiplier * randSeed + adder;
			return randSeed % n;
		}
		
	};
static cRandNumber g_Rnd;

/* */
/*
模乘运算，返回值 x=a*b mod n
*/
		UInt64 MulMod(UInt64 a, UInt64 b, UInt64 n)
	{
		 return a * b % n;
	}
/*
模幂运算，返回值 x=base^pow mod n
*/
		UInt64 PowMod(UInt64 nbase, UInt64 pow, UInt64 n)
		{
			UInt64 a=nbase, b=pow, c=1;
			while(b!=0)
			{
				while((b & 1)==0)
	 			{
					b>>=1; 
					//a=a * a % n; //函数看起来可以处理64位的整数，但由于这里a*a在a>=2^32时已经造成了溢出，
					//因此实际处理范围没有64位
					a=MulMod(a, a, n);
				} b--; 
				//c=a * c % n; //这里也会溢出，若把64位整数拆为两个32位整数不知是否可以解决这个问题。
				c=MulMod(a, c, n);
			} 
			return c;
		}      
  /*
    Rabin-Miller素数测试，通过测试返回1，否则返回0。
    n是待测素数。
    注意：通过测试并不一定就是素数，非素数通过测试的概率是1/4
    */
		long RabinMillerKnl(UInt64 n)
		{
			UInt64 b, m, j, v, i;
			m=n - 1;
			j=0; //0、先计算出m、j，使得n-1=m*2^j，其中m是正奇数，j是非负整数
			while((m & 1)==0)
			{
				++j;
				m>>=1;
			} 
			//1、随机取一个b，2<=b 
			b=2 + g_Rnd.Random(n - 3); 
		
			//2、计算v=b^m mod n
			v=PowMod(b, m, n); //3、如果v==1，通过测试
			if(v == 1)
			{
				return 1;
			} //4、令i=1
			i=1; //5、如果v=n-1，通过测试
			while(v != n - 1)
			{
				//6、如果i==l，非素数，结束
				if(i == j)
				{
					return 0;
				} //7、v=v^2 mod n，i=i+1
				v=PowMod(v, 2, n);
				++i; //8、循环到5
			} return 1;
		}
	
	/*
    Rabin-Miller素数测试，循环调用核心loop次
    全部通过返回1，否则返回0
    */
		long RabinMiller(UInt64 n, long loop)
		{
			//先用小素数筛选一次，提高效率
			for(long i=0; i < g_PrimeCount; i++)
			{
				if(n % g_PrimeTable[i] == 0)
				{
					return 0;
				}
			} //循环调用Rabin-Miller测试loop次，使得非素数通过测试的概率降为(1/4)^loop
			for(long i=0; i < loop; i++)
			{
				if(RabinMillerKnl(n)==0)
				{
					return 0;
				}
			} return 1;
		}
		/*
    随机生成一个bits位(二进制位)的素数，最多32位
    */
		UInt64 RandomPrime(int bits)
		{
			UInt64 nbase;
			do
			{
				nbase= (ulong)1 << (bits - 1); //保证最高位是1
				nbase+=g_Rnd.Random(nbase); //再加上一个随机数

				nbase|=1; //保证最低位是1，即保证是奇数

			} 
			while(RabinMiller(nbase, 30)==0); //进行拉宾－米勒测试30次
			return nbase; //全部通过认为是素数
		}
/*
    欧几里得法求最大公约数
    */
		UInt64 EuclidGcd(UInt64 p, UInt64 q)
		{
			UInt64 a=Math.Max(  p , q);
			UInt64 b=Math.Min( p , q);
			UInt64 t;
			if(p == q)
			{
				return p; //两数相等，最大公约数就是本身
			}
			else
			{
				while(b!=0) //辗转相除法，gcd(a,b)=gcd(b,a-qb)
				{
					a=a % b;
					t=a;
					a=b;
					b=t;
				} return a;
			}
		}
		/*
    Stein法求最大公约数
    */

    UInt64 SteinGcd(UInt64 p, UInt64 q)
	{
		UInt64 a=Math.Max(  p , q);
		UInt64 b=Math.Min( p , q);
		UInt64 t, r=1;
		if(p == q)
		{
			return p; //两数相等，最大公约数就是本身
		}
		else
		{
			while(((a & 1)==0) && (0==(b & 1)))
			{
				r<<=1; //a、b均为偶数时，gcd(a,b)=2*gcd(a/2,b/2)
				a>>=1;
				b>>=1;
			} if((a & 1)==0)
			  {
				  t=a; //如果a为偶数，交换a，b
				  a=b;
				  b=t;
			  } 
			do 
			{ 
			while((b & 1)==0)
			{
				b>>=1; //b为偶数，a为奇数时，gcd(b,a)=gcd(b/2,a)
			} 
				if(b < a)
				{
					t=a; //如果b小于a，交换a，b
					a=b;
					b=t;
				} 
				b=(b - a) >> 1; //b、a都是奇数，gcd(b,a)=gcd((b-a)/2,a)
			}while(b!=0);
			return r * a;
		}
	}
	/*
    已知a、b，求x，满足a*x =1 (mod b)
    相当于求解a*x-b*y=1的最小整数解
    */
		UInt64 Euclid(UInt64 a, UInt64 b)
		{
			UInt64 m, e, i, j, x, y;
			long xx, yy;
			m=b;
			e=a;
			x=0;
			y=1;
			xx=1;
			yy=1;
			while(e!=0)
			{
				i=m / e;
				j=m % e;
				m=e;
				e=j;
				j=y;
				y*=i;
				if(xx == yy)
				{
					if(x > y)
					{
						y=x - y;
					}
					else
					{
						y-=x;
						yy=0;
					}
				}
				else
				{
					y+=x;
					xx=1 - xx;
					yy=1 - yy;
				} x=j;
			} if(xx == 0)
			  {
				  x=b - x;
			  } return x;
		}
	/*
	随机产生一个RSA加密参数
	*/

		RSA_PARAM RsaGetParam()
		{
			RSA_PARAM Rsa;//=new RSA_PARAM( 0);//{ };
			UInt64 t;
			Rsa.p=RandomPrime(16); //随机生成两个素数
			Rsa.q=RandomPrime(16);
			Rsa.n=Rsa.p * Rsa.q;
			Rsa.f=(Rsa.p - 1) * (Rsa.q - 1);
			do
			{
				Rsa.e=g_Rnd.Random(65536); //小于2^16，65536=2^16
				Rsa.e|=1; //保证最低位是1，即保证是奇数，因f一定是偶数，要互素，只能是奇数
			} while(SteinGcd(Rsa.e, Rsa.f) != 1); Rsa.d=Euclid(Rsa.e, Rsa.f);
			Rsa.s=0;
			t=Rsa.n >> 1;
			while(t!=0)
			{
				Rsa.s++; //s=log2(n)
				t>>=1;
			} return Rsa;
		}
		
		/*
    拉宾－米勒测试
    */
		string TestRM()
		{
			string cout;
			ulong k=0;
			cout= " - Rabin-Miller prime check.\n"+ endl;
			for(UInt64 i=4197900001; i < 4198000000; i+=2)
			{
				if(RabinMiller(i, 30)!=0)
				{
					k++;
					cout += i + endl;
				}
			} cout += "Total: " + k + endl;
			return cout;
		}
	/*
    RSA加密
    */
		public ulong[] encode(char[] pSrc ,UInt64 e,UInt64 n)
		{	ulong ulCharCount=Convert.ToUInt64(pSrc.GetUpperBound(0)) ;
			UInt64[] pEnc=new UInt64[ulCharCount+1];
			for(ulong i=0; i <= ulCharCount; i++)
			{
				pEnc[i]=PowMod(pSrc[i], e, n);
			} 
		return pEnc;
		}

		public ulong[] encode(char[] pSrc )
		{
			ulong e = 18317;
			ulong n=1949399909;
			return encode( pSrc ,e, n);
			
		}
		public string encode(string sSrc)
		{
			ulong[] uCode;
			string strRet="";//,strRet1="";
			string strTemp;
			uCode = encode(sSrc.ToCharArray());

			for(long i = 0; i< uCode.LongLength; i++)
			{
				strTemp="0"+uCode[i].ToString("X");
//				strRet1 += Convert.ToChar(uCode[i] / 10000);
//				strRet1 += Convert.ToChar(uCode[i] / 10000);
				strRet += strTemp.Substring(strTemp.Length-8,8);
			}

		return strRet;
		}


// 解密

		public char[] decode(UInt64[] pEnc ,UInt64 d,UInt64 n)
		{
		
			ulong ulCharCount=Convert.ToUInt64(pEnc.GetUpperBound(0)) ;

			char[]  pDec;
			//string cout;
			pDec =new char[ulCharCount+1];
		
			for(ulong i=0; i <=ulCharCount; i++)
			{
				pDec[i]=(char)PowMod(pEnc[i], d, n);
			}
				return pDec;
			}

		public char[] decode(UInt64[] pEnc )
		{
			ulong d=1795636193;
			ulong n=1949399909;			
			return decode(pEnc,d,n);
		}
		public string decode(string sEnc )
		{
		
			UInt64[] pEnc;
			long longCharCount;
			string strOut="",strTemp;
			char[] cDecoded;
			longCharCount=(long)(sEnc.Length % 8) ;
			if (longCharCount!=0 )
			{return "error "; 
			}else
			{
				longCharCount=(long)(sEnc.Length / 8);
				pEnc=new UInt64[longCharCount];
				for(long i=0 ; i<longCharCount;i++)
				{
					strTemp="0x" + sEnc.Substring(0,8);

					pEnc[i]=Convert.ToUInt64(strTemp,16);

					sEnc=sEnc.Substring(8);

				}
			}

			cDecoded=decode(pEnc);
			for(long i=0 ; i< longCharCount;i++)
			{
			strOut += cDecoded[i];
			}
		return strOut;
		}

   		public CatsicRSA()
		{
			//
			// TODO: 在此处添加构造函数逻辑
			//
			g_Rnd=new cRandNumber();
			g_PrimeCount=g_PrimeTable.GetLongLength(0);
		}	
	}

}