https加密是对称还是非对称（群论与RSA加密算法）

#创作挑战赛#

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算法的步骤，来自算法导论。

,