[原创]如何手工计算0x31333134的CRC-32值？-付费问答-看雪-安全社区|安全招聘|kanxue.com

[旧帖] [原创]如何手工计算0x31333134的CRC-32值？ 0.00雪花

发表于: 2008-3-28 22:24 11789

[旧帖] [原创]如何手工计算0x31333134的CRC-32值？ 0.00雪花

tnttools

2008-3-28 22:24

11789

如何手工计算0x31333134的CRC-32值？

献给那些永远充满着好奇心的人们
有些答案永远在二进制洪流中飘

[前言]

这几天，分析某软件算法时，涉及到CRC。在重拾记忆碎片时，发现有网友提出一个问题：如何手工计算0x31333134的CRC-32值。我乐于接受这个挑战。因为此任务可以强化我的记忆。（虽然已经我的大脑证明，2年前写的东西我已经可以全部忘光。但愿这次，我可以记得更久一些。）

[过程]

CRC-32标准有着各种各样的变形，下面的参数集定义的是最常见的一个，也是本文中采用的CRC-32算法。

―――――――――――――――――― [Ross93]

Name : "CRC-32"

Width : 32

Poly(Reverse) : 04C11DB7( EDB88320 )

Init : FFFFFFFF

RefIn : True

RefOut : True

XorOut : FFFFFFFF

Check : CBF43926

――――――――――――――――――

[预备知识1]

最常见的一种解决方案

little-endian CPU

－－－－－－－－－－－－

每一个字节内，相对低位的比特位是多项式中的相对高位的系数；

每一个机器字内，相对低位的字节是多项式中的相对高位的系数。

－－－－－－－－－－－－

big-endian

－－－－－－－－－－－－这样来表述：

每一个字节内，相对低位的比特位是多项式中的相对高位的系数；

每一个机器字内，相对高位的字节是多项式中的相对高位的系数。

－－－－－－－－－－－－

每一次模2除法的被除数：上一次模2除法的余数+上一次未参与运算的被除数的低位

模2除法的余数总比除数少1位。

polynormical arithmetics多项式运算，特指没有进位的多项式加法和乘法、没有借位的多项式减法和除法。

模n多项式运算：对运算结果的各项系数进行模n运算，运算过程中各项系数的加减执行模n加、模n减。

Step I. 被除数是什么？

0010 1100 1000 1100 1100 1100 1000 1100 … …

+ 1111 1111 1111 1111 1111 1111 1111 1111 … …

1101 0011 0111 0011 0011 0011 0111 0011 … …（这就是被除数）

注I． … …表示跟在后面的无穷字节

0x31333134在CRC, Little-endian的语境中，要表示成多项式的话，应该所有n比特位与所有的32-n比特位互调位置，结果如下

3 1 3 3 3 1 3 4

0011 0001 0011 0011 0011 0001 0011 0100

0010 1100 1000 1100 1100 1100 1000 1100

Init 值为FFFFFFFF，它表示上一次高位的模2除法运算的余数，理所当然要加到本次除法中。

Step II. 除数是什么？

1 0000 0100 1100 0001 0001 1101 1011 0111（这就是除数）

因为Poly(Reverse)的值为04C11DB7( EDB88320 )，表示成二进制数就是

0000 0100 1100 0001 0001 1101 1011 0111

在说明除数Poly时，一般省略了最高位32位的比特1。

所以，别忘了最高位32位的1，它保证了CRC-32的结果值为32位，...

Step III. 计算

记住，是无进位的多项式模2除法

被除数（后面的32个比特零仅仅是余数的占位符）

1101001101110011001100110111001100000000000000000000000000000000 … …

除数

100000100110000010001110110110111

过程-> 商，余数

-> 1,

101000100010011101111011010100010000000000000000000000000000000

-> 11,

01000000100011111110101100010101000000000000000000000000000000

-> 1101,

000001101111111010110001111000110000000000000000000000000000

-> 1101000001,

101110110110110101100101011101110000000000000000000000

-> 11010000011,

01110010000110111101011101011001000000000000000000000

-> 1101000001101

110011001010111001000000110100110000000000000000000

-> 11010000011011

10011101100111011001110000010001000000000000000000

-> 110100000110111

0011111111111010001001011001010100000000000000000

-> 110100000110111001

1111101100010000001100010001111100000000000000

-> 1101000001101110011

111100101110000101111111100010010000000000000

-> 11010000011011100111

11100001000000111110001010100101000000000000

-> 110100000110111001111

1100011011000110110110001111110100000000000

登录后可查看完整内容

[注意]看雪招聘，专注安全领域的专业人才平台！

收藏・3

免费・7

支持

最新回复 (7)
sskey 雪币： 216 活跃值： (26) 能力值： ( LV4，RANK：50 ) 在线值：发帖 10 回帖 152 粉丝 0 关注私信	sskey 1 2 楼学习................. 2008-3-28 22:27 0
scz 雪币： 5398 活跃值： (4232) 能力值： ( LV12，RANK：240 ) 在线值：发帖 15 回帖 253 粉丝 71 关注私信	scz 5 3 楼先谢过，待我回头看完并验证了再来请教。你是我个人碰到过的惟一一个肯解答我这个变态问题的人，十分感谢。在下的初等数学基本还给了中学老师，要慢慢看。顺便先问一下，我用现成的工具计算hex string，"31333134"或者计算ascii串"1314"，得到的结果都是0xa817e816，由于我还未能仔细消化你的运算过程，可能这个问题比较愚蠢，见谅。 2008-3-29 15:08 0
tnttools 雪币： 297 活跃值： (27) 能力值： ( LV13，RANK：380 ) 在线值：发帖 15 回帖 96 粉丝 1 关注私信	tnttools 9 4 楼我确实就是想回答你的问题。但在写文章计算到一半时，发现我计算的是C型字符串"4131"，而不是你要求的"1314"，就是说我计算的是另一个字符串。但只要你根据我的文章的思路，慢慢地算，你也会找到答案。文章中已经加入"1314"的计算过程，欢迎纠错。 2008-3-29 18:14 0
scz 雪币： 5398 活跃值： (4232) 能力值： ( LV12，RANK：240 ) 在线值：发帖 15 回帖 253 粉丝 71 关注私信	scz 5 5 楼非常感谢！待我拜读。 2008-3-29 22:02 0
bluecode 雪币： 303 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 4 回帖 184 粉丝 0 关注私信	bluecode 6 楼哈.非常感谢tnttools 正在找此类文章.看了N个都看不明白. 看了tnttools大侠的文章后,感觉明白了许多. 2008-3-30 00:27 0
scz 雪币： 5398 活跃值： (4232) 能力值： ( LV12，RANK：240 ) 在线值：发帖 15 回帖 253 粉丝 71 关注私信	scz 5 7 楼 (我把tnttools的文字风格化了一下) tnttools@pediy给出了最终手工运算过程，他是唯一一个正面解答了我的困惑的人，十分感谢。 -------------------------------------------------------------------------- [PKZIP, AUTODIN II, Ethernet, FDDI] Width : 32 Poly : 04C11DB7 : x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + x^0 : (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) Init : FFFFFFFF RefIn : True RefOut : True XorOut : FFFFFFFF -------------------------------------------------------------------------- (Poly:04C11DB7) \| v 0000 0100 1100 0001 0001 1101 1011 0111 \| (给出Poly时，一般省略了最高位的1，实际运算时要补上) \| v 1 0000 0100 1100 0001 0001 1101 1011 0111 \| v (这就是除数) "\x31\x33\x31\x34" (原始数据) \| (展开成二进制表示) \| v 0011 0001 0011 0011 0011 0001 0011 0100 \| (RefIn:True) \| v 1000 1100 1100 1100 1000 1100 0010 1100 \| (Init:FFFFFFFF) \| v 1000 1100 1100 1100 1000 1100 0010 1100 1111 1111 1111 1111 1111 1111 1111 1111 +(模2加法，非进位算术加法，就是异或) --------------------------------------- 0111 0011 0011 0011 0111 0011 1101 0011 (由于是与全1异或，实际就相当于取反) \| (在尾部添加0，0的个数比除数的2进制位数少1，就本例而言，添加32个0) \| v 0111 0011 0011 0011 0111 0011 1101 0011 0000 0000 0000 0000 0000 0000 0000 0000 \| v (这就是被除数) 进行多项式长除法运算: 1110010110111011010101100101110(我们不关心商) +---------------------------------------------------------------- 100000100110000010001110110110111 ) 111001100110011011100111101001100000000000000000000000000000000 100000100110000010001110110110111 --------------------------------- 110010000000110011010010111110110 100000100110000010001110110110111 --------------------------------- 100101001101100010111000010000010 100000100110000010001110110110111 --------------------------------- 101101011100000110110100110101000 100000100110000010001110110110111 --------------------------------- 110111101000010011101000001111100 100000100110000010001110110110111 --------------------------------- 101110011100100011001101110010110 100000100110000010001110110110111 --------------------------------- 111011101010000100001100010000100 100000100110000010001110110110111 --------------------------------- 110110011000001100000101001100110 100000100110000010001110110110111 --------------------------------- 101101111100011100010111110100010 100000100110000010001110110110111 --------------------------------- 110101101001111001100100001010100 100000100110000010001110110110111 --------------------------------- 101010011111110111010101111000110 100000100110000010001110110110111 --------------------------------- 101011100111010101101100111000100 100000100110000010001110110110111 --------------------------------- 101100000101011110001000111001100 100000100110000010001110110110111 --------------------------------- 110010001101110000011000111101100 100000100110000010001110110110111 --------------------------------- 100101010111100100101100010110110 100000100110000010001110110110111 --------------------------------- 101110001100110100010100000001000 100000100110000010001110110110111 --------------------------------- 111010101011011001101011011111100 100000100110000010001110110110111 --------------------------------- 110100011010110111001011010010110 100000100110000010001110110110111 --------------------------------- 101001111001101010001011001000010 100000100110000010001110110110111 --------------------------------- 10010111111010000001011111101010(余数) 1001 0111 1110 1000 0001 0111 1110 1010 (余数) \| (RefOut:True) \| v 0101 0111 1110 1000 0001 0111 1110 1001 \| (XorOut:FFFFFFFF) \| v 0101 0111 1110 1000 0001 0111 1110 1001 1111 1111 1111 1111 1111 1111 1111 1111 +(模2加法，非进位算术加法，就是异或) --------------------------------------- 1010 1000 0001 0111 1110 1000 0001 0110 (由于是与全1异或，实际就相当于取反) \| v 0xA817E816 (最终结果) 我当时手工计算失败的原因在于没有针对下列参数进行相应处理，只是简单地进行多项式长除法运算: -------------------------------------------------------------------------- Init : FFFFFFFF RefIn : True RefOut : True XorOut : FFFFFFFF -------------------------------------------------------------------------- 再次感谢tnttools@pediy的手工运算过程。 2008-3-31 13:28 0
zhaoyutg 雪币： 200 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 2 回帖 14 粉丝 0 关注私信	zhaoyutg 8 楼学习了。。。。。。 2008-3-31 15:42 0
	游客登录 \| 注册方可回帖回帖表情雪币赚取及消费高级回复

tnttools

发帖

回帖

380

RANK

关注

私信

他的文章

关于我们

联系我们

企业服务

看雪公众号

最新回复 (7)
sskey 雪币： 216 活跃值： (26) 能力值： ( LV4，RANK：50 ) 在线值：发帖 10 回帖 152 粉丝 0 关注私信	sskey 1 2 楼学习................. 2008-3-28 22:27 0
scz 雪币： 5398 活跃值： (4232) 能力值： ( LV12，RANK：240 ) 在线值：发帖 15 回帖 253 粉丝 71 关注私信	scz 5 3 楼先谢过，待我回头看完并验证了再来请教。你是我个人碰到过的惟一一个肯解答我这个变态问题的人，十分感谢。在下的初等数学基本还给了中学老师，要慢慢看。顺便先问一下，我用现成的工具计算hex string，"31333134"或者计算ascii串"1314"，得到的结果都是0xa817e816，由于我还未能仔细消化你的运算过程，可能这个问题比较愚蠢，见谅。 2008-3-29 15:08 0
tnttools 雪币： 297 活跃值： (27) 能力值： ( LV13，RANK：380 ) 在线值：发帖 15 回帖 96 粉丝 1 关注私信	tnttools 9 4 楼我确实就是想回答你的问题。但在写文章计算到一半时，发现我计算的是C型字符串"4131"，而不是你要求的"1314"，就是说我计算的是另一个字符串。但只要你根据我的文章的思路，慢慢地算，你也会找到答案。文章中已经加入"1314"的计算过程，欢迎纠错。 2008-3-29 18:14 0
scz 雪币： 5398 活跃值： (4232) 能力值： ( LV12，RANK：240 ) 在线值：发帖 15 回帖 253 粉丝 71 关注私信	scz 5 5 楼非常感谢！待我拜读。 2008-3-29 22:02 0
bluecode 雪币： 303 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 4 回帖 184 粉丝 0 关注私信	bluecode 6 楼哈.非常感谢tnttools 正在找此类文章.看了N个都看不明白. 看了tnttools大侠的文章后,感觉明白了许多. 2008-3-30 00:27 0
scz 雪币： 5398 活跃值： (4232) 能力值： ( LV12，RANK：240 ) 在线值：发帖 15 回帖 253 粉丝 71 关注私信	scz 5 7 楼 (我把tnttools的文字风格化了一下) tnttools@pediy给出了最终手工运算过程，他是唯一一个正面解答了我的困惑的人，十分感谢。 -------------------------------------------------------------------------- [PKZIP, AUTODIN II, Ethernet, FDDI] Width : 32 Poly : 04C11DB7 : x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + x^0 : (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) Init : FFFFFFFF RefIn : True RefOut : True XorOut : FFFFFFFF -------------------------------------------------------------------------- (Poly:04C11DB7) \| v 0000 0100 1100 0001 0001 1101 1011 0111 \| (给出Poly时，一般省略了最高位的1，实际运算时要补上) \| v 1 0000 0100 1100 0001 0001 1101 1011 0111 \| v (这就是除数) "\x31\x33\x31\x34" (原始数据) \| (展开成二进制表示) \| v 0011 0001 0011 0011 0011 0001 0011 0100 \| (RefIn:True) \| v 1000 1100 1100 1100 1000 1100 0010 1100 \| (Init:FFFFFFFF) \| v 1000 1100 1100 1100 1000 1100 0010 1100 1111 1111 1111 1111 1111 1111 1111 1111 +(模2加法，非进位算术加法，就是异或) --------------------------------------- 0111 0011 0011 0011 0111 0011 1101 0011 (由于是与全1异或，实际就相当于取反) \| (在尾部添加0，0的个数比除数的2进制位数少1，就本例而言，添加32个0) \| v 0111 0011 0011 0011 0111 0011 1101 0011 0000 0000 0000 0000 0000 0000 0000 0000 \| v (这就是被除数) 进行多项式长除法运算: 1110010110111011010101100101110(我们不关心商) +---------------------------------------------------------------- 100000100110000010001110110110111 ) 111001100110011011100111101001100000000000000000000000000000000 100000100110000010001110110110111 --------------------------------- 110010000000110011010010111110110 100000100110000010001110110110111 --------------------------------- 100101001101100010111000010000010 100000100110000010001110110110111 --------------------------------- 101101011100000110110100110101000 100000100110000010001110110110111 --------------------------------- 110111101000010011101000001111100 100000100110000010001110110110111 --------------------------------- 101110011100100011001101110010110 100000100110000010001110110110111 --------------------------------- 111011101010000100001100010000100 100000100110000010001110110110111 --------------------------------- 110110011000001100000101001100110 100000100110000010001110110110111 --------------------------------- 101101111100011100010111110100010 100000100110000010001110110110111 --------------------------------- 110101101001111001100100001010100 100000100110000010001110110110111 --------------------------------- 101010011111110111010101111000110 100000100110000010001110110110111 --------------------------------- 101011100111010101101100111000100 100000100110000010001110110110111 --------------------------------- 101100000101011110001000111001100 100000100110000010001110110110111 --------------------------------- 110010001101110000011000111101100 100000100110000010001110110110111 --------------------------------- 100101010111100100101100010110110 100000100110000010001110110110111 --------------------------------- 101110001100110100010100000001000 100000100110000010001110110110111 --------------------------------- 111010101011011001101011011111100 100000100110000010001110110110111 --------------------------------- 110100011010110111001011010010110 100000100110000010001110110110111 --------------------------------- 101001111001101010001011001000010 100000100110000010001110110110111 --------------------------------- 10010111111010000001011111101010(余数) 1001 0111 1110 1000 0001 0111 1110 1010 (余数) \| (RefOut:True) \| v 0101 0111 1110 1000 0001 0111 1110 1001 \| (XorOut:FFFFFFFF) \| v 0101 0111 1110 1000 0001 0111 1110 1001 1111 1111 1111 1111 1111 1111 1111 1111 +(模2加法，非进位算术加法，就是异或) --------------------------------------- 1010 1000 0001 0111 1110 1000 0001 0110 (由于是与全1异或，实际就相当于取反) \| v 0xA817E816 (最终结果) 我当时手工计算失败的原因在于没有针对下列参数进行相应处理，只是简单地进行多项式长除法运算: -------------------------------------------------------------------------- Init : FFFFFFFF RefIn : True RefOut : True XorOut : FFFFFFFF -------------------------------------------------------------------------- 再次感谢tnttools@pediy的手工运算过程。 2008-3-31 13:28 0
zhaoyutg 雪币： 200 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 2 回帖 14 粉丝 0 关注私信	zhaoyutg 8 楼学习了。。。。。。 2008-3-31 15:42 0
	游客登录 \| 注册方可回帖回帖表情雪币赚取及消费高级回复