DES

基本介绍

Data Encryption Standard(DES),数据加密标准,是典型的块加密,其基本信息如下

  • 输入 64 位。

  • 输出 64 位。

  • 密钥 64 位,使用 64 位密钥中的 56 位,剩余的 8 位要么丢弃,要么作为奇偶校验位。

  • Feistel 迭代结构

    • 明文经过 16 轮迭代得到密文。

    • 密文经过类似的 16 轮迭代得到明文。

基本流程

给出一张简单的 DES 流程图

加密

我们可以考虑一下每一轮的加密过程

$L_{i+1}=R_i$

$R_{i+1}=L_i\oplus F(R_i,K_i)$

那么在最后的 Permutation 之前,对应的密文为$(R_{n+1},L_{n+1})$。

解密

那么解密如何解密呢?首先我们可以把密文先进行逆置换,那么就可以得到最后一轮的输出。我们这时考虑每一轮

$R_i=L_{i+1}$

$L_i=R_{i+1}\oplus F(L_{i+1},K_i)$

因此,$(L_0,R_0)$ 就是加密时第一次置换后的明文。我们只需要再执行逆置换就可以获得明文了。

可以看出,DES 加解密使用同一套逻辑,只是密钥使用的顺序不一致。

核心部件

DES 中的核心部件主要包括(这里只给出加密过程的)

  • 初始置换

  • F 函数

    • E 扩展函数

    • S 盒,设计标准未给出。

    • P 置换

  • 最后置换

其中 F 函数如下

如果对 DES 更加感兴趣,可以进行更加仔细地研究。欢迎提供 PR。

衍生

在 DES 的基础上,衍生了以下两种加密方式

  • 双重 DES

  • 三种 DES

双重 DES

双重 DES 使用两个密钥,长度为 112 比特。加密方式如下

$C=E_{k2}(E_{k1}(P))$

但是双重 DES 不能抵抗中间相遇攻击,我们可以构造如下两个集合

$I={E_{k1}(P)}$

$J=D_{k2}(C)$

即分别枚举 K1 和 K2 分别对 P 进行加密和对 C 进行解密。

在我们对 P 进行加密完毕后,可以对加密结果进行排序,这样的复杂度为$2^nlog(2^n)=O(n2^n)$

当我们对 C 进行解密时,可以每解密一个,就去对应的表中查询。

总的复杂度为还是$O(n2^n)$。

三重 DES

三重 DES 的加解密方式如下

$C=E_{k3}(D_{k2}(E_{k1}(P)))$

$P=D_{k1}(E_{k2}(D_{k3}(C)))$

在选择密钥时,可以有两种方法

  • 3 个不同的密钥,k1,k2,k3 互相独立,一共 168 比特。

  • 2 个不同的密钥,k1 与 k2 独立,k3=k1,112 比特。

攻击方法

  • 差分攻击

  • 线性攻击

2018 N1CTF N1ES

基本代码如下

显然,我们可以将其视为一个 Feistel 加密的方式,解密函数如下

最后结果为

2019 CISCN part_des

题目只给了一个文件:

考虑到题目名以及数据特征,Round n part_encode 为执行n轮des的中间结果,Key map 应为des的子密钥,要还原出明文只需进行n轮des加密的逆过程即可,解密时注意以下三点。

  • 子密钥的选取,对于只进行了n轮的加密结果,解密时应依次使用密钥 n, n-1..., 1。

  • des 最后一轮后的操作,未完成的 des 没有交换左右两部分和逆初始置换,因此解密时我们应先对密文进行这两步操作。

  • n 的选择,在本题中,我们并不知道 n,但这无关紧要,我们可以尝试所有可能的取值(0-15)flag应为ascii字符串。

??? note "解题代码" ``` python

解密结果(部分):

可以看出n为13,flag为flag{y0ur9Ood}

参考

  • 清华大学研究生数据安全课程课件

  • https://en.wikipedia.org/wiki/Data_Encryption_Standard

Last updated