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

CRIPTOGRAFÍA Y SEGURIDAD

EN

COMPUTADORES

Versión 4-0.9.0

27 de mayo de 2011

MANUEL JOS É LUCENA L ÓPEZ

UNIVERSIDAD DE JA ÉN

2

Manuel J. Lucena López

Criptografía y Seguridad en Computadores

3

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

J.R.R. Tolkien, El Señor de Los Anillos

Yo seguía sin entender. De pronto, tuve una iluminación:

—¡Super thronos viginti quatuor! ¡La inscripción! ¡Las palabras grabadas sobre el espejo!

—¡Vamos! —dijo Guillermo—. ¡Quizás a ún estemos a tiempo de salvar una vida!

Umberto Eco, El Nombre de la Rosa

—¿Y qué? —preguntó un visitante de Washington—. ¿Qué significan otros n úmeros primos
más?

—Tal vez significa que nos están enviando un dibujo. Este mensaje está compuesto por una
enorme cantidad de bits de información. Supongamos que esa cantidad es el producto de tres
n úmeros más peque ños (. . . ). Entonces, el mensaje tendría tres dimensiones.

Carl Sagan, Contact

En la pantalla se formaban y volvían a formarse dibujos de hielo mientras él tanteaba en
busca de brechas, esquivaba las trampas más obvias y trazaba la ruta que tomaría a través
del hielo de la Senso/Red.

William Gibson, Neuromante

Manuel J. Lucena López

Criptografía y Seguridad en Computadores

4

Manuel J. Lucena López

Criptografía y Seguridad en Computadores

5

Aviso Importante

Este libro está en constante evolución. Por ello, le aconsejo que consulte la siguien-

te página web:

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

En ella podrá:

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

Consultar la Fe de Erratas.

Descargar la última versión.

Manuel J. Lucena López

Criptografía y Seguridad en Computadores

6

Manuel J. Lucena López

Criptografía y Seguridad en Computadores

7

Reconocimiento-NoComercial 2.5 Espa ña

Usted es libre de:

copiar, distribuir y comunicar p úblicamente la obra.

hacer obras derivadas.

Bajo las condiciones siguientes:

Reconocimiento. Debe reconocer los créditos de la obra de la manera
especificada por el autor o el licenciador (pero no de una manera que
sugiera que tiene su apoyo o apoyan el uso que hace de su obra).

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

Al reutilizar o distribuir la obra, tiene que dejar bien claro los términos 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.

Nada en esta licencia menoscaba o restringe los derechos morales del autor.

Los derechos derivados de usos legítimos u otras limitaciones reconocidas por ley

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ón:

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

Manuel J. Lucena López

Criptografía y Seguridad en Computadores

8

Manuel J. Lucena López

Criptografía y Seguridad en Computadores

Agradecimientos

A mis alumnos, por aguantarme cada a ño.
A Borja Arberas, Jordi Barnes, Alejandro Benabén, Manuel Cátedra, Jes ús Cea,
Dextar, Gabriel Horacio Díez, Luis Escánez, Lázaro Escudero, Silvia Fandi ño, Sacha
Fuentes, Antonio J. Galisteo, Carlos García, David García, Luis García, Alfonso
González, Germán Jácome, Juen Juen, Martín Knoblauch, Jorge Iglesias, Inkel,
Ignacio Llatser, Daniel Lombra ña, Juan Martín, Nicolás Mendia, Ana Celia Molina,
Javier Nieto, Juan Andrés Olmo, Juan Ramón Moral, Antonio Jes ús Navarro,
Alejandro Noguera, José A. Ramos, Carlos Romeo, Roberto Romero, Javier Rubio,
Juan José Ruiz, Miguel Sánchez, Felipe Santos, Pablo Tellería, Manuel Vázquez,
Rafael Vendrell, Víctor A. Villagra, y 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.
A todos los que durante todo este tiempo me han animado a seguir trabajando en
esta obra.

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
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 en Sistemas Informáticos
. . . . . . . . . . . . . . . . . . . .
2.6.1. Tipos de Autentificación . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

II Fundamentos Teóricos de la Criptografía

3. Teoría de la Información

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

21

23
23
24
27
29
29

31
31
32
34
34
36
37
39

41

43
43

Manuel J. Lucena López

Criptografía y Seguridad en Computadores

12

ÍNDICE GENERAL

.

.

.

. .

. .

. .

. .

. .

3.2. Entropía .
. . . . . . . . . . . . . . . . . . . . . . . .
3.3. Entropía Condicionada .
. . . . . . . . . . . . . . . . . . . . . . . . .
3.4. Cantidad de Información entre dos Variables . . . . . . . . . . . . . . .
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 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ética Modular

5.2. Cálculo de Inversas en Zn

5.1. Concepto de Aritmética Modular . . . . . . . . . . . . . . . . . . . . . .
5.1.1. Algoritmo de Euclides . . . . . . . . . . . . . . . . . . . . . . . .
5.1.2. Complejidad de las Operaciones Aritméticas 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 . . . . . . . . . . . . . . . . . . .

.

.

45
47
48
49
50
52
53
53
57

59
59
61
62
63
64
65
66

69
69
71
72
72
72
73
74
76
77

Manuel J. Lucena López

Criptografía y Seguridad en Computadores

ÍNDICE GENERAL

5.4.1. Algoritmo Rápido de Exponenciación . . . . . . . . . . . . . . .
5.4.2. El Problema de los Logaritmos Discretos
. . . . . . . . . . . . .
5.4.3. El Problema de Diffie-Hellman . . . . . . . . . . . . . . . . . . .
Importancia de los N úmeros Primos . . . . . . . . . . . . . . . . . . . .
5.5.
5.6. Algoritmos de Factorización . . . . . . . . . . . . . . . . . . . . . . . . .
5.6.1. Método de Fermat
. . . . . . . . . . . . . . . . . . . . . . . . . .
5.6.2. Método p − 1 de Pollard . . . . . . . . . . . . . . . . . . . . . . .
5.6.3. Métodos Cuadráticos de Factorización . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
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.1. Polinomios en Zn . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.9. Ejercicios Resueltos .
5.10. Ejercicios Propuestos .

5.8. Anillos de Polinomios

5.7. Tests de Primalidad .

.

13

77
78
78
79
80
81
81
82
84
84
85
85
86
86
88
89
92

6. Curvas Elípticas en Criptografía

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