PDF de programación - Criptografía y Seguridad en Computadores

Criptografía y Seguridad en Computadores4ª Edición. Versión 0.7.3Manuel J. Lucena López 2

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

3

—¿Qu´e significa habla, amigo y entra? —pregunt´o Merry.
—Es bastante claro —dijo Gimli—. Si eres un amigo, dices la contrase ˜na y las puertas se abren
y puedes entrar.

—S´ı —dijo Gandalf—, es probable que estas puertas est´en gobernadas por palabras. . .

J.R.R. Tolkien, El Se˜nor de Los Anillos

Yo segu´ıa sin entender. De pronto, tuve una iluminaci´on:

—¡Super thronos viginti quatuor! ¡La inscripci´on! ¡Las palabras grabadas sobre el espejo!

—¡Vamos! —dijo Guillermo—. ¡Quiz´as a ´un estemos a tiempo de salvar una vida!

Umberto Eco, El Nombre de la Rosa

—¿Y qu´e? —pregunt´o un visitante de Washington—. ¿Qu´e significan otros n ´umeros primos
m´as?

—Tal vez significa que nos est´an enviando un dibujo. Este mensaje est´a compuesto por una
enorme cantidad de bits de informaci´on. Supongamos que esa cantidad es el producto de tres
n ´umeros m´as peque ˜nos (. . . ). Entonces, el mensaje tendr´ıa tres dimensiones.

Carl Sagan, Contact

En la pantalla se formaban y volv´ıan a formarse dibujos de hielo mientras ´el tanteaba en
busca de brechas, esquivaba las trampas m´as obvias y trazaba la ruta que tomar´ıa a trav´es
del hielo de la Senso/Red.

William Gibson, Neuromante

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

4

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

5

Aviso Importante

Este libro est´a en constante evoluci´on. Por ello, le aconsejo que consulte la siguien-

te p´agina web:

http://wwwdi.ujaen.es/ mlucena/lcripto.html

En ella podr´a:

Si no dispone de los archivos .sig correspondientes, verificar la firma digital
del libro.

Consultar la Fe de Erratas.

Descargar la ´ultima versi´on.

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

6

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

7

Reconocimiento-NoComercial-SinObraDerivada 2.0 Espa ˜na

Usted es libre de:

copiar, distribuir y comunicar p ´ublicamente la obra

Bajo las condiciones siguientes:

Reconocimiento. Debe reconocer y citar al autor original.

No comercial. No puede utilizar esta obra para fines comerciales.

Sin obras derivadas. No se puede alterar, transformar o generar una
obra derivada a partir de esta obra.

Al reutilizar o distribuir la obra, tiene que dejar bien claro los t´erminos de la
licencia de esta obra.

Alguna de estas condiciones puede no aplicarse si se obtiene el permiso del
titular de los derechos de autor

Los derechos derivados de usos leg´ıtimos u otras limitaciones no se ven afectados

por lo anterior.

Esto es un resumen legible por humanos del texto legal (la licencia completa)

disponible en la siguiente direcci´on:

http://creativecommons.org/licenses/by-nc-nd/2.0/es/legalcode.es

Advertencia

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

8

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

´Indice general

I Preliminares

1. Introducci´on

.

.

.

.

.

.

.

.

.

.

1.1. C´omo Leer esta Obra . . .
.
1.2. Algunas notas sobre la Historia de la Criptograf´ıa .
1.3. N ´umeros Grandes . . . . .
.
.
1.4. Acerca de la Terminolog´ıa Empleada .
.
1.5. Notaci´on Algor´ıtmica . . .
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2. Conceptos B´asicos

.
.
.
.

.
.
.
.

.
.
.
.

2.1. Criptograf´ıa . . . . . . .
.
.
.
2.2. Criptosistema . . . . . . .
2.3. Esteganograf´ıa . . . . . . .
.
2.4. Criptoan´alisis . . . . . .
.
.
2.5. Compromiso entre Criptosistema y Criptoan´alisis .
.
2.6. Seguridad . . . . . . . .
2.7. Autentificaci´on . . . . .
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

II Fundamentos Te´oricos de la Criptograf´ıa

3. Teor´ıa de la Informaci´on

3.1. Cantidad de Informaci´on .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

19

21
21
22
25
27
27

29
29
30
32
32
34
35
36

39

41
41

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

10

´INDICE GENERAL

.
.

.
.

.
.

.
.

.
.

.
.

.
.

3.2. Entrop´ıa . . . . . . . . . . . . . .
.
3.3. Entrop´ıa Condicionada . . . . . .
.
3.4. Cantidad de Informaci´on entre dos Variables .
.
.
3.5. Criptosistema Seguro de Shannon .
.
3.6. Redundancia . . . . . . . . . . .
.
.
3.7. Desinformaci´on y Distancia de Unicidad .
.
3.8. Confusi´on y Difusi´on . . . . . . .
.
.
.
.
3.9. Ejercicios Resueltos . . . . . . . .
3.10. Ejercicios Propuestos . . . . . . .
.
.

.
.
.
.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.

.
.

.
.

.

.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

4. Complejidad Algor´ıtmica

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

4.1. Concepto de Algoritmo . . . . . .
4.2. Complejidad Algor´ıtmica . . . .
4.2.1. Operaciones Elementales .

.
.
.
4.3. Algoritmos Polinomiales, Exponenciales y Subexponenciales .
.
4.4. Clases de Complejidad . . . . . .
4.5. Algoritmos Probabil´ısticos . . . .
.
.
.
4.6. Conclusiones . . . . . . . . . . .

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

5. Aritm´etica Modular

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

5.2. C´alculo de Inversas en Zn

5.1. Concepto de Aritm´etica Modular .
.

.
.
5.1.1. Algoritmo de Euclides . .
5.1.2. Complejidad de las Operaciones Aritm´eticas en Zn
.
.
.
.
.
.

.
. . . .
.
5.2.1. Existencia de la Inversa .
5.2.2. Funci´on de Euler . . . . .
.
5.2.3. Algoritmo Extendido de Euclides
5.3. Teorema Chino del Resto . . . . .
.
5.4. Exponenciaci´on. Logaritmos Discretos .

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.

.

.

.
.

.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

43
45
46
47
48
50
51
51
55

57
57
59
60
61
62
63
64

67
67
69
70
70
70
71
72
74
75

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

´INDICE GENERAL

.

.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

5.5.
5.6. Algoritmos de Factorizaci´on .
.

5.4.1. Algoritmo R´apido de Exponenciaci´on .
5.4.2. El Problema de los Logaritmos Discretos
5.4.3. El Problema de Diffie-Hellman .
.
Importancia de los N ´umeros Primos .
.
.
.
.
.
.
.
5.6.1. M´etodo de Fermat
.
.
.
.
.
5.6.2. M´etodo p − 1 de Pollard .
.
.
.
5.6.3. M´etodos Cuadr´aticos de Factorizaci´on .
.
.
.
.
.
.
.
.
.

.
.
.
5.7.1. M´etodo de Lehmann .
.
.
5.7.2. M´etodo de Rabin-Miller .
.
5.7.3. Consideraciones Pr´acticas .
5.7.4. Primos fuertes . .
.
.
.
.
.

.
. .
5.8.1. Polinomios en Zn .
5.9. Ejercicios Resueltos . . . .
5.10. Ejercicios Propuestos . .
.

5.7. Tests de Primalidad . . . .

5.8. Anillos de Polinomios

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.

.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

6.1. Curvas El´ıpticas en R . .
6.1.1. Suma en E(R) . .

6. Curvas El´ıpticas en Criptograf´ıa
.
.
6.2. Curvas El´ıpticas en GF (n) .
6.3. Curvas El´ıpticas en GF (2n)
6.3.1. Suma en E(GF (2n))

.
.
.
.
.
6.4. El Problema de los Logaritmos Discretos en Curvas El´ıpticas .
.
6.5. Ejercicios Resueltos . . . .
6.6. Ejercicios Propuestos . .
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

11

75
76
76
77
78
79
79
80
82
82
83
83
84
84
86
87
90

91
92
93
95
95
96
96
97
99

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

7. Aritm´etica Entera de M ´ultiple Precisi´on

101

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

12

´INDICE GENERAL

.

.

.

.

.

.

7.2.1. Suma . . . . . . . . . . .
.
7.2.2. Resta . . . . . . . . . . . .
7.2.3. Producto . . . . . . . . . .
7.2.4. Divisi´on . . . . . . . . . .

7.1. Representaci´on de enteros largos .
.
7.2. Operaciones aritm´eticas sobre enteros largos .
.
.
.
.
.
.
.

.
.
.
.
7.3. Aritm´etica modular con enteros largos .
.
7.4. Ejercicios Resueltos . . . . . . . .
7.5. Ejercicios Propuestos . . . . . . .
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.

.
.

.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

8