00 c3 b3+c2 a3+b2+c1 右移记存器.
00+d3 c3+d2 b3+c2+d1 a3+b2+c1+d0 上面两行对应位做XOR运算. 现在记存器是: (d3) (c3+d2) (b3+c2+d1) (a3+b2+c1+d0) Processing fourth byte, W:
(a3+b2+c1+d0)+W 这是顶部字节的计算结果(4). e3 e2 e1 e0 这是(4)在表中索引对象序列. 00 d3 c3+d2 b3+c2+d1 右移记存器.
00+e3 d3+e2 c3+d2+e1 b3+c2+d1+e0 上面两行对应位做XOR运算. 最后,记存器为: (e3) (d3+e2) (c3+d2+e1) (b3+c2+d1+e0)
我用一个不同一点的方法来表示:
a0 + X =(1) 在表中指向 b3 b2 b1 b0 a1 + b0 + Y =(2) 在表中指向 c3 c2 c1 c0 a2 + b1 + c0 + Z =(3) 在表中指向 d3 d2 d1 d0 a3 + b2 + c1 + d0 + W =(4) 在表中指向 e4 e3 e2 e1 b3 + c2 + d1 + e0 =f0 c3 + d2 + e1 =f1 d3 + e2 =f2 e3 =f3 (1) (2) (3) (4) (figure 4)
这里是用的与CRC-16同样的方法来实现的,我会给出一个具体值的例子.查找用附录中
CRC-32的值表.
Take for CRC register before, a3 a2 a1 a0 -> AB CD EF 66
Take for CRC register after, f3 f2 f1 f0 -> 56 33 14 78 (wanted value) 我们开始:
First byte of entries entry value
e3=f3 =56 -> 35h=(4) 56B3C423 for e3 e2 e1 e0 d3=f2+e2 =33+B3 =E6 -> 4Fh=(3) E6635C01 for d3 d2 d1 d0 c3=f1+e1+d2 =14+C4+63 =B3 -> F8h=(2) B3667A2E for c3 c2 c1 c0 b3=f0+e0+d1+c2=78+23+5C+66=61 -> DEh=(1) 616BFFD3 for b3 b2 b1 b0
Now we have all needed values, then X=(1)+ a0= DE+66=B8 Y=(2)+ b0+a1= F8+D3+EF=C4 Z=(3)+ c0+b1+a2= 4F+2E+FF+CD=53 W=(4)+d0+c1+b2+a3=35+01+7A+6B+AB=8E (final computation)
结论:要将 CRC-32 的记存器的值从 ABCDEF66 改变到 56331478 我们需要这样一个字节
序列: B8 C4 53 8E
CRC-32的破解算法
假如你考虑手动计算这个可以还原CRC记存器的字节序列,那么这将很难变成一个
简洁的算法.
看看下面这个最后计算的附加版本: Position X =(1) + a0 0 Y =(2) + b0 + a1 1 Z =(3) + c0 + b1 + a2 2 W =(4) + d0 + c1 + b2 + a3 3 f0= e0 + d1 + c2 + b3 4 f1= e1 + d2 + c3 5 f2= e2 + d3 6 f3= e3 7 (figure 5)
它就等同于figure 4,只不过是一些值/字节被交换了.这种方法可以帮助我们构造一个
简洁的算法.这里我们用一个8字节的缓冲区,0-3位我们放置a0到a3,4-7位我们放置f0到
f3.象以前一样,我们用这个已知值e3(由figure 5中得知)在表中查出(e3 e2 e1 e0),并且
象图5(figure 5)中所示,将它们放到第4位(position 4),我们马上得到了d3的值.因为f2=
e2+d3,所以f2+e2=d3.又因为(4)已知(入口值),我们照样把它也放到位置3.然后在用d3查表
得到(d3 d2 d1 d0),同上也将他们放到图中所述位置.同样,由于有f1+e1+d2=c3在位置5上.
我们继续做直到将b3 b2 b1 b0放到位置1,对了，就是它! Et voila! 此时,缓冲区的第3-第0字节中已经包含全部元素,用来计算X~W!
算法总结如下:
1.对于这个8字节的缓冲区,0~3字节放入a0...a3(CRC记存器起始值),4~7字节放入f0...f3
(目标记存器的值).
2.取出位置7的已知值,查表得到相应值.
3.将查出值放如图5相应位置,其实就是做XOR运算.(为了直观,可以拟定此图) 4.将入口字节放入图中.也是做XOR运算.
5.继续做2,3两步3次,同时每次降低1个位置 position 5 to 4, 4 to 3 and so on.
算法的实现:
现在是时候给出代码了.下面就是用汇编写成的可执行的CRC-32算法(用其他语言也一样
简单,对于其他的CRC-32标准也一样).注意在汇编中(计算机里)双字在读写操作中顺序都是
反着的.就是逆向顺序. crcBefore dd (?) wantedCrc dd (?) buffer db 8 dup (?)
mov eax, dword ptr[crcBefore] ;/* mov dword ptr[buffer], eax
mov eax, dword ptr[wantedCrc] ; Step 1 mov dword ptr[buffer+4], eax ;*/ mov di, 4 computeReverseLoop:
mov al, byte ptr[buffer+di+3] ;/* call GetTableEntry ; Step 2 */ xor dword ptr[buffer+di], eax ; Step 3 xor byte ptr[buffer+di-1], bl ; Step 4 dec di ;/*
jnz computeReverseLoop ; Step 5 */ Notes:
-Registers eax, di bx are used Implementation of GetTableEntry
crctable dd 256 dup (?) ;should be defined globally somewhere & initialized of course