#创作挑战赛#
RSA算法，是为了给在互联网上传输的数据加密而设计的。
如下图，是RSA加密数据的传输过程：
RSA加密的传输
给谁发信息，就用谁的公钥加密，然后接收端可以用他自己的私钥解密。
公钥是公开的，私钥是保密的（只有接收端知道），这样中途截获数据的一方就没法解密，看到的只是加密后的“乱码”。
公钥和私钥之间互为逆运算，而且与两个大素数的乘积有关，这个乘积很难再分解成原来的两个大素数！
整数对素数的模运算（取余数），在加法和乘法下是一个有限的循环群：
它可以把用来传输信息的字母表变化一下，让有意义的单词变成乱码。
英文有26个字母：让a变成b，b变成c，......，y变成z，z变成a，这就是个简单的循环群。
hello world用它加密之后就是：ifmmp xpsme。
当然用这么简单的群去加密，是非常容易被破解的。
这个破解难度也就比“二进制取反”复杂一点：
secret = ~data; // 加密
data = ~secret; // 解密
这两行代码是最简单的加密和解密“算法”，如果这也叫算法的话[捂脸]
二进制取反算法也是个二阶循环群：它的作用是在(0 1)之间对换，它只有2个元素：
{ (0 1), (0 1)^2 = e }.
1，整数对素数的余数，是个循环群。
整数Z对5的余数只有{0, 1, 2, 3, 4}，这5个数字的加法是封闭的。
从1开始，1的倍数对5的余数构成了这个群的元素，1的5倍正好对应到余数0。
1的2倍就是1 1，1的3倍是1 1 1，4倍是1 1 1 1，5倍是1 1 1 1 1 = 5，5%5 = 0。
5个1加到一起，正好除以5的余数是0。
0是加法的单位元（俗称零元），显然加法是个循环群。
乘法实际上也是个循环群。因为1是乘法的单位元，从2开始算：
2^1 = 2, 2 % 5 = 2;
2^2 = 4, 4 % 5 = 4;
2^3 = 8, 8 % 5 = 3;
2^4 = 16, 16 % 5 = 1;
2^5 = 32, 32 % 5 = 2.
整数对5的余数去掉0之后，正好是（乘法的）4阶循环群，它可以用2的幂来生成。
32 = 2^5 = 2^4 x 2 = 16 x 2 = (5n 1) x 2 = 10n 2，所以32 % 5 = 2。
总之只要余数循环到1，那么就开始循环了。
对于整数Z除以素数p的余数去掉0之后形成的集合Zp，Zp里的元素a都符合这公式：
这叫费马定理，是最伟大的法国业余数学家费马提出来的。
费马定理之外还有一个欧拉定理：
欧拉给乘法群Zn的元素个数设计了一个欧拉函数：
对于一个正整数n > 1，整数集对它取余数（去掉0）形成的乘法群Zp的元素个数，跟n的素因子的关系符合上面的欧拉函数。
5本身就是个素数，它的素因子只有它自己（1不是素数），所以它的乘法群的元素个数是5(1-1/5) = 4，正好是{1, 2, 3, 4}.
所以，2^4 = 16 = 3x5 1，根据欧拉定理：余数正好是1。
当然，3^4 = 81 = 16x5 1，4^4 = 256 = 51x5 1，都符合欧拉定理。
2，RSA算法，就是利用了欧拉定理和中国剩余定理。
RSA算法的步骤是：
1）选两个大素数p和q，并且p不等于q，
2）计算它们的乘积n = pq，
3）根据上面的欧拉函数，计算整数Z对n的余数的乘法群Zn的元素个数，
因为n是两个素数的乘积pq，所以元素个数是：
4）选一个与元素个数互素的奇数e，再计算出在对取余数时的乘法逆元d，
也就是e和d要满足公式：
对于两个互素的数e和，它们的最大公约数就是1，也就是满足如下的关系：
两边同时对取余数，左边的第2项被整除，只关注左边第1项和右边就行：
所以，e的乘法逆元d是存在的，并且在取余数之后是唯一的。
5）数对(e, n)就是公钥，数对(d, n)就是私钥。
两个算法：
P(M) = M^e mod n.
S(M) = M^d mod n.
其中的任意一个都是加密算法，而另外一个就是对应的解密算法。
私钥是由所有者持有，公钥是公开的：
所有者（S）对外发信息使用私钥加密，看他消息的人（P）使用公钥解密；
P给S发消息则反过来，P使用公钥加密，这个消息只有S可以使用私钥解密，其他人拿到的消息都是乱码。
公钥和私钥各作用1次，就可以把消息变成明文：P(S(M)) = S(P(M)) = M。
也就是说，M^ed mod n = M mod n.
证明：
因为 ed = 1 mod (p - 1)(q - 1)，
所以 ed = 1 k(p - 1)(q - 1)，其中k是一个整数，
所以
根据费马定理，其中的 M^(p-1) 对素数p的余数是1，1的k(q-1)次方还是1，
所以，最右边在取p的余数之后只剩下了M。
一样可以证明，M^ed在取q的余数之后也只剩下了M。
根据中国剩余定理，M^ed在取n = pq的余数之后，剩下的还是M。
3，中国剩余定理，
两两互素的一组正整数ai，在同余意义下存在唯一的数x，满足如下的方程组：
x = xi mod ai，i = 1, 2, 3, ..., m.
关于同余定理的细节，在我之前的文章里介绍过，就不细说了。
在RSA的场景下，只需要2个方程：
x = M mod p,
x = M mod q，
满足这两个方程的整数，也满足方程x = M mod pq.
RSA的算法还是很简单的，它会把e和n作为公钥发布出去。
私钥d是e关于(p-1)(q-1)在同余意义下的“倒数”（乘法逆元，也叫数论倒数），而n = pq，
所以只要能把n因数分解成p和q，那么很快就可以算出私钥d！
但是，两个大素数的乘积非常难分解，所以暂时RSA还是安全的[捂脸]
PS：RSA算法的步骤，来自算法导论。
,
