RSA 在C#里简单实现

1.选择两个大素数：p,q;
2.计算所得n：n=p*q;
3.计算中间结果t：t=(p-1)*(q-1);
4.选择一个e：要求e和t的最大公因数是1（也就是e与t互素）;
5.计算所得d：d*e mod t=1，就是说要求d和e的乘积除以t余1;
（n,e）就是公钥，(n,d)就是私钥 

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int p = 3;              //质数
            int q = 17;             //质数

            if (!IsSuShu(p) || !IsSuShu(q))
            {
                Console.WriteLine("选择的数字必须是素数");
            }

            int n = p * q;
            int r = (p - 1) * (q - 1); //欧拉函数

            var keyList = GetKeyList(r);
            var key = keyList.Where(k => k.Item1 != p && k.Item1 != q && k.Item2 != p && k.Item2 != q).LastOrDefault();
            int e = key.Item1;  //公钥
            int d = key.Item2;  //私钥

            long msg = new Random().Next(1, n); //msg必须小于n
            double encodeMsg = RSA(n, e, msg);
            double decodeMsg = RSA(n, d, encodeMsg);
            Console.WriteLine("加密前：" + msg);
            Console.WriteLine("加密后：" + encodeMsg);
            Console.WriteLine("解密后：" + decodeMsg);
            Console.Read();
        }

        private static List<Tuple<int, int>> GetKeyList(int r)
        {
            var list = new List<Tuple<int, int>>();
            int e = r;
            int d = 0;
            while (true)
            {
                if (e <= 1)
                {
                    break;
                }
                if (IsSuShu(e))
                {
                    if (!IsHaveGongYueShu(r, e)) //r与e互质
                    {
                        d = GetE2(r, e);
                        if (d > 0)
                        {
                            list.Add(new Tuple<int, int>(e, d));
                        }
                    }
                }
                e--;
            }
            if (list.Count == 0)
            {
                throw new Exception("找不到合适的数字用来当做公钥");
            }
            return list;
        }

        private static int GetE2(int r, int e)
        {
            for (int d = r; d > 0; d--)
            {
                if ((d * e) % r == 1 && d != e) //求e关于r的模反元素
                {
                    return d;
                }
            }
            return 0;
        }

        private static bool IsHaveGongYueShu(int r, int e)
        {
            var rList = new List<int>();
            var dList = new List<int>();
            for (int i = 2; i < r; i++)
            {
                if (r % i == 0)
                {
                    rList.Add(i);
                }
            }
            for (int i = 2; i < e; i++)
            {
                if (e % i == 0)
                {
                    dList.Add(i);
                }
            }
            int result = rList.Where(p => dList.Contains(p)).Count();
            if (result > 0) //两个数字是否有公约数
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        private static bool IsSuShu(int num)
        {
            bool bl = true;
            for (int i = 2; i <= Math.Sqrt(num) && bl == true; i++) //数字是否是素数
            {
                if (num % i == 0)
                {
                    bl = false;
                }
            }
            return bl;
        }


        public static double RSA(int n, int key, double message)
        {
            if (n < 1 || key < 1)
            {
                return 0;
            }
            double rsaMessage = 0L;
            rsaMessage = Math.Pow(message, key) % n;
            return rsaMessage;
        }
    }
}