Algoritmo de Luhn

El algoritmo de Luhn o fórmula de Luhn, también conocida como "algoritmo de módulo 10", es una fórmula de suma de verificación, utilizada para validar una diversidad de números de identificación; como números de tarjetas de crédito, números IMEI, etc. Su idea se convirtió en la base de uno de los algoritmos más importantes de nuestra era, la función resumen/hash como la conocemos hoy.

Creación[editar]

Este algoritmo fue creado por el científico de IBM llamado Hans Peter Luhn y descrito en la patente U.S. Patent n.º 2,950,048, solicitada el 6 de enero de 1954, y concedida el 23 de agosto de 1960.

Dominio público[editar]

Este algoritmo es de dominio público y es ampliamente usado en la actualidad. Su especificación está contenida en la norma ISO/IEC 7812-1.^[1] Su propósito no es de ser una función hash criptográfica segura contra ataques maliciosos, sino que fue diseñada para protección contra errores accidentales. La gran mayoría de tarjetas de crédito y otros números de identificación usan este algoritmo como un método simple de distinguir números válidos a partir de una entrada de números al azar.

Fortalezas y debilidades[editar]

El algoritmo de Luhn detecta cualquier error de un único dígito, así como casi todas las transposiciones de dígitos adyacentes. No obstante, no puede detectar la transposición de la secuencia de dos dígitos 09 a 90 (o viceversa). En ese sentido, detectará siete de los 10 posibles errores individuales posibles (no detectará 22 ↔ 55, 33 ↔ 66 o 44 ↔ 77).

Además, otros algoritmos más complejos basados en chequeo de dígitos (como el algoritmos de Verhoeff) pueden detectar más errores de transcripción. El algoritmo de Luhn mod N es una extensión que soporta cadenas de texto no numéricas.

Debido a que el algoritmo opera sobre los dígitos, de derecha a izquierda, y los dígitos cero afectan el resultado sólo si causan cambio en una posición, una cadena de números rellenada de ceros al principio no afecta el cálculo. Por lo tanto, los sistemas que rellenan un número específico de dígitos mediante la conversión de 1234 a 0.001.234 (por ejemplo), pueden llevar a cabo la validación Luhn antes o después del relleno y lograr el mismo resultado.

El algoritmo apareció en una patente estadounidense para un dispositivo mecánico manual que valida números por suma de verificación. El algoritmo por tanto debía ser bastante sencillo. El dispositivo toma la suma mod 10 por medios mecánicos. Los dígitos de sustitución , es decir, el resultado del proceso de duplicar y reducir, no se producía mecánicamente. Más bien, los dígitos eran marcados en su orden permutado en el cuerpo de la máquina.

Explicación informal[editar]

La fórmula verifica un número contra su dígito de chequeo incluido, el cual es usualmente agregado a un número de cuenta parcial para generar el número de cuenta completo. Este número de cuenta debe pasar la siguiente prueba:

A partir del dígito de chequeo incluido, el cual está a la derecha de todo el número, ir de derecha a izquierda duplicando cada segundo dígito.
Sumar los dígitos del resultado: (ejemplo: 10 = 1 + 0 = 1, 14 = 1 + 4 = 5) juntos con los dígitos sin duplicar del número original.
Si el total de módulo 10 es igual a 0 (si el total termina en cero), entonces el número es válido de acuerdo con la fórmula Luhn, de lo contrario no es válido.

Supongamos un ejemplo de un número de cuenta "7992739871", que contará con un dígito de control adicional, por lo que es de la forma 7992739871x:

Dígitos del número de cuenta	7	9	9	2	7	3	9	8	7	1	x
Duplicar dígitos pares	7	18	9	4	7	6	9	16	7	2	x
Sumar los dígitos	7	1+8	9	4	7	6	9	1+6	7	2	=67

El dígito de chequeo (x) se obtiene entonces de (67 * 9 mod 10). En términos sencillos:

Calcular la suma de los dígitos (67).
Multiplicar por 9 (603).
Tomar el último dígito (3).
El resultado es el dígito de chequeo.

(Método alternativo) El dígito de chequeo (x) se obtiene de (67 => dígito de las unidades: 7; 10 - 7 = dígito de chequeo: 3). En términos sencillo:

Calcular la suma de los dígitos (67).
Tomar el dígito de las unidades 7.
Restar el dígito de las unidades del módulo 10.
El resultado es 3.
El resultado es el dígito de chequeo.

Entonces, el número de cuenta completo es 79927398713.

Implementaciones[editar]

Verificación del dígito de chequeo[editar]

En Pascal

function CheckLuhn(purportedCC: String): Boolean;
var
  i: Integer;
  Sum: Integer;
  Digit: Integer;
begin
  Sum := 0;
  for i := Length( purportedCC ) downto 1 do begin
    Digit := Ord( purportedCC[ i ] ) - Ord( '0' );
	if not(Odd( i )) then begin
	  Digit := Digit * 2;
	  if (Digit > 9) then Digit := Digit - 9;
        end;
    Inc( Summ, Digit );
  end;
  Result := Summ mod 10 = 0;
end;

En Python:

def is_luhn_valid(cc): #Parametro ejemplo 5256783371567695

    num = map(int, str(cc))
    return sum(num[::-2] + [sum(divmod(d * 2, 10)) for d in num[-2::-2]]) % 10 == 0

Cálculo del dígito de chequeo[editar]

La implementación de arriba chequeó la validez de una entrada con un dígito de chequeo. El cálculo de dicho dígito requiere de una pequeña adaptación de lo anterior:

Cambiar la multiplicación par / impar.
Si la (suma mod 10) == 0, entonces el dígito de chequeo es 0.
Si no, el dígito de chequeo es igual a (10 - (sum mod 10))

En Python:

def calculate_luhn(cc):
    nums = [int(x) for x in str(cc)]
    check_digit = 10 - sum(nums[-2::-2] + [sum(divmod(d * 2, 10)) for d in nums[::-2]]) % 10
    return check_digit % 10