本帖最后由 hotpower 于 2011-12-25 07:14 编辑
CRC不可逆的“真谛”
根据《菜农CRC可逆定理》：
在任意CRC多项式对应的CRC算法中，当CRC多项式满足一定条件时，该CRC移动方向上
可能存在CRC的逆向算法，CRC逆向算法确保从CRC正向算法的运算结果即CRC校验值中
逆算出原始输入时的待校验信息。
任意CRC多项式字符串可逆条件判别：
CRC多项式字符串内出现“+1”时存在CRC逆向算法，不出现“+1”时不存在CRC逆向算法。
任意CRC多项式数字权值可逆条件判别：
若将CRC多项式对应的数字值称为CRC权值，则有具体CRC移动方向的判别：
对于左移CRC运算，CRC权值为奇数时存在CRC逆向算法，偶数时不存在CRC逆向算法。
对于右移CRC运算，CRC权值为负数时存在CRC逆向算法，正数时不存在CRC逆向算法。
给出CRC4表达式：左移CRC4=X4+X3+X2+X，初值=0，出值=0
对应的CRC4简写：CRCL4_E_0_0
根据《菜农CRC可逆定理》：CRC4权值可逆=0xF,CRC4权值不可逆=0xE,
//CRC位域8表(大端):
const unsigned char CRCL4_E_Table[16] = {//此表不可逆
0x0,0xE,0x2,0xC,0x4,0xA,0x6,0x8,0x8,0x6,0xA,0x4,0xC,0x2,0xE,0x0
};
可以看出0x1,0x3,0x5,0x7,0x9,0xB,0xD,0xF这8个数据在表中(CRC[明文]对应的密文)从未出现
那么久意味着0~F这16个明文只对应0x0,0xE,0x2,0xC,0x4,0xA,0x6,0x8这8个密文。
发生了一半的CRC碰撞，即每两个明文对应一个密文。
给出CRC4表达式：右移CRC4=X4+X3+X2+X，初值=0，出值=0
对应的CRC4简写：CRCR4_7_0_0
根据《菜农CRC可逆定理》：CRC4权值可逆=0xF,CRC4权值不可逆=0x7,
//CRC位域8表(小端):
const unsigned char CRCR4_7_Table[16] = {//此表不可逆
0x0,0x1,0x2,0x3,0x4,0x5,0x6,0x7,0x7,0x6,0x5,0x4,0x3,0x2,0x1,0x0
};
可以看出0x8,0x9,0xA,0xB,0xC,0xD,0xE,0xF这8个数据在表中(CRC[明文]对应的密文)从未出现
那么久意味着0~F这16个明文只对应0x0,0x1,0x2,0x3,0x4,0x5,0x6,0x7这8个密文。
发生了一半的CRC碰撞，即每两个明文对应一个密文。
故我们可以给出CRC不可逆的“真谛”：
在CRCn中(n=4,...128,...1024...),其CRC位域8表中元素的排列若属于全排列(2^n)!的一组子排列，
那么此CRCn的权值必然是可逆的，即满足《菜农CRC可逆定理》中对可逆的定义。
否则此CRCn的权值必然是不可逆的，即不满足《菜农CRC可逆定理》中对可逆的定义。而且其排列一定
是全排列(2^n)!的一组子排列的一半。此时发生“CRC碰撞”，故CRC不可逆、
菜农HotPower@126.com 2009.12.15 于雁塔菜地 |
楼主
