A veces surge una tarea para proteger la cadena de identificación de errores accidentales cometidos por una persona. Por ejemplo, número de tarjeta de pago. Para hacer esto, se agrega un dígito de verificación calculado de manera especial a la línea, y cuando una persona ingresa este número, puede hacer una verificación de error inicial sin acceder a la base de datos. La opción más fácil es agregar el resto de dividir la suma de todos los dígitos por 10, en cuyo caso la distorsión de cualquier dígito (incluido el control) será fácil de detectar, y dicha línea no pasará la prueba. Pero algunos otros errores tales como una suma de verificación fallarán, por ejemplo, una permutación de dos dígitos en lugares, y este también es un error bastante común.
Para proteger los números de las tarjetas bancarias, se eligió un algoritmo un poco más complejo,
el algoritmo
Moon . Agrega una modificación: los números en lugares pares se multiplican por 2 antes de sumar (y si obtiene más de nueve, reste 9). Esto le permite capturar, además de distorsionar cualquier dígito, la mayoría (aunque no todas) las permutaciones de dígitos adyacentes.
¿Existen algoritmos que puedan detectar permutaciones de dígitos adyacentes (además de distorsionar un solo dígito)? Sí, existen, aunque por alguna razón no son muy comunes. Este es
el algoritmo Verhuff basado en grupos diédricos, y
el algoritmo Damm , que se basa en los cuasigrupos Damm. Suena aterrador, pero de hecho no hay nada complicado (para aquellos que están familiarizados con el concepto de "grupo").
Jacobus Verhoeff, un matemático y escultor holandés (una de sus esculturas en la fotografía), propuso un algoritmo basado en
grupos diédricos . Un grupo diédrico es un grupo de simetrías de un N-gon regular, que incluye tanto rotaciones como simetrías axiales. Tal grupo no es conmutativo: si un polígono regular con vértices renumerados se muestra primero simétricamente y luego se gira, en la mayoría de los casos no será lo mismo que si primero girara y luego mostrara. Y por lo tanto, al "multiplicar" secuencialmente los dígitos de la cadena original utilizando la operación del grupo diédrico, es decir Aplicando sucesivamente las operaciones de rotación y mapeo simétrico sobre el N-gon regular, obtenemos protección contra la mayoría de las permutaciones. De la mayoría, pero aún no de todos. Verkhuff sugirió mejorar este algoritmo, y antes de multiplicar cada dígito para reemplazarlo por otro de acuerdo con una tabla especial, dependiendo del lugar del dígito en la línea. La tabla se obtiene de una permutación aplicándola secuencialmente al resultado anterior, y después de 8 de tales aplicaciones llegamos al orden original, por lo que puede precompilar la tabla 8x10 y tomar el valor a partir de ahí. Algunas de estas permutaciones nos permiten determinar el 100% de los posibles errores en el orden de los dígitos adyacentes de la cadena de origen, es decir, esta es una solución completa y correcta al problema de encontrar un dígito de verificación que proteja contra estos dos tipos de errores. Aparentemente, Verkhuff encontró una permutación exitosa por selección aleatoria, hay bastantes.
La cuestión de si existen grupos que permiten encontrar permutaciones de dígitos adyacentes sin modificaciones adicionales ha permanecido abierta durante mucho tiempo. Y ya en el siglo XXI, en 2004, el matemático alemán Michael Damm demostró la existencia de tales grupos, que se denominan quazigroups débilmente totalmente antisimétricos. No he descubierto completamente cómo construirlos; aquellos que lo deseen pueden intentar hacerlo ellos mismos
publicándolo . Y aunque no parece tan complicado durante una mirada rápida (incluso es extraño que la pregunta haya permanecido abierta durante tanto tiempo), para la implementación práctica hay una manera más fácil: usar
tablas preparadas .
Ahora pasemos a la siguiente y principal pregunta: ¿qué sucede si necesito proteger no una cadena de dígitos decimales, sino una cadena de caracteres arbitrarios, por ejemplo, hexadecimal o base64 o base58? Es decir, para resolver el problema no en el caso particular del sistema de números decimales, sino en forma general.
El algoritmo Moon se extiende a este caso sin problemas, pero no es tan interesante porque no encuentra todas las permutaciones de dígitos vecinos. El método de construcción de un cuasigrupo antisimétrico de tamaño arbitrario no está del todo claro. Para el algoritmo Verhuff, un grupo diédrico de tamaño N es fácil de construir, pero aún necesita una tabla de permutación, que tampoco está claro dónde obtenerla (y ni siquiera está claro si existe). Este es el estudio de la última pregunta, y comencé.
Buscar en Google no produjo más que intentos separados y el uso de soluciones "bastante buenas" (es decir, detectar casi todas las permutaciones) para N = 64.
Quizás no describa todas las formas probadas y comprobadas para encontrar la permutación deseada, que no dio un resultado. Traté de resolver un problema particular: encontrar una permutación para base64 y base58, que brinda protección contra el cambio del orden de los dígitos vecinos. Solo puedo decir que los intentos de encontrar dicha permutación mediante búsqueda aleatoria o secuencial con diferentes opciones de optimización han fallado. Pero al final, encontré una solución general para cualquier par n.
La permutación es la siguiente:
0, N-1 .. N/2+1, 1 .. N/2
Por ejemplo, para N = 10 esto sería:
0, 9, 8, 7, 6, 1, 2, 3, 4, 5
Esta permutación tiene otra propiedad notable: siempre tiene un período (para N> = 8) de 12, que le permite preconstruir una tabla de 12xN y tomar un dígito desde allí.
Aquí hay un ejemplo de la implementación de la extensión propuesta del algoritmo Verhuff para base58 (estrictamente hablando, este no es
el algoritmo
de Verkhuff , sino su generalización). No es una biblioteca completa, sino solo una utilidad, por así decirlo, prueba de concepto.
La prueba de que esta permutación tiene la propiedad necesaria, y que tiene un período de 12, la proporcionaré más adelante. Hay muy poco espacio en el margen para ajustarlo aquí.