SItema 06

Tema 6
Teoría de la Complejidad Algorítmica
Seguridad Informática y Criptografía
Ultima actualización: 03/03/03

Archivo con 28 diapositivas
Material Docente de Jorge Ramió Aguirre

v 3.1
Libre Distribución Universidad Politécnica de Madrid
Este archivo forma parte de un curso sobre Seguridad Informática y Criptografía. Se autoriza la
reproducción en computador e impresión en papel sólo con fines docentes o personales, respetando
en todo caso los créditos del autor. Queda prohibida su venta, excepto a través del Departamento de
Publicaciones de la Escuela Universitaria de Informática, Universidad Politécnica de Madrid, España.
Curso de Seguridad Informática y Criptografía © JRA

Nota del autor
El contenido de este tema
corresponde sólo a una breve
introducción a la complejidad
de los algoritmos, con el objeto
de que el lector pueda hacerse
una idea de la importancia de
este tema en el análisis y diseño de los algoritmos de
cifra y firma digital que se verán en este curso. La
fortaleza de estos algoritmos y de los protocolos que
los incluyen dependerá de la complejidad asociada al
criptoanálisis o ataque de los mismos.
Seguridad Informática y Criptografía. Tema 6: Teoría de la Complejidad Algorítmica Diapositiva 2
© Jorge Ramió Aguirre Madrid (España) 2003

Introducción a la teoría de la complejidad
La teoría de la complejidad de los algoritmos nos

permitirá conocer si un algoritmo tiene fortaleza y tener
así una idea de su vulnerabilidad computacional.
Complejidad Computacional
Los algoritmos se clasifican según el tiempo de
ejecución y en función del tamaño de la entrada.
 Complejidad Polinomial 
 Complejidad Exponencial 
Esto dará lugar a tipos de “problemas” que nos interesarán.

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 (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.

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.

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
f = O(n) ssi  co,no / f(n)  cog(n)

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
co no cono2 f (n) = 4n2 + 2n + 5 ¿con2  f (n)?
6 1 6 11 No
6 2 24 25 No
Se cumple
6 3 54 38 Sí siempre
6 4 96 77 Sí
Luego, la complejidad de f (n) es exponencial.

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)

Algoritmos de complejidad lineal
• Un algoritmo se dice que tiene tiempo de ejecución
polinomial 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 Suma
Si t = 2, el sistema es cuadrático Producto
Si t = 3, el sistema es cúbico mcd Euclides

Ejemplo de complejidad lineal
Ejemplo: El tiempo de ejecución de un algoritmo es

O(log3 n). Si doblamos la entrada, ¿en cuánto aumenta
este tiempo?
Solución: En el primer caso el tiempo es O(log3 n) y en
el segundo O(log3 2n). Luego para este sistema lineal
el tiempo se incrementará 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.
Seguridad Informática y Criptografía. Tema 6: Teoría de la Complejidad Algorítmica Diapositiva
10
Algoritmos de complejidad exponencial
• Un algoritmo se dice que tiene tiempo de ejecución

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).
Ejemplo
Para t = 2, será exponencial de orden 2 n!
Para t = 3, será exponencial de orden 3

11
Ejemplo de complejidad exponencial
Ejemplo: El tiempo de ejecución de un algoritmo es

O(n3). Si doblamos la entrada, ¿en cuánto aumenta
este tiempo?
Solución: En el primer caso el tiempo es O(n3) y en el
segundo O(2n3) = O(8n3). Para este sistema exponencial
el tiempo 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.
12
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) ... etc.
– Exponencial  O(dh(n))
donde d es una constante y h(n) un polinomio
Si suponemos un ordenador capaz de realizar
109 instrucciones por segundo se tiene el cuadro:
13
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 10-7 seg 10-5 seg 10-3 seg 41013 años
n = 103 10-6 seg 10-3 seg 1 seg Muy grande
Incrementos de un Computacionalmente
orden de magnitud imposible
Entrada/109: Para n = 100  O(n2) = 1002/109 = 10-5 seg
14
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 ...
15
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?

16
Ejemplo del problema de la mochila
S = a 1 + a 2 + a3 A = {a1, a2, a3}
Sea una mochila
¿Se incluye a1 en la suma S?
a1 Los resultados son todos con 4 elementos
Sí No distintos: una casualidad {2, 4, 9, 10}
¿Se incluye a2 en la suma?
 ¿Cuántas sumas
a2 a2
Sí No Sí No posibles hay?
¿Se incluye a3? Solución: 24 = 16
a3 a3 a3 a3 , 2, 4, 6,
Sí No Sí No Sí No Sí No 9, 10, 11, 12,
13, 14, 15, 16,
S1 S2 S3 S4 S5 S6 S7 S8
19, 21, 23, 25.
S1 = a1+a2+a3 S2 = a1+a2 S3 = a1+a3 S 4 = a1 Repita con
{2, 4, 6, 10}
S5 = a2+a3 S 6 = a2 S 7 = a3 S8 = 
Hemos tenido que evaluar 23 = 8 valores  (carácter exponencial)
17
Interés de las mochilas en criptografía
¿Por qué tiene interés este problema en criptografía?
a) Es de tipo NP completo: su resolución por lo general
implica una complejidad exponencial. Luego, será
difícil de atacar o criptoanalizar.
b) Existe un caso en el que la resolución es lineal y, si la
solución existe, es única. Se da si A = {a1, a2, a3, .., an}
está ordenado de menor a mayor y en donde cada ai es
mayor que la suma de los aj que le preceden.
Esto dará lugar a los criptosistemas de mochila
tramposa que veremos en un próximo capítulo.
18
El problema de la factorización PFNG
Dado un número n que es el resultado del producto de

dos primos n = pq, se pide encontrar estos factores.
• Cuando el valor n es muy grande, el Problema de la
Factorización de Números Grandes PFNG se vuelve
computacionalmente intratable.
• No obstante, el caso inverso, dado dos números p y q,
encontrar el resultado pq = n, se trata de un problema
de tipo polinomial.
• Este problema se usará en la generación del par de
claves del sistema de cifra con clave pública RSA.
19
Un ejemplo del PFNG
 Cálculo fácil o polinomial (función directa)
Calcule “a mano” los siguientes productos de dos primos y
tome el tiempo aproximado que tarda en la operación:
a) 1331 b) 113131 c) 1.0131.031 calcule...
No vale usar ¿A qué conclusiones
calculadora... puede llegar ahora?
 Cálculo difícil o no polinomial (función inversa)
Usando la criba de Eratóstenes, factorice en dos primos los
siguientes números y vuelva a tomar el tiempo empleado:
a) 629 b) 17.399 c) 1.052.627 calcule...
En el caso a) son primos de 2 dígitos, en c) de 3 y en d) de 4.
20
Solución al ejemplo anterior
 Cálculo fácil o polinomial
a) 1331 = 403 b) 113131 = 14.803 c) 10131031 = 1.044.403
A medida que aumenta el tamaño de la entrada, el tiempo de
cálculo aumenta proporcionalmente con los dígitos.
Un computador
 Cálculo difícil o no polinomial experimentará lo
a) 629 b) 17.399 c) 1.052.627 mismo....
Aquí resulta evidente que el tiempo de cálculo (da igual que el
algoritmo sea éste u otro más depurado y eficaz) aumenta mucho al
incrementar en un dígito los números en cuestión.
Solución: a), b) y c) son el producto de los números primos
inmediatamente superiores a los de arriba (ver tabla en SItema18).
21
El problema del logaritmo discreto PLD
Dado un par de enteros  y  que pertenecen al Campo
de Galois GF(p), se pide encontrar un entero x de forma
que x = log  mod p.
Si el valor p es muy grande, el Problema del Logaritmo
Discreto PLD es computacionalmente intratable.
No obstante, el caso inverso, dado dos números  y x,
encontrar  = x mod p es un problema polinomial.
Este problema se usará en la creación de las claves del
sistema de cifra con clave pública ElGamal y en el
protocolo de intercambio de clave de Diffie y Hellman.
22
Un ejemplo del PLD
 Cálculo fácil o polinomial (función directa)
Calcule “a mano” las siguientes exponenciaciones mod p y
tome el tiempo aproximado que tarda en la operación:
a) 54 mod 7 b) 817 mod 41 c) 9211 mod 251
54 = 625
817 = 2.251.799.813.685.248
9211 = 3.996.373.778.857.415.671.808
Nota: Haciendo uso de la propiedad de reducibilidad del capítulo 5,
podrá reducir significativamente el tiempo de cálculo. No obstante,
este tiempo será de tipo polinomial según el tamaño de la entrada.
23
Solución al ejemplo anterior
 Cálculo difícil o no polinomial (función inversa)
Aunque existen varios algoritmos para este tipo de cálculos
(al igual que para la factorización) use la fuerza bruta que se
explica a continuación para encontrar los siguientes valores y
vuelva a tomar el tiempo empleado:
a) log5 2 mod 7 b) log8 39 mod 41 c) log92 217 mod 251
Aplicando fuerza bruta en el 1er caso (la base elevada a todos
los restos de p) al final se obtiene que log5 2 mod 7 = 4.
En media deberá
51 mod 7 = 5 52 mod 7 = 4 53 mod 7 = 6 recorrer la mitad
54 mod 7 = 2 55 mod 7 = 3 56 mod 7 = 1 del espacio... 

24
Logaritmo discreto con  generador
log2 1 mod 13 = 0 log2 2 mod 13 = 1 log2 3 mod 13 = 4
20 mod 13 = 1 21 mod 13 = 2 22 mod 13 = 4

23 mod 13 = 8 24 mod 13 = 3 25 mod 13 = 6
26 mod 13 = 12 27 mod 13 = 11 28 mod 13 = 9
Es 29 mod 13 = 5 210 mod 13 = 10 211 mod 13 = 7
decir
Se cumplirá además que ap-1 mod p = a0 mod p = 1.
25
Logaritmo discreto con  no generador
En p=13, el 2 30 mod 13 = 1 31 mod 13 = 3 32 mod 13 = 9
es generador,
pero no así el 33 mod 13 = 1 34 mod 13 = 3 35 mod 13 = 9
número 3... 36 mod 13 = 1 37 mod 13 = 3 38 mod 13 = 9
Luego 39 mod 13 = 1 310 mod 13 = 3 311 mod 13 = 9
log3 1 mod 13 = 0 log3 2 mod 13 = NE log3 3 mod 13 = 1

log3 4 mod 13 = NE log3 5 mod 13 = NE log3 6 mod 13 = NE
log3 7 mod 13 = NE log3 8 mod 13 = NE log3 9 mod 13 = 2
log3 10 mod 13 = NE log3 11 mod 13 = NE log3 12 mod 13 = NE
NE = no existe
26
¿Hay más funciones NP?
Existen otros problemas matemáticos que dan lugar a

problemas del tipo NP basados en estas funciones
unidireccionales (one way functions) pero las dos
últimas funciones vistas –factorización de números
grandes y logaritmo discreto- son las que más uso
tienen, de momento, en la criptografía.
Algunos de ellos se presentarán en el Tema dedicado

a los Protocolos Criptográficos.
Fin del Tema 6

27
Cuestiones y ejercicios
1. Deseamos sumar de forma binaria el número 15 (1111) y el
número 10 (1010), ambos de k = 4 bits. Haga la suma binaria y
verifique que el número de operaciones bit desarrolladas es k = 4.
2. Si multiplicamos en binario 101011, donde k = 4 bits y h = 2 bits,
compruebe que el número de operaciones bit realizadas es 2kh.
3. ¿Por qué son interesantes los problemas de tipo NP en criptografía?
4. Defina el problema de la mochila y su posible utilización en un
sistema de cifra.
5. Factorice mentalmente el valor n = 143. Intente hacer lo mismo
para n = 1.243. ¿Qué opina ahora del problema de la factorización?
6. A partir de la ecuación  = x mod p, defina el problema del
logaritmo discreto. ¿Qué utilidad tiene en criptografía?

28

SItema 06

Cargado por

Copyright:

Formatos disponibles

SItema 06

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

SItema 06

Cargado por

Copyright:

Formatos disponibles

Tema 6

Teoría de la Complejidad Algorítmica

Seguridad Informática y Criptografía

Ultima actualización: 03/03/03

Material Docente de Jorge Ramió Aguirre

Curso de Seguridad Informática y Criptografía © JRA

© Jorge Ramió Aguirre Madrid (España) 2003

La teoría de la complejidad de los algoritmos nos

Seguridad Informática y Criptografía. Tema 6: Teoría de la Complejidad Algorítmica Diapositiva 3

© Jorge Ramió Aguirre Madrid (España) 2003

Ejemplo: encontrar el número de operaciones bit necesarias en la

Seguridad Informática y Criptografía. Tema 6: Teoría de la Complejidad Algorítmica Diapositiva 4

© Jorge Ramió Aguirre Madrid (España) 2003

© Jorge Ramió Aguirre Madrid (España) 2003

Seguridad Informática y Criptografía. Tema 6: Teoría de la Complejidad Algorítmica Diapositiva 6

© Jorge Ramió Aguirre Madrid (España) 2003

© Jorge Ramió Aguirre Madrid (España) 2003

© Jorge Ramió Aguirre Madrid (España) 2003

Si t = 2, el sistema es cuadrático Producto

Si t = 3, el sistema es cúbico mcd Euclides

Seguridad Informática y Criptografía. Tema 6: Teoría de la Complejidad Algorítmica Diapositiva 9

© Jorge Ramió Aguirre Madrid (España) 2003

Ejemplo: El tiempo de ejecución de un algoritmo es

Estos son los denominados problemas fáciles y son

• Un algoritmo se dice que tiene tiempo de ejecución

Para t = 3, será exponencial de orden 3

Seguridad Informática y Criptografía. Tema 6: Teoría de la Complejidad Algorítmica Diapositiva

Ejemplo: El tiempo de ejecución de un algoritmo es

Estos son los denominados problemas difíciles y son a

Entrada O(n) O(n2) O(n3) O(2n)

n = 10 10-8 seg 10-7 seg 10-6 seg 10-6 seg

Seguridad Informática y Criptografía. Tema 6: Teoría de la Complejidad Algorítmica Diapositiva

Dado un número n que es el resultado del producto de

Seguridad Informática y Criptografía. Tema 6: Teoría de la Complejidad Algorítmica Diapositiva

20 mod 13 = 1 21 mod 13 = 2 22 mod 13 = 4

log3 1 mod 13 = 0 log3 2 mod 13 = NE log3 3 mod 13 = 1

Existen otros problemas matemáticos que dan lugar a

Algunos de ellos se presentarán en el Tema dedicado

Seguridad Informática y Criptografía. Tema 6: Teoría de la Complejidad Algorítmica Diapositiva

Seguridad Informática y Criptografía. Tema 6: Teoría de la Complejidad Algorítmica Diapositiva

También podría gustarte