从FIPS 46-3中理解DES算法
DES是一种对称密钥的块加密算法。”对称密钥”,是因为加密、解密用的密钥是一样的(这不同于RSA等非对称密钥体系)。“块加密”,是因为这种算法把明文划分为很多个等长的块(block),对每个块进行加密,最后以某种手段拼在一起。“块加密”亦称“分组加密”。
1973年,NSA向社会征集满足安全要求的加密算法。1973-1974年,IBM研发了DES加密算法。1974年,NSA开始了第二次征集,此后DES在1976年成为美国联邦标准。
一、DES概述
DES的功能是:给定一个64位的明文和一个64位的密钥,输出一个64位的密文。这个密文可以用相同的密钥解密。所谓“64位的密钥”,其实里面只有54位在起作用。剩余的位可以直接丢弃,或者当作奇偶校验位。
虽然DES一次只能加密8个字节,但我们只需要把明文划分成每8个字节一组的块,就可以实现任意长度明文的加密。如果明文长度不是8个字节的倍数,还得进行填充。现在流行的填充方式是PKCS7/PKCS5,都是很简单的思路,用于把任意长度的文本填充成8字节的倍数长,也能方便地恢复原文,这里不再赘述。此外,独立地对每个块加密,最后直接拼起来是不行的(这种方式称为“电子密码本”,ECB模式。它会导致明文中重复的块,加密结果也重复,这对于图片之类的数据来说几乎是致命的)。因为不涵盖在算法流程中,因此对有关DES输入输出的处理后续再讲。
DES有一个非常不平凡的性质——加密与解密算法几乎一模一样。这大大简化了软件和硬件的设计。和加密算法的区别是,给它加上一行(倒转子密钥的顺序),就是一个解密算法了。
在这篇文章中,我们只关注一个核心任务——如何把64位的明文,用64位的密钥,加密成64位的密文,并执行解密。
二、DES算法框架
DES算法是在Feistel Network(费斯妥网络)的基础上执行的。以下是DES算法的流程图:
可以看到,整个算法可以看成是两个部分
-
密钥调度计算(右边基于给定密钥生成子密钥的过程)
所谓密钥调度,就是从一把64位的主密钥,得到16把48位的子密钥,然后把这些子密钥参与到后续16轮迭代加密中。那么,如何从一把主密钥得到16把子密钥呢?
-
首先是从64位的主密钥中通过选择置换1选取特定的56位,其余的位就作为检验位,不参与后续计算。于是我们现在手上有了一个56位的密钥
-
接着把它分成左、右两个半密钥C0、D0,它们都是28位的密钥
-
然后对C0和D0进行16轮的迭代,每轮迭代都包括以下步骤:
- 左、右两个半密钥Cn、Dn都左旋(也就是循环左移。整个数组往左移,左边弹出去了的东西补到最右边去)一定位数得到Cn+1、Dn+1,这个左移的位数也是指定的。有些轮次是1位,有些轮次是2位
- 把左、右半密钥拼起来成为Kn+1,再通过选择置换2得到Kn,就得到了这一轮生成的子密钥。这个置换是从56位的数组里面选取指定的48位。所以现在每一轮都可以生成一个48位的子密钥。(注意,步骤3并不改变左右半密钥)。
-
最后,经过16轮迭代之后,就生成了16个48位的子密钥,这些子密钥被用于加密和解密数据
-
解密过程中,除了子密钥输出的顺序相反外,密钥调度的过程与加密完全相同
-
-
迭代加密(左边的16轮迭代加密的过程) 迭代加密就是由具体数据参与的主流程的加密逻辑,具体逻辑是
-
输入的明文(64bit)做一个置换(IP置换)。仍然得到64bit的数组(位数不等会导致信息丢失)
-
同样基于Feistel Network的概念将数据拆分成左右两个半数据,各32bit
-
每轮迭代都是接收一组L、R,返回L’、R’,作为下一轮迭代的 L, R . 迭代过程如下:
1 2
L' = R R' = L⊕F(R,subkey)
关键在于F函数,也称为轮(Round)函数,是整个算法的核心,用于以子密钥加密32bit的信息
-
步骤3执行16轮,每轮分别更新L、R值
-
将最终得到的L、R值进行合并,再做一次置换(FP置换),即可得到密文
-
以上就是DES算法的大致过程,文中也提到,加解密的唯一区别就在于子密钥的顺序不同
1 密钥调度计算
详细来看看DES如何通过给定的主密钥而生成16把子密钥的,图示如下:
首先,采用“选择置换1 (PC-1)”,从64位key里面选出56位。这一步属于encode,对信息安全没有帮助。PC-1方法如下:
|
|
经过PC-1之后,我们有了左、右两个半密钥,长度都是28位。接下来,我们每一轮把左、右半密钥左旋几位,再调用PC-2方法来造子密钥。框架如下:
|
|
其中, shift_bit是循环左移,实现如下:
|
|
PC-2又是一个简单置换,用于从左右半密钥拼起来的56位密钥中,选取48位作为一个子密钥。实现如下:
|
|
这样,我们就实现了密钥调度算法。基于主密钥而得到的16个48位的子密钥。不难看出,整个密钥调度的过程都是对主密钥的encode。生成这么多子密钥的目的,是使得加密迭代变得更加复杂、难以分析
2 迭代加密
|
|
DES的安全性在很大程度上取决于F函数,也就是轮函数。那么Feistel函数是干了什么事呢?来看下面一张流程图:
一个32-bit的块,经过一个扩张(Expand函数),变成48位,然后与子密钥异或。得到的48-bit的结果分为8组,每一组是6-bit的数据,丢进对应的S盒,输出4-bit的信息。把这些输出收集起来,一共是4*8=32位,做一次置换(P置换),得到32-bit的结果。这与输进来的32-bit信息是等长度的。
Expand算法是指定的
|
|
分成8组分别进入S盒处理
|
|
S盒构成如下
|
|
|
|
最后得到的32位结果还需要经过一个P置换
|
|
三、理解
DES也算是第一代的公认的对称加密的标准算法,核心在于F函数的概念与实现。当然DES算法主体流程还是依赖于固定64位的输入输出,而到了实际使用上还存在有不同的工作方式以及安全性问题,这些问题还等到后续继续补充