专栏中心

EEPW首页 > 专栏 > CRC密钥碰撞及S盒的遐想

CRC密钥碰撞及S盒的遐想

发布人：0750long 时间：2009-07-11 来源：工程师

加入技术交流群
- 扫码加入
  和技术大咖面对面交流
  海量资料库查询

引用:

再如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.

专栏文章内容及配图由作者撰写发布，仅供工程师学习之用，如有侵权或者其他违规问题，请联系本站处理。联系我们

关键词：

更多焦点

更多视频

专栏中心

CRC密钥碰撞及S盒的遐想

相关推荐

感应电加热自动控制电路

自动点烟器

持续扭矩驱动峰值性能

混合用于低功耗传感器的模拟和数字脉冲神经网络

光电自动控制器

触摸式报警器电路

四弦_花样流水呼吸灯

《嵌入式Linux驱动程序设计》讲课视频下载

朔萌阁主_八位灯交叉闪烁

网络犯罪分子攻击智能家居，BadBox 2.0 僵尸网络在全球蔓延

三年暴涨50%！全球首个AI家庭机器人龙头赴港上市

赛灵思Virtex-7 GTX收发器演示

《嵌入式Linux系统的电源管理》PDF课件下载

芯片巨头，「扔掉」这些业务

ysjabcd_速度里程计带时间显示.红外调时

《嵌入式Linux系统开发基础》视频下载

《嵌入式Linux系统开发基础》PDF课件下载

有人用过思创vxworks的bsp吗？交流一下啊。

高温IC设计基础知识：环境温度和结温

在 WWDC 25 上，苹果应该就 AI 不足和诉讼向开发者进行赔偿

s3c2500,bootloader问题？（急，疑！）

《嵌入式Linux系统的存储技术》PDF课件下载

这款“机器人鸟”以 45 英里/小时的速度在森林中飞行——无需 GPS 或灯光

高手，近来看看

地平线CEO余凯：未来两到三年，自动驾驶「飞入寻常百姓家」

1.1 亿欧元计划用于在德累斯顿建设 GF 晶圆

[原创]《8位单片机的无线时代和无线时代的8051单片机》

ylzhjy_日期、时间的显示与调整

求教：Vxworks编译问题

微波防盗报警电路

技术专区