Un problema al que nos enfrentamos habitualmente cuando tenemos que obtener datos de un usuario es el de detectar información falsa o con errores.

No siempre, pero cuando se trata de cierto tipo de datos es posible aplicar fórmulas para verificar la veracidad de esos datos.

En esta entrada veremos algunas de esas fórmulas, y algunos ejemplos para implementarlas en C++.

Número DNI o NIF

Al menos en España, desde hace bastantes años, cada ciudadano tiene un DNI (Documento Nacional de Identidad), en el que figuran algunos datos sobre él. Cuando se obtiene por primera vez, se le asigna un número de ocho cifras, que es único para cada persona.

Posteriormente, con fines fiscales, se creó el NIF (Número de Identificación Fiscal). En el caso de personas físicas, el NIF es el mismo número del DNI al que se añadió una letra como control. Esa letra se obtiene aplicando una fórmula al número del DNI, de modo que si se cambia cualquiera de los dígitos, o la letra, es posible detectar el error.

No se trata de un algoritmo demasiado sofisticado, como veremos a continuación.

Algoritmo

Básicamente se compone de dos pasos:

1. Se calcula el módulo, o resto de la división del número del DNI entre el valor 23.
2. La letra de control se obtiene usando como índice el valor actual, en la siguiente tabla de 23 letras:

0	1	2	3	4	5	6	7	8	9	10	11
T	R	W	A	G	M	Y	F	P	D	X	B
12	13	14	15	16	17	18	19	20	21	22
N	J	Z	S	Q	V	H	L	C	K	E

Se excluyen en esta tabla las letras: ‘I’, ‘Ñ’, ‘O’, ‘U’.

La ‘I’ y la ‘O’ se descartan porque es fácil confundirlas con otros caracteres, como ‘1’, ‘l’ ó ‘0’. La ‘Ñ’, porque se puede confundir con la ‘N’, y la u, seguramente, porque sobraba una letra.

Ejemplo de validación de NIF:

const int nifok = 0;
const int noesnif = 1;
const int faltaletra = 2;
const int nifincorrecto = 3;
const int niferroneo = 4;

int VerificarNIF(char *dni) {
    char letra[] = "TRWAGMYFPDXBNJZSQVHLCKET";
    unsigned int i;
    char l;
    int retval = nifok;

    if(strlen(dni) == 0) {
        retval = noesnif;
    } else
    if(isdigit(dni[strlen(dni)-1])) {
        retval = faltaletra;
    } else {
        for(i = 0; i < strlen(dni)-1; i++) {
            if(!isdigit(dni[i])) {
                retval = nifincorrecto;
            }
        }
    }
    if(!retval) {
        i = atoi(dni);
        l = dni[strlen(dni)-1];
        if(letra[i % 23] != toupper(l)) {
            retval = niferroneo;
        }
    }
    return retval;
}

Tarjetas de crédito

Para verificar los números de las tarjetas de crédito se usa el algoritmo de Luhn.

En este caso, el último dígito también es un dígito de control, que se puede calcular a partir de los dígitos restantes.

Hay más niveles de verificación, aunque nos limitaremos a este.

Por ejemplo, los seis primeros dígitos, conocidos como BIN, identifican el tipo de tarjeta, el primer dígito, y la entidad que emite la tarjeta, los cinco restantes.

Por ejemplo las tarjetas VISA empiezan siempre por ‘4’, las Mastercard por ‘5’, etc.

El algoritmo de Luhn es también muy simple. Hay que tener en cuenta que estos algoritmos de verificación están pensados para que sean sencillos y sirven para detectar pequeños errores.

1. Tomando los dígitos de derecha a izquierda, incluyendo el dígito de control, se duplican los de las posiciones pares y si el resultado es mayor de 9 se resta 9.
2. Se suman todos los dígitos así obtenidos.
3. Si el resultado es divisible entre 10, es decir, el módulo 10 es cero, el número es correcto.

Por ejemplo:

5245 6585 6635 5458

1285 3575 3665 1418

8+(2*5 mod 9)+4+(2*5 mod 9)+5+(2*3 mod 9)+6+(2*6 mod 9)+5+(2*8 mod 9)+5+(2*6 mod 9)+5+(2*4 mod 9)+2+(2*5 mod 9) =

8+1+4+1+5+6+6+3+5+7+5+3+5+8+2+1 =

70

Es decir, el número es correcto.

bool VerificarTarjeta(const char *numero) {
    char *n;
    int digito;
    bool par = false;
    int res = 0;

    n = new char[strlen(numero)+1];
    strcpy(n, numero);
    do {
        digito = n[strlen(n)-1]-'0';
        n[strlen(n)-1] = 0;
        res += digito;
        if(par) {
            res += digito;
            if(digito > 4) res -= 9;
        }
        par = !par;

    } while(strlen(n));
    delete[] n;
    return !(res % 10);
}

ISBN

El ISBN (International Standard Book Number) es un código numérico que se usa para identificar libros internacionalmente. Hay dos variedades, una de diez dígitos, y posteriormente se creó una segunda, de trece dígitos.

En ambos casos el último dígito se usa como dígito de control. Pero, cada una de ellas usa un algoritmo diferente para calcularlo.

ISBN de diez dígitos

En este caso, el dígito de control se calcula de la siguiente forma:

1. Se toman nueve dígitos de izquierda a derecha, multiplicando cada uno por la posición que ocupa, es decir, el primero por uno, el segundo por dos, etc. Y se suma cada resultado.
2. Al valor resultante se le aplica el módulo con once. Esto da un valor entre 0 y 10.
3. El dígito de control es ese valor, si está entre 0 y 9, ó X si es 10.

Por ejemplo, para un ISBN de diez dígitos:

84-9736-467-8

8+4*2+9*3+7*4+3*5+6*6+4*7+6*8+7*9 = 261

261 % 11 = 8

ISBN de trece dígitos

Se usa el mismo algoritmo que para códigos de barras EAN (European Article Number), que son los códigos de barras de toda la vida, que aparecen en casi todos los productos comerciales.

Algoritmo:

1. Se toman los doce caracteres de izquierda a derecha, multiplicando los impares por uno y los pares por tres, y se suma cada resultado.
2. El dígito de control se calcula restando de diez el módulo del resultado con diez. Es decir, el valor que habría que sumar al resultado para que sea divisible entre diez

Por ejemplo, para este ISBN:

978-84-253-4025-3

(9+8+4+5+4+2)+3*(7+8+2+3+0+5) = 32+3*25 = 32+75 = 107

10-107%10 = 10-7 = 3

bool ISBN10(const char *numero) {
    int res = 0;
    char control;

    if(strlen(numero) != 10) return false;
    for(int i = 0; i < 9; i++) {
        res += (numero[i]-'0') * (i+1);
    }
    control = res % 11;
    if(control == 10) control = 'X'; else control += '0';

    return control==numero[9];
}

bool ISBN13(const char *numero) {
    int res = 0;

    if(strlen(numero) != 13) return false;
    for(int i = 0; i < 13; i++) {
        if(i%2) res += 3*(numero[i]-'0');
        else res += numero[i]-'0';
    }

    return !(res % 10);
}

Códigos de cuenta de cliente e IBAN

Los códigos de cuenta de cliente (CCC) son los números de cuenta bancaria, que actualmente se están sustituyendo por el IBAN (International Bank Account Number)

El IBAN se obtiene fácilmente a partir del CCC. Basta con añadir cuatro caracteres delante del CCC, los dos primeros son dos letras que identifican el país, y los otros dos, son dos dígitos de control.

Verificación del CCC

Pero empecemos por el CCC, ya que también tienen un formato con dígitos de control.

El formato tiene veinte dígitos con la estructura siguiente:

 EEEE OOOO CC NNNNNNNNNN

EEEE: 4 dígitos que identifican la entidad bancaria
OOOO: 4 dígitos que identifican la oficina
C Un dígito de control Entidad/Oficina
C Un dígito de control Número de cuenta
NNNNNNNNNN: 10 dígitos de número de cuenta

El primer dígito de control se obtiene de los ocho primeros dígitos, y el segundo de los diez últimos.

El algoritmo es el mismo en los dos casos, aunque para los ocho primeros dígitos añadiremos dos ceros al principio, para que ambos conjuntos tengan diez dígitos cada uno.

1. Tomando los dígitos uno a uno, de izquierda a derecha, multiplicamos cada uno por los siguientes valores, respectivamente: 1,2,4,8,5,10,9,7,3,6.
2. Sumamos cada uno de los productos.
3. Calculamos el módulo once del valor obtenido.
4. Restamos ese valor de 11.
5. Si el módulo está entre 0 y 9, ese es el dígito de control, si es 10, tomaremos el valor 1, y si es 11, tomaremos el valor 0.

Los valores del paso 1 se calculan como 2ⁿ % 11, desde n=0 a n=9.

Por ejemplo:

1234 5678 06 1234567890

0*1+0*2+1*4+2*8+3*5+4*10+5*9+6*7+7*3+8*6 = 231

231 % 11 = 0

11-0 = 11

DC1 = 0

1*1+2*2+3*4+4*8+5*5+6*10+7*9+8*7+9*3+0*6 = 280

280 % 11 = 5

11-5 = 6

DC2 = 6

bool VerificarCCC(char *ccc) {
    // EEEE OOOO CC NNNNNNNNNN
    // 4 dígitos Entidad
    // 4 dígitos Oficina
    // Dígito de control Entidad/Oficina
    // Dígito de control Número de cuenta
    // 10 dígios Número de cuenta
    int peso[10] = {1,2,4,8,5,10,9,7,3,6};
    unsigned int i;
    int j, DC1, DC2;
    char ccc_l[21];

    if(strlen(ccc) != 20) {
        return false;
    }

    for(i = 0; i < strlen(ccc)-1; i++) {
        if(!isdigit(ccc[i])) {
            return false;
        }
    }
    strcpy(ccc_l, ccc);

    for(DC1 = i = 0; i < 8; i++) {
        DC1 += peso[i+2] * (ccc[i]-'0');
    }
    DC1 = 11-(DC1%11);
    if(DC1 == 10) DC1 = 1;
    if(DC1 == 11) DC1 = 0;

    for(DC2 = i = 0; i < 10; i++) {
        DC2 += peso[i] * (ccc[i+10]-'0');
    }
    DC2 = 11-(DC2%11);
    if(DC2 == 10) DC2 = 1;
    if(DC2 == 11) DC2 = 0;

    if(ccc[8]-'0' != DC1 || ccc[9]-'0' != DC2) {
        return false;
    }
    return true;
}

Verificación del IBAN

Para formar el IBAN se usan veinticuatro caracteres. Los dos primeros son dos letras que identifican el país, en el caso de España, «ES». Los dos siguientes son un número de control. A continuación se añaden los veinte dígitos del CCC.

Para verificar el IBAN se usa el siguiente algoritmo:

1. Los cuatro nuevos caracteres se eliminan y se añaden al final de número
2. Las letras se sustituyen por un valor numérico de dos dígitos cada uno. Ese valor numérico es 10 para la ‘A’, 11 para la ‘B’, etc.
3. Se calcula el módulo del número resultante con 97.
4. Si es 1, el código IBAN es correcto.

Por ejemplo:

ES68 1234 5678 06 1234567890

12345678061234567890ES68

E: 14, S:28

12345678061234567890142868 % 97 = 1

Tenemos que resolver un pequeño problema adicional: C++ no dispone de enteros lo suficientemente grandes como para manejar números de 26 cifras, y el valor 97 se escogió deliberadamente por ser el mayor número primo menor de 100, de modo que…

Afortunadamente disponemos de un algoritmo para calcular restos de divisiones cuando el dividendo es un número grande y el divisor es relativamente pequeño, al menos lo suficiente para poder manejarlo con un int de C++. Se trata del algoritmo Big Mod, que vimos en una entrada anterior.

En el caso de los códigos IBAN, la verificación es doble, ya que los veinte dígitos finales deben verificar el algoritmo para CCC, y el código completo, el de IBAN:

bool VerificarIBAN(const char *iban) {
    char *iban2;
    int resto;

    if(!VerificarCCC(&iban[4])) return false;

    iban2 = new char[27];
    strcpy(iban2, &iban[4]);
    sprintf(iban2, "%s%02d%02d%c%c", 
        &iban[4], 10+iban[0]-'A', 10+iban[1]-'A', iban[2], iban[3]);
    resto = moduloNG(iban2, 97);
    delete[] iban2;
    return resto == 1;
}

int moduloNG(const char *numero, int d) {
    int i = 0, n = 0;

    while(numero[i]) n = (n * 10 + numero[i++] - '0') % d;
    return n;
}

---

Enlaces de interés:

NIF: Wikipedia

Código de cuenta cliente: Luciano.com

Código IBAN: CienciaExplora.com

Tarjetas: Wikipedia, eHow Español

Pongamos que tenemos que calcular el módulo o resto de la división de un número de muchas cifras entre otro más pequeño, lo suficiente para que pueda almacenarse en un int, o en un long int.

No es algo que no nos vayamos a encontrar nunca. De hecho, la razón de esta entrada es que he necesitado hacer estas operaciones, y pronto veremos un ejemplo en una entrada posterior.

En principio no parece fácil, pero las matemáticas vienen en nuestra ayuda. Concretamente la teoría de números.

El algoritmo que vamos a ver, como dice el título se llama Big Mod.

Este algoritmo se basa en estas dos propiedades:

(a*b*c) mod m =((a mod m)*(b mod m)*(c mod m)) mod m (1)
(a+b+c) mod m =((a mod m)+(b mod m)+(c mod m)) mod m (2)

Primero veamos qué significa exactamente calcular el módulo de una división.

dividendo  = cociente * divisor + resto

Hay que tener en cuenta que, a la hora de calcular el resto, nos podemos despreocupar del valor del cociente. Esto nos puede ayudar, porque el resto es el mismo si restamos del dividendo el divisor un número entero de veces:

dividendo – n * divisor = (cociente-n) * divisor + resto

Por otra parte, si descomponemos el dividendo en dos factores, a y b:

a*b = cociente * divisor + resto

(a-n*divisor)*(b-m*divisor) = (cociente-n-m) * divisor + resto

Es decir, el resto es el mismo si restamos de cualquiera de los factores un múltiplo del divisor.

Lo mismo sirve para sumas, si descomponemos el dividendo en dos sumandos c y d:

c+d = cociente * divisor + resto

(c-n*divisor)+(d-m*divisor) = (cociente-n-m) * divisor + resto

Esto es, el resto es el mismo si restamos de cualquiera de los sumandos un múltiplo del divisor.

¿Cómo nos ayuda esto a resolver nuestro problema?

Veamos un ejemplo:

5657866541284565 % 67 =

(565*10¹³+7866541284565) % 67

Ahora, podemos restar del primer número, el 565 el valor 67, tantas veces como queramos. Lo haremos el máximo, es decir, nos quedaremos con el resto de 565/67, o lo que es lo mismo, 565 % 67 = 29.

(29*10¹³+7866541284565) % 67

O:

297866541284565 % 67

Como se puede ver, hemos disminuido en una unidad los dígitos del número grande.

Podemos aplicar esta técnica recursivamente, o mejor, iterativamente.

Algoritmo

1. Partimos de n igual a cero.
2. Tomamos un dígito de la izquierda del número grande y lo añadimos a la derecha de n.
3. Calculamos el módulo n % d, y lo guardamos en n.
4. Repetimos desde 2, hasta terminar los dígitos del número grande.
5. n contiene el valor del módulo.

5657866541284565 % 67

5 % 67 = 5

56 % 67 = 56

565 % 67 = 29

297 % 67 = 29

298 % 67 = 30

306 % 67 = 38

etc.

Código C++

Una implementación sencilla es esta:

int moduloNG(const char *numero, int d) {
    int i = 0, n = 0;

    while(numero[i]) {
        n = n * 10 + numero[i] - '0';
        n = n % d;
        i++;
    }
    return n;
}

Otra, más compacta:

int moduloNG(const char *numero, int d) {
    int i = 0, n = 0;

    while(numero[i]) n = (n * 10 + numero[i++] - '0') % d;
    return n;
}