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

102

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.

aquanar
fonte
9
Seu código para gerar a tabela CRC32 parece estar correto. Seu polinômio CRC32 lsbit-first ( reverso ) de 0xEDB88320também pode ser escrito msbit-first ( normal ) como 0x04C11DB7. Os valores da tabela que você encontrou em outro lugar foram gerados usando o mesmo polinômio CRC?
jschmier
1
@jschmier oi, sinto que estou um passo atrás desse cara que faz as perguntas? stackoverflow.com/questions/62168128/…
bluejayke
Se alguém mais estiver curioso para ler "Um guia indolor para algoritmos de detecção de erro CRC" com o link acima, o URL original está hospedado, mas o Google encontrou facilmente várias cópias, incluindo esta: zlib.net/crc_v3.txt
Stéphane

Respostas:

114

O polinômio para CRC32 é:

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

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 32 ) 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.

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

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.

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.)

ilkkachu
fonte
13
1 para a "Avaliação do cara médio" no final - talvez considere mover isso para o topo - uma espécie de TL; DR: P
aaronsnoswell
4
@abstractnature Lembre-se de que estamos dividindo polinômios, não apenas números binários. Não podemos fazer a subtração "normal" porque não podemos "emprestar" $ x ^ n $ de $ x ^ {n + 1} $; eles são diferentes tipos de coisas. Além disso, como os bits são apenas 0 ou 1, o que -1 seria? Na verdade, estamos trabalhando no anel de polinômios com coeficientes no campo $ Z / 2Z $, que possui apenas dois elementos, 0 e 1, e onde $ 1 + 1 = 0 $. Ao colocar os cofficientes em um campo, os polinômios formam o que é chamado de Domínio Euclidiano, que basicamente permite que o que estamos tentando fazer seja bem definido em primeiro lugar.
calavicci de
6
Apenas para esclarecer, o polinômio real é 100000100110000010001110110110111 = 0x104C11DB7. O MSB está implícito, mas ainda deve ser levado em consideração em uma implementação. Uma vez que ele sempre será definido porque o polinômio precisa ter 33 bits de comprimento (então o restante pode ter 32 bits), algumas pessoas omitem o MSB.
Felipe T.
2
x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 ... If we assume x is base 2 then we get: x^7 + x^3 + x^2 + x^1 + x^0. Não é assim que a matemática funciona. Os coeficientes para o polinômio são mod (2) ou GF (2), os x são deixados sozinhos, resultando em x ^ 6 + x ^ 5 + x ^ 4 + x ^ 3 + x ^ 2 + x ^ 1 + x ^ 0 (desde 3 mod (2) = 1). Tack the remainder on the end of your message- tecnicamente, o restante é subtraído dos bits 0 que foram acrescentados à mensagem, mas como este é o mod (2) math, tanto a adição quanto a subtração são iguais a XOR, e os bits zero XOR'ed com o restante são os mesmos como o restante.
rcgldr
2
@MarcusJ - Why did you append four 0s though?- os algoritmos de software para calcular o crc acrescentam efetivamente os 0s, mesmo que não seja aparente. Se estiver mostrando o cálculo CRC usando divisão de mão longa, então 0s precisam ser anexados para que o exemplo de divisão apareça corretamente.
rcgldr
11

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.

Pavlo Bobrek
fonte
2
Esta é a melhor resposta aqui até agora, embora eu substitua 'inverter os bits de cada um dos 4 bytes' por 'inverter os bits dos 4 bytes, tratando-os como uma entidade' por exemplo, 'abcdefgh ijklmnop qrstuvwx yzABCDEF' por 'FEDCBAzy xwvutsrq ponmlkji hgfedcba '. Veja também: Tutorial de hash CRC-32 - Comunidade AutoHotkey .
vafylec
1
oi, qual "mensagem" exatamente; y você inverte? stackoverflow.com/questions/62168128/…
bluejayke
10

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.

WhirlWind
fonte
1
Para CRC32 ou CRC32b, obtemos o significado de colisão hash para duas strings diferentes, obtemos o mesmo CRC
indianwebdevil
1
oi, estou um pouco confuso o que você quer dizer com "divifde os polinômios nos dados"? stackoverflow.com/questions/62168128/… o que é X no polinômio representado por? Devo usar os outros bytes do bloco?
bluejayke
7

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

jschmier
fonte
oi, você pode elaborar um pouco?
bluejayke
7

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
vafylec
fonte
1
Se você quiser mais velocidade, existe um método desenvolvido por alguns engenheiros da Intel em 2006, usando normalmente 4 ou 8 bytes da largura do barramento de dados da máquina simultaneamente. Artigo acadêmico: static.aminer.org/pdf/PDF/000/432/446/… Projeto no Sourceforge: sourceforge.net/projects/slicing-by-8 Página geral crc: create.stephan-brumme.com/crc32
Alan Corey
1
Olá, obrigado, parece ótimo, mas como exatamente você obtém o valor polinomial? o que X representa exatamente? E quando diz x ^ 32, esse x é a potência de 32 ou o operador bit a bit ^? stackoverflow.com/questions/62168128/…
bluejayke
1

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]

Gabriel Furstenheim
fonte
1
estou tendo um pouco (trocadilho intencional) de dificuldade em entender isso? stackoverflow.com/questions/62168128/…
bluejayke
1
hey @bluejayke, verifique esta biblioteca github.com/furstenheim/sparse_crc32/blob/master/main.go ela implementa o crc32 para arquivos esparsos, você pode ver lá os detalhes essenciais sobre a computação. Não é otimizado, por isso é mais fácil de seguir do que as implementações normais. Pode ser que você não entenda a parte GF (2) [x]. Basicamente, x ^ 3 + x significa 1010, x ^ 4 + x + 1 significa 10011. Então você precisa realizar a divisão, por exemplo x ^ 3 + x é x * (x ^ 2 + 1). então, o lembrete de x ^ 3 + x sobre x é 0, mas sobre x ^ 2 seria x ^ 2 * x + x, ou seja, o lembrete seria x.
Gabriel Furstenheim
1
@bluejayke e reminderIEEE significam lembrete contra um polinômio bem conhecido, o polinômio IEEE
Gabriel Furstenheim
oi de novo, obrigado pela sua resposta. Só estou tentando entender (para propósitos de javascript) o que o "x" representa no polinômio. "X" é algum tipo de palavra-código para algo que estou perdendo aqui? Há muitos termos que me confundem aqui, nunca tinha ouvido falar do CRC32 antes e, mesmo depois de pesquisar, não consegui encontrar uma explicação real. Para um PNG, por exemplo, ele diz que preciso pegar o "CRC para cada bloco". Isso significa "para todos os dados no bloco"? Mas como faço para "conectá-lo" ao polinômio? O que "x" representa? Além disso, quando diz x ^ 32, é como Math.pow (x, 32) ou o bit a bit ^
bluejayke
1
Olá @bluejayke, x é uma abstração para facilitar os cálculos. Não se espera que seja substituído por nada. x ^ 2 quero dizer x * x, como uma multiplicação formal. Aqui, em chrisballance.com/wp-content/uploads/2015/10/CRC-Primer.html, você pode encontrar uma boa explicação dessa divisão. O que tentei com minha resposta foi preencher a lacuna entre a divisão (naquele link) e o cálculo real
Gabriel Furstenheim