原创 菜农对于CRC划归单向散列函数的疑惑

原贴出处：http://bbs.pediy.com/showthread.php?t=92571

先引用有关的基本概念：

　　1、散列（HASH）函数

　　散列（HASH）函数H也称哈希函数或杂凑函数等，是典型的多到一的函数，其输入为一可变长x（可以足够的长），输出一固定长的串h（一般为128位、160位，比输入的串短），该串h被称为输入x的Hash值（或称消息摘要Message Digest、指纹、密码校验和或消息完整性校验），计作h=H（x）。为防止传输和存储的消息被有意或无意地篡改，采用散列函数对消息进行运算生成消息摘要，附在消息之后发出或与信息一起存储，它在报文防伪中具有重要应用。

　　消息摘要采用一种单向散列算法将一个消息进行换算。在消息摘要算法中，文件数据作为单向散列运算的输入，这个输入通过HASH函数产生一个散列值。如果改动了文件，散列值就会相应地改变，接收者即能检测到这种改动过的痕迹。从理论上来讲，攻击者不可能制造一个替用的消息来产生一个完全相同的消息摘要。Hash函数可用于数字签名、消息的完整性检测、消息的起源认证检测等。

　　散列函数是安全的是指它具有：

　　一致性：相同的输入产生相同的输出。

　　随机性：消息摘要外观是随机的，以防被猜出源消息。

　　唯一性：几乎不可能找到两个消息产生相同的消息摘要。

　　单向性：即如果给出输出，则很难确定出输入消息。

　　Hash函数H一般满足以下几个基本要求：

　　（1）输入x可以为任意长度；输出数据串长度固定；

　　（2）正向计算容易，即给定任何x，容易算出H（x）；反向计算困难，即给出一Hash值h，很难找出一特定输入x，使h=H（x）；

　　（3）抗冲突性（抗碰撞性），包括两个含义，一是给出一消息x，找出一消息y使H（x）=H（y）是计算上不可行的（弱抗冲突），二是找出任意两条消息x、y，使H（x）=H（y）也是计算上不可行的（强抗冲突）。

　　2、私钥加密

　　私钥加密又称为对称加密，因为同一密钥既用于加密又用于解密。私钥加密算法非常快（与公钥算法相比），特别适用于对较大的数据流执行加密转换。

　　3、公钥加密（PKCS）和数字签名

　　公钥加密使用一个必须对未经授权的用户保密的私钥和一个可以对任何人公开的公钥。用公钥加密的数据只能用私钥解密，而用私钥签名的数据只能用公钥验证。公钥可以被任何人使用；该密钥用于加密要发送到私钥持有者的数据。两个密钥对于通信会话都是唯一的。公钥加密算法也称为不对称算法，原因是需要用一个密钥加密数据而需要用另一个密钥来解密数据。

　　数据加密/编码算法列表

　　常见用于保证安全的加密或编码算法如下：

　　1、常用密钥算法

　　密钥算法用来对敏感数据、摘要、签名等信息进行加密，常用的密钥算法包括：

　　DES（Data Encryption Standard）：数据加密标准，速度较快，适用于加密大量数据的场合；

　　3DES（Triple DES）：是基于DES，对一块数据用三个不同的密钥进行三次加密，强度更高；

　　RC2和 RC4：用变长密钥对大量数据进行加密，比 DES 快；

　　IDEA（International Data Encryption Algorithm）国际数据加密算法，使用 128 位密钥提供非常强的安全性；

　　RSA：由 RSA 公司发明，是一个支持变长密钥的公共密钥算法，需要加密的文件快的长度也是可变的；

　　DSA（Digital Signature Algorithm）：数字签名算法，是一种标准的 DSS（数字签名标准）；

　　AES（Advanced Encryption Standard）：高级加密标准，是下一代的加密算法标准，速度快，安全级别高，目前 AES 标准的一个实现是 Rijndael 算法；

　　BLOWFISH，它使用变长的密钥，长度可达448位，运行速度很快；

　　其它算法，如ElGamal、Deffie-Hellman、新型椭圆曲线算法ECC等。

　　2、单向散列算法

　　单向散列函数一般用于产生消息摘要，密钥加密等，常见的有：

　　MD5（Message Digest Algorithm 5）：是RSA数据安全公司开发的一种单向散列算法，MD5被广泛使用，可以用来把不同长度的数据块进行暗码运算成一个128位的数值；

　　SHA（Secure Hash Algorithm）这是一种较新的散列算法，可以对任意长度的数据运算生成一个160位的数值；

　　MAC（Message Authentication Code）：消息认证代码，是一种使用密钥的单向函数，可以用它们在系统上或用户之间认证文件或消息。HMAC（用于消息认证的密钥散列法）就是这种函数的一个例子。

　　CRC（Cyclic Redundancy Check）：循环冗余校验码，CRC校验由于实现简单，检错能力强，被广泛使用在各种数据校验应用中。占用系统资源少，用软硬件均能实现，是进行数据传输差错检测地一种很好的手段（CRC 并不是严格意义上的散列算法，但它的作用与散列算法大致相同，所以归于此类）。


菜农长期疑惑CRC的可逆问题，也有过在网上的探讨。

“单向性：即如果给出输出，则很难确定出输入消息。”

菜农10年前已证实过CRC的半可逆性，因为菜农不是数学家，写不出什么论点和论据~~~

所以俺认为CRC应该是陷门单向散列函数。

俺真想找个数学家或密码学家探讨一番，以消除俺多年的疑惑。