1.2. Generación de la
subclave Ki
La clave Ki tiene un valor inicial
de 64 bits, su longitud es fija.
Tabla de 56 bits | |||||||||||||
1 | 2 | 3 | 4 | 5 | 6 | 7 | |||||||
9 | 10 | 11 | 12 | 13 | 14 | 15 | |||||||
17 | 18 | 19 | 20 | 21 | 22 | 23 | |||||||
25 | 26 | 27 | 28 | 29 | 30 | 31 | |||||||
33 | 34 | 35 | 36 | 37 | 38 | 39 | |||||||
41 | 42 | 43 | 44 | 45 | 46 | 47 | |||||||
49 | 50 | 51 | 52 | 53 | 54 | 55 | |||||||
57 | 58 | 59 | 60 | 61 | 62 | 63 | |||||||
Tabla de 64 bits Inicial | |||||||||||||
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ||||||
9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | ||||||
17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | ||||||
25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | ||||||
33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | ||||||
41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | ||||||
49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | ||||||
57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 |
Permutación PC1 | ||||||
57 | 49 | 41 | 33 | 25 | 17 | 9 |
1 | 58 | 50 | 42 | 34 | 26 | 18 |
10 | 2 | 59 | 51 | 43 | 35 | 27 |
19 | 11 | 3 | 60 | 52 | 44 | 36 |
63 | 55 | 47 | 39 | 31 | 23 | 15 |
7 | 62 | 54 | 46 | 38 | 30 | 22 |
14 | 6 | 61 | 53 | 45 | 37 | 29 |
21 | 13 | 5 | 28 | 20 | 12 | 4 |
La tabla de la Permutación PC1, se utiliza para
realizar la permutación inicial en la generación de
la subclave Ki , para cada vuelta. Una vez realizada
la permutación, los 56 bits se dividen en dos
sub-bloques
Ci y Di de 28 bits. En estas
condiciones, la clave esta definida por las ecuaciones:
Ci = LS
(Ci-1) Di = LS(Di
-1)
Ki = PC2 (Ci ,
Di)
Ejemplo Permutación
PC1
Clave K: Santiago
Decimal | Carácter | Binario | |
97 | a | 01100001 | |
103 | g | 01100111 | |
105 | i | 01101001 | |
110 | n | 01101110 | |
111 | o | 01101111 | |
83 | S | 01010011 | |
116 | t | 01110100 | |
S | 01010011 | ||
a | 01100001 | ||
n | 01101110 | ||
t | 01110100 | ||
i | 01101001 | ||
a | 01100001 | ||
g | 01100111 | ||
o | 01101111 |
Utilizando la Permutación PC1
obtenemos:
Tabla de 64 bits de Ki | |||||||
0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
Tabla de 56 bits | |||||||
0 | 1 | 0 | 1 | 0 | 0 | 1 | |
0 | 1 | 1 | 0 | 0 | 0 | 0 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | |
0 | 1 | 1 | 1 | 0 | 1 | 0 | |
0 | 1 | 1 | 0 | 1 | 0 | 0 | |
0 | 1 | 1 | 0 | 0 | 0 | 0 | |
0 | 1 | 1 | 0 | 0 | 1 | 1 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 |
Permutación PC1 | ||||||
0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 1 | 0 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 0 | 1 | 0 |
1 | 1 | 1 | 0 | 0 | 1 | 1 |
0 | 0 | 1 | 0 | 0 | 1 | 0 |
1 | 0 | 0 | 1 | 0 | 0 | 1 |
Sub-bloque C0 = 0000000
0111111 1111111 1100000
Sub-bloque D0 = 1100010
1110011 0010010 1001001
Sub-bloques iniciales
1.2.1. Desplazamiento
LS(…)
El desplazamiento LS(…) se aplica a los
sub-bloques de longitud fija de 7 bits (Ci y
Di), donde LS(…) es un desplazamiento
circular a la izquierda de 1 o 2 bits del entero binario que toma
el argumento de acuerdo a la siguiente tabla:
Vuelta | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
No. Bits desplazados. Izda. | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 1 |
Con el propósito de comprender mejor el
desplazamiento LS(…) se realizara el proceso.
Ejemplo Permutación
LS(..)
Al tener los sub-bloques C0 y
D0, el siguiente paso es el desplazamiento LS,
se marcan los dos primeros bits, con el propósito de
poder
identificar el resultado del desplazamiento.
Sub-bloque C0 =
0000000 0111111 1111111
1100000
Sub-bloque D0 =
1100010 1110011 0010010
1001001
Al ser la primer vuelta, el desplazamiento es de un bit
a la izquierda como se indica en la tabla, dando como resultado
C1 y D1.
Sub-bloque C1 = 0000000
1111111 1111111 1000000
Sub-bloque D1 = 1000101
1100110 0100101 0010011
Sub-bloques después del
desplazamiento LS(..)
1.2.2. Permutación PC2
La permutación PC2 se
conoce como permutación de compresión, dada por las
operaciones de
concatenar y permutar Ci y Di, se va a
comprimir de 56 bits a 48 bits para obtener la clave
Ki, posteriormente será utilizada en la
función
(f(Ri-1, Ki))
El orden de concatenar Ci y Di, es
utilizando primero los 28 bits de Ci y posteriormente
los 28 bits de Di, la tabla PC2 es una tabla de 8 x 6,
dando como resultado 8 bloques de 6 bits.
Tabla ( Ci, | ||||||
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 | 32 | 33 | 34 | 35 |
36 | 37 | 38 | 39 | 40 | 41 | 42 |
43 | 44 | 45 | 46 | 47 | 48 | 49 |
50 | 51 | 52 | 53 | 54 | 55 | 56 |
Tabla de 8 x 6 bits | ||||||
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | |
13 | 14 | 15 | 16 | 17 | 18 | |
19 | 20 | 21 | 22 | 23 | 24 | |
25 | 26 | 27 | 28 | 29 | 30 | |
31 | 32 | 33 | 34 | 35 | 36 | |
37 | 38 | 39 | 40 | 41 | 42 | |
43 | 44 | 45 | 46 | 47 | 48 |
Permutación PC2 | |||||
14 | 17 | 11 | 24 | 1 | 5 |
3 | 28 | 15 | 6 | 21 | 10 |
23 | 19 | 12 | 4 | 26 | 8 |
16 | 7 | 27 | 20 | 13 | 2 |
41 | 52 | 31 | 37 | 47 | 55 |
30 | 40 | 51 | 45 | 33 | 48 |
44 | 49 | 39 | 56 | 34 | 53 |
46 | 42 | 50 | 36 | 29 | 32 |
Ejemplo Permutación
PC2
Continuando con el ejemplo se mostrará el proceso
utilizado en la permutación PC2, para obtener la clave
Ki.
Concatenando Ci,
Di
0000000 1111111 1111111 1000000
1000101 1100110 0100101 0010011
Los 56 bits de entrada en la
permutación PC2
Para ver la tabla seleccione la
opción "Descargar" del menú
superior
El resultado de haber realizado la permutación
PC2 es la generación de la clave K1
siendo:
K1 = PC2 (C1,
D1) =
111000 001011 011001 100110 110111
010010 110100 000110
Clave K1
Las operaciones LS(..) y PC2, se repiten 15 veces
para así obtener las 15 subclaves de cifrado restantes.
Los procesos de
cifrado y generación de claves se representan
esquemáticamente en la siguiente imagen.
Al tener la clave Ki y la expansión de
(R0), el siguiente paso es la función
f(Ri-1 , Ki), la cual consta de tres
procesos (Suma OR exclusivo, ocho funciones no
lineales, Permutación P), siendo las ocho funciones
lineales la mayor virtud del algoritmo, se
han propuesto modificaciones en varios procesos, pero cualquier
modificación realizada, en las funciones lineales hace
débil al algoritmo. A continuación se explican los
procesos.
Con la clave Ki y E(Ri-1), se
procede a realizar la suma OR exclusiva, al realizar la
operación se tiene un 50% de certeza que el siguiente bit
sea 1, con lo cual aumenta la dificultad de poder descifrar el
mensaje. La operación OR exclusiva se ejemplifica en la
siguiente tabla:
A | B | A B |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Se encuentra definido por la ecuación.
E(Ri-1) Ki
La clave Ki y Ri-1 se encuentra
formado por 8 bloques de 6 bits cada, con lo cual es posible
realizar la suma OR exclusiva como se muestra a
continuación.
Ejemplo Suma OR
exclusiva
Retomando los bits de la expansión del sub-bloque
R0 y la subclave K1, se procede a realizar
la suma OR exclusiva.
E(R0) = 000000 000001
011111 111101 011001 011001 010000 001000
K1 = 111000 001011 011001
100110 110111 010010 110100 000110
111000 001010 000110 011011 101110
001011 100100 001110
Resultado de la suma OR exclusiva
E(R0) K1
1.3.2. Funciones no lineales
La cadena de bits obtenida de la suma OR exclusiva, se
subdivide en 8 bloques de 6 bits, como se puede apreciar en el
ejemplo anterior, siendo cada bloque
(b6b5b4b3b2b1)
la entrada a una de las funciones no lineales, conocidas como
cajas, el resultado de la operación es un numero
con valor entre 0 a 15, representado con cuatro bits,
concatenados forman una cadena de 32 bits, la cual será la
entrada para la permutación P. La posición de los
bits dentro de cada caja se encuentra definida por la fila
b6b1 y la columna
b5b4b3b2 de la caja,
el orden de los valores
numéricos de las cajas se puede ver en la siguiente
imagen.
Ejemplo función no lineal
(cajas)
E(R0) K1 =
111000 001010
000110 011011
101110 001011
100100 001110
En la Caja S1 se utiliza el primer
bloque 111000, en la Caja S2 se utiliza
el segundo bloque y así sucesivamente.
Para ver la tabla seleccione la
opción "Descargar" del menú superior
La salida del bloque 1 es: 3 (0011), el procedimiento se
repite en las siguientes 7 cajas obteniendo como
resultado:
E(R0) K1 = 0011 1011
1110 1010 1000 1100 1011 0001
3 11 14 10 8 12 11 1
Resultado de las funciones no
lineales
1.3.3. Permutación P
El ultimo paso de la función
f(Ri-1 , Ki), es una
permutación P, cuyo resultado se sumara con la salida del
sub-bloque Li, dando origen a la entrada del
sub-bloque Ri
Para ver la tabla seleccione la
opción "Descargar" del menú superior
Ejemplo Permutación P
Retomando el ejemplo se realiza el ultimo paso de la
f(Ri-1 , Ki), recordando que dicho
proceso se repite 15 veces.
E(R0) K1 = 0011 1011
1110 1010 1000 1100 1011 0001
Resultado de las funciones no
lineales
Para ver la tabla seleccione la
opción "Descargar" del menú superior
El registro de bits
obtenido por la función f(Ri-1 ,
Ki), es sumado con un OR exclusivo con el registro de
bits de L0, dando como resultado la entrada para el
siguiente sub-bloque de Ri. El registro de bits
realizado en la permutación inicial P1, que origino al
sub-bloque R0, es la entrada para el siguiente
sub-bloque Li, el proceso se repite 15 veces, siendo
el ultimo proceso la permutación
P1-1.
Ejemplo Suma Li f(Ri-1 ,
Ki)
f(Ri-1 , Ki) = 0101
0011 0100 1001 0100 1111 0100 1111
L0 = 1111 1111 0001 1000 1101 0111 1110
1010
1010 1100 0101 0001 1001 1000 1010
0101
Resultado de la suma OR exclusiva L0 f(R0 ,
K1)
Obteniendo los registros de 32
bits para el siguiente sub-bloque Li y Ri
como se muestra a continuación:
L1 = 0000 0000 1111 1110 1100 1100 1000
0100
R1 = 1010 1100 0101 0001 1001 1000 1010
0101
Donde se verifican las ecuaciones:
L1 = R0
00000000111111101100110010000100 =
00000000111111101100110010000100
R1 = L0 f(R0 ,
K1)
10101100010101011001100010100101
=
1111111100011000110101111110101001010011010011010100111101001111
La permutación inversa se define por la siguiente
tabla, siendo la salida, el cifrado del mensaje.
Para ver la tabla seleccione la
opción "Descargar" del menú superior
Ejemplo Permutación
P1-1
Si tomamos los valores que
tenemos de L1 y R1, suponiendo los valores
de L16 y R16, podemos realizar el
procedimiento, como muestra del resultado final, cabe mencionar
si el mensaje es mayor de 64 bits, se utilizan los bloques
necesarios para dividir el mensaje original, si un bloque formado
por un mensaje, no tiene la longitud de 64 bits, se rellena
utilizando 0.
L16 = 10101100 01010001 10011000
10100101
R16 = 00000000 11111110 11001100
10000100
Concatenando L16 ,
R16
10101100 01010001 10011000 10100101
00000000 11111110 11001100 10000100
Para ver la tabla seleccione la
opción "Descargar" del menú superior
El cifrado del mensaje es:
◄(spacio){l4a8o
00010001 00100000 01101011 01101100
00110100 01100001 00111000 01101111
Decimal | Carácter | Binario |
17 | ◄ | 00010001 |
32 | (space) | 00100000 |
123 | { | 01111011 |
108 | l | 01101100 |
52 | 4 | 00110100 |
97 | a | 01100001 |
56 | 8 | 00111000 |
111 | o | 01101111 |
1.6. Descifrado
El algoritmo se utiliza para obtener el mensaje
original, con un sentido inverso al inicial, esto es, empezando
con la entrada del mensaje cifrado de 64 bits, aplicando la
permutación P1, dividir el mensaje en dos sub-bloques
L16 y R16, teniendo la subclaves calculadas
previamente, se realiza el procedimiento descrito anteriormente
la f(Ri-1 , Ki), realizando las 16
vueltas hasta obtener el mensaje en claro.
Ejemplo Permutación P1
Descifrado
Mensaje a Descifrar =
◄(spacio){l4a8o
Para ver la tabla seleccione la
opción "Descargar" del menú
superior
L16 = 10101100 01010001
10011000 10100101
R16 = 00000000 11111110
11001100 10000100
Ejemplo Permutación E
Descifrado
Al tener la secuencia de R16 de 32 bits, es
necesario aplicar la permutación E, la cual se muestra a
continuación.
R16 = 00000000 11111110
11001100 10000100
Para ver la tabla seleccione la
opción "Descargar" del menú superior
E(R16) = 000000 000001
011111 111101 011001 011001 010000 001000
Ejemplo Suma OR exclusiva
Descifrado
La suma OR exclusiva se realiza utilizando la ultima
clave generada (K16), en nuestro ejemplo utilizaremos
la clave K1, como la clave K16.
E(R16) = 000000 000001 011111 111101
011001 011001 010000 001000
K16 = 111000 001011 011001 100110 110111
010010 110100 000110
111000 001010 000110 011011 101110 001011 100100
001110
Resultado de la suma OR exclusiva
E(R16) K16
Ejemplo función no lineal
(cajas) Descifrado
E(R0) K1 = 111000
001010
000110
011011
101110
001011
100100
001110
Como resultados de las operaciones no
lineales (cajas) tenemos los siguientes:
E(R0) K1 = 0011 1011
1110 1010 1000 1100 1011 0001
3 11 14 10 8 12 11 1
Resultado de las funciones no
lineales
Ejemplo Permutación P
Descifrado
Retomando el ejemplo se realiza el ultimo paso de la
f(Ri-1 , Ki), recordando que dicho
proceso se repite 15 veces mas.
E(R0) K1 = 0011 1011
1110 1010 1000 1100 1011 0001
Para ver la tabla seleccione la
opción "Descargar" del menú superior
Ejemplo Suma Li f(Ri-1 ,
Ki) Descifrado
f(Ri-1 , Ki) = 0101
0011 0100 1001 0100 1111 0100 1111
L16 = 1010 1100 0101 0001 1001 1000
1010 0101
1111 1111 0001 1000 1101 0111 1110
1010
Resultado de la suma OR exclusiva L0
f(Ri-1 , Ki)
Obteniendo los registros de 32 bits para el siguiente
sub-bloque Li y Ri como se muestra a
continuación:
L15 = 0000 0000 1111 1110 1100 1100 1000
0100
R15 = 1111 1111 0001 1000 1101 0111 1110
1010
Donde se verifican las ecuaciones:
L15 =
R16
00000000111111101100110010000100 =
00000000111111101100110010000100
R1 = L16 f(R16 ,
K16)
11111111000110001101011111101010
=
1010110001010001100110001010010101010011010010010100111101001111
Ejemplo Permutación
P1-1 Descifrado
Si tomamos los valores que tenemos de L1 y
R1, suponiendo los valores de L16 y
R16, podemos realizar el procedimiento, como muestra
del resultado final, cabe mencionar si el mensaje es mayor de 64
bits, se utilizan los bloques necesarios para dividir el mensaje
original, si un bloque formado por un mensaje y este no tiene la
longitud de 64 bits, se rellena utilizando 0.
L1 = 1111 1111 0001 1000 1101 0111 1110
1010
R1 = 0000 0000 1111 1110 1100 1100 1000
0100
Concatenando L1 y R1, da como
resultado:
11111111 00011000 11010111
11101010 00000000 11111110 11001100
10000100
Para ver la tabla
seleccione la opción "Descargar" del menú
superior
En la siguiente sección se
definirán, los ataques activos y
pasivos, se mencionarán los ataques al algoritmo
DES.
2.Ataques a la seguridad
criptográfica
La seguridad criptográfica sufre, dos tipos de
ataques pasivosIII y activosIV, la
finalidad de realizar un ataque pasivo, es obtener información y evitar ser detectado, a
diferencia de los ataques activos, cuya finalidad es captar la
información, modificarla, obtener claves, entre otras
actividades no legales.
Los ataques activos se dividen en Ataques a los
Operadores Criptográficos y Ataques a los protocolos, a
continuación se mencionan algunos ataques a los operadores
criptográficos.
- Ataque a partir del cifrado: El atacante tiene
acceso al texto
cifrado y de ahí trata de encontrar la clave
secreta. - Ataque a partir del texto en claro: El atacante
tiene acceso al texto en claro y al cifrado con los cuales
intenta obtener la clave secreta. - Ataque a partir del texto en claro elegido: El
atacante puede elegir un texto en claro y su
cifrado. - Ataque a partir de texto en claro condicionado: El
atacante puede elegir un texto en claro condicionado a los
cifrados previamente obtenidos.
- Ataque con clave conocida: El atacante obtiene
algunas claves utilizadas en cifrados previos para determinar
nuevas claves. - Reutilización del protocolo:
El atacante, ataca utilizando una comunicación captada previamente,
insertándola en la
comunicación. - Suplantación de Identidad:
El atacante toma la identidad de un usuario registrado en la
red de
comunicaciones.
Otros ataques.
- Ataque de fuerza
bruta: El ataque por fuerza bruta consiste en un ejercicio de
combinación, donde se van cifrando todas las posibles
contraseñas y comparándolas con las existentes
en el registro, buscando también coincidencias. Este
método, por definición, siempre
consigue su meta, si bien el problema que tienen es de
recursos y
tiempo.
2.1 Ataques al Algoritmo DES
Criptoanálisis Diferencial
El criptoanálisis diferencial fue introducido por
E. Biham y A. Shamir, es un ataque en texto claro escogido y esta
basado en comparaciones del OR exclusivo de dos textos en claro
escogidos con el OR exclusivo de sus correspondientes cifrados.
Este método de análisis permite romper el DES utilizando
en teoría
alrededor de 247 parejas de textos en claro
seleccionados, siendo aproximadamente 236 las
útiles para el criptoanálisis, con un tiempo de
calculo equivalente a unos 237 cifrados. El problema
básico de este ataque es obtener los cifrados de los
textos en claro, ya que para obtenerlos es necesario
engañar a la entidad que realiza el cifrado o violar la
seguridad física
del lugar donde se realiza el cifrado, lo cual en la practica es
casi imposible.
Criptoanálisis Lineal
El criptoanálisis lineal fue introducido por M.
Matsui, se basa en un ataque en texto en claro escogido y
consiste en la obtención de ecuaciones lineales que
representen la probabilidad
existente entre algunos bits del mensaje en claro y otros del
cifrado DES del mismo mensaje. La ecuación utilizada es la
siguiente:
F(P[i1,…ip] ,
C[j1,…jp]) = k[k1,
k2,…kk]
Donde F(…) es una función lineal y
[i1,…ip]
,[j1,…jp]) ,[k1,
k2,…kk] son bits que ocupan
posiciones fijas respectivamente en P, C y K.
http://csrc.nist.gov/cryptval/des.htm
http://cereal.rutgers.edu/~xylu/519_hw4.html
http://www.infoworld.com/article/04/07/29/HNdesinadequate_1.html
Criptografía Digital Fundamentos y
Aplicaciones
José Pastor Franco, Miguel Ángel Sarasa
López
2da, Edición
Rafael Martinez
Página anterior | Volver al principio del trabajo | Página siguiente |