关于可逆系统与不可逆系统的思考，从md5说开去(含续文)

cncxz

正在上＜信号与系统＞的课，讲到可逆系统的定义：一个系统，如果给定不同的输入，一定会得到不同的输出，就称该系统是可逆的。即输入与输出有一一对应的关系。

说到这里，我就想到了md5算法：对于不同的输入，算法的输出是不同的散列。从这点看，md5算法应该是属于可逆系统。可是md5算法又号称是不可逆的算法，即给定一个md5散列，没法从算法上得到其原始值（还是算法存在但是没人想出来！？），到底md5是可逆还是不可逆呢？

老师说：“md5应该是可逆的，因为我总可以列出一个输入与输出的对应表，即使这要花很多时间，但我总能列出来，我的逆算法就是查表，这不就可以了么？”我对老师这种说法不太同意，很困惑。

欢迎大家发表看法…

P.S.我知道有人写出两个md5值相同的程序，具体原理我不太清楚…

 

这个问题我想清楚了，感谢戴唯思和张华枫的指点。

是这样的：

我一开始想到的“对于不同的输入，算法的输出是不同的散列。”是错误的。在我们的日常生活中，确实是这样子。我的思维也就是被这日常生活所局限了。

其实MD5算法属于不可逆系统，即总可以找到N个不同的输入，产生相同的输入。

拿16位的md5来讨论：（因为32位MD5的中间16位就是其对应的16位MD5，如果硬要分析，情况是一样的。）

每一位可以是a-z,0-9共36个字母，16位就是说MD5共有36^16种散列，这就是16位MD5的最大容量。

平常我们用MD5来加密数据（这在web apps中的密码验证尤为常见），加密的都仅仅是一些很简单的字符串。

如果有这样一种情况，我要加密的内容是17位的字符串，第一位是a-z,0-9，后16位满足MD5的16位散列特征，这样MD5的常规意义上容量就不够用了，因为算法总成立，总能产生一个输出，在这种时候，就会有不同的输入产生相同的输出了。18位呢？19位呢？100位呢？

对于拿MD5来做程序文件的指纹，也是一样的道理。比如一个简单的C程序，printf输出上述的N位不同字符串即可。

现在感觉豁然开朗