密码学专题| 四、实际分组密码 —— DES 和 AES

2020-05-29 cryptography 密码学 分组密码

实际密码方案与实际安全

分组密码加密方案假设了分组代换-置换是一种伪随机函数,这是一个非常典型的安全假设。另一个 RSA 算法假设大数分解是困难。这些假设的引入,使得加密方案的安全性不再等于计算安全

如果假设成立,分组代换-置换是一种伪随机函数,那么可以证明这种加密方案是满足计算安全假设的。然而,如果分组置换并不满足伪随机函数的定义,此时基于分组代换-置换的分组密码就无法达到了计算安全假设了。RSA 的例子也是如此,我们都假设大数分解难题是一个 NP 问题,因此一个线性多项式时间的敌手攻破 RSA 算法的可能性很低。但是如果 N=NP,此时 RSA 算法就不再是安全的了。

我们称这样一种基于长期认为可靠、或者是有大量理论认为成立的假设的安全为实际安全。通常,这时候,我们认为这些加密方案在一个非常可靠的时间内是安全的(比如十年或者一百年)。

代换-置换网络是分组密码的基本结构

将 n 个数随机置换,有约 \(n*2^n\) 种可能性。分组置换中,分组大小 n 应当充分的大,分组密码的安全性和 n 的大小直接相关。就目前来说 128 bit 几乎是最低标准, 256 bit 和 512 bit 的分组将变得更加流行。

一个分组置换网络通常具有许多轮,比较典型的数字是 16 轮及以上。每一轮中,子秘钥将和明文进行混合,通过被称为 “S盒” 的固定置换函数,并进行位置代换。

注意到此时 “S 盒” 是一个一一映射的函数,也就是说这种置换是可逆的。此时可以发现这种映射可以说是线性的,那么还需要位置轮换,进行非线性映射。

通常,在这种网络中,需要充分利用雪崩效应,也就是单个 bit 的改变也应当影响其他尽可能多的 bit 。这要求算法设计满足下面一些条件: S 盒的设计,使得单个 bit 输入的差值可以输出在尽可能多的位数上;单个 S 盒的改变,应当进入下一轮多个 S 盒中;尽可能增加分组置换的轮数。

DES 算法族和 Feistel 网络

Feistel 网络

这种网络是一个可逆的分组置换网络,其具有基本的变换形式如下:将第 i 轮输入分为左侧输入 \(L_i\) 和右侧属于 \(R_i\)。还有一个和子秘钥 \(k_i\) 相关的不可逆函数 \(f_i\)。那么: \[L_i = R_{i-1}, R_i = L_{i-1} \bigotimes f_i(k_i, R_{i-1}) \]

可以证明即便是使用了不可逆函数 fi, 但是网络整体是可逆的。

DES 加密标准

DES 是一种基于 Feistel 网络的加密标准,使用 64 bit 秘钥(实际 56 bit),目前由于分组长度不足,导致安全性已经被攻破了,因此已经不再使用了,取而代之的是 AES 以及 3DES。

DES 算法由 16 轮 Feistel 置换构成,每轮分组长度 64 bit,秘钥长度 56 bit。f 的选取输入和输出均为 32 bit,在 f 中扩展为 48 bit,有 8 个进行挑选的 S 盒。

双重 DES 加密和中间相遇攻击

使用双重 DES 加密使用了两个 56 bit 秘钥,因此秘钥空间是 \(2^{112}\)。

设 E(k,m) 表示 DES 加密算法,而 D(k,c) 表示 DES 解密算法,则双重 DES 加密描述如下: \(c = E(k_2, E(k_1, m) )\)

此时存在中间相遇攻击,使得攻击复杂和 DES 相同,即 \(2^{56}\)。假设敌手 A 拥有一对明文密文对 m,c :

  1. 使用 i 表示指标,遍历 k 的秘钥空间。计算中间结果 \(z_1^i = E(k_1^i, m)\) 并存表 \( (z_1^i, k_1^i) \)
  2. 使用 j 表示指标,遍历 k 的秘钥空间。计算中间结果 \(z_2^j = D(k_2^j, c)\) 并存表 \( (z_2^j, k_2^j) \)
  3. 对中间结果进行排序并比对,找出 \( z_1^i = z_2^j \)。此时 \( k_1^i \) 和 \(k_2^j \) 就是秘钥。

3DES

为了对抗中间相遇攻击,因此提出了 3DES 算法,作为 AES 算法的过度算法。但是由于其进行了三次 DES 操作,因此加密解密开销较大。 3DES 的形式如下: \[ c = E(k_3, D(k_2, E(k_1, m)) \]

有两点值得说明:

  1. 有时候 k3 和 k1 使用同一个秘钥,此时总秘钥长度是 128 bit (实际 112 bit)
  2. 使用 EDE 的方案使得加密和解密使用了同样的过程,而无需单独编程。

高级加密标准 AES

AES 算法使用了 AES 置换网络结构,而不是 Feistel 结构。 AES 算法使用 128 bit 分组长度。秘钥长度有 128 bit,192bit 和 256 bit,分别对应 10, 12 和 14 轮变换。每一轮变换有加秘钥、字节代换、行位移和列混合四个步骤。

分组密码的攻击

1. 差分攻击

差分攻击是一种选择明文攻击。此时构建了输入的查分 \(\Delta_m\),并在随机秘钥k 的情形下,统计输出的差分 \(\Delta_c\)的 p 。如果分组置换网络设计合理,并与伪随机函数无法区分,那么输出的概率 p 应接近 \( 2^{-n}\)。如果偏离了这样的分布,那么这种分组置换网络则是不安全的。

2. 线性攻击

线性攻击是一种已知明文攻击。此时假定比特位 \( i_1,i_2 … i_l \) 和 \( i_1’,i_2’ … i_l’ \) 有偏移。那么:

\[ Pr[m_{i_1} \bigotimes … \bigotimes m_{i_l} \bigotimes c_{i_1’} \bigotimes … \bigotimes c_{i_l’} = 0] = p \]

如果分组置换网络设计合理,并与伪随机函数无法区分,那么输出的概率 p 应接近 \( \frac{1}{2} \)。如果偏离了这样的分布,那么这种分组置换网络则是不安全的。

本人保留对侵权者及其全家发动因果律武器的权利

版权提醒

如无特殊申明,本站所有文章均是本人原创。转载请务必附上原文链接:https://www.laytonchen.com/post/crypto/crypto-blockcipher/

如有其它需要,请邮件联系!版权所有,违者必究!