Às vezes, surge uma tarefa para proteger a cadeia identificadora de erros acidentais cometidos por uma pessoa. Por exemplo, número do cartão de pagamento. Para fazer isso, um dígito de verificação calculado de uma maneira especial é adicionado à linha e, quando uma pessoa digita esse número, você pode fazer uma verificação de erro inicial sem acessar o banco de dados. A opção mais fácil é adicionar o restante da divisão da soma de todos os dígitos por 10; nesse caso, a distorção de qualquer dígito (incluindo o controle) será fácil de detectar e essa linha não passará no teste. Mas alguns outros erros, como uma soma de verificação, perderão, por exemplo, uma permutação de dois dígitos em alguns lugares, e esse também é um erro bastante comum.
Para proteger os números dos cartões bancários, foi escolhido um algoritmo um pouco mais complexo,
o algoritmo
Moon . Foi adicionada uma modificação: os números que estão em lugares pares são multiplicados por 2 antes da soma (e se ocorrer mais de nove, 9 será subtraído). Isso permite capturar, além de distorcer qualquer dígito, a maioria (embora não todas) das permutações de dígitos adjacentes.
Existem algoritmos que podem detectar permutações de dígitos adjacentes (além de distorcer qualquer dígito único)? Sim, eles existem, embora por algum motivo não sejam muito comuns. Esse é
o algoritmo Verhuff baseado em grupos diédricos e
o algoritmo Damm , que é baseado nos quasigrupos Damm. Parece assustador, mas na verdade não há nada complicado (para aqueles que estão familiarizados com o conceito de "grupo").
Jacobus Verhoeff, um matemático e escultor holandês (uma de suas esculturas na fotografia), propôs um algoritmo baseado em
grupos diédricos . Um grupo diédrico é um grupo de simetrias de um N-gon regular, incluindo rotações e simetrias axiais. Esse grupo não é comutativo: se um polígono regular com vértices renumerados for primeiro exibido simetricamente e depois girado, na maioria dos casos, não será o mesmo que se você girasse primeiro e depois exibisse. E, portanto, ao "sequencialmente" multiplicar os dígitos da string original usando a operação do grupo diédro, ou seja, aplicando sucessivamente as operações de rotação e mapeamento simétrico sobre o N-gon regular, obtemos proteção contra a maioria das permutações. Da maioria, mas ainda não de todos novamente. Verkhuff sugeriu melhorar esse algoritmo e antes de multiplicar cada dígito para substituir por outro de acordo com uma tabela especial, dependendo do local do dígito na linha. A tabela é obtida de uma permutação aplicando-a sequencialmente ao resultado anterior e, após 8 aplicações, chegamos à ordem original, para que você possa pré-construir a tabela 8x10 e obter o valor a partir daí. Algumas dessas permutações nos permitem determinar todos os 100% de erros possíveis na ordem dos dígitos adjacentes da cadeia de origem, ou seja, esta é uma solução completa e correta para o problema de encontrar um dígito de verificação que proteja esses dois tipos de erros. Aparentemente, Verkhuff encontrou uma permutação bem-sucedida por seleção aleatória; existem algumas delas.
A questão de saber se existem grupos que permitem encontrar permutações de dígitos adjacentes sem modificações adicionais permanece em aberto por um longo tempo. E já no século XXI, em 2004, o matemático alemão Michael Damm provou a existência de tais grupos, chamados de quazigroups fracamente totalmente anti-simétricos. Eu ainda não descobri como construí-los; aqueles que desejam podem tentar fazer isso
publicando-os . E, embora não pareça tão complicado durante uma rápida olhada (é até estranho que a pergunta permaneça em aberto por tanto tempo), para implementação prática, há uma maneira mais fácil: use
tabelas prontas .
Agora vamos para a próxima e principal pergunta: o que devo fazer se quiser proteger não uma sequência de dígitos decimais, mas uma sequência de caracteres arbitrários, por exemplo, hexadecimal ou base64 ou base58? Ou seja, resolver o problema não no caso particular do sistema de números decimais, mas na forma geral.
O algoritmo Moon se estende a este caso sem problemas, mas não é tão interessante, porque não encontra todas as permutações de dígitos vizinhos. O método de construção de um quase-grupo antissimétrico de tamanho arbitrário não é totalmente claro. Para o algoritmo Verhuff, é fácil construir um grupo diédrico de tamanho N, mas você ainda precisa de uma tabela de permutação, que também não está clara de onde obtê-la (e nem é claro se ela existe). Este é o estudo da última pergunta e eu comecei.
O Google não produziu nada além de tentativas separadas e o uso de soluções "razoavelmente boas" (ou seja, detectar quase todas as permutações) para N = 64.
Talvez eu não descreva todas as maneiras experimentadas e testadas para encontrar a permutação desejada, o que não deu resultado. Tentei resolver um problema específico: encontrar uma permutação para base64 e base58, que oferece proteção contra a alteração da ordem dos dígitos vizinhos. Só posso dizer que as tentativas de encontrar essa permutação por pesquisa aleatória ou seqüencial com diferentes opções de otimização falharam. Mas no final, encontrei uma solução geral para qualquer número par.
A permutação é a seguinte:
0, N-1 .. N/2+1, 1 .. N/2
Por exemplo, para N = 10, isso seria:
0, 9, 8, 7, 6, 1, 2, 3, 4, 5
Essa permutação tem outra propriedade notável: sempre possui um período (para N> = 8) de 12, o que permite pré-construir uma tabela 12xN e pegar um dígito a partir daí.
Aqui está um exemplo da implementação da extensão proposta do algoritmo Verhuff para a base58 (estritamente falando, esse não é
o algoritmo
de Verkhuff , mas sua generalização). Não é uma lib completa, mas apenas um utilitário, por assim dizer, prova de conceito.
A prova de que essa permutação tem a propriedade necessária e de um período de 12, fornecerei algum tempo depois. Há muito pouco espaço na margem para ajustá-lo aqui.