上回研究产生大素数，产生大素数，肯定是和加密有关的。现在我们就来实现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))即可。 原理讲完了。现在贴代码：
代码语言：javascript复制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();
}
}
