非对称加密算法
能实现
机密性
、
身份验证、
抗抵赖性
目标。大部分算法能实现安全密钥交换，所以非对称算法成了公钥基础架构、身份验证、数字签名的底层技术。这些算法都是由传说中最厉害的数学家程序员发明的。
前文说过，非对称加密算法有一对数学相关的、关系奇妙的密钥：
-
-
-
用其中一个加密，只能通过另一个解密，也就是只使用其中一个密钥无法既加密又解密；
-
在非对称加密算法的理论（特别是数学理论）被破解前，可放心使用它们，下面简单描述常见的非对称算法和其他相关知识。
单向函数
单向函数是RSA算法和其他非对称算法的基础。
从数学的角度上来说，单向函数是一种具有下述特点的单射函数：对于每一个输入，函数值都容易计算，但是给出一个随机输入的函数值，算出原始输入却非常困难。
通常会用玻璃来说明单向函数的特性：打碎玻璃很容易（加密），但将碎玻璃重新组合成原来的一整块几乎不可能（解密），但是如果知道这个单向函数的陷门（代表还原玻璃的知识），就能在可接受的时间内解密消息。
🎈有兴趣同学可以研究计算复杂度理论。
非对称加密算法
1/5. Rivest-Shamir-Adleman(RSA)
最流行的非对称算法，事实上的全球标准。
1978年由三位数学家Ron Rivest、Adi Shamir和Leonard Adleman发明。能够用于数字签名、密钥交换和加密。
RSA的安全性基于将一个大整数分解成两个素因子的难度（解密方向），容易的方向是相乘的过程（加密方向）。RSA中的公钥和私钥分别是一对大素数的函数，如果没有私钥，则将密文解密成明文所需的操作与将一个大整数乘积分解成两个素数的难度相当。有人做了一个实验，分解一个 232 位整数需要一组研究人员1,500 多年的计算时间（计算分布在数百台终端上）。有兴趣同学也可以研究扩展欧几里得算法。
① 随机选择两个大素数，p和q；
② 计算这两个数的乘积：n=pq，n用作模（称为钥模）；
③ 随机选择一个整数e作为公钥，满足1<e<(p-1)(q-1)，确保e和(p-1)(q-1)互素；
④ 计算私钥d，满足de-1是(p-1)(q-1)的倍数
⑤ 公钥=(n,e) （ASN.1格式）
⑥ 私钥=(n,d)
⑦要用公钥（n,e）加密消息m，则公式为C=me mod n，C最大值n-1
⑧ 要用私钥（n,d）解密消息c，则公式为M=cd mod n，M最大值n-1
从上面步骤可以看出，RSA算法本身要求明文长度m必须0<m<n（n是密钥长度），还要考虑填充的问题，例如采用1024位密钥和PKCS1Padding，则最大明文长度为（1024bit/8-11Byte=117Byte）。由于有填充，对同样的数据，用同样的密钥进行RSA加密， 每次的输出都会不一样， 但是这些加密的结果都能正确解密。
RSA填充方式和输出
当用户使用公钥加密一条消息时，这条消息就是被一个单向函数编码。这个单向函数包含一个陷门（即还原的知识），通过私钥可了解陷门，了解如何得到最初的素数。因为私钥能找到陷门所以不可泄露。
结合上面对于单向函数和RAS算法特征的了解，我们知道：
ECC
与RSA类似，具有数字签名、安全密钥分发和加密功能。ECC比RSA和其他非对称算法效率高很多，需要的资源也少，广泛用于无线设备和移动电话。
一般来说，密钥越长，密码系统的保护能力越强。要达到同样级别的安全性，ECC的密钥比RSA更短。因为密钥越长，执行数学运算所需的资源就越多。ECC密钥短，所需的资源相对少。换句话说，ECC可以比RSA使用较小的密钥长度并提供相当等级的安全性。
ECC算法依赖于被广泛承认的解决椭圆曲线离散对数问题的困难性上，对应有限域上椭圆曲线的群。
🎈使用离散对数理论的密码系统包括：
Diffie-Hellman
MQV
El Gamal离散对数密码体制
数字签名算法DSA。
常规椭圆曲线
DH第一个非对称的密钥协商算法。SSH（Secure Shell，安全外壳协议）中两台计算机就是通过DH算法握手进程交换会话密钥。
通过DH算法生成一对私钥和公钥，两个人不需要提前建立关系就能通过密钥交换来分发会话密钥——这就是DH算法的主要功能：通过密钥协商来分发密钥。
🎈密钥协商和密钥交换不同：前者无需通过网络传输密钥，而后者需要。
密钥协商（生成会话密钥）过程如下：
①用户Alice用DH算法生成私钥和公钥，用户Bob同样生成自己的私钥和公钥；
②如果Alice要生成和Bob之间的会话密钥，那么Alice将自己的私钥和Bob的公钥（Bob怎样把自己的公钥传送给Alice的无所谓）输入DH算法，生成一个对称密钥；
③Bob将将自己的私钥和Alice的公钥输入DH算法，这时算法会生成和Alice在第②步相同的密钥，这样就可以不通过网络交换就能获得会话密钥，这个过程叫密钥协商。
①选择两个公开的参数，一个素数p和一个整数g，g是p的一个原根（g<p）。
②Alice和Bob要协商一个会话密钥，Alice选择一个随机数a(a<p)作为私钥，然后计算公开密钥A=g^a mod p。而Bob选择一个随机数b(b<p)作为私钥，计算公开密钥B=g^b mod p。
③Alice通过计算公式Ka = (B)^a mod p得到会话密钥。同样Bob通过公式Kb = (A)^b mod p得到会话密钥。
④根据取模运算规则可知，这两个计算产生的结果相同：Ka= (B)^a mod p = (g^b mod p)^a mod p = (g^b)^a mod p = g^(ab) mod p = (g^a)^b mod p = (g^a mod p)^b mod p =(A)^b mod p = Kb，因此相当于双方已经协商了一个相同的会话密钥K=Ka=Kb。
⑤现在攻击者已知g、p、A和B。他必须通过计算离散对数来试图获得密钥a和b。我们都知道计算以一个素数为模的指数相对容易，但计算离散对数却很困难。对于大的素数，在有限域上求解离散对数几乎是不可能的，所以DH密钥协商算法有很高的安全性。
DH算法可用于密钥交换，但它不提供加密和数字签名功能。且DH算法容易受到中间人攻击（某人分别冒充A和B，让AB误认为自己在和正确的人通信，前提是攻击者能截获AB之间的通信流量），因为密钥交换过程无法确认是谁的公钥。抵抗这种攻击的方法是在接受公钥前进行身份验证：在信任双方收到的数据前，彼此先用证书之类的文件证明发送方和接收方的身份。实现身份验证最常见的方法之一是RSA密码系统。
🎈MQV（Menezes-Qu-Vanstone）是一种带认证的密钥协商协议，与DH算法非常相似。用户交换公钥，以创建会话密钥。MQV能抵抗攻击者获得会话密钥，因为攻击者必须拥有用户双方的私钥。
🎈Oakley算法是对DH密钥协商算法的优化，它对Diffie-Hellman交换进行鉴别以对抗中间人的攻击。
可用于数字签名、加密和密钥交换的公钥算法，实际上是Diffie-Hellman的扩展。
El Gamal也是基于有限域上计算离散对数的困难性。（如前所述，离散对数是一个整数要变成另一个整数需要自乘的次数，即bk=g，k为此方程的对数，当数字很大时，计算对数就是不可能完成的任务，可以参见DH算法的数学过程）
El Gamal的缺点是性能。几乎是所有非对称算法中最慢的一个：
数字签名在验证发送者的身份方面具有非常重要的作用，1991年NIST提议设立了DSS这个联邦标准。
DSA是El Gamal和Schnorr两个签名算法的变形，如前所述，该算法的安全性依赖于计算模数的离散对数的难度。
DSA签名和验签步骤如下（参阅NIST相关资料）：
p：L位长的素数。L是64的倍数，范围是512到1024
q：是p - 1的160位素因子
g：g = h^((p-1)/q) mod p，h满足h < p - 1，h^((p-1)/q) mod p > 1
x：私钥，正整数，满足x < q
y：y = g^x mod p ，( p, q, g, y )为公钥
p, q, g可由一组需要签名和验签的用户共享。
s = ( k^(-1) (H(m) + xr)) mod q
u1 = ( H( m ) * w ) mod q
u2 = ( r * w ) mod q
v = (( g^u1 * y^u2 ) mod p ) mod q
若v = r，则验签成功。
🎈H( x )：单向哈希函数，在DSS中为SHA（哈希函数是下一节的内容）。
