Chinaunix

标题: 如何计算这样一类文件的md5 [打印本页]

作者: liubinbj 时间: 2006-06-10 19:23
标题: 如何计算这样一类文件的md5
一般文件的md5编码很简单，照着算法做或md5sum就可以。
问题是我们现在需要在文件本身里写入这个文件的md5信息，而不是用外部文件来表达，举例来说，有一个文本文件，我们在最后告诉读者这个文件的md5为xxxxxxxxxxxx，而你通过md5sum计算这个文件的时候恰好是文件内容中的md5编码。
还有一例，比如制作了电影文件到后期处理，需要添加字幕显示当前电影文件的md5码以便观众确认这个版本的文件是正版，这个字幕本身包含了md5信息，只是表现方式是图形方式。

问题是这样的md5可不可以通过某种方式被计算得到？

作者: wolf0403 时间: 2006-06-11 01:14
参考 TCP header 计算 checksum 的办法。预先在文件中留空白串（"\0\0\0\0..." 足够写入整个 MD5 结果为准），计算 MD5SUM，然后把结果写入预留空间。进行检验的时候，把这个部分的内容置 '\0' 计算，然后再与包含的结果进行比较。

作者: liubinbj 时间: 2006-06-11 13:22

原帖由 wolf0403 于 2006-6-11 01:14 发表
参考 TCP header 计算 checksum 的办法。预先在文件中留空白串（"\0\0\0\0..." 足够写入整个 MD5 结果为准），计算 MD5SUM，然后把结果写入预留空间。进行检验的时候，把这个部分的内容置 '\0' 计算，然 ...

checksum是可以累加的，你可以留白后期再算，md5似乎不能这么做，不知道你是否了解md5的计算方式，它本质上是个hash码。

一个最简单的例子是：
建立一个新文件，在文件中写下一个md5码并保存，并用md5算法来计算这个字符串得到的结果就是原来这个串，用公式来表达就是：

md5(stringA)=stringA ----------1

当有其他文本时公式变成
md5(stringB+stringA)=stringA --------2

对于1式请给出一个或多个解stringA
对于2式，已知stringB,要求一个满足条件的stringA

问题是方程是非线性的md5算法不是checksum算法，所以要求这个方程好像比较难哦，我没有找到方法，所以来问，但感觉楼上的说法不对，似乎不那么简单。

作者: yulc 时间: 2006-06-12 13:48
如果有这种方法,做出来一定要通知我!
我将不远万里赶来膜拜!

作者: ppcl 时间: 2006-06-12 14:22

原帖由 liubinbj 于 2006-6-11 13:22 发表

checksum是可以累加的，你可以留白后期再算，md5似乎不能这么做，不知道你是否了解md5的计算方式，它本质上是个hash码。

一个最简单的例子是：
建立一个新文件，在文件中写下一个md5码并保存，并用md5算法 ...

你没看懂2楼的意思，仔细读10遍，如果再想不出来，别做了。

作者: isjfk 时间: 2006-06-12 16:04
不用吧，再读一篇还理解不了的话建议 lz 改行算了...

我开玩笑的。

PS: 如果 lz 真能在电影的字幕（存在电影文件里的字幕，不是通过字幕文件附加的）里放上 md5 码，那建议 lz 马上入美国国籍，今年的图灵奖肯定是你的了...

还是开玩笑的，别介意...

作者: liubinbj 时间: 2006-06-12 23:58

原帖由 yulc 于 2006-6-12 13:48 发表
如果有这种方法,做出来一定要通知我!
我将不远万里赶来膜拜!

我感觉我做不出来，我遗憾不能受到你的膜拜。

作者: liubinbj 时间: 2006-06-13 00:01

原帖由 isjfk 于 2006-6-12 16:04 发表
不用吧，再读一篇还理解不了的话建议 lz 改行算了...

我开玩笑的。

PS: 如果 lz 真能在电影的字幕（存在电影文件里的字幕，不是通过字幕文件附加的）里放上 md5 码，那建议 lz 马上入美国国籍，今年的图 ...

再读了一遍，理解了他的意思，他给的方法不包含编码自身的编码。和我需要的不一致。

不知道是否有谁证明过不存在一个多项式算法能计算这个问题
即解方程：
md5(x)=x
或者方程
md5(const+x)=x

有谁证明过方法不存在呢？

[ 本帖最后由 liubinbj 于 2006-6-13 00:06 编辑 ]

作者: flw 时间: 2006-06-13 08:07

原帖由 liubinbj 于 2006-6-13 00:01 发表

再读了一遍，理解了他的意思，他给的方法不包含编码自身的编码。和我需要的不一致。

不知道是否有谁证明过不存在一个多项式算法能计算这个问题
即解方程：
md5(x)=x
或者方程
md5(const+x)=x

有谁证 ...

这个问题不是
如何解方程
md5(data+md5sum) = md5sum
这么简单的问题，
事实上，如果是视频的话，
方程式实际上是这样的：
md5(data+f(md5sum)) = md5sum
其中 data 是常量，f 是另一个函数，该函数把一个字符串转换成一个用来呈现该字符串的视频流。

to liubinbj：
大家也没说不可能，
或许也是有可能的，
所以才让做出来的人去拿图灵奖呀！
如果根本就做出来，
那怎么让人家去拿图灵奖？

[ 本帖最后由 flw 于 2006-6-13 08:08 编辑 ]

作者: ppcl 时间: 2006-06-13 14:29

原帖由 flw 于 2006-6-13 08:07 发表

这个问题不是
如何解方程
md5(data+md5sum) = md5sum
这么简单的问题，
事实上，如果是视频的话，
方程式实际上是这样的：
md5(data+f(md5sum)) = md5sum
其中 data 是常量，f 是另一个函数，该函数把一 ...

其实这个不是想象中那么难，山东大学的某位教授已经破解了MD5，将寻找MD5冲突的时间缩短了若干个数量级，现在貌似已经能在40分钟的时间内找到MD5的一个冲突，所以伪造这个字符串已经是可能的了。

作者: flw 时间: 2006-06-13 14:56

原帖由 ppcl 于 2006-6-13 14:29 发表

其实这个不是想象中那么难，山东大学的某位教授已经破解了MD5，将寻找MD5冲突的时间缩短了若干个数量级，现在貌似已经能在40分钟的时间内找到MD5的一个冲突，所以伪造这个字符串已经是可能的了。

如果你学过数学的话，
你就会知道，
解方程

md5(data) = md5(x) data 为常量 (1)

复制代码

和解方程

md5(data + foo(x)) = x (2)

复制代码

有多大区别。

为了能够让你更加容易理解我想要表达的意思，
我们不妨把上面的两个方程做个变换：
对于 (1) 式，它其实等价于下面这个式子：

md5(x) = str str 为常量 (1')

复制代码

对于 (2) 式，它其实包含了下面这种情况：

md5(foo(x)) = x (2')

复制代码

你现在再比较一下 (1') 和 (2')，到底后者比前者复杂多少。

[ 本帖最后由 flw 于 2006-6-13 15:02 编辑 ]

作者: ppcl 时间: 2006-06-13 15:22

原帖由 flw 于 2006-6-13 14:56 发表

如果你学过数学的话，
你就会知道，
解方程
md5(data) = md5(x) data 为常量
也即
md5(x) = str str 为常量
和解方程
md5(data + foo(x)) = x
有多大区别。

我的数学水平不需要楼上来评价,不见得比楼上差.

不偏离问题了,先看楼主的原文:
-----------------
问题是我们现在需要在文件本身里写入这个文件的md5信息，而不是用外部文件来表达，举例来说，有一个文本文件，我们在最后告诉读者这个文件的md5为xxxxxxxxxxxx，而你通过md5sum计算这个文件的时候恰好是文件内容中的md5编码。
还有一例，比如制作了电影文件到后期处理，需要添加字幕显示当前电影文件的md5码以便观众确认这个版本的文件是正版，这个字幕本身包含了md5信息，只是表现方式是图形方式。
-----------------

首先假设已经存在一个寻找MD5冲突的算法: 即,给定初始的MD5 state,通过计算加入一些字节,最终可以得出需要的MD5值.
以第二个问题为例,只需要事先任意选定一个MD5 值,将其做入字幕之中,得到最终可播放的文件,计算当前文件的MD5,得出一个MD5 state, 然后以这个MD5 state为起始,执行上述的冲突寻找算法,在文件后面附加算法得出的填充内容.即得到楼主想要的结果.

当然,这个解法是理论上的,寻找MD5冲突的算法是否能够达到我说的程度也未可见,所以具体实现起来也不见得能成功,还是建议楼主使用其它的方法.

[ 本帖最后由 ppcl 于 2006-6-13 17:16 编辑 ]

作者: JohnBull 时间: 2006-06-13 16:59
LZ的思路不可行，换。

作者: flw 时间: 2006-06-13 18:52
在文件后面附加算法得出的填充内容
-------------
不知道附加之后能不能显示成字幕？

作者: assiss 时间: 2006-06-13 21:21

原帖由 ppcl 于 2006-6-13 14:29 发表

其实这个不是想象中那么难，山东大学的某位教授已经破解了MD5，将寻找MD5冲突的时间缩短了若干个数量级，现在貌似已经能在40分钟的时间内找到MD5的一个冲突，所以伪造这个字符串已经是可能的了。

即便用王教授的方法，楼主的问题可能仍然无法得到解决。
找到冲突！=按指定的前提字串找到冲突

作者: supersarah 时间: 2006-06-15 00:04
提示: 作者被禁止或删除内容自动屏蔽

作者: gnap 时间: 2006-06-15 07:38
大家是不是偏题了哦？我觉得LZ是否考虑把文件的格式分为header和body。只对body进行散列，结果放在header里面。这样不就行了？

作者: supersarah 时间: 2006-06-15 09:22
提示: 作者被禁止或删除内容自动屏蔽

作者: gnap 时间: 2006-06-15 14:26
晕哦！各位是不是把问题复杂化了？

其实不散列文件头不就行了。RPM包里面不是有分header、signature、archive的吗？。散列时候只散列header和archive,散列的值存储在signature里面。此在PGP的签名也在signature里面。

[ 本帖最后由 gnap 于 2006-6-15 15:20 编辑 ]

作者: isjfk 时间: 2006-06-15 16:22
lz 已经把楼上的方法否定了~

算啦，lz 自己研究去吧，我等还是等他研究出来再去膜拜好了

作者: liubinbj 时间: 2006-06-22 16:17
很多人认为能够有效求解方程
md5(const+x) =x
或
md5(x)=x
就是破解了md5算法
我倒不这么认为。

拿md5(x)=x来说，你可以通过暴力找到一两个这样的解（虽然我没有去找，是否确实存在也不可知），但并不代表任意给出一个md5可以反推出原文件内容，实际根本也不可能推出原文件的内容，因为md5是有损的。那么是否能够有效求解md5(x)=x就可以有效求解这么一个问题，即已知一个文件的md5，我往这个文件中差进一个常数数据使得结果的md5保持不变来实现伪造文件呢？用数学来表示就是：
存在有效求解md5(x)=x或md5(x+const)=x可以推出
存在有效求解md5(x+const)=z 其中y和z是已知数据，且md5(const)=z,要求一个满足方程的x使得原数据const被伪造而且原md5的结果z保持不变
这两类问题是等价的吗？个人感觉不是，如果后者存在有效求解方法，那md5就完了，目前为止还没有这样的算法可以做到，也就是md5继续存在的理由。但是如果前者的问题和后者是等价的，那前者也就不可解。
那么这两个问题是等价的吗？谁能够证明这一点？看来这真是一个数学问题了。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)