Algorithm 版 (精华区)

发信人: zjliu (Robusting), 信区: Algorithm
标  题: DES算法的实现与破解
发信站: 哈工大紫丁香 (Sun Nov 17 15:40:45 2002) , 转信

来源：瑞星香港信息 安全资讯网站

               DES算法的实现与破解

DES算法实现

DES算法可以按四种操作模式之一使用，这四种操作模式是电子密文、密码分组链接、输
出反馈及密文反馈。其中，电子密文是最简单的模式，安全性也最差；密码分组链接则
经常以软件方法实现；输出反馈和密文反馈往往在硬件实现的算法中实现。
DES公布之后，制造有关DES设备的厂商已达几十家，大部分用于加密敏感信息。随着DE
S应用的日益扩大，各种DES专用芯片也应运而生。这种DES芯片价格便宜、加密解密速度
快，在有关产品中使用十分广泛。
不但可以用硬件而且也可以用软件实现DES算法。

DES密码的破解

在对DES密码进行鉴定的期间，美国国家保密局和计算机科学技术学会组织各界专家研究
了DES密码体制的安全性问题，讨论了破译DES密码体制的一切可能途径。尽管有些专家
和学者对它的安全性仍持怀疑态度，但官方却得出了十分乐观的结论。他们宣布：“没
有任何可以破译DES密码体制的系统分析法。若使用穷举法，则在1990年以前基本上不可
能产生出每天能破译一个DES密钥的专用计算机。即使届时能制造出这样的专用机，它的
破译成功率也只会在0.1到0.2之间，而且造价可能高达几千万美元。”
先我们考虑用穷举法破译DES 密码的问题。设已知一段密码文C及与它对应的明码文M，
用一切可能的密钥K加密M，直到得到E（M）=C，这时所用的密钥K即为要破译的密码的密
钥。穷举法的时间复杂性是T=O（n），空间复杂性是S=O（1）。对于DES密码，n=256≈
7×1016，即使使用每秒种可以计算一百万个密钥的大型计算机，也需要算106天才能求
得所使用的密钥，因此看来是很安全的。但是Diffie和Hellman指出，如果设计一种一微
秒可以核算一个密钥的超大规模集成片，那么它在一天内可以核算8.64×1010个密钥。
如果由一个百万个这样的集成片构成专用机，那么它可以在不到一天的时间内用穷举法
破译DES密码。他们当时（1977年）估计：这种专用机的造价约为两千万美元。如果在五
年内分期偿还，平均每天约需付一万美元。由于用穷举法破译平均只需要计算半个密钥
空间，因此获得解的平均时间为半天。这样，破译每个DES密码的花销只是五千美元。后
来，Diffie在1981年又修改了他们的估计，认为以1980年的技术而论，用造价为五千万
美元的专用机破译DES密码平均要花两天时间。但是他与Hellman都预计：1990年时，破
译DES密码的专用机的造价将大幅度下降。
计算及科学家Tanenbaum指出，即使没有这种专用机，也可以用穷举法破译DES。


--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 202.118.229.86]