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

Criptograf´ıa y Seguridad en

Computadores

Tercera Edici´on (Versi´on 1.00). Junio de 2001

Manuel Jos´e Lucena L´opez
e-mail:
[email protected]
[email protected]

2

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

—¿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. . .

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

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

4

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

Copyright

c(cid:13)1999, 2000, 2001 de Manuel Jos´e Lucena L´opez. Todos los derechos reservados.
Este documento puede ser distribuido libre y gratuitamente bajo cualquier soporte siempre

que se respete su integridad.

Queda prohibida su venta sin permiso expreso del autor.

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

6

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

Agradecimientos

A Loles, ella sabe por qu´e.
A los chicos de Kript´opolis, por darme esta oportunidad.
A mis alumnos, por aguantarme cada a˜no.
A todos aquellos que, enviando sugerencias o correcciones, han ayudado a mejorar esta obra.
A todos los que alguna vez han compartido sus conocimientos, por enriquecernos a todos.

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

8

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

Prefacio

El presente documento ha sido elaborado originalmente como apoyo a la asignatura “Crip-
tograf´ıa y Seguridad en Computadores”, de 3er Curso de Ingenier´ıa T´ecnica en Inform´atica de
Gesti´on, de la Universidad de Ja´en, empleando el procesador de textos LATEX 2ε, y los editores
gr´aficos XFig y Gimp. Puede descargarse su ´ultima versi´on y eventuales correcciones en las
siguientes direcciones web:

http://www.kriptopolis.com

http://wwwdi.ujaen.es/~mlucena

No se pretende que estos apuntes sustituyan a la bibliograf´ıa de la asignatura, ni a las
clases te´oricas, sino que sirvan m´as bien como complemento a las notas que el alumno debe
tomar en clase. Asimismo, no debe considerarse un documento definitivo y exento de errores,
si bien ha sido elaborado con detenimiento y revisado exhaustivamente. El autor pretende que
sea mejorado y ampliado con cierta frecuencia, lo que probablemente desembocar´a en sucesivas
versiones, y para ello nadie mejor que los propios lectores para plantear dudas, buscar errores,
y sugerir mejoras.

Ja´en, Junio de 2001.

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

10

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 sobre Criptograf´ıa

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

II Fundamentos Te´oricos de la Criptograf´ıa

3 Teor´ıa de la Informaci´on

3.1 Cantidad de Informaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Entrop´ıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Entrop´ıa Condicionada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Cantidad de Informaci´on entre dos Variables
. . . . . . . . . . . . . . . . . . .

19

21
21
22
24
25
25

29
29
30
31
32
33
34

37

39
39
40
42
44

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

12

´INDICE GENERAL

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

4 Introducci´on a la 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 Fundamentos de Aritm´etica Modular

5.1 Aritm´etica Modular. Propiedades . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1 Algoritmo de Euclides . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.2 Complejidad de las Operaciones Aritm´eticas en Zn . . . . . . . . . . . .
5.2 C´alculo de Inversas 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 . . . . . . . . . . . . . . . . . . . . . . .
5.4.1 Algoritmo de Exponenciaci´on R´apida . . . . . . . . . . . . . . . . . . .
5.4.2 El Problema de los Logaritmos Discretos
. . . . . . . . . . . . . . . . .
5.4.3 El Problema de Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . .
Importancia de los N´umeros Primos
. . . . . . . . . . . . . . . . . . . . . . . .
5.5
5.6 Algoritmos de Factorizaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6.1 M´etodo de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44
45
46
47
48

49
49
51
52
53
53
54
55

57
57
58
59
60
60
61
62
63
64
64
65
65
66
66
67

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

´INDICE GENERAL

5.6.2 M´etodo p − 1 de Pollard . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6.3 M´etodos Cuadr´aticos de Factorizaci´on . . . . . . . . . . . . . . . . . . .

5.7 Tests de Primalidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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 Anillos de Polinomios

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

6 Introducci´on a las Curvas El´ıpticas

6.1 Curvas El´ıpticas en R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Suma en E(R)

6.1.1

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

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

7.1 Representaci´on de enteros largos

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

7.2 Operaciones aritm´eticas sobre enteros largos . . . . . . . . . . . . . . . . . . . .

7.2.1

Suma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.2.2 Resta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.2.3 Multiplicaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.2.4 Divisi´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.3 Aritm´etica modular con enteros largos . . . . . . . . . . . . . . . . . . . . . . .

7.4 Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 Criptograf´ıa y N´umeros Aleatorios

13

68

69

70

70

71

71

72

72

73

74

75

75

76

78

79

79

80

80

81

81

82

82

83

84

86

89

90

91

Manuel J. Lucena L´opez

Criptograf´ıa y Seguridad en Computadores

14

´INDICE GENERAL

8.1 Tipos de Secuencias Aleatorias

8.2 Generaci´on de Secuencias Aleatorias Criptogr´aficamente V´alidas

8.1.1
8.1.2
8.1.3

. . . . . . . . . . . . . . . . . . . . . . . . . . .
Secuencias pseudoaleatorias . . . . . . . . . . . . . . . . . . . . . . . . .
Secuencias criptogr´aficamente aleatorias . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .