PDF de programación - Criptografía

Criptografía 

Temario
 Criptografía de llave secreta (simétrica)
 Algoritmos de cifrado
 Definir el problema con este tipo de cifrado
 Criptografía de llave pública (asimétrica)
 Algoritmos de cifrado
 Definir el problema con este tipo de cifrado
 Firmas digitales
 Sobres digitales
 Certificado digital

 Autoridad certificadoras

Definición de Criptografía
 La criptografía proviene del griego kryptos:
"ocultar", y grafos: "escribir". Es decir,
significa "escritura oculta". Como concepto
son las técnicas utilizadas para cifrar y
descifrar información utilizando técnicas
matemáticas que hagan posible el
intercambio de mensajes de manera que
sólo puedan ser leídos por las personas a
quienes van dirigidos.

Esquema de cifrado simétrico

Los sistemas criptográficos  se 
clasifican en:

a) El número de claves usadas
b) El tipo de operación utilizado para
transformar el texto claro en texto cifrado
La forma de procesar el texto claro

c)

El número de claves usadas
 Si tanto el emisor como el receptor usan la
misma clave, el sistema se denomina
simétrico, de clave única, de clave secreta o
cifrado convencional. En cambio, si el
emisor y el receptor usan cada uno claves
diferentes, el sistema se denomina
asimétrico, de dos claves o cifrado de clave
pública.

El tipo de operación utilizado para 
transformar el texto claro en texto 
cifrado
 Todos los algoritmos de cifrado se basan en
dos principios: sustitución* y transposición*.
Lo fundamental es que todas las
operaciones sean inversas (descifrar).

La forma de procesar el texto claro

 Un cifrador de bloques procesa un bloque

de elementos cada vez, produciendo un
bloque de salida por cada bloque de
entrada. Un cifrador de flujo procesa los
elementos de entrada continuamente,
produciendo la salida de un elemento cada
vez.

Criptoanálisis
 Es el proceso por el que se intenta descubrir

un texto claro o una clave de cifrado. La
estrategia usada por el criptoanalista
depende de la naturaleza del esquema de
cifrado y de la información disponible.

Ataque de fuerza bruta 
 Implica intentar cada clave posible hasta
que se obtenga la traducción legible del
texto cifrado al texto claro
 Como promedio, se debe intentar la mitad
de todas las claves posibles para conseguir
descubrirla

Tiempo medio para la búsqueda 
exhaustiva de claves
Tamaño de 
clave (bits)

Número de 
claves 
alternativas

Tiempo 
necesario a 1 
cifrado/µs

Tiempo 
necesario a 106 
cifrado/µs

32

56

128

168

232 = 4,3 x 109

256 = 7,2 x 1016

2128 = 3,4 x 1038

2168 = 3,7 x 1050

231 µs = 35,8 
minutos
255 µs = 1.142 
años
2127 µs = 5,4 x 
1024 años
2167 µs = 5,9 x 
1036 años

2,15 
milisegundos
10,01 horas

5,4 x 1018 años

5,9 x 1030 años

Esquema de cifrado simétrico

DES (Data Encryption Standard)
 El texto en claro tiene una longitud de 64 bits y la
clave de 56; si el texto es más largo se procesa en
bloques de 64 bits.
 El cifrado y descifrado de cada bloque de 64 bits es
realizado mediante:
 Permutaciones de bits
 Sumas binarias tipo XOR entre los datos y la llave secreta
 Funciones de sustitución que mediante tablas fijas

mapean un grupo de bits a un grupo de bits diferente.

DES (Data Encryption Standard)

Estructura de los algoritmos de C.S. 
incluido el DES
 16 etapas de proceso.
 Se generan 16
subclaves partiendo de
la clave original de 56
bits, una para cada
etapa

Descifrado 
 El proceso de descifrado del DES es

básicamente el mismo que el de cifrado.
Simplemente se utiliza el texto cifrado como
entrada al algoritmo del DES, pero las
subclaves Ki se pasan en orden inverso. Es
decir, en la primera etapa se usa K16, K15 en
la segunda y así hasta K1 en la 16ª y última
etapa.

Robustez del DES
 Se engloba en dos aspectos:

 Aspectos sobre el algoritmo mismo (nadie ha conseguido
descubrir ninguna debilidad grave en el DES)
 Aspectos sobre el uso de una clave de 56 bits (con dicha
clave, existen 256 claves posibles, no parece práctico un
ataque por fuerza bruta, ya que en promedio se intenta la
mitad del espacio de claves, una única máquina que
realice un cifrado por microseg. Tardaría más de mil años
en romper el cifrado)

DES ­­ no seguro
 En 1998 la Electronic Frontier Foundation (EFF)

anunció que había roto un cifrado DES utilizando
una máquina especializada <<DES cracker>>. La
EFF ha publicado la descripción detallada de la
máquina, haciendo posible que cualquiera
construya su propio cracker.
cifrado es la fuerza bruta, entonces se necesitan
usar claves más largas.

 Si la única forma de ataque a un algoritmo de

Cracker de la EFF suponiendo 1 
millón de descifrados por µs

Triple DES
 El 3DES usa tres claves y tres ejecuciones del

algoritmo DES. La función sigue la secuencia cifrar-
descifrar-cifrar.

C = EK3 [ DK2 [ EK1[P]]]

Donde:

C = texto cifrado
P = texto claro
EK[X] = cifrado de X usando la clave K
DK[Y] = descifrado de Y usando la clave K

Descifrado.­ misma operación con las claves en 
orden inverso
 P = DK1 [ EK2 [ DK3[C]]] 

Robustez del 3DES
 Con tres claves diferentes, el 3DES tiene una

longitud efectiva de clave de 168 bits. También se
permite el uso de dos claves, con K1 = K3, lo que
proporciona una longitud de clave de 112 bits.
 Con una clave de 168 bits de longitud, los ataques
de fuerza bruta son efectivamente imposibles
 Único inconveniente es que tiene 3 veces más
etapas que el DES y por ello 3 veces más lento.

Algoritmos de cifrado 
convencional

Problemas con los sistemas de clave 
simétrica 
 El problema principal de seguridad consiste
en mantener la privacidad de la clave
 Así como la distribución de la misma.

Criptografía de llave pública
 Los algoritmos de clave pública están

 Esta criptografía es asimétrica, lo que

basados en funciones matemáticas y no en
simples operaciones sobre los patrones de
bits.
implica el uso de dos claves separadas (una
clave pública y otra privada) y no solo de
una como en la criptografía simétrica

Claves
 Como los nombres lo sugieren, la clave
pública de dicha pareja de claves se hace
pública para que los otros la usen, mientras
que la clave privada sólo es conocida por su
propietario. Un algoritmo criptográfico de
clave pública con propósito general se basa
en una clave para el cifrado y otra diferente,
aunque relacionada para el descifrado

Criptografía de llave pública

Confusiones comunes
 El cifrado de clave pública es más seguro

ante el criptoanálisis que el cifrado
convencional (falso)
 La seguridad de cualquier esquema de cifrado
depende de la longitud de la llave. No hay nada
sobre el cifrado simétrico ni de clave pública que
haga a uno superior al otro en lo que respecta a
la resistencia al criptoanálisis.

 La idea que el cifrado de clave pública ha
dejado desfasado el cifrado convencional
(falso)
 Por el contrario, debido al coste computacional
de los esquemas actuales de cifrado de clave
pública, no parece que el cifrado simétrico vaya a
abandonarse.
 Se piensa que es más sencillo la distribución

de llaves
 Se necesita de alguna autoridad certificadora
para validar las claves públicas

Los pasos fundamentales son los 
siguientes:
 Cada usuario genera un par de llaves
 Localiza una de las dos claves en un registro

 Si Benito quiere enviar un mensaje privado a Alicia,
 Cuando Alicia recibe el mensaje, lo descifra usando

público u otro archivo accesible. Esta es la clave
pública.
cifra el mensaje usando la clave pública de Alicia.
su clave privada. Ningún otro receptor puede
descifrar el mensaje porque sólo Alicia conoce su
clave privada.

Requisitos para la criptografía de clave 
pública
 Desde el punto de vista computacional, para
una parte B es fácil generar una pareja de
claves (pública KUb, privada KRb)
 En términos computacionales, para un
emisor A que conozca la clave pública y el
mensaje que ha de cifrarse, M, es fácil
generar el texto cifrado:

C = EKUb(M)

 Desde el punto de vista computacional, es
imposible que un oponente, conociendo la
clave pública KUb, determine la clave privada
KRb.
 Desde el punto de vista computacional, es
imposible que un oponente, conociendo la
clave pública, KUb, y un texto cifrado, C,
recupere el mensaje original, M.
 Cualquiera de las claves relacionadas puede
usarse para el cifrado, y la otra para el
descifrado
M = DKRb [EKUb(M)] = DKUb [EKRb(M)]

Generación de claves

d Inverso multiplicativo de 
e

Ejemplo del RSA
1.- Seleccionar dos números primos, p = 17 y
q = 11.
2.- Calcular n = pq = 17 x 11 = 187
3.- Calcular Ф(n)=(p - 1) (q - 1)=16x10 = 160
4.- Seleccionar e tal que sea primo relativo de
Ф(n)=160 y menor a Ф(n); e = 7.
5.- Determinar d tal que de mod 160 = 1 y
d<160. El valor es d=23, porque 23x7 =
161 = 10x160+1
* Por lo que KU = {7,187} y KR={23,187}

Algoritmo de clave pública 
RSA
Tanto el emisor como el receptor deben
conocer los valores de n y e, y sólo el
receptor conoce el valor de d. Por tanto:
KU = {e, n} y KR = {d, n}
de texto cifrado C, el cifrado y descifrado
son de la siguiente forma:
M = Cd mod n = (Me)d mod n = Med mod n

 Para un bloque de texto claro M y un bloque

C = Me mod n

Ejemplo 

KU = {e, n}

KR = {d, n}

Por las propiedades de la aritmética 
modular se tiene que:

187)x(881 mod 187)] mod 187

887 mod 187 = [(884 mod 187)x(882 mod
881 mod 187 = 88
882 mod 187 = 7744 mod 187 = 77
884 mod 187 = 59,969,536 mod 187 = 132
887 mod 187 = (88x77x132) mod 187 = 11

Y para calcular M = 1123 mod 187
187)x(114 mod 187) x(118 mod 187)

1123 mod 187 = [(111 mod 187)x(112 mod
x(118 mod 187)] mod 187
111 mod 187 = 11
112 mod 187 = 121
114 mod 187 = 14,641 mod 187 = 55
118 mod 187 = 214,358,881 mod 187 = 33
1123 mod 187 = (11x121x55x33x33) mod
187 = 79,720,245 mod 187 = 88

Robustez del RSA
 Cuanto mayor sean los números e y d, más seguro
será el algoritmo. Sin embargo debido a los
cálculos que tienen lugar tanto