Algoritmos de criptografía asimétrica
[3.1] ¿Cómo estudiar este tema?
[3.2] Cifradores asimétricos
[3.3] Certificados y firmas digitales
TEMA
Esquema
Algoritmos de criptografía asimétrica
TEMA 3 – Esquema
Firma digital y
Concepto Algoritmos
certificados digitales
Protección de la Algoritmo RSA Firma digital
información
Seguridad Certificados
2
Autenticación digitales
Vulnerabilidades
Ataque
man-in-the-middle
Algoritmo Diffie-Hellman
Algoritmo El Gammal
Algoritmo DSA
Criptografía y mecanismos de seguridad
Criptografía y mecanismos de seguridad
Ideas clave
3.1. ¿Cómo estudiar este tema?
Para estudiar este tema, además de las Ideas clave, lee los apartados 12.1, 12.2, 12.3
y 12.4 del capítulo 12 «Cifrados asimétricos» y los apartados 17.1, 17.2 y 17.3
del capítulo 17 «Autentificación, certificados y firmas digitales» del libro
Criptografía y seguridad de computadores de Manuel Lucena, disponible en:
[Link]
Una vez tratados los algoritmos simétricos, a continuación se presentan los algoritmos
que los complementan, los criptosistemas asimétricos. Estos sistemas en los que
existen dos claves de cifrado, una pública y otra privada, no precisan de un canal
seguro para que las partes puedan intercambiar la clave de cifrado. Esta
indudable ventaja permite que, disponiendo de la clave pública del destinatario, el
emisor pueda enviarle mensajes confidenciales sin necesidad de acordar una clave de
cifrado con este. Por otro lado, y a diferencia de esta ventaja de los criptosistemas
asimétricos, se trata de criptosistemas generalmente más lentos que los
simétricos y que permiten obtener altos niveles de seguridad deben manejar grandes
longitudes de clave.
Dentro de este tema también se trata la firma digital, que permite mediante el
empleo de la clave privada del emisor verificar la autenticidad del emisor; y
también de los certificados de clave pública que son necesarios para poder
verificar la asociación entre una clave pública (y la privada asociada) y un determinado
usuario.
Este tema tiene como objetivo principal presentarte los algoritmos de cifrado
asimétrico. Así el primer bloque, engloba esos conceptos y el segundo los relacionados
con la firma digital y del empleo de certificados digitales de clave pública.
TEMA 3 – Ideas clave
3
Criptografía y mecanismos de seguridad
3.2. Cifrados asimétricos
La principal característica de este tipo de algoritmos de cifrado es que la clave
empleada para el cifrado y descifrado de los mensajes está formada, en realidad, por
un par de ellas (clave pública y privada). Su fortaleza está basada en la complejidad
computacional que existe a la hora de calcular la clave privada partiendo del
conocimiento de la clave pública.
Las claves utilizadas por este tipo de algoritmo son de mayor longitud que las de los
simétricos y, además, su rendimiento es bastante menor (algoritmos pesados).
Debido a estos inconvenientes, el cifrado asimétrico se suele utilizar, en lugar de para
cifrar mensajes de longitud considerable, para cifrar las claves de sesión que serán
utilizadas por cifradores simétricos que cifrarán dichos mensajes.
Protección de la información
Teniendo dos entidades A y B que disponen de sus respectivos pares de claves
y donde A quiere enviar un mensaje hacia B y B quiere
responder a A, el proceso a seguir es el siguiente:
1. A cifrará el mensaje con (clave pública conocida por todos).
2. A envía el mensaje cifrado a B.
3. B descifrará el mensaje con (clave privada solo conocida por B).
4. B cifrará el mensaje con (clave pública conocida por todos).
5. B envía el mensaje cifrado a A.
6. A descifrará el mensaje con (clave privada solo conocida por A).
Autentificación
Mediante cifrado asimétrico y el empleo de funciones resumen es posible autentificar
la procedencia de los mensajes recibidos.
TEMA 3 – Ideas clave
4
Criptografía y mecanismos de seguridad
A continuación se detalla el método de autentificación en un escenario básico:
1. A recibe un mensaje cifrado con proveniente de B.
2. B genera el resumen del mensaje y lo envía cifrado con .
3. A descifra el mensaje proveniente de B con su .
4. A calcula el resumen del mensaje descifrado.
5. A descifra el resumen proveniente de B con su .
6. A compara con para autentificar a B.
Ataque man-in-the-middle
Todo algoritmo asimétrico es vulnerable a este tipo de
ataque. El atacante se interpone entre A y B en el
momento que se intercambian sus claves públicas, las
almacena y envía su propia clave pública a A y B para
poder suplantar la identidad de ambos. En este
momento C podrá descifrar todos los mensajes
provenientes de A y B y podrá enviarles mensajes que
ellos interpretarán como correctos.
La única solución ante tal ataque es confiar en un tercero (redes de «amigos») que
asegure que las claves públicas pertenecen a quien la envía.
Algoritmo RSA
Algoritmo asimétrico más sencillo de implementar y sin vulnerabilidades descubiertas
hasta la fecha. La fortaleza de RSA reside en la dificultad para factorizar el producto de
dos primos de gran tamaño.
TEMA 3 – Ideas clave
5
Criptografía y mecanismos de seguridad
Conceptos matemáticos
La generación de claves se realiza siguiendo los siguientes pasos:
1. Escoger dos primos grandes y , de forma aleatoria y calcular su producto
.
2. La clave pública será donde es un coprimo de que tendrá
inversa modulo , de lo que se deduce:
3.
Donde es la inversa de módulo . Forma la clave privada.
4. El cifrado se realizará mediante la ecuación .
5. El descifrado por su parte se realizará con .
Los primos escogidos suelen tener una longitud de 512 bits (o superior). El cifrado
incrementa ligeramente la longitud del texto respecto al original.
Los cálculos del algoritmo RSA pueden reducirse mediante el empleo del Teorema
Chino del Resto o de la ecuación .
Ejemplo:
1. Escogemos y . Por tanto .
2. Calculamos .
3. Escogemos , ya que (coprimos).
4. Calculamos la inversa módulo , por lo que
. .
5. La clave privada es por tanto y la pública .
6. Si queremos cifrar el mensaje se calculará con .
7. Para descifrarlo utilizaremos .
TEMA 3 – Ideas clave
6
Criptografía y mecanismos de seguridad
Seguridad
La seguridad de RSA se basa en la complejidad matemática de factorizar el
producto de primos grandes, ya que cualquier método que se encuentre para
atacar RSA supondrá también encontrar una forma más simple de factorización.
Se calculan números que sean «probablemente» primos, ya que no se comprueba que
los números sean coprimos (es computacionalmente muy costoso verificar su
primaridad con números tan grandes), aunque la probabilidad de que los números
escogidos no sean coprimos es despreciable.
Vulnerabilidades
Aunque la fuerza bruta queda descartada en este algoritmo, existen puntos débiles que
pueden ser utilizados por atacantes:
Claves débiles: Existen claves en RSA que no alteran el texto original al cifrarlo,
donde .
Claves cortas: Las claves de RSA deben ser mayores de 1024 bits y
recomendablemente, no inferiores a 2048 bits.
Texto en claro escogido: Existen dos posibles ataques.
o Enviando mensajes y tal que . Si la víctima los firma obtenemos
y con lo que podemos obtener el mensaje firmado .
o Explotando la posibilidad de que un usuario codifique y firme con el mismo par
de claves el mensaje completo (no el resultado del resumen).
Módulo común: Si se reutilizan los primos para generar las claves de RSA, el
atacante puede obtener el mensaje en claro empleando el algoritmo de Euclides
(ya que los valores de de la clave antigua y nueva suelen ser coprimos).
TEMA 3 – Ideas clave
7
Criptografía y mecanismos de seguridad
Exponente bajo: Existen implementaciones que utilizan valores de bajos para
optimizar el rendimiento (recomendable el mismo número de bits que n), esto
ocasiona:
o Teniendo 3 mensajes cifrados con distintos módulos (probablemente coprimos) y
un mismo valor bajo de , utilizando el Teorema Chino del Resto es posible
obtener el mensaje original.
o Siendo es posible obtener el mensaje original mediante un algoritmo
tradicional. Una solución es alargar el mensaje con bits aleatorios.
Firma y codificación: Es necesario firmar antes de codificar para evitar ataques.
Algoritmo Diffie-Hellman
Siendo A y B las entidades que quieren negociar la clave, se procede de la siguiente
forma:
1. Calcular un primo y un generador de donde (información
pública).
2. A escoge un número aleatorio tal que . A envía el valor .
3. B escoge un número aleatorio tal que . B envía el valor .
4. B calcula la clave .
5. A calcula la clave .
Algoritmo ElGamal
Su fortaleza reside en el problema de logaritmos discretos. Permite tanto firma
digital como cifrado de mensajes. La generación de claves se realiza escogiendo un
primo y dos números aleatorios y menores que . La clave privada es y la clave
pública está formada por el conjunto donde:
TEMA 3 – Ideas clave
8
Criptografía y mecanismos de seguridad
Para la firma digital:
1. Escoger un número aleatorio y coprimo con . El valor debe ser secreto y
cambiar cada vez.
2. Calcular .
3. Calcular .
4. La firma está formada por y la firma se comprueba mediante:
El cifrado y descifrado se realiza de la siguiente forma:
1. Escoger un número aleatorio y coprimo con . El valor debe ser secreto.
2. Calcular .
3. Calcular . Donde es el mensaje original.
4. El cifrado está formado por (doble longitud de ) y el descifrado se realiza
mediante:
Algoritmo de DSA
Variante del método de ElGamal utilizado para realizar firma digital.
El algoritmo de generación de claves es el siguiente:
1. Escoger tal que y un número primo tal que .
2. Escoger un número primo tal que y que sea divisor de .
3. Seleccionar un elemento y calcular .
4. Si volver al paso 3.
5. Escoger un número entero aleatorio tal que .
6. Calcular .
7. La clave pública la componen .
TEMA 3 – Ideas clave
9
Criptografía y mecanismos de seguridad
El proceso de firma y verificación queda descrito a continuación:
Siendo la firma y el mensaje original, el algoritmo a seguir es el siguiente:
1. Seleccionar un número aleatorio tal que .
2. Calcular .
3. Calcular .
4. Calcular .
5. La firma es la pareja .
La comprobación se realizará mediante los siguientes pasos:
1. Verificar que y . Rechazar la firma si no se cumple.
2. Calcular a partir de .
3. Calcular .
4. Calcular y .
5. Calcular .
6. Si aceptar la firma.
3.3. Certificados y firmas digitales
Firmas digitales
Firma digital
Secuencia de bits añadida a un mensaje y que garantiza su autenticidad.
La firma digital está vinculada a un único mensaje, únicamente puede ser generada
por el legítimo titular y es públicamente verificable.
La firma digital se realiza mediante el cifrado asimétrico del resumen del mensaje
original (clave privada). El receptor deberá realizar el resumen del mensaje y
comprobar si coincide con el descifrado de la firma digital (clave pública).
TEMA 3 – Ideas clave
10
Criptografía y mecanismos de seguridad
Certificados digitales
Un certificado digital está compuesto por una clave pública y un identificador que
son firmados por una autoridad de certificación (entidad que asegura que una clave
pública pertenece a un titular). Los certificados en formato X.509 son los más
conocidos y usados.
Si una clave se quiere revocar (por pérdida o robo) es posible realizar un certificado
de revocación. Este certificado contiene la clave pública firmada con la clave privada
del titular (de esta forma solo el titular puede revocar un certificado).
TEMA 3 – Ideas clave
11
Criptografía y mecanismos de seguridad
Lo + recomendado
No dejes de leer…
Cómo trabaja RSA
Interesante documento que describe el algoritmo RSA, algunas curiosidades y
potenciales vulnerabilidades.
El artículo completo está disponible en el aula virtual o en la siguiente dirección web:
[Link]
No dejes de ver…
Gambling with Secrets (RSA Encryption)
Se trata de un interesante vídeo que
ayuda a la compresión del algoritmo
RSA y de los algoritmos de
criptografía asimétrica.
El vídeo completo está disponible en el aula virtual o en la siguiente dirección web:
[Link]
TEMA 3 – Lo + recomendado
12
Criptografía y mecanismos de seguridad
+ Información
A fondo
PKCS #1
Texto que describe los aspectos técnicos y de implementación del algoritmo RSA. Se
trata del documento de referencia del algoritmo de criptografía asimétrica más
utilizado en la actualidad.
El artículo está disponible en el aula virtual o en la siguiente dirección web:
[Link]
Webgrafía
RSA Laboratories Home: RSA Security Research Center
Web del laboratorio de investigación de la empresa RSA, la página ofrece
documentación técnica sobre los algoritmos y nuevas investigaciones relacionadas.
[Link]
TEMA 3 – + Información
13
Criptografía y mecanismos de seguridad
Actividades
Algoritmo Diffie-Hellman
Usando el freeware Fortaleza de cifrados, desarrollar el algoritmo de intercambio de
clave de Diffie-Hellman con los siguientes parámetros. La zona de descarga del mismo
se informará oportunamente en el foro de la asignatura.
Primo p: 83
Generador α: 2
Valor secreto de Alicia: 16
Valor secreto de Bernardo: 58
1. Calcula la clave común que se intercambian Alicia y Bernardo.
Contesta en el documento Word que se adjunta y conviértelo a formato PDF. Para
realizar la entrega, se subirá a la plataforma únicamente el documento PDF con los
resultados obtenidos.
Trabajo: Cifrado y descifrado con RSA
Usaremos el freeware genRSA para generar claves y cifrar con RSA. La zona de
descarga del mismo se informará oportunamente en el foro de la asignatura.
1. Cifra el valor secreta 2001 con la siguiente clave RSA: p = 199, q = 227, e = 31.
2. Con la misma clave anterior, se ha recibido el criptograma 6408. Encuentra a qué
valor secreto representa el 6408 descifrando este criptograma usando ahora la clave
privada. Para usar este mismo software, haz uso de la propiedad de cambiar la clave
pública por la privada en la generación de la misma y que hemos visto en clase.
Contesta en el documento Word que se adjunta y conviértelo a formato PDF. Para
realizar la entrega, se subirá a la plataforma únicamente el documento PDF con los
resultados obtenidos.
TEMA 3 – Actividades
14
Criptografía y mecanismos de seguridad
Trabajo: Firma digital con SHA-1/RSA
Con el freeware Criptores vas a obtener la función hash SHA-1 en hexadecimal del
mensaje M y luego vas a firmarlo con RSA usando el freeware genRSA. La zona de
descarga de ambos programas se informará oportunamente en el foro de la asignatura.
M=
Este es el último trabajo práctico del módulo. Haremos primero el hash SHA-1 del
mensaje y después lo firmaremos con RSA.
Obtener la función hash SHA-1 del mensaje M (punto y aparte incluido).
Crea una clave RSA hexadecimal de 1024 bits con los siguientes valores:
Primo p =
D3A84CC4A4D9AB15A926F6DD91EC687F03C973B4A854A6DB2F0CD490958F73
7FA30D427AB8FB2FCAC80C77C3A55D0F9C7DEF437DA45B9DD894C108FD330
235FB
Primo q =
DC466B9B227C0E29548B2C2B7EC3A98247361EF7A90FDB2D0A2628D3A9D1D1
1E3CFCE177D87CAD7110A014FD610906E1CEBC4366C77665514F4021155E42CA7
F
Clave pública e =
010001
Una vez creada esa clave con genRSA, copia el valor de la clave privada d en la caja
de la cave pública, y vuelve a generar esta nueva clave. Observa que el valor anterior
de e = 010001 ahora queda como clave privada.
Cifra con genRSA el hash hexadecimal del punto 1 con esta nueva clave RSA para
que la cifra se realice con la clave privada d y así firmar.
Vuelve a generar la clave cambiando las claves d por e y comprueba la firma.
Contesta en el documento Word que se adjunta y conviértelo a formato PDF. Para
realizar la entrega, se subirá a la plataforma únicamente el documento PDF con los
resultados obtenidos.
TEMA 3 – Actividades
15
Criptografía y mecanismos de seguridad
Test
1. Los algoritmos de Diffie-Hellman y el RSA:
A. Ambos son algoritmos que basan su seguridad en el logaritmo discreto.
B. Ambos son algoritmos de cifra con clave pública.
C. Ambos pueden sufrir el ataque de hombre en medio.
D. Los interlocutores no precisan negociar una clave.
2. Supón un sistema RSA basado en p=9 y q=11:
A. Si la clave de cifrado es 3 la clave de descifrado es 67.
B. Si la clave de cifrado es 3 la clave de descifrado es 11.
C. Las claves no pueden ser calculadas.
D. Ninguna de las anteriores.
3. Supuesto el criptosistema RSA, el resultado de cifrar M=34 con la clave pública
(11,35) es:
A. 32.
B. 33.
C. 34.
D. 35.
4. La seguridad de RSA se basa en:
A. La dificultad del cálculo de la función de Euler.
B. La dificultad de factorización de números primos.
C. Las respuestas A y B son correctas.
D. Ninguna de las anteriores.
5. La criptografía asimétrica nace a partir de:
A. Los trabajos de Rivest, Shamir y Adleman en 1978.
B. Los trabajos de Claude Shannon en 1949.
C. Los trabajos de Diffie y Hellman en 1976.
D. Ninguna de las anteriores.
TEMA 3 – Test
16
Criptografía y mecanismos de seguridad
6. La seguridad de RSA se basa en:
A. La dificultad de factorización de grandes números compuestos.
B. La dificultad de encontrar el logaritmo discreto en primos grandes.
C. La fortaleza de las cajas S.
D. Ninguna de las anteriores.
7. Supuesto el criptosistema RSA, el resultado de cifrar M=2 con la clave pública (5,35)
es:
A. 18.
B. 32.
C. 23.
D. Ninguna de las anteriores.
8. ¿Cuál de los siguientes elementos no debe ir en el contenido de un certificado de
clave pública?
A. El algoritmo asimétrico empleado.
B. La fecha de emisión del certificado.
C. La clave privada del usuario.
9. La firma digital estándar DSA es:
A. Una modificación del algoritmo de Diffie y Hellman
B. Una modificación del algoritmo de Elgamal.
C. Una modificación del algoritmo RSA.
D. Una modificación del algoritmo AES.
10. El algoritmo RSA puede romperse:
A. Buscando la clave privada aplicando fuerza bruta.
B. Mediante un ataque Man in the middle.
C. Mediante un ataque Meet in the middle.
D. Ninguna de las anteriores.
TEMA 3 – Test
17
