首页
论坛
课程
招聘
DES(Weakkey,X)=X的分析
2005-12-16 13:18 16716

DES(Weakkey,X)=X的分析

2005-12-16 13:18
16716
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) ,则有:
   Ri=R(i-2) Xor f(weakkey,R(i-1))     ,其中i=1,…,16。
下面就利用逆向分析法,来求应满足的关系式:

既然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,…。即 ,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×(2^32)个。
事实上,利用DES的互补性质,只需生成2×(2^32)个明文,就可以通过取反,得到另外2×(2^32)个明文。

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

[附件]word文档,有些公式在word里用mathtype做的,论坛不能显示。

附件:des weakkey des(x)=x.rar

【看雪培训】《Adroid高级研修班》2022年夏季班招生中!

收藏
点赞0
打赏
分享
最新回复 (33)
雪    币: 193
活跃值: 活跃值 (13)
能力值: ( LV9,RANK:250 )
在线值:
发帖
回帖
粉丝
林海雪原 活跃值 6 2005-12-16 13:24
2
0

顶下
雪    币: 261
活跃值: 活跃值 (114)
能力值: ( LV9,RANK:330 )
在线值:
发帖
回帖
粉丝
laoqian 活跃值 8 2005-12-16 13:48
3
0
原来winndy是科班出身,怪不得功力深厚,我们都看不懂了 ,严重支持!
雪    币: 225
活跃值: 活跃值 (38)
能力值: ( LV9,RANK:410 )
在线值:
发帖
回帖
粉丝
killl 活跃值 10 2005-12-16 13:57
4
0
一定要学习了
雪    币: 1018
活跃值: 活跃值 (9934)
能力值: (RANK:350 )
在线值:
发帖
回帖
粉丝
kanxue 活跃值 8 2005-12-16 14:12
5
0
附件:des_c.zip

好文章,放个DES的C源码
雪    币: 341
活跃值: 活跃值 (139)
能力值: ( LV9,RANK:690 )
在线值:
发帖
回帖
粉丝
winndy 活跃值 17 2005-12-16 14:48
6
0
过奖了,
谢谢鼓励
继续努力...
雪    币: 200
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
sonic530 活跃值 2005-12-16 14:59
7
0
学习了这么多年,可是还是没有学会思考....
雪    币: 118
活跃值: 活跃值 (180)
能力值: ( LV8,RANK:130 )
在线值:
发帖
回帖
粉丝
Lenus 活跃值 3 2005-12-16 17:02
8
0
不光是研究生教育制度值得思考,更重要的是研究生的录取制度等一整套系统的问题。
雪    币: 454
活跃值: 活跃值 (22)
能力值: ( LV12,RANK:660 )
在线值:
发帖
回帖
粉丝
prince 活跃值 16 2005-12-16 17:35
9
0
好文!

政府和社会都应该反思...
雪    币: 1331
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Ivanov 活跃值 2005-12-17 01:45
10
0
可以简单的改良来对抗上面的逆推分析。
如果有兴趣,我可以粘贴出改良方式

先补充一下 楼主的示意图
雪    币: 219
活跃值: 活跃值 (20)
能力值: ( LV9,RANK:1140 )
在线值:
发帖
回帖
粉丝
冷血书生 活跃值 28 2005-12-17 03:14
11
0
绝对的好文,学习了!!
雪    币: 341
活跃值: 活跃值 (139)
能力值: ( LV9,RANK:690 )
在线值:
发帖
回帖
粉丝
winndy 活跃值 17 2005-12-17 14:29
12
0
最初由 Ivanov 发布
可以简单的改良来对抗上面的逆推分析。
如果有兴趣,我可以粘贴出改良方式

...


当然,本文的方法是针对标准DES的。
关键之处还在于最后一轮左右交换了,即R16L16。

不妨贴出来大家讨论一下。
雪    币: 1331
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Ivanov 活跃值 2005-12-17 14:58
13
0
这里帖不上数学符号,我弄到PDF上
我截了个图
雪    币: 341
活跃值: 活跃值 (139)
能力值: ( LV9,RANK:690 )
在线值:
发帖
回帖
粉丝
winndy 活跃值 17 2005-12-17 15:45
14
0
PDF打不开。
雪    币: 1331
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Ivanov 活跃值 2005-12-17 15:49
15
0
这回就可以拉,哈哈,用惯了PDF用没想来截图;

这个就可以看得很清楚了

C1和D1 创建了 K1  
做了一个小的改良选择, 这样 新的改良PC2 就有了5个位置和原始PC2 (见上帖的那个原始PC2图)有了位置的变换

再向下看

<<< 2表示 2-bit 左旋转  1=<i< 16  2< i <16
雪    币: 341
活跃值: 活跃值 (139)
能力值: ( LV9,RANK:690 )
在线值:
发帖
回帖
粉丝
winndy 活跃值 17 2005-12-17 16:07
16
0
当然装了,兄弟
而且是最新的。
雪    币: 1331
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Ivanov 活跃值 2005-12-17 16:55
17
0
kanxue对了,要麻烦你了,我上传了两个有问题的pdf,它们在你的上传目录中,mod.zip 似乎有自动添加了一个数字后缀,你找找删除了吧,辛苦了,哈哈
雪    币: 1018
活跃值: 活跃值 (9934)
能力值: (RANK:350 )
在线值:
发帖
回帖
粉丝
kanxue 活跃值 8 2005-12-17 17:07
18
0
最初由 Ivanov 发布
kanxue对了,要麻烦你了,我上传了两个有问题的pdf,它们在你的上传目录中,mod.zip 似乎有自动添加了一个数字后缀,你找找删除了吧,辛苦了,哈哈


好的
Ivanov如有什么好东西多放点出来,呵~~
雪    币: 1331
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Ivanov 活跃值 2005-12-17 17:13
19
0
主要是我看不懂中文的数学术语\再一个就是俄罗斯的数学符号与中国的不大通行; 还有一个就是论坛打不上数学符号;
所以,我放英文版看的人少,没有讨论,那就成了光占空间了
雪    币: 341
活跃值: 活跃值 (139)
能力值: ( LV9,RANK:690 )
在线值:
发帖
回帖
粉丝
winndy 活跃值 17 2005-12-17 17:18
20
0
解释一下符号的含义...
delt代表什么?
一撇代表什么?
雪    币: 341
活跃值: 活跃值 (139)
能力值: ( LV9,RANK:690 )
在线值:
发帖
回帖
粉丝
winndy 活跃值 17 2005-12-17 17:20
21
0
原来Ivanov是Russian的兄弟,:)
Welcome!

英文的没问题,放出来。
雪    币: 484
活跃值: 活跃值 (18)
能力值: ( LV9,RANK:1060 )
在线值:
发帖
回帖
粉丝
wenglingok 活跃值 26 2005-12-17 17:21
22
0
^_^,有热门话题了,关注一下。
雪    币: 1331
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Ivanov 活跃值 2005-12-17 22:02
23
0
为了pdf怕打不开,还是照像吧,哈哈
另外,不要叫我 “兄弟”,怎么总感觉有匪的味道? 咔咔
还是叫 同志吧 , 伊凡普罗夫同志;
雪    币: 1331
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Ivanov 活跃值 2005-12-17 22:03
24
0
雪    币: 1331
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Ivanov 活跃值 2005-12-17 22:07
25
0
游客
登录 | 注册 方可回帖
返回