各种加密算法与SSL简介

简介

非对称加密

非对称加密：两个密钥，一个公钥，一个私钥，如果用公钥加密的数据只有用私钥才能解密，用私钥加密的数据只有公钥才能解密

特点：算法强度复杂，安全性能高，导致加密速度慢

主要算法：RSA，Elgamal，背包算法，Rabin，D-H，ECC，

对称加密

双方使用同样的密钥加解密，这个是有一个问题的，首先得保证密钥不被泄露，而且需要定期在通信网络的源端和目的端同时修改密钥

密钥越大，加密越强，但加密与解密的过程越慢

主要算法：DES，3DES，IDEA，AES

非对称加密算法介绍

RSA

首先给出两个已知公式

欧拉函数：表示小于n的正整数中，有多少个与n构成互质关系，其中 $n=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{r}^{k_{r}}$ 表示任何一个大于1的整数都可以写成多个质数次方的积
$\phi(n)=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{r}^{k_{r}}(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})...(1-\frac{1}{p_{r}})$
欧拉定理：如果a，n互质，则下面公式成立：
$a^{\phi(n)}=1\,\, mod \,\,n\\$

RSA的公钥私钥选取过程

选取两个不相等的质数p和q
计算乘积n=p*q，其中n转为二进制的长度即为密钥的长度
计算$\phi(n)$

因为p和q为质数，不能分解，因此代入欧拉函数得到：
$\phi(n)=p^{1}q^{1}(1-\frac{1}{p})(1-\frac{1}{q})\\ =(p-1)(q-1)$
在{ $x_{i}|gcd(x_{i},n)=1,x_{i}<n$ }中选取e
计算d
$满足：ed\,\,\%\,\,\phi(n)=1\\ 即：ed=k\phi(n)+1$
计算出一组满足上式的整数解(d,k)
将（n，e）封装为公钥，（n，d）封装为私钥

加解密及私钥解密证明

要加密信息为m ，m为整数（转换）且mn,可以将上信息分割为若干个短信息

加密：$m^{e}=c\,\,（mod\,\,n）$

计算出c，作为密文发送出去

解密：$c^{d}=m\,\,（mod\,\,n）$

计算出m，即为明文

证明过程如下：

由加密的式子可得：

$m^{e}=kn+c\\ c=m^{e}-kn$

将c代入解密的式子，得到：

$(m^{e}-kn)^{d}=m \,\,（mod\,\,n）\\ 使用二项式展开如下： \\ C_{d}^{0}(m^{e})^{0}(-kn)^{d}+C_{d}^{1}(m^{e})^{1}(-kn)^{d-1}+...+C_{d}^{d}(m^e)^{d}=m\,\,（mod\,\,n）\\ 上式只有一项不可能是n得倍数，因此对n取模的结果简化后如下：\\ m^{ed}=m\,\,（mod\,\,n）$

由$ed\,\,\%\,\,\phi(n)=1$ 即：$ed=h\phi(n)+1$ ,上式变为：

$m^{h\phi(n)+1}=m\,\,（mod\,\,n）$

对于上式，如果m和n互质，根据欧拉定理：

$m^{\phi(n)}=1\,\,（mod\,\,n）\\ 而m^{h\phi(n)+1}\,\,\%\,\,n=(m^{h\phi(n)}\,\,\%\,\,n\,\,*\,\,m\,\,\%\,\,n)\,\,\%n=m\,\,\%\,\,n\\ 即m^{h\phi(n)+1}=m \,\,（mod\,\,n）\\ 得证$

如果m和n不互质，即说明m和n存在非1的公因子，由于n=pq，且p，q均为质数，说明n的非1因子是p，q；

那么m必然是p得倍数或者是q得倍数，设$m=kp$

由于m<n，可得k<q，即k与q互质，那么kp和q互质，由欧拉定理得：

$(kp)^{\phi(q)}=1 \,\,（mod\,\,q）\\ 即(kp)^{q-1}=1 \,\,（mod\,\,q）\\ 那么m^{h\phi(n)+1}\,\,\%\,\,q= \big((kp)^{q-1}\big)^{h(p-1)}*kp\,\,\%\,\,q \\ =\bigg(\big((kp)^{q-1}\big)^{h(p-1)}\,\,\%\,\,q\,\,*\,\,kp\,\,\%q\bigg)\,\,\%\,\,q\\ =kp\,\,\%\,\,q\\ 即：(kp)^{ed}=kp \,\,（mod\,\,q）\\ 即：(kp)^{ed}=tq+kp\\ 两边同除p：k^{ed}p^{ed-1}=\frac{tq}{p}+k\\ 左边为整数，那么右边一定为整数，而要使右边为整数，\\ 那么一定存在整数t^{'}使得tq=t^{'}p,又q，p为质数，即有t=t^{'}p\\ 上式可写为：(kp)^{ed}=t^{'}pq+kp\\ 即：m^{ed}=t^{'}n+m\\ 得证$

RSA算法的可靠性：

公钥开放，也就是说如果知道了d，私钥就泄露了

$ed\,\,\%\,\,\phi(n)=1\\ \phi(n)=(p-1)(q-1)\\ n=p q$

由上面第一个式子，要想知道d，必须知道$\phi(n)$ ,而$\phi(n)$由第二个式子可知，与p和q相关，由第三个式子知道p和q是n的因式分解

因此如果想破解RSA算法，必须知道满足$pq=n$的所有质数对(p,q)，即如果高效解决大整数的因式分解就能快速破解RSA算法

D-H密钥交换

a为Alice的私钥，b为Bob的私钥，公开的时g，p，A，B，密钥为K

原理就是通过自己的私钥运算，并发送公钥给对方，通过运算获取相同的密钥，使用对称加密来加密明文

证明

$B^a \,\,mod\,\,p=(g^b\,\,mod\,\,p)^a\,\,mod\,\,p=g^{ba} \,\,mod\,\,p=K\\ A^b\,\,mod\,\,p=(g^a\,\,mod\,\,p)^b\,\,mod\,\,p=g^{ab}\,\,mod\,\,p=K$

可靠性

要知道K，需要知道$g^{ab}\,\,mod\,\,p$ ,即需要知道a和b，而a和b分别由下式得到：

$A=g^a\,\,mod\,\,p\\ B=g^b\,\,mod\,\,p$

上式是离散对数问题，目前没有快速求解离散对数的算法

ElGamal加密算法

实质上就是将D-H算法变为非对称加密算法

密钥生成

选择素数p，两个随机数g和x，满足g,x<p，

计算 y=$g^x\,\, mod \,\,p$

私钥为x

公钥为y,g,p,

加密

随机选择k，满足k与p-1互素

$a=g^k\,\,mod\,\,p\\ b=y^k M \,\,mod\,\,p$

其中M为明文，（a,b)为密文

解密

$M=b/a^x\,\,mod\,\,p$

可靠性

同D-H算法，是离散对数难题

ECC加密算法

椭圆曲线：

关于X轴对称
画一条直线跟椭圆曲线相交，它们最多有三个交点

椭圆曲线上的运算：

加法运算：

设椭圆曲线上有两点，A和B，作这两点的直线与该曲线相交于第三点C，将C点关于X轴对称得到D点

记D=A+B

当A和B重合时，即作A点的切线，与曲线相交于第二点(B点)，然后关于X轴对称得到C点

记 C=A+A

乘法运算

转为加法运算

$kA=\underbrace{A+...A+A}_{k}$

如下图所示：

椭圆曲线上点的阶：

P为椭圆曲线上的点，如果nP=无穷远点，n取最小整数，即为P的阶

无穷远点：如果椭圆曲线上的两点A，B的连成的直线不与椭圆曲线交于第3点，则有A+B=无穷远点

椭圆曲线在密码学中的应用

对于实数域上的椭圆曲线，做如下变化：

实数域中取整数点
对整数点取模处理

如下，对一椭圆曲线 mod 17的结果

对于椭圆曲线中的运算仍然成立，如下图所示，描述C=A+B的过程

有限域椭圆曲线上的加解密

用户A作如下处理：

在椭圆曲线上选取一基点G，椭圆曲线$E_{p}(a,b)$ ,选取整数k作为私钥（k小于n，n为G的阶），

计算K=kG

将G，K，$E_{p}(a,b)$ 作为公钥公开

用户B要将明文M传给A，作如下处理：

随机产生一个随机数r，（r<n)

计算点 $C_{1}=M+rK\,\,\,\,\,\,\,,\,\,\,\,C_{2}=rG$

将 $C_{1},C_{2}$ 传给用户A

用户A接收到 $C_{1},C_{2}$ 后作如下处理：

$M=C_{1}-kC_{2}$

证明：

$C_{1}-kC_{2}\\=M+rK-krG\\=M+rK-rK\\=M$

可靠性

已知K和G，如何求解k的问题：对于椭圆曲线上的kG运算是不可逆的，这是椭圆曲线上的离散对数问题，目前无法找到快速解决该问题的方法。

实际的函数如下：

Point result = P;
for (int i = 0; i < k - 1; i++)
    result = add(P, result);
sendTo((result, P), others);

有个问题：具体的kG如何计算？，为什么不可逆？
以下只是猜测，并没有找到什么确切的答案
原因：比如k=17，加密的时候因为知道k，作如下运算，由G得到2G，由2G得到4G，由4G得到8G，由8G得到16G，16G再和1G运算得到17G，总共走了5步；而如果破解的话，需要一步一步遍历，如果作倍数运算可能会漏掉k，导致永远找不到，因此只能有1G得2G，由2G得3G，…直到17G，最后的结果是走了17步；而如果k很大，结果会更明显；已知k的运算时间复杂度为O(log n)，未知k的时间复杂度为O(n)
更者，如果17G不等于17G（即不同的叠加出现不同的17G)，那么就有更多的可能了

背包算法

超递增背包：其中的每一项都大于它之前所有项之和

记超递增背包为{ $a_{1},a_{2},…,a_{k}$ }

选取N满足N与背包中的任何一个数没有公因子

并取一个模数M，满足该模数比背包中的所有数的和都大

对背包中的每个元素作如下运算：

$c_{i}=a_{i}N\,\,mod\,\,M$

将修改后的背包{ $c_{1},c_{2},...$ }作为公钥，原始的超递增背包{ $a_{1},a_{2},...$ }作为私钥

加密

对于要加密的二进制消息，按照背包个数分组，然后将每组二进制消息中1对应的背包元素相加，将每组最后相加的结果{ $b_{1},b_{2}...$ }作为密文发送出去

解密

计算$N^{-1}$ : 满足$N\,\,N^{-1}\,\,mod\,\,M=1$

对密文做如下运算

$b_{i}N^{-1}\,\,mod\,\,M=a_{i}+a_{j}+...$

最后将 $a_{i},a_{j}$ 在背包中的位置映射到二进制上，即得到了二进制消息

证明

对于一组二进制消息来说，假设第i,j…等位上为1，加解密的运算如下：

$(a_{i}N\,mod\,M+a_{j}N\,mod\,M+...)N^{-1}\,mod\,M\\ =(a_{i}NN^-1\,mod\,M+a_{j}NN^{-1}\,mod\,M+...)\,mod\,M\\ =(a_{i}+a_{j}+...)\,mod\,M\\ =a_{i}+a_{j}+...$

前提条件M的选取使得倒数第二行求和的结果和最后一行相等，超递增背包使得最后一个等式唯一

可靠性

公钥为{ $c_{1},c_{2},...$ }，M，N，得到密文后，可以将每组的 $a_{i}+a_{j}+…$ 的和s求出来

由公钥的求解方法，我们可以得到一个矩阵，矩阵的第i行表示私钥中第i个元素所有可能的取值，即私钥一定由下面的矩阵中每一行选取一个值组成：

$\begin{bmatrix} a_{1}^{1} & a_{1}^{2} & a_{1}^{3}&...\\ a_{2}^{1} & a_{2}^{2} & a_{2}^{3}&...\\ . & .& .&...\\ a_{k}^{1} & a_{k}^{2} & a_{k}^{3}&...\\ \end{bmatrix}$

需要k重for循环进行遍历，每次选取元素时需满足该背包为超递增背包，选取完k个元素后，将得到的背包用于计算密文，如果所有的密文均可以由得到的背包中的元素组成，则该背包为密钥

时间复杂度为$O(m^k)$，m为矩阵的宽

举个例子：

取一个超递增序列{2,3,6,13,27,52}，N=31，M=105

$2*31\%105=62\\ 3*31\%105=93\\ 6*31\%105=81\\ 13*31\%105=88\\ 27*31\%105=102\\ 52*31\%105=37$

公钥为{62,93,81,88,102,37}，N=31，M=105

加密过程：

需要传递的明文为011000110101101110，按照背包的大小分为三组：011000 110101 101110

011000 对应 93+81=174

110101 对应 62+93+88+37=280

101110 对应 62+81+88+102=333

密文为{174，280，333}

解密过程：

求解$N^{-1}=61$

$174*61 \,\%\,105=9=3+6 \,\,\,\,\,\,\,\,\,\,\,\,\,对应011000\\ 280*61\,\%\,105=70=2+3+13+52 \,\,\,\,\,\,\,\,\,\,\,\,\,对应110101\\ 333*61\,\%\,105=48=2+6+13+27 \,\,\,\,\,\,\,\,\,\,\,\,\,对应101110\\$

对于超递增背包，上面求解的结果都会唯一对应一组背包中的数字

Rabin

选取两个素数p,q，满足同余3模4. 作为私钥，n=pq作为公钥

加密消息M：

$C=M^2\,\,mod\,\,n$

解密：

由于n=pq，由中国剩余定理得到$M^2=C\,\,(mod\,\,n)$等价为：

$M^2=C \,\,(mod\,\, p)\\ M^2=C\,\,(mod \,\,q)\\$

引入符号Legendre$\left [ \frac{a}{p} \right ]$：假设p为一个奇素数，a为一个整数，那么有

$\left [ \frac{a}{p} \right ]=a^{(p-1)/2}\,\,(mod\,\,p)$

对于同余方程式$x^2\equiv a(mod\,\,q)$，如果Legendre符号$\left [ \frac{a}{p} \right ]=1$，且$p\equiv3(mod\,\,4)$

则方程式的解为 $\pm\,\,a^{\frac{p+1}{4}}$

由模n二次剩余问题的定理1可以证明$\left [ \frac{C}{p} \right ]=1$,$\left [ \frac{C}{q} \right ]=1$

则4个解分别为：

$m_{1}=C^{\frac{p+1}{4}}\,\,mod\,\,p\\ m_{2}=(-C^{\frac{p+1}{4}})\,\,mod\,\,p\\ m_{3}=C^{\frac{q+1}{4}}\,\,mod\,\,q\\ m_{4}=(-C^{\frac{q+1}{4}})\,\,mod \,\,q$

从 $m_{1},m_{2}$ 中选择一个，从 $m_{3},m_{4}$ 中选择一个，有4种组合方式，由之前的等价公式合并，利用中国剩余定理求解M的值

$\left\{\begin{matrix} M=m_{1}\,\,mod\,\,p\\ M=m_{3}\,\,mod\,\,q \end{matrix}\right.\\ \,\,\\ \,\,\\ \left\{\begin{matrix} M=m_{1}\,\,mod\,\,p\\ M=m_{4}\,\,mod\,\,q \end{matrix}\right.\\ \,\,\\ \,\,\\ \left\{\begin{matrix} M=m_{2}\,\,mod\,\,p\\ M=m_{3}\,\,mod\,\,q \end{matrix}\right.\\ \,\,\\ \,\,\\ \left\{\begin{matrix} M=m_{2}\,\,mod\,\,p\\ M=m_{4}\,\,mod\,\,q \end{matrix}\right.$

可以得到4个值，其中有一个就是M，需要在消息加密前加入一个已知的标题，以确定M

可靠性

基于求合数n的模平方根难度，解密过程在已知合数为pq的条件下，使用一种数学方法来得到M

对称加密算法

DES

DES是基于组块的加密算法，输入输出均为64位长度

加密过程：

密钥K转为二进制64位，根据表格PC-1变换为56位，拆为左右两半部分 $C_{0}和D_{0}$ ，每半边28位
对 $C_{0}和D_{0}$ 进行左移，对于前一个来说左移位数按照1，1，2，2，2，2，2，2，1，2，2，2，2，2，2，1进行，最后得到 $C_{1},D_{1},…,C_{16},D_{16}$ 16组子密钥
将 $C_{i},D_{i}$ 拼接，并对应到表格PC-2，得到 $K_i$ 为48位，$1\leqslant i \leqslant 16$
将明文M转为二进制，并按照IP表变换，记为ip，将ip的左半部分32位记为 $L_{0}$ ，右半部分32位记为 $R_{0}$
使用函数$f$执行16次迭代：
$L_{n}=R_{n-1}\\ R_{n}=L_{n-1}\bigoplus f(R_{n-1},K_{n})$
具体$f$中先将 $R_{n-1}$ 从32位扩展为48位，按照表E；然后进行异或运算： $E(R_{n-1})\bigoplus K_{n}$ ，记为 $B_{i}$ ;再将 $B_{i}$ 进行S运算，即 $S_{i}(B_{i})$ ， $S_{i}$ 的运算原理是计算 $B_{i}$ 中第一位和最后一位的组成的二进制值作为i，中间的二进制值作为j，在 $S_{i}$ 中对应的第i行第j列的值转为二进制，最后输出的 $S_{i}(B_{i})$ 再由表P转为32位的输出
将得到的 $R_{16}和L_{16}$ 逆转结合得到一个64位的区块： $R_{16}L_{16}$ ；将其按表IP-1输出写为16进制即为明文加密后的结果