1. 算法类型与模式

介绍什么是对称加密和非对称加密之前,先来讨论加密算法的两个重要的属性:算法类型算法模式

1.1. 算法类型

算法类型定义加密算法每一步要加密的明文长度。

有的算法一位一位加密,例如将明文和密钥通过异或进行加密,每一位的加密是互相独立的,所以可以看成一位一位加密。这叫做流加密法

而有的算法一块一块加密,称为块加密法。例如要加密的明文为 FOUR_AND_FOUR,利用块加密法,可以先加密 FOUR,再加密 _AND_,然后再加密FOUR,每一个块加密的结果和块中每一个字符的每一位的取值相关,所以可以看作一块一块加密。

1.2. 算法模式

算法模式是在加密过程中每一块的组合逻辑。例如有的加密算法,加密的每一块之间没有联系。而有的加密算法,前一块加密的结果会影响下一块的加密。

电子编码簿(ECB)模式,最简单的算法模式。将输入明文分成64位块,然后单独加密每一块,每一块的加密之间没有联系。可知这种情况下,明文中如果出现了重复的64位块,则密文也会重复,这样就会为算法的破解提供线索。

加密块链接(CBC)模式,弥补了电子编码簿模式的不足,在加密中引入了反馈机制。即上一块的加密结果先和当前块异或,之后再正常加密,这样,即使原文块出现了重复,密文块也不会相同。

加密反馈(CFB)模式,与 CBC 具有不同的反馈机制,且每次加密的原文位数更小,通常为 8 位。

输出反馈(OFB)模式,类似于 CFB ,改变了反馈的位置。

计数器(CTR)模式,类似于 OFB ,但 CTR 的每一块加密时输入的反馈并不来自于上一块的加密,而是取自于一个计数器,每加密一块计数器就递增。这样块和块加密并不是链接在一起的,可以并行加密,速度很快。

2. 对称加密算法

2.1. 简介

对称加密算法,也被称为对称密钥加密(Symmetric Key Cryptography)。“对称”在这里的意思是,加密和解密使用同一个密钥。

其加密解密过程可以表示为下图:

如图所示,在对称加密体系中,原文通过对称密钥被加密成密文,而密文可以使用相同的对称密钥解密成原文。所以这个对称密钥就是保持一条加密通信链路的关键,必须确保对称密钥不能被任何不属于通信双方的人得到。

下面简要介绍几个对称加密算法。

2.2. 数据加密标准(DES)

简介

对称加密算法中最有名的当属大名鼎鼎的数据加密标准了(DES, Data Encryption Standard)。这个算法曾经被广泛使用在各种场景中。后来,人们发现 DES 在强大的攻击下太脆弱,因此使用 DES 的应用有所下降。

DES 的产生可以追溯到 1972 年,美国的国家标准局(NBS)启动了一个项目,旨在保护计算机和计算机通信中的数据。其中的重点就是开发一个加密算法。两年之后,NBS 发现 IBM 公司的 Lucifer 相当理想,那么就没必要重新开发一个新的加密算法了。到 1976 年底,美国联邦政府正式决定采用这个算法,并将其更名为 DES 。之后其他组织也快速跟进采用 DES 作为标准的加密算法。

DES 是一种块加密算法,它接受固定长度的明文并对其做了一系列复杂的操作,最终将明文转换成同样长度的密文。在 DES 中,块长度为 64 位,即每次加密 64 位原文,产生 64 位密文。DES 使用同样的密钥用于加密和解密,这个密钥最初长 64 位,但其中的 8 位只用来做奇偶校验保证密钥没有被破坏,所以真实参与加解密的只有 56 位。DES 一个奇妙的特性是加密和解密使用的算法完全相同,只不过在解密的时候要把密钥逆序,就可以用完全相同的算法完成解密。

算法过程

这篇博客不对涉及到的算法进行细致的描述,如果日后有机会会对这些常见的算法分别写博客详细实现的。

上图表示了 DES 的大致流程。图正中间的省略号表示这里有 16 轮完全相同的运算。在最上面和最下面分别是初始置换(initial permutation, IP)和最终置换(final permutation, FP),IP 和 FP 是两个互逆的运算(即对做完 IP 的结果再做 FP 会得到做 IP 之前的信息)。IP 和 FP 其实没有任何密码学方面的意义,它们只是用来优化 1970 年代的 8 位硬件的计算机对块的导进和导出的速度。

在 DES 的主流程也就是那 16 轮运算开始之前,经过 IP 的 64 位原文先被拆分为两块 32 位的子块,然后分别进行运算,这就对应了上图中左右两列数据流。图中这种交叉型的运算方式是被精心设计过的,这种设计思想称为 Feistel 密码结构,其最大的优点就是使得加密和解密可以用完全相同的结构进行,只需要将密钥逆序即可。

图中的红色加号代表按位异或操作。图中的 F 运算以右半部分子块和一部分密钥作为输入,然后将运算结果和左半子块进行异或操作,然后把结果作为下一轮运算的右子块,上一轮的右子块作为下一轮的左子块。就这样一直进行 16 轮运算,最终将运算后的左子块和右子块合在一起再进行 FP 就可以得到密文了。

这里就不对 IP 、 FP 、 F 做更具体的展开了,其实这些运算从根本上讲就是对那些输入的数据进行一系列繁杂的位尺度的运算,例如二进制位多次交换、和密钥进行异或等等。要知道所谓的加密不是说你给我一个原文我凭空给你变出一个密文,而就是这样把原文的每一位都揉来揉去尽可能加大破解的难度,最终得到一个密文。

DES 的强度

我们知道,DES 使用的是 56 位的密钥,也就是说密钥总共有 $2^{56}$ 个可能,所以直接暴力破解的话可能需要一台计算遍历 1000 多年才行。当然还有些其他攻击 DES 的方法,例如差分密码分析、线性密码分析和计时攻击等等。随着现代计算机的算力的精进,以及越来越多针对 DES 的破解算法,如今 DES 已经不推荐使用在高安全性的场景了。

2.3. 国际数据加密算法(IDEA)

简介

国际数据加密算法(IDEA, International Data Encryption Algorithm)是最强大的加密算法之一,出现在 1990 年。

尽管 IDEA 很强大,但不像 DES 那么普及,原因有两个:第一,IDEA 受专利保护,而 DES 不受专利保护,IDEA 要先获得许可证之后才能在商业应用程序中使用;第二,DES 比 IDEA 具有更长的历史和记录。

算法过程

IDEA 和 DES 同样是块加密算法,块大小同样为 64 位。但是其密钥更长,共 128 位。和 DES 一样,IDEA 算法是可逆的,即使用相同的算法加密和解密。

上图展示了 IDEA 的基本过程。可以看到首先将 64 位原文分成 4 个 16 位子块作为第一轮运算的输入,同样作为输入的还有密钥生成器生成的 6 个 16 位的子密钥,密钥生成器负责将原 128 位密钥转换成每轮所需的 6 个 16 位子密钥。这样做完 8 轮完全相同的运算后再做最后一轮输出转换生成 4 个 16 位密文块,合在一起就构成了最终的密文。

IDEA 的强度

IDEA 使用 128 位密钥,是 DES 密钥长度的两倍,因此要破解 IDEA ,就要进行 $2^{128}$ 次加密运算,一个计算机大概需要 540000000000000000000000 年才能破解 IDEA 。

2.4. 高级加密标准(AES)

简介

20 世纪 90 年代,美国政府想把已经广泛使用的加密算法标准化,称为高级加密标准(AES, Advanced Encryption Standard),为此提了许多草案,经过多次争论,最后采用了 Rijndael 算法。

之所以需要新算法,是因为人们感到 DES 有弱点。DES 的 56 位密钥在穷举密钥搜索的攻势下显得不太安全。AES 采用了 128 位块和至少 128 位的密钥。

按照设计者的说法,AES 的主要特性如下:

  • 对称和并行结构:使算法实现具有很大的灵活性,而且能够很好的抵抗密码分析攻击。
  • 适应现代处理器:算法很适合现代处理器。
  • 适合智能卡:这个算法很适合智能卡。

Rijndael 支持的密钥长度和明文块长度为 128 位 ~ 256 位。密钥长度和明文块长度要分别选取。AES 规定,明文块大小必须是 128 位,密钥长度是 128 位、192 位或 256 位。通常使用的两个 AES 版本是:128 位明文块加 128 位密钥,以及 128 位明文块加 256 密钥。

算法过程

Rijndael 的基础是一个称为伽罗瓦场论的数学概念。这里不多介绍,只是从算法的过程上简要的介绍一下。

https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#Description_of_the_ciphers

AES 不同于使用了 Feistel 密码结构 DES,AES 使用了被称为 substitution–permutation network 的设计思想,这使得 AES 在硬件和软件上都能快速的加解密。

AES 的密钥长度和明文块长度决定了需要运行的轮数,轮数的可能值为 10、12、14。首先看图的右边,这里有一个密钥扩展器,用于从原 128 或 256 位密钥生成每轮所需的子密钥 $K_1$ 、$ K_2 $ ... $K_r$ 。原文首先和子密钥 $K_1$ 做一步运算合在一起,这一步称为 Add Round Key ,接下来再进行 9 或 11 或 13 轮相同的运算,最后一轮和前几轮的步骤稍有不同。最后一轮的运算的输出就是得到的密文。

由于并没有使用 Feistel 密码结构,所以这次 AES 并不能直接用原算法进行解密,而是要做类似于加密算法的逆运算,这里不再赘述。

AES 的强度

拥有至少 128 位密钥的 AES 已经很难从暴力破解的方向找到一点希望了。2003 年,美国政府声明 AES 可以用来保护所有的机密文件,顶级机密文件建议使用 192 或 256 位密钥。

2.5. 对称加密存在的问题

第一个,就是密钥交换问题。由对称加密的定义可知,如果通信方想解开由对称加密算法加密的消息,他必须拥有对称密钥。那么加密者如何把这个密钥交给这个人呢?直接口头交接自然不现实,我都口头交接了为啥不把要加密的消息直接告诉你呢?不口头交接那就只能通过网络了,可我总不能明文把密钥直接传输给对方吧,那就得加密,可如果把密钥也用对称加密算法加密的话,那不就又要传输一个新的密钥了吗,成了无限循环了。。。

1976 年,Whitefield Diffie 和他的老师 Martin Hellman 提出了神奇的 Diffie-Hellman 密钥交换协议/算法,成功的解决了这个问题,这个算法我有写过博客介绍,可以看这里:https://laihaodong.cn/2236.html 。更厉害的是,这两个人在发明Diffie-Hellman 密钥交换算法的时候,受到该算法的启发,又发现了下一章要介绍的非对称加密体系!神人也。

第二个,就是一个人想要同时和多人进行对称密钥加密,就需要多对对称密钥。当人非常多的时候,保存和管理这些密钥也成了一个麻烦。

幸运的是,后来诞生的非对称密钥加密体系成功的解决了这两个问题!

3. 非对称加密算法

3.1. 简介

非对称密钥加密(Asymmetric Key Cryptography)又称公钥加密(Public Key Cryptography),这类算法使用一对密钥,一个用于加密,即公钥(Public Key),通常可以公开的在网上传播,另一个用于解密,即私钥(Private Key),一般被所有者私密保存。

非对称密钥加密的过程可以用下图表示:

在非对称加密体系中,想要接收加密消息的一方将公钥发布在网上,而任何一个人都可以通过这个公钥将原文加密并传输给接收方,但是只有接收方的私钥才能解开这个密文,这就保证了通信的安全性。

3.2. RSA

简介

在非对称加密体系中最有名且可靠的当属 RSA 算法了。RSA 这个名字取自这个算法的三个发明者 Rivest 、Shamir 和 Adleman 。

RSA 的基本原理和上面讲的非对称加密一模一样。需要两个密钥,公钥可以公开传输,私钥则被通信方私有。公钥可以加密信息,但加密后的信息只能用私钥解密。

有关 RSA 算法的具体步骤以及通信的流程,我另写了一篇博客详细介绍,参见:https://laihaodong.cn/2267.html

这里也简要介绍一下,RSA 算法的四个基本步骤分别是:密钥生成、密钥发布、加密和解密。正如博客中提到的,RSA 公钥私钥的生成基于两个大素数 $p$ 和 $q$ ,而公钥中只包含了这两个数的乘积 $N=p*q$ ,假设攻击者得到了公开传输的公钥,他也不能因此算出私钥,因为计算私钥必须要用到 $p$ 和 $q$ ,也就是要对公钥中的 $N$ 分解因数。但是对极大数的因式分解是非常困难的,现实中 $N$ 通常在几百位十进制,对这么大的数做因式分解简直难于登天,这也就是 RSA 的安全所在。假如以后有人发明了一个高速分解因数的算法,RSA 这座大厦可能就要倒塌了。

4. 对称与非对称密钥加密的比较

终于介绍完了对称密钥加密和非对称密钥加密,现在就是将两个体系做以比较的时候了,比较分几个方面。

4.1. 安全性

其实现在对称密钥加密和非对称密钥加密中的佼佼者都很安全

AES 的安全性取决于对称密钥的长度,AES 的最短 128 位的密钥如果要暴力破解的话,需要一个计算机算 540000000000000000000000 年,更别提 256 位了。

RSA 的安全性取决于大整数因数分解的难度,现在没有可以明显缩短该过程的算法,所以硬要破解的话估计时间不比上面的短。

4.2. 速度

https://www.zhihu.com/question/350824284

http://vearne.cc/archives/164

但在速度这一方面,对称密钥加密所需的时间明显短于非对称密钥加密,这个差距不是某两个算法之间的比较而是这两个体系之间的比较,而且通常具有数量级的差异。

这一差异也可以从 AES 和 RSA 的具体流程上略窥一二。AES 代表的对称密钥加密在加解密时通常只需要做 10 轮左右计算,每一轮中需要做很多次位尺度(bit-scale)的变换。而 RSA 需要做的是对一个几百位十进制的数做 $mod$ 运算以及幂运算,这可能就需要费些时间了。

4.3. 密钥交换

在前面说过,对称密钥加密中如何把密钥传输给对方是一个大问题。而在非对称密钥加密体系中,这就不再是一个问题了,公钥可以放心的在网络中传播。

5. 数字信封

前面提到了,对称加密和非对称加密各有各的好处,对称加密速度快但是密钥交换很麻烦,非对称加密不需要解决复杂的密钥交换问题,但如果大段大段的明文都用非对称加密算法加密就会很慢。那么人们就想了,能不能把这两种方法进行取长补短呢?当然可以,这就是数字信封(digital envelope)

在实际中,我们可以把对称和非对称密钥加密结合起来,这提供了相当高效的安全方案,具体的工作步骤如下,这里假设 A 是发送方,B 是接收方。

  1. A 的计算机通过对称加密算法例如 AES 等将明文消息(PT)加密,产生密文消息(CT)。这一步使用了对称密钥(K1)。
  2. 然后用非对称加密算法例如 RSA 等将对称密钥(K1)加密,这里使用的非对称密钥是 B 发布的公钥(K2)。
  3. 现在,A 把密文 CT 和加密后的对称密钥一起放在数字信封中,并将这个数字信封通过网络传输给 B 。其实这里的数字信封就是类似于将其中的内容包装起来,没有什么更特殊的含义。
  4. B 收到数字信封后,得到其中的加密后的对称密钥,以及被该对称密钥加密的密文 CT 。B 使用自己的私钥(K3)将加密后的对称密钥解密得到 K2 ,然后用对称密钥 K2 将密文 CT 解密得到明文 PT 。

就这样,我们结合了对称密钥加密和非对称密钥加密各自的优点,整个过程不仅速度快还不用直接交换密钥。当然还有一些小问题,B 如何知道 A 使用了哪种对称加密算法呢?实际上,A 发给 B 的数字信封中包含了这个信息,这样 B 打开信封的时候就能知道自己需要用什么算法来解密了。

Last modification:March 14th, 2020 at 11:25 pm