DES基本原理

数据加密标准（Data Encryption Standard，DES）学习笔记。

---

DES出现的背景

1. 民间对密码学研究较少
2. 没有对密码的评估标准
3. 商业保密的需求出现

DES提出的目的

1. 算法必须提供较高的安全性
2. 算法必须完全确定且易于理解
3. 算法的安全性必须依赖于密钥，而不依赖于算法
4. 算法必须对所有的用户都有效
5. 算法必须适用于各种应用
6. 用以实现算法的电子器件必须很经济
7. 算法必须能有效使用
8. 算法必须能验证
9. 算法必须能出口

DES算法的实现

背景：用户自己设定的密码直接运算，不靠谱；希望实现类似一次密码本的安全性

算法：

1. 用户输入的父密钥，生成16个子秘钥（如下图），进行16轮Feistel加密运算（如下图，因为Feistel加密中，2轮加密整个输入值，因此16轮Feistel算加密了8次）。

   

   

2. 单轮Feistel的算法：将输入的64bit拆分为左右两个部分，右部分通过轮转函数后充当密钥，加密左侧。加密的左侧和右侧明文组合在一起，算作一轮的输出。因为这种算法只加密了一半，因此需要采用多轮Feistel进行加密。

   Feistel轮的特点：加密算法和解密算法逻辑相同，可以使用同一套电路；用以实现算法的电子器件很经济；明文自身参加密钥流的生成。

   

3. 轮转函数：无可逆性要求，输入是密钥和明文。

   

DES的安全性

坊间对DES的安全质疑

1. NSA对S盒（替换运算）切入陷门（同一问题的快速算法），NSA可以通过一个简单地方法对消息进行解密。
2. 112位密钥被修改为56位密钥。
3. 为何选择16轮的迭代加密运算，不多也不少。

密码分析的DES安全性

弱密钥

1. 全弱密码：全0全1密钥，DES轮转加密变成完全相同的16次重复运算。
2. 半弱密码：只生成2个子秘钥。
3. 1/4弱密码：只生成4个子秘钥。
4. 弱密钥问题可以忽略不计因为密钥空间很大。

补密钥

1. Ek(P)=C
2. Ek’(P’)=C’
3. 选择明文攻击，测试的密钥数减少一半 2^56 -> 2^55

代数结构

1. 理想的DES：64位明文分组映射到(2^64)!可能密文分组。
2. 56位密钥，理想上提供了2^56个映射关系，采用多重加密看起来似乎可以获得这些可能映射关系中的更多部分。然而，这仅仅在DES运算不具有某种代数结构的条件下才成立。
3. 1992年数学证明DES不是一个群
4. 担心中间相遇攻击（Meeting In The Middle）：Ek3(Ek2(Ek1(P))) = Ek4(P)

密钥长度

1. IBM最初的112为密钥，被NSA修改为56位密钥
2. 暴力攻击现在已经成为可能

迭代次数

1. 为什么是16轮而不是32轮
2. 密文5轮迭代后，密文每一位基本上是所有明文和密文的函数。经过8轮迭代后，密文基本上是所有明文和密钥位的随机函数（雪崩效应），那么为什么8轮后还不停止。
3. 目前的成果，低于16轮任意DES的已知明文攻击，要比群举攻击有效。有趣的是当算法恰好有16轮时，只有群举攻击最有效。

其他攻击

1. 差分密码分析
2. 线性密码分析

优化的DES：3DES算法实现

3DES的实现：加密 - 解密 - 加密

其他优化方式：DESX、更换S盒、独立子秘钥、RDES、SnDES、GDES、CRYPT(3)，但是大部分都存在问题。