对称加密与非对称加密，以及RSA的原理

 

一 ， 概述

在现代密码学诞生以前，就已经有很多的加密方法了。例如，最古老的斯巴达加密棒，广泛应用于公元前7世纪的古希腊。16世纪意大利数学家卡尔达诺发明的栅格密码，基于单表代换的凯撒密码、猪圈密码，基于多表代换的维吉尼亚密码，二战中德军广泛使用的恩格玛加密机…但最终都找到了有效的破解算法。

现代密码学的诞生标志是1977年1月由美国国家标准局公布的数据加密标准(Data Encryption Standard，DES)。
在经过20多年之后，为适应现代的安全要求，2000年美国国家和标准技术协会筛选和评测出了被称为AES(Advanced Encryption Standard)的加密算法作为新的加密标准。目前，AES已被广泛使用，且未发现致命缺陷。到目前为止，AES是一个安全的加密算法。

然而，在加密算法之外，面临一个问题，那就是：秘钥的分发。就是说，解密方如何获得加密方的秘钥呢？ 从而出现了：对称加密和非对称加密。

二，对称加密和非对称加密

1. 对称加密

对称加密指的就是加密和解密使用同一个秘钥，所以叫做对称加密。对称加密只有一个秘钥，作为私钥。
常见的对称加密算法：DES，AES，3DES等等。

2. 非对称加密

非对称加密指的是：加密和解密使用不同的秘钥，一把作为公开的公钥，另一把作为私钥。公钥加密的信息，只有私钥才能解密。私钥加密的信息，只有公钥才能解密。
常见的非对称加密算法：RSA，ECC

3. 区别

对称加密算法相比非对称加密算法来说，加解密的效率要高得多。但是缺陷在于对于秘钥的管理上，以及在非安全信道中通讯时，密钥交换的安全性不能保障。所以在实际的网络环境中，会将两者混合使用.

例如针对C/S模型，

1. 服务端计算出一对秘钥pub/pri。将私钥保密，将公钥公开。
2. 客户端请求服务端时，拿到服务端的公钥pub。
3. 客户端通过AES计算出一个对称加密的秘钥X。 然后使用pub将X进行加密。
4. 客户端将加密后的密文发送给服务端。服务端通过pri解密获得X。
5. 然后两边的通讯内容就通过对称密钥X以对称加密算法来加解密。

三，RSA原理

我们先来看这样一些基础知识，并且以下我们讨论全都是整数：

整数运算

在整数运算中 我们定义一个整数x$x$x，那么他的负数为-x$x$x，并且有x$x$x+(-x$x$x)=0；

他的倒数为x−1$x^{-1}$x−1 , 并且有x×x−1$xtimes x^{-1}$x×x−1 =1;

同余运算

有整数a，b，正整数m。 假如a除以m余b。我们称为a模m同余b，模数为m。并且记为a≡b(modm)$aequiv bpmod{m}$a≡b(modm) ,例如10除以3余1

我们称10模3同余1，记为10≡1(mod3)$10equiv 1pmod{3}$10≡1(mod3) 。

我们分别讨论模数为合数和质数情况下，基于同余运算的负数和倒数。

1. 当模数为合数n$n$n时

简单起见，我们讨论当n$n$n为10的情况,10是两个质数乘积

当模数为10的时候，参与运算的都是小于10的数。因为大于10的数除模取余之后都会小于10，所以只需要考虑小于模的数。

那么在同余运算中

一个小于10的数a，他的负数x$x$x是什么？ 也就是说使得(a+x)≡0(mod10)$(a+x)equiv 0pmod{10}$(a+x)≡0(mod10) ; 那就是n−a$n-a$n−a,即x=n−a$x=n-a$x=n−a。这里的x$x$x就像是常规运算下的-a。常规运算下a+(−a)=0$a+(-a)=0$a+(−a)=0,我们说−a$-a$−a是a$a$a的负数，这里(a+x)≡0(mod10)$(a+x)equiv 0pmod{10}$(a+x)≡0(mod10)，我们说x$x$x是a$a$a的负数。;

有a+(n−a)=a+(−a)+n=n≡0(modn)$a+(n-a)=a+(-a)+n= nequiv 0pmod{n}$a+(n−a)=a+(−a)+n=n≡0(modn) 。 当n=10$n=10$n=10的时候 ，有如下表

那么，a$a$a的倒数a−1$a^{-1}$a−1是什么呢？ 它要使得a×a−1$atimes a^{-1}$a×a−1在模数为n的情况下等于1，即a×a−1≡1(modn)$atimes a^{-1}equiv 1pmod{n}$a×a−1≡1(modn)

当n=10$n=10$n=10的时候我们会发现，对于有的数我们可以找到它的倒数，有的数却找不到

例如当a=3$a=3$a=3，我们可以找到7，使得$3times7= 21 equiv 1pmod {10} $ ;

而当a=4的时候，我们有4×0=0$4times0 = 0$4×0=0，4×1=4$4times 1= 4$4×1=4，4×2=8$4times2 = 8$4×2=8，4×3=12$4times3= 12$4×3=12，4×4=16$4times4 = 16$4×4=16，4×5=20$4times5 = 20$4×5=20，4×6=24$4times6 = 24$4×6=24，4×7=28$4times7 = 28$4×7=28，4×8=32$4times8 = 32$4×8=32，4×9=36$4times9 = 36$4×9=36，在模10的情况下，都不会等于1。

我们对于所有小于10的a$a$a都找他的倒数a−1$a^{-1}$a−1，有下表

有什么规律呢？

数学界已证明：当a&lt;n$a&lt;n$a<n时，只有当a$a$a和n$n$n互质才能找到a−1$a^{-1}$a−1。 同时还有以下结论，当n=p×q$n=ptimes q$n=p×q ,且p$p$p和q$q$q都为质数时，所有小于n$n$n的数中，能找到倒数的个数为(p−1)×(q−1)$(p-1)times (q-1)$(p−1)×(q−1)个。如果n有更多的质因子，那么计算会更复杂点。

我们把所有小于n，并且能和n互质的数的总个数记为一个函数φ(n)$varphi(n)$φ(n) ，这个函数叫做欧拉函数。例

即当n=p×q$n=ptimes q$n=p×q ,且p$p$p和q$q$q都为质数时，有φ(n)=(p−1)×(q−1)$varphi(n)=(p-1)times(q-1)$φ(n)=(p−1)×(q−1), 那么就有φ(10)=(2−1)×(5−1)=4$varphi(10)=(2-1)times(5-1)=4$φ(10)=(2−1)×(5−1)=4

同时这些数还有以下两个有趣的情况

1. 这些数之间进行互乘的同余运算，结果还是这些数。

   例如对于1：1×1≡1(mod10)$1times1equiv 1pmod{10}$1×1≡1(mod10), 1×3≡3(mod10)$1times3equiv 3pmod{10}$1×3≡3(mod10), 1×7≡7(mod10)$1times7equiv 7pmod{10}$1×7≡7(mod10), 1×9≡9(mod10)$1times9equiv 9pmod{10}$1×9≡9(mod10)

   对于3：3×1≡3(mod10)$3times1equiv 3pmod{10}$3×1≡3(mod10), 3×3≡9(mod10)$3times3equiv 9pmod{10}$3×3≡9(mod10), 3×7≡1(mod10)$3times7equiv 1pmod{10}$3×7≡1(mod10), 3×9≡7(mod10)$3times9equiv 7pmod{10}$3×9≡7(mod10)

   对于7：7×1≡7(mod10)$7times1equiv 7pmod{10}$7×1≡7(mod10),7×3≡1(mod10)$7times3equiv 1pmod{10}$7×3≡1(mod10),7×7≡9(mod10)$7times7equiv 9pmod{10}$7×7≡9(mod10),7×9≡3(mod10)$7times9equiv 3pmod{10}$7×9≡3(mod10)

   对于9：9×1≡9(mod10)$9times1equiv 9pmod{10}$9×1≡9(mod10),9×3≡7(mod10)$9times3equiv 7pmod{10}$9×3≡7(mod10),9×7≡3(mod10)$9times7equiv 3pmod{10}$9×7≡3(mod10),9×9≡1(mod10)$9times9equiv 1pmod{10}$9×9≡1(mod10)

   如果一些数在互相运算之后，得到的结果还是这些数中，我们称这些数在这个运算条件下具有封闭性。

2. 对这些数进行求幂运算，并且再模10，结果如下表

   a$a$a	1	3	7	9
   a0$a^0$a0	1	1	1	1
   a1$a^1$a1	1	3	7	9
   a2$a^2$a2	1×1=1$1times1=1$1×1=1	3×3=9$3times3=9$3×3=9	7×7=9$7times7=9$7×7=9	9×9=1$9times9=1$9×9=1
   a3$a^3$a3	1×1×1=1$1times1times1=1$1×1×1=1	3×3×3=7$3times3times3=7$3×3×3=7	7×7×7=3$7times7times7=3$7×7×7=3	9×9×9=9$9times9times9=9$9×9×9=9
   a4$a^4$a4	1×1×1×1=1$1times1times1times1=1$1×1×1×1=1	3×3×3×3=1$3times3times3times3=1$3×3×3×3=1	7×7×7×7=1$7times7times7times7=1$7×7×7×7=1	1×1×1×1=1$1times1times1times1=1$1×1×1×1=1

   其中，

   • 我们规定a0≡1(mod10)$a^0equiv 1pmod{10}$a0≡1(mod10)

   • 所有aφ(10)$a^{varphi(10)}$aφ(10)的结果都为1,即有aφ(n)≡1(mod10)$a^{varphi(n)}equiv 1pmod{10}$aφ(n)≡1(mod10)。(根据前面的介绍可知这里的φ(10)=(2−1)×(5−1)=4$varphi(10)=(2-1)times(5-1)=4$φ(10)=(2−1)×(5−1)=4)

   • 对于3和7来说，他们的a0$a^0$a0、a1$a^1$a1、a2$a^2$a2、a3$a^3$a3刚好把1,3,7,9各得到了一遍。到a4$a^4$a4时刚好又回到了1，如果大于4之后，又会开始循环

   在模n的情况下一定能找到一个数g$g$g,使得g0$g^0$g0、g1$g^1$g1、g2$g^2$g2、…gφ(n)−1$g^{varphi(n)-1}$gφ(n)−1刚好把所有与n互质并且小于n的数各得到一遍。我们把满足这种条件的数称为 生成元。

2. 当模数为质数p$p$p的时候

当模p$p$p为质数的时候，我们假设p=7$p=7$p=7时。

同样求小于 p$p$p 的数 a$a$a 的负数 x$x$x 使得(a+x)≡0(mod10)$(a+x)equiv 0pmod{10}$(a+x)≡0(mod10)有如下表