program.cs

RSA ENCODE and DECODE C#

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics; 

namespace RSAceshi
{
    //class Program
    //{
    //    static void Main(string[] args)
    //    {
    //    }
    //}

    namespace rsatest 
{ 

/* 
??? RSA算法 
? 1978年就出现了这种算法，它是第一个既能用于数据加密也能用于数字签名的算法。 
??? 它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, 
??? AdiShamir 和Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。 

? RSA的安全性依赖于大数难于分解这一特点。公钥和私钥都是两个大素数（大于100个 
??? 十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大 
??? 素数的积。 

? 密钥对的产生。选择两个大素数，p 和q 。计算：n = p * q 然后随机选择加密密钥e， 
??? 要求 e 和 ( p - 1 ) * ( q - 1 )互质。最后，利用Euclid 算法计算解密密钥d, 满足 
??? e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )其中n和d也要互质。数e和n是公钥，d是私钥。 
??? 两个素数p和q不再需要，应该丢弃，不要让任何人知道。加密信息 m（二进制表示）时， 
??? 首先把m分成等长数据块 m1 ,m2,..., mi ，块长s，其中 2^s <= n, s 尽可能的大。对应 
??? 的密文是： 
ci = mi^e ( mod n ) .................( a ) 
解密时作如下计算： 
mi = ci^d ( mod n ) .................( b ) 

? RSA 可用于数字签名，方案是用 ( a ) 式签名， ( b )式验证。具体操作时考虑到安全性 
??? 和 m信息量较大等因素，一般是先作HASH 运算。RSA 的安全性。RSA的安全性依赖于大数 
??? 分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定 
??? 需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。 
??? 目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。 
??? 现在，人们已能分解140多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。 
??? 
??? 由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍，无论是软件还是硬件实现。 
??? 速度一直是RSA的缺陷。一般来说只用于少量数据加密。 
*/    
   public 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) 
 }; 

 class Program 
 { 
 //小素数表 
 #region Prime Table 
 readonly static long[] g_PrimeTable = 
 { 
 3, 
 5, 
 7, 
 11, 
 13, 
 17, 
 19, 
 23, 
 29, 
 31, 
 37, 
 41, 
  43, 
  47, 
 53, 
 59, 
  61, 
 67, 
 71, 
  73, 
  79, 
  83, 
  89, 
  97 
  }; 
 #endregion 

  readonly long g_PrimeCount = g_PrimeTable.Length; 
  const UInt64 multiplier = 12747293821; 
 const UInt64 adder = 1343545677842234541; 

 //随机数类 
  public class RandNumber 
 { 
  /* */ 
  private UInt64 randSeed;/* */ 
  public RandNumber():this(0) { } 

  public RandNumber(UInt64 s) 
  { 
  if (0 == s)//(!s) 
  { 
   randSeed = (UInt64)new Random().Next();//time(NULL); 
 } 
  else 
 { 
  randSeed = s; 
 } 
  } 
  
  /* */ 
  public UInt64 Random(UInt64 n) 
 { 
  randSeed = multiplier * randSeed + adder; 
  return randSeed % n; 
  } 
 } 

 static RandNumber g_Rnd = new RandNumber(); 

 /* 模乘运算，返回值 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 bas, UInt64 pow, UInt64 n) 
 { 
 UInt64 a = bas, b = pow, c = 1; 
 while (b != 0)  // (b) 
  { 
  while (1 != (b & 1)) // !(b&1) 
 { 
  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 (1 != (m&1))  // (!(m & 1)) 
 { 
  ++j; 
  m >>= 1; 
   }  //1、随机取一个b，2<=b b = 2 + g_Rnd.Random(n - 3); //2、计算v=b^m mod n 
   b = 6;
 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 % unchecked((ulong)g_PrimeTable[i])) == 0) 
  { 
  return 0; 
  } 
  } 

 //循环调用Rabin-Miller测试loop次，使得非素数通过测试的概率降为(1/4)^loop 
 for (long i = 0; i < loop; i++) 
 { 
 if (0 == RabinMillerKnl(n)) //(! ...) 
  { 
  return 0; 
 } 
  } return 1; 
  } 
  /* 随机生成一个bits位(二进制位)的素数，最多32位 */ 
 UInt64 RandomPrime(char bits) 
  { 
  UInt64 bas; 
 do 
  { 
  bas = (UInt32)1 << (bits - 1);  //保证最高位是1 
 bas += g_Rnd.Random(bas);  //再加上一个随机数 
  bas |= 1;  //保证最低位是1，即保证是奇数 
 } while (0 == RabinMiller(bas, 30)); // (!RabinMiller(bas, 30))??? //进行拉宾－米勒测试30次 
 return bas;  //全部通过认为是素数 
 } 

 /* 欧几里得法求最大公约数 */ 
  UInt64 EuclidGcd(UInt64 p, UInt64 q) 
 { 
  UInt64 a = p > q ? p : q; 
  UInt64 b = p < q ? p : q; 
  UInt64 t; 
 if (p == q) 
 { 
  return p; //两数相等，最大公约数就是本身 
 } 
  else 
  { 
  while (0 != b) //(b)  //辗转相除法，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 = p > q ? p : q; 
  UInt64 b = p < q ? p : q; 
  UInt64 t, r = 1; 
 if (p == q) 
  { 
 return p;  //两数相等，最大公约数就是本身 
 } 
  else 
 { 
  //while ((!(a & 1)) && (!(b & 1))) 
  while ((0 ==(a & 1)) && (0 ==(b & 1))) 
 { 
  r <<= 1;  //a、b均为偶数时，gcd(a,b)=2*gcd(a/2,b/2) 
  a >>= 1; 
 b >>= 1; 
 } 
 if (0 == (a&1))//(!(a & 1)) 
 { 
  t = a; //如果a为偶数，交换a，b 
 a = b; 
  b = t; 
  } 
        do 
  {  
        while (0 == (b & 1))//(!(b & 1)) 
  { 
  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); //(b); 
  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 (0 != e)//(e) 
 { 
  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(); 
  UInt64 t; 
  Rsa.p = RandomPrime((char)16);  //随机生成两个素数 
  Rsa.q = RandomPrime((char)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 (0 != t)//(t) 
  { 
  Rsa.s++;  //s=log2(n) 
 t >>= 1; 
  } return Rsa; 
 } 

  /* 拉宾－米勒测试 */ 
  void TestRM() 
  { 
  UInt32 k = 0; 
 Console.Write(" - Rabin-Miller prime check.\n\n"); 
 for (UInt64 i = 4197900001; i < 4198000000; i += 2) 
  { 
 if (0 != RabinMiller(i, 30)) 
 { 
 k++; 
  Console.WriteLine(i); 
  } 
  } 
  Console.WriteLine("Total: " + k); 
 } 

 /* RSA加密解密 */ 
  void TestRSA() 
 { 
 RSA_PARAM r; 
 string pSrc = "abcdefghijklmnopqrstuvwxyz"; 
  UInt32 n = (uint)pSrc.Length; 
 //unsigned char  *q, pDec[n]; 
  byte[] pDec = new byte[n]; 
 UInt64[] pEnc = new UInt64[n]; 
 r = RsaGetParam(); 
 Console.WriteLine("p=" + r.p); 
 Console.WriteLine("q=" + r.q); 
 Console.WriteLine("f=(p-1)*(q-1)=" + r.f); 
 Console.WriteLine("n=p*q=" + r.n); 
  Console.WriteLine("e=" + r.e); 
 Console.WriteLine("d=" + r.d); 
 Console.WriteLine("s=" + r.s); 
 Console.WriteLine("Source:" + pSrc); 
 //q= (unsigned char *)pSrc; 
 Console.Write("Encode:"); 
 for (int i = 0; i < (int)n; i++) 
 { 
 //pEnc[i]=PowMod(q[i], r.e, r.n); 
  pEnc[i] = PowMod((ulong)pSrc[i], r.e, r.n); 
 Console.Write(pEnc[i].ToString() + " "); 
  } Console.WriteLine(""); 
 Console.Write("Decode:"); 
 for (int i = 0; i < (int)n; i++) 
 { 
 pDec[i] = (byte)PowMod((ulong)pEnc[i], r.d, r.n); 
 Console.Write((UInt32)pDec[i] + " "); 
  } Console.WriteLine(""); 
 Console.WriteLine(Encoding.Default.GetString(pDec)); 
 }/* */ 


 static void Main(string[] args) 
  { 
 new Program().TestRSA();
 Console.ReadLine();

  } 
  } 
} 
}