Algoritmo de Luhn

¿Qué es una función Hash?
Si vamos a la definición de Wikipedia, nos dice "En informática, una función hash o algoritmo hash es una función para identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor ..."

Una función hash es un algoritmo matemático que nos da un resultado B al aplicarlo a un valor inicial A. Es como cualquier función matemática, por ejemplo la función raíz cuadrada nos daría como resultado 2 si se la aplicamos al número 4. E igual que cualquier función matemática tiene que actuar de tal forma y tiene que cumplir con ciertos criterios. No nos puede devolver cualquier cosa, lo que nos devuelva requiere que tenga ciertas propiedades para que podamos usarlo.

¿Qué propiedades tienen que cumplir las funciones hash?
1- Sea cual sea la longitud del texto base A, la longitud de su hash resultante B siempre va a ser la misma. Por ejemplo, si la longitud de la salida B esta definida en 128 bits, si aplicamos una función hash a un A de 5 bits nos dará un B de 128 bits, y si se la aplicamos a un A de 380 millones de bits, nos dará un B de 128 bits igualmente.

2- Para cada entrada A, la función generará una salida B única. O lo que es lo mismo, es imposible que dos textos bases A y A' tengan un mismo hash B.

Según estas dos primeras propiedades, nos damos cuenta enseguida de la utilidad de las funciones de hash.

La más inmediata es usarla para generar un resumen de algo. De hecho, estas funciones se conocen también como funciones resumen. Un ejemplo real puede ser el del típico repositorio de documentos. Si alguien quiere almacenar digamos "Las_Aventuras_Del_Ingenioso.doc" cuyo contenido es El Quijote enterito, el sistema lo primero que tiene que hacer es revisar que no está previamente ya almacenado con el mismo o con otro nombre, por ejemplo "ElQuijote.doc". El sistema puede comparar letra a letras el documento de entrada con todos los docs de su BBDD para comprobar que no está, o puede comparar el resumen del documento de entrada con los resúmenes de los documentos de la BBDD, opción mucho más manejable y rápida.

Además, como la salida B es única para cada A, se puede usar también para verificar la integridad de A. Podemos ver que muchos programas incluyen su hash junto con su descarga, de esta forma, podemos verificar que el programa no ha sido modificado ni le han introducido un virus o ha sido troyanizado. Si a los bytes de una aplicación A les calculo el hash B y lo adjunto, cuando alguien modifique la aplicación A, al calcular de nuevo su hash su valor habrá cambiado y será distinto de B.

Pueden probar a calcular el md5 de un documento, luego con una simple modificación comouna coma del documento y calculando de nuevo el MD5. Verás como ha cambiado completamente, aunque solo hemos realizado un simple cambio.

Una función muy utilizada actualmente es la de verificar el IMEI de los teléfonos móviles mediante un simple algoritmo. Te propongo el análisis de ese algoritmo y determinar si el mismo responde de una manera elemental a una función hash.

De Wikipedia, la enciclopedia libre

El IMEI (del inglés International Mobile Equipment Identity, Identidad Internacional de Equipo Móvil) es un código pre-grabado en los teléfonos móviles GSM. Este código identifica al aparato unívocamente a nivel mundial, y es transmitido por el aparato a la red al conectarse a ésta.

Esto quiere decir, entre otras cosas, que la operadora que usemos no sólo conoce, quién y desde dónde hace la llamada (SIM) sino también desde qué terminal telefónico la hizo. La empresa operadora puede usar el IMEI para verificar el estado del aparato mediante una base de datos denominada EIR (Equipment Identity Register).

El IMEI de un aparato habitualmente está impreso en la parte posterior del equipo, bajo la batería. Se puede marcar la secuencia *#06# (asterisco, numeral, cero, seis, numeral) para que aparezca en el display; El IMEI tiene 15 cifras (en algunos teléfonos 14, se omite el ultimo digito SPARE normalmente un 0). En los teléfonos en los que aparezcan 17, los 2 últimos no se emplean. El IMEI subdivide en varios campos TAC, FAC, SNR y SPARE.

EIR

La EIR es una base de datos en la que existe información sobre el estado de los teléfonos móviles. Dentro de esta base de datos existen tres listas de IMEI: la blanca, la gris y la negra.

La lista blanca identifica a los equipos que están autorizados para recibir y realizar llamadas. Esta lista debe siempre existir en el EIR, aun cuando sea la única; las otras dos son opcionales.

La lista gris identifica a los equipos que pueden hacer y recibir llamadas, pero que pueden ser monitoreados para descubrir la identidad del usuario utilizando la información almacenada en el chip SIM.

La lista negra identifica a los equipos a los que se les impide conectarse a la red. Contiene los identificativos de los equipos robados o utilizados de forma ilegal y también la de aquellos equipos que no pueden acceder al sistema porque podrían producir graves problemas técnicos; por lo tanto, no pueden realizar ni recibir llamadas.

Estructura del código de IMEI

El código de IMEI consta de cuatro partes y sigue el siguiente esquema: 358987010052195

La primera parte (358987) se denomina Type Allocation Code(TAC), en donde los primeros dos dígitos indican el RBI,la organización que regula el telefono vendido, en este caso 35 que corresponde a BABT

La segunda parte (01) es el Final Assembly Code (FAC) e indica el fabricante del equipo.

La tercera parte (005219) es el número de serie del teléfono.

El último dígito (5), es el dígito verificador, usado para verificar que el IMEI es correcto.

Check digit

El ultimo dígito del IMEI es un Check Digit o dígito verificador calculado usando el Algoritmo de Luhn, fórmula (ISO/IEC 7812). Ver GSM 02.16 / 3GPP 22.016.

El dígito verificador es calculado por medio de tres pasos:

Iniciando a la derecha, duplicar cada dígito par (e.g., 7 → 14).

Sumar todos los dígitos obtenidos (e.g., 14 → 1 + 4).

Verificar que la suma es divisible por 10.

Por ejemplo, si el IMEI de su teléfono es: 49015420323751?, no registramos el último dígito

Para hacer que la suma sea divisible por 10, se requiere que el dígito verificador sea un 8, por lo tanto el IMEI es 490154203237518.

Con el siguiente código en C++ puedes verificar si el número de IMEI de tu teléfono es válido.

Puedes complementar este artículo con el siguiente: Algoritmo de Luhn