Criptografía

1

UNIVERSIDAD NACIONAL DE LA LIBERTAD Facultad de Ciencias F´ ısicas y Matem´ticas a Departamento de Inform´tica a

´ Algebra universal para la Ciencia de la Computaci´n: Aplicaci´n a la Criptograf´ o o ıa

Jos´ A. Rodr´ e ıguez Melquiades
MsC. Ciencia de la Computaci´n o

Teresa Bracamonte Nole
Ing. Inform´tico a

Trujillo - PERU 2009

2

Prefacio

´ Indice general
1.Introducci´n a la criptograf´ o ıa 1.1. Evoluci´n historica de la criptograf´ . . . . . . . . o ıa 1.1.1. Criptograf´ cl´sica . . . . . . . . . . . . . . ıa a 1.1.2. Criptograf´ moderna . . . . . . . . . . . . ıa 1.2. Elementos participantes en un modelo criptogr´fico a 1.2.1. Entidades . . . . . . . . . . . . . . . . . . . 1.2.2. Escenario b´sico . . . . . . . . . . . . . . . a 1.2.3. Criptosistemasim´trico . . . . . . . . . . . e 1.2.4. Criptosistema asim´trico . . . . . . . . . . . e 1.3. Investigadores que han aportado a la criptograf´ . ıa 1.3.1. Antes del siglo XX . . . . . . . . . . . . . . 1.3.2. Durante las guerras mundiales . . . . . . . 1.3.3. Creadores de algoritmos sim´tricos . . . . . e 1.3.4. Creadores de algoritmos asim´tricos . . . . e 1.4. Ejercicios . . . . . . . . . . . . . .. . . . . . . . . 2. Algoritmos y Complejidad computacional 2.1. Algoritmos . . . . . . . . . . . . . . . . . . . . . . 2.2. Complejidad computacional . . . . . . . . . . . . . 2.2.1. An´lisis de algoritmos . . . . . . . . . . . . a 2.2.2. Formalizaci´n del an´lisis de los algoritmos o a 2.2.3. Clases de problemas . . . . . . . . . . . . . 2.2.4. Complejidad computacional con enteros . . 2.3.Ejercicios . . . . . . . . . . . . . . . . . . . . . . . 3. Teor´ de n´ meros ıa u 3.1. Qu´ es la teor´ de n´meros . . . . . . e ıa u 3.2. Divisibilidad . . . . . . . . . . . . . . . 3.3. MCD, MCM y N´meros primos . . . . u 3.3.1. M´ximo com´n divisor (mcd) . a u 3.3.2. M´ ınimo com´n m´ltiplo (mcm) u u 3.3.3. N´meros primos . . . . . . . . u 3.4. Congruencia . . . . . . . . . . . . . . . 3.5.Enteros modulo n: Zn . . . . . . . . . 3.5.1. Operaciones en Zn . . . . . . . 3.5.2. Grupo multiplicativo . . . . . . 3.6. Funci´n de Euler φ . . . . . . . . . . . o 3.7. Problema de factorizaci´n entera . . . o 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 8 8 9 11 11 11 13 14 15 15 16 16 16 17 19 19 21 22 23 26 28 31 33 33 35 36 37 40 40 45 48 48 50 51 52

4

´ INDICE GENERAL 3.7.1. Factorizaci´n de prop´sito especial . . . . . . . o o 3.7.2. Factorizaci´n de prop´sito general . . . . . . . o o 3.8. Residuo cuadr´tico . . . . . . . . . . .. . . . . . . . . a 3.8.1. Residuo cuadr´tico y residuo no cuadr´tico . . a a 3.9. Problema de la ra´ cuadrada modulo n . . . . . . . . ız 3.9.1. Ra´ cuadrada cuando n un n´mero primo . . . ız u 3.9.2. Ra´ cuadrada cuando n un n´mero compuesto ız u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . 53 53 55 55 58 58 58 61 61 61 66 75 76 77 80 84 85 86 88 89

4. Criptosistemas basados en teor´ de n´ meros ıa u 4.1. Cifrado por clave sim´trica . . . . . . . . . . . . e 4.1.1. Cifrado por caracteres . . . . . . . . . . . 4.1.2. Cifrado por bloque y flujo . . . . . . . . 4.2. Cifrado por clave asim´trica . . . . . . . . . . . . e 4.2.1....