Como uma soma de verificação CRC32 é calculada?

Talvez eu simplesmente não esteja vendo, mas CRC32 parece desnecessariamente complicado ou insuficientemente explicado em qualquer lugar que pude encontrar na web.

Eu entendo que é o resto de uma divisão aritmética não baseada em carry do valor da mensagem, dividido pelo polinômio (gerador), mas a implementação real dele me escapa.

Eu li um guia indolor para algoritmos de detecção de erro CRC e devo dizer que não foi indolor. Ele repassa a teoria muito bem, mas o autor nunca chega a um simples "é isso". Ele diz quais são os parâmetros do algoritmo CRC32 padrão, mas se esquece de definir claramente como chegar a ele.

A parte que me pega é quando ele diz "é isso" e, em seguida, acrescenta: "ah, a propósito, pode ser revertido ou iniciado com diferentes condições iniciais" e não dá uma resposta clara de qual é o caminho final de calcular uma soma de verificação CRC32 dadas todas as mudanças que ele acabou de adicionar.

• Existe uma explicação mais simples de como o CRC32 é calculado?

Tentei codificar em C como a tabela é formada:

for (i = 0; i < 256; i++)
{
    temp = i;

    for (j = 0; j < 8; j++)
    {
        if (temp & 1)
        {
            temp >>= 1;
            temp ^= 0xEDB88320;
        }
        else {temp >>= 1;}
    }
    testcrc[i] = temp;
}

mas isso parece gerar valores inconsistentes com valores que encontrei em outro lugar na Internet. Eu poderia usar os valores que encontrei online, mas quero entender como eles foram criados.

Qualquer ajuda para esclarecer esses números incrivelmente confusos seria muito apreciada.

O polinômio para CRC32 é:

x ³² + x ²⁶ + x ²³ + x ²² + x ¹⁶ + x ¹² + x ¹¹ + x ¹⁰ + x ⁸ + x ⁷ + x ⁵ + x ⁴ + x ² + x + 1

• Wikipedia
• Cálculo CRC

Ou em hexadecimal e binário:

0x 01 04 C1 1D B7
1 0000 0100 1100 0001 0001 1101 1011 0111

O termo mais alto (x ³² ) geralmente não é escrito explicitamente, então pode ser representado em hexadecimal

0x 04 C1 1D B7

Sinta-se à vontade para contar os 1s e 0s, mas você descobrirá que eles correspondem ao polinômio, onde 1é o bit 0 (ou o primeiro bit) e xé o bit 1 (ou o segundo bit).

Por que esse polinômio? Porque é necessário que haja um determinado polinômio padrão e o padrão foi definido pelo IEEE 802.3. Além disso, é extremamente difícil encontrar um polinômio que detecte erros de bits diferentes com eficácia.

Você pode pensar no CRC-32 como uma série de "Aritmética Binária sem Cargas" ou basicamente "XOR e operações de deslocamento". Isso é tecnicamente chamado de aritmética polinomial.

• Primer CRC, Capítulo 5

Para entender melhor, pense nesta multiplicação:

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
 + x^5 + x^3 + x^2
 + x^3 + x^1 + x^0)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

Se assumirmos que x é a base 2, obteremos:

x^7 + x^3 + x^2 + x^1 + x^0

• CRC primer Chp.5

Por quê? Como 3x ^ 3 é 11x ^ 11 (mas precisamos apenas de 1 ou 0 pré-dígito), transferimos:

=1x^110 + 1x^101 + 1x^100          + 11x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^100 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^101          + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^110                   + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^111                            + 1x^11 + 1x^10 + 1x^1 + x^0

Mas os matemáticos mudaram as regras para que seja o mod 2. Então, basicamente, qualquer mod 2 polinomial binário é apenas uma adição sem carry ou XORs. Portanto, nossa equação original se parece com:

=( 1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0 ) MOD 2
=( 1x^110 + 1x^101 + 1x^100 +  1x^11 + 1x^10 + 1x^1 + x^0 )
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 (or that original number we had)

Sei que isso é um ato de fé, mas está além da minha capacidade como programador de linha. Se você é um estudante de ciência da computação ou engenheiro, eu o desafio a decifrar isso. Todos se beneficiarão com esta análise.

Então, para trabalhar um exemplo completo:

   Original message                : 1101011011
   Polynomial of (W)idth 4         :      10011
   Message after appending W zeros : 11010110110000

Agora dividimos a Mensagem aumentada pelo Poli usando aritmética CRC. Esta é a mesma divisão de antes:

            1100001010 = Quotient (nobody cares about the quotient)
       _______________
10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
=Poly   10011,,.,,....
        -----,,.,,....
         10011,.,,....
         10011,.,,....
         -----,.,,....
          00001.,,....
          00000.,,....
          -----.,,....
           00010,,....
           00000,,....
           -----,,....
            00101,....
            00000,....
            -----,....
             01011....
             00000....
             -----....
              10110...
              10011...
              -----...
               01010..
               00000..
               -----..
                10100.
                10011.
                -----.
                 01110
                 00000
                 -----
                  1110 = Remainder = THE CHECKSUM!!!!

A divisão produz um quociente, que descartamos, e um resto, que é o checksum calculado. Isso encerra o cálculo. Normalmente, a soma de verificação é então anexada à mensagem e o resultado transmitido. Nesse caso, a transmissão seria: 11010110111110.

• Primer CRC, Capítulo 7

Use apenas um número de 32 bits como seu divisor e use todo o seu fluxo como seu dividendo. Jogue fora o quociente e guarde o restante. Pegue o restante no final de sua mensagem e você terá um CRC32.

Avaliação de cara comum:

         QUOTIENT
        ----------
DIVISOR ) DIVIDEND
                 = REMAINDER

1. Pegue os primeiros 32 bits.
2. Bits de deslocamento
3. Se 32 bits forem inferiores a DIVISOR, vá para a etapa 2.
4. XOR 32 bits da DIVISOR. Vá para a etapa 2.

(Observe que o fluxo deve ser divisível por 32 bits ou deve ser preenchido. Por exemplo, um fluxo ANSI de 8 bits teria que ser preenchido. Também no final do fluxo, a divisão é interrompida.)

Para IEEE802.3, CRC-32. Pense na mensagem inteira como um fluxo de bits serial, acrescente 32 zeros ao final da mensagem. A seguir, você DEVE inverter os bits de CADA byte da mensagem e fazer um complemento de 1 para os primeiros 32 bits. Agora divida pelo polinômio CRC-32, 0x104C11DB7. Finalmente, você deve complementar os 1's do restante de 32 bits dessa divisão, invertendo cada um dos 4 bytes do restante. Isso se torna o CRC de 32 bits que é anexado ao final da mensagem.

A razão para esse procedimento estranho é que as primeiras implementações Ethernet serializariam a mensagem um byte por vez e transmitiriam o bit menos significativo de cada byte primeiro. O fluxo de bits serial então passou por um cálculo de registro de deslocamento CRC-32 serial, que foi simplesmente complementado e enviado na rede após a mensagem ser concluída. O motivo para complementar os primeiros 32 bits da mensagem é para que você não obtenha um CRC totalmente zero, mesmo que a mensagem seja totalmente zeros.

Um CRC é muito simples; você pega um polinômio representado como bits e os dados e divide o polinômio nos dados (ou você representa os dados como um polinômio e faz a mesma coisa). O resto, que está entre 0 e o polinômio, é o CRC. Seu código é um pouco difícil de entender, em parte porque está incompleto: temp e testcrc não são declarados, então não está claro o que está sendo indexado e quantos dados estão sendo executados pelo algoritmo.

A maneira de entender os CRCs é tentar computar alguns usando um pequeno pedaço de dados (16 bits ou mais) com um polinômio curto - 4 bits, talvez. Se praticar dessa forma, você realmente entenderá como proceder para codificá-lo.

Se você estiver fazendo isso com frequência, um CRC é muito lento para computar no software. A computação de hardware é muito mais eficiente e requer apenas algumas portas.

Além da verificação de redundância cíclica da Wikipedia e dos artigos Computação de CRC , achei um artigo intitulado Reversing CRC - Theory and Practice ^* uma boa referência.

Existem essencialmente três abordagens para calcular um CRC: uma abordagem algébrica, uma abordagem orientada a bits e uma abordagem baseada em tabelas. Em Reversing CRC - Theory and Practice ^* , cada um desses três algoritmos / abordagens é explicado em teoria, acompanhado no APÊNDICE por uma implementação para o CRC32 na linguagem de programação C.

^{* PDF Link
Reversing CRC - Teoria e Prática.
HU Berlin Public Report
SAR-PR-2006-05
May 2006
Autores:
Martin Stigge, Henryk Plötz, Wolf Müller, Jens-Peter Redlich}

Passei um tempo tentando descobrir a resposta a esta pergunta e finalmente publiquei um tutorial sobre CRC-32 hoje: Tutorial de hash CRC-32 - Comunidade AutoHotkey

Neste exemplo, demonstro como calcular o hash CRC-32 para a string ASCII 'abc':

calculate the CRC-32 hash for the ASCII string 'abc':

inputs:
dividend: binary for 'abc': 0b011000010110001001100011 = 0x616263
polynomial: 0b100000100110000010001110110110111 = 0x104C11DB7

011000010110001001100011
reverse bits in each byte:
100001100100011011000110
append 32 0 bits:
10000110010001101100011000000000000000000000000000000000
XOR the first 4 bytes with 0xFFFFFFFF:
01111001101110010011100111111111000000000000000000000000

'CRC division':
01111001101110010011100111111111000000000000000000000000
 100000100110000010001110110110111
 ---------------------------------
  111000100010010111111010010010110
  100000100110000010001110110110111
  ---------------------------------
   110000001000101011101001001000010
   100000100110000010001110110110111
   ---------------------------------
    100001011101010011001111111101010
    100000100110000010001110110110111
    ---------------------------------
         111101101000100000100101110100000
         100000100110000010001110110110111
         ---------------------------------
          111010011101000101010110000101110
          100000100110000010001110110110111
          ---------------------------------
           110101110110001110110001100110010
           100000100110000010001110110110111
           ---------------------------------
            101010100000011001111110100001010
            100000100110000010001110110110111
            ---------------------------------
              101000011001101111000001011110100
              100000100110000010001110110110111
              ---------------------------------
                100011111110110100111110100001100
                100000100110000010001110110110111
                ---------------------------------
                    110110001101101100000101110110000
                    100000100110000010001110110110111
                    ---------------------------------
                     101101010111011100010110000001110
                     100000100110000010001110110110111
                     ---------------------------------
                       110111000101111001100011011100100
                       100000100110000010001110110110111
                       ---------------------------------
                        10111100011111011101101101010011

remainder: 0b10111100011111011101101101010011 = 0xBC7DDB53
XOR the remainder with 0xFFFFFFFF:
0b01000011100000100010010010101100 = 0x438224AC
reverse bits:
0b00110101001001000100000111000010 = 0x352441C2

thus the CRC-32 hash for the ASCII string 'abc' is 0x352441C2

Depois, há sempre o Rosetta Code, que mostra o crc32 implementado em dezenas de linguagens de computador. https://rosettacode.org/wiki/CRC-32 e possui links para muitas explicações e implementações.

Para reduzir o crc32 ao lembrete, você precisa:

1. Inverta bits em cada byte
2. xou os primeiros quatro bytes com 0xFF (isso é para evitar erros nos 0s iniciais)
3. Adicione preenchimento no final (isso é para fazer com que os últimos 4 bytes participem do hash)
4. Calcular o lembrete
5. Inverta os bits novamente
6. xou o resultado novamente.

No código é:

func CRC32 (file []byte) uint32 {
    for i , v := range(file) {
        file[i] = bits.Reverse8(v)
    }
    for i := 0; i < 4; i++ {
        file[i] ^= 0xFF
    }

    // Add padding
    file = append(file, []byte{0, 0, 0, 0}...)
    newReminder := bits.Reverse32(reminderIEEE(file))

    return newReminder ^ 0xFFFFFFFF
}

onde reminderIEEE é o lembrete puro em GF (2) [x]