Secretos inconfesables

El trabajo de programador es un trabajo poco agradecido y quizá por ello tan denostado por muchos informáticos. Hay que estar hecho de una pasta especial. Horas y horas ante un ordenador, implementando pedazos de código. Horas de concentración para no cometer errores (o los menos posibles). Horas y horas tratando de hacer realidad la fantasía perpetrada a partes iguales por el cliente y mi jefe de proyecto que, por supuesto, no ha escrito una línea de código en su vida. Eso sí, no esperes recibir la gloria el día que la aplicación comience a funcionar. Tu sólo habrás sido el albañil que ha colocado los ladrillos. Ni por asomo será mérito tuyo, sino de tu jefe por haber sabido apretarte las tuercas... En mi caso, ese jefe se llama Gaznápiro y aquél día se había levantado con ganas fastidiarnos un poco. A cada rato se posaba sobre mi hombro a mirar el código que estaba escribiendo y soltar la primera chorrada que se le pasaba por la cabeza: "Esos nombres de variable no me gustan", "Coloca las llaves en la siguiente línea para que los bloques queden más claros", "No uses la doble barra para el comentario, que no es ANSI C", ... Y así toda la mañana. Hasta que por fin salió a ver a un cliente. Como tenía ganas de desahogarme le envié a Sofía el siguiente mensaje por email:

AOPA CWVJWMEÑL AO QJ EJQPEH

Era un mensaje cifrado. Lo enviaba así, por una parte, porque nunca me he fiado de la privacidad del correo electrónico del trabajo y, por otra, porque sabía que a Sofía le encantaban los enigmas.



No habían pasado ni cinco minutos cuando Sofía me miró con cara de perdonarme la vida: vas a tener que esmerarte más porque este cifrado lo descifraría mi abuela hasta borracha. Aunque te doy toda la razón a lo que dices.

Lo cierto es que era un cifrado muy básico llamado Cifrado del César, porque ya lo usó Julio César. Es lo que se llama un cifrado por sustitución, ya que lo que se hace es sustituir una letra por otra. En este caso yo había hecho la siguiente correspondencia:

ABCDEFGHIJKLMNÑOPQRSTUVWXYZ
WXYZABCDEFGHIJKLMNÑOPQRSTUV

Es decir, sustituir la A por W y así sucesivamente; o lo que es lo mismo, desplazar el abecedario 4 posiciones a la derecha. Sustituyendo las letras de esta forma la frase en cuestión era:

ESTE GAZNAPIRO ES UN INUTIL
AOPA CWVJWMEÑL AO QJ EJQPEH

Sofía había deducido que "AO QJ" podría ser "ES UN" ya que no hay demasiadas palabras de dos letras que puedan ir juntas en una frase, y a partir de ahí había deducido el resto de sustituciones (supongo que antes probó con "ES LA" o "EN EL").

Sofía se impulsó sobre su silla de ruedas y se acercó a mi mesa: si quieres jugar hazlo bien -dijo con una sonrisa de oreja a oreja. ¿No se te ocurre nada mejor?
Sí -contesté- supongo que la clave está en buscar un algoritmo de codificación que sea sólo conocido por el emisor y el receptor.
Supones mal -contestó Sofía. Seguramente un buen criptoanalista acabaría descubriendo tu algoritmo y ¿entonces qué? ¿inventas otro algoritmo? Y si no que se lo cuenten a los Alemanes de la Segunda Guerra Mundial y su máquina Enigma.
Lo mejor -continuó- sería poder contar con un sistema de encriptación de información que fuera seguro incluso aunque el algoritmo fuera conocido. Se trata de codificar la información con una clave que sólo el emisor y el receptor conozcan, y que aún sabiendo el procedimiento para desencriptar la información, sin la clave sea imposible o muy difícil de descifrar. Algo como lo que tu has hecho con el cifrado del César: Has usado la clave 4, ya que, por ejemplo, la letra R menos 4 posiciones se corresponde con la letra Ñ.
Pero tú has roto la clave en muy poco tiempo -contesté- Si uso otra clave la volverías a averiguar.
Sí, porque tu clave es pequeña -prosiguió Sofía- De hecho, sin tener ninguna pista, sólo tengo que probar 26 claves diferentes para dar con tu frase encriptada. La idea es tener una clave tan fuerte que sea computacionalmente muy costoso encontrarla probando todas las posibilidades. En eso se basan los sistemas criptográficos actuales, como RSA.
Había leído un artículo sobre RSA no hacía mucho. Es el método más usado para firmar y encriptar datos actualmente. Es un sistema criptográfico de clave pública o asimétrico, es decir, que al contrario de un sistema de clave simétrica, donde emisor y receptor deben conocer la clave (¿quién nos asegura que nadie la intercepta cuando emisor y receptor intercambian la clave?), en el caso de RSA disponemos de una clave privada, que sólo nosotros conocemos, y otra pública que conoce todo el mundo. De esta forma, si quiero enviar un mensaje cifrado a alguien sólo tengo que encriptarlo con su clave pública, y sólo él podrá desencriptarlo con su clave privada.
Lo que no tenía muy claro es cómo funcionaba internamente y por qué se suponía que era tan robusto. Afortunadamente Sofía estaba dispuestísima a explicármelo:
La seguridad de un buen sistema de cifrado se basa en encontrar un proceso que sea fácil de resolver computacionalmente en una dirección, pero muy difícil de resolver en la dirección contraria. En eso se basa RSA. La idea básica es encontrar dos números primos los suficientemente grandes. Una vez los tengamos multiplicarlos es fácil, obtendremos un número muy grande. Sin embargo, el proceso contrario es muy difícil. Factorizar ese gran número para encontrar los primos iniciales es una tarea computacionalmente muy costosa. Sofía me explico los pasos para generar las claves pública y privada:

- Elegimos dos número primos a los que llamaremos P y Q. Mientras más grandes, más difícil será romper el cifrado, pero también será más costosa la encriptación/desencriptación. Hay que buscar un equilibrio. Primos de 1024bits en adelante son usados habitualmente con una seguridad bastante decente.

- Efectuamos la operación N=PxQ. A N lo llamamos Módulo de la clave. Por ejemplo, supongamos que tomamos P=157 y Q=251. En este caso N=39407. Evidentemente estos números son muy pequeños, pero así podremos seguir mejor el ejemplo.

- Calculamos phi(N)=(P-1)x(Q-1). Phi(N) es el número de enteros más pequeños que N que son primos relativos de N. En este caso phi(N)=(157-1)x(251-1)=39000.

- Buscamos un entero al que llamaremos E que es menor que phi(N) y además primo relativo con phi(N). Denominamos E como exponente de la clave pública. En este caso vamos a elegir E=5549.

- Buscamos un entero D tal que DxE=1 mod phi(N) (la inversa del modulo Phi(N)). A D lo denominamos exponente de la clave privada. Tras operar obtenemos D=7949.

En este punto tenemos ya la clave pública, que es la tupla (N, E) y la clave privada formada por (N, D).

Cifrar un mensaje es de lo más sencillo. Dado que RSA trabaja con números enteros habrá que codificar el texto que quiero cifrar con números enteros (por ejemplo, su valor ASCII). Supongamos que quiero cifrar un entero M para enviártelo a ti. Con tu clave pública lo encriptaría usando la fórmula:

valor_cifrado=M^E mod N.

Y para descifrarlo tú sólo tendrías que usar tu clave privada:
M=valor_cifrado^D mod N.

Desgraciadamente -continuó Sofía- cuando trabajamos con valores grandes los números que se manejan son astronómicos y no son manejables por los tipos primitivos de ningún lenguaje de programación, que son habitualmente de hasta 64bits. Es por ello, que si quieres hacer una inplementación del algoritmo tendrás que recurrir a alguna librería para el cálculo con números de precisión arbitraria, como libgmp u otra similar.

Sofía se volvió a su ordenador y al rato me envió un correo con el siguiente programa y un texto para descifrar que no reproduciré aquí por si mi jefe de proyecto, Gaznápiro, anda leyendo este blog.

1. // Este programa usa la librería libgmp (http://gmplib.org)
2. // para cálculo de números de precisión arbitraria.
3.  
4. #include <stdio.h>
5. #include <gmp.h>
6.  
7.  
8. // Calculo de la calve privada a partir de la clave pública.
9. int genkey(int n1, int n2, mpz_t e , mpz_t palabra) {
10.     // n1 y n2 son números primos.
11.     // e es un número aleatorio primo relativo con phi(n)
12.    
13.     int phi,i,tmp,ee,dd;
14.     mpz_t n,d,temp;
15.  
16.     mpz_init(n);
17.     mpz_init(d);
18.     mpz_init(temp);
19.     tmp=n1*n2;
20.     mpz_set_si(n,tmp);
21.     ee=mpz_get_si(e);  
22.     phi=(n1-1)*(n2-1);
23.  
24.     // Buscamos la inversa de d módulo phi.
25.     i=1;
26.     dd=1;
27.     while (i>0) {
28.         tmp=ee*i++;
29.         if (tmp%phi==1) {
30.             // Tenemos d
31.             dd=i-1;
32.             i=0;
33.         }
34.     }
35.        
36.     return dd;
37.  
38. }
39.  
40.  
41. // Algoritmo de encriptación.
42. int crypt(int n1, int n2, mpz_t e , mpz_t palabra) {
43.     // n1 y n2 son números primos.
44.     // e es un número aleatorio primo relativo con phi(n)
45.    
46.     int phi,i,tmp,ee;
47.     mpz_t n,temp;
48.  
49.     mpz_init(n);
50.     mpz_init(temp);
51.     tmp=n1*n2;
52.     mpz_set_si(n,tmp);
53.     ee=mpz_get_si(e);  
54.     phi=(n1-1)*(n2-1);
55.  
56.    
57.     mpz_powm(temp,palabra,e,n);
58.     tmp=mpz_get_si(temp);  
59.     return tmp;
60.  
61. }
62.  
63.  
64.  
65. // Algoritmo de desencriptación RSA.
66. int decrypt(int n1, int n2, int d , mpz_t palabra) {
67.     // n1 y n2 son números primos.
68.     // e es un número aleatorio primo relativo con phi(n)
69.    
70.     int tmp;
71.     mpz_t n,temp,dd;
72.  
73.     mpz_init(n);
74.     mpz_init(dd);
75.     mpz_init(temp);
76.     tmp=n1*n2;
77.     mpz_set_si(n,tmp);
78.     mpz_set_si(dd,d);
79.    
80.     mpz_powm(temp,palabra,dd,n);
81.     tmp=mpz_get_si(temp);  
82.     return tmp;
83.  
84. }
85.  
86.  
87. int main () {
88.     char i,texto[255];
89.     int j,d;
90.     mpz_t palabra,e;
91.    
92.     // Definimos los parametros de la encriptación (Clave pública).
93.     int n1=157;
94.     int n2=251;
95.  
96.     mpz_init(palabra);
97.     mpz_init(e);
98.     mpz_set_si(e,5549); // e = 5549
99.    
100.     d=genkey(n1,n2,e,palabra);
101.     printf ("\n\nImplementación del algoritmo RSA de encriptación.\n");
102.     printf ("Clave Pública: N=39407, e=5549\n");
103.     printf ("1 - Encriptar.\n");
104.     printf ("2 - Desencriptar.\n");
105.     printf ("--\n");
106.     printf ("Entre opción:");
107.     scanf ("%c",&i);
108.  
109.     switch (i) {
110.         case '1':
111.             printf ("Entre texto a codificar: ");
112.             scanf("%s",texto);
113.             j=0;
114.             do {
115.                 mpz_set_si(palabra,texto[j]);
116.                 printf("%d\n",crypt(n1,n2,e,palabra));
117.             } while ((texto[j++])!='\0');
118.             break;
119.         case '2':
120.             do {
121.                 printf ("\nEntre entero a decodificar: ");     
122.                 scanf("%d",&j);
123.                 mpz_set_si(palabra,j);
124.                 printf("%d = %c\n",j,decrypt(n1,n2,d,palabra));
125.             } while (j!=0);
126.             break;
127.     }
128.  
129.    return 0;
130. }