• Author / Uploaded
• Agustin Flores

• Categories
• Criptografía
• Determinante
• Matriz (Matemáticas)
• Cifrado
• Clave (criptografía)

Citation preview

Teoría de Códigos y Criptografía

Pedro Valero Mejía UAM - Curso 2015/2016 C1 11 de febrero de 2016 14:31

Apuntes UAM Doble Grado Mat.Inf. Código en Github

Teoría de Códigos y Criptografía - Curso 2015/2016 C1 - UAM

Pedro Valero Mejía

Índice general I

Ideas generales I.1 Modelo básico . . . . . I.1.1 Poca seguridad . I.1.2 Poca fiabilidad . I.1.3 Poca capacidad

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

4 4 4 5 5

II Criptosistemas clásicos II.1 Esteganografía . . . . . . . . . . . . . . . . . . . II.2 Criptografía . . . . . . . . . . . . . . . . . . . . II.2.1 El criptosistema de Cesar . . . . . . . . . II.2.2 Formalización . . . . . . . . . . . . . . . II.3 Criptosistema afín (sobre letras) . . . . . . . . . . II.3.1 ¿Para qué valores de a,b es fa,b inyectiva? II.3.2 La función de Euler . . . . . . . . . . . . II.4 Criptosistema de sustitución . . . . . . . . . . . . II.5 Definción de Criptabeto . . . . . . . . . . . . . . II.6 Lucha contra el análisis de frecuencias . . . . . . II.6.1 Sustitución polialfabética . . . . . . . . . II.6.2 Criptosistema de Vigenère . . . . . . . . .

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

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

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

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

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

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

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

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

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

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

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

6 6 6 7 7 8 9 10 14 14 15 20 23

III De la criptografía clásica a la de clave pública III.1 Enigma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.2 Criptosistemas de clave simétrica . . . . . . . . . . . . . . . . III.3 Estimaciones de tiempo . . . . . . . . . . . . . . . . . . . . . III.4 Usos criptográficos de las funciones de un sólo sentido . . . . . III.4.1 Compartición de clave privada . . . . . . . . . . . . . . III.4.2 Recibir mensajes cifrados sin necesidad de acordar claves III.4.3 Firmas . . . . . . . . . . . . . . . . . . . . . . . . . . III.4.4 Identificación . . . . . . . . . . . . . . . . . . . . . . . III.4.5 Challenge: Identificación a partir de otro . . . . . . . . III.4.6 Tarjeta de crédito . . . . . . . . . . . . . . . . . . . . III.4.7 El gran cambio de la tecnología moderna . . . . . . . . III.5 Modos de ataque . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . a . . . . . .

. . . . . . . . . . . . . . . priori . . . . . . . . . . . . . . . . . .

25 26 28 29 31 31 32 32 32 33 33 34 35

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

IV El criptosistema RSA 36 IV.1 Generación de claves . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 IV.2 Manejo de las funciones . . . . . . . . . . . . . . . . . . . . . . . . . 37 IV.3 Tratamiento de los mensajes . . . . . . . . . . . . . . . . . . . . . . . 38 0

Documento compilado el 11 de febrero de 2016 a las 14:31

1 de 237

Teoría de Códigos y Criptografía - Curso 2015/2016 C1 - UAM

IV.4 Ataques contra RSA . . . . . . . . . . . IV.4.1 Ataque de texto en claro elegido . IV.5 Cifrado y firma con RSA . . . . . . . . . IV.6 Elección de primos para RSA . . . . . . IV.7 Otros criptosistemas de clave pública . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

Pedro Valero Mejía

. . . . .

. . . . .

V Algoritmos de factorización y tests de primalidad V.1 Test de primalidad . . . . . . . . . . . . . . . . . . . V.1.1 Tests probabilísticos . . . . . . . . . . . . . . V.1.2 Números de Carmichael . . . . . . . . . . . . V.1.3 Test de primalidad de Miller-Marsin (1974) . . V.2 Algoritmos de Factorización . . . . . . . . . . . . . . V.2.1 Idea detrás de los métodos modernos de criba

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . .

38 39 41 41 42

. . . . . .

43 44 45 47 50 52 55

VI Otros sistemas de clave pública y más aplicaciones 58 VI.1 Criptosistema de ElGamal . . . . . . . . . . . . . . . . . . . . . . . . 58 VIICódigos detectores y correctores de errores VII.1 Motivación . . . . . . . . . . . . . . . . . . VII.2 Distancia de Hamming . . . . . . . . . . . . VII.3 Código de barras . . . . . . . . . . . . . . . VII.3.1 Detección de errores . . . . . . . . . VII.3.2 Corrección de errores . . . . . . . . . VII.4 International Standard Book Number . . . . VII.4.1 Detección de errores . . . . . . . . . VII.4.2 Corrección de errores . . . . . . . . . VII.5 Número de Identificación Fiscal . . . . . . . VII.5.1 Detección de errores . . . . . . . . . VII.5.2 Corrección de errores . . . . . . . . . VII.6 Probabilidades . . . . . . . . . . . . . . . . VII.7 Cota de Hamming o del empaquetamiento de VII.7.1 Código de Hamming . . . . . . . . . VIIICódigos lineales VIII.1¿Por qué códigos lineales? . . . . . VIII.2Definición . . . . . . . . . . . . . VIII.3Codificación con códigos lineales . VIII.4Decodificación con códigos lineales VIII.4.1 Decodificación por síndrome

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . esferas . . . .

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

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

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

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

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

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

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

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

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

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

59 59 61 69 70 71 72 73 74 74 75 75 76 82 84

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

85 85 85 88 88 91

IX Códigos de Hamming IX.1 Códigos de Hamming binarios . . . . . . . . . . . . . IX.2 Códigos BCH (Bose Ray-Chaudhury y Hocquenghem) IX.3 Códigos binarios extendidos . . . . . . . . . . . . . . IX.4 Códigos binarios acortados (o reducidos) . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

94 94 98 102 103

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . para Ham(3,2)

A Ejercicios 105 A.1 Hoja 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 A.2 Control 1 (22-09-2014) Modelo A . . . . . . . . . . . . . . . . . . . . 114

2 de 237

Teoría de Códigos y Criptografía - Curso 2015/2016 C1 - UAM

A.3 A.4 A.5 A.6 A.7 A.8 A.9 A.10 A.11 A.12 A.13 A.14 A.15 A.16

Hoja 2 Control Control Hoja 3 Control Hoja 4 Hoja 5 Hoja 6 Control Control Hoja 7 Hoja 8 Control Control

. 2 2 . 3 . . . 4 4 . . 5 5

. . . . . . . . . . . . . (13-10-2014) Modelo A (13-10-2014) Modelo B . . . . . . . . . . . . . (6-11-2014) Modelo A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (1-12-2014) Modelo A (1-12-2014) Modelo B . . . . . . . . . . . . . . . . . . . . . . . . . . (18-12-2014) Modelo A (18-12-2014) Modelo B

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

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

Índice alfabético

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

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

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

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

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

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

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

Pedro Valero Mejía

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

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

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

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

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

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

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

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

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

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

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

116 135 136 138 153 156 174 185 197 199 200 214 232 235 237

3 de 237

Teoría de Códigos y Criptografía - Curso 2015/2016 C1 - UAM

Pedro Valero Mejía

Capítulo I Ideas generales Matemáticas de la transmisión de información

I.1.

Modelo básico

emisor –(info)-> receptor la flecha es el canal. Ejemplos de canales son: cable aire/espacio papel disco duro / USB / CD El canal con el que vamos a trabajar tiene 3 defectos: 1. poco seguro 2. poco fiable 3. con poca capacidad

I.1.1.

Poca seguridad

Existe un "malo", es decir, que no es el emisor o receptor y puede interferir con la información (leerla y alterarla). Se soluciona con criptografía. Emisor -> [cifrador]—canal—>[descifrador] -> Receptor

4 de 237

Teoría de Códigos y Criptografía - Curso 2015/2016 C1 - UAM

I.1.2.

Pedro Valero Mejía

Poca fiabilidad

El mensaje puede sufrir alteraciones involuntarias, tales como erratas (papel), polvo o ralladuras (disco duro o CD), rayo cósmico, ruido, etc... Se soluciona con códigos detectores/correctores de errores. Emisor -> [codificador]—canal—>[descodificador] -> Receptor

I.1.3.

Poca capacidad

Puede faltar capacidad en varios sentidos. Puede faltar tiempo (como en una clase si el profesor repite mucho), capacidad (como en un disco duro) o energía (como cuando un satélite tiene una energía limitada para transferir información). Se soluciona con algoritmos de compresión (no es parte del temario). Emisor -> [compresor]—canal—>[descompresor] -> Receptor

Si queremos resolver los tres problemas a la vez es obvio que debemos combinarlos todos, pero en que orden? Colocaremos en último lugar (cerca del canal) el proceso de codificación y descodificación, ya que depende mucho del canal y puede verse anulado con un posterior proceso de cifrado o compresión. Respecto a los otros dos, podemos debatir sobre su orden. Pero hay que tener en cuenta, por lo menos en el caso de cadenas de texto, que conviene comprimir primero, ya que algunos ataques sobre el cifrado se pueden realizar si los mensajes cifrados se repiten y/o tienen patrones reconocibles. Estas posibilidades se reducen bastante al comprimir primero.

5 de 237

Teoría de Códigos y Criptografía - Curso 2015/2016 C1 - UAM

Pedro Valero Mejía

Capítulo II Criptosistemas clásicos La criptografía tiene como objetivo resolver el siguiente problema:

Figura II.1: Cómo enviar un mensaje de manera segura entre Bob y Alice por un canal al que Eve tiene acceso

El objetivo es garantizar tanto la confidencialidad del mensaje (Eve no es capaz de saber qué se están diciendo) como de autentifiación (Alice está segura de que es Bob quien mandó el mensaje y viceversa) A lo largo de este capítulo veremos los métodos que han sido empleados a lo largo de la historia para lograr este objetivo.

II.1.

Esteganografía

Intentar ocultar la existencia del mensaje. Es un método con origen muy antigüo ( 486-425 a.C)

II.2. Criptografía

Criptografía

Definición II.1 Criptografía. Tradicionalmente se ha definido como el ámbito de la criptología el que se ocupa de las técnicas de cifrado o codificado destinadas a alterar las representaciones lingüísticas de ciertos mensajes con el fin de hacerlos ininteligibles a receptores no autorizados. 6 de 237

Teoría de Códigos y Criptografía - Curso 2015/2016 C1 - UAM

Pedro Valero Mejía

El primer método de criptografía data del siglo V antes de cristo La mayoría de estos métodos se basaban en transposición. Transposición

Definición II.2 Transposición. Cambio en el orden de las letras de un mensaje

II.2.1.

El criptosistema de Cesar

Se utiliza la sustitución como método de cifrado, normalmente cambiando cada letra por su correspondiente al desplazarse d espacios atrás en el abecedario. Por ejemplo: sin cifrar A B C ...

II.2.2.

cifrado D E F ...

Formalización

Vamos a ver cómo denominamos formalmente los elementos que intervienen en un proceso de cifrado: Mensajes Tenemos dos diferentes mensajes en todo proceso de cifrado 1. M = Mensajes en claro 2. C = Mensajes cifrados Alfabeto Tendremos un alfabeto o dos, dependiendo de si los alfabetos de M y C son el mismo o no. Ejemplos de alfabetos serían: • A = {A, B...Z} • A = {0, 1} • A = {A, B...Z, . . . , ¿, ?, 1, 2, 3, . . . , 9, 0} • A = Código ASCII Funciones para cifrar Serán funciones de la forma f : M → C donde f es inyectiva Funciones para descifrar Serán funciones de la forma f −1 : C → M donde f es la misma función empleada para cifrar el mensaje.

7 de 237

Teoría de Códigos y Criptografía - Curso 2015/2016 C1 - UAM

Pedro Valero Mejía

Para que pueda llevarse a cabo la comunicación entre A y B, A debe conocer f y B debe conocer f −1 . A envía un mensaje m ∈ M a B usando f (m) = c y enviando c. B puede obtener el mensaje calculando f −1 (c) = m. En este modelo, romper el sistema de cifrado equivale a que un tercero averigüe f −1 . ¿Podemos usar más de una función para cifrar? En el sistema de Cesar se puede cambiar, por ejemplo, la longitud desplazamiento por el abecedario al realizar el cifrado, aunque no hay muchas posibilidades. Criptosistema

Definición II.3 Criptosistema. Colección de functiones para cifrar. Se trata de funciones de la forma fe : Me 7−→ Ce

Ejemplo:

Como romper la criptografía Cesar

Se puede romper "facilmente" la criptografía Cesar con análisis de frecuencias. Por ejemplo, en castellano la letra más frecuente es la E, con un 13,68 %, sabiendo la letra más frecuente de un mensaje cifrado se puede calcular la distancia entre esa y la E y muy probablemente hayamos hallado la clave de cifrado. La fiabilidad de este método puede verse mermada por la genericidad del texto cifrado. Si es corto y si habla de un tema en particular es posible que las frecuencias varíen respecto a otros textos genéricos en Español. De hecho, por ejemplo, en el manual de UNIX la frecuencia de la letra e baja al 9 % dejando a la letra relegada al cuarto puesto, por detrás de la t, la n y la i. Veamos la frecuencia general de distintos grupos de letras en ingles. grupos e taoiushr cumwfgypb vkjxqz

II.3. Cifrado afín

frec 12.7 % 56.9 19.9 2.2

rango 12.7 6-9 1.5 - 3