PDF de programación - Criptografía y seguridad en computadores

Criptografía y Seguridad en

Computadores

Tercera Edición (Versión 1.00). Junio de 2001

Manuel José Lucena López

e-mail:
[email protected]
[email protected]

2

Manuel J. Lucena López

Criptografía y Seguridad en Computadores

—¿Qué significa habla, amigo y entra? —preguntó Merry.

—Es bastante claro —dijo Gimli—. Si eres un amigo, dices la contraseña y las puertas se
abren y puedes entrar.

—Sí —dijo Gandalf—, es probable que estas puertas estén gobernadas por palabras. . .

El Señor de Los Anillos

J.R.R. Tolkien

Manuel J. Lucena López

Criptografía y Seguridad en Computadores

4

Manuel J. Lucena López

Criptografía y Seguridad en Computadores

Copyright

c1999, 2000, 2001 de Manuel José Lucena López. 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ópez

Criptografía y Seguridad en Computadores

6

Manuel J. Lucena López

Criptografía y Seguridad en Computadores

Agradecimientos

A Loles, ella sabe por qué.

A los chicos de Kriptópolis, por darme esta oportunidad.

A mis alumnos, por aguantarme cada año.

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ópez

Criptografía y Seguridad en Computadores

8

Manuel J. Lucena López

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écnica en Informática de
Gestión, de la Universidad de Jaén, empleando el procesador de textos LATEX 2ε, y los editores
gráficos XFig y Gimp. Puede descargarse su última versión 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óricas, sino que sirvan más 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á en sucesivas
versiones, y para ello nadie mejor que los propios lectores para plantear dudas, buscar errores,
y sugerir mejoras.

Jaén, Junio de 2001.

Manuel J. Lucena López

Criptografía y Seguridad en Computadores

10

Manuel J. Lucena López

Criptografía y Seguridad en Computadores

Índice General

I Preliminares

1 Introducción

1.1 Cómo Leer esta Obra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2 Algunas notas sobre la Historia de la Criptografía . . . . . . . . . . . . . . . . .

1.3 Números Grandes

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

1.4 Acerca de la Terminología Empleada . . . . . . . . . . . . . . . . . . . . . . . .

1.5 Notación Algorítmica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Conceptos Básicos sobre Criptografía

2.1 Criptografía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Criptosistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3 Esteganografía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4 Criptoanálisis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5 Compromiso entre Criptosistema y Criptoanálisis . . . . . . . . . . . . . . . . .

2.6 Seguridad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

II Fundamentos Teóricos de la Criptografía

3 Teoría de la Información

3.1 Cantidad de Información . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2 Entropía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3 Entropía Condicionada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4 Cantidad de Información 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ópez

Criptografía y Seguridad en Computadores

12

ÍNDICE GENERAL

3.5 Criptosistema Seguro de Shannon . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6 Redundancia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.7 Desinformación y Distancia de Unicidad . . . . . . . . . . . . . . . . . . . . . .

3.8 Confusión y Difusión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.9 Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Introducción 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ética Modular

5.1 Aritmética Modular. Propiedades . . . . . . . . . . . . . . . . . . . . . . . . . .

5.1.1 Algoritmo de Euclides . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.1.2 Complejidad de las Operaciones Aritméticas en Zn . . . . . . . . . . . .

5.2 Cálculo de Inversas en Zn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2.1 Existencia de la Inversa . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2.2 Función de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2.3 Algoritmo Extendido de Euclides . . . . . . . . . . . . . . . . . . . . . .

5.3 Teorema Chino del Resto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.4 Exponenciación. Logaritmos Discretos . . . . . . . . . . . . . . . . . . . . . . .

5.4.1 Algoritmo de Exponenciación Rápida . . . . . . . . . . . . . . . . . . .

5.4.2 El Problema de los Logaritmos Discretos

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

5.4.3 El Problema de Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . .

5.5

Importancia de los Números Primos

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

5.6 Algoritmos de Factorización . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.6.1 Método 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ópez

Criptografía y Seguridad en Computadores

ÍNDICE GENERAL

5.6.2 Método p − 1 de Pollard . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6.3 Métodos Cuadráticos de Factorización . . . . . . . . . . . . . . . . . . .

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

5.7.1 Método de Lehmann . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.7.2 Método de Rabin-Miller . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.7.3 Consideraciones Prácticas . . . . . . . . . . . . . . . . . . . . . . . . . .

5.7.4 Primos fuertes

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

5.8 Anillos de Polinomios

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

5.8.1 Polinomios en Zn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.9 Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 Introducción a las Curvas Elípticas

6.1 Curvas Elípticas en R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.1.1

Suma en E(R)

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

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ética Entera de Múltiple Precisión

7.1 Representación de enteros largos

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

7.2 Operaciones aritméticas sobre enteros largos . . . . . . . . . . . . . . . . . . . .

7.2.1

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

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

7.2.3 Multiplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.2.4 División . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.3 Aritmética modular con enteros largos . . . . . . . . . . . . . . . . . . . . . . .

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

8 Criptografía y Números 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ópez

Criptografía y Seguridad en Computadores

14

ÍNDICE GENERAL

8.1 Tipos de Secuencias Aleatorias

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

8.1.1

Secuencias pseudoaleatorias . . . . . . . . . . . . . . . . . . . . . . . . .

8.1.2

Secuencias criptográficamente aleatorias . . . . . . . . . . . . . . . . . .

8.1.3

Secuen