RSA. Sistemas de clave pública

1. Sistemas de Clave Pública
2. Encriptación de clave pública
3. Algoritmo de Rivest, Shamir y Adelman (RSA)
4. Gestión de claves

5. Ejemplo
6. Conclusiones

Sistemas de Clave Pública

Uno de los criterios con los que se diseña un sistema informático(SI) es el de la seguridad. Seguridad es la facultad de estar a cubierto de algún riesgo o amenaza. Los SI deben incorporar mecanismos que permitan ofertar unos servicios de seguridad a los usuarios. Los criterios fundamentales al establecer la seguridad de la información son:

• Confidencialidad (secreto): información sólo disponible a ususarios autorizados a manejar el mismo
• Integridad: permite asegurar que no se ha falseado la información.
• Accesibilidad: asegura quién puede acceder a la información y en qué momento.
• Autenticidad: permite asegurar el origen y el destino de la información.
• Imposibilidad de rechazo (no repudio): permite asegurar que una entidad que envia o recibe no puede negar ante terceros su envio o recepción.

Un sistema criptográfico consta de 5 componentes:

• Espacio de mensajes M: conjunto de posibles mensajes
• Espacio de cifrados C: conjunto de textos cifrados
• Espacio de claves K
• Transformaciones de cifrado: donde K es el parámetro necesario para transformar M en C
• Transformaciones de descifrado: donde K es el parámetro necesario para transformar C en M

• Criptosistemas simétricos: una única clave privada para cifrar y descifrar
• Criptosistemas asimétricos: dos claves (una pública y otra privada) para cifrar y descifrar.

Encriptación de clave pública

El encriptado de clave pública se propuso por primera vez en 1.976 por Diffie y Hellman. Se basa en funciones matemáticas en lugar de sustituciones y permutaciones. Antes de entrar en describir su modo de funcionamiento diremos que sus características principales son:

• La resolución de la desencriptación es un problema NP completo: no existe un algoritmo conocido capaz de reslizar la desencriptación en un tiempo polinomial
• Preservan las propiedades de confidencialidad y autenticidad.
• Cualquier clave de las dos que se utilizan se pueden utilizar para el encriptado y el desencriptado indistintamente.
• Introduce más complejidad en los procesos de gestión de claves (generación, almacenamiento, distribución y mantenimiento)
• Constituye la base del sistema de firma electrónica.

Modo de funcionamiento

1. Característica de confidencialidad
• Para cada usuario A y B se generan un par de claves de las cuales una (la clave pública) se publica en un registro o fichero público y la otra (clave privada) se mantiene en secreto por su propietario.
• Para encriptar un mensaje se utiliza la clave pública mientras que para desencriptar se usa la clave privada.
• Si A desea enviar un mensaje a B, encripta el mensaje usando la clave pública de B.
• Cuando B recibe el mensaje lo desencripta usando la clave privada de B (su propia clave). Ningún otro puede desencriptar el mensaje ya que sólo B conoce la clave privada.
• El sistema es seguro mientras que cada usuario controle su clave privada.
• En cualquier momento se puede cambiar la clave privada generando un nuevo par de claves.
2. Característica de autenticidad
• En este caso, A prepara un mensaje para B y lo encripta utilizando su propia clave privada (la clave privada de A).
• Cuando B lo recibe lo desencripta utilizando la clave pública de A.
• La autenticidad se asegura ya que solamente A puede encriptar el mensaje.
• Es imposible alterar el mensaje sin acceder a la clave privada de A por lo tanto se asegura la autenticidad y la integridad de los datos.
• El mensaje entero encriptado sirve como una firma digital y requiere gran cantidad de almacenamiento:
• el mensaje original sin cifrar (por motivos prácticos)
• el mensaje original cifrado que sirve para verificar el origen y el contenido
• Para reducir el almacenamiento y conseguir el mismo resultado de firma digital:
• Se encripta un pequeño bloque de bits resultado de una función del documento (normalmente suele ser una función hash). Este bloque de bits se denomina autentificador y tiene la propiedad de que no es posible cambiar el documento sin que varíe el autentificado.
• Para la encriptación se utiliza la clave privada del emisor por lo que sirve como firma digital.
• Con este mecanismo no se asegura la confidencialidad ya que el mensaje va en claro, pero sí se garantiza la autenticidad y la integridad.

Algoritmo de Rivest, Shamir y Adelman (RSA)

Fue desarrollado en 1.977 por estos autores en el MIT y es el único algoritmo mundialmente aceptado como encriptado de clave pública. Se basa en el problema de la factorización de un número con un gran número de cifras en sus factores primos.

En el RSA el texto motivo M y el texto cifrado C se califican como enteros entre 0 y n-1 para un n dado. La función de cifrado es c(e,n), donde emisor debe conocer los valores e y n

La función de descifrado es dc(d,n), donde el receptor debe de conocer los valores de d y n. Por lo tanto éste es un algoritmo de clave pública donde la clave pública es e, n, y la clave privada es d,n.

La generación de las claves se hace de la siguiente forma:

1. Se relacionan dos números primos p y q cuyo producto es n= p·q
2. Calculamos el valor d(n) (totalizada de Euler de n) que es el nº de dispositivos menores que n y relativamente primos a n.
3. Se relaciona el entero d que es relativamente primo al valor d(n), esto es que al máximo común divisor de d y (n) debe ser 1.
4. Se calcula e como la inversa de d, módulo d(n).

• Siempre es posible encontrar valores n, e y d tal que se asegure el cifrado y descifrado pata todo M
• Es relativamente fácil calcular M y C para todos los valores M
• Es imposible calcular d dado e y n en un tiempo computacional razonable para claves de 300 dígitos decimales 1.024 bits.

• Fuerza bruta: probar todas las claves privadas posibles, actualmente imposible para el tamaño de claves que se utilizan.
• Factorizar n en un número primo ya que así se puede obtener fácilmente d(n) y d. Esta tarea es hoy computacionalmente imposible en un tiempo razonable para claves mayores de 1.024 bits.

Gestión de claves

Para que el método de cifrado sea válido es necesaria la protección adecuada de las claves y, por lo tanto, son necesarias una serie de procedimientos adecuados a la gestión de claves. La gestión de claves son una serie de técnicas de generación, almacenamiento, distribución y mantenimiento, aplicada a la información almacenada y transmitida a las redes de ordenadores.

• Generación de claves. Un método para la generación de claves sería aquel que proporcionara claves de forma equiprobable. En la práctica los algoritmos existentes generan claves pseudoaleatorias lo más impredecibles posible. Los procedimientos más utilizados son los generadores aletorios de bits, los generadores mediante registros de desplazamiento y mediante la utilización de algoritmos matemáticos, generadores de secuencias.
• Almacenamiento de claves. En los sistemas de clave pública existen un par de claves para cada usuario: la clave privada es responsabilidad del usuario que debe mantenerla en secreto y fuera del alcance de intrusos; en cambio, la clave pública debe ser accesible por todo el mundo y, por lo tanto, debe residir en un lugar con máxima accesibilidad. El problema puede surgir para asegurar que las claves públicas pertenecen a quien dicen ser. Para esto surge el concepto de entidad certificadora que almacena todas las claves públicas y se comporta como un notario que asegura la identidad de los propietarios de cada clave pública.

• Distribución de claves. En los sistemas de clave pública hay que evitar la suplantación de clave pública. El emisor genera una clave privada que mantiene en secreto y una pública que envía a la entidad certificadora. La entidad certificadora determina por algún procedimiento de identificación personal que es la verdadera clave pública del emisor, e incorpora una marca de tiempo a la clave pública, genera un código hash al resultado y encripta el resultado con su clave privada formando una firma digital. Esta firma se incorpora a la clave pública, para que cualquiera pueda verificar que la clave pública del emisor es auténtica.
• Mantenimiento de claves. Se refiere al cambio periódico de las claves y a las acciones a tomar cuando son reveladas o robadas.
• Cambio de claves: se deben de cambiar con cierta frecuencia y comunicar su cambio a la entidad certificadora para que valide la nueva clave pública. De esta forma se incrementa la seguridad del criptosistema.
• Pérdida, revelación o robo de claves: se debe comunicar inmediatamente a la entidad certificadora que invalidará la clave pública. Entonces se procederá a la generación de un nuevo par de claves.

Ejemplo

Sea una codificación del alfabeto que transforma las letras de la A a la Z en los números del 0 al 25 (utilizaremos el alfabeto español sin considerar la LL, Ñ ni la CH ). Nosotros seremos el usuario A, cuya clave publica es (na, eA)=(155011,2347) y cuya clave privada es dA =151267. Deseamos enviar un mensaje al usuario B utilizando la codificación anterior.

Veamos como el usuario B elabora su clave publica y su clave privada.

El usuario B elige 2 números primos pB=281 y qB=167, calcula nB=281*167=469127 y considera el conjunto reducido de residuos modulo nB a R46927. La función de Euler para R46927 vale f(46927)=280*166=46480. El usuario B elige él numero eB =39423 y comprueba que mod(39423, 46480)=1. A continuación determina el dB / dB * 39423 º 1 (mod 46480), donde dB = 26767. Por tanto, la clave publica de B vale (nB , eB ) = (46927, 39423), y su clave privada vale dB = 26767.

Ahora vamos a enviar a B el mensaje “YES”. Para enviar el mensaje hemos de codificarlo, es decir, expresarlo en base 26, de modo que el mensaje sea un elemento de RnB .

YES = Y*26 ^ 2 + E*26 ^ 1 + S*26 ^ 0 = 24*26 ^ 2 + 4*26 ^ 1 + 18*26 ^ 0 = 16346 = m.

Ahora encriptamos m con la clave publica de B.

c = (16346)39423 mod 46927 = 21166

Decodificamos el mensaje encriptado

c =1*26 ^ 3 + 5*26 ^ 2 + 8*26 ^ 1 + 2*26 ^ 0= BFIC

Por tanto el mensaje que se envía a B es “BFIC”. Para que B pueda recuperar el mensaje, deberá codificar los datos reducidos en base 26, y a continuación aplicar la función de desencriptado.

BFIC = 1*26 ^ 3 + 5*26 ^ 2 + 8*26 ^ 1 + 2*26 ^ 0 = c

m= (21166)26767 mod 46927 =21166

Se decodifica m y se obtiene el texto original.

m =24*26 ^ 2 + 4*26 ^ 1 + 18*26 ^ 0 = YES

Ejemplos con OpenSSL para generar una clave:
 

#include <openssl/rsa.h>
#include <stdlib.h>

void introduce (void);
 

main()
{
   RSA *clave;

   introduce();
   clave= RSA_generate_key(64, 17, NULL, NULL);
/* funcion de openssl/rsa.h que genera una clave de rsa de 64 bits con */
/* clave publica 17*/
}
 

void introduce (void)
{
   int *vector;
   int indice;

   vector= (int *) malloc (sizeof(int)*1000);
   for (indice= 0; indice< 1000; indice++)
            vector[indice]= rand();
 

 /* Ahora faltaria una funcion que generara numeros aleatorios */
}

Ejemplo con OpenSSL para generar claves automaticamente:

                 openssl genrsa -out clave.pem

                  - Convertir una clave en una clave privada RSA:

                   openssl rsa -in clave1.pem -out clave2.pem

                  - Encriptar una clave privada usando triple DES:

                    openssl rsa -in clave1.pem -des3 -out clave2.pem

Conclusiones

El sistema de encriptación de clave publica RSA es del orden de 1000 veces mas lento que cualquier algoritmo de cifrado de clave privada como el DES. No obstante, a pesar de esta deficiencia, el criptosistema RSA ( y otras de clave publica) se utilizan mucho porque permiten firmar digitalmente los mensajes que se envían. Dado que el criptosistema RSA es bastante lento en su ejecución, generalmente se utiliza en conjunción con el criptosistema de clave privada DES de la siguiente manera:

1. A se quiere comunicar con B, y para ello elige un numero aleatorio s de 168 bits y lo cifra utilizando la clave publica de B.
2. B descifra el paquete con su clave privada y obtiene s. Este numero se ha transmitido de forma confidencial.