RSA

Whitfield Diffie y Martin Hellman
Diffie – Hellman

Es un algoritmo de cifrado asimétrico por bloques de clave pública y acrónimo de Rivest, Shamir y Adleman, autores del mismo en 1.977. En la actualidad es uno de los algoritmos más usados.

 

Para la comprensión del mismo se necesitan buenos conocimientos matemáticos en los siguientes conceptos: Anillo de los enteros, aritmética modular y descomposición en factores primos. Indicar que Ron Rivest, Adi Shamir y Len Adleman no fueron los descubridores del cifrado de clave pública, el origen está en el servicio secreto del Reino Unido mucho antes de la publicación del RSA.

 

Hay que destacar que los trabajos de Rivest, Shamir y Adleman se basan en los de Bailey Whitfield Diffie y Martin Hellman publicados como «New Directions in Cryptography» en 1.976, dónde presentaban, un nuevo método de distribución de claves criptográficas para solucionar uno de los problemas fundamentales la propia distribución de la clave.

Shamir Rivest y Adleman
Shamir, Rivest y Adleman

La seguridad del algoritmo se basa en:

  1. El desconocimiento del valor de la clave privada cpr.
  2. Tomar dos números grandes, que otros no conocen, haciendo que su diferencia también sea grande (p y q).
  3. Dificultad al factorizar el producto de los números p y q.

Funcionalmente lo podemos ver así:

Usuario A

  • Toma dos nºs primos grandes (p y q) que sólo él conoce (> 100 dígitos) y calcula n = p ×q.
  • Genera un número aleatorio a relacionado con n.
    Ya tiene una clave pública cpu: dos números (n, a). El resto de los usuarios utiliza estos dos números para cifrar los mensajes que quieren enviar a A.
  • También tiene una clave privada cpr, que él sólo conoce y relacionada con n y a.

Usuario B

  • Conoce la clave pública de A (n, a).
  • Su sistema de cifrado opera y envía el mensaje a A.

 

Simplificando la operatoria del algoritmo tenemos la siguiente secuencia:

 

Fase 1. Preparativos

  1. Tomamos dos números primos grandes p y q y los multiplicamos, con ello obtenemos n
  2. Creamos otro número, nf = (p-1) × (q-1)
  3. Generamos dos claves, una denominada pública (cpu) para cifrar, y otra privada (cpr) para descifrar.
  4. cpu y nf son primos relativos. (*1)
  5. cpr tiene que ser cpu × cpr ? 1 (mod nf), también cpr = cpu-1 (mod nf)

Fase 2. Tratamiento del mensaje.

  1. Tomamos el mensaje y lo dividimos en piezas de un tamaño inferior a n. Mensaje = me1 + me2 + me3, … + men. (*2)
  2. Ciframos cif = (me1cpu) (mod n)
  3. Descrifamos cif cpr = (me1 cpu) cpr = me1 cpu × cpr
    1. Sabemos que (cpu × cpr) ? 1 (mod nf)
    2. También que (cpu × cpr) / n da resto 1, es decir que existe otro número k que cumple (cpu × cpr) = k × nf + 1 que es igual a (cpu × cpr) = k × (p-1) × (q-1)
    3. Por tanto me1 cpu × cpr = me1 k × (p-1) × (q-1) + 1 = me1 z
    4. Hacemos el MCD de (me1, p). Sabemos que p es primo, por tanto:
      1. p es divisor de me1. Hacemos el MCD de (me1,p) = p y nos proporciona dos posibilidades:
        1. ( me1 cpu × cpr ) / p da resto cero
        2. ( me1 cpu × cpr ) / p da resto me1
        3. Esto significa que me1 cpu × cpr ? me1 (mod p)
      2. p no es divisor de me1. Tenemos que me1 p -1 ? 1 (mod p), resumiendo me1 k × (p-1) × (q-1) + 1 ? me1 (mod p)
    5. En los dos casos casos anteriores (4.1 y 4.2) tenemos el mismo resultado, me1 cpu × cpr ? me1 (mod p). Esto también es aplicable a q
  4. Resumen:
    1. me1 cpu × cpr me1 es divisible tanto por p como por q, de la misma forma también es divisible por p × q
    2. me1 cpu × cpr ? me1 (mod n)
    3. me1 = cif cpr (mod n)

Fase 3. Cifrado y descifrado.

Cifrado: cif = me1 cpu (mod n)
Descifrado: me1 = cif cpr (mod n)

 

 

(*1) Dos números son primos relativos cuando no tienen divisores comunes.

(*2) Los trozos del mensaje se representan como un número. En computación todo signo tiene un nº asignado.

 

RSA en Java
RSA en Java

 

 

 

Atención: En 2007, Bruce Schneier insinuó la existencia de una puerta trasera en RSA. Edward Snowden lo confirmó en 2.013, «se introdujo un fallo intencionado de seguridad creado por la NSA (National Security Agency de EEUU)», aplicable en RSA, que se «pegó» a la herramienta BSafe de ECM. La contraprestación, 10.000.000 dólares USA. Su punto débil fue dejar una serie de números fijos en la generación de los nºs aleatorios que utiliza RSA .

Bruce Schneier RSA
Bruce Schneier
 Edward Snowden RSA
Edward Snowden

 

Hasta 1.999 se recomendaba una clave de 512 bits, en esa fecha Adi Shamir desarrolló, teóricamente, unos dispositivos denominados Twirl y Twinkle capaces de factorizar números de manera muy rápida. Estos dispositivos pondrían en riesgo los mensajes cifrados con claves de 512 bits. Esto conlleva que la clave que utilicemos sea como mínimo de 2.048 a fecha de 2.015.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

cuatro + 19 =