1990年R. Merkle认识到DES快结束其生命期并提出了二个密码系统作为可能的替代品,当时其基本设计原则如下:
1.DES的56位钥长太小。考虑到增长密钥的代价是微不足道的(计算机存储器既廉又丰),应该增长密钥。
2．DES中广泛使用置换操作,虽适合于硬件实现,但软件实现是很困难的。DES的快速软件实现通过查表法实现置换,查表法可提供与置换同样的“扩散”特性并更为灵活。
3.DES中S盒太小每个盒只有64个4位项。既然存储器更大了,S盒也应加大,而且应同时使用8个S盒。虽然这适合于硬件实现,但对软件似乎是个不合理的限制,应该使用更大并且是顺序的(而不是并行的)S盒。
4.DES中的初始和最后置换普遍认为在密码效果上没有意义,应取消。所有DES的快速实现都预计算每轮中的密钥,因此没有理由不把该计算设计成更为复杂。
5.不像DES,S盒的设计应该公开。
Khufu是64位的块密码算法,64位明文块首先分成各为32位的左右二半L和R,L和R，都与同一子钥异或,再经过类似于DES的几轮迭代。每一轮中,L的最低字节用作256项S盒的输入,S盒中每一项为32位。S盒中选取的32位项与R异或,接着L循环移位8的倍数位,L与R交换,一轮结東。S盒本身也不是静止的,每8轮改变一次。最后一轮之后,L和R与更多的子钥异或,并且合并在一起形成密文块。
虽然密钥的某些部分在算法开始和结尾处与加密块异或,密钥的主要目的是生成S盒,这些S盒是保密的且本质上是部分密钥。 Merkle的算法需要512位(64字节)钥长,并由一个算法从密钥生成S盒。算法的轮数还未公开, Merkle推测几乎所有应用场合都采用16,24或32轮(他把轮数限制为8的倍数)。
由于 Khufu密钥相关且有保密的S盒,差分分析对它毫无结果。如果蛮力攻击是攻击Khufu的最好方法,它是非常难以攻破的:任何情况下,22的复杂度是不可想象的。
Khafre是由 Merkle提出的二个密码系统中的另一个( Khufu和 Khafre是以二位埃及法老而取名的), Khafre的设计类似于 Khufu,只是 Khafre是为没有预计算时间的应用场合而设计的。S盒独立于密钥, Khafre采用一组标准的S盒,并且密钥与加密块异或不仅在首轮之前和末轮之后,而且每8轮之后都执行一次。
Merkle推测 Khafre中钥长为64或128位,并且 Khafre的加密轮数比 Khufu多,再加上Khafre的每轮都比 Khufu更复杂,使得 Khafre要比 Khufu慢。另一方面, Khafre没有预计算,所以加密少量数据要比 Khufu快一些。
1990年, Biham和 Shamir用差分密码分析技术攻击 Khafre,他们以约1500个选择明文攻破16轮的 Khafre,用PC机运行了约1个小时。
