对称加密和非对称加密
对称加密和非对称加密
2022年7月15日
目录
摘要
在上次关于 Git 配置的文章中,提到了设备和 GitHub 之间通讯使用了一种名为 RSA 的非对称加密算法,挖了一个坑,这次纯属是为了填坑。为了更清楚的介绍非对称加密算法,从源头理解非对称加密算法的必要性, 本文还将大致介绍一下现代信息加解密的简单发展历程, 从明文储存(Plaintext)到对称加密(Symmetric Encryption),再到哈希(Hash),加盐哈希(Salted Hash),最后引出非对称加密(Asymmetric Encryption)与带签名的非对称加密(Asymmetric Encryption with Signature)。
背景与需求
我觉得现如今信息为什么需要加密传输,然后收到之后再解密这事儿,压根儿没必要写。。但是对于信息加密,有几个非常重要且具体的要求(以下列表越靠前的要求越基础):
- 不能被通信方以外的对象直接读取信息的内容。
- 即使第三方得知具体的加密方式甚至是密钥,也不可被逆向破解或解码出信息内容。
- 不可被轻易通过穷举可能的信息来正向试出加密信息包含的内容。
- 使第三方完全无法得知具体密钥。
- 防止第三方伪造受信任方发送信息(中间人攻击)。
至少要达到以上 5 点要求,才能算是一个较为完备的加解密算法。
发展历程
明文(Plaintext)
最基础通信方式,即为明文通信,简单来讲,就是完全不加密。这样的通信方式是最不安全的,任何有恶意的第三方都可以通过监听信道的方式读取到信息的内容,除此之外,第三方还可以非常简单的伪装成发送方发送假信息。注意,并不是说明文传输一无是处,其最大的好处就是简单,在追求速率,传输不重要数据,或是使用可信信道时,明文传输也是一个非常可用的方案。
对称加密(Symmetric Encryption)
为了在明文的基础上增加信息的安全性,最简单的方式是使用一种可逆的算法对原始数据做一定的处理,比如字母替换,按照字母表顺序移位,或是任意其他不损失信息,可还原成原始信息的方法,使原始信息变得看不出是什么。接收方收到该信息后,用加密算法的逆过程,将其还原得到原文,即可完成解密。由于双方的加密和解密过程互为逆算法,是对称的,所以叫对称加密。
至此,不能被通信方以外的对象直接读取信息的内容,这一点,被完美的实现了。
这样的方式看似完美,可是其存在一个潜在的巨大风险:既然发送方和接收方要使用一套约定好的方式进行通信,那这个方法本身也是需要被作为信息发送一次的,那么,这个方法信息,这个密码本,这个密钥,如果被截获了,那所谓的对称加密,对于有了密钥的第三方来说,就和明文毫无区别了。当然,有的人会想,那就把密钥加密了传输就好了呗,然而,这是做不到的,要解密这个加了密的密钥,还需要更上一层的密钥,那这个密钥,又要怎么安全传输呢?这里有一个不可回避的前提,双方在从未通信过的时候,互不知晓,所以第一次通信只能使用明文,否则此次通信的内容谁也看不懂是什么。如果第一次就用加密信息,那接收方即使推理出了可读的内容,也无法确定推理出的是否是发送方想表达的内容,例如2775361629
这串数字,你收到过后或许可以推断出这是一个 QQ 号,并且真的找到了存在这么一个人,你以为你猜对了,然而,这只是表示了Apple M1 Max
每个字母或数字在九宫格输入法上的位置。
现代常用的对称加密算法主要有:
- DES
- 3DES
- AES
注:在对称加密中,明文和密文是一对一的,同一算法下,一条明文只能被加密成一条密文,同样的,一条密文也只能被解密成一条明文。
哈希(Hash)
在某些场景下,发送方所发送的加密信息仅需要被用于完成某些校验,并不需要知道其对应的原文,例如,用户登录账号时,用户输入密码,密码字符串被加密后发送至服务器,服务器校验密码是否输入正确。
简单来讲,哈希算法是使用一个不可逆的算法,将任意长度的明文经过处理后,生成一段定长的密文。举个例子,将任意正整数除以 10 取余数即时一种最简单的哈希算法,由于有无穷个正整数除以 10 都可以得到同样的余数,所以即使得知了哈希过后的密文和所使用的哈希算法,也无从得知原始信息是什么。服务器内储存的,自始至终,都只有哈希过后的密码,每次登录所校验的,也只是设定密码时服务器收到的哈希值,和登录时收到的哈希值,是否一致。服务器自己都永远不知道你设定的原始密码是什么,所以原文无法被服务器泄露。
至此,即使第三方得知具体的加密方式甚至是密钥,也不可被逆向破解或解码出信息内容,被不完美实现了,因为哈希算法加密的信息,不仅第三方无法解密,接收方也无法解密,所以不可用于通信。
那么,问题来了,按照上文除以 10 取余数的哈希算法,是否代表着使用哈希算法可能存在多个不同的密码对应同一个哈希值,造成别的密码碰巧也能登录?很遗憾,这种可能性的确存在,并且这个攻击方式还有自己的名字,叫哈希碰撞,所以,现实中使用的哈希算法,远比除以 10 取余数复杂,并且生成的哈希值长度也会很长,尽可能避免在所有可能的密码空间内找到重复的哈希值。例如,常用的 MD5 算法,会生成一个长 128 位的数字和字母(不区分大小写)的字符串,而设定密码时,一般会有一个长度限制,例如 16 位,20 位,这时,所有可能的哈希值的个数,比所有可能的密码的个数,高几十个数量级,所以多个密码对应同一个哈希值的可能性,会被降到极低。当然,如果用 MD5 来生成 1000 位密码的哈希值,因为所有可能的密码数量远大于所有可能的哈希值数量,所以必有多个不同的密码对应同一个哈希,因此,选择哈希算法时,一定要选择哈希值远长于密码长度的哈希算法。
即使哈希算法从设计思路来看,十分安全,但哈希算法加密的信息也不是完全不可被解密。虽然说,哈希算法本身不存在逆向算法来解密信息,但是,例如123456
,88888888
,Jack
,1314520
,admin
或是生日之类的常见密码,经过常见哈希算法得到的密文,早已被黑客做成表格,可以通过查表的方式猜到密码的原文,并且,如今计算机算力越来越强,越来越多不那么常见的密码,也在被挨个穷举生成表格,被破解只是时间问题,这样的攻击方式,叫做彩虹表。
现代常用的哈希算法主要有:
- MD5
- SHA-0,SHA-1(不建议使用)
- SHA-2(SHA-224,SHA-256,SHA-384,SHA-512)
- SHA-3(SHA3-224,SHA3-256,SHA3-384,SHA3-512)
注:在哈希算法中,明文和密文是多对一的,同一算法下,一条明文只能被加密成一条密文,但是,一条密文或许可以从条明文得到。
加盐哈希(Salted Hash)
为了解决黑客通过穷举生成彩虹表,反向找到哈希值对应的原文,加盐哈希算法被发明了出来,其解决问题的思路非常简单,每条密码在被哈希之前,在最后追加一段随机字符串,最后,将{密码+随机字符串}
这个整体一起哈希,以后每次输入密码,系统都自动加上这段随机字符串,这样,即使常见的123456
这样的密码,加上如876tghjo0plkjh6
这样的随机字符串后,就变成了123456876tghjo0plkjh6
,即使另一个用户也使用同样的123456
作为密码,但是生成的随机字符串不同,如23rtyhi9okjhu
,得到12345623rtyhi9okjhu
,最终,两个同样的密码会得到两个完全不同的哈希值。这样的操作,对用户来说完全不可见且不可感知,都是系统的后台操作,但是,不仅将常见简单密码变成了不常见复杂密码,还将穷举的难度进行了极大提升。
至此,不可被轻易通过穷举可能的信息来正向试出加密信息包含的内容,也得到了解决。
很遗憾的是,即使加盐哈希使密码管理变得更加安全,但哈希的本质并没有改变,穷举难度提高了,但是未来计算机算力进一步提升过后,加盐哈希或许还是会被穷举出彩虹表。
注:在加盐哈希算法中,明文和密文是多对多的,同一算法下,一条明文在掺杂不同的随机字符串后可能被加密成多条密文,并且,一条密文或许可以从条明文得到。
非对称加密(Asymmetric Encryption)
既然对称加密那么容易被截获密钥从而使信息被破解,哈希算法又从理论上无法使用算法恢复出原始信息,不可用于通信,那么,有没有一种更安全的方式,使得密钥无法被截获,并且能使用一定的算法恢复出原始信息呢?其实是有的。废话,要不然我写啥。。 为了达成这个目的,我们需要的就是非对称加密,和对称加密不同的是,在非对称加密中,解密时使用的算法,并不是加密算法的逆过程,换句话来讲,解密算法并不能从加密算法中推出。另外,为了使密钥无法被截获,最简单粗暴的方法,就是不发送密钥。
解密算法并不能从加密算法中推出,且不发送密钥,是否听起来有些离谱?其实,仔细思考一下,大概就能猜出非对称加密的精髓了。既然解密算法并不能从加密算法中推出,那只要解密算法不泄露,第三方即使拿到了加密算法,也无法解密信息,同时,为了达成解密算法不泄露,不正是刚刚提到的,不发送密钥吗?也就是说,接收方(B)只需要把加密算法(锁)提供给发送方(A),然后接收方(B)自己留着解密算法(钥匙),发送方(A)将信息用接收方(B)提供的加密算法(锁)加密后,发送给接收方(B),接收方(B)再用解密算法(钥匙)解码(开锁),即可得到原始信息。其中,加密解密算法(钥匙和锁)都是接收方(B)制定的。
如果上面的例子很绕,那就再来一个例子,我家有个邮筒,上面有个缝,下面有个门,缝和门都上了锁,不同的锁,我可以把缝的钥匙(加密算法)发给一堆我批准的人,这些人都可以打开缝给我投信,但是门的钥匙(解密算法)只有我有,除了我以外没人能打开门读信。与此同时,不管是谁,就算有缝的钥匙(加密算法),也没法推出门的钥匙(解密算法)是什么样的,因为二者毫无关系。但是在实际算法中,为什么一个算法能解开另一个算法加密的东西呢?主要是利用了数学中的欧拉定理和同余的性质,本文只是基础的概念科普与备忘,不涉及具体推导。
上文中,所谓的加密算法,就叫公钥(Public Key),用于分发给各个发送方,解密算法,就叫私钥(Secret Key),储存在本地,仅自己拥有。
至此,使第三方完全无法得知具体密钥,也被完美解决,且可用于通信。
现代常用的非对称加密算法主要有:
- RSA
- DSA
带签名的非对称加密(Asymmetric Encryption with Signature)
即使非对称加密看起来如此完美,还是有一个潜在问题,既然公钥被发送出去了,那么,便无法防御第三方盗取公钥,伪造成受信任的发信人,发送假信息,也叫中间人攻击。所以,还需要设计一个有效的算法,从而允许受信任的发送方签名,从而识别伪造信息。
首先,再讲一个背景,在最常用的 RSA 非对称加密算法中,私钥和公钥在某种意义上是一对,通过公钥加密的信息只能用私钥解密,通过私钥加密的信息只能通过公钥解密。
来自受信任的发信人
有了这个背景,上述问题就很好解决了。与普通的非对称加密相比,带签名的非对称加密通信的双方,需要互相交换公钥,发送方在使用接收方的公钥加密信息过后,算出加密信息的哈希值,并且用自己的私钥对这个哈希值加密,得到一个数据包:
{B_Pub(x), A_Priv( SHA( B_Pub(x) ) )}
此数据包由发送方(A)生成,后半段即为签名信息,A 拥有 B 的公钥和自己的公钥与私钥,B 没有 A 的私钥,所以 A 只能用自己的私钥签名,B 才能用 A 的公钥解开。
接收方收到数据包后,先对后半段签名部分用 A 的公钥解密,得到:
{B_Pub(x), SHA( B_Pub(x) )}
后半段解密后即为哈希值,此时接收方就可以自行计算前半段的哈希值是否与后半段对应,若对应,即可用自己的私钥解密信息。
来自不受信任的发信人
接下来,假设一个场景,若存在一个恶意中间人(C)盗取了A 和 B 的公钥,伪装成 A 向 B 发信息,那么,C 共持有四个密钥:C_Priv
、C_Pub
、A_Pub
、B_Pub
,那么,按照之前的规则,C 所能强行生成(因为其并不拥有 A_Priv
,无法按规则生成数据包)的数据包一共有四种:
1. {B_Pub(x), C_Priv ( SHA( B_Pub(x) ) )}
2. {B_Pub(x), C_Pub ( SHA( B_Pub(x) ) )}
3. {B_Pub(x), A_Pub ( SHA( B_Pub(x) ) )}
4. {B_Pub(x), B_Pub ( SHA( B_Pub(x) ) )}
当接收方(B)按照规则使用 A_Pub
去尝试解码后半段的签名时,由于都不是被A_Priv
加密的数据,所以得到的都是乱码,无法通过校验,则该条信息会被接收方(B)直接当作无效信息丢弃。
因此,通过带签名的非对称加密,有且仅有受信任的发信人能够通过签名发送有效信息。
至此,防止第三方伪造受信任方发送信息(中间人攻击),也被完美实现。
总结
写完累死了,好困。