非对称加密 RSA加密算法原理简述

非对称加密：

非对称加密是与对称加密完全相反的概念，对称加密指的是加密解密使用的是同样的密钥Key，如流加密，块加密，一次性密码本之类的。而非对称加密，使用加密Key叫公钥，解密用的是私钥。

至于为什么要这样做呢？因为这样可以极大的方便看密钥的管理。假设一个银行机构，如果使用对称加密，一个用户一个Key，千万用户千万Key，根本无法管理，而使用非对称加密，一个解密用的私钥就能解决一切问题。

另外，与对称密钥加密相比，公钥加密无需共享的通用密钥，减少了很多不必要的麻烦。

RSA：

1977年，由三位麻省理工的人提出，RSA取自他们三人名字的开头。

1997年，披露了一位英国政府通信总部的数学家先与三人发现，但一经发现直接被列为机密，只到1994年才被披露。

数学原理：

m=明文 c=密文 N=随机数 e=公钥 d=密钥

依旧以两个大质数相乘得到的大数难以被因式分解为核心。

核心：

m^e mod N = c (明文m用公钥e加密并和随机数N取余得到密文c)

c^d mod N = m　(密文c用密钥解密并和随机数N取余得到明文m)

因此，两者合并就是：m^(e^d) mod N = m, 也就是：m^(ed) mod N =m

问题是，如何敲定这个解密用d呢？这就需要引入一个概念叫：欧拉函数 φ ( n ) ：小于或等于n的正整数中与n互质的数的数目。

比如φ ( 8 )，1 2 3 4 5 6 7，符合这个条件的是：1 3 5 7，因此φ ( 8 )=4

因此我们可以得知，φ ( n ) 如果n为质数，φ ( n ) = n - 1

而且φ ( n )还符合φ ( a*b ) =φ ( a ) *φ ( b )

此外，还得借助欧拉定理：

因此计算e的模返元素d的方式如下：

1.选取两个大质数P1，P2，P1*P2=N，并能得到φ ( N )

2.更具欧拉定理能得知，ed=1（mod φ ( n )）

3.等价于ed-1 = k φ ( n )

4.于是等价于求解二元一次方程 ex +φ ( n )y = 1

求得一组解中的x便为d

步骤：

具体还是来看看步骤，举个栗子，假设Alice和Bob又要相互通信，这次用的是非对称加密。

1.Alice 随机取大质数P1=53，P2=59，那N=53*59=3127，φ ( n )=3016，取一个e=3，计算出d=2011。

2.只将n=3127，e=3 作为公钥传给Bob。

3.假设Bob需要加密的明文m=89，c = 89^3 mod 3127=1394，于是Bob传回c=1394

4.Alice使用c^d mod n = 1394^2011 mod 3127，就能得到明文m=89。

回过头来看看，攻击者能截取到n=3127，e=3，c=1394，然而他仍然无法不通过d来进行密文解码。