Post Técnico
Como Calcular o Checksum
Somas de verificação de diversos tipos são amplamente utilizadas em protocolos de comunicação de dados para permitir que o destinatário de uma mensagem determine, 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 verificar (desconsiderando o estouro) que o resultado é 96, e então acrescentar esse número à mensagem antes de enviá-la, o destinatário poderá repetir o mesmo cálculo nos primeiros N – 1 bytes da mensagem e comparar o resultado com o último byte para ver se é igual a 96. Se for, o destinatário pode inferir que a mensagem provavelmente não foi alterada durante a transmissão.
Existe uma grande variedade de técnicas de soma de verificação em uso comum. Três das mais populares são a soma de verificação convencional, o LRC (verificação de redundância longitudinal) e o CRC (verificação de redundância cíclica). Este último não é exatamente uma soma de verificação no sentido tradicional, mas sim um exemplo de função de hash unidirecional que pertence à família dos "geradores lineares congruentes".
Observe que, anteriormente, mencionei que essas técnicas de integridade de dados podem indicar se os dados "provavelmente foram corrompidos". Nenhuma técnica de soma de verificação é 100% infalível no caso geral, para dados de comprimento arbitrário. No entanto, algumas técnicas são definitivamente mais eficazes do que outras.
Vejamos como calcular LRC, soma de verificação e CRC utilizando JavaScript.
Como Calcular a Soma de Verificação de Forma Tradicional
A soma de verificação convencional de 8 bits é exatamente o que o nome sugere: a soma dos valores de todos os bytes da entrada, descartando qualquer estouro resultante de operações de carry. Em JavaScript:
A entrada desta função deve ser uma string hexadecimal com o formato "48656C6C6F20776F726C6421" (que, neste caso, é a 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) interpretando a entrada hexadecimal em blocos de dois nibbles por meio da expressão regular /../g — que significa: encontrar substrings que correspondam ao padrão "qualquer caractere seguido de qualquer caractere" (é 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 o valor final pode ser muito maior que 255. Ao concluir o loop, precisamos garantir que a soma seja restringida 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 a base 16 na representação final do número).
Nas Linhas 10 e 11, precisamos verificar se o valor hexadecimal final tem dois nibbles de comprimento. 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 experimentar 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 no final (fora da função) com CHECKSUM("48656C6C6F20776F726C6421"). Ao pressionar Enter, o console deverá exibir '5d' como valor de retorno.
Como Calcular o 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 por meio de XOR, em vez de adição numérica.
Na Linha 6, é possível observar o operador XOR no lugar (^=).
Como o XOR nunca gera estouro, não é necessário restringir o resultado final a 8 bits por meio de um AND. Basta verificar se o comprimento é de dois nibbles e, em seguida, retornar o valor final.
Se você testar o código no console utilizando a string exibida anteriormente, deverá obter o resultado '21'.
Crítica ao Checksum e ao 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, se você reverter a mensagem byte a byte, de modo que ela passe a começar com 21 e terminar com 48). Novamente, o LRC e o checksum permanecem os mesmos que os 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 pode assumir apenas 256 valores diferentes, 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" algoritmos de checksum e LRC, portanto eles não são realmente muito confiáveis para verificação de integridade de mensagens.
Felizmente, existem algoritmos melhores do que o LRC ou o checksum para verificação de integridade, porém eles têm um custo em termos de sobrecarga computacional.
Como Calcular o Checksum com CRC
Quando a verificação de integridade é realmente importante, em 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, mas esses são computacionalmente intensivos e podem ser considerados "excessivos" em muitas situações.
Um bom equilíbrio entre sobrecarga computacional e confiabilidade pode ser encontrado no Cyclic Redundancy Check, disponível em diversas versões, embora o CRC de 16 bits descrito a seguir seja adequado (e bastante popular) para mensagens curtas (de até aproximadamente 4 kilobytes).
CRC é um tema interessante, mas o espaço não permite um tratamento abrangente aqui. (Consulte o Google.) Basta dizer que, do ponto de vista prático, um CRC de dois bytes oferece uma sensibilidade muito boa 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 pouquíssima memória, você o encontrará em diversos ambientes de comunicação de dados, incluindo drivers de disco de armazenamento (onde erros de disco são frequentemente detectados via CRC), modems e pequenos dispositivos eletrônicos (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 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 buscar um "byte de substituição" na tabela conhecida como crcTable — Linha 15
- Desloque o valor de crc 8 bits à ESQUERDA e aplique XOR com o "byte de substituição" — Linha 15
- Repita essas operações a partir da Linha 13, utilizando o próximo byte da entrada
- Após processar toda a entrada dessa forma, aplique XOR ao resultado com zero e mantenha os 16 bits inferiores do crc — Linha 17
Utilizamos uma pequena rotina auxiliar 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 de 'BD22' para os dados de entrada "Hello world!".
Como exercício, você pode tentar inverter um bit na entrada para observar o efeito na saída. Por exemplo, ao usar a string "Hello world!" como entrada e alterar o último byte dos dados de 21 para 20, o CRC muda para 'AD03', sem nenhuma relação com 'BD22'. Alterando os dois últimos bytes para '6520', obtém-se um CRC de '9E32'. (Lembre-se: essa mesma alteração não afetou o LRC nem o checksum.)
Considere uma string representando dez bytes nulos (zero). O valor LRC de tal string seria zero. O checksum seria obviamente zero. Porém, o CRC seria E139.
É bastante fácil perceber que inverter a entrada produziria um CRC completamente diferente do que usar a entrada na direção original. (O que não era verdade para 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 deslocar tudo para a esquerda (o que é semelhante ao funcionamento do encadeamento de blocos de cifra , exceto que, neste caso, o tamanho do "bloco de cifra" é de 8 bits).
Note que, embora o CRC seja um hash unidirecional, não é um hash criptográfico em sentido estrito, pois é relativamente simples calcular um "valor de correção" que, se anexado aos dados, faria com que uma determinada alteração dos dados produzisse o CRC final desejado. (Isso não se aplica aos chamados hashes criptográficos, nos quais é 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 usados para monitorar pacotes de dados em busca de corrupção. Em alguns casos, um simples checksum ou LRC é suficiente. Mas em situações que envolvem volumes consideráveis de dados e requisitos rigorosos de integridade, é quase inevitável recorrer a um hash do tipo "gerador congruencial linear" . A família de algoritmos CRC foi bem ajustada e otimizada para oferecer boa discriminação de integridade 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 — de discos rígidos a leitores de cartão de crédito.