PDF de programación - Elementos de criptografía

Elementos de
criptografía

Llorenç Huguet Rotger

Josep Rifà Coma

Juan Gabriel Tena Ayuso

PID_00200951

Los textos e imágenes publicados en esta obra están sujetos –excepto que se indique lo contrario– a
una licencia de Reconocimiento-NoComercial-SinObraDerivada (BY-NC-ND) v.3.0 España de
Creative Commons. Podéis copiarlos, distribuirlos y transmitirlos públicamente siempre que citéis
el autor y la fuente (FUOC. Fundació per a la Universitat Oberta de Catalunya), no hagáis un uso
comercial y no hagáis una obra derivada. La licencia completa se puede consultar en
http://creativecommons.org/licenses/by-nc-nd/3.0/es/legalcode.es

CC-BY-NC-ND • PID_00200951

Índice

Elementos de criptografía

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1. Criptosistemas simétricos o de clave privada . . . . . . . . . . . . . . . . .

1.1. Criptosistema DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2. Criptosistema IDEA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3. Criptosistema AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4. Modos de operación de los criptosistemas de clave privada . . .

2. Criptosistemas de clave pública . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.

Funciones unidireccionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2. Criptosistema RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1. Descripción del criptosistema . . . . . . . . . . . . . . . . . . . . . . . .

2.2.2.

Firma digital, basada en el RSA . . . . . . . . . . . . . . . . . . . . . . .

2.3. Criptosistema ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.1. Descripción del criptosistema ElGamal . . . . . . . . . . . . . . .

2.3.2.

Firma digital, basada en el ElGamal . . . . . . . . . . . . . . . . . .

2.4. Algoritmo DSA como alternativa a la firma digital RSA . . . . . . .

2.5.

Funciones hash: MD5 y SHA-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5.1.

El algoritmo MD5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5.2.

El algoritmo SHA-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.6.

Infraestructura de clave pública: PKI . . . . . . . . . . . . . . . . . . . . . . . . . .

2.6.1.

Sistemas gestores de certificados electrónicos:

la recomendación X.509 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.6.2.

Listas de certificados revocados: CRL . . . . . . . . . . . . . . . . .

3. Criptografía cuántica y post-cuántica . . . . . . . . . . . . . . . . . . . . . . . . .

3.1. Criptografía cuántica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.

Los códigos correctores de errores en la criptografía

post-cuántica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.1. Nociones básicas de códigos correctores de errores . . .

3.2.2. Códigos lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.3.

Los códigos lineales cíclicos: BCH y RS . . . . . . . . . . . . . . .

3.2.4.

Los códigos cíclicos BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.5.

Los códigos cíclicos RS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.

Los criptosistemas de McEliece y de Niederreiter . . . . . . . . . . . . . .

3.3.1. Criptosistema de McEliece . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.2. Criptosistema de Niederreiter. . . . . . . . . . . . . . . . . . . . . . . . .

5

8

9

9

12

13

14

16

17

17

18

19

21

21

22

23

25

26

27

29

31

32

33

35

37

37

39

43

45

46

47

47

49

CC-BY-NC-ND • PID_00200951

Elementos de criptografía

Ejercicios de autoevaluación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

Solucionario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

Bibliografía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

CC-BY-NC-ND • PID_00200951

5

Elementos de criptografía

Introducción

Lectura recomendada

Para hacer más
comprensible este módulo
didáctico se puede
acompañar del libro de
Criptografía de J. Domingo,
J. Herrera y H. Rifà-Pous de
los estudios de Informática
y Multimedia, de la UOC.

Tradicionalmente, la criptografía tiene como objetivo la transmisión o alma-

cenamiento de mensajes indescifrables para todo receptor que no disponga de

la clave del algoritmo de descifrado.

Hoy, la criptografía se presenta como la solución al problema de la vulnera-

bilidad de los sistemas de transmisión, o de almacenamiento, con respecto al

secreto y a la autenticidad de la información transmitida, o almacenada. El

objetivo concerniente a la privacidad y autenticidad asociados a una red de

sistemas es evitar que un espía pueda violar o eliminar la protección del sis-

tema en referencia a las líneas de comunicación, a la conexión de acceso a la

red (contraseñas) y a la utilización de los recursos de un determinado sistema.

En tiempos pasados, la criptografía ha sido una actividad casi exclusivamente

utilizada en la diplomacia y en la guerra, pero, a partir de la Segunda Guerra

Mundial, la aparición de los ordenadores ha hecho que todos los sistemas crip-

tográficos utilizados antes, excepto el método de Vernam (basado en claves de

un solo uso y del cual se puede demostrar matemáticamente su inviolabili-

dad), formen parte de la historia puesto que la velocidad en el tratamiento de

la información hace que sea un juego de niños el problema de encontrar sus

correspondientes claves (criptoanálisis).

De esta simplicidad de los métodos clásicos es un ejemplo el sistema cripto-

gráfico, llamado de Julio César, por ser él su primer usuario, utilizado todavía

durante la segunda guerra mundial, que consistía en numerar los caracteres

alfabéticos y cifrar el mensaje m como el criptograma c, mediante una trasla-

ción cíclica que hoy enunciaríamos como c = (m + k) (mod 25), donde m es el
valor numérico asignado a cada letra del alfabeto {A = 0,B = 1,...,Z = 24}, por
ejemplo, y para un cierto valor de k previamente elegido (Cesar escogía k = 3).

El texto AMOR quedaría, en valores numéricos, 0,12,14,17 que se cifrarían en

3,15,17,20; es decir, se transmitiría el mensaje cifrado (criptograma): DPRU.

Desde siempre, toda técnica criptográfica que opera sobre un mensaje, sin

tener en cuenta su estructura lingüística, está basada en una operación ejecu-

tada por el emisor, transformando el mensaje original en un mensaje cifrado,

mediante un algoritmo que implementa esta operación, ligado a una clave k.

Al mismo tiempo, esta operación posee la operación inversa, ejecutada por el

receptor, que permite encontrar el mensaje original.

Todo sistema criptográfico, también denominado criptosistema, consta de cin-
co componentes: {M,C,K,E y D}, donde M es el conjunto de todos los mensa-

CC-BY-NC-ND • PID_00200951

6

Elementos de criptografía

jes a transmitir, C el de todos los mensajes cifrados, K el de las claves a utilizar,
E el de todos los métodos de cifrado: E = {Ek|Ek(m) ∈ C,∀m ∈ M,∀k ∈ K} y D el
de todos los métodos de descifrado: D = {Dk|Dk(c) ∈ M,∀c ∈ C,∀k ∈ K}.

Cada método de cifrado de E, y cada método de descifrado de D, está definido

mediante un algoritmo, que es común a todos los métodos, y donde cada
clave k ∈ K, distinguirá la instancia correspondiente a cada transformación Ek,
y Dk, respectivamente.

Para toda clave k ∈ K, la transformación Dk es la inversa de Ek; es decir:

Dk(Ek(m)) = m,∀m ∈ M

Observar sin embargo, que esto no quiere decir que Ek sea el inverso de Dk, en
sentido matemático.

Criptoanálisis

Fuente

m

Cifrado
Ek(m) = c

c

Descifrado
Dk(c) = m

m

Receptor

Ek

Métodos
de cifrado

k

Claves

Dk

Métodos

de descifrado

k

Canal seguro

Todo criptosistema, tal y como muestra la figura anterior, debe cumplir al

Principios de Kerchoff

menos estos tres requisitos:

1) Todos los algoritmos de cifrado y descifrado Ek y Dk deben ser computacio-
nalmente eficientes.

2) Los algoritmos Ek y Dk deben ser fácilmente implementables.

3) La seguridad del sistema solo debe depender del secreto de las claves k ∈ K,
y no de los algoritmos correspondientes de E y D.

Además, siempre se deberá tener en cuenta los objetivos de privacidad y au-

tenticidad, donde se considera:

En criptografía, las
propiedades deseables de un
criptosistema constituyen los
principios de Kerckhoff; de
entre ellos, los más
importantes: Si el
criptosistema no es
teóricamente irrompible, al
menos lo debe ser en la
práctica. La efectividad del
criptosistema no debe
depender de que su diseño
permanezca en secreto. El
criptosistema debe ser fácil
de usar. La clave debe ser
fácilmente memorizable, para
evitar recurrir a notas escritas.
Los criptogramas deberían
ser alfanuméricos.

CC-BY-NC-ND • PID_00200951

7

Elementos de criptografía

• Privacidad: como la incapacidad, para un criptoanalista, de determinar un

mensaje original a partir del criptograma que haya podido interceptar.

• Autenticidad: como la incapacidad, para un criptoanalista, de sustituir un
criptograma falso c′, en lugar del criptograma real c, sin que sea detectado.

Consideraciones a los criptosistemas

Actualmente, se consideran dos tipos de criptosistemas, según la utilización

y administración de los algoritmos de cifrado y descifrado. El criptosistema

clásico o convencional, en el cual la clave correspondiente