打印

一直想不明白的CRC校验算法问题

[复制链接]
10265|23
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
quakegod|  楼主 | 2009-2-28 04:35 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
恕敝人少见多怪
偶一直觉得这个CRC算法里面有一个重大的BUG,
就是对一个全0值的数据段进行CRC最后等到的结果居然是0
得到了一个全0的数据包,
而这个全0的数据包恰恰是在出现错误的时候最容易出现的,
然而校验结果居然正确。
偶窃以为,应该在生成CRC后,加上一个类似55AA的数据,
这样既不破坏CRC的强壮,也能防止全0包的出现。

相关帖子

沙发
quakegod|  楼主 | 2009-2-28 04:40 | 只看该作者

再推导到其他校验算法

偶们常用的校验算法还有很多,
比如说常用的累加值校验算法,
这个算法也会产生同样的BUG,
有些是不能防全0数据,有些是不能防全1数据,
偶自己在做简单的累加和算法时,都会在累加数据上在加上一个固定值,
偶窃以为偶并没有改变算法本身的什么东东,只是改了一下表示方法,
不知道这种方法值不值得提倡。

这个问题偶想了好几年了,一直没好意思说出来。
今天斗胆发言,欢迎大家批评指正。

使用特权

评论回复
板凳
HotC51| | 2009-2-28 05:10 | 只看该作者

我个人最喜欢数据包CRC后的结果再1次CRC后结果为0

简单地说,若数据包长8个字节,CRC8次后得到1结果。

若将此结果再进行1次CRC运算,则结果为0.

利用此现象,我们就可以不去比对CRC的合法性即可知道数据包的CRC是正确的。

楼主说“对一个全0值的数据段进行CRC最后等到的结果居然是0”。

我可以理解:对一个全0值的数据段长度-1进行CRC后的结果为0.

则再进行1次(此时到了数据段的最大长度),即对0再CRC(此时为0)结果也应该

为0.

故这不是什么"CRC重大的BUG".

即使其他演算方法,如求和,异或等都无法避免这种全零数据的问题。




相关链接:http://www.google.cn/search?hl=zh-CN&q=crc+hotpower&meta=&aq=f&oq=

使用特权

评论回复
地板
HotC51| | 2009-2-28 06:15 | 只看该作者

关于CRC表及HotPower的CRC/PEC网上计算器用法简介

开课:

看到近来阶级敌人为CRC“打得头破血流”,俺农忙“无力参战”~~~

故本课给大家看看菜农的小玩具~~~源码可以用IE的“查看”--“源文件”

看到CRC的源文件,它是个JavaScript脚本语言做的,目的就是让大家看源程序~~~

同时,也想有天有人来答复菜农“CRC可逆”即CRC有无“反函数”的问题。


至今未有答案~~~俺十分之郁闷~~~

期望吴旭光教授赶紧给俺找个数学家来帮菜农解谜~~~

unsigned int crc_ta[256]={ /* CRC余式表 */
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,
0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,
0x 1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6,

0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de,
0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485,
0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d,
0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4,
0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc,
0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823,
0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b,
0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12,
0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a,
0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41,
0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49,
0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70,
0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78,
0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f,
0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067,
0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e,
0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256,
0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d,
0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,

0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c,
0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634,
0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab,
0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3,
0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a,
0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92,
0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9,
0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1,
0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8,
0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0
};

HotPower的CRC/PEC网上计算器用法简介:
1.在右下角选择"16位左移"CRC运算方式。

  此时出现"初值=0",“权=0x0810”.

2.在输入键入4位所需的演算数字
  如: CRC16[0xff]=0x1ef0.
  在“输入处输入”:0x00ff 点击“计算”
  (实际是“加密”,俺没好意思写,怕“数学家”的砖头)
  这时:“输出”处显示:1EF0
同理:
  如: CRC16[0x01]=0x1021.(俺称之为1021法~~~)
  在“输入处输入”:0x0001 点击“计算”
  这时:“输出”处显示:1021
同理:
  如: CRC16[0x10]=0x1231.
  在“输入处输入”:0x0010 点击“计算”
  这时:“输出”处显示:1231

3.演算HotPower的CRC/PEC网上计算器的“还原”及解密过程

  菜农酷爱CRC算法,虽然搞不出为什么。一直迷恋了20年之久~~~
  当91年攻克了美国FLUK的64为CRC密码后,就琢磨着CRC是否“可逆”
  
  居然又被俺猜中,而且悟出了“权”,这样就得到了“初值”和“权”
  何为CRC的“密钥”。
  
  为了在网上让大家直接玩耍,在俺做“JavaScript语言菜鸟”时,菜鸟
  的唯一“作品”就是这个程序~~~

  “还原”及解密步骤:
   CRC16[0xFE]=0x0ED1
   
   1)在“输出”键入"0ED1",注意此时“初值”="0000",“权”="0810"
   2)点击“还原”,“输出”得到“00FE”
     这样即可验证了CRC16[0xFE]=0x0ED1,
     即:
     “初值”="0000",“权”="0810",“明文”="00FE"时,
     “密文”="0ED1"
     反之:
     “初值”="0000",“权”="0810",“密文”="0ED1"时,
     “明文”="00FE"
     
   3)变换“密钥”
     将“初值”改为“0250”~~~俺喜欢这个
     再“权”也改为“0250”~~~2个也有意思~~~
     “输出”即“密文”不变="0ED1"。
     “还原后”则“输入”即“明文”就为“7FE1”~~~
     
     将“初值”改回"0000",“权”改回"0810",
    “还原后”则“输入”即“明文”就为“00FE”~~~

   4)关于“权”“同方向加权”的重码问题
     现在可以看到,当“权”不变时,看不出问题,但是。
     当选择“16位左移”,则“同方向加权”即“左面最高位置1”
     
     即将“权”变为"8810"时,可以会惊奇地发现:
    “计算”“还原”结果都不变!!!~~~

   这个菜农做了8、16、32、64的“左移”和“右移”的CRC运算,
   可惜没做12、24、48的,至今很是“后悔”~~~

   但是“菜鸟的”“热情”已过,打死俺也不会再做了~~~
   因为只有一个字:“眼晕”~~~


哈哈~~~大家都为CRC战斗吧~~~俺只关心能有一位数学家为菜农

验证俺一直不解的“CRC可逆过程”~~~

也想知道数学界对俺一个“知识老农民”无知的“数学脑浆”“琢磨”
出来的“CRC密码”的“强度”有多高~~~


俺手里还有2个“级别高的CRC滚动密码的”网上计算器版本~~~

https://bbs.21ic.com/upfiles/img/20092/200922872315539.gif

https://bbs.21ic.com/upfiles/img/20092/200922872418649.gif

https://bbs.21ic.com/upfiles/img/20092/200922872458145.gif

https://bbs.21ic.com/upfiles/img/20092/200922872444566.gif

https://bbs.21ic.com/upfiles/img/20092/20092287259646.gif

  

课毕

HotC51@126.com   2009.2.27于菜地。
团部:http://group.**/1623/

相关链接:http://www.hotpage.net.cn/hotpower/HotPower三角及冗余校验密码技术.htm

使用特权

评论回复
5
quakegod|  楼主 | 2009-2-28 07:58 | 只看该作者

偶晕,

看来 HotC51 根本没有明白偶要说的意思。
偶要说的是 
“而这个全0的数据包恰恰是在出现错误的时候最容易出现的情况,”
假如说,在Flash芯片中存数据,528个字节中,512个存数据,剩16个存校验,
结果这528个字节同时被毁了,都变成0了,
明明数据全都错了,而你处理程序却还傻傻的认为,CRC校验没有错误,数据还可以拿来用的。
又或者说,在数据传输过程中,产生了持续的干扰,使整个数据包的数据都变成全0,
偶不是说CRC算法的问题,而是说,这么一个弱智的BUG怎么会没有被发现呢,怎么还会使用了这么长时间呢。

好不容易发的一个帖子被广告贴毁了,偶要重新开贴。

使用特权

评论回复
6
HotC51| | 2009-2-28 08:30 | 只看该作者

哈哈~~~不识好人心~~~随你去吧,阿门

使用特权

评论回复
7
学生D| | 2009-2-28 15:38 | 只看该作者

其实接收端与发送端的最后CRC是不一样的。


假定发送端发送报文为2字节0x00,0x00(简化表达为 0000H),那么假定现在CRC累加器初值设为16位 FFFFH;这样2字节报文0000H的CRC余数为1DF0H,(HDLC协议规定FCS采用R(x)的反码,即:发送端发送数据为0000E20FH。到这里,理解都是没有疑问的。

关键是接收端:接收报文0000e2f0H经过CRC校验电路后得到余数FFFFH这是没错的。(FFFFe2f0/11021的余数为FFFFH。)但是接收端是把0000E2F0H作为报文而不是0000H作为保文!因此在接收端的算式是:

0000E2F00000/11021=FFFF0000/11021=F0EF 余数 1D0FH

也就是说:凡是按照HDLC/SDLC规程设计的通信控制器,接收端电路是对0000E2F00000h进行的运算(相对发送报文源码0000H来说),对于任何字节长度的报文,(如果接收报文正确的话)接收端CRC运算电路最终都是对FFFF0000h进行的运算,所以最终余数正确值是1D0Fh。 而不是0000或者FFFFH。

有没有可能错误发生后正好错算出1D0FH?   除非就是所发送报文在到达接收端之前的途中连续错了NM位(NM>17还是33?),(奇偶校验校验一位。CRC16或者CRC32校验17或32位。)并且如此恰好地落入了FFFF设定的最高不可能发生初值。

使用特权

评论回复
8
学生D| | 2009-2-28 15:56 | 只看该作者

HOT老师把国际标准的东西当作是自己的创新,不太好吧。

“我个人最喜欢数据包CRC后的结果再1次CRC后结果为0。”
???!!!
********************************************************************
不知看懂了我的**没有:——这就是阶级敌人的好处。

凡是按照HDLC/SDLC规程设计的通信控制器,对于任何字节长度的报文,(如果接收报文正确的话)接收端CRC运算电路最终都是对FFFF0000h进行的运算,所以最终余数的正确值是1D0Fh。 而不是0000或者FFFFH。

也就是说,在30年前,国际...协会就规定了:接收端的CRC电路对接收到的报文(发送端带有CRC值的报文)再一次进行CRC运算,也就是当CRC累加器初值为FFFFH时,对FFFF0000H进行运算,结果必为1D0FH。

看懂了吗?用你的计算器计算一下FFFF0000H/11021H看看是不是等于1D0FH?

我是用手算的,与协议标准一致。

使用特权

评论回复
9
hotpower| | 2009-2-28 15:58 | 只看该作者

哈哈~~~“权”是俺“发明的”~~~

使用特权

评论回复
10
学生D| | 2009-2-28 17:11 | 只看该作者

你的权是CCITT-16,即11021H,国际标准。

FE/11021=F1  余数 0ED1h
10/11021=11  余数 1231H
FF/11021=F0  余数 1EF0h 

不用上机,眼睛都看得出来。

至于0810H,加权G(x)=0810+1831=1021H
1831就算密匙?


看一下上个世纪1988年铁道出版社出版的 《实用纠错编码》这本书。

再看看1990年铁道出版社出版的《信息论与编码方法》,《实用纠错编码》。

拿书上的东西忽悠菜鸟!






使用特权

评论回复
11
ZRL700424| | 2009-2-28 17:14 | 只看该作者

忽悠,接着忽悠!

使用特权

评论回复
12
学生D| | 2009-2-28 17:14 | 只看该作者

你的表是从书上抄来的?

不是自己算的吧。《串行通信编程指南》上有,即使网上下的也要注明作者。

抄的就要注明摘抄出处,现在讲究学者的基本道德。

使用特权

评论回复
13
hotpower| | 2009-2-28 18:21 | 只看该作者

哈哈~~~菜农从不抄袭“地球人之术”~~~这个俺80年代

91年俺雷翻了美国鬼子~~~

学生D 发表于 2009-2-28 17:11 侃单片机 ←返回版面    

10楼: 你的权是CCITT-16,即11021H,国际标准。 

FE/11021=F1  余数 0ED1h
10/11021=11  余数 1231H
FF/11021=F0  余数 1EF0h 

不用上机,眼睛都看得出来。

至于0810H,加权G(x)=0810+1831=1021H
1831就算密码?


看一下上个世纪1988年铁道出版社出版的 《实用纠错编码》这本书。

再看看1990年铁道出版社出版的《信息论与编码方法》,《实用纠错编码》。

拿书上的东西忽悠菜鸟!
 
 
哈哈~~~俺村里要早有这些玩意,俺真没今天~~~

正因为俺“不学无术”,才造就了今天“无法无天”,看不起“地球人”之狂热~~~

使用特权

评论回复
14
hotpower| | 2009-2-28 18:25 | 只看该作者

跪求“阶级敌人”~给俺找个数学泰斗,问问CRC可逆及反函

哈哈~~~等村里的教授论证出来,这“黄瓜菜”都凉了~~~

使用特权

评论回复
15
学生D| | 2009-2-28 20:33 | 只看该作者

敬重hotpower老师,咱没有恶意。

咱100%相信您所有的东西都是自己研究的。我只是说如果您好不容易花了若干年想出了一个解决方案或者诀窍,本以为地球人谁也想不到,结果得意了若干年,突然知道,世界上20年前就有人解决了,并且解决方法比您还要好。不知您心里是什么滋味?

美国科技界曾有此先例,某某科学家A宣称发现了什么奥秘,一时轰动,正得意时,有人拿出证据,说10年前,某某科学家B早就写了论文证明了这个原理,结果众皆哗然,骂A欺骗了全世界。其实A并没有造假,不过是无知,研究前缺少调研,现在A怎么办?
顶不住舆论压力,自杀了!

使用特权

评论回复
16
HotC51| | 2009-2-28 20:45 | 只看该作者

俺也绝对尊重“阶级敌人”~~~俺已四处跪求数学大师,会有

我准备网上跪求数学“泰山”们:

1。CRC是否可逆,即有无反函数。

2.若有,俺的源码"htm"的方法和他们的一样吗???

3.给出"htm"文件就是要鉴定真伪,让菜农"离开地球前"安心

  否则,俺不愿意“到了火星”还背着“剽窃地球人CRC逆运算之恶名”~~~

俺现在已经拜托了3个人~~~

使用特权

评论回复
17
HotC51| | 2009-2-28 21:06 | 只看该作者

俺主要是用它来作为密文通讯,而且解密比加密更快之特点

网上计数器纯属是为MCU人在1-wire,hdq16,smbus等场合提供方便之工具。

而且菜农也比较过此类工具。

因为俺的权是随意的,故俺认为它概括了所有“地球人”小工具之特点。

不过自己要设定“初值”、“权”、“位数”及“方向”这4项设置。

使用特权

评论回复
18
学生D| | 2009-2-28 21:34 | 只看该作者

hot 老师会不会自杀?

HOT老师:如果我证明了你的CRC逆反公式,那么您就会成为笑料。到时侯您是选择下课还是选择为尊严“自杀”?

因为您一直在说:“地球人不可能想到....”

我看了一下,....那么简单的事也要吹?数学教授比我差远了。

不想让你难堪,敢不敢赌一把?



使用特权

评论回复
19
HotC51| | 2009-2-28 22:54 | 只看该作者

“阶级敌人”把菜农看扁了~菜农刚打完“美国鬼子”,俺还

俺真诚地需要知道俺的问题~~~

首先若有雷同,俺会向推倒“菜农公式”一样向122年前的蔡勒同志敬礼!!!

当然俺实现是知道星期的大概算法,但绝没仔细研究~~~

因为俺从小就有一个梦:“长大了俺自己推出星期公式”,所以俺根本就不知道

世上还有个“蔡勒同志”

至于CRC密码,俺会更高兴看到“XXX同志”~~~因为俺曾打击过美国3大CRC高手~~~

菜农一生清贫,现在也是“做人要低调”~~~至今村里只有3个小朋友知道俺是

菜农~~~前天由被一人发现,惊呼时,俺捂住了他的嘴~~~

本来他很清高,总认为俺是个戴草帽的农民伯伯~~~

俺不会自杀~~~因为俺要看到“帝国主义灭亡的那一天”~~~

使用特权

评论回复
20
HotC51| | 2009-2-28 23:03 | 只看该作者

有功夫研究研究~~~

使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

27

主题

1882

帖子

18

粉丝