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

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

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

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

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

Verificación del dígito de chequeo

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):
    nums = [*map(int, str(cc))][::-1]
    # str(cc) convierte el número en una cadena de texto
    # map(int, str(cc)) convierte cada dígito en la cadena de texto en un entero
    # obteniendo los digitos del numero cc individualmente
    # [*map(...)] convierte el objeto map en una lista a través de unpacking
    # Finalmente, [...][::-1] devuelve la lista en reversa

    for i in range(1, len(nums)+1, 2):
        # Itera sobre todos los numeros entre 1 y la longitud de la lista de dos en dos
        # p. Ej. [1, 3, 5, 7, 9, 11, 15]
        nums[i] *= 2
        # Multiplica el numero que está en ese índice en la lista por 2
        if nums[i] > 9:
        # Verifica si ese numero se volvió mayor que 9
            nums[i] -= 9
        # En caso de ser así, le resta 9 para obtener la suma de sus digitos
    return sum(nums) % 10 == 0
    # Finalmente, la función devuelve True si el residuo al dividir la suma de los numeros entre 10 es 0
    # Es decir, si la suma de los números da como resultado un multiplo de 10
    # De lo contrario, devuelve False

Un código simplificado luciría de esta manera:

def is_luhn_valid(cc):
    nums = [*map(int, str(cc))]
    nums[-2::-2] = [sum(divmod(d*2, 10)) for d in nums[-2::-2]]
    # slice assignment
    return not sum(nums)%10
    # Si sum(nums)%10 devuelve 0, este 0 será tratado como False y, al negarlo con «not» devolverá True
    # Si sum(nums)%10 es cualquier otro número distinto de 0, este lo tratará como True y, al negarlo, devolverá False

Cálculo del dígito de chequeo

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