C#筆記：RSA加解密實現

• 2019 年 11 月 22 日
• 筆記

上回研究產生大素數，產生大素數，肯定是和加密有關的。現在我們就來實現RSA演算法。哈哈。

第一步，隨機選擇兩個不相等的質數p和q。

第二步，計算p和q的乘積n。

第三步，計算n的歐拉函數φ(n)。 

根據公式：φ(n) = (p-1)(q-1)　

第四步，隨機選擇一個整數e，條件是1< e < φ(n)，且e與φ(n) 互質。一般取e1=65537 第五步，計算e對於φ(n)的模反元素d。  滿足e*d ≡ 1 (mod φ(n))即可。 原理講完了。現在貼程式碼：

BigInteger p = GetPrimeNum.CreatePrimeNum(128);              Console.WriteLine("p:" + p);              Console.WriteLine();              BigInteger q = GetPrimeNum.CreatePrimeNum(128);              Console.WriteLine("q:" + q);              Console.WriteLine();              BigInteger on = (p - 1) * (q - 1);              Console.WriteLine("o(n):" + on);              Console.WriteLine();              BigInteger n = p * q;              Console.WriteLine("n:" + n);              Console.WriteLine();              BigInteger e1 = BigInteger.Parse("65537");              Console.WriteLine("e1:" + e1);              Console.WriteLine();              BigInteger d = RSAProvider.CreateD(e1, on);              Console.WriteLine("d:" + d);              Console.WriteLine();              Console.WriteLine("加密123");              BigInteger c = RSAProvider.RsaEncrypt(123, e1, n);              Console.WriteLine("c:" + c);              Console.WriteLine("解密C");              BigInteger m = RSAProvider.RsaEncrypt(c, d, n);              Console.WriteLine("m:" + m);            public static class RSAProvider      {          /*            int r = MaxDivisorex(1769, 551, out a, out b);              MessageBox .Show(string.Format ("{0} * 1769 + {1} *551 = {2}",a,b,(a*1769+b*551)));           * 擴展歐幾里德演算法           *            */          private static BigInteger ext_euclid(BigInteger a, BigInteger b, out BigInteger x, out BigInteger y)          {              BigInteger t, d;              if (b == 0) { x = 1; y = 0; return a; }              d = ext_euclid(b, a % b, out x, out y);              t = x;              x = y;              y = t - a / b * y;              return d;          }          public static BigInteger CreateD(BigInteger e1, BigInteger on)          {              BigInteger d;              BigInteger y;              RSAProvider.ext_euclid(e1, on, out d, out y);              if (d.Sign == -1)              {                  int i = 1;                  while (true)                  {                      if (((1 + i * on) % e1) == 0)                      {                          d = (1 + i * on) / e1;                          y = i * (-1);                          break;                      }                      ++i;                  }              }              return d;          }          public static BigInteger RsaEncrypt(BigInteger m, BigInteger e1, BigInteger n)          {              BigInteger c = BigInteger.ModPow(m, e1, n);              return c;          }          public static BigInteger RsaDecrypt(BigInteger c, BigInteger d, BigInteger n)          {              return BigInteger.ModPow(c, d, n);          }      }            public static class GetPrimeNum      {          static RandomNumberGenerator rng = RandomNumberGenerator.Create();          public static BigInteger CreateRandomNum(int length)          {              byte[] bytes = new byte[length];              rng.GetBytes(bytes);              BigInteger a = new BigInteger(bytes);              if (a.IsEven)//如果是偶數就加一              {                  a += 1;              }              if (a.Sign == -1)//如果是負數就乘-1              {                  a *= -1;              }              return a;          }          static ManualResetEvent mre = new ManualResetEvent(false);//執行緒阻塞器設置為阻塞狀態          static BigInteger result = BigInteger.Zero;//result的初始化值設為0          //候選數的工作隊列，執行緒從此隊列取數驗證直到找到素數          static BlockQueue<BigInteger> quePrime = new BlockQueue<BigInteger>(2000);                    //這個標籤用來在運算完畢後結束多餘的執行緒          private static volatile bool isOver = false;          public static BigInteger CreatePrimeNum(int length)          {              //將執行緒阻塞器設置為阻塞狀態。此狀態下，主執行緒會等待工作執行緒找到數再返回result。              mre.Reset();              isOver = false;              //初始化7個任務用來對隊列中的數進行取數驗證              //使用的是系統默認的執行緒池，當執行緒池中有空餘執行緒時，會對這7個任務進行計算。              for (int i = 0; i < 7; i++)              {                  ThreadPool.QueueUserWorkItem(ThreadMethod, mre);              }              //每次工作時將隊列清除              quePrime.Clear();              //重新初始化種子值，一個1024bit的數。              BigInteger bigNum = CreateRandomNum(128);              //將種子值也入隊              quePrime.EnQueue(bigNum);              //這個執行緒不斷的把種子值+2入隊,以免隊列空虛使得死鎖。              Thread thInsertNum = new Thread(new ThreadStart(delegate              {                  while (true)                  {                      bigNum += 2;                      quePrime.EnQueue(bigNum);                  }              }));              thInsertNum.Start();              //等待後台執行緒釋放主執行緒的阻塞              mre.WaitOne();              /*後台執行緒找到了素數，並對result賦值，關閉將數字不斷入隊的執行緒。               * 至於執行緒池中的任務不必操心。後台自然會自動處理。因為標籤已經置為isover了。              */              thInsertNum.Abort();                           //返回這個值，它是素數              return result;          }          public static BigInteger CreatePrimeNum2(int length)          {              //這是以單執行緒形式進行運算的例子，通過測試，顯然，它比較慢。              BigInteger primeNum = CreateRandomNum(length);              int i = 0;              do              {                  i++;                  primeNum += 2;              }              while (!primeNum.IsProbablePrime());              return primeNum;          }          private static void ThreadMethod(object obj)          {              //尋找素數並賦值給result的執行緒中運行的方法              while (!isOver)              {                  //將隊列中的數出隊，使用隊列是為了避免同一個數被重複運算。防止執行緒衝突。                  BigInteger tempNum = quePrime.DeQueue();                  if (tempNum.IsProbablePrime())                  {                      //找到了素數，對全局變數賦值                      result = tempNum;                      //釋放進程鎖，此後主進程將會把這個result返回                      ManualResetEvent mre = (ManualResetEvent)obj;                      mre.Set();                      isOver = true;                      break;                  }              }          }          //此類來自維基百科          public static bool IsProbablePrime(this BigInteger source)          {              if (PreCheckPrime(source) != 0)              {                  return false;              }              int certainty = 4;//確認4次差不多了              //if (source == 2 || source == 3)              //    return true;              //if (source < 2 || source % 2 == 0)              //    return false;              //就本類的隨機數發生器，以上情況不可能出現                           BigInteger d = source - 1;              int s = 0;              while (d % 2 == 0)              {                  d /= 2;                  s += 1;              }                                    byte[] bytes = new byte[source.ToByteArray().LongLength];              BigInteger a;              for (int i = 0; i < certainty; i++)              {                  do                  {                                         rng.GetBytes(bytes);                      a = new BigInteger(bytes);                  }                  while (a < 2 || a >= source - 2);                  BigInteger x = BigInteger.ModPow(a, d, source);                  if (x == 1 || x == source - 1)                      continue;                  for (int r = 1; r < s; r++)                  {                      x = BigInteger.ModPow(x, 2, source);                      if (x == 1)                          return false;                      if (x == source - 1)                          break;                  }                  if (x != source - 1)                      return false;              }              return true;          }          //在使用RabinMiller演算法前先進行素數的篩選          public static int PreCheckPrime(BigInteger bigNum)          {              //檢驗被3,5,7,17特殊數字整除              string strBigNum = bigNum.ToString();              int everyDigit = 0;//這個數字除個位的其它位之和              for (int i = 0; i < strBigNum.Length - 1; i++)              {                  everyDigit += int.Parse(strBigNum[i].ToString());              }              int lastDigit = int.Parse(strBigNum[strBigNum.Length - 1].ToString());              //每一位上數字之和能被3整除，那麼這個數就能被3整除。              if ((everyDigit + lastDigit) % 3 == 0)              {                  return 3;              }              //個位上是0或5的數都能被5整除。              if (lastDigit.Equals(5))              {                  return 5;              }              int[] shortPrimes = { 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999 };              for (int i = 0; i < shortPrimes.Length; i++)              {                  if (bigNum % shortPrimes[i] == 0)                  {                      return shortPrimes[i];                  }              }              return 0;          }      }      //這是一個阻塞隊列      public class BlockQueue<T>      {          public readonly int SizeLimit = 0;          private Queue<T> _inner_queue = null;          public int Count          {              get { return _inner_queue.Count; }          }          private ManualResetEvent _enqueue_wait = null;          private ManualResetEvent _dequeue_wait = null;          public BlockQueue(int sizeLimit)          {              this.SizeLimit = sizeLimit;              this._inner_queue = new Queue<T>(this.SizeLimit);              this._enqueue_wait = new ManualResetEvent(false);              this._dequeue_wait = new ManualResetEvent(false);          }          public void EnQueue(T item)          {              if (this._IsShutdown == true) throw new InvalidCastException("Queue was shutdown. Enqueue was not allowed.");              while (true)              {                  lock (this._inner_queue)                  {                      if (this._inner_queue.Count < this.SizeLimit)                      {                          this._inner_queue.Enqueue(item);                          this._enqueue_wait.Reset();                          this._dequeue_wait.Set();                          break;                      }                  }                  this._enqueue_wait.WaitOne();              }          }          public T DeQueue()          {              while (true)              {                  if (this._IsShutdown == true)                  {                      lock (this._inner_queue) return this._inner_queue.Dequeue();                  }                  lock (this._inner_queue)                  {                      if (this._inner_queue.Count > 0)                      {                          T item = this._inner_queue.Dequeue();                          this._dequeue_wait.Reset();                          this._enqueue_wait.Set();                          return item;                      }                  }                  this._dequeue_wait.WaitOne();              }          }          public void Clear()          {              this._inner_queue.Clear();              this._dequeue_wait.Reset();              this._enqueue_wait.Set();          }          private bool _IsShutdown = false;          public void Shutdown()          {              this._IsShutdown = true;              this._dequeue_wait.Set();          }      }