Codificacion RSA

Bitácora 09

Criptografía de clave pública o clave asimétrica [Diffie-Hellman 1976]
Snoopy tiene dos claves: la clave pública, que la conoce
todo el mundo, y la clave privada que solo la conoceél.
Mafalda le quiere enviar un mensaje
codificado E(m) a Snoopy y usa la clave pública
de Snoopy para codificarlo. Él usa su clave secreta para recuperar el
mensaje, es decir, desencriptarlo.
Elespía no es capaz de descifrar el
mensaje que Mafalda le envía a Snoopy, a
pesar de que conoce la clave pública, ya que
lo que necesita es la privada, que solo
Snoopy conoce.

Matemática básica autilizar
Dados dos primos p y q es fácil multilplicarlos: n=pq.
•
•
•
•
•

Pero dado n, ¿cómo encontrar p y q rápidamente? ¿Cómo factorizar n?
Fácil para números pequeños (ej.: 6,35).Durante siglos, los matemáticos han intentado encontrar métodos para factorizar
números muy grandes. Ninguno es conocido.
Para factorizar un número n de 10000 dígitos, el ordenador más rápido tardaríasiglos.
Pretendemos que para que el espía sepa el mensaje, deba factorizar números más
grandes.

Esquema de codificación RSA [Rivest Shamir Adleman 1978]
•
•
•
•

Elegir dos primos muygrandes p y q y calcular n=pq.
Conociendo p y q, elegir e y d. Para todo m:(me)d ≡ m (mod n)
La clave pública será e, n.
La clave secreta será d.

Pequeño teorema de Fermat
Si a y p, p primo /mcd(p,a)=1. p y a son primos entre si (p no divide a a).
ap-1≡ 1 (mod p)
ap ≡ a (mod p)
an ≡ a (mod a)

n = pq p, q primos
elegir el e, d tales que:
(me)d ≡ m (mod n)
CLAVE PÚBLICA
CLAVE PRIVADAe, n
d

Para codificar el mensaje m, Mafalda calcula: (encriptar (E))
• E(m) = me (módulo n)
solo ha utilizado la clave pública
¿Cómo recuperamos el mensaje original? (desencriptar (D))
• D(m)= xd (módulo n)
utilizando la clave privada

(me) módulo n ≡ m es congruente con m.
La única manera de calcular m el E(m) implica factorizar n y cp,p no se puede
factorizar n, utilizamos la...