DES (Weak Key,X)=X
 作者:winndy【FCG】【DFCG】【PYG】
Email:cnwinndy@hotmail.com
完稿时间:2005.12.16
如果有疑问,欢迎大家讨论。

这是密码学开卷考试的一道题目:
在DES中,若K是弱密钥,证明存在明文X,使DES(K,X)=X。
也就是明文经DES加密后还是明文自身。

一、首先应了解什么是DES弱密钥。
  
       先从DES的解密说起:
       DES的解密过程,DES的解密过程和DES的加密过程完全类似,只不过将16圈的子密钥序列K1,K2……K16的顺序倒过来。即第一圈用第16个子密钥K16,第二圈用K15,其余类推。
       如果K16=K1,K15=K2,…,K9=K8,则加密所用的子密钥与解密所用的子密钥相同,对一个明文X加密两次,得到的还是明文X。
       更强的,若K1=K2=…=K16,则加密过程与解密过程完全一样。
       弱密钥的定义也就是这样定义:若k使得加密函数与解密函数一致,则称k为弱密钥。
      DES至少有4个弱密钥,让我们先来看看子密钥的产生过程:
      
图片来自:风雨无阻,《公路坐标计算系统  1.0》。
http://www.pediy.com/bbshtml/BBS5/pediy50649.htm
要了解更详细的DES的流程,可参考上面的文章,这里只简要介绍一下。

 

64Bits的密钥K经PC-1之后,变为56Bits,然后分为高28Bits和低28Bits,分别进行移位。
LSi是循环左移。PC-2是从56Bits中选出48Bits输出。若C0和D0为全0或全1,则经过移位后显然不变,于是16个子密钥都相同。C0和D0是独立进行移位的,组合一下,就有4个弱密钥了。因此至少有4个弱密钥。
(1)K1=…=K16=0x000000000000
(2)K1=…=K16=0xFFFFFFFFFFFF
(3)K1=…=K16=0x000000FFFFFF
(4)K1=…=K16=0xFFFFFF000000

还可以注意到,第一组和第二组是互补的,第三组和第四组也是互补的。
事实上,对于任意密钥k,我们还有以下关系成立:(DES的互补性)
若y=Des(k,X),则yBar=DES(kBar,XBar)。(后缀Bar表示取补)

二、分析(逆推法)
    
刚拿到这个题目,不知怎么着手。首先想到的是从置换盒SBox着手,
                     DES的加密流程图
 

因为,如果存在明文X使得f函数的输出为0,那么由于0 Xor 0=0,0 Xor 1=1,那么若L0=R0,则L1=R2,…。最终必有R16=L0,L16=R0。
事实上,当我把SBox盒为0的情况都列举出来以后,根据每一种排列情况,看其是否满足E扩展后的格式,不幸的是,不存在任何X使得f函数的输出为0。

   回过头,再仔细观察DES的加密流程图,不能忽略这样一个Xor的基本性质:
      A Xor B=C,则A=B xor C。
同时注意到L(i-1)=Ri,其中i=1,…,16。
为了简化讨论,可以写出这样的序列:
L0,R0,R1,R2,…,R7,R8,…,R16。
不妨记L0=R-1,则有:
   
下面就利用逆向分析法,来求应满足的关系式:
 
既然L0R0加密后为R16R15,那么我们令R16=L0,R15=R0,然后来求R14看看。
R16=R14 Xor f(weakkey,R15),于是R14=R16 Xor f(weakkey,R15),
=L0 Xor f(weakkey,R0)=R1,继续推下去,…
R13=R2,…,R8=R7,…。即Ri =R15-i ;,i=-1,0,…7。
事实上,只要R8=R7,就可以推出其他的等式。很容易就可以证明。
上面,得到了R8=R7是DES(weakkey,X)=X的必要条件。
反过来,给定R8=R7,是否就有DES(weakkey,X)=X成立呢?
答案是肯定的,很容易推出来。

于是,我们可以令L0=R0,经过8圈DES加密过程,再经过IP-1,就可以得到满足要求的明文X。
我编了一个简单的程序进行了校验,结果完全是正确的。
故满足这样的要求的明文共有4×(232)个。
事实上,利用DES的互补性质,只需生成2×(232)个明文,就可以通过取反,得到另外2×(232)个明文。

三、小结
    思路很简单,逆推就可以了,在做注册机,分析算法后,要经常逆推,得到注册流程。虽然这么简单,但我还没发现周围的同学有独立思考出来的,甚至我给了提示,也有人想不出来。我们应该反思一下我们的教育制度了,而且是研究生教育……..