Post Técnico
Como Calcular o Checksum
Checksums de diversos tipos são amplamente utilizados em protocolos de comunicação de dados para permitir que o destinatário de uma mensagem verifique, de forma rápida e simples, se os dados podem ter sido corrompidos durante a transmissão. Se você somar todos os bytes de uma mensagem e obtiver (desconsiderando o overflow) a soma 96, basta anexar esse número à mensagem antes de enviá-la. O destinatário pode repetir o mesmo cálculo nos primeiros N – 1 bytes da mensagem e comparar o resultado com o byte final para verificar se ele é 96. Em caso afirmativo, o destinatário pode inferir que a mensagem provavelmente não foi alterada durante o trânsito.
Há uma grande variedade de técnicas de checksum em uso atualmente. Três das mais populares são o checksum convencional, o LRC (verificação de redundância longitudinal) e o CRC (verificação de redundância cíclica). Este último não é, a rigor, um checksum no sentido tradicional, mas sim um exemplo de função hash unidirecional pertencente à família dos "geradores congruenciais lineares".
Vale observar que, anteriormente, afirmei que essas técnicas de integridade de dados podem indicar se os dados "provavelmente foram corrompidos". Nenhuma técnica de checksum é 100% infalível no caso geral, para dados de comprimento arbitrário. No entanto, algumas técnicas são claramente superiores a outras.
Vejamos como calcular LRC, checksum e CRC utilizando JavaScript.
Como Calcular o Checksum de Forma Tradicional
O checksum convencional de 8 bits é exatamente o que o nome sugere: a soma dos valores de todos os bytes da entrada, descartando qualquer overflow resultante de operações de carry. Em JavaScript:
A entrada desta função deve ser uma string hexadecimal com o seguinte formato: "48656C6C6F20776F726C6421" (que, neste caso, corresponde à representação hexadecimal da string ASCII "Hello world!"). Utilizando "48656C6C6F20776F726C6421" como entrada para a função acima, o resultado será "5d", que é o valor hexadecimal da soma final de 8 bits.
O código é bastante simples. Começamos (na Linha 3) analisando a entrada hexadecimal em blocos de dois nibbles usando a expressão regular /../g — que significa encontrar substrings que correspondam ao padrão "qualquer coisa seguida de qualquer coisa" (é isso que os dois pontos representam), e fazê-lo de forma global (é isso que o 'g' significa). O resultado é um array, s, de valores hexadecimais de dois dígitos.
Na Linha 5, entramos em um loop (usando o construtor de iteração forEach ) no qual convertemos a versão em string de um valor hexadecimal de dois nibbles em um número real com o qual podemos operar. Na Linha 7, realizamos a soma propriamente dita. Observe que o número sum é, essencialmente, um inteiro de 32 bits nos bastidores, o que significa que nosso valor final pode ser muito maior que 255. Ao terminar o loop, precisamos garantir que a soma seja limitada a um valor de 8 bits. Fazemos isso na Linha 9, com o AND lógico contra 255. Ao mesmo tempo, convertemos de volta para hexadecimal usando o método toString() com um argumento de 16 (indicando que queremos usar o radix 16 ou "base 16" na representação final do número).
Nas Linhas 10 e 11, precisamos verificar se o valor hexadecimal final possui dois nibbles. A operação toString(16) do JavaScript retorna um valor de um único dígito para valores menores que 10. Nesse caso, precisamos acrescentar '0' antes da resposta.
Se quiser testar o código, copie e cole o código acima no console JS (no Chrome, use Shift-Cmd-J para abrir o console) e, em seguida, adicione uma linha ao final (fora da função) com CHECKSUM("48656C6C6F20776F726C6421"). Ao pressionar Enter, o console deverá exibir '5d' como valor de retorno.
Como Calcular Checksum com LRC
A verificação de redundância longitudinal (LRC) é uma variação do checksum de 8 bits, diferindo apenas no fato de que a "soma" é realizada com XOR, em vez de adição numérica.
Na Linha 6, é possível ver o operador XOR de atribuição composta (^=).
Como o XOR nunca gera overflow, não precisamos restringir o resultado final a 8 bits com um AND. Simplesmente verificamos se o comprimento é de dois nibbles e, em seguida, retornamos o valor final.
Se você testar o código no console usando a string mostrada anteriormente, deverá obter o resultado '21'.
Análise Crítica do Checksum e do LRC
Nem o checksum nem o LRC podem ser considerados robustos contra corrupção de mensagens. Por exemplo, considere a mensagem original ("48656C6C6F20776F726C6421"); suponha que alteremos os dois últimos bytes da mensagem de 6421 para 6520. Tanto o LRC quanto o checksum permanecem inalterados! (Simplesmente ativamos um bit em um byte anterior e desativamos o bit na mesma posição em um byte posterior, criando duas alterações que se cancelam mutuamente no momento do cálculo do checksum.)
Da mesma forma, considere o que acontece se você inverter a mensagem (ou seja, reverter a mensagem byte a byte, de modo que ela comece com 21 e termine com 48). Novamente, o LRC e o checksum permanecem iguais aos da mensagem original. Isso ocorre porque o XOR e a adição são comutativos. A + B sempre será igual a B + A.
Além disso, considere o fato de que, como um LRC ou checksum de 8 bits só pode assumir 256 valores distintos, há uma chance de 1 em 256 de que qualquer mensagem produza exatamente o mesmo LRC (ou checksum) que outra mensagem escolhida aleatoriamente.
Em geral, é muito fácil "enganar" os algoritmos de checksum e LRC, portanto, eles não são realmente muito confiáveis para a verificação de integridade de mensagens.
Felizmente, existem algoritmos mais eficientes do que o LRC ou o checksum para verificação de integridade, porém com um custo maior em termos de processamento computacional.
Como Calcular Checksum com CRC
Quando a verificação de integridade é realmente importante, de modo geral é necessário utilizar algum tipo de hash não comutativo. Frequentemente, isso implica o uso de um hash criptográfico, como SHA-1 ou MD5, porém esses são computacionalmente intensivos e podem ser considerados "excessivos" em muitas situações.
Um bom equilíbrio entre custo computacional e confiabilidade pode ser encontrado na Verificação de Redundância Cíclica (CRC), disponível em diversas versões, sendo que o CRC de 16 bits descrito a seguir é adequado (e bastante popular) para mensagens curtas (de até aproximadamente 4 kilobytes).
CRC é um tema interessante, mas o espaço aqui não permite um tratamento abrangente do assunto. (Consulte o Google.) Basta dizer que, do ponto de vista prático, um CRC de dois bytes oferece muito boa sensibilidade a inversões aleatórias de bits nos dados e dificilmente gera falsos positivos em dados com múltiplas inversões de bits. Por isso, e por ser fácil de implementar em hardware ou software, além de executar rapidamente com uso mínimo de memória, ele é amplamente utilizado em diversos ambientes de comunicação de dados, incluindo drivers de discos de armazenamento (onde erros de disco são frequentemente detectados por CRC), modems e dispositivos eletrônicos de pequeno porte (incluindo todos os leitores de cartão de crédito da série ViVOpay da ID TECH).
O código JavaScript a seguir demonstra como calcular um valor CRC de 16 bits (retornado como quatro nibbles em hex-ASCII).
O CRC implementa um algoritmo de hash que pode ser descrito em linguagem natural da seguinte forma:
- Defina o valor inicial de crc como 0xFFFF — Linha 10
- Leia um byte dos dados de entrada (como um número de 8 bits) — Linha 13
- Desloque o valor atual de crc 8 bits à direita — Linha 14
- Aplique XOR entre o crc deslocado à direita e o byte de entrada — Linha 14
- Use o valor resultante j (apenas os 8 bits inferiores) como deslocamento de tabela para localizar um "byte de substituição" na tabela conhecida como crcTable — Linha 15
- Desloque o valor crc 8 bits à ESQUERDA e aplique XOR contra o "byte de substituição" — Linha 15
- Repita essas operações, a partir da Linha 13, utilizando o próximo byte de entrada
- Após todo o processamento da entrada, aplique XOR ao resultado com zero e mantenha os 16 bits inferiores do crc — Linha 17
Utilizamos uma pequena rotina utilitária para converter o número final de inteiro para uma string hexadecimal:
Se você carregar ambas as funções (numToHex e CRC) no console JS do seu navegador e executar CRC( "48656C6C6F20776F726C6421" ), você deverá obter um CRC para os dados de entrada "Hello world!" igual a 'BD22'.
Como exercício, você pode tentar inverter um bit na entrada para observar o efeito na saída. Por exemplo, ao utilizar a string "Hello world!" como entrada e alterar o byte final dos dados de 21 para 20, o CRC muda para 'AD03', sem qualquer relação com 'BD22'. Alterando os dois bytes finais para '6520', obtém-se um CRC de '9E32'. (Lembre-se: essa mesma alteração não perturbou o LRC nem o checksum.)
Considere uma string que representa dez bytes de valor zero (nulo). O valor LRC de tal string seria zero. O checksum seria obviamente zero. Mas o CRC seria E139.
É fácil perceber que inverter a ordem dos dados de entrada produziria um CRC completamente diferente do obtido com a ordem original. (O que não ocorre com LRC ou checksum.) O CRC não é comutativo, devido à forma como os 8 bits superiores do CRC são submetidos a XOR com o byte de entrada antes de todo o conjunto ser deslocado para a esquerda (de maneira semelhante ao funcionamento do encadeamento de blocos de cifra , exceto que, neste caso, o tamanho do "bloco de cifra" é de 8 bits).
Observe que, embora o CRC seja um hash unidirecional, ele não é um hash criptográfico propriamente dito, pois é relativamente simples calcular um "valor de correção" que, se anexado aos dados, faria com que uma determinada alteração nos dados resultasse no CRC final desejado. (Isso não se aplica aos chamados hashes criptográficos, nos quais é computacionalmente difícil calcular um "fator de correção" capaz de reverter um bloco de dados alterado ao hash desejado.) O CRC é, portanto, adequado para detectar corrupção de dados não intencional.
Conclusão
Não faltam algoritmos de "verificação de integridade" que podem ser utilizados para monitorar pacotes de dados em busca de corrupção. Em alguns casos, um simples checksum ou LRC é suficiente. Porém, em situações que envolvem volumes consideráveis de dados e um requisito rigoroso de integridade, é quase indispensável recorrer a um hash do tipo "gerador congruencial linear" . A família de algoritmos CRC foi cuidadosamente ajustada e otimizada para oferecer boa capacidade de detecção de erros aliada à facilidade de implementação, execução rápida e baixos requisitos de memória, tornando o CRC atraente para uma ampla variedade de cenários de verificação de dados — desde discos rígidos até leitores de cartão de crédito.