Seguridad Informatica PDF
Seguridad Informatica PDF
Seguridad Informatica PDF
Sin más, y con la esperanza de que el libro electrónico de este curso que en su versión anterior
superó las dos mil descargas desde el servidor pueda serle de provecho, reciba un cordial saludo
Uno de los retos más fascinantes de la informática del futuro, inmersa en sistemas de
interconexión de redes y autopistas de la información, con un espacio virtual para el
intercambio de mensajes y datos a través de canales por definición vulnerables será, sin
lugar a dudas, la protección de la información. Representada por archivos confidenciales
o mensajes que se intercambian dos o más interlocutores autenticados y cuyo contenido
en muchos casos debe mantenerse en secreto por razones personales, empresariales,
políticas o de otra índole, la información es el bien más preciado en estos días. Por poner
sólo un ejemplo sencillo y común, un problema de gran actualidad es el asociado con el
correo electrónico que se transmite a través de redes y cuyo nivel seguridad deja mucho
que desear. Internet es un claro ejemplo de estas amenazas en tanto es un entorno
abierto en su sentido más amplio. Por lo visto en estos pocos años de existencia de la
llamada red de redes, sobran los comentarios acerca de pérdida de intimidad, accesos
no autorizados, ataques y otros delitos informáticos a nivel nacional e internacional.
Ante tales amenazas, la única solución consiste en proteger nuestros datos mediante el
uso de técnicas criptográficas. Esto nos permitirá asegurar al menos dos elementos
básicos de la Seguridad Informática, a saber la confidencialidad o secreto de la
información y la integridad del mensaje, además de la autenticidad del emisor.
Pág. 1
a comienzos de los 90 aparecía como una tímida apuesta por esta enseñanza en
carreras relacionadas principalmente con la Informática y las Telecomunicaciones, hoy
después de 10 años permite ver un mapa universitario en España en el que ninguna
universidad tecnológica se queda fuera en cuanto a la oferta de este tipo de asignaturas,
superándose las 40. Es más, comienzan ya a plantearse perfiles en los nuevos planes
de estudio con una clara orientación hacia la seguridad informática de forma integral.
Personalmente creo que esto es sólo el comienzo; incluso me he atrevido a proponer ya
no sólo un perfil, sino una carrera de ingeniería en la que cerca de un 30% de los créditos
estén relacionados con esta materia, en una ponencia presentada en un congreso el año
2001 y que podrá encontrar en el mismo servidor del que ha descargado este curso.
Puede parecer una utopía, para otros tal vez una locura, pero por lo que he visto en estos
últimos años tengo el presentimiento de que quizás el tiempo me dé la razón y veamos
en algunos años más un Ingeniero en Seguridad Informática.
Estoy plenamente consciente de que quedan muchos temas interesantes fuera del
contexto del libro electrónico, como son las nuevas técnicas de cifra con curvas elípticas,
estudio y profundización en sistemas actuales de clave secreta que tendrán importante
protagonismo en el futuro como Skipjack y Rijndael, diversas técnicas y protocolos de
autenticación, la teoría de cifra y factorización de polinomios, técnicas y algoritmos de
cifra en flujo, gestión completa de claves, protección en entornos de red, protocolos de
firma, Autoridades de Certificación, criptografía visual, esteganografía, etc. Resulta
imposible abordar tantos temas y plasmarlos en un libro electrónico que tenga un tamaño
relativamente normal: en la actualidad son casi 700 diapositivas. Ahora bien, como ya le
he comentado, estos apuntes se actualizan de forma periódica. Aunque no hay fechas
definidas para estas actualizaciones, como consejo le recomiendo que visite la Web dos
o tres veces al año y seguro encontrará una versión nueva.
* jramio@eui.upm.es
Web: http://www.lpsi.eui.upm.es/SInformatica/SInformatica.htm
CriptoRed: http://www.criptored.upm.es/
Pág. 2
SEGURIDAD INFORMÁTICA
LIBRO ELECTRONICO EN DIAPOSITIVAS
DE LIBRE DISTRIBUCIÓN EN INTERNET
Copyright
Fin de la Introducción
Criptografía
una definición ...
La Real Academia de la Lengua Española define
criptografía (oculto + escritura) como:
"el arte de escribir mensajes con una
clave secreta o de modo enigmático".
Resulta difícil dar una definición tan poco
ajustada a la realidad actual. Véase la siguiente diapositiva
Curso de Seguridad Informática. Tema 0: Una Introducción a la Criptografía. 3
© Jorge Ramió Aguirre Madrid (España) 2002
Imprecisiones de esta definición
Arte: la criptografía ha dejado de ser un arte: es una ciencia.
Escritura de mensajes: ya no sólo se escriben mensajes; se
envía o se guarda en un ordenador todo tipo de documentos e
información de distintos formatos (txt, doc, exe, gif, ...).
Una clave: los sistemas actuales usan más de una clave.
Clave secreta: existirán sistemas de clave secreta que usan
una sola clave y sistemas de clave pública (muy importantes)
que usan dos: una clave privada (secreta) y la otra pública.
Representación enigmática: la representación binaria de la
información podría ser enigmática para nosotros los humanos
pero jamás para los ordenadores J ... es su lenguaje natural.
Curso de Seguridad Informática. Tema 0: Una Introducción a la Criptografía. 4
© Jorge Ramió Aguirre Madrid (España) 2002
Una definición más técnica de criptografía
Criptografía
Lo que realmente es
Rama de las Matemáticas -y en la actualidad de la
Informática y la Telemática- que hace uso de métodos y
técnicas matemáticas con el objeto principal de cifrar un
mensaje o archivo por medio de un algoritmo, usando
una o más claves. Esto da lugar a los criptosistemas que
permiten asegurar cuatro aspectos fundamentales de la
seguridad informática: confidencialidad, integridad,
disponibilidad y no repudio de emisor y receptor.
Curso de Seguridad Informática. Tema 0: Una Introducción a la Criptografía. 5
© Jorge Ramió Aguirre Madrid (España) 2002
Confidencialidad e integridad
Cualquier medio de transmisión es inseguro
Criptosistema Medio de
Transmisor Transmisión Receptor
M C C M
T MT R
Confidencialidad
Usurpación de identidad Integridad Interceptación del mensaje
por un intruso (I) por un intruso (I)
Estos dos principios de la seguridad informática, el de la
confidencialidad y la integridad, (además de la disponibilidad
y el no repudio) serán muy importantes en un sistema de
intercambio de información segura a través de Internet.
Curso de Seguridad Informática. Tema 0: Una Introducción a la Criptografía. 6
© Jorge Ramió Aguirre Madrid (España) 2002
Tipos de criptosistemas
C’ no permitido M no permitido
Integridad Intruso Confidencialidad
M EB MT DDBB M
Usuario A C C Usuario B
Criptograma protegida
M no permitido
M DAA
D MT EA M
Usuario A C C Usuario B
protegida Criptograma
Cifrado de la información:
Sistemas de clave secreta
Firma e intercambio de clave de sesión:
Sistemas de clave pública
Curso de Seguridad Informática. Tema 0: Una Introducción a la Criptografía. 13
© Jorge Ramió Aguirre Madrid (España) 2002
Sistema híbrido de cifra y firma
k privada k pública
de A k secreta k secreta de A
M DA K K EA M
C
Usuario A K Usuario B K
internas o externas
Amenazas
La seguridad informática
será un motivo de
preocupación.
... y las empresas, organismos y particulares comienzan a
tener verdadera conciencia de su importancia.
Curso de Seguridad Informática. Tema 1: Conceptos Básicos de Seguridad Informática. 3
© Jorge Ramió Aguirre Madrid (España) 2002
Las dos últimas décadas
• A partir de los años 80 el uso del ordenador
personal comienza a ser común. Asoma ya la
preocupación por la integridad de los datos.
• En la década de los años 90 proliferan los ataques
a sistemas informáticos, aparecen los virus y se
toma conciencia del peligro que nos acecha como
usuarios de PCs y equipos conectados a Internet.
• Las amenazas se generalizan a finales de los 90.
Se toma en serio la seguridad: década de los 00s
Intruso
Intruso
Intruso
Intruso
HD SW
Interrupción (denegar servicio) Modificación (falsificación)
Interceptación (robo) Interrupción (borrado)
Interceptación (copia)
• Hardware:
– Agua, fuego, electricidad, polvo, cigarrillos, comida.
• Software:
– Borrados accidentales, intencionados, fallos de líneas
de programa, bombas lógicas, robo, copias ilegales.
• Datos:
– Los mismos puntos débiles que el software.
– Dos problemas: no tienen valor intrínseco pero sí su
interpretación y algunos son de carácter público.
• Confidencialidad
– Los componentes del sistema son accesibles sólo por
los usuarios autorizados.
• Integridad
– Los componentes del sistema sólo pueden ser creados
y modificados por los usuarios autorizados.
• Disponibilidad
– Los usuarios deben tener disponibles todos los
componentes del sistema cuando así lo deseen.
• No Repudio
– Este término se ha introducido en los últimos años
como una característica más de los elementos que
conforman la seguridad en un sistema informático.
– Está asociado a la aceptación de un protocolo de
comunicación entre emisor y receptor (cliente y
servidor) normalmente a través del intercambio de
sendos certificados digitales.
– Se habla entonces de No Repudio de Origen y No
Repudio de Destino, forzando a que se cumplan todas
las operaciones por ambas partes en una comunicación.
DATOS
Datos Seguros
Canal inseguro
Clave
Espacio de MENSAJES
Espacio de TEXTOS CIFRADOS
Espacio de CLAVES
Transformaciones de CIFRADO y DESCIFRADO
VjbmljYSBkZSBNYWRyaW
QgQ0ExLTArBgN... C = {c1, c2, ..., cn}
– Normalmente el alfabeto es el mismo que el utilizado
para crear el mensaje en claro.
– Supondremos que el espacio de los textos cifrados C y
el espacio de los mensaje M (con y sin sentido) tienen
igual magnitud.
– En este caso, a diferencia del espacio de mensajes M,
serán válidos todo tipo de criptogramas.
Ek: M ® C kÎK
Dk: C ® M kÎK
Medio de
Clave k Transmisión Clave k
M C C M
Texto Cifrado MT Descifrado
Texto
Base
Base
Ek Mensaje cifrado Dk
Clave
única
Cifrado: Ek Descifrado: Dk
• CIFRADO EN BLOQUE:
– El mismo algoritmo de cifra se aplica a un bloque de
información (grupo de caracteres, número de bytes,
etc.) repetidas veces, usando la misma clave.
• CIFRADO EN FLUJO:
– El algoritmo de cifra se aplica a un elemento de
información (carácter, bit) mediante un flujo de clave
en teoría aleatoria y mayor que el mensaje.
Buscamos la
M no permitido
confidencialidad
intruso
M no permitido
Usuario A Usuario B
Confidencialidad
Integridad
Esta característica
será muy importante
La integridad y la confidencialidad se
obtendrán ahora por separado ...
• El concepto en ingeniería:
– Estudio de las estadísticas y características del
lenguaje que nos permitirá su análisis desde un
punto de vista matemático, científico y técnico.
• El concepto en la empresa:
– Conjunto de datos propios que se gestionan y
mensajes que se intercambian personas y/o
máquinas dentro de una organización.
Curso de Seguridad Informática. Tema 2: Calidad de Información y Virus. 3
© Jorge Ramió Aguirre Madrid (España) 2002
Teoría de la Información
Solución Política 1
Política 2
La solución es Política 3
Sabotaje
Acción con la que se desea perjudicar a una empresa
entorpeciendo deliberadamente su marcha, averiando
sus equipos, herramientas, programas, etc. El autor no
logra normalmente con ello beneficios económicos pero
pone en jaque mate a la organización.
Mascarada
Utilización de una clave por una persona no autorizada
y que accede al sistema suplantando una identidad. De
esta forma el intruso se hace dueño de la información,
documentación y datos de otros usuarios con los que
puede, por ejemplo, chantajear a la organización.
Gusanos
Virus que se activa y transmite a través de la red. Tiene
como finalidad su multiplicación hasta agotar el espacio
en disco o RAM. Suele ser uno de los ataques más
dañinos porque normalmente produce un colapso en la
red (p.e. el gusano de Internet de Robert Morris Jr.).
Curso de Seguridad Informática. Tema 2: Calidad de Información y Virus. 17
© Jorge Ramió Aguirre Madrid (España) 2002
Algunos delitos informáticos (4)
Caballos de Troya
Virus que entra al ordenador y posteriormente actúa de
forma similar a este hecho de la mitología griega. Así,
parece ser una cosa o programa inofensivo cuando en
realidad está haciendo otra y expandiéndose. Ejemplo:
el huevo de Pascua de Windows 95.
Y hay muchos más delitos. Incluso aparecerán nuevos delitos
y ataques a los sistemas informáticos y redes que a fecha de
hoy no sabemos cómo serán ni qué vulnerabilidad atacarán...
Este enfrentamiento entre el “bien” y el “mal” es inevitable en
un sistema abierto ... y las comunicaciones hoy son así.
Si B£P*L
Hay que implementar una medida de
prevención.
Si B>P*L
No es necesaria una medida de prevención.
Factor L
• El factor de impacto total L es difícil de evaluar.
Incluye daños a la información, equipos,
pérdidas por reparación, por levantar el sistema y
pérdidas por horas de trabajo.
• Hay una parte subjetiva.
• La pérdida de datos puede llevar a una pérdida
de oportunidades. Efecto cascada.
Recomendación:
• En la organización debe existir una comisión
especializada interna o externa que sea capaz de
evaluar todas las posibles pérdidas y
cuantificarlas.
Factor P
• El factor P está relacionado con la determinación
de impacto total L. Depende del entorno en el
que esté la posible pérdida. La probabilidad
puede asociarse a una tendencia o frecuencia
conocida.
– Conocido P para un L dado, se obtiene la
probabilidad de pérdida relativa de la ocurrencia P*L
que se comparará con B, el peso que supone
implantar la medida de prevención respectiva.
Factor B
• Indica qué se requiere para prevenir una pérdida.
Factor B
• ¿Cuánta protección es necesaria?
– ¿Cuánta gasolina debemos echar en el depósito?
Depende de hasta dónde queramos desplazarnos con
el coche.
2. Determinar susceptibilidad.
Posibilidad de pérdida (P)
Curso de Seguridad Informática. Tema 3: Seguridad Física. 16
© Jorge Ramió Aguirre Madrid (España) 2002
Ejemplo de análisis de riesgo
• Políticas administrativas
– Procedimientos administrativos.
• Políticas de control de acceso
– Privilegios de acceso del usuario o programa.
• Políticas de flujo de información
– Normas bajo la cuales se comunican los
sujetos dentro del sistema.
• Políticas administrativas
Lo veremos a continuación
– Protección de software y
• Virus hardware con un
• Programas malignos antivirus.
• Pérdida de clientes
• Pérdida de imagen
• Pérdida de ingresos por beneficios
• Pérdida de ingresos por ventas y cobros
• Pérdida de ingresos por producción
• Pérdida de competitividad
• Pérdida de credibilidad en el sector
Curso de Seguridad Informática. Tema 3: Seguridad Física. 36
© Jorge Ramió Aguirre Madrid (España) 2002
Tiempo de recuperación ante desastres
• Plan de emergencia
– Vidas, heridos, activos, evacuación personal
– Inventariar recursos siniestrados
– Evaluar el coste de la inactividad
• Plan de recuperación
– Acciones tendentes a volver a la situación que
existía antes del desastre.
Curso de Seguridad Informática. Tema 3: Seguridad Física. 38
© Jorge Ramió Aguirre Madrid (España) 2002
Plan de continuidad
• Instalaciones alternativas
– Oficina de servicios propia
– Acuerdo con empresa vendedora hardware
– Acuerdo recíproco entre dos o más empresas
– Arranque en frío; sala vacía propia
– Arranque en caliente: centro equipado
– Sistema Up Start: caravana, unidad móvil
– Sistema Hot Start: centro gemelo
Fin del Tema 3
ci = - log2 (pi ) 0 pi
0 1
Combinación nº 1 Combinación nº 5
Combinación nº 2 Combinación nº 6
Combinación nº 3 Combinación nº 7
Combinación nº 4 Combinación nº 8
Combinación nº 1 Combinación nº 5
Combinación nº 2 Combinación nº 6
Combinación nº 3 Combinación nº 7
Combinación nº 4 Combinación nº 8
H(X)máx = log2 n
I 2 veces
A 3 veces I E A ““ M
““ 3 veces I E A ““
M 6 veces I E A
Creación del árbol de
Código óptimo: frecuencias observadas I E
• Ratio r
– Es el número de “bits de información” en cada carácter
para mensajes con una longitud igual a N caracteres.
Luego, según la definición de entropía, se tiene:
r = H(X)/N (bits/letra)
– Si codificáramos un mensaje letra a letra suponiendo
además equiprobabilidad entre las letras, se obtiene la
ratio absoluta del lenguaje, R:
R = H(X) castellano = 27 letras
Rcastellano = log2 n = log2 27 = 4.75 (bits/letra)
Curso de Seguridad Informática. Tema 4: Teoría de la Información. 26
© Jorge Ramió Aguirre Madrid (España) 2002
La ratio del lenguaje (2)
• Ratio verdadera
- Como las letras que aparecen en un texto no tienen
igual probabilidad, su frecuencia de aparición es
distinta, los lenguajes está muy estructurados, hay
bloques de dos palabras (digramas) característicos,
trigramas, poligramas, etc., la ratio baja mucho...
1.2 < r < 1.5
- A este valor se llega codificando los mensajes con
monogramas, digramas, trigramas, etc.
M = __H__B__N__V__Z__N__C__R__C__
Curso de Seguridad Informática. Tema 4: Teoría de la Información. 31
© Jorge Ramió Aguirre Madrid (España) 2002
Un ejemplo de redundancia (2)
Teníamos el mensaje M = HBNVZNCRC y además
M = __H__B__N__V__Z__N__C__R__C__
2a ayuda:
“El mensaje original contiene cinco palabras”.
Esto nos permite limitar el número de mensajes posibles
que tengan sentido. En estas condiciones podrían existir
muchos mensajes de 5 palabras, aunque no cumpliesen de
forma lógica con las reglas del lenguaje. Un ejemplo
podría ser...
M = AHÍ BUENO AVE ZONA CERCA
Curso de Seguridad Informática. Tema 4: Teoría de la Información. 32
© Jorge Ramió Aguirre Madrid (España) 2002
Un ejemplo de redundancia (3)
Teníamos el mensaje M = HBNVZNCRC y además
M = __H__B__N__V__Z__N__C__R__C__
M = AHÍ BUENO AVE ZONA CERCA
3a ayuda y siguientes:
a) “El mensaje original tiene que ver con un circo”.
b) “Corresponde al estribillo de una canción infantil”.
c) “Los espacios están: M = HB N VZ N CRC”.
Seguro que habrá adivinado ya el mensaje.... J
$ kj / Ekj(Mi) = Ci
M1 k1 C1
k3 k2
k2
M2 k3 C2
k1
k3 k1
M3 C3
k2
k1
p(M1) = 1/3 M1 C1 p(C1) = 3/9
k3 k2
k2
p(M2) = 1/3 M2 k3 C2 p(C2) = 2/9
k1
k3 k1
p(M3) = 1/3 M3 k2 C3 p(C3) = 2/9
p(C4) = 2/9
Algo más C4
C4
M1
k1
C1 SV: Un criptograma está asociado
k2
sólo a un texto en claro con sentido
M2 k1 C2 cifrado con una única clave ki.
k2
k2
M3 C3 SF: Cualquier otra solución de
k1
k1
cifra distinta a la anterior.
k2
M4 C4
M5
k1
C5 SV: C3 = Ek1(M5) C4 = Ek1(M2)
k2
M6 Soluciones: C6
C6 = Ek2(M1) C7 = Ek1(M3)
k1
Verdaderas Þ SV
M8 C8 SF: C2 = Ek1(M4) C2 = Ek2(M4)
SF C2: Condición obvia
M9 C9
C5 = Ek2(M2) C5 = Ek2(M5)
SF C5: Condición débil
SF C1: Condición fuerte
C1 = Ek1(M1) C1 = Ek2(M3)
M10 C 10
(A) Inicialmente hay que hacer un arduo trabajo para obtener algo
coherente. Habrá muchas soluciones falsas.
(B) Cuando se tiene una cantidad “adecuada” de texto cifrado, la
cantidad de trabajo disminuye. Se descartan algunas soluciones.
(C) Cuando se anula la equivocación de la clave, H(M/C) = 0,
disminuyen las soluciones falsas y la solución tiende a ser única.
Curso de Seguridad Informática. Tema 4: Teoría de la Información. 49
© Jorge Ramió Aguirre Madrid (España) 2002
Difusión y confusión
Para lograr un mayor secreto en las operaciones de cifra
Shannon propuso dos técnicas:
Difusión: Transformación sobre el texto en claro con objeto
de dispersar las propiedades estadísticas del lenguaje sobre
todo el criptograma.
TRANSPOSICIONES O PERMUTACIONES Fin del Tema 4
• Propiedad Reflexiva:
a º a mod n "aÎZ
• Propiedad Simétrica:
a º b mod n Þ b º a mod n " a,b Î Z
• Propiedad Transitiva:
Si a º b mod n y b º c mod n
Þ a º c mod n " a,b,c Î Z
¿7 mod 3 = 4? Þ Sí porque:
7 º 4 mod 3 7-4 = 3 = k*3 (k=1)
Y además: 7 mod 3 = 1 y 4 mod 3 = 1
es lo mismo que
Algoritmo de Euclides:
– a) Si x divide a a y b Þ a = x * a’ y b = x * b’
– b) Por lo tanto: a - k * b = x * a’ - k * x * b’
a - k * b = x (a’ - k * b’)
– c) Entonces se concluye que x divide a (a - k * b)
Curso de Seguridad Informática. Tema 5: Teoría de los Números. 11
© Jorge Ramió Aguirre Madrid (España) 2002
Divisibilidad de los números (2)
28 = 2 * 12 + 4 73 = 14 * 5 + 3
12 = 3 * 4 + 0 5 = 1* 3 + 2
No hay
mcd (148, 40) = 4 factor común 3 = 1* 2 + 1
385 = 5 * 7 * 11 2=2*1+0
Será importante
en criptografía E 78 = 2 * 3 * 13 mcd (385, 78) = 1
Curso de Seguridad Informática. Tema 5: Teoría de los Números. 13
© Jorge Ramió Aguirre Madrid (España) 2002
Inversos en un cuerpo (1)
Si mcd (a, n) ¹ 1
No existe ningún x que 0 < x < n / a * x mod n = 1
Sea: a = 3 y n = 6 Valores de i = {1, 2, 3, 4, 5}
3*1 mod 6 = 3 3*2 mod 6 = 0 3*3 mod 6 = 3
3*4 mod 6 = 0 3*5 mod 6 = 3
No existe el inverso para ningún resto del cuerpo.
D
Curso de Seguridad Informática. Tema 5: Teoría de los Números. 17
© Jorge Ramió Aguirre Madrid (España) 2002
Inversos aditivos y multiplicativos
(A+B) mod 4 (A*B) mod 4
B + 0 1 2 3 B * 0 1 2 3
A 0 0 1 2 3 A 0 0 0 0 0
1 1 2 3 0 0+0 = 0 1 0 1 2 3
2 2 3 0 1 1*1 = 1 2 0 2 0 2
Es trivial
3 3 0 1 2 3 0 3 2 1
En la operación suma siempre En la operación producto, de
existirá el inverso (0) para existir un inverso (1) éste es
cualquier resto del cuerpo. único y para ello debe haber
primalidad entre A y B.
(p-1)(q-1)
Curso de Seguridad Informática. Tema 5: Teoría de los Números. 24
© Jorge Ramió Aguirre Madrid (España) 2002
Función f(n) de Euler (n = p*q) (2)
(k1 * n + k2 * a) mod n = 1
Tabla de restos
x1 = 1 x2 = 0
4 ecuaciones en x
x3 = 3 x4 = 3
t
y1 = 7 y2 = 8
x = S (n/di)*yi*xi mod n
y3 = 3 y4 = 7 i=1
Generadores en Z13
Como p = 13 Þ p-1 = 12 = 22*3
Luego: q1 = 2 q2 = 3
Si se cumple g(p-1)/qi mod p ¹ 1 " qi g: 2,
entonces g será un generador de p
Sigue
OPERACIONES BIT
6 4 96 77 Sí
Luego, la complejidad de f (n) es exponencial.
Curso de Seguridad Informática. Tema 6: Teoría de la Complejidad. 6
© Jorge Ramió Aguirre Madrid (España) 2002
Tiempos de ejecución (1)
Incrementos de un Computacionalmente
orden de magnitud imposible
Entrada/109: Para n = 100 Þ O(n2) = 1002/109 = 10-5 seg
Curso de Seguridad Informática. Tema 6: Teoría de la Complejidad. 14
© Jorge Ramió Aguirre Madrid (España) 2002
Problemas de tipo NP
En criptografía nos interesan las funciones f(x) de un solo
sentido, es decir:
¤ Fácil calcular f(x) pero muy difícil calcular f-1(x)
salvo que conozcamos un secreto o trampa
Porque dan lugar a problemas tipo NP, polinomiales no
deterministas, computacionalmente difíciles de tratar.
Ø Problema de la mochila
Veremos
Ø Problema de la factorización cada
Ø Problema del logaritmo discreto uno de ellos
Ø Otros ...
Curso de Seguridad Informática. Tema 6: Teoría de la Complejidad. 15
© Jorge Ramió Aguirre Madrid (España) 2002
El problema de la mochila
• Es un problema de tipo NP en el
que el algoritmo debe realizar en
cada paso una selección iterativa
entre diferentes opciones.
Enunciado:
Dada una mochila de determinadas dimensiones de alto,
ancho y fondo, y un conjunto de elementos de distintos
tamaños menores que ella y de cualquier dimensión, ...
¿es posible llenar la mochila (completa) con distintos
elementos de ese conjunto sin repetir ninguno de ellos?
101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199
211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293
307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397
401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499
503 509 521 523 541 547 557 563 569 571 577 587 593 599
601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691
701 709 711 727 733 739 743 751 757 761 769 773 787 797
809 811 821 823 827 829 839 853 857 859 863 877 881 883 887
907 911 919 929 937 941 947 953 967 971 977 983 991 997
1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193
1201 1213 1217 1223 1229 1231 1237 1249 1259 1277 1279 1283 1289 1291 1297
1301 1303 1307 1319 1321 1327 1361 1367 1373 1381 1399
1409 1423 1427 1429 1433 1439 1447 1451 1453 1459 1471 1481 1483 1487 1489 1493 1499
1511 1523 1531 1543 1549 1553 1559 1567 1571 1579 1583 1597
1601 1607 1609 1613 1619 1621 1627 1637 1657 1663 1667 1669 1693 1667 1699
1709 1721 1723 1733 1741 1747 1753 1759 1777 1783 1787 1789
1801 1811 1823 1831 1847 1861 1867 1871 1873 1877 1879 1889
1901 1907 1913 1931 1933 1949 1951 1973 1979 1987 1993 1997 1999
ESCÍTALA
COLUMNAS VERNAM
FILAS N-GRÁMICA
DIGRÁMICA
LINEALES PROGRESIVOS
ALFABETO
ESTÁNDAR PLAYFAIR HILL
ENIGMA
ALFABETO ALFABETO ALFABETO
CÉSAR MIXTO ESTÁNDAR MIXTO
AFÍN
OTROS VIGENÈRE OTROS
A S I C I F R A B Se trata de un
A N C O N L A E S sistema de cifra
C I T A L A por transposición
De aquí proviene el
famoso bastón de
mando que vemos
El texto en claro es: en las Alcaldías
M = ASI CIFRABAN CON LA ESCITALA
El texto cifrado o criptograma será:
C = AAC SNI ICT COA INL FLA RA AE BS
Curso de Seguridad Informática. Tema 7: Criptosistemas Clásicos. 10
© Jorge Ramió Aguirre Madrid (España) 2002
El cifrador de Polybios
Es el cifrador por sustitución de caracteres más antiguo
que se conoce (siglo II a.d.C.) pero duplica el tamaño.
A B C D E 1 2 3 4 5
A A B C D E 1 A B C D E
B F G H IJ K 2 F G H IJ K
C L M N O P 3 L M N O P
D Q R S T U 4 Q R S T U
E V W X Y Z 5 V W X Y Z
Mi ABCDEFGHIJKLMNÑOPQRSTUVW XYZ
Ci DEFGHIJKLMNÑOPQRSTUVWXYZABC
Mi A B C D E F G H IJ K L M N Ñ O P Q R S T U V W X Y Z
Ci D E F G H I J K L M N Ñ O P Q R S T U V W X Y Z A B C
ESTIMADO/A LECTOR/A:
http://www.criptored.upm.es/paginas/software.htm#propio
LFSRs A5
Telefonía móvil; CLAVE PÚBLICA CLAVE SECRETA
tiempo real
Problema de la factorización
Problema de la mochila
origen destino
NUESTROS PROTAGONISTAS
Benito Adelaida
Claves: eB, nB, dB C = EeA(M) mod nA Claves: eA, nA, dA
Claves públicas
origen destino
Si ahora Benito realiza
la operación de cifra con
su clave privada dB en el
Benito cuerpo nB Adelaida será Adelaida
capaz de comprobar esa
Claves: eB, nB, dB cifra ya que posee (entre Claves: eA, nA, dA
otras) la clave pública de
eB, nB: públicas Benito. Comprueba así eA, nA: públicas
tanto la autenticidad del
dB: privada dA: privada
mensaje como del autor.
eB y dB son eA y dA son
inversas dentro inversas dentro
de un cuerpo Z C = EdB(M) mod nB de un cuerpo Z
Benito Adelaida
Claves: eB, nB, dB C = EdB(M) mod nB Claves: eA, nA, dA
Clave privada
Gestión de claves
Clave Secreta Clave Pública
Hay que memorizar Sólo es necesario
un número muy alto memorizar la clave
de claves: ® n2. privada del emisor.
Condiciones de la autenticidad:
a) El usuario A deberá protegerse ante mensajes
dirigidos a B que un tercer usuario desconocido C
introduce por éste. Es la suplantación de identidad o
problema de la autenticación del emisor.
b) El usuario A deberá protegerse ante mensajes
falsificados por B que asegura haberlos recibido
firmados por A. Es la falsificación de documento o
problema de la autenticación del mensaje.
Autenticación
Clave Secreta Clave Pública
Sólo será posible Al haber una clave
autenticar el mensaje pública y otra privada,
con una marca pero se podrá autenticar el
no al emisor. mensaje y al emisor.
Velocidad de cifra
Clave Secreta Clave Pública
La velocidad del La velocidad de cifra
cifrado es muy alta. es muy baja. Se usa
Es el algoritmo de para el intercambio de
cifra del mensaje. clave y la firma digital.
Cientos de En cuanto a la velocidad de Cientos de
M Bytes/seg cifra, los sistemas simétricos K Bytes/seg
son de 100 a 1.000 veces más
rápidos que los asimétricos.
Curso de Seguridad Informática. Tema 8: Introducción a los Criptosistemas Modernos. 30
© Jorge Ramió Aguirre Madrid (España) 2002
Resumen cifra simétrica v/s asimétrica
Cifrado Simétrico Cifrado Asimétrico
• Confidencialidad • Confidencialidad
• Autenticación parcial • Autenticación total
• Sin firma digital • Con firma digital
• Claves: • Claves:
– Longitud pequeña – Longitud grande
– Vida corta – Vida larga
– Número elevado – Número reducido
• Velocidad alta • Velocidad baja
Fin del Tema 8
Algoritmo S C S Algoritmo
Determinístico
Å Å Determinístico
Criptograma
MENSAJE M M MENSAJE
Rachas de 1s
Rachas de 0s Un 1 entre dos 0s
Un 0 entre dos 1s
Racha de 00s
Racha de 1111s Racha de 11s Un 00 entre dos 1s
Función de Autocorrelación:
– Autocorrelación AC(k) fuera de fase de una secuencia
Si de período T desplazada k bits a la izquierda:
AC(k) = (A - F) / T
Aciertos Þ bits iguales Fallos Þ bits diferentes
Ejemplo
Si 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 Si k = 1
A= 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 A=7; F=8
F= AC(1)= -1/15
Curso de Seguridad Informática. Tema 9: Cifrado en Flujo con Clave Secreta. 6
© Jorge Ramió Aguirre Madrid (España) 2002
Importancia de una AC(k) constante
Si 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0
• Facilidad de implementación:
– Debe ser fácil construir un generador de secuencia
cifrante con circuitos electrónicos y chips, con bajo
coste, alta velocidad, bajo consumo, un alto nivel de
integración, etc.
Curso de Seguridad Informática. Tema 9: Cifrado en Flujo con Clave Secreta. 8
© Jorge Ramió Aguirre Madrid (España) 2002
Primer postulado de Golomb G1
Postulado G1:
– Deberá existir igual número de ceros que de unos. Se
acepta como máximo una diferencia igual a la unidad.
S1 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0
En la secuencia S1 de 15 bits, hay 8 unos y 7
ceros, luego cumple con el postulado G1.
S2 1 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1
En la secuencia S2 de 16 bits, hay 7 unos y 9
ceros, luego no cumple con el postulado G1.
Curso de Seguridad Informática. Tema 9: Cifrado en Flujo con Clave Secreta. 9
© Jorge Ramió Aguirre Madrid (España) 2002
Significado del postulado G1
Si 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0
Si 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0
Si 0 1 1 1 0 1 0 0 Secuencia original
Si 0 1 1 1 0 1 0 0 No cumple con G3
Si 1 0 1 0 11 0 0 Sí cumple con G3
1
XOR
1 Observe que
0
OR primero se
0 0 transmite
AND NOT S4S3S2S1
Si
S101 S012 S13 S14 1
S1 S2 S3 S4
Semilla: S1S2S3S4 = 0111
Continuando la secuencia Si = 1110 1100 1010 0001
Tmáx = 2n = 24 = 16 (Secuencia de De Bruijn)
Curso de Seguridad Informática. Tema 9: Cifrado en Flujo con Clave Secreta. 21
© Jorge Ramió Aguirre Madrid (España) 2002
Generadores lineales LFSR (1)
a(t) = C1a(t-1) Å C2a(t-2) Å C3a(t-3) Å ... Å Cna(t-n)
Ci = {1,0} Þ conexión/no conexión celda Cn = 1
Función única: XOR Tmáx = 2n - 1
Polinomio asociado:
f(x) = Cnxn + Cn-1xn-1 + .... + C2x2 + C1x + 1
XOR
Generador
C1 C2 C3 C4 LFSR de 4
etapas/celdas
S1 S2 S3 S4 Si
Curso de Seguridad Informática. Tema 9: Cifrado en Flujo con Clave Secreta. 22
© Jorge Ramió Aguirre Madrid (España) 2002
Generadores lineales LFSR (2)
En función del polinomio asociado tendremos:
Å Si asignamos valores
C1 C2 C3 C4=1 de esos 2*n = 8 bits
S1 S2 S3 S4 Si S1S2S3S4S5S6S7S8
seremos capaces de
S5 = C1•S1Å C2•S2Å C3•S3Å C4•S4 resolver este sistema
S6 = C1•S5Å C2•S1Å C3•S2Å C4•S3 Primero se transmite
S7 = C1•S6Å C2•S5Å C3•S1Å C4•S2 S4S3S2S1 (semilla) y
S8 = C1•S7Å C2•S6Å C3•S5Å C4•S1 luego bits S5S6S7S8.
C3 = 0 C4 = 1
0 = C1•0 Å C2•0 Å C3•1 Å C4•0
Curso de Seguridad Informática. Tema 9: Cifrado en Flujo con Clave Secreta. 35
© Jorge Ramió Aguirre Madrid (España) 2002
Ejemplo de ataque Berlekamp-Massey (3)
CONCLUSIONES:
• Como se conoce la configuración del generador
LFSR, y Si es una m-secuencia de período 2n - 1,
entonces por el conjunto de n celdas pasarán todos
los restos del campo de Galois de 2n menos la
cadena de n ceros que está prohibida.
• Para el ejemplo, esto quiere decir que cualquier
grupo de 4 dígitos correlativos de los 8 conocidos
permite generar la secuencia máxima.
• La solución es aumentar la complejidad lineal del
generador por ejemplo conectando varios LFRs.
Curso de Seguridad Informática. Tema 9: Cifrado en Flujo con Clave Secreta. 36
© Jorge Ramió Aguirre Madrid (España) 2002
Algoritmos de cifrado en flujo
3 LFSR con R1
C1: bit
m-secuencia
Å de reloj
21 C2 0
Si Å R2
C2: bit
n1 = 19 Å de reloj
n2 = 22 22 C3 7 0
n3 = 23 R3
C3: bit
Clave = 64 bits Å de reloj
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 4
© Jorge Ramió Aguirre Madrid (España) 2002
Ejemplo básico de cifra tipo Feistel (2)
Si: +1 mod 27
M = STAR WARS, LA MISIÓN CONTINÚA Pi: Õ3241
M1 = STAR WARS LAMI SION CONT INUA
S1 = TUBS WARS MBNJ SION DPÑU INUA Primera
P1 = BUST WARS NBJM SION ÑPUD INUA vuelta
Skipjack 64 80 32
RIJNDAEL 128 128 o más flexible
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 6
© Jorge Ramió Aguirre Madrid (España) 2002
Características de estos algoritmos
• Lucifer: algoritmo original tipo Feistel que dará lugar al DES.
DES: algoritmo tipo Feistel que se convirtió en un estándar de
hecho durante casi treinta años, hoy en día vulnerable.
• Loki: algoritmo australiano similar al DES, tipo Feistel.
• RC2: algoritmo propuesto por Ron Rivest y que se incluye en
los navegadores desde 1999 con una clave de 40 bits.
• CAST: algoritmo tipo Feistel que se ofrece como cifrador por
defecto en últimas versiones de PGP junto a IDEA y T-DES.
• Blowfish: algoritmo tipo Feistel propuesto por Bruce Schneier.
• IDEA: algoritmo seguro y muy usado en correo electrónico.
• Skipjack: propuesta de nuevo estándar en USA a finales de los
90 para comunicaciones oficiales (tiene puerta trasera).
• RIJNDAEL: nuevo estándar mundial desde finales de 2001.
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 7
© Jorge Ramió Aguirre Madrid (España) 2002
Otros algoritmos de cifra
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 8
© Jorge Ramió Aguirre Madrid (España) 2002
Características de estos algoritmos
• Khufu: algoritmo propuesto por Ralph Merkle con una clave
generada con un sistema de “cajas” S.
• Khafre: algoritmo propuesto por Ralph Merkle en el que la
clave ya no depende de las cajas S.
• Gost: algoritmo similar al DES con cajas S secretas propuesto
en la Unión Soviética.
• RC5: algoritmo propuesto por Ron Rivest; realiza operaciones
or exclusivo, suma modular y desplazamiento de bits.
• SAFER 64: algoritmo propuesto por James Massey.
• Akelarre: algoritmo español propuesto en 1996 por el CSIC,
Consejo Superior de Investigaciones Científicas.
• FEAL: algoritmo propuesto en Japón.
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 9
© Jorge Ramió Aguirre Madrid (España) 2002
Algunas tasas de cifra comparativas
Velocidad de cifra de algoritmos en un PC 486 a 33 MHz
Algoritmo Kbytes/seg Algoritmo Kbytes/seg
DES 35 Triple DES 12
IDEA 53 FEAL (32 v) 91
Khufu (16 v) 221 Khufu (32 v) 115
RC5 (8 v) 127 RC5 (16 v) 65
SAFER (6 v) 81 SAFER (12 v) 41
Blowfish (12 v) 182 Blowfish (20 v) 110
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 11
© Jorge Ramió Aguirre Madrid (España) 2002
Especificaciones del algoritmo DES
Especificaciones del concurso
• El nivel de seguridad computacional debe ser alto.
• El algoritmo debe ser fácil de entender y deberá estar
especificado en todos sus detalles.
• La seguridad del sistema no debe verse afectada por la
publicación y divulgación del algoritmo.
• Debe estar disponible para cualquier usuario.
• Deberá poder usarse en diferentes aplicaciones.
• Fabricación con dispositivos electrónicos de bajo costo.
• Se debe poder usar como validación.
• Debe ser exportable.
No se cumplen en 1973 pero sí en 1974, aunque ...
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 12
© Jorge Ramió Aguirre Madrid (España) 2002
El papel de la NSA en el DES
La NSA impone una limitación en la longitud de la clave:
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 13
© Jorge Ramió Aguirre Madrid (España) 2002
¿Por qué esta reducción?
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 15
© Jorge Ramió Aguirre Madrid (España) 2002
Visión general del DES
v Cifrador de bloque
v Tipo Feistel
v Longitud de clave de 56 bits
v Nº de vueltas: 16
v Cifra del bloque
b central:
técnicas de sustituciones y
permutaciones
En el descifrado se aplican claves y
desplazamientos en sentido inverso
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 16
© Jorge Ramió Aguirre Madrid (España) 2002
Permutación inicial del DES: tabla IP
Tabla IP sobre bloque de texto
Sin interés criptográfico
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 17
© Jorge Ramió Aguirre Madrid (España) 2002
Bloques izquierdo y derecho de texto
58 50 42 34 26 18 10 2 L0 = 58 50 42 34 26 18 10 02 60 52 44 36
60 52 44 36 28 20 12 4 28 20 12 04 62 54 46 38 30 22 14 06
62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 08
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
R0 = 57 49 41 33 25 17 09 01 59 51 43 35
27 19 11 03 61 53 45 37 29 21 13 05
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 07
63 55 47 39 31 23 15 7
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 20
© Jorge Ramió Aguirre Madrid (España) 2002
Módulo de cifra en DES
16 bits repetidos
Esquema de la
función de cifra
f en cada ciclo
Columnas 1ª y
2ª repetidas
En las cajas S
se logra la
fortaleza del
algoritmo. Es
una función
unidireccional
y no lineal.
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 21
© Jorge Ramió Aguirre Madrid (España) 2002
Operación de las cajas S en DES
Permutación con expansión a 48 bits (Tabla E)
ki (48 bits)
1 6 7 12 13 18 19 24 25 30 31 36 37 42 43 48
S1 S2 S3 S4 S5 S6 S7 S8
1 4 5 8 9 12 13 16 17 20 21 24 25 28 29 32
F 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
I 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
L
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
A
S 3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
COLUM NAS
S2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
F 0 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
I 1 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
L
A 2 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
S 3 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 23
© Jorge Ramió Aguirre Madrid (España) 2002
Valores de las cajas S del DES (2)
COLUM NAS
S3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 5
F 0 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
I 1 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
L
2 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
A
S 3 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
COLUM NAS
S4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
F 0 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
I 1 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
L
A 2 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
S 3 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 24
© Jorge Ramió Aguirre Madrid (España) 2002
Valores de las cajas S del DES (3)
COLUM NAS
S5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 5
F 0 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
I 1 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
L
2 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
A
S 3 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
COLUM NAS
S6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
F 0 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
I 1 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
L
A 2 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
S 3 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 25
© Jorge Ramió Aguirre Madrid (España) 2002
Valores de las cajas S del DES (4)
COLUM NAS
S7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 5
F 0 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
I 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
L
2 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
A
S 3 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
COLUM NAS
S8 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
F 0 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
I 1 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
L
A 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
S 3 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 26
© Jorge Ramió Aguirre Madrid (España) 2002
Ejemplo de operación de cajas S del DES
Ejemplo:
Sean los bits 7 al 12 los siguientes: 101100
Los bits corresponderán entonces a la entrada de la caja S2
Para seleccionar la fila tomamos los bits extremos: 102 = 210 = 2
Para seleccionar la columna tomamos los bits centrales: 01102 = 610 = 6
La caja S2 indica una salida igual a 1310 = 11012
explicación
Entrada: 101100
Salida: 1101
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 27
© Jorge Ramió Aguirre Madrid (España) 2002
Cálculo de subclaves en el DES (PC-1)
28 bits 28 bits Tabla PC-1 (56 bits)
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
48 bits
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
48 bits 44 49 39 56 34 53
46 42 50 36 29 32
Algunas implementaciones:
– Cryptech CRY12C102 (22.5 Mbits/s)
– Pijnenburg PCC100 (20 Mbits/s)
– “Supercrypt” de Computer Elektronic
Infosys (100 Mbits/s)
• Versiones software disponibles via ftp:
– kampi.hut.fi:alo/des-dist.tar.z
– ftp.funet.fi:pub/unix/security/destoo.tar.z
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 32
© Jorge Ramió Aguirre Madrid (España) 2002
Modos de cifra: modo ECB
NOTA: estos modos de cifra se usan en todos los cifradores.
MODO ECB
Electronic CodeBook: cifra cada bloque con la clave k de
forma independiente. Por lo tanto, el resultado es como si se
codificase mediante un gran libro electrónico de códigos. .
F Recuerde que codificar no es lo mismo que cifrar.
Debilidades:
L Se podría reconstruir ese libro electrónico sin necesidad
de conocer la clave.
L Aparece el problema denominado de comienzos y finales
fijos que permiten un tipo de ataque sencillo.
L Se ataca a través de la repetición de bloques similares.
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 33
© Jorge Ramió Aguirre Madrid (España) 2002
Características del modo ECB en el DES
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 34
© Jorge Ramió Aguirre Madrid (España) 2002
Esquema de cifra modo CBC en el DES
Cipher Block Chaining Vector IV = I0
• Se pueden cifrar
unidades de datos más
pequeñas que bloques,
por lo general un byte.
• Se usa un registro de
desplazamiento RD de
64 bits como vector
inicial IV.
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 37
© Jorge Ramió Aguirre Madrid (España) 2002
Operaciones de cifra modo CFB en el DES
Cifrado Descifrado
Se suma XOR cada byte del Se cifra el registro RD.
texto claro con bytes resultado Se obtienen de esta forma
de la cifra de RD y la clave K. los elementos de Ci-d.
El byte Ci se envía al registro; Se suma XOR los Ci-d con
se desplaza 8 bits a la izquierda los Ci del criptograma para
hasta formar otro RD y se repite obtener Pi.
el proceso de cifra. Se realimenta Ci al registro
RD y se repite el proceso.
CARACTERÍSTICAS:
Evita el ataque por repetición de bloque; enmascara el mensaje como
en cifra en flujo, el espacio de claves es igual a 64 bits; la propagación
de un error se limita a un bloque.
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 38
© Jorge Ramió Aguirre Madrid (España) 2002
Esquema de cifra modo OFB en el DES
El byte se va desplazando por el registro
Output Feedback
Registro Desplazamiento (64 bits)
Cifra por realimentación
de bloques de salida
La realimentación de la
señal se realiza antes K DES
de la operación XOR.
Bits menos
El DES, la clave y el significativos Ci-1
Registro RD actúan
como un generador de
Byte
secuencia cifrante. Mensaje Bi Å Ci
Si la cifra se realiza bit a bit, OFB se convierte en cifrador de flujo.
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 39
© Jorge Ramió Aguirre Madrid (España) 2002
Características del modo OFB en el DES
q Evita el ataque por repetición de bloque.
q Produce un enmascaramiento del mensaje similar al de
un cifrador de flujo.
q El espacio de claves es igual a 64 bits.
q La propagación de un error afecta sólo a un byte, el
que se realimenta en el registro de desplazamiento.
q Las operaciones de cifrado y descifrado son iguales.
A pesar de las propiedades interesantes de los
últimos modos, el más utilizado en los sistemas
de cifra de diversos protocolos es el CBC.
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 40
© Jorge Ramió Aguirre Madrid (España) 2002
¿Es el DES un grupo? (1)
Si un sistema forma un grupo, entonces cifrar un mensaje M
con una clave k1 y luego el resultado con una clave k2, es lo
mismo que cifrar el mensaje con una única clave k3.
Por ejemplo, el cifrador de Vigenère es un grupo como se
demuestra a continuación. Sea k1 = PACO y k2 = CINE y el
mensaje a cifrar M = ESTO ES UN GRUPO.
M1 = ESTO ESUN GRUP O M2 = TSVD TSWB VRWE E
k1 = PACO PACO PACO P k2 = CINE CINE CINE C
C1 = TSVD TSWB VRWE E C2 = VAIH VAJF XZJI G
M C’ C
DES DES
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 43
© Jorge Ramió Aguirre Madrid (España) 2002
Ataque por encuentro a medio camino
k1 k2 k1 y k2 son
claves n bits
Y
M DES DES C
a) Se descripta el criptograma C por fuerza bruta usando las 2n claves
posibles y realizando entonces 2n cálculos. Se obtiene así Y.
b) Con los “textos intermedios” Y se forma una tabla ordenada de
textos cifrados con sus correspondientes valores k2.
c) Se cifran los textos en claro M elegidos con todas las claves k1 y se
comparan con Y, realizando un máximo de 2n cálculos.
d) Una de las claves será la verdadera y se ha realizado un número
menor que 2n + 2n = 2n+1 cálculos. Luego la clave real es igual a
2n+1.
Este ataque se conoce con el nombre de meet-in-the-middle.
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 44
© Jorge Ramió Aguirre Madrid (España) 2002
Cifrado múltiple: triple DES
k1 y k2 son
k1 k2 k1 claves n bits
M C
E (DES) D (DES) E (DES)
M C
E (DES) D (DES) E (DES)
Aunque el algoritmo DES haya sufrido diversos ataques y no se
haya vuelto a certificar por el NIST como estándar de cifrado, el
Triple DES sí tiene una gran seguridad debido al tamaño de su
clave de 112 bits efectivos y sigue siendo muy válido en el año
2002. De hecho, es el algoritmo propuesto en el protocolo SET y
se encuentra, entre otras aplicaciones, en el programa PGP.
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 46
© Jorge Ramió Aguirre Madrid (España) 2002
International Data Encryption Algorithm IDEA
Historia del IDEA
< En 1990 Xuejia Lai y James Massey proponen el PES,
Proposed Encryption Standard.
< En 1991 -debido a los avances de Biham y Shamir en el
criptoanálisis diferencial- los autores proponen el IPES,
Improved Proposed Encryption Standard.
< En 1992 los autores proponen finalmente el algoritmo
IDEA, International Data Encryption Algorithm.
< En 1999 el algoritmo IDEA, mucho más seguro que el
DES y sus versiones, se comienza a usar ampliamente en
el sistema de correo electrónico seguro PGP.
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 47
© Jorge Ramió Aguirre Madrid (España) 2002
Estructura y esquema de IDEA
• Cifra bloques de 64 bits
en 8 vueltas
• Divide la entrada M en
cuatro bloques de 16 bits
• Un algoritmo genera 52
subclaves a partir de una
clave de 128 bits
• Usa 6 claves por vuelta
• Hay una transformación
Todas sus operaciones
final con 4 claves para se realizan dentro de
invertir operación inicial un cuerpo finito
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 48
© Jorge Ramió Aguirre Madrid (España) 2002
Operaciones matemáticas en IDEA
Operaciones básicas
XOR Es primo y se
asegura el inverso
multiplicativo
Suma módulo 216 (mod 65.536)
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 49
© Jorge Ramió Aguirre Madrid (España) 2002
Ejemplo de operaciones en IDEA (1)
Ejemplo dentro de un grupo n pequeño
Como 2n + 1 debe ser primo, sea n = 2 ya que 22 = 4 y 22 + 1 = 5
X Y X+Y XÄ Y XÅY n=2
0 00 0 00 0 00 1 01 0 00
0 00 1 01 1 01 0 00 1 01 dos bits
0 00 2 10 2 10 3 11 2 10
0 00 3 11 3 11 2 10 3 11
1
1
01
01
0
1
00
01
1
2
01
10
0
1
00
01
1
0
01
00
Veamos cómo
1
1
01
01
2
3
10
11
3
0
11
00
2
3
10
11
3
2
11
10
se opera con la
2 10 0 00 2 10 3 11 2 10 multiplicación.
2
2
10
10
1
2
01
10
3
0
11
00
2
0
10
00
3
0
11
00 La suma y el or
2
3
10
11
3
0
11
00
1
3
01
11
1
2
01
10
1
3
01
11
exclusivo son
3 11 1 01 0 00 3 11 2 10 operaciones
3 11 2 10 1 01 1 01 1 01
3 11 3 11 2 10 0 00 0 00 similares.
Operaciones: + mod 2n (mod 4), Ä mod 2n+1 (mod 5), XOR (mod 2)
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 50
© Jorge Ramió Aguirre Madrid (España) 2002
Ejemplo de operaciones en IDEA (2)
X Y X+Y XÄ Y XÅY
0 00 0 00 0 00 1 01 0 00 Recuerde que 0
0 00 1 01 1 01 0 00 1 01 es igual a 2n = 4
0 00 2 10 2 10 3 11 2 10
0 00 3 11 3 11 2 10 3 11 por lo que:
1 01 0 00 1 01 0 00 1 01
1 01 1 01 2 10 1 01 0 00
0Ä0 = 22 x 22
= 22 x21 = 4 10
1 0Ä1 01 3 11 2 10 3 11 = 16 mod 5
1 01 3 11 0 00 3 11 2 10
2
= 4 mod
10 0
5 00 2 10 3 11 2 10
=1
2 = 4 = 10
10 01 3 11 2 10 3 11
2 10 2 10 0 00 0 00 0 00
(por 10
definición) 10Ä2 =0122 x 21 = 8 01
2 3 11 1 01 0Ä3 = 22 x 3 = 12
3 11 0 00 3 118 mod
=00 2 5 10 3 11
3 11 1 01 0 3 11 2 10 = 12 mod 5
3 11 2 10 1 =013 1 01 1 01 =2
3 11 3 11 2 10 0 00 0 00
Operaciones: + mod 2n (mod 4), Ä mod 2n+1 (mod 5), XOR (mod 2)
Los demás cálculos con los diferentes valores de X e Y son todos similares
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 51
© Jorge Ramió Aguirre Madrid (España) 2002
Detalles del algoritmo IDEA
Operación cifrado
Operaciones inversas
MA
al comienzo y al final
del algoritmo. Esto
permite usar el mismo
algoritmo para cifrar
que para descifrar.
Bloque principal
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 52
© Jorge Ramió Aguirre Madrid (España) 2002
Bloque principal de IDEA
Estas tres operaciones provocan confusión y no
cumplen las leyes distributiva ni asociativa.
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 53
© Jorge Ramió Aguirre Madrid (España) 2002
Generación de claves en IDEA
A partir de una entrada de Se produce un desplazamiento de 25
128 bits, se generan las 52 bits a la izquierda en cada una de las
subclaves de cifrado. 7 fases de generación de claves.
26
Con los
Los 64 primeros
últimos 128 bits se
bits de generan 8
la fase 7 subclaves
no se de 16 bits
usan. cada una.
23 86
64 bits de últimas claves
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 54
© Jorge Ramió Aguirre Madrid (España) 2002
Desplazamientos de la clave en IDEA
En cada operación sobre la clave de 128 bits, se obtienen 8
claves de 16 bits de las que sólo se usan 6 en cada vuelta.
Clave Principal k = 128 bits
001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032
033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064
065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096
097 098 099 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 55
© Jorge Ramió Aguirre Madrid (España) 2002
Bits de la clave IDEA en cada en vuelta
Primera vuelta: k1k2k3k4k5k6 B[1…96]
Segunda vuelta: k7k8k9k10k11k12 B[97…128; 26…89]
Tercera vuelta: k13k14k15k16k17k18 B[90…128; 1…25; 51…82]
Cuarta vuelta: k19k20k21k22k23k24 B[83…128; 1…50]
Quinta vuelta: k25k26k27k28k29k30 B[76…128; 1…43]
Sexta vuelta: k31k32k33k34k35k36 B[44…75; 101…128; 1…36]
Séptima vuelta: k37k38k39k40k41k42 B[37…100; 126…128; 1…29]
Octava vuelta: k43k44k45k46k47k48 B[30…125]
Transformación: k49k50k51k52 B[23…86]
Las primeras claves de cada vuelta k1, k7, k13, k19, k25, k31, k37 y
k43 usan un conjunto diferente de bits. Excepto en las vueltas
primera y octava, los 96 bits de subclave usados en cada vuelta,
no son contiguos. Debido al desplazamiento en cada fase de 25
bits a la izquierda, hace muy difícil el ataque a la clave.
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 56
© Jorge Ramió Aguirre Madrid (España) 2002
Descifrado con IDEA
El algoritmo IDEA, al igual que el DES, permite cifrar y
descifrar con la misma estructura. Como las operaciones se
hacen dentro de un cuerpo finito, en este caso las claves se
toman como los inversos de las operaciones XOR, suma
mod 216 y producto mod 216+1, dependiendo de las
operaciones realizadas en la fase de cifrado.
INVERSOS
Las operaciones
se hacen ahora
hacia arriba
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 59
© Jorge Ramió Aguirre Madrid (España) 2002
Uso de claves inversas en descifrado IDEA
Ultimas 6 claves
de descifrado
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 60
© Jorge Ramió Aguirre Madrid (España) 2002
Fortaleza del algoritmo IDEA
· IDEA se muestra inmune ante un criptoanálisis diferencial. Sus
autores conocían esta debilidad del DES y lo hicieron resistente.
· Joan Daemen descubre en 1992 una clase de claves débiles. La
siguiente clave k = 0000,0000,0x00,0000,0000,000x,xxxx,x000
en hexadecimal es débil, en el sentido de que un criptoanalista
podría identificarla en un ataque con texto en claro elegido. Las
posiciones x pueden ser cualquier número en hexadecimal.
· La probabilidad de que se use este tipo de claves es sólo de uno
en 296 y se puede, además, eliminar por diseño.
· A la fecha, año 2002, no se conoce todavía ningún sistema o
algoritmo de ataque que haya criptoanalizado IDEA.
· Joan Daemen y Vincent Rijmen crearán en 1997 el RIJNDAEL,
nuevo algoritmo estándar del NIST desde finales de 2001.
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 61
© Jorge Ramió Aguirre Madrid (España) 2002
AES, nuevo estándar en cifra (1)
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 62
© Jorge Ramió Aguirre Madrid (España) 2002
AES, nuevo estándar en cifra (2)
AES: Advanced Encryption Standard
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 65
© Jorge Ramió Aguirre Madrid (España) 2002
Ejemplo de suma en GF(28)
Vamos a sumar los valores hexadecimales 57 y 83:
A = 5716 = 0101 01112 B = 8316 = 1000 00112
que expresados en polinomios dentro de GF(28) serán:
A = 0101 01112 = x6 + x4 + x2 + x + 1
B = 1000 00112 = x7 + x + 1
Sumando: A+B = (x6 + x4 + x2 + x + 1) + (x7 + x + 1) mod 2
A+B = (x7 + x6 + x4 + x2 + 2x + 2) mod 2
A+B = x7 + x6 + x4 + x2 = 1101 0100 = D416
Y lo mismo se obtiene con la suma Or exclusivo:
0101 0111 Å 1000 0011 = 1101 0100 = D416
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 66
© Jorge Ramió Aguirre Madrid (España) 2002
Ejemplo de producto en GF(28) (1)
Vamos a multiplicar los valores hexadecimales 57 y 83:
A = 5716 = 0101 01112 B = 8316 = 1000 00112
que expresados en polinomios dentro de GF(28) serán:
A = 0101 01112 = x6 + x4 + x2 + x + 1
B = 1000 00112 = x7 + x + 1
Sea p(x) = x8 + x4 + x3 + x + 1 Þ x8 = x4 + x3 + x + 1
A*B = (x6 + x4 + x2 + x + 1)*(x7 + x + 1) mod 2
A*B = x13 + x11 + x9 + x8 + 2x7 + x6 + x5 + x4 + x3 + 2x2 + 2x +1
A*B = x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1
Este resultado hay que reducirlo por p(x) = x8 + x4 + x3 + x + 1
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 67
© Jorge Ramió Aguirre Madrid (España) 2002
Ejemplo de producto en GF(28) (2)
Están fuera del cuerpo de 8 bits p(x): x8 = x4 + x3 + x + 1
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 68
© Jorge Ramió Aguirre Madrid (España) 2002
Ejemplo de producto en GF(28) (3)
Están fuera del cuerpo de 8 bits p(x): x8 = x4 + x3 + x + 1
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 69
© Jorge Ramió Aguirre Madrid (España) 2002
Ejemplo de producto en GF(28) (4)
x13 = x6 + x3 + x2 + 1 x11 = x7 + x6 + x4 + x3
x9 = x5 + x4 + x2 + x x8 = x4 + x3 + x + 1
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 70
© Jorge Ramió Aguirre Madrid (España) 2002
Transformaciones (capas) de RIJNDAEL
§ Hay tres transformaciones distintas llamadas capas en
las que se tratan los bits. Estas constan de:
§ Capa de Mezcla Lineal: en ella se busca la difusión de
los bits.
§ Capa No Lineal: se trata de una zona similar a las cajas
S del DES.
§ Capa Clave: operaciones con una función Xor de la
subclave y la información de esta etapa intermedia.
§ Las transformaciones realizadas en cada paso del
algoritmo se denominan estados; se representa por un
array de 4 filas. Fin del Tema 10
Curso de Seguridad Informática. Tema 10: Cifrado en Bloque con Clave Secreta. 71
© Jorge Ramió Aguirre Madrid (España) 2002
Tema 11
Cifrado con Mochilas de Clave Pública
S Si*Vi = T
i
Si se cumple esta relación, la mochila tiene solución.
Curso de Seguridad Informática. Tema 11: Cifrado con Mochilas de Clave Pública. 3
© Jorge Ramió Aguirre Madrid (España) 2002
Un ejemplo del problema de la mochila (1)
Tenemos la mochila S = {20, 5, 7, 36, 13, 2} con m = 6 y el
valor T = 35. Se pide encontrar una solución, si es que ésta
existe, en una única vuelta.
Curso de Seguridad Informática. Tema 11: Cifrado con Mochilas de Clave Pública. 4
© Jorge Ramió Aguirre Madrid (España) 2002
Un ejemplo del problema de la mochila (2)
S = {S1, S2, S3, S4, S5, S6} = {20, 5, 7, 36, 13, 2} T = 35
Sk > S Sj
es mayor que la suma de los j=1
Curso de Seguridad Informática. Tema 11: Cifrado con Mochilas de Clave Pública. 7
© Jorge Ramió Aguirre Madrid (España) 2002
Operación de cifra con mochila simple
Se representa la información en binario y se pasan los bits
por la mochila. Los bits 1s incluyen en la suma el elemento
al que apuntan y los bits 0s no.
Con la mochila S = {2, 4, 10, 19, 40} de m = 5 elementos
cifraremos el mensaje M = ADIOS.
SOLUCIÓN: Usando código ASCII/ANSI: A = 01000001;
D = 01000100; I = 01001001; O = 01001111; S = 01010011
M = 01000 00101 00010 00100 10010 10011 11010 10011
C = (4), (10+40), (19), (10), (2+19), (2+19+40), (2+4+19), (2+19+40)
C = 4, 50, 19, 10, 21, 61, 25, 61
Curso de Seguridad Informática. Tema 11: Cifrado con Mochilas de Clave Pública. 8
© Jorge Ramió Aguirre Madrid (España) 2002
Descifrado con mochila simple
C = 4, 50, 19, 10, 21, 61, 25, 61 S = {2, 4, 10, 19, 40}
La operación de descifrado es elemental: pasamos por la
mochila los valores de C, encontramos el vector Vi y por
último agrupamos el resultado en grupos de 8 bits. En este
caso 4 = 4 Þ Vi = 01000, 50 = 40 + 10 Þ Vi = 00101, etc.
Curso de Seguridad Informática. Tema 11: Cifrado con Mochilas de Clave Pública. 11
© Jorge Ramió Aguirre Madrid (España) 2002
Diseño mochila de Merkle y Hellman (2)
5. Se calcula el inverso de w en el cuerpo m. w-1 = inv(w,m)
CIFRADO: DESCIFRADO:
C=S*M M = w-1 * C mod m
como S = w * S’ mod m Entonces obtenemos:
C = w * S’* M mod m S’* M
Curso de Seguridad Informática. Tema 11: Cifrado con Mochilas de Clave Pública. 12
© Jorge Ramió Aguirre Madrid (España) 2002
Cifrado mochila de Merkle y Hellman (1)
Vamos a cifrar el mensaje M = Sol usando la mochila simple y
supercreciente S’ = {3, 5, 12, 21}.
1. Elección de m: m ³ 2*S4 ³ 2*21 m = 45
2. Elección de w: mcd(w, m) = 1 w = 32 (w-1 = 38)
3. Mochila S: S = w * S’ mod m
S1 = 32 * 3 mod 45 = 96 mod 45 = 6
S2 = 32 * 5 mod 45 = 160 mod 45 = 25
S3 = 32 * 12 mod 45 = 384 mod 45 = 24
S4 = 32 * 21 mod 45 = 672 mod 45 = 42
Clave pública: S = {6,25,24,42} Clave privada: m=45, w-1=38
Curso de Seguridad Informática. Tema 11: Cifrado con Mochilas de Clave Pública. 13
© Jorge Ramió Aguirre Madrid (España) 2002
Cifrado mochila de Merkle y Hellman (2)
Curso de Seguridad Informática. Tema 11: Cifrado con Mochilas de Clave Pública. 14
© Jorge Ramió Aguirre Madrid (España) 2002
Descifrado mochila de Merkle y Hellman
Clave pública: S = {6,25,24,42} Clave privada: m = 45, w-1 = 38
Curso de Seguridad Informática. Tema 11: Cifrado con Mochilas de Clave Pública. 22
© Jorge Ramió Aguirre Madrid (España) 2002
Pasos del ataque de Shamir y Zippel (2)
4. Encontrado el candidato para S1’se calcula:
w = (S1/S1’) mod m = [S1* inv(S1’, m)] mod m
Esto implica una nueva condición: mcd (S1’, m) = 1
5. Conocido w encontramos w-1 = inv(w, m) y así calculamos
todos los elementos de la mochila Si’ = Si * w-1 mod m que
debería ser del tipo supercreciente.
6. Si no se genera una mochila supercreciente, se elige el
siguiente valor más pequeño del conjunto CM y así hasta
recorrer todos sus valores. Si con este conjunto CM no se
obtiene una mochila simple, se repite el punto 2 tomando
ahora valores en el rango 2m+i con i = 2, 3, ...
Curso de Seguridad Informática. Tema 11: Cifrado con Mochilas de Clave Pública. 23
© Jorge Ramió Aguirre Madrid (España) 2002
Usos de protección con mochilas
Existen varios algoritmos propuestos como sistemas de cifra
usando el problema de la mochila: el de Graham-Shamir,
Chor-Rivest, etc.
No obstante todos han sucumbido a los criptoanálisis y en la
actualidad en el único entorno que se usan es en la protección
de diversos programas de aplicación, en forma de hardware
que se conecta en la salida paralela del computador para
descifrar el código ejecutable de esa aplicación dejando, sin
embargo, activa la salida a impresora. De esta manera sólo en
aquel sistema con la mochila instalada se puede ejecutar el
programa. Fin del Tema 11
Curso de Seguridad Informática. Tema 11: Cifrado con Mochilas de Clave Pública. 24
© Jorge Ramió Aguirre Madrid (España) 2002
Tema 12
Cifrado Exponencial
N C
¿Algo más óptimo?
1ª opción: usar reducibilidad Exponenciación rápida
Ejemplo
Características
o Se elige un grupo multiplicativo Zp*, p es primo grande.
o Del grupo p se elige una raíz a, generador del grupo.
o Cada usuario elige un número aleatorio l dentro de p.
o Esta será la clave privada. Para descubrir la clave privada
el atacante deberá enfrentarse
o Cada usuario calcula al mod p. al Problema del Logaritmo
o Junto con p es la clave pública. Discreto para un valor p alto.
El mensaje M se transforma en
números y éstos se dividen en bloques
de de g-1 dígitos, siendo g el número
de dígitos del módulo de trabajo: el
valor n para RSA y p para ElGamal.
Ejemplo
Curso de Seguridad Informática. Tema 12: Cifrado Exponencial. 24
© Jorge Ramió Aguirre Madrid (España) 2002
Ejemplo de elección del bloque con RSA
Se representará el mensaje en su valor ANSI decimal.
n = p*q = 89*127 = 11.303 Þ bloques de cuatro dígitos
f(n) = 11.088; e = 25; d = inv (25, 11.088) = 10.201
M = Olé = 079 108 233 Þ M = 0791 0823 3
Se recupera el mensaje agrupando en
bloques de 4 dígitos excepto el último
CIFRADO DESCIFRADO
C1 = 79125 mod 11.303 = 7.853 M1 = 7.85310201 mod 11.303 = 0791
C2 = 82325 mod 11.303 = 2.460 M2 = 2.46010201 mod 11.303 = 0823
C3 = 325 mod 11.303 = 6.970 M3 = 6.97010201 mod 11.303 = 3
Características
v Se elige un grupo multiplicativo Zp*, p es un primo grande.
v Cada usuario elige una clave e, que sea primo relativo con el
grupo f(p) = p-1 y luego calcula d = inv (e, f(p)].
v La clave secreta serán los valores e y d.
CIFRADO DESCIFRADO
C = Me mod p M = Cd mod p
Ejemplo
Curso de Seguridad Informática. Tema 12: Cifrado Exponencial. 27
© Jorge Ramió Aguirre Madrid (España) 2002
Operación de cifra Pohlig y Hellman
A cifra un mensaje M que envía a B
p = 263 Þ f(p) = 262; e = 15 Þ d = inv(15,262) = 35
Sea M = Adiós = 65 100 105 243 115
Como se usa el código ANSI, podremos cifrar en bloques
de un carácter pues el módulo p es algo mayor que 256.
Operación Cifrado:
C = Me mod p = 6515 mod 263; 10015 mod 263;
10515 mod 263; 24315 mod 263; 11515 mod 263
C = 245; 143; 179; 86; 101
Curso de Seguridad Informática. Tema 12: Cifrado Exponencial. 28
© Jorge Ramió Aguirre Madrid (España) 2002
Operación de descifrado Pohlig y Hellman
Operación Descifrado:
M = Cd mod p = 24535 mod 263; 14335 mod 263;
17935 mod 263; 8635 mod 263; 10135 mod 263
M = 065; 100; 105; 243; 115
Convirtiéndolo al código ANSI: M = Adiós
Curso de Seguridad Informática. Tema 12: Cifrado Exponencial. 29
© Jorge Ramió Aguirre Madrid (España) 2002
Fortaleza de la cifra exponencial
El problema de la Factorización de Números Grandes PFNG
tiene una complejidad similar al del Logaritmo Discreto PLD:
ambos suponen un tiempo de ejecución no polinomial.
Número de pasos que debe realizar el algoritmo PFNG:
eÖ{ln(n)*ln[ln(n)]} Sistema que consuma
1 mseg por paso:
n = 60 dígitos Þ 2,7*1011 pasos 3 días
n = 100 dígitos Þ 2,3*1015 pasos 74 años
n = 200 dígitos Þ 1,2*1023 pasos 3,8*109 años
Y1 Y2 Yq YL-1
RESUMEN
HMD5 HMD5 HMD5 HMD5
ABCD Primer resumen
de 128 bits
F (x, y, z) F (b, c, d)
(x AND y) OR (NOT x AND z) (b AND c) OR (NOT b AND d)
G (x, y, z) G (b, c, d)
(x AND z) OR (y AND NOT z) (b AND d) OR (c AND NOT d)
H (x, y, z) H (b, c, d)
x XOR y XOR z b XOR c XOR d
I (x, y, z) I (b, c, d)
y XOR (x OR NOT z) c XOR (b OR NOT d)
Curso de Seguridad Informática. Tema 13: Funciones Hash. 12
© Jorge Ramió Aguirre Madrid (España) 2002
Algoritmo de las funciones en MD5
Desplazamiento del registro da ab bc dc
Situación luego del desplazamiento
1ª Vuelta:
FF(a,b,c,d,Mj,tj,s) Þ a = b + ((a + F(b,c,d) + Mj + tj) <<< s)
2ª Vuelta:
GG(a,b,c,d,Mj,tj,s) Þ a = b + ((a + G(b,c,d) + Mj + tj) <<< s)
3ª Vuelta:
HH(a,b,c,d,Mj,tj,s) Þ a = b + ((a + H(b,c,d) + Mj + tj) <<< s)
4ª Vuelta:
II(a,b,c,d,Mj,tj,s) Þ a = b + ((a + I(b,c,d) + Mj + tj) <<< s)
Curso de Seguridad Informática. Tema 13: Funciones Hash. 14
© Jorge Ramió Aguirre Madrid (España) 2002
Algoritmo y desplazamiento en MD5
Vector de 128 bits
a b c d
Segunda vuelta
FF(b, c, d, a, M7, FD469501, 22) GG(b, c, d, a, M4, E7D3FBC8, 20)
Primera vuelta
Cuarta vuelta
HH(d, a, b, c, M0, EAA127FA, 11) II(d, a, b, c, M15, FE2CE6E0, 10)
HH(c, d, a, b, M3, D4EF3085, 16) II(c, d, a, b, M6, A3014314, 15)
HH(b, c, d, a, M6, 04881D05, 23) II(b, c, d, a, M13, 4E0811A1, 21)
HH(a, b, c, d, M9, D9D4D039, 4) II(a, b, c, d, M4, F7537E82, 6)
HH(d, a, b, c, M12, E6DB99E5, 11) II(d, a, b, c, M11, BD3AF235, 10)
HH(c, d, a, b, M15, 1FA27CF8, 16) II(c, d, a, b, M2, 2AD7D2BB, 15)
HH(b, c, d, a, M2, C4AC5665, 23) II(b, c, d, a, M9, EB86D391, 21)
Curso de Seguridad Informática. Tema 13: Funciones Hash. 17
© Jorge Ramió Aguirre Madrid (España) 2002
Función de resumen SHA-1
Un resumen de 128 bits tiene una complejidad algorítmica de
sólo 264, un valor en la actualidad muy comprometido... D
La función SHA-1, Secure Hash Algorithm, entregará un
resumen de 160 bits Þ una complejidad algorítmica de 280. C
Vector Inicial : A = 67452301 B = EFCDAB89
SHA-1
C = 98BADCFE D = 10325476 E = C3D2E1F0
Suma
Véase la próxima diapositiva...
+ mod 232
M1 M2 ... Mn E (K,M)
emisor K
receptor
M1 M2 ... Mn Am
E (K,M) = Am Î MR MR: espacio de marcas de autenticación
• La Marca Am son sólo 16, 32 ó 64 bits.
¿Cuáles son las
debilidades de • Es un tamaño muy pequeño y puede
este modelo? dar lugar a colisiones: mensajes
distintos con iguales MACs.
Curso de Seguridad Informática. Tema 14: Autenticación y Firma Digital. 13
© Jorge Ramió Aguirre Madrid (España) 2002
Aproximación con cifrado convencional
1. A ® B: IDA||NA Tickets
2. B ® KDC: IDB||NB||EKB[IDA||NA||TB]
3. KDC ® A: EKA[IDB||NA||KS||TB]||EKB[IDA||KS||TB]||NB
4. A ® B: EKB[IDA||KS||TB]||EKS[NB]
Tickets
Solución al problema del timestamp
Servicio de autenticación
desarrollado en el Massachusetts
Institute of Technology (MIT)
aq mod p = 1
En este caso se cumple para todo t que:
at = at (mod q) mod p
Curso de Seguridad Informática. Tema 14: Autenticación y Firma Digital. 36
© Jorge Ramió Aguirre Madrid (España) 2002
Generación de firma DSS de A ® B
GENERACIÓN DE LA FIRMA POR PARTE DE A
• Claves públicas de A: primos p, q y el generador a
• Clave secreta de la firma: a (1 < a < q) aleatorio
• Clave pública de la firma: y = aa mod p
• Para firmar un mensaje 1 < M < p, el firmante elige un
valor aleatorio 1 < h < q y calcula:
• r = (ah mod p) mod q
• s = [(M + a*r) * inv (h,q)] mod q
• La firma digital de M será el par (r, s)
¿igualdad?
Comprobación de firma Se acepta la firma
Autoridad de Certificación es un A B
certificado de B
ente u organismo que, de acuerdo
con unas políticas y algoritmos, certificado de A
certificará -por ejemplo- claves
públicas de usuarios o servidores.
clave pública AC
clave pública AC
El usuario A enviará al usuario B
su certificado (la clave pública
firmada por AC) y éste comprobará AC
con esa autoridad su autenticidad. C C
Lo mismo en sentido contrario. Autoridad de Certificación AC
http://www.criptored.upm.es/paginas/software.htm
El archivo cifrado
puede guardarse,
Clave Local por ejemplo, en
de 128 bits disco.
La contraseña es una frase de paso.
Se recomienda que tenga espacios, Borrado del texto
signos y caracteres de puntuación en claro opcional.
CONTRASEÑA
Cada nuevo cifrado requiere una contraseña. Esta puede ser igual o distinta.
Sellado de tiempo Clave ID* Clave pública Clave privada cifrada ID usuario
T1 e1 mod 264 Clave púb. 1 Clave priv. 1 Usuario 1
--- --- --- --- ---
Ti ei mod 264 ei EH(FPi)(di) Usuario i
--- --- --- --- ---
Tn en mod 264 Clave púb. n Clave priv. n Usuario n
C1 C2 C3 C4 C5 Nivel C
X Y ?
X es firmado por Y D1 Nivel D
? ?
C1 estados finales C2
? D1
D2 C1 D1
estados iniciales
A1 cree en el propietario de la clave para firmar otra clave
A1 cree parcialmente en el propietario de la clave para firmar otra clave
PGP hace que A1 crea en la legitimidad de las claves pues tienen al menos dos
firmas parciales (B1-B2)o una completa (C2) pero no da confianza para firmar
A1 no cree que la clave sea legítima
Curso de Seguridad Informática. Tema 16: Correo Electrónico Seguro. 28
© Jorge Ramió Aguirre Madrid (España) 2002
Problema en estos escenarios de confianza
La gestión de claves en PGP se
basa en la confianza mutua:
¡los amigos de tus amigos son
mis amigos!
ü En un sistema abierto en Internet como puede ser el
comercio electrónico, esta situación y otras más que
pueden darse en este sistema de gestión de claves de
confianza mutua, resulta inaceptable.
ü La solución, que PGP contempla en sus últimas
versiones, es la aceptación de las Autoridades de
Certificación como certificadores de claves públicas.
Curso de Seguridad Informática. Tema 16: Correo Electrónico Seguro. 29
© Jorge Ramió Aguirre Madrid (España) 2002
Cifrado PGP con clave pública destino
Mensaje Mensaje
en claro El documento se comprime
antes con el algoritmo ZIP cifrado
Necesitamos una
clave de sesión... Clave de
sesión
Clave cifrada
Se busca en el anillo de de
claves públicas del emisor sesión
Por compatibilidad de
Clave pública sistemas clientes de
del destinatario correo, se le añade
armadura (Base 64)
antes de transmitirlo
Pasos:
Clave de Clave
sesión de
cifrada sesión
CONTRASEÑA
Pasos:
Clave privada
descifrada Bloque de
Necesitamos nuestra firma
clave privada... digital
Si se desea se puede
Clave privada enviar también cifrado
cifrada IDEA
CONTRASEÑA
Firma
correcta
Bloque de
firma Sí
digital
¿ IGUALES ?
No
Se busca la clave pública del
emisor para descifrar la firma
Firma
incorrecta
Clave pública
del emisor
Curso de Seguridad Informática. Tema 16: Correo Electrónico Seguro. 36
© Jorge Ramió Aguirre Madrid (España) 2002
Algoritmos en nuevas versiones de PGP
• Generación de claves
• RSA: 1.024, 1.536, 2.048 bits
• Diffie y Hellman: 1.024, 1.536, 2.048, 3.072, 4.096 bits
• Firma digital
• DSS Digital Signature Standard 1.024 bits
• Cifrado
• CAST, IDEA, TripleDES
• Resumen
• SHA-1 (160 bits) y MD5 (128 bits)
Entre otras
Verisign
Barra flotante
PGPkeys Freespace Wipe
Encrypt Wipe
Sign Decrypt/Verify
También puede
escribirse
directamente
desde Clipboard
con PGPtray
usando la opción
editar.
default
Esquema de Blum
Finalización
del protocolo
8. A repite la operación de los pasos 5 y 6 para cada uno de
los bloques de su firma y B el paso 7.
9. Terminados los bloques de su firma, A repite el paso 6
utilizando ahora su otra clave privada y B el paso 7.
Curso de Seguridad Informática. Tema 17: Protocolos Criptográficos. 30
© Jorge Ramió Aguirre Madrid (España) 2002
La firma de contratos (4)
@ Si A y B han elegido al azar la misma clave con una
probabilidad del 50% para cada uno, B descifrará un
mensaje con sentido en la primera vuelta. En caso
contrario, B recibe un texto sin sentido y deberá
esperar hasta recibir el último bloque de la segunda
vuelta para obtener el texto en claro.
@ Sin embargo, A no tiene cómo saber en cuál de los dos
pasos (en la primera o la segunda vuelta) ha logrado B
descifrar el criptograma y obtener un texto con sentido
lo que fuerza a ambas partes a terminar el algoritmo.
Curso de Seguridad Informática. Tema 17: Protocolos Criptográficos. 31
© Jorge Ramió Aguirre Madrid (España) 2002
Firma de contratos: algoritmo de Even (1)
En el año 1985 Even, Goldreinch y Lempel proponen el uso
de sistemas de cifra simétricos para la firma de contratos.
¿Será para mí
ese e-mail?
Para evitar estas situaciones podemos
usar el protocolo del correo certificado
Los sistemas actuales de e-mail permiten emitir desde
el cliente de correo del receptor un acuse de recibo.
No obstante, esto sólo significa que “alguien” en
extremo receptor desde el buzón de entrada pincha
sobre un mensaje nuevo y a la pregunta ¿enviar acuse
recibo al emisor? pulsa Enter eligiendo la opción Sí.
Curso de Seguridad Informática. Tema 17: Protocolos Criptográficos. 35
© Jorge Ramió Aguirre Madrid (España) 2002
Correo electrónico certificado
• El usuario A desea enviar un mensaje electrónico
como correo certificado al usuario B.
• El usuario A le descubre el mensaje (le envía la
clave) sólo después ed que el usuario B le envíe
el acuse de recibo correspondiente.
• El algoritmo será muy similar al anterior de
firma de contratos propuesto por Even.
Este algoritmo de correo electrónico certificado
se implementará en una próxima edición.
I(A)