C#笔记：RSA加解密实现

上回研究产生大素数，产生大素数，肯定是和加密有关的。现在我们就来实现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))即可。 原理讲完了。现在贴代码： <pre class="brush:c#;toolbar:false">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();
        }
    }</pre>

来自大脸猫写于 2015-02-16 22:08 -- 更新于2020-10-19 13:06 -- 0 条评论

大猪 & 大兔

C#笔记：RSA加解密实现

0条评论

评论:

文章分类

相册

关于网站

友情链接