Publicado el 14 de Septiembre del 2018
493 visualizaciones desde el 14 de Septiembre del 2018
188,7 KB
16 paginas
Creado hace 18a (07/03/2006)
Libro Electrónico de Seguridad Informática y Criptografía v4.1
Capítulo 8
Teoría de la Complejidad Algorítmica
Seguridad Informática y Criptografía
Ultima actualización del archivo: 01/03/06
Este archivo tiene: 31 diapositivas
v 4.1
Material Docente de
Libre Distribución
Dr. Jorge Ramió Aguirre
Universidad Politécnica de Madrid
Este archivo forma parte de un curso completo sobre Seguridad Informática y Criptografía. Se autoriza el uso,
reproducción en computador y su impresión en papel, sólo con fines docentes y/o personales, respetando los
créditos del autor. Queda prohibida su comercialización, excepto la edición en venta en el Departamento de
Publicaciones de la Escuela Universitaria de Informática de la Universidad Politécnica de Madrid, España.
Curso de Seguridad Informática y Criptografía © JRA
Capítulo 8: Teoría de la Complejidad Algorítmica
Página 313
Introducción a la teoría de la complejidad
La teoría de la complejidad de los algoritmos permitirá, entre otras
cosas, conocer la fortaleza de un algoritmo y tener así una idea de
su vulnerabilidad computacional.
Complejidad Computacional
Los algoritmos pueden clasificarse según su tiempo de ejecución,
en función del tamaño u orden de la entrada. Hablamos así de
complejidad:
• Polinomial ⇒ comportamiento similar al lineal
• Polinomial No Determinísta ⇒ comportamiento exponencial
Esto dará lugar a “problemas fáciles” y “problemas difíciles” cuyo
uso será muy interesante en la criptografía.
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 8: Teoría de la Complejidad Algorítmica
Libro Electrónico de Seguridad Informática y Criptografía v4.1
Capítulo 8: Teoría de la Complejidad Algorítmica
Página 314
Operaciones bit en la suma
Si deseamos sumar dos números binarios n y m, ambos de k bits
realizaremos k operaciones bit puesto que cada operación básica
con los dígitos de una columna es una operación bit.
• Recuerde que 0+0 = 0, 0+1=1, 1+0 = 1, 1+1 = 0 con bit 1 de acarreo.
• Si un número tiene menos bits, se rellena con ceros por la izquierda.
Ejemplo: encontrar el número de operaciones bit necesarias en la
suma en binario de 13+7 ⇒ 1101 + 0111 (de k = 4 bits)
1 1 1 1 (bits de acarreo)
+
1 1 0 1
0 1 1 1
1 0 1 0 0
Cada operación básica que hacemos con una columna se conoce
como operación bit, luego necesitamos k = 4 operaciones bit.
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 8: Teoría de la Complejidad Algorítmica
Página 315
Operaciones bit en la multiplicación
Para la multiplicación de un número n de k bits por un número
m de h bits, el número de operaciones bit será igual a 2∗k∗h.
Suponemos que k ≥ h.
• Recuerde que 0x0 = 0, 0x1=0, 1x0 = 0, 1x1 = 1.
Ejemplo: encontrar el número de operaciones bit necesarias en la
multiplicación en binario 10x5 ⇒ 1010 x 101 (4 y 3 bits)
1 0 1 0 x 1 0 1
1 0 1 0
0 0 0 0
+ 1 0 1 0 (procedemos ahora a sumar)
1 1 0 0 1 0
Como cada operación básica entre dos bits es una operación bit,
hemos realizado h∗k = 3∗4 multiplicaciones y luego k∗h = 4∗3
sumas, es decir en total 2∗k∗h = 24 operaciones bit.
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 8: Teoría de la Complejidad Algorítmica
Libro Electrónico de Seguridad Informática y Criptografía v4.1
Capítulo 8: Teoría de la Complejidad Algorítmica
Página 316
La función O(n)
Las operaciones dependerán del tamaño de la entrada por lo
que esta complejidad se expresará en términos del tiempo T
necesario para el cálculo del algoritmo y del espacio S que
utiliza en memoria, y se expresará mediante una función
f (n), donde n es el tamaño de la entrada.
Esta función será una aproximación pues el resultado exacto
dependerá de la velocidad del procesador.
f (n) = O(g(n))
Ejemplo
Y se define así: f = O(n) ssi ∃ co,no / f(n) ≤ co∗g(n)
http://www.mm.informatik.tu-darmstadt.de/courses/2002ws/ics/lectures/v14.pdf
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 8: Teoría de la Complejidad Algorítmica
Página 317
Complejidad de una función f(n)
Si f (n) = 4n2 + 2n + 5 ¿ f = O(n2)?
¿se cumple que co∗g(n) = co∗n2 ≥ f (n)? Sea co = 6
f (n) = 4n2 + 2n + 5 ¿co∗n2 ≥ f (n)?
co
6
6
6
6
No
No
Sí
Sí
Luego, la complejidad de f (n) es exponencial.
no
1
2
3
4
Se cumple
siempre
2
cono
6
24
54
96
11
25
38
77
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 8: Teoría de la Complejidad Algorítmica
Libro Electrónico de Seguridad Informática y Criptografía v4.1
Capítulo 8: Teoría de la Complejidad Algorítmica
Página 318
Tiempos de ejecución
En la expresión O(n) aparecerá el término que domina al
crecer el valor de n.
• El tiempo de ejecución de un algoritmo T1 que realiza
2n+1 operaciones es de tipo O(n); uno T2 que realiza
3n2+n+3 operaciones será de tipo O(n2), etc.
• Para realizar la suma de la diapositiva anterior necesitamos
O(n) = O(log n) operaciones bit y para el caso de la
multiplicación, éstas serán O(n∗m) = O(log n ∗ log m)
operaciones bit.
+ Operación binaria: n+m (de k bits cada uno)
∗ Operación binaria: n∗m (de k y h bits respectivamente)
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 8: Teoría de la Complejidad Algorítmica
Página 319
Algoritmos de complejidad polinomial
• Un algoritmo se dice que tiene tiempo de ejecución
polinomial (no confundir con lineal) si éste depende
polinómicamente del tamaño de la entrada.
• Si la entrada es de tamaño n y t es un entero, el
número de operaciones bit será O(logt n).
Ejemplos
Si t = 1, el sistema es lineal
Si t = 2, el sistema es cuadrático
Si t = 3, el sistema es cúbico
Suma
Producto
Máximo Común
Divisor (Euclides)
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 8: Teoría de la Complejidad Algorítmica
Libro Electrónico de Seguridad Informática y Criptografía v4.1
Capítulo 8: Teoría de la Complejidad Algorítmica
Página 320
Ejemplo de complejidad polinomial
Pregunta: El tiempo de ejecución de un algoritmo es
O(log3 n). Si doblamos el tamaño de la entrada, ¿en
cuánto aumentará este tiempo?
Solución: En el primer caso el tiempo es O(log3 n) y en
el segundo O(log3 2n). Para este sistema polinomial, el
tiempo se incrementará sólo en log3 2 operaciones bit.
Estos son los denominados problemas fáciles y son
los que involucrarán un proceso de cifra y descifrado
(o firma) por parte del o de los usuarios autorizados.
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 8: Teoría de la Complejidad Algorítmica
Página 321
Algoritmos de complejidad no determinista
• Un algoritmo se dice que tiene tiempo de ejecución
polinomial no determinista (en este caso exponencial)
si éste depende exponencialmente del tamaño de la
entrada.
• Si la entrada es de tamaño n y t es un entero, el
número de operaciones bit será O(nt).
Para t = 2, será exponencial de orden 2
Para t = 3, será exponencial de orden 3
© Jorge Ramió Aguirre Madrid (España) 2006
Ejemplo
n!
Capítulo 8: Teoría de la Complejidad Algorítmica
Libro Electrónico de Seguridad Informática y Criptografía v4.1
Capítulo 8: Teoría de la Complejidad Algorítmica
Página 322
Ejemplo de complejidad no determinista
Pregunta: El tiempo de ejecución de un algoritmo es
O(n3). Si doblamos el tamaño de la entrada, ¿en cuánto
aumentará este tiempo?
Solución: En el primer caso el tiempo es O(n3) y en el
segundo O((2n)3) = O(8n3). El tiempo para este sistema
exponencial, se incrementará en 8 operaciones bit.
Estos son los denominados problemas difíciles y son a
los que deberá enfrentarse un criptoanalista o atacante
que desea romper una cifra o la clave de un usuario.
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 8: Teoría de la Complejidad Algorítmica
Página 323
Comparativas de complejidad
• Los algoritmos polinómicos y exponenciales se
comparan por su complejidad O(nt).
– Polinómico constante ⇒ O(1)
– Polinómico lineal ⇒ O(n)
– Polinómico cuadrático ⇒ O(n2)
– Polinómico cúbico ⇒ O(n3)
– Exponencial ⇒ O(dh(n))
... etc.
donde d es una constante y h(n) un polinomio
Si suponemos un ordenador capaz de realizar 109
instrucciones por segundo obtenemos este cuadro:
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 8: Teoría de la Complejidad Algorítmica
Libro Electrónico de Seguridad Informática y Criptografía v4.1
Capítulo 8: Teoría de la Complejidad Algorítmica
Página 324
Tabla comparativa de tiempos
Entrada
O(n) O(n2) O(n3) O(2n)
n = 10 10-8 seg 10-7 seg 10-6 seg 10-6 seg
n = 102
n = 103
10-7 seg 10-5 seg 10-3 seg 4∗1013 años
10-6 seg 10-3 seg 1 seg Muy grande
Incrementos de un
orden de magnitud
Computacionalmente
imposible
Entrada/109: Para n = 100 ⇒ O(n2) = 1002/109 = 10-5 seg
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 8: Teoría de la Complejidad Algorítmica
Página 325
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 de tipo NP, polinomiales no
deterministas, computacionalmente difíciles de tratar:
Problema de la mochila
Problema de la factorización
Problema del logaritmo discreto
Problema logaritmo discreto en curvas elípticas
Otros
Definición del
problema y
ejemplos
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 8: Teoría de la Complejidad Algorítmica
Libro Electrónico de Seguridad Informática y Criptografía v4.1
Capítulo 8: Teoría de la Complejidad Algorítmica
Página 326
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
Comentarios de: Capítulo 8 Teoría de la Complejidad Algorítmica (0)
No hay comentarios