¿Qué es RSA?

septiembre 14, 2007 § 1 comentario

El sistema criptográfico con clave pública RSA es un algoritmo asimétrico cifrador de bloques, que utiliza una clave pública, la cual se distribuye (en forma autenticada preferentemente), y otra privada, la cual es guardada en secreto por su propietario.

Una clave es un número de gran tamaño, que una persona puede conceptualizar como un mensaje digital, como un archivo binario o como una cadena de bits o bytes.

Cuando se envía un mensaje, el emisor busca la clave pública de cifrado del receptor y una vez que dicho mensaje llega al receptor, éste se ocupa de descifrarlo usando su clave oculta.

Los mensajes enviados usando el algoritmo RSA se representan mediante números y el funcionamiento se basa en el producto de dos números primos grandes (mayores que 10100) elegidos al azar para conformar la clave de descifrado.

Emplea expresiones exponenciales en aritmética modular.

La seguridad de este algoritmo radica en que no hay maneras rápidas conocidas de factorizar un número grande en sus factores primos utilizando computadoras tradicionales.
La computación cuántica podría proveer una solución a este problema de factorización.

El algoritmo RSA es un algoritmo de clave pública desarrollado en 1977 en el MIT por Ronald Rivest, Adi Shamir y Leonard Adelman.

Fue registrado el 20 de Septiembre de 1983. El 20 de Septiembre del 2000, tras 17 años, expiró la patente RSA, pasando a ser un algoritmo de dominio público.

Este popular sistema se basa en el problema matemático de la factorización de numeros grandes.

El algoritmo RSA funciona de la siguiente manera:

  1. Inicialmente es necesario generar aleatoriamente dos números primos grandes, a los que llamaremos p y q.
  2. A continuación calcularemos n como producto de p y q: n = p * q
  3. Se calcula fi: fi(n)=(p-1)(q-1)
  4. Se calcula un número natural e de manera que MCD(e, fi(n))=1 , es decir e debe ser primo relativo de fi(n).
    Es lo mismo que buscar un numero impar por el que dividir fi(n) que de cero como resto.
  5. Mediante el algoritmo extendido de Euclides se calcula d: e.d mod fi(n)=1 Puede calcularse d=((Y*fi(n))+1)/e para Y=1,2,3,… hasta encontrar un d entero.
  6. El par de números (e,n) son la clave pública.
  7. El par de números (d,n) son la clave privada.
  8. Cifrado: La función de cifrado es C = M^e mod n
  9. Descifrado: La función de descifrado es M = C^d mod n

Ejemplo con números pequeños

  1. Escogemos dos números primos, por ejemplo p=3 y q=11.
  2. n = 3 * 11 = 33
  3. fi(n) = (3-1) * (11-1) = 20
  4. Buscamos e: 20/1=0, 20/3=6.67. e=3
  5. Calculamos d como el inverso multiplicativo módulo z de e, por ejemplo, sustituyendo Y por 1,2,3,… hasta que se obtenga un valor entero en la expresión: d = ((Y * fi(n)) + 1) / e = ( Y * 20 + 1) / 3 = 21 / 3 = 7
  6. e=3 y n=33 son la clave pública
  7. d=7 y n=33 son la clave privada
  8. Cifrado: Mensaje = 5, C = M^e mod n = 5^3 mod 33 = 26
  9. Descifrado: M = C^d mod n = 26^7 mod 33 = 8031810176 mod 33 = 5

Ejemplo visual de RSA

Un ejemplo pedagógico trivial del algoritmo RSA se muestra en la siguiente animación. Para este ejemplo hemos seleccionado p=3 y q=11, dando n=11 y z=20. Un valor adecuado de d es d=7, puesto que 7 y 20 no tienen factores comunes.

Con estas selecciones, e puede encontrarse resolviendo la ecuación 7e=1(mod 20), que produce e=3.El texto cifrado, C, de un mensaje de texto normal, P, se da por la regla C=P3(mod 33). El texto cifrado lo descifra el receptor de acuerdo con la regla P= C7(mod 33). Observe la animación tanto en el emisor como en el receptor, donde se muestra el cifrado-descifrado del texto normal “CASA”.

Dado que los números primos escogidos para este ejemplo son tan pequeños, P debe ser menor que 33, por lo que cada bloque de texto normal puede contener sólo un carácter. El resultado es un cifrado por sustitución monoalfabética, no muy impresionante. En cambio si hubiéramos seleccionado p y q 10100, podríamos tener n 10200, para que cada bloque pueda ser de hasta 664 bits (s644 10200) u 83 caracteres de 8 bits, contra 8 caracteres para el DES.

Más información de algoritmos de clave pública, de criptosistemas, de ataques a RSA y por supuesto el infaltable libro de criptografía del profesor Jorge Ramio Aguirre y de Manuel Lucena, todos ellos descargables de nuestra sección de libros de seguridad.

Fuentes:
http://neo.lcc.uma.es/evirtual/cdd/tutorial/presentacion/ejmrsa.html
http://es.wikipedia.org/wiki/RSA
http://daniellerch.com/sources/doc/algoritmo_rsa.html

Anuncios

§ Una respuesta a ¿Qué es RSA?

  • Muchas gracias me sirvió muchísimo el articulo, no entendía bien esto de la generación de claves y me hice bolas con la aritmética modular, la explicación que das esta correcta. Y me servirá para aplicarla en mi tesis de grado que estoy haciendo. Gracias. (tesis) Modelo criptografico híbrido basado en criptografia simétrica y criptografia asimétrica.

Responder

Por favor, inicia sesión con uno de estos métodos para publicar tu comentario:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

¿Qué es esto?

Actualmente estás leyendo ¿Qué es RSA? en Seguridad Informática.

Meta

A %d blogueros les gusta esto: