安全的登录身份认证分析（二） - Be4r的博客

非对称加密

1976年，美国学者Dime和Henman为解决信息公开传送和密钥管理问题，提出一种新的密钥交换协议，允许在不安全的媒体上的通讯双方交换信息，安全地达成一致的密钥，这就是公开密钥系统。
与对称加密算法不同，非对称加密算法需要两个密钥：公开密钥（publickey）和私有密钥（privatekey）。公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。

加解密逻辑

A、B之间如需进行数据交互, 使用非对称加密方式逻辑将会如下形式：

A 生成公私钥对，并将公钥向B公开
B 需要向A发送数据时，需使用A公开的密钥进行加密，并将密文传输给A
A 使用自身拥有的密钥(私钥)将密文解密，获取得到B向A传输的信息
_{数据交互示意流程图}

RSA加密算法

我们在上一篇文中提到了安全的登录身份认证使用AES加密传输。那我为什么要在这里提出一个完全不同的加密算法RSA呢。因为对称加密是指采用单密钥，可同时用作信息的加密和解密。当我们获取到本次加密使用的密钥时，我们就能轻易地解密出密文所表示的含义。我们在这里需要明确一点，没有绝对的安全，我们能做到的只是尽可能地提高攻击者想要获取有价值信息的难易程度，即攻击者想要获取价值信息需要付出的代价。当攻击者认为他想要获取的信息与他需要付出的价值不相符时，我们就认为做到了一定程度的安全。
因此，在这里提出RSA加密，并不是否认之前的AES的可用性。

什么是RSA

RSA是第一个比较完善的公开密钥算法，它既能用于加密，也能用于数字签名。RSA以它的三个发明者Ron Rivest, Adi Shamir, Leonard Adleman的名字首字母命名，这个算法经受住了多年深入的密码分析，虽然密码分析者既不能证明也不能否定RSA的安全性，但这恰恰说明该算法有一定的可信性，目前它已经成为最流行的公开密钥算法。

RSA详解

RSA的安全性是在于大数分解的难度。因其为非对称加密算法，存在公私钥对，其公钥和私钥是一对大素数函数。想要从公钥和密文中破解出明文，其难度相当于是分解两个大素数的积。而分解大素数积是公认的数学大难题，在没有足够算力支持下，RSA的破解将会存在重重困难。

欧拉函数

在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。此函数以其首名研究者欧拉命名(Euler’s totient function)，它又称为Euler’s totient function、φ函数、欧拉商数等。例如φ(8)=4，因为1,3,5,7均和8互质。
RSA算法使用的便是欧拉函数的一个特例，如果N能够分解为两个互质整数积：$$N=pq$$
我们即可计算得欧拉函数值：$$φ(N)=φ(p)φ(q)=(p-1)(q-1)$$
举个例子:φ(35)=φ(5)φ(7)=(5-1)(7-1)=24

模反元素

如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。$$ab\equiv 1(modn)$$
这时，b就叫做a的“模反元素”。
欧拉定理证明当 a,n 为两个互素的正整数时，则有$$a^{φ(n)}≡1(modn)$$
其中 φ(n) 为欧拉函数（小于等于 n 且与 n 互素的正整数个数）。
上述可分解为$$a^{φ(n)}=a⋅a^{φ(n)−1}≡1(modn)$$，其中 a^φ(n)−1即为a关于模n的模反元素。
举个例子:
求整数 3 对同余 11 的模逆元素 x:$$x\equiv 3^{-1}(mod11)$$
转换可得:$$3x\equiv 1(mod11)$$
在小于11的整数范围内，可以找到满足该同余等式的x值为4，如下式所示:$$3(4)=12\equiv 1(mod11)$$
并且，在上述整数范围内不存在其他满足此同余等式的值。因此，3对同余11的模反元素为4。

生成公私钥对

随机生成大素数p和q，p与q不相等，计算得N=pq，p、q保密，不能泄露
根据欧拉函数，求得φ(N)=φ(p)φ(q)=(p−1)(q−1)
选择一个小于φ(N)的整数e，使e与φ(N)互质。并求得e关于φ(N)的模反元素，命名为d,求d令 ed≡1(modφ(N))，即d≡e^-1(modφ(N))。(模反元素存在，当且仅当e与φ(N)互质)

通过上述三步，可得公钥:(N,e),私钥:(N,d)。公钥是公开的，可供加密的，私钥将用来私有解密。

加密数据

假设客户端要向服务器发送消息m，服务器的公钥是N和e。客户端将消息m转换为一个小于N的非负整数n，比如可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如信息非常长的话，可以将这个信息分为几段，然后将每一段转换为n。用下面这个公式他可以将m(明文)加密为c(密文)：$$m^{e}\equiv c(modN)$$

解密数据

得到消息密文c后，可以利用私钥d来解码。可以用以下这个公式来将c转换为m:$$c^{d}\equiv m(modN)$$

逻辑总述

我们上述所说的所有内容可以化整为下述图表：

_{逻辑综述示意图}

实例解释

我们继续用两个经典人物Alice、Bob来完成这样一个流程。
第一步：获取两个不相等的质数p,q,Alice获取了p=61,q=53,计算得：N=pq=61*53=3233
N的长度即是密钥的长度。3233的二进制为110010100001，长度为12位，则密钥长度为12位。我们实际使用中，密钥长度应当在2048位及以上。
第二步：根据φ(N)=φ(p)φ(q)=(p−1)(q−1)得出φ(3233)=60*52=3120
第三步：取1<e<φ(N),使得e与φ(N)互质。Alice取e=17。
第四步：计算e对φ(N)的模反元素d，可以使得ed≡1(modφ(N))，即ed-1=kφ(N)，想要计算出d，实际上就是求解一个二元一次方程ex+φ(N)y=1，即17x+3120y=1。这里我们需要用扩展欧几里得算法求解，可得出结果(x,y)=(2753,-15)，得出d=2753。
第五步：最终Alice得出公钥(3233,17),私钥(3233,2753)。
第六步：
第七步：
第八步：