DES详解

Posted by rk700 on October 13, 2016

DES(Data Encryption Standard)是一种对称加密算法。之前我仅对DES的基本使用方式有了解,但对具体的加解密细节没有深入研究。这里,便是阅读相关资料后,对DES加密细节的记录笔记。


DES概述

DES是20世纪70年代初,由IBM设计的一种对称加密算法。DES使用56位的密钥,块长度为64位。当然,今天看来,这个密钥过于短了。

整个DES加密过程,可以大致分为以下几个阶段:

  • 对输入的块进行初始置换(Initial Permutaion),得到premuted input
  • 使用密钥,对premuted input进行16轮变换,得到preoutput
  • 最后,对preoutput进行最终置换,得到加密结果

初始置换

加密开始时,对输入的长度为64位的明文,进行初始置换 。其置换方式如下图中 的表格所示:

58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7

即:置换结果的各位,依次为输入的第58, 50, 42, …, 15, 7位。

这一阶段完成之后,得到的结果记为premuted input,作为下一阶段的输入。


加密

得到了premuted input之后,便是整个加密的主要过程了。在这个阶段,会进行16轮的变换。

记第 轮的输入为 ,其中 是输入的前32位, 是输入的后32位。那么每一轮计算的方式如下:

其中:

  • 取值从1到16
  • 是异或操作(XOR)
  • 长度为48位,由密钥 计算得到,每轮根据Key Schedule进行更新
  • 是加密函数(Cipher Function),其输入为32位和48位的两个值,输出结果的长度为32位

当这16轮计算完成之后,将结果拼接得到 。将其记为preoutput,长度为64位,作为最后置换的输入。

在进行解密时,同样需要进行16轮计算。具体地,由于置换的方法是固定的,在已知密钥的情况下,可以计算出16轮用到的全部 (具体计算方法见下文)。那么,解密需要做的,就是由 ,计算得到

这个计算过程,可以由加密时的计算公式倒推而得。例如,由

可知

从而 可以计算得到。使用同样的方法,一步步可将全部 求得,进而完成解密。

Key Schedule

在这16轮计算中,每一轮的 是根据Key Schedule进行计算的,将该计算方法记为 。这一过程中涉及以下3种操作:

  • Permutated Choice 1():将长度为64位的输入,置换得到两个长度为28位的输出
  • Permutated Choice 2():将长度为56位的输入,置换得到长度为48位的输出
  • Left Shifts():对输入进行位运算,向左循环移位

下面,将具体介绍 的计算过程。

首先,将64位的密钥 使用 进行置换,得到两个长度为28位的结果,分别记为 。用于计算这两者的置换分别如下:

57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4

可以看到,输入的64位中,只有56位被使用了,第8, 16, 24, 32, 40, 48, 56, 64位没有被使用。实际上,这就是DES的实际密钥长度为56位的原因:未被使用的8位,被用作56位密钥的奇偶校验。

具体地:

  • 使用第一张表置换得到 ,其各位依次为 的第57, 49, 41, …, 44, 36位
  • 使用第二张表置换得到 ,其各位依次为 的第63, 55, 47, …, 12, 4位

接下来,在每一轮计算 时,使用如下公式:

其中 即为向左循环移位操作,具体每轮移位的位数由下表确定:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
左移位数 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

将得到的 拼接,得到长度为56位的块,再使用置换 得到长度为48位的块,作为这一轮的 。置换 的方式可见下面的表格:

14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32

综上,DES的Key Schedule过程,可见Wiki上的这张图所示:

Cipher Function

回顾之前提到的每轮计算方式:

现在,我们由 知道了每轮的 的值。接下来,就需要了解加密函数 是如何工作的。其大致流程如下图所示:

其中涉及3种操作:

  • 扩张置换:输入长度为32位,输出长度为48位
  • Substitution-Box():输入长度为6位,输出长度为4位
  • 置换 :输入长度为32位,输出长度为32位

下面,是具体计算过程。

首先, 的第一个参数,即32位的 ,经过 的变换,得到48位的结果。变换 由如下表格确定:

32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1

具体地,经过 的变换,结果中的各位,依次为输入的第32, 1, 2, …, 32, 1位。可以看到,输入的有些位,在输出中重复出现了。所以输出的位数,由输入时的32,增加到了48。

接下来,得到的这48位的块,与函数 的参数 进行 操作,即异或操作,得到的结果仍然是48位的。将其每6位编为一组,记为:

然后,对每一个 ,使用对应的sbox进行变换,并将结果继续拼接起来。

sbox将6位的输入,变换为4位的输出,那么其具体计算方式是什么呢?以 为例,其内容如下:

S1 x0000x x0001x x0010x x0011x x0100x x0101x x0110x x0111x x1000x x1001x x1010x x1011x x1100x x1101x x1110x x1111x
0yyyy0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0yyyy1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
1yyyy0 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
1yyyy1 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

对于长度为6位的输入,根据其第1, 6位确定所在行,再根据其第2至5位确定所在列,找到对应的值,即为sbox的输出结果。

例如,对于 ,如果输入是 011011,那么其变换的结果是在第2行,倒数第3列,值为5=0101。所以:

剩下7个sbox的内容,可见Wiki。对于这8个 ,通过 全部计算完成后再拼接,得到长度为32位的结果:

最后,再对这32位使用 进行置换。 的定义如下:

16 7 20 21 29 12 28 17
1 15 23 26 5 18 31 10
2 8 24 14 32 27 3 9
19 13 30 6 22 11 4 25

于是,加密函数 的最终返回值,为:


最终置换

经过了漫长的加密,即将得到最终的DES加密结果。再次回顾之前的内容,进行了16轮加密计算后,我们得到了 。将其交换之后,进行最终置换

此置换为初始置换的逆 ,其内容如下:

40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25

即:DES最终加密结果的各位,依次为 的第40, 8, 48, …, 57, 25位。

以上便是整个DES的加密流程,其大致示意图如下:

当然,这只是对一个块进行加密,实际使用中,还涉及到工作模式如ECB等。由于相关资料较多,这里就不赘述了。


安全性

自从DES加密算法被采取为标准之后,对DES安全性的分析和研究便一直在进行。而DES设计过程中NSA的参与,更是催生出了“DES算法中存在NSA的后门”这种论点。质疑者认为,过短的密钥长度,以及神器的sbox的选取,都有可能是NSA为了便于破解DES而故意设计的。

sbox

抛开密钥长度不论,sbox是DES加密中非常重要的一环,其直接影响到了整个加密的安全性。这是因为sbox是加密过程中唯一的非线性部分。由于sbox的设计准则迟迟没有被公开,所以有些人怀疑sbox的设计上存在缺陷,可以被NSA利用来破解DES。

事实上,一直到DES被公布后约20年,对sbox的设计的质疑才慢慢停歇。而这与微分密码分析(Differential cryptanalysis)的公开有关。这种破解方法,是由Eli Biham和Adi Shamir(RSA算法的发明者之一)在80年代晚期,才逐渐研究并公开的。于是,人们尝试将这种破解方法试用在70年代发明的DES上,却发现sbox的设计可以有效抵御Differential cryptanalysis。

这难道是巧合?当然不是。时间到了1994,终于真相大白。曾经参与过DES设计的IBM研究人员,Don Coppersmith,发布了一篇论文The Data Encryption Standard (DES) and its strength against attacks。在这篇论文中,Coppersmith提到,在当时设计DES时,他们就已经知道了Differential cryptanalysis这种攻击方法。于是在设计sbox时,就考虑到了对其防御。

那么,既然IBM,当然也有NSA,早在近20年前就知道了这种攻击方法,为什么不公开呢?这就值得回味了。根据Coppersmith那篇论文中的解释,Differential cryptanalysis是一种非常强大的攻击方法,对于许多加密方式都有效。一旦他们将其公开,就会对美帝的国家安全造成危害。当然,直到90年代被公开之前,Differential cryptanalysis应该就是NSA的”黑科技“了,不知道他们利用其破解了多少信息。

同时,在Coppersmith的论文中,也第一次公开了sbox的一些设计准则。例如:sbox不能接近线性;只相差1位的输入,经过sbox变换后,相差至少2位,等等。详细内容可见Coppersmith的论文。

3DES

仅仅56位的密钥长度,是DES另一个被人诟病的地方。为此,Triple Data Encryption Algorithm(TDES或3DES)被提出。3DES实际上是使用3个56位的密钥 , , ,进行了3次DES。具体地,加密过程如下:

其中, 是输入的明文, 是输出的密文, 指用 进行DES加密, 指用 进行解密。

知道了3DES的加密过程,那么解密便是其逆过程,具体如下:

而3DES用到的密钥 ,可以有以下3种选择:

  • , , 互相独立
  • 互相独立,
  • 3个密钥全部相同

第一种选择中,虽然3个密钥是互相独立的,但由于Meet-in-the-middle_attack,其有效安全性仅有112位


参考文献