A verificação cíclica de redundância (do inglês, CRC - Cyclic Redundancy Check) é um método de detecção de erros normalmente usada em redes digitais e dispositivos de armazenamento para detectar mudança acidental em cadeias de dados. Mensagens de dados entrando nesses sistemas recebem um pequeno anexo com um valor de verificação baseado no resto de divisão polinomial do seu conteúdo. No ato da recuperação do dado o cálculo é refeito e comparado com o valor gerado anteriormente. Se os valores não se mostrarem semelhantes podem ser aplicadas ações para correção de dados, evitando assim a corrupção de dados. CRC pode ser usada para correção de erros a partir de alguns métodos.
O nome CRC vem da redundância do valor de verificação atrelado ao dado (A mensagem recebe um aumento em seu tamanho sem adicionar uma informação) e o algoritmo de validação é construído com laços de repetição cíclicos.
A verificação cíclica de redundância é amplamente utilizada em dispositivos binários por ser de simples implementação, é matematicamente fácil de ser analisada e apresenta bons resultados na detecção de erros comuns em canais de transmissão causados por ruído. A função utilizada para gerar o valor de verificação possui tamanho fixo, e é utilizada igualmente como uma função hash.
O primeiro a propor a CRC foi W. Wesley Peterson em 1961. Hoje, a função CRC de 32 bits do Ethernet e vários outros padrões são trabalhos de vários pesquisadores e foi publicada em 1975.
Introdução Verificação cíclica de redundância é baseada na teoria de códigos de correção de erros cíclicos. O uso de códigos cíclicos sistemáticos, que alteram a mensagem adicionando um valor de verificação de tamanho fixo, com o propósito de detecção de erros em redes de comunicação foi proposta por W. Wesley Peterson em 1961. Códigos cíclicos são simples de implementar e possuem o benefício apresentar ótimas respostas na detecção de erros causados pela “Rajada” de bits: sequencias continuas de símbolos de dados errados (Burst Errors).
Eles são importantes porque Burst Errors são ocorrências comuns em canais de comunicação, incluindo canais óticos ou magnéticos. Geralmente, um n-bit CRC aplicado sobre uma mensagem de tamanho qualquer irá detectar cada um desses erros que forem menores que n bits e uma fração de 1/(1- 2^(-n)) de bits em mensagens maiores.
A determinação de um valor para o código de validação requer a definição de um Gerador Polinomial.
Esse polinômio será o divisor em uma divisão polinomial em que a mensagem de dados será o dividendo e o quociente é descartado, porém o resto será o código de verificação. É importante mencionar que os coeficientes do gerador são calculados de acordo com a aritmética de campo finito, para que a operação de adição possa sempre ocorrer paralelamente bit-a-bit (sem carry entre dígitos).O tamanho do resto será sempre menor que o do gerador polinomial, com isso pode-se determinar o tamanho do código de verificação.
Na prática, a maioria dos códigos utilizam um campo Galois de 2 elementos, GF(2).Os elementos são geralmente chamados de 0 e 1 coincidentemente utilizados na arquitetura binária.
Um CRC é chamado de n-bit CRC quando seu código de verificação possui tamanho de n bits. Para um dado n, múltiplos códigos de verificação são possíveis de serem construídos, cada um com um polinômio diferente. Tal polinômio possui o maior grau de valor n, além de n + 1 termos. Ou seja, ele possui tamanho n + 1 bits.
Várias especificações descartam o MSB ou o LSB, pois eles sempre serão iguais a 1. Essas especificações serão encontradas mais a frente na forma de CRC-n-XXX.
O sistema de detecção de erro mais simples, o bit de paridade, é na verdade um 1-bit CRC, de polinômio x + 1 (dois termos), de nome CRC-1.
Aplicações Um dispositivo que suporta CRC calcula uma pequena sequência binária de tamanho fixo, conhecido como código de verificação ou CRC, para cada mensagem que será enviada ou recebida e a anexa aos dados, formando uma palavra-código (codeword).
Quando uma palavra código é recebida ou lida, o dispositivo compara seu código de verificação anexado com um novo, calculado a partir da mensagem, ou aplica o CRC sobre toda a palavra-código e compara o resultado com uma constante residual pré-definida.
Se os códigos CRC não são semelhantes a mensagem contém erros de dados. O dispositivo pode realizar ações corretivas como reler a mensagem ou requisitar um novo envio da mesma.
Senão os dados podem ser tratados como corretos e sem erro. (Com uma pequena probabilidade o código pode conter erros não detectados; essa é a natureza fundamental da verificação de erros).
Integridade dos dados Os códigos de verificação cíclica de redundância são projetados para proteger contra erros típicos dos canais de comunicação, onde podem garantir a integridade de mensagens de forma rápida e confiável. Entretanto, eles não são aplicáveis para proteção contra alteração intencional de dados.
Não há nenhum tipo de autenticação, um invasor pode editar a mensagem e recalcular seu código de verificação sem que a substituição seja detectada. Quando as funções criptográficas de hash e a CRC são armazenadas em conjunto com os dados, elas não podem proteger contra alterações intencionais dos dados. Aplicações que requerem tal proteção devem usar mecanismos de autenticação criptográficas como códigos de autenticação da mensagem ou assinaturas digitais.
Diferente das funções hash criptográficas , um CRC pode ser revertido facilmente, o que o torna inaplicável para uso com assinaturas digitais.
Finalmente, CRC são criados a partir de funções lineares, com a seguinte propriedade:
Logo, mesmo que o CRC seja criptografado com uma cifra de fluxo (Stream cipher, um algoritmo de chave simétrica) que use a operação lógica OU exclusivo (XOR) como sua operação combinatória, ambas mensagem e CRC associada podem ser manipuladas sem o conhecimento da chave de manipulação. Essa era uma das falhas conhecidas do protocolo WEP.
Cálculo Para calcular um CRC de n bits, coloque os bits representando o dado em uma linha, e abaixo do MSB dessa linha posicione o padrão (n + 1)-bit que representa o divisor CRC, também chamado de "polinômio".
Neste exemplo será utilizado uma mensagem de 14 bits, com um 3-bit CRC, e o polinômio gerador. O polinômio precisa ser escrito em binário, um polinômio de 3ª ordem possui 4 coeficientes (). Nesse caso, os coeficientes são: 1, 0, 1, 1. O resultado do cálculo tem 3 bits de tamanho.
A mensagem a ser codificada será:
11010011101100
Primeiro, são adicionados zeros no fim da palavra correspondentes ao tamanho n do CRC. Então é feito o primeiro cálculo para se obter o 3-bit CRC:
11010011101100 000 <--- entrada deslocada para a direita com 3 zeros 1011 <--- divisor (4 bits) = x³ + x + 1
01100011101100 000 <--- resultado
O algoritmo age sobre os bits diretamente acima do divisor em cada passo. O resultado para a iteração acima é a operação OU-exclusivo bit-a-bit para os bits acima do divisor polinomial. Os bits restantes são diretamente copiados para o resultado daquele passo. O Divisor é então deslocado para a direita em 1 bit e o processo é repetido até que divisor alcance o ultimo bit da mensagem. O cálculo completo pode ser visto a seguir:
11010011101100 000 <--- entrada deslocada para a direita com 3 zeros 1011 <--- divisor 01100011101100 000 <--- resultado (note que os primeiros 4 bits são um XOR com os bits acima do divisor, o resto é copiado). 1011 <--- divisor ... 00111011101100 000 1011 00010111101100 000 1011 00000001101100 000 <--- note que o divisor irá se mover mais de 1 bit para se alinhar com o próximo bit 1 do dividendo (por que o quociente da operação para aquele passo seria 0). 1011 (Ou seja, ele não se move apenas 1 bit necessariamente.) 00000000110100 000 1011 00000000011000 000 1011 00000000001110 000 1011 00000000000101 000 101 1
00000000000000 100 <--- resto (3 bits). O algoritmo de divisão para neste ponto pois o dividendo é zero.
Como o bit divisor mais à esquerda zerou todos os bits que interagiu, ao final desse processo apenas os n bits mais à direita da mensagem não serão zerados. Esses n bits correspondem ao resto da divisão polinomial, e ao valor da função CRC (a menos que a especificação do CRC escolhido exija algum processamento posterior).
A validade de uma mensagem recebida pode ser avaliada de maneira simples, aplicando o calculo acima novamente, porém o valor da função CRC será adicionado no lugar dos zeros à direita. O resto dessa operação deverá ser zero se nenhum erro for detectado.
11010011101100 100 <--- mensagem com o CRC 1011 <--- divisor 01100011101100 100 <--- resultado passo 1 1011 <--- divisor ... 00111011101100 100
......
00000000001110 100 1011 00000000000101 100 101 1
00000000000000 000 <--- resto
Matemática A análise matemática desse processo de “divisão” demonstra como selecionar um divisor que garantirá boas propriedades de detecção de erro. Nessa análise, os dígitos da linha de bits são utilizados como coeficientes de um polinômio em uma variável qualquer x (coeficientes que são na verdade elementos do campo finito de GF(2), ao invés de números quaisquer propriamente). Esse conjunto binário polinomial é um anel matemático.
Determinando polinômios Selecionar o polinômio gerador é a parte mais importante de um algoritmo de verificação cíclica de redundância(CRC). O polinômio deve ser escolhido a fim de maximizar a capacidade de detecção de erros e minimizar a probabilidade de resultados semelhantes se utilizado outros polinômios.
O atributo mais importante do polinômio é seu tamanho (o maior grau de qualquer termo da expressão (maior expoente) + 1), pois isso impactará diretamente sobre o tamanho do valor de verificação.
Os tamanhos mais utilizados de polinômios são: 9 bits (CRC-8) 17 bits (CRC-16) 33 bits (CRC-32) 65 bits (CRC-64) A determinação do polinômio de CRC depende do tamanho total da mensagem de dados a ser protegida (dados + bits de verificação CRC), das propriedades de proteção contra erros desejadas e da quantidade/tipo de recursos disponíveis para a implementação do CRC, além, é claro, da performance desejada. Um erro comum é assumir que os “melhores” polinômios para CRC são encontrados a partir de polinômios irredutíveis ou polinômios irredutíveis multiplicados pelo fator 1+x, que adiciona ao algoritmo a capacidade de detectar todos os erros que afetam um número ímpar de bits (1, 3, 5, ...).
Na realidade, todos os fatores descritos acima devem ser considerados para a escolha do polinômio e podem levar a um polinômio redutível. Entretanto, a escolha de um polinômio redutível irá causar um aumento na quantidade de erros que não serão detectados pelo CRC, pois o quociente do anel matemático terá divisores nulos.
A vantagem na escolha de um polinômio primitivo como gerador para um código CRC será encontrada no resultado que terá um tamanho total de mensagem tal que todos os erros de 1-bit contidos na mensagem terão restos da divisão distintos (chamados de síndromes) e por isso, o resto será uma função linear, e o algoritmo será capaz de detectar qualquer erro de 2 bits contidos na mensagem. Se é o grau do polinômio primitivo gerador, então o tamanho máximo da mensagem de dados será , e o código de verificação anexado será capaz de detectar qualquer erro de um bit ou de um par de bits.
Isso pode ser otimizado, se for utilizado um polinômio gerador , onde é um polinômio primitivo de grau , então o tamanho máximo da mensagem será , e o código se tornará capaz de detectar erros de bit único, duplo, triplo e qualquer conjunto de tamanho ímpar de bits.