查看: 2151|回复: 3

图解CRC编解码矩阵及解码矩阵列坐标“CRC碰撞” [复制链接]

hotpower (离线)
积分
82850
帖子
313
发表于 2009-7-26 22:21:11 |显示全部楼层
关键词: CRC碰撞 , 解码 , 矩阵 , 图解 , 坐标
实际碰撞很简单,但必须心中虚构“2个CRC编解码矩阵”,碰撞会在CRC解码矩阵的列中产生。
下图列中会看见“红蓝圈发生的碰撞”。

CRCL4_D.gif


CRCL4_F.gif


CRCR4_A.gif
hotpower (离线)
积分
82850
帖子
313
发表于 2009-7-26 22:22:05 |显示全部楼层
本帖最后由 hotpower 于 2009-7-26 22:23 编辑

实际很简单,这要和CRC运算的规则有关系:
CRC运算由初值,权值,明文流和密文流四部分组成。
每次一个完整的CRC运算由初值,权值,一组对应的明文和密文。

特别注意:
CRC运算的结果即密文将作为下次CRC运算的初值或整个CRC运算的校验和。

为了完成“CRC碰撞”,就至少需要2对明文和密文。
最后1对中的密文就是我们要求碰撞的校验和。

例如(左移CRC4,权=D,想碰撞A):

第1步设想的模板:
初值:0  输入:YZ
权值 D  输出:XA

根据CRC的性质,输出中的密文X就是我们准备的“碰撞种子”。

密文X的初值=0,而且又是明文Z的初值。

第2步任选一个“碰撞种子”,如X=8.
初值:0  输入:YZ
权值 D  输出:8A

从下图中的CRC解码矩阵(CRC逆运算),可以查表:

明文Y=左移CRC解码矩阵D[初值0,密文8]=E
初值:0  输入:EZ
权值 D  输出:8A

第3步用密文8做为明文Z和密文A和CRC初值得到明文Z
初值:8  输入:Z
权值 D  输出:A

从下图中的CRC解码矩阵(CRC逆运算),可以查表:
明文Z=左移CRC解码矩阵D[初值8,密文A]=B
初值:8  输入:B
权值 D  输出:A

经过3次运算就得到了X=8,Y=E,Z=B:

填入
初值:0  输入:YZ
权值 D  输出:XA

得到
初值:0  输入:EB
权值 D  输出:8A

即第1个“碰撞种子”X=8得到明文EB,校验和=A

同理再任选一个“碰撞种子”X=9,得到:
初值:0  输入:6A
权值 D  输出:9A

故EB和6A后会得到同一个校验和A,即发生了“CRC碰撞”。

以上分解了“CRC碰撞”的过程,用工具只要填入不同的“碰撞种子”,
点击“还原”即可得到相同的校验和及对应的明文流。

CRCL4_D.gif
hotpower (离线)
积分
82850
帖子
313
发表于 2009-7-26 22:27:05 |显示全部楼层
点击下载16个CRC4编解码的贴图,可从中分析所有CRC的性质

CRC4GIF.rar

531.43 KB, 下载次数: 8, 下载积分: 积分 -1

pcbkey (离线)
积分
1662
帖子
1485
发表于 2015-2-7 10:12:40 |显示全部楼层
支持一下
您需要登录后才可以发表评论 登录 | 立即注册

关于我们  -  服务条款  -  使用指南  -  站点地图  -  友情链接  -  联系我们
电子工程网 © 版权所有   京ICP备11013910号 | 京公网安备11010502021702
回顶部