Criptograf´ıa y Seguridad en
Computadores
Segunda Edici´on. Septiembre de 1999
Manuel Jos´e Lucena L´opez
Departamento de Inform´atica
Escuela Polit´ecnica Superior
Universidad de Ja´en
e-mail:
[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 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 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ε.
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, Septiembre de 1999.
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 . . . . . . . . . . . . . . . . . . . . . . . .
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
. . . . . . . . . . . . . . . . . . .
3.5 Criptosistema Seguro de Shannon . . . . . . . . . . . . . . . . . . . . . . . . . .
17
19
19
20
22
24
25
25
26
27
28
29
30
33
35
35
36
38
40
40
Manuel J. Lucena L´opez
Criptograf´ıa y Seguridad en Computadores
12
´INDICE GENERAL
3.6 Redundancia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7 Desinformaci´on y Distancia de Unicidad . . . . . . . . . . . . . . . . . . . . . .
3.8 Confusi´on y Difusi´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.9 Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 Fundamentos de Aritm´etica Modular
4.1 Aritm´etica Modular. Propiedades . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Algoritmo de Euclides . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 C´alculo de Inversas en Aritm´etica Modular
. . . . . . . . . . . . . . . . . . . .
4.2.1 Existencia de la Inversa . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.2 Funci´on de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.3 Algoritmo Extendido de Euclides . . . . . . . . . . . . . . . . . . . . . .
4.3 Exponenciaci´on. Logaritmos Discretos . . . . . . . . . . . . . . . . . . . . . . .
4.3.1 Algoritmo de Exponenciaci´on R´apida . . . . . . . . . . . . . . . . . . .
4.3.2 El Problema de los Logaritmos Discretos
. . . . . . . . . . . . . . . . .
4.4 Factorizaci´on. Tests de Primalidad . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1 M´etodo de Lehmann . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.2 M´etodo de Rabin-Miller . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.3 Consideraciones Pr´acticas . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.4 Primos fuertes
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 Aritm´etica Entera de M´ultiple Precisi´on
. . . . . . . . . . . . . . . . . . . . . . . . . .
5.1 Representaci´on de enteros largos
5.2 Operaciones aritm´eticas sobre enteros largos . . . . . . . . . . . . . . . . . . . .
Suma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1
5.2.2 Resta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.3 Multiplicaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.4 Divisi´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Aritm´etica modular con enteros largos . . . . . . . . . . . . . . . . . . . . . . .
5.4 Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
42
43
43
45
45
46
47
47
47
48
49
49
50
50
51
52
52
53
53
55
55
56
56
57
58
60
62
62
Manuel J. Lucena L´opez
Criptograf´ıa y Seguridad en Computadores
´INDICE GENERAL
6 Criptograf´ıa y N´umeros Aleatorios
6.1 Tipos de Secuencias Aleatorias
6.2 Generaci´on de Secuencias Aleatorias Criptogr´aficamente V´alidas
6.1.1
6.1.2
6.1.3
. . . . . . . . . . . . . . . . . . . . . . . . . . .
Secuencias pseudoaleatorias . . . . . . . . . . . . . . . . . . . . . . . . .
Secuencias criptogr´aficamente aleatorias . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
Secuencias totalmente aleatorias
. . . . . . . .
6.2.1 Obtenci´on de Bits Aleatorios . . . . . . . . . . . . . . . . . . . . . . . .
6.2.2 Eliminaci´on del Sesgo . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.3 Generadores Aleatorios Criptogr´aficamente Seguros . . . . . . . . . . . .
6.2.4 Generador Blum Blum Shub . . . . . . . . . . . . . . . . . . . . . . . .
III Criptograf´ıa de Llave Privada
7 Criptograf´ıa Cl´asica
7.1 Algoritmos Cl´asicos de Cifrado . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.1 Cifrados Monoalfab´eticos
7.1.2 Cifrados Polialfab´eticos
. . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.3 Cifrados por Sustituci´on Homof´onica . . . . . . . . . . . . . . . . . . . .
7.1.4 Cifrados de Transposici´on . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2 M´aquinas de Rotores. La M´aquina ENIGMA . . . . . . . . . . . . . . . . . . .
7.2.1 Un poco de Historia . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2.2 Consideraciones Te´oricas Sobre la M´aquina ENIGMA . . . . . . . . . .
7.2.3 Otras M´aquinas de Rotores . . . . . . . . . . . . . . . . . . . . . . . . .
8 Algoritmos Sim´etricos de Cifrado
8.1 Cifrado de producto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.1.1 Redes de Feistel
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.1.2 Cifrados con Estructura de Grupo . . . . . . . . . . . . . . . . . . . . .
8.1.3
S-Cajas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2 El Algoritmo DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2.1 Claves D´ebiles en DES . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
65
65
65
66
66
67
67
69
70
71
73
75
75
76
77
78
78
79
80
82
82
83
83
83
84
85
86
87
Manuel J. Lucena L´opez
Criptograf´ıa y Seguridad en Computadores
14
´INDICE GENERAL
8.3 Variantes de DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.3.1 DES M´ultiple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.3.2 DES con Subclaves Independientes . . . . . . . . . . . . . . . . . . . . .
8.3.3 DES Generalizado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.3.4 DES con S-Cajas Alternativas . . . . . . . . . . . . . . . . . . . . . . . .
8.4 El algoritmo IDEA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.5 Modos de Operaci´on para Algoritmos de Cifrado por Bloques . . . . . . . . . .
8.5.1 Modo ECB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.5.2 Modo CBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.5.3 Modo CFB . . .
Comentarios de: Criptografía y Seguridad en Computadores (0)
No hay comentarios