首页
社区
课程
招聘
[讨论]已知许多密文和明文,密文长度仅32bit,怎么推测其算法? (已压缩为16bit,提供更多密文对)
发表于: 2009-3-29 21:42 12941

[讨论]已知许多密文和明文,密文长度仅32bit,怎么推测其算法? (已压缩为16bit,提供更多密文对)

2009-3-29 21:42
12941
有一个黑盒算法,输入一个32bit数的密文,输出一个解密后明文,也是32bit
我可以手工输入一些特别的密文,如下,然后让黑盒解密,输出的结果在右边。

密文   ->算法-> 明文
00 00 00 00  ->  C3 80 28 33
00 00 00 01  ->  C3 80 28 32
00 00 00 02  ->  C3 80 02 05
00 00 00 03  ->  C3 80 3F A8
  FF FF FF FF  -> 40 0A AB B9
55 55 55 55  ->  F2 71 19 C2
AA AA AA AA  ->  84 60 6F D3
01 01 01 01  ->  EB 83 00 30
5A 5A 5A 5A  ->  FB 3B 10 88
A5 A5 A5 A5  ->  99 A5 72 16

请问推测解密算法的方法,谢谢。
比如再取什么特别的密文,让其解密,从而更容易发现特征?
32bit到32bit,除了换位,异或,还有什么不损失信息的对称加密办法?

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!

收藏
免费 0
支持
分享
最新回复 (20)
雪    币: 58
活跃值: (28)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
2
问楼主几个问题:
1、根据该算法,你输入密文00 00 00 00,将输出解密结果C3 80 28 33。
请问你如果输入C3 80 28 33,输出结果是否为00 00 00 00?(即算法是否可逆。)
2、现在的密码算法一般有一个密钥控制,你现在的算法没有相关密钥设置吗?
2009-3-30 18:29
0
雪    币: 208
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
算法是一个黑箱,不是我写的。 我现在只有一堆密文明文,然后数据仅32bit,
我估计还是可以分析出怎么换位和异或的。

32bit的,可能会是DES或blowfish的对称算法吗?

我希望有人能提示一下,有什么有效分析的方法?
2009-3-30 23:38
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
des会有雪崩效应,00 00 00 00  ->  C3 80 28 33,00 00 00 01  ->  C3 80 28 32,改变量不大,应该不是des
不知道有没有记忆错
2009-3-30 23:49
0
雪    币: 156
活跃值: (48)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
5
32 位 如果你能利用这个黑盒
生成一个全集的对应表不就 破解了
还管他是什么算法干什么
2009-3-31 20:27
0
雪    币: 58
活跃值: (28)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
6
根据现在的算法,如果能够用程序自动生成2^32个输入与输出的对应关系,的确就拥有了该算法的全部知识。 不过看LZ的意思,好像只能手工输入一些例子来做测试。
2009-3-31 20:41
0
雪    币: 58
活跃值: (28)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
7
根据LZ提供的几个例子,肯定不是DES或blowfish这种对称算法,因为这些算法是非常复杂的,不可能产生如下的输入输出关系对:
00 00 00 00  ->  C3 80 28 33
00 00 00 01  ->  C3 80 28 32
00 00 00 02  ->  C3 80 02 05
00 00 00 03  ->  C3 80 3F A8

如果想通过观察输入-输出关系来判断算法的部分逻辑,可以从逻辑函数的角度去分析。
实际上,32bit输出的每1 bit都是32 bit输入的一个逻辑函数(所谓逻辑函数,可以理解成32bit输入值的与、或、非逻辑操作),这其实是一个典型的密码分析问题,如果LZ很希望解决这个问题,可以将软件公布出来,大家看看吧。
2009-3-31 20:48
0
雪    币: 993
活跃值: (442)
能力值: ( LV12,RANK:403 )
在线值:
发帖
回帖
粉丝
8
假设密文4字节为A B C D,对应的明文4字节为a b c d,从已知结果看,对一组密文A=B=C=D和另一组密文A'=B'=C'=D'的明文结果进行对照,就会发现它们的明文结果按字节异或后有一个明显的特征,就是a^a'=c^c'和b^b'=d^d',很明显密文的4字节被分成两组,AB和CD各为一组,因为从已知结果的前四个可以看出,CD变化并没有影响到AB的对应输出,因此,基本上该算法的原理为一张65536大小的代替表,实现f(AB)->ab的变化,而且AB和CD两个分组用的是同一张代替表,只是在代替运算后,对各自的结果再异或上一个不同的值EF和GH,而且EF和GH在整个算法中是固定的,也就是最终的模型应该是ab = f(AB)^EF,cd = f(CD)^GH。纯属个人猜测,仅供参考。
2009-4-1 01:01
0
雪    币: 208
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
9
首先,谢谢楼上各位的分析。
这个黑箱是个数字电路,是颗ASIC,应该只有几K的容量,所以应该不会有代替表。只能用逻辑运算,ASIC速度很快,可以进行非常多次的运算,可以异或、换位、循环移位。

我现在只是手工输入一些参数,让其解密。后续我也可以自动输入所有参数,让其输出更多结果。当然,不能存成一个替代表,那样太大了。
2009-4-1 23:49
0
雪    币: 58
活跃值: (28)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
10
Loka的分析有道理,代替表是数学模型的等价描述,真正实现还是简单的逻辑运算的组合。
但要分析出到底是什么样的逻辑组合,LZ需要给大家提供更多的输入输出关系来观测。
2009-4-2 00:39
0
雪    币: 993
活跃值: (442)
能力值: ( LV12,RANK:403 )
在线值:
发帖
回帖
粉丝
11
不错,从等价关系上说函数f是一张65536的代替表,但它应该是由一些简单的运算操作组成,如果能再给出更多的对应数据,分析出f不是难题。
2009-4-2 00:44
0
雪    币: 201
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
12
先写个小程序,自动输入所有参数,得到对照表,容易找到规律。
2009-4-2 08:29
0
雪    币: 101
活跃值: (12)
能力值: ( LV12,RANK:210 )
在线值:
发帖
回帖
粉丝
13
输入雷格码看看输出的变化。。
2009-4-2 09:53
0
雪    币: 208
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
14
谢谢,你说的是“格雷码”吧?
请等待我提供完整的密文明文数据吧。
2009-4-2 22:52
0
雪    币: 208
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
15
根据LoKa的提示,我已经把ab = f(AB)^EF,cd = f(CD)^GH 中的异或值去掉了,

异或的值就是              ^  C3 80 28 33
00 00 00 00  ->  C3 80 28 33  异或后->  00 00 00 00
00 00 00 01  ->  C3 80 28 32  异或后->  00 00 00 01
00 00 00 02  ->  C3 80 02 05  异或后->  00 00 2a 36
00 00 00 03  ->  C3 80 3F A8  异或后->  00 00 17 9b
  FF FF FF FF  -> 40 0A AB B9    异或后-> 83 8a 83 8a
55 55 55 55  ->  F2 71 19 C2   异或后-> 31 f1 31 f1
AA AA AA AA  ->  84 60 6F D3  异或后-> 47 E0 47 E0  
01 01 01 01  ->  EB 83 00 30   异或后-> 28 03 28 03  
5A 5A 5A 5A  ->  FB 3B 10 88   异或后-> 38 bb 38 bb     
A5 A5 A5 A5  ->  99 A5 72 16   异或后-> 5a 25 5a 25   (确实如LoKa所说,异或后,ab和cd 一样了)

这样32bit就压缩为16bit的问题。
00 00  -> 00 00
00 01  -> 00 01
00 02  -> 2a 36
00 03  -> 17 9b
FF FF  -> 83 8a
55 55  -> 31 f1
AA AA  -> 47 E0  
01 01  -> 28 03  
5A 5A  -> 38 bb     
A5 A5  -> 5a 25

另外,还增加了下面128行的数据,够不够分析出f(AB)的算法?

AB           ab
密文   -> 明文
00 2E -> BB D6
00 44 -> 9C C0
00 84 -> 01 69
07 1A -> 76 5C
07 51 -> 69 DE
09 F4 -> 9E 2D
0A 7C -> 8B 84
0A F2 -> 2A 43
0B 5B -> C9 A6
0B 92 -> 54 16
0C B5 -> 90 43
0C D2 -> BD BA
0F 4E -> 69 A6
11 36 -> BD D5
11 53 -> 8C 1D
11 CA -> EA A4
12 3A -> 0F 6C
12 F8 -> A6 33
16 16 -> A5 EB
16 75 -> 48 45
17 49 -> 4B 50
17 5F -> C4 F4
18 14 -> 58 9F
19 72 -> FE 09
1A 6C -> 78 7B
1B 0A -> A4 5C
1D AF -> D3 28
1D E2 -> 91 68
1E 53 -> 43 01
1E FC -> 9C 78
1F 89 -> CF 33
1F C9 -> 0C DC
20 39 -> 25 6E
20 B4 -> 99 43
22 D7 -> 22 F2
24 C5 -> 7D 7F
24 F8 -> EE 2B
26 B5 -> F6 BE
27 0A -> 9E F3
27 94 -> 1D 5E
28 A7 -> 0B 85
29 11 -> 1E E4
2B 4B -> 83 45
2C 78 -> 71 E2
2C 82 -> 45 BC
2C AF -> 63 C5
2D 06 -> C1 49
2D A8 -> 2A 28
2F B7 -> F7 7D
30 F2 -> 98 84
33 4F -> A2 8B
34 17 -> 35 1D
35 15 -> 31 73
36 48 -> EF CF
37 BD -> A5 25
38 16 -> FB DE
39 07 -> B9 BC
3B EC -> 4F 1D
3C 26 -> 97 25
3D 65 -> 17 27
40 66 -> A8 0A
41 87 -> B6 90
41 8F -> 40 90
42 6E -> 9E 7D
42 89 -> 30 F2
45 53 -> 3A A6
47 34 -> 30 BA
49 64 -> CC E4
49 79 -> B0 53
49 A0 -> 0E DE
4A 3B -> F3 F7
4A D9 -> 43 B9
4B 4D -> B0 11
4C 2C -> 58 15
4F 70 -> 77 B5
51 8B -> CC C3
55 2F -> 02 A5
56 03 -> 43 13
58 F6 -> 29 4E
5B D3 -> 5B 94
5B E5 -> 91 6E
5E 5D -> 66 14
5F C9 -> 10 71
60 FB -> F3 1B
63 05 -> 59 9A
64 7A -> 98 CE
65 9D -> C7 8E
66 3E -> 90 F0
67 23 -> 42 20
67 2B -> E5 F8
67 8F -> 62 E8
68 F2 -> 9F 2B
69 CC -> 38 02
6B 36 -> EE E9
6D F6 -> FD 53
6E B6 -> 39 DF
73 1D -> D2 44
73 78 -> FE 33
73 F4 -> 4B CA
76 A3 -> 52 8D
78 A6 -> 61 05
78 F3 -> 52 B1
7B C9 -> 17 42
7C FF -> 55 53
7D 3D -> EF 6B
7E 11 -> AA 47
7E 42 -> 7A 43
7E AE -> 7D F9
7E C4 -> 27 AE
80 4A -> C8 D9
80 A9 -> 7A B0
81 18 -> 22 CE
81 FB -> 87 C2
82 75 -> 72 D7
83 E3 -> 24 6F
83 E4 -> 71 23
84 81 -> 57 9D
84 DC -> D9 25
85 30 -> F6 E9
85 A0 -> 42 D8
86 70 -> BD EC
87 F4 -> 84 95
88 1A -> 88 0A
89 AC -> 60 71
89 DB -> 68 CA
8A 8A -> E3 CA
8D 31 -> A3 53
8D 7A -> 7B BB
2009-4-20 23:19
0
雪    币: 201
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
16
AB为什么不每个差1?
2009-4-21 10:30
0
雪    币: 993
活跃值: (442)
能力值: ( LV12,RANK:403 )
在线值:
发帖
回帖
粉丝
17
正如Jeffcjh所说,假设密文为a0~a15,明文为b0~b15,那分析的第一步就是要找到b中每一比特究竟对应a中哪些比特的变化。来个笨人笨法。
即然把坐标原点简化至00 00 -> 00 00那么一个一个分析,
00 01 -> 00 01   0000 0000 0000 0001  -> 0000 0000 0000 0001
从这个信息中我们唯一可以得知的就是b15的变化一定与a15有关
00 02 -> 2a 36   0000 0000 0000 0010  -> 0010 1010 0011 0110
和坐标原点对比有b2、b4、b6、b10、b11、b13、b14与a14有关。
00 03 -> 17 9b   0000 0000 0000 0011  -> 0001 0111 1001 1011
和坐标原点对比有b3、b5、b6、b7、b8、b11、b12、b14、b15可能与a14、a15的变化有关。
和00 01、00 02组对比有b3、b5、b6、b7、b8、b11、b12、b14与a14有关,b2、b3、b4、b5、b7、b8、b10、b12、b13、b15与a15有关
01 01 -> 28 03   0000 0001 0000 0001  -> 0010 1000 0000 0011
和00 01组对比有b2、b4、b14与a7变化有关
通过比对数据之间的变动,你慢慢可以归纳出每个bi与每个ai之间的关系,全部理清之后再进行第二步分析,就是逐一针对各个bi,和已经找出与之变化有关联的各个ai,分析出具体的计算式,看看各个ai是如何参与运算的,结果得出之时也就是你收工之时。
2009-4-21 13:41
0
雪    币: 208
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
18
我现在的疑惑就是,16bit到16bit的变换,是一个bit影响一个bit呢?
还是几个bit影响一个bit?

如果是几个bit影响一个bit,这样信息不是压缩了吗?
如果要反过来,从明文生成密文,等于是个解压的过程?

另外,我可以生成完整的64KWord数据,然后写软件来自动分析。
比如画成一个xy的坐标图
只是,我对这个f(AB)没有概念,不知道分析哪个概率?
2009-4-21 15:30
0
雪    币: 993
活跃值: (442)
能力值: ( LV12,RANK:403 )
在线值:
发帖
回帖
粉丝
19
如果是1bit影响1bit,那就不用分析了,那是最简单的了,0和1再怎么变也还是0和1。
几bit影响1bit不见得信息就一定会被压缩,这和线性方程是一回事。
比如 ~a1 = b1
       a1^a2 = b2
a1和a2共同影响b2,但信息没有丢失,你有a1和a2能计算出b1和b2,同样,你有b1和b2一样能计算出a1和a2。
现在的问题在于如果f函数恰如你所说的是一个芯片中的逻辑操作的组合,那上面说的分析方法加上你拥有的64K数据,基本可以算是搞定了。但如果f函数中有类似DES中S盒的东东,那就有点麻烦了。
2009-4-21 17:07
0
雪    币: 202
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
20
学习了。很有启发。
2009-4-21 19:04
0
雪    币: 208
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
21
谢谢Loka ,还要好好理解消化你的解释,感冒了,等我头脑清醒一点继续。
2009-4-22 11:04
0
游客
登录 | 注册 方可回帖
返回
//