Cifrado Rsa

Criptosistemas de clave pública. El cifrado RSA
Criptosistemas de clave pública
Como ya se ha visto en el apartado de introducción a la criptografía, los criptosistemas de clave pública (también llamados criptosistemas asimétricos) se caracterizan por utilizar claves distintas para el cifrado y descifrado de la información. Su principal ventaja es que facilitan el proceso de distribución eintercambio de claves entre los participantes de la comunicación segura, que era un problema importante de los criptosistemas simétricos o de clave privada.
Los algoritmos asimétricos emplean generalmente longitudes de clave mucho mayores que los simétricos, que usan una única clave secreta. Por ejemplo, mientras que para algoritmos simétricos se considera segura una clave de 128 bits, para lamayoría de algoritmos asimétricos (incluido el del RSA), se recomiendan actualmente claves de al menos 1024 bits de longitud. Además, la complejidad de cálculo que comportan los algoritmos de los criptosistemas asimétricos los hace considerablemente más lentos que los algoritmos de cifrado simétricos. Por eso en la práctica los métodos asimétricos se emplean principalmente para codificar la clave desesión (simétrica) de cada comunicación o transacción particular.
La criptografía basada en criptosistemas de clave pública es relativamente reciente, pues los primeros algoritmos asimétricos aparecen después de 1975. El criptosistema de esta clase más importante y extendido hoy en dia es el RSA, que utiliza la exponenciación modular para cifrar y descifrar y basa su seguridad en la complejidad delproblema de la factorización de enteros grandes.
El criptosistema RSA
De entre todos los algoritmos asimétricos, RSA es el más usado y también quizás el más sencillo de entender e implementar. Una peculiaridad de este algoritmo es que sus dos claves sirven indistintamente tanto para cifrar como para autenticar. Debe su nombre a sus tres inventores: Ronald Rivest, Adi Shamir y Leonard Adleman, quepublicaron por primera vez el método RSA en 1977. Ha estado bajo patente de los Laboratorios RSA hasta el 20 de septiembre de 2000, por lo que su uso comercial estuvo restringido hasta esa fecha.
RSA, como ya se ha indicado, se basa en la difcultad que presenta la factorización de números grandes. Las claves pública y privada se calculan a partir de un número que se obtiene como producto de dosprimos grandes. Un atacante que quiera recuperar un texto claro a partir del criptograma y de la clave pública, tiene que enfrentarse a dicho problema de factorización.
El problema de la factorización de números grandes
Ya conocemos una forma posible de descomponer un número n en sus factores: probar a dividirlo por todos los números enteros positivos comprendidos entre 2 y la raíz de n. Perocuando hablamos de un número de tamaño 1024 bits, este método es computacionalmente impracticable. Por supuesto, a lo largo del tiempo los matemáticos han inventado otros métodos de factorización más eficientes, pero ninguno ha conseguido un algoritmo con un orden de complejidad que permita factorizar en un tiempo razonable números de tamaños como los empleados en RSA actualmente, aun con la potenciacomputacional disponible hoy en día.
De hecho el problema de la factorización de enteros se considera que es un problema de clase NP, es decir, un problema para el que existe uno o más algoritmos que lo resuelven, pero ninguno de los algoritmos conocidos se ejecutan en un tiempo polinomial (que pueda ser expresado polinómicamente en función del tamaño de los datos de entrada), y por lo tanto sonineficientes o intratables para datos de entrada muy grandes.
El algoritmo RSA
(1) Generación del par de claves
Para generar un par de claves (KP ; Kp), en primer lugar se eligen aleatoriamente dos números primos grandes, p y q (de unas 200 cifras cada uno, por ejemplo). Después se calcula el producto n = p.q
Escogeremos ahora un número e primo relativo con (p-1) y con (q-1). Este par de...