首页
社区
课程
招聘
[旧帖] [原创]如何手工计算0x31333134的CRC-32值? 0.00雪花
2008-3-28 22:24 11273

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

2008-3-28 22:24
11273
如何手工计算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

-> 1101000001101110011111
100010010100110010101100010011010000000000

-> 11010000011011100111111
00010110010110000100010100101101000000000

-> 110100000110111001111110001
0110000101000101010011110110011100000

-> 11010000011011100111111000101
10000001110101000010000000101011000

-> 110100000110111001111110001011
0000011101101001010111011110000100

-> 11010000011011100111111000101100
00011101101001010111011110000100

因为人工计算和机器计算的差异,结果要反序存放
00100001111011101010010110111000
最后还要与0xFFFFFFFF值异或(XorOut : FFFFFFFF)
1101 1110 0001 0001 0101 1010 0100 0111
所以最后的结果是:
DE115A47


[致谢]

Ross, [Ross93]  PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS
My Family, though you all will never have interest in taking a look of this shit.


[补充]


如何手工计算0x31 0x33 0x31 0x34的CRC-32值?
ASCII C型字符串”1314”用十六进制数表示是0x31 0x33 0x31 0x34 0x00
ASCII C型字符串”4131”用十六进制数表示是0x34 0x31 0x33 0x31 0x00
我在上文中计算的是”4131”的CRC-32值,现在计算”1314”的CRC-32值。

在这里,要注意,对于字符串"1314"和数据流0x31 0x33 0x31 0x34 0x00的计算结果是不同的。对于针对字符串的算法,当遇到0x00时便停止计算;对于针对数据流的算法,0x00要继续参与计算。对于针对字符串的算法,是把NULL字符作为停止计算的条件;对于针对数据流的算法,是把到达整个数据流的长度作为停止计算的条件。

Step I. 被除数
1000 1100 1100 1100 1000 1100 0010 1100
+   1111 1111 1111 1111 1111 1111 1111 1111 … …
=
+   0111 0011 0011 0011 0111 0011 1101 0011  (被除数)


Step II. 除数

1 0000 0100 1100 0001 0001 1101 1011 0111(这就是除数)


Step III. 计算


被除数(后面的32个比特零是余数的占位符)
0111001100110011011100111101001100000000000000000000000000000000 … …

除数
100000100110000010001110110110111

-> 商,余数
-> 01,
11001000000011001101001011111011000000000000000000000000000000
-> 011
1001010011011000101110000100000100000000000000000000000000000
-> 0111
001011010111000001101101001101010000000000000000000000000000
-> 0111001
011011110100001001110100000111110000000000000000000000000
-> 011100101
1011100111001000110011011100101100000000000000000000000
-> 0111001011
011101110101000010000110001000010000000000000000000000
-> 011100101101
1101100110000011000001010011001100000000000000000000
-> 0111001011011
101101111100011100010111110100010000000000000000000
-> 01110010110111
01101011010011110011001000010101000000000000000000
-> 0111001011011101
101010011111110111010101111000110000000000000000
-> 01110010110111011
01010111001110101011011001110001000000000000000
-> 0111001011011101101
010110000010101111000100011100110000000000000
-> 011100101101110110101
0110010001101110000011000111101100000000000
-> 01110010110111011010101
10010101011110010010110001011011000000000
-> 011100101101110110101011
0010111000110011010001010000000100000000
-> 011100101101110110101011001
0111010101011011001101011011111100000
-> 01110010110111011010101100101
11010001101011011100101101001011000
-> 011100101101110110101011001011
1010011110011010100010110010000100
-> 0111001011011101101010110010111
010010111111010000001011111101010
-> 01110010110111011010101100101110
10010111111010000001011111101010

结果倒序存放
01010111111010000001011111101001
与0xFFFFFFFF异或
10101000000101111110100000010110
转换成十六进制数,为
A817E816

TnTTools
The ART of Reverse Engineering
Enjoy it.

[培训]《安卓高级研修班(网课)》月薪三万计划

收藏
点赞7
打赏
分享
最新回复 (7)
雪    币: 216
活跃值: (26)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
sskey 1 2008-3-28 22:27
2
0
学习.................
雪    币: 3999
活跃值: (2986)
能力值: ( LV12,RANK:230 )
在线值:
发帖
回帖
粉丝
scz 5 2008-3-29 15:08
3
0
先谢过,待我回头看完并验证了再来请教。

你是我个人碰到过的惟一一个肯解答我这个变态问题的人,十分感谢。

在下的初等数学基本还给了中学老师,要慢慢看。

顺便先问一下,我用现成的工具计算hex string,"31333134"或者计算ascii串"1314",得到的结果
都是0xa817e816,由于我还未能仔细消化你的运算过程,可能这个问题比较愚蠢,见谅。
雪    币: 297
活跃值: (27)
能力值: ( LV13,RANK:380 )
在线值:
发帖
回帖
粉丝
tnttools 9 2008-3-29 18:14
4
0
我确实就是想回答你的问题。但在写文章计算到一半时,发现我计算的是C型字符串"4131",而不是你要求的"1314",就是说我计算的是另一个字符串。但只要你根据我的文章的思路,慢慢地算,你也会找到答案。

文章中已经加入"1314"的计算过程,欢迎纠错。
雪    币: 3999
活跃值: (2986)
能力值: ( LV12,RANK:230 )
在线值:
发帖
回帖
粉丝
scz 5 2008-3-29 22:02
5
0
非常感谢!待我拜读。
雪    币: 303
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
bluecode 2008-3-30 00:27
6
0
哈.非常感谢tnttools
正在找此类文章.看了N个都看不明白.
看了tnttools大侠的文章后,感觉明白了许多.
雪    币: 3999
活跃值: (2986)
能力值: ( LV12,RANK:230 )
在线值:
发帖
回帖
粉丝
scz 5 2008-3-31 13:28
7
0
(我把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的手工运算过程。
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
zhaoyutg 2008-3-31 15:42
8
0
学习了。。。。。。
游客
登录 | 注册 方可回帖
返回