数据加密标准DES分析
DES:data encryption standard
- 20世纪70年代初，非军用密码学的研究处于混乱不堪的状态中。
- 1972年，美国国家标准局（NBS），即现在的国家标准与技术研究所（NIST），拟定了一个旨在保护计算机和通信数据的计划。计划中提出要开发一个单独的标准密码算法。
- 1973年，NBS公开征集标准密码算法。
- 1974年，NBS第二次征集。收到一个有前途的候选算法，该算法从IBM 1970年初开发出的Lucifer算法发展而来。
- 1975年3月，NBS公布了算法细节。
- 1976年11月，DES被美国政府采纳作为联邦标准，并授权在非密级的政府通信中使用。
- 1981年，美国国家标准研究所（ANSI）批准DES作为私营部门的标准（ANSI X3.92）。
DES算法说明：
- DES是一种分组加密算法，输入的明文分组长度为64位，通过**计算，生成的密文为64位。
- 对64位的明文分组先进行一个初始置换，将明文分组分成左半部分和右半部分，各32位长；然后进行16轮完全相同的运算。
- **为56位，需要产生16个子**参与每轮内的运算。
DES算法加密流程：
其中的F为轮处理函数⬇️
DES算法说明：
①初始置换IP
【初始置换的作用】
把输入的64位明文m按位重新组合，并把输出分为长32位的L0、R0两部分。
其置换规则如下表，即——第58位到第1位，第50位到第2位，依次类推，第64位到第7位
|
IP |
|
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 |
②轮函数中的扩展置换E
【扩展置换的作用】
将输入的32位的右部分扩展为48位，以备与48位**进行计算，原数据的1位扩展到了多位上
输入的32位数，有16个位的比特出现了两次（蓝色表示）。
③轮函数中的S盒
S-盒共8个，将上面计算的48-bit结果作为输入，替代操作成32-bit的输出,增加混乱。过程如下：
-
- 48-bit组被分成8个6-bit组，每一个6-bit组作为一个S盒的输入
- 6-bit数的首、末两位数决定输出项所在的行；中间的四位决定输出项所在的列；利用该行列数查S盒的表即得到输出
例如：假设第6个S-盒的输入为110101，则输出为第3行第10列的项（行或列的记数从0开始），即输出为4-bit组0001。
如 S6:
12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11,
10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8,
9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6,
4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13,
④轮函数中的P盒
- P-置换将S盒32位的输出进行置换，增加扩散性
-
P-盒
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轮后的64位数据，经过最终置换IP-1后生成的比特串就是密文e。
|
IP-1 |
|
40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 |
- DES经过精心选择的各种操作，获得了一个非常有用的性质：加密和解密可使用相同的算法。唯一的不同点就是，如果各轮加***分别是K1,K2,K3….K16，那么解***则是K16,K15,K14…K1。
DES子**的生成
DES算法的**根据用户的输入生成，用户输入的**通常为64-bit，但算法把8的倍数位，即第8、16、24、32、40、48、56、64位作为奇偶校验位，在计算**时要忽略这8位，实际的**长度为56-bit。
DES密码的8位校验位
输入的密码只在8位校验位上有区别的话，操作的结果将是一样的，如:
输入的密码为wuzhenll，特定地改变这64位数据奇偶校验位上的数，可以得到不同的密码，如把8个奇偶检验位全取反:
w->v ：1110111->1110110
u->t ：1110101->1110100
z->{ ：1111010->1111011
h->i ： 1001000->1001001
e->d ：1100101-> 1100100
n->o ：1101110-> 1101111
l->m ：1101100-> 1101101
形成新密码:vt{idomm
表面上新密码和原密码迥然不同，但是由于他们仅在奇偶校验位上有区别，实际加密过程中用到的其他位都相同，所以用这两个密码进行加密解密操作得到的结果是一样的。
DES的算法安全性问题
- **长度：
最大缺陷就是56位**长度短，**空间可选**数256，抵抗不了穷举攻击
- 弱**与半弱**
->DES的弱**和半弱**
- 主**产生的16个子**都相同，该**就是weak key，DES有4个弱**：
|
弱**值（带奇校验） |
真实**(经过PC1) |
|
0101 0101 0101 0101 |
0000000 0000000 |
|
1F1F 1F1F 0E0E 0E0E |
0000000 FFFFFFF |
|
E0E0 E0E0 F1F1 F1F1 |
0000000 FFFFFFF |
|
FEFE FEFE FEFE FEFE |
FFFFFFF FFFFFFF |
- 如果一个主**在16轮中只产生两个不同的子**，每个被使用8次，这个主**就是半弱**（semi-weak key）
->DES的破译——密码分析
- 1990年，以色列密码学家Eli Biham和Adi Shamir提出了差分密码分析法( Differential cryptanalysis) ，可对DES进行选择明文攻击；
- Rueppel[1986]的流密码专著中曾提出以最接近的线性函数逼近非线性布尔函数的概念，Matsui推广了这一思想以最隹线性函数逼近S盒输出的非零线性组合[1993]，即所谓线性攻击，这是一种已知明文攻击法。
->DES的破译——穷举攻击
- 设一次加密需要1us，穷举尝试所有**需要的时间比较：
->DES的破译——穷举攻击
- 1977年，一台专用于破译DES的并行计算机能在一天中找到**，耗资2000万美元。当时DES被认为是一种十分强壮的加密方法。
- 在CRYPTO’93上，Session和Wiener给出了一个非常详细的**搜索机器的设计方案，这个机器基于并行运算的**搜索芯片，所以16次加密能同时完成。花费10万美元，平均用1.5天左右就可找到DES**。
- 1993年，花费100万美元建造的穷举DES破译机平均3.5小时就能找到一个**。并且这种机器的造价以每10年20%的速度下降。
- 美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同工作下，成功地找到了DES的**，赢得了悬赏的1万美元。
- 1998年7月电子前沿基金会（EFF）使用一台25万美圆的电脑在56小时内破译了56比特**的DES。
- 1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告**了一个DES的**。