公钥加密算法/哈希算法

公钥加密算法 也叫非对称加密，它在加密和解密时使用的是不同的密钥，具有这样的特征：

• 有一对密钥 a 和 b ，满足 a ≠ b

• 用密钥a加密的数据只能用b进行解密，a自身无法解密，反之亦然

• 只知道其中一个密钥，无法推导出另一个

• 把其中一个可以公开的叫做公钥，另一个不能公开的叫做私钥

  
  
  WechatIMG30.png

最常见的公钥加密算法是RSA公钥加密算法，也是签名中普遍使用的算法。其数学原理如下：

• 选定两个超大的素数p, q，并计算他们的乘积n = p * q
• 计算欧拉函数 φ(n) = φ(p) * φ(q) = (p-1) * (q-1)
• 随机选定一个数e，满足1 < e < φ(n) ，且与φ(n)互质
• 根据扩展欧几里得算法计算e对于φ(n)的乘法逆元d ，e * d = 1 mod φ(n)
• {n, e} 和 {n, d} 分别组成这个算法的一对密钥
• 对于给定明文p, 若使用{n, e} 作为加密密钥，其密文计算方法为 c = p ^ e mod n
  这是一个单向函数，已知{c, n, e} 无法计算出p
• 相应地需要使用{n, d}进行解密， p = c * d mod n,这是上一步加密函数的逆函数
• 两组密钥中n是相同的，那么如果已知了e和d其中的一个，想要计算另一个，必须知道φ(n)，也就是必须先将n分解质因数，得到p和q，但由于n的值非常大，这样的计算量基本上是不可能的，也就保障了算法的安全性.

理论上 {n, e} 和 {n, d} 可以互换，任何一个都可以是公钥或者私钥，加密和解密的函数也可以互换。但实践中，一般固定设置e=65537(0x10001)，相当于公开的一个约定，这样一来{n, e}就只能作为公钥使用。

哈希算法
也叫散列或者摘要算法，对一段任意长度的数据，通过一定的映射和计算，得到一个固定长度的值，这个值就被称为这段数据的哈希值(hash)。给定一个哈希算法，它一定具有以下特征：

• 哈希值不同的两段数据绝对不同
• 相同的数据计算出的哈希值绝对相同
• 由于哈希值是固定长度， 也就意味着哈希值的数量是有限的。而任意数据都可以计算出一个哈希值，计算哈希的过程，相当于无限集到有限集的映射。因此哈希值相同，对应的原始数据不一定相同，如果不同，则称这两段数据存在哈希碰撞，实际应用中认为这是小概率事件(数学意义上的”不可能事件”)，优秀的哈希算法都是碰撞率极低的。
• 哈希算法是单向算法，无法通过哈希值，计算出原始数据，这一点非常重要！

常见的哈希算法有: md5, sha1, sha256等，其中sha1长度为160bits，而sha256长度为256bits，二者相比，sha256的取值范围更大，因此碰撞和破解的概率更低，也就相对更安全。