El algoritmo Luhn mod N es una extensión del algoritmo Luhn (también conocido como algoritmo mod 10) que le permite trabajar con secuencias de valores en cualquier base . Esto puede resultar útil cuando se requiere un dígito de control para validar una cadena de identificación compuesta de letras, una combinación de letras y dígitos o cualquier conjunto arbitrario de N caracteres.
Explicación informal
El algoritmo Luhn mod N genera un dígito de control (más precisamente, un carácter de control) dentro del mismo rango de caracteres válidos que la cadena de entrada. Por ejemplo, si el algoritmo se aplica a una cadena de letras minúsculas (de la a a la z ), el carácter de verificación también será una letra minúscula. Aparte de esta distinción, se parece mucho al algoritmo original.
La idea principal detrás de la extensión es que el conjunto completo de caracteres de entrada válidos se asigna a una lista de puntos de código (es decir, enteros secuenciales que comienzan con cero). El algoritmo procesa la cadena de entrada convirtiendo cada carácter en su punto de código asociado y luego realizando los cálculos en mod N (donde N es el número de caracteres de entrada válidos). Finalmente, el punto de código de verificación resultante se vuelve a asignar para obtener su carácter de verificación correspondiente.
Asignación de caracteres a puntos de código
Inicialmente, se debe crear un mapeo entre caracteres de entrada válidos y puntos de código. Por ejemplo, consideran que los caracteres válidos son las letras minúsculas de una a f . Por tanto, un mapeo adecuado sería:
Personaje | a | B | C | D | mi | F |
---|---|---|---|---|---|---|
Punto de código | 0 | 1 | 2 | 3 | 4 | 5 |
Tenga en cuenta que el orden de los personajes es completamente irrelevante. Este otro mapeo también sería aceptable (aunque posiblemente más engorroso de implementar):
Personaje | C | mi | a | F | B | D |
---|---|---|---|---|---|---|
Punto de código | 0 | 1 | 2 | 3 | 4 | 5 |
También es posible mezclar letras y dígitos (y posiblemente incluso otros caracteres). Por ejemplo, este mapeo sería apropiado para dígitos hexadecimales en minúsculas:
Personaje | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | B | C | D | mi | F |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Punto de código | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
Algoritmo en C #
Suponiendo que se definan las siguientes funciones:
int CodePointFromCharacter ( carácter char ) {...} char CharacterFromCodePoint ( int codePoint ) {...}int NumberOfValidInputCharacters () {...}
La función para generar un carácter de control es:
char GenerateCheckCharacter ( entrada de cadena ) { factor int = 2 ; int suma = 0 ; int n = NumberOfValidInputCharacters (); // Comenzar desde la derecha y trabajar hacia la izquierda es más fácil ya que // el "factor" inicial siempre será "2". for ( int i = entrada . Longitud - 1 ; i > = 0 ; i -) { int codePoint = CodePointFromCharacter ( entrada [ i ]); int sumando = factor * codePoint ; // ¿Alternar el "factor" de que cada "codePoint" se multiplica por factor = ( factor == 2 ) ? 1 : 2 ; // Suma los dígitos de la "sumando" como se expresa en base "n" sumando = IntegerValue ( sumando / n ) + ( sumando % n ); suma + = sumando ; } // Calcula el número que se debe sumar a la "suma" // para que sea divisible por "n". resto int = suma % n ; int checkCodePoint = ( n - resto ) % n ; return CharacterFromCodePoint ( checkCodePoint ); }
Y la función para validar una cadena (con el carácter de verificación como último carácter) es:
bool ValidateCheckCharacter ( entrada de cadena ) { factor int = 1 ; int suma = 0 ; int n = NumberOfValidInputCharacters (); // Empezando por la derecha, trabaja hacia la izquierda // Ahora, el "factor" inicial siempre será "1" // ya que el último carácter es el carácter de verificación. for ( int i = entrada . Longitud - 1 ; i > = 0 ; i -) { int codePoint = CodePointFromCharacter ( entrada [ i ]); int sumando = factor * codePoint ; // ¿Alternar el "factor" de que cada "codePoint" se multiplica por factor = ( factor == 2 ) ? 1 : 2 ; // Suma los dígitos de la "sumando" como se expresa en base "n" sumando = IntegerValue ( sumando / n ) + ( sumando % n ); suma + = sumando ; } resto int = suma % n ; retorno ( resto == 0 ); }
Algoritmo en Java
Suponiendo que se definan las siguientes funciones:
int codePointFromCharacter ( carácter char ) {...} char characterFromCodePoint ( int codePoint ) {...}int numberOfValidInputCharacters () {...}
La función para generar un carácter de control es:
char generateCheckCharacter ( Entrada de cadena ) { factor int = 2 ; int suma = 0 ; int n = numberOfValidInputCharacters (); // Comenzar desde la derecha y trabajar hacia la izquierda es más fácil ya que // el "factor" inicial siempre será "2". for ( int i = input . length () - 1 ; i > = 0 ; i - ) { int codePoint = codePointFromCharacter ( input . charAt ( i )); int sumando = factor * codePoint ; // ¿Alternar el "factor" de que cada "codePoint" se multiplica por factor = ( factor == 2 ) ? 1 : 2 ; // Suma los dígitos del "sumando" como se expresa en la base "n" sumando = ( sumando / n ) + ( sumando % n ); suma + = sumando ; } // Calcula el número que se debe sumar a la "suma" // para que sea divisible por "n". resto int = suma % n ; int checkCodePoint = ( n - resto ) % n ; return characterFromCodePoint ( checkCodePoint ); }
Y la función para validar una cadena (con el carácter de verificación como último carácter) es:
boolean validateCheckCharacter ( String input ) { int factor = 1 ; int suma = 0 ; int n = numberOfValidInputCharacters (); // Empezando por la derecha, trabaja hacia la izquierda // Ahora, el "factor" inicial siempre será "1" // ya que el último carácter es el carácter de verificación. for ( int i = input . length () - 1 ; i > = 0 ; i - ) { int codePoint = codePointFromCharacter ( input . charAt ( i )); int sumando = factor * codePoint ; // ¿Alternar el "factor" de que cada "codePoint" se multiplica por factor = ( factor == 2 ) ? 1 : 2 ; // Suma los dígitos del "sumando" como se expresa en la base "n" sumando = ( sumando / n ) + ( sumando % n ); suma + = sumando ; } resto int = suma % n ; retorno ( resto == 0 ); }
Algoritmo en JavaScript
Suponiendo que se definan las siguientes funciones:
const codePoints = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" ; // Puede ser cualquier cadena de caracteres permitidosfunction numberOfValidInputCharacters () { devuelve codePoints . longitud ; }función codePointFromCharacter ( carácter ) { devuelve codePoints . indexOf ( carácter ); }función characterFromCodePoint ( codePoint ) { devuelve codePoints . charAt ( codePoint ); }
La función para generar un carácter de control es:
función generateCheckCharacter ( input ) { let factor = 2 ; sea suma = 0 ; let n = numberOfValidInputCharacters (); // Comenzar desde la derecha y trabajar hacia la izquierda es más fácil ya que // el "factor" inicial siempre será "2". for ( sea i = input . length - 1 ; i > = 0 ; i - ) { let codePoint = codePointFromCharacter ( input . charAt ( i )); let sumando = factor * codePoint ; // ¿Alternar el "factor" de que cada "codePoint" se multiplica por factor = ( factor == 2 ) ? 1 : 2 ; // Suma los dígitos del "sumando" como se expresa en la base "n" sumando = ( Math . Piso ( sumando / n )) + ( sumando % n ); suma + = sumando ; } // Calcula el número que se debe sumar a la "suma" // para que sea divisible por "n". sea resto = suma % n ; let checkCodePoint = ( n - resto ) % n ; return characterFromCodePoint ( checkCodePoint ); }
Y la función para validar una cadena (con el carácter de verificación como último carácter) es:
function validateCheckCharacter ( input ) { let factor = 1 ; sea suma = 0 ; let n = numberOfValidInputCharacters (); // Empezando por la derecha, trabaja hacia la izquierda // Ahora, el "factor" inicial siempre será "1" // ya que el último carácter es el carácter de verificación. for ( sea i = input . length - 1 ; i > = 0 ; i - ) { let codePoint = codePointFromCharacter ( input . charAt ( i )); let sumando = factor * codePoint ; // ¿Alternar el "factor" de que cada "codePoint" se multiplica por factor = ( factor == 2 ) ? 1 : 2 ; // Suma los dígitos del "sumando" como se expresa en la base "n" sumando = ( Math . Piso ( sumando / n )) + ( sumando % n ); suma + = sumando ; } dejar resto = suma % n ; retorno ( resto == 0 ); }
Ejemplo
Generacion
Considere el conjunto anterior de caracteres de entrada válidos y la cadena de entrada de ejemplo abcdef . Para generar el carácter de verificación, comience con el último carácter de la cadena y muévase a la izquierda doblando cada dos puntos de código. Los "dígitos" de los puntos de código tal como están escritos en la base 6 (ya que hay 6 caracteres de entrada válidos) se deben resumir:
Personaje | a | B | C | D | mi | F |
---|---|---|---|---|---|---|
Punto de código | 0 | 1 | 2 | 3 | 4 | 5 |
Doble | 2 | 6 (base 10) 10 (base 6) | 10 (base 10) 14 (base 6) | |||
Reducir | 0 | 2 | 2 | 1 + 0 | 4 | 1 + 4 |
Suma de dígitos | 0 | 2 | 2 | 1 | 4 | 5 |
La suma total de dígitos es 14 (0 + 2 + 2 + 1 + 4 + 5). El número que se debe sumar para obtener el siguiente múltiplo de 6 (en este caso, 18 ) es 4 . Este es el punto de código de verificación resultante. El carácter de verificación asociado es e .
Validación
La cadena resultante abcdefe se puede validar mediante un procedimiento similar:
Personaje | a | B | C | D | mi | F | mi |
---|---|---|---|---|---|---|---|
Punto de código | 0 | 1 | 2 | 3 | 4 | 5 | 4 |
Doble | 2 | 6 (base 10) 10 (base 6) | 10 (base 10) 14 (base 6) | ||||
Reducir | 0 | 2 | 2 | 1 + 0 | 4 | 1 + 4 | 4 |
Suma de dígitos | 0 | 2 | 2 | 1 | 4 | 5 | 4 |
La suma total de dígitos es 18 . Dado que es divisible por 6, el carácter de verificación es válido .
Implementación
El mapeo de caracteres a puntos de código y viceversa se puede implementar de varias formas. El enfoque más simple (similar al algoritmo de Luhn original) es usar aritmética de código ASCII. Por ejemplo, dado un conjunto de entrada de 0 a 9 , el punto de código se puede calcular restando el código ASCII para '0' del código ASCII del carácter deseado. La operación inversa proporcionará el mapeo inverso. Se pueden tratar rangos adicionales de caracteres mediante el uso de declaraciones condicionales.
Los conjuntos no secuenciales se pueden mapear en ambos sentidos utilizando una declaración de caso / conmutador codificada de forma rígida . Un enfoque más flexible es usar algo similar a una matriz asociativa . Para que esto funcione, se requiere un par de matrices para proporcionar el mapeo bidireccional.
Una posibilidad adicional es utilizar una matriz de caracteres donde los índices de la matriz son los puntos de código asociados con cada carácter. El mapeo de carácter a punto de código se puede realizar con una búsqueda lineal o binaria. En este caso, el mapeo inverso es solo una simple búsqueda de matriz.
Debilidad
Esta extensión comparte la misma debilidad que el algoritmo original, es decir, no puede detectar la transposición de la secuencia