Criptografía de clave privada:
Cifrado de Vernam o “one-time pad”
Mensaje:
DEAD
Clave:
BEEF
Cifrado:
Canal
público
Bob
Tiempo
Alicia
Ejemplo:
1101 1110 1010 1101

=
1011 1110 1110 1111
0110 0000 0100 0010 = 6042
6042
Cifrado:
6042
Clave:
BEEF
Mensaje:
0110 0000 0100 0010

=
1011 1110 1110 1111
1101 1110 1010 1101 = DEAD
Problemas
• El emisor y el receptor necesitan obtener de manera
segura copias de la clave y mantenerlas seguras.
• Es seguro sólo si la clave es tan larga como el
mensaje que hay que cifrar.
• La clave no puede volver a usarse.
 No es práctico para uso general.
Ejemplo
“One-time pad” soviético
capturado por el MI5
Criptografía de clave pública
• Encriptación:
– M = mensaje
– KU = clave pública del emisor
– Cifrado: C = E(M, KU)
• Desencriptación:
– C = cifrado
– KR = clave (secreta) privada del receptor
– Mensaje original: M = D(C, KR)
El algoritmo de Rivest, Shamir y Adleman
El algoritmo RSA
•
•
•
•
•
•
•
Seleciona dos números primos p y q
Calcula n = p q
Calcula f(n) = (p-1)(q-1)
Seleciona e tal que 1 < e < f(n) y mcd(f(n), e) = 1
Calcula d tal que d e mod f(n) = 1
La clave pública es {e, n}
La clave privada es {d, n}
El algoritmo RSA
• Mensaje: M
e
• Cifrado: C = M mod n
• Mensaje: M = Cd mod n
El algoritmo RSA (ejemplo)
•
•
•
•
Selecciona dos números primos p =7 y q =17
Calcula n = p q = 119
Calcula f(n) = (p-1)(q-1) = 96
Selecciona e tal que 1 < e < f(n) y mcd(f(n), e) = 1,
e.g., e = 5
• Calcula d tal que d e mod f(n) = 1, d = 77
• La clave pública es {e, n} = {5, 119}
• La clave privada es {d, n} = {77, 119}
El algoritmo RSA (ejemplo)
• Mensaje: M = 19
e
5
• Cifrado: C = M mod n = 19 mod 119 = 66
• Mensaje: M = Cd mod n = 6677 mod 119 = 19
Para romper RSA
•
•
•
•
Factoriza n, que es público, y así obtienes p y q
Calcula f(n) = (p-1)(q-1)
Calcula d tal que d e mod f(n) = 1 (e es público)
La clave privada es KR = {d, n}
Rompiendo RSA (ejemplo)
•
•
•
•
Factoriza 119, que es público, y así obtienes 7 y 17
Calcula f(119) = (7-1)(17-1) = 96
Calcula d tal que d 5 mod 96 = 1 (5 es público), d = 77
La clave privada es KR = {77, 119}
Historia (pública) de la criptografía de clave pública
• 1976 – Propuesta por Diffie y Hellman.
– Se basa en la dificultad de calcular logaritmos discretos (resolver
ax = b mod n para x).
• 1977 – Algoritmo RSA desarrollado por Rivest, Shamir y Adleman.
– Se basa en la dificultad de factorizar números grandes.
– RSA129 (129 dígitos) publicado como desafío.
• 1994 – RSA129 roto con 1600 ordenadores en red.
• 1999 – RSA140 roto con 185 ordenadores en red en 8,9 años-CPU.
• 1999 – RSA155 (clave de 512 bits) roto con 300 ordenadores en red.
• 2002 – RSA recomiendan claves de 1024 bits.
Descargar

The KS theorem