公钥加密算法 也叫非对称加密,它在加密和解密时使用的是不同的密钥,具有这样的特征:
有一对密钥
a
和b
,满足a ≠ b
用密钥
a
加密的数据只能用b
进行解密,a
自身无法解密,反之亦然只知道其中一个密钥,无法推导出另一个
-
把其中一个可以公开的叫做公钥,另一个不能公开的叫做私钥
最常见的公钥加密算法是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
modn
这是一个单向函数,已知{c, n, e}
无法计算出p
- 相应地需要使用
{n, d}
进行解密,p
=c
*d
modn
,这是上一步加密函数的逆函数 - 两组密钥中
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的取值范围更大,因此碰撞和破解的概率更低,也就相对更安全。