引用:
再如DES的8个S盒。(6入4出)
每个S盒有4列16行，共16行32列。
根据数学的“全排列”定义，DES的S盒排列数应该有16!=20927789888000
故此密码的编码只是其全排列的很小一部分。
CRC4和DES的S盒都属于这个全排列，CRC4有16行(明文)16列(初值、权)。
可惜在CRC4的一行(表)中找不到DES的S盒的一行~~~
但我们可以在CRC4表中到处找到S盒的“身影”。
CRC碰撞一般指CRC明文的碰撞，即CRC密钥确定时不同明文流所产生同一CRC结果的现象。
而CRC密钥碰撞是指一对CRC明文和CRC密文确定时,有多少个CRC密钥与之配对的问题。
站在CRC密钥碰撞的立场上，“CRC明文碰撞”是“一对一”的关系，而“CRC密钥碰撞”是“多对一”的关系。
前者是CRC密码的问题，后者是CRC运算的问题。故菜农自贺的是后者。
本文不再讨论CRC明文碰撞问题。
在CRC密码体系中，成员包括CRC密钥(初值、权及方向)和明文及密文三个主要部分。算法为基本的CRC运算即简单的移位和异或运算。
CRC一次运算的结果实际是在密钥下对应的一组结果即明文和密文对。
我们可以把这样的操作视为一个广义的“表”，如同S盒或特殊数组及矩阵一样。
在密钥即表的行列确定时，必得到一组唯一无重码的成员即明文和密文对。即“一对一”的关系。
但是CRC或S盒都只选取了这张全排列的广义表的其中一小部分，故不同的密钥就比对应同一结果。
即“多对一”得关系。
如S盒的“6入4出”。2^6中选2^4,必有2^2个冗余，4次密钥碰撞。
再以CRC4加以说明：
已知明文0x01，密文0x02。那么有对少个密钥即初值和权与之配对???
这实际是个类同S盒的“6入4出”的"8入4出"问题。故必有2^4个CRC密钥碰撞。
16组碰撞数据列举如下：
方向： 左移CRC4 右移CRC4
明文0x01 初值：3 E 9 6 2 9 C 5 3 7 B F A C 6 0
密文0x02 权值：1 3 5 7 9 B D F 8 9 A B C D E F
从表中可以看到：
初值=0x03 权=0x01 左移CRC4 明文0x01 得到密文0x02 即CRC校验结果0x02
初值=0x06 权=0x07 左移CRC4 明文0x01 得到密文0x02 即CRC校验结果0x02
初值=0x03 权=0x08 右移CRC4 明文0x01 得到密文0x02 即CRC校验结果0x02
初值=0x06 权=0x0E 右移CRC4 明文0x01 得到密文0x02 即CRC校验结果0x02
故得此结论：
在CRC密钥不确定即“一次一密”时，与明文及密文有关的所有攻击手段是“徒劳”的。
因为它是“多对一”即不可逆的。(这就是CRC密码或S盒应用的目的所在)
CRC密钥碰撞的“碰撞次数”恒为2^N。
即CRC4有16次CRC密钥碰撞，CRC8有256次CRC密钥碰撞...
可见DES的S盒的4次“碰撞”比CRC密钥碰撞要少许多，只不过是选择的“广义表”不同而已。
CRC的“广义表”依据CRC运算规则排列，S盒的规则排列只能去问美国大鼻子老头了~~~
“CRC密钥碰撞”是菜农选择CRC做HotWC3系统中的“S盒”最重要的原因之一。
也是菜农回应某些人嘲笑“CRC太简单”的“论据吧”~~~
S盒“号称非线性”菜农绝不认同！！！它的排列规则肯定类同CRC4.
发布文章
