Criptografía

 

La criptografia moderna se basa en en los números primos para la ejecución de sus algoritmos. Esta idea parte de la base que factorizar un número grande es una tarea muy costosa para cualquier computador moderno, ya que estos se vuelven ineficientes a partir de ciertas cantidades.Algunos de los protocolos y aplicaciones criptográficas mas importantes SSL, 3D-secure, OpenPGP, SSH, SSL o el más moderno TLS se basan en algoritmos de este estilo.

Esto hace que existan algoritmos como RSA de clave pública (Estándar IEE) utilizados para cifrar y firmar digitalmente. Este algoritmo utiliza 2 números primos de 155 dígitos en adelante (512 bits), obteniendo un producto de aproximadamente 310 dígitos (1024 bits) resultando prácticamente imposible de descifrar por los computadores actuales.

DESCRIPCIÓN DEL RSA

El algoritmo utiliza dos claves, una privada y una pública. Solo se envia la pública para cifrar y la privada se utiliza para descifrar.

La clave pública será (n,e) (que son el módulo y el exponente de cifrado).
La clave privada será (n,d) (que son el módulo y el exponente de descifrado).

n = p · q (p y q números primos de 155 dígitos generados aleatoriamente)
e = Un número mas pequeño y comprimo con f(n)
d = Un número donde ed – 1 sea divisible por f(n) (se calcula con el algoritmo de euclides extendido)

y f(n) = (p-1) · (q-1) donde f es la función fi de Euler y mide el número de coprimos con n hasta n.

EJEMPLO

Willy quiere enviar un mensaje “OK” a Pam (que dependiendo de la aplicación puede ser una operación bancaria, una firma digital, incluso un simple mensaje de whatsapp)

1. El pc de Pam calcula la clave privada y la clave pública y le envia la clave pública a Willy.

p = 439, q = 449 (En este ejemplo usamos primos pequeños para que se pueda ver)

n = 439 · 449 = 197111

f(197111) = 196244 = 73 · 7 · 2 · 2 · 2 · 2 · 2 · 2 · 2

e = 19 · 11 · 5 = 1045 (un número que no comparta factores, es decir coprimo con 196244)

d:
(d · 1045) – 1 = múltiplo de 196244
d · 1045 – 1 = k · 196244
d = (k·196244 + 1)/1045 (para que d sea entero la división tiene que ser exacta)

k=1, d=187,7.. NO
k=2, d=365,5.. NO
.
.
k=31, d=5821 OK

Pam tiene como clave privada (197111,5821) y clave pública (197111,1045) y envia la clave pública a Willy.

2. El pc de Willy recibe la clave pública (n,e) de Pam y transforma el mensaje en un número m que sea menor que n.

Willy recibe la clave pública (197111,1045)

Ahora transforma el mensaje OK en un número m:

O:2
K:1

(En este ejemplo es una asignación completamente arbitraria ya que esto se realiza con unas tablas de conversión.)

m = “OK” = 21

3. El pc de willy cifra el texto que se transforma de m a c con la operación c = m^e mod n

c = 21¹⁰⁴⁵ mod 197111 = 63202

4. Willy envia el mensaje c a Pam

Willy envia 63202

5. Pam recibe c y lo decodifica con m = c^d mod n

Pam descifra el mensaje con la clave privada

m = 63202⁵⁸²¹ mod 197111 = 21 = “OK”

¿DONDE ESTÁ LA SEGURIDAD?

Si un hacker pudiera recuperar los mensajes que se envían, podría recuperar en este caso:

• La clave pública (197111,1045)

• El mensaje “63202”

por tanto tendría:

n = 197111
e = 1045
c = 63202

pero para descifrar el mensaje m necesita d ya que:

m = 63202^d mod 197111

y la única manera de obtener d:

(d · e) – 1 = múltiplo de fi(197111)
d · 1045 – 1 = k  · f(197111)

d = (k · f(197111) + 1)/1045

El problema es que para conocer f(197111) necesita p y q y no los tiene.
La única manera es factorizar n pero en números de 1024 bits resulta imposible para el pirata porque tardaría años en resolverlo.

Esto se conoce como el problema RSA y su dificultad para resolver con números grandes es lo que garantiza la seguridad del sistema.
Otros algoritmos de encriptación basados en los primos son:

• DSA

• ECDSA

• Diffie-Hellman

• ElGamal