Ejercicios DES

e) En un sistema DES en la caja S1 se tiene como entrada la siguiente cadena de bits: 101110. ¿Qué secuencia de bits es la salida de dicha caja S1?

Sol: Como los bits de entrada a la caja S1 son 101110, separamos estos dígitos para buscar filas y columnas: los dígitos de los extremos (1....0) nos entregan la fila y los cuatro dígitos centrales (..0111..) la columna en dicha caja. Fila: 102 = 210 Fila 2; Columna: 01112 = 710 Columna 7Según las tablas de Cajas S, en caja S1 la intersección de fila 2 y columna 7 entrega el número 11 que pasado a notación binaria es: 1011.Luego, la secuencia de salida de la caja S1 es: 1011.

3. Al cifrar el bloque de texto M = ¿BUENOS? con una determinada clave K mediante el sistema DES, se obtiene como resultado que la entrada a las cajas S es una cadena de 48 bits que pueden representarse por los siguientes valores en hexadecimal: A4 E2 DF EF 8C D4. Se pide:a) Indicar la salida de cada una de las cajas S en decimal.b) ¿Cuántos bits hay en total a la salida de las cajas S?c) ¿Qué mensaje ASCII sale de las cajas S si agrupamos la salida en 8 bits?

Solución:a) En binario la entrada a las cajas S será: A4 = 1010 0100; E2 = 1110 0010;

DF = 1101 1111; EF = 1110 1111; 8C = 1000 1100; D4 = 1101 0100.Luego en las cajas S entran los siguientes 6 bits:S1 = 101001; S2 = 001110; S3 = 001011; S4 = 011111;S5 = 111011; S6 = 111000; S7 = 110011; S8 = 010100.Por lo tanto la salida de cada caja S será:S1 = 4; S2 = 4; S3 = 4; S4 = 9; S5 = 4; S6 = 1; S7 = 5; S8 = 3.

b) El número total de bits de salida de las cajas S será 32, correspondientes a los valores de Si, es decir: S = 0100 0100 0100 1001 0100 0001 0101 0011.

c) Agrupando S en bloques de 8 bits obtenemos los siguientes valores decimales: 68 73 65 83 (44 49 41 53 en hexadecimal) que en ASCII se corresponden con la cadena de caracteres DIAS.

5. ¿Se puede firmar digitalmente un mensaje con el algoritmo Data Encryption Standard, DES? Si es así, ¿cómo lo haría y por qué?

Solución: No. Es imposible firmar digitalmente un

mensaje con el algoritmo DES pues se trata de un método

de clave privada y es, por tanto, una función simétrica

que no posee inversa. La firma digital debe contemplar

siempre dos valores inversos entre sí en el módulo de

trabajo del transmisor y firmante del mensaje, de forma

que éste firme con su clave privada (que permite la

autenticidad) y el destinatario pueda comprobar dicha

firma con la clave pública, inversa de la anterior.

2. En el cifrador IDEA se utilizan tres operaciones algebraicas sobre cadenas de 16 bits: suma módulo 2, suma módulo 216 y producto módulo 216+1.

a) ¿Por qué se hace la multiplicación en módulo 216+1 y no en 216? ¿Cómo se obtiene la tabla de multiplicación?

b) Compruebe la operación producto XY para 3 bits para X=2 y el valor de Y igual a todos los restos de 23. ¿Cuál es el inverso de 2 en 23+1?

Solución:2a) Todas las operaciones algebraicas deben tener inversa. Es el caso de las dos sumas. En cambio si el cuerpo de la multiplicación es 216 no se obtienen todos los restos y por lo tanto no se asegura la existencia de inverso. Si el módulo es 216 +1 y se considera que el bloque de 16 ceros es igual al número 216 = 65.536, se obtiene para cada multiplicación el conjunto completo de restos y por tanto la existencia de un único inverso para cada valor. La tabla del producto XY (números de 16 bits cada uno) se obtiene haciendo la multiplicación en decimal o binario de todos los posibles valores de X e Y en el cuerpo 216 (0, …, 65.535) considerando que 0 = 65.536 y reduciendo todas las operaciones en módulo 216+1.

2b) Cálculo de XY mod 23+1 = 2Y mod 9. Se supone 0 = 23 = 8.X Y X Y XY mod 216+1 Cálculo Valor010 000 2 0 28 mod 9 16 mod 9 7010 001 2 1 21 mod 9 2 mod 9 2010 010 2 2 22 mod 9 4 mod 9 4010 011 2 3 23 mod 9 6 mod 9 6010 100 2 4 24 mod 9 8 mod 9 0010 101 2 5 25 mod 9 10 mod 9 1010 110 2 6 26 mod 9 12 mod 9 3010 111 2 7 27 mod 9 14 mod 9 5

El inverso de 2 en 23+1 es inv(2,9) = Y = 5 pues el resultado es igual a la unidad. No obstante, no cumple la condición de cuerpo de cifra 2n+1ya que 9 no es primo. De hecho, no existirán inversos parea los valores 3 y 6 lo que no tiene sentido.

3. En una vuelta del algoritmo DES entra en las Cajas S la siguiente cadena de 48 bits: S = 01110010 00001100 11001011 01101011 00100110 11111000. Si los bits más significativos afectan a la caja S1 y así sucesivamente, se pide:

a) Indicar para cada caja S la entrada en bits, la fila y columna dentro de ella para obtener el valor de salida y la salida en decimal.

b) ¿Cuál es la cadena completa de bits de salida en esta fase del DES en octetos?

Solución:2b) Pasando a binario esta cadena de bits se tiene la siguiente salida en octetos:S = 00000000 11111111 00000000 11111111

CAJA ENTRADA FILA COLUMNA SALIDAS1 011100 0 14 0S2 100000 2 0 0S3 110011 3 9 15S4 001011 1 5 15S5 011010 0 13 0S6 110010 2 9 0S7 011011 1 13 15S8 111000 2 12 15

Ejercicio práctico nº 3: (2.0 puntos. Tiempo Recomendado: 45 minutos)

Firmar digitalmente el mensaje del punto 2 mediante el algoritmo RSA, usando para ello como función resumen del mensaje en claro el esquema que se indica:

M1 M2 Mn+R

Cajas S Cajas S Cajas S (DES) (DES) ….. (DES)

V0 V1 V2 Vn = r XOR XOR XOR

Mi = Cadenas de seis caracteres de texto en claro.V0 = Vector inicial de 32 bits cuyo valor en hexadecimal es V0 = ABCD 1234.+R = Relleno de bits (todos unos) si el mensaje no es múltiplo de 48 bits.Nota: El valor r se subdivide para su posterior cifra en dos bloques de 16 bits: r1 y r2.

a) Indicar todas las salidas del último bloque (bloque n) de Cajas S en decimal.

b) Si los vectores V1 y V2 son V1 = 0AA5 9FEB y V2 = 647E 9E34, encontrar el valor del resumen r = r1 r2 en decimal.

c) Expresar la ecuación de firma digital a partir del resumen r encontrado en el apartado anterior, sin calcular su valor.

Solución:

a) Aunque en el examen se pide sólo el último bloque, en esta solución se entregará el problema completo. Como el mensaje tiene 17 caracteres, se usarán 3 bloques de cajas S (3 6 = 18) y en la última habrá un relleno de un byte es decir R = 1111 1111.M1 = ESTA_E = 01000101 01010011 01010100 01000001 00100000 01000101M2 = N_EL_C = 01001110 00100000 01000101 01001100 00100000 01000011M3 =ARIBE(+R) = 01000001 01010010 01001001 01000010 01000101 11111111

Los valores de las tres cajas S serán los que se indican en la tabla:

Bloque I

Bloque II

Bloque III

Fila Col. Salida Fila Col. Salida Fila Col. SalidaS1 1 8 10 1 9 6 0 8 3S2 1 10 1 2 1 14 1 10 1S3 1 6 6 1 0 13 1 4 3S4 0 10 8 1 2 11 1 4 6S5 0 8 8 1 9 0 0 8 8S6 0 9 13 0 1 1 2 2 15S7 1 0 13 1 0 13 1 11 12S8 1 2 13 1 1 15 3 15 11

b) Comprobación de los vectores V1 y V2 y cálculo del resumen r. En el examen sólo se pide este último valor.

Salida Bloque I: 1010 0001 0110 1000 1000 1101 1101 1101Vector V0: 1010 1011 1100 1101 0001 0010 0011 0100 (ABCD 1234)Vector V1: 0000 1010 1010 0101 1001 1111 1110 1011 (Suma or exclusivo)Salida Bloque II: 0110 1110 1101 1011 0000 0001 1101 1111Vector V1: 0000 1010 1010 0101 1001 1111 1110 1011 (0AA5 9FEB)Vector V2: 0110 0100 0111 1110 1001 1110 0011 0100 (Suma or exclusivo)Salida Bloque III: 0011 0001 0011 0110 1000 1111 1100 1011Vector V2: 0110 0100 0111 1110 1001 1110 0011 0100 (647E 9E34)Vector V3 = r: 0101 0101 0100 1000 0001 0001 1111 1111 (Suma or exclusivo) Luego: r1 = 0101 0101 0100 1000 = 21.832

r2 = 0001 0001 1111 1111 = 4.607

c) Firma1 = r1dA mod nA = 21.83251.296.042 mod 256.480.209

Firma2 = r2dA mod nA = 4.60751.296.042 mod 256.480.209

Realizando los cálculos (no pedidos en el examen) se obtiene:r1 = 6.152.071r2 = 826.678

Nota: Si no se divide la firma digital en dos partes, el mayor valor posible de la función hash sería 32 bits unos, lo que es igual a 4.294.967.295 que resulta ser mayor que el tamaño del cuerpo de cifra. Con dos trozos de firma de 16 bits cada

uno el mayor valor de cada uno sería 65.535, que ahora es mucho menor que el módulo en cuestión y además muy pequeña por lo que puede dar lugar a muchas colisiones. Ninguna de las dos situaciones son las más indicadas para una firma digital. Lo ideal (y lo que se hace en la práctica) es que el módulo de trabajo sea del orden de los 1.000 bits (1.024 o al menos 512) y el resumen de 128 ó 160 bits.

2) La entrada (IN) de 48 bits representados en hexadecimal de las 8 cajas S de una vuelta del DES es la cadena IN16 = 123456ABCDEF.Preguntas: a) ¿Cuál es la salida de cada una de las cajas S en representación decimal? b) ¿Cuál es la cadena de bits a la salida de esta etapa? ¿Cuál es su representación en hexadecimal?

Solución:

IN = 0001 0010 0011 0100 0101 0110 1010 1011 1100 1101 1110 1111. Agrupando en bloques de 6 bits, IN = 000100 100011 010001 010110 101010 111100 110111 101111. a) En la tabla se muestra las entradas y salidas de cada caja S.b) En la tabla se muestran las salidas en binario y en hexadecimal.

S1 S2 S3 S4 S5 S6 S7 S8

ENTRADA 000100 100011 010001 010110 101010 111100 110111 101111FILA 0 3 1 0 2 2 3 3

COLUMNA 2 1 8 11 5 14 11 7SALIDA10 13 8 2 5 13 11 15 13SALIDA2 1101 1000 0010 0101 1101 1011 1111 1101SALIDA16 D 8 2 5 D B F D

3) Paquito intenta explicar a Eulalia las ventajas de firmar un documento digitalmente a partir del resumen MD5 del mensaje.Preguntas: a) ¿Cómo le explica a Eulalia que es muy difícil que alguien encuentre a partir de ese resumen el mensaje en claro que lo generó? b) ¿Cómo le convence ahora sobre la imposibilidad de que dos mensajes distintos tengan igual resumen?

Solución:

a) Porque la función hash MD5 al ser unidireccional no puede invertirse. Resulta imposible deducir el mensaje a partir de su resumen. La dificultad de encontrar un mensaje a partir de su resumen es del orden de 2128 operaciones.b) Como cada resumen tiene 128 bits y éstos son el resultado de diversas operaciones del algoritmo que entregan como resumen una cadena de bits de carácter casi aleatorio que dependen de cada uno de los bits de entrada, la dificultad de encontrarse con dos mensajes que tengan el mismo resumen es del orden de 264 operaciones. Esto convierte en casi imposible el hecho de que dos mensajes al azar tengan resúmenes iguales. Nota: ambas conjeturas son aceptables; han sido presentadas por Ron Rivest y todavía no se ha demostrado

S1 S2 S3

lo contrario. No obstante MD5 presenta algunos puntos débiles.

Cuestiones de Teoría nº 2 (0.5 pts. Tiempo recomendado 10 minutos)La entrada de 48 bits a las Cajas S en una vuelta DES es en hexadecimal 1FA3 BD81 EF34. Indique la salida de cada una de las cajas S en binario y en hexadecimal.

SOLUCIÓN:La conversión a binario de la entrada en hexadecimal es:1FA3 BD81 EF3416 = 0001 1111 1010 0011 1011 1101 1000 0001 1110 1111 0011 0100Entrada a las Cajas S = 000111 111010 001110 111101 100000 011110 111100 110100

Entrada Caja Si Fila Columna Salida10 Salida2 Salida16

S1 000111 1 3 4 0100 4S2 111010 2 13 3 0011 3S3 001110 0 7 5 0101 5S4 111101 3 14 2 0010 2S5 100000 2 0 4 0100 4S6 011110 0 15 11 1011 BS7 111 100 2 14 9 1001 9S8 110100 2 10 10 1010 A

S2 = 0100 0011 0101 0010 0100 1011 1001 1010; S16 = 4352 4B9A

Cuestiones de Teoría nº 3 (0.5 pts. Tiempo recomendado 10 minutos)Nos dicen que a partir del producto de los polinomios f1(x) = (x2 + x +1) y f2(x) = (x + 1) se obtiene un tipo de generador de secuencia cifrante con registro de desplazamiento y realimentación lineal (LFSR). ¿De qué generador se trata?

SOLUCIÓN:f(x) = f1(x)f2(x) = (x2 + x +1)(x + 1) = (x3 + x2)+(x2 + x)+(x + 1) = x3 + 2x2 + 2x + 1Reduciendo módulo 2 nos queda f(x) = x3 + 1 cuya representación es:

Si

Como no hay suma de los elementos del registro y sólo se realimenta una muestra del bit que sale, simplemente se transmitirá como secuencia la semilla S3S2S1. Esto no es un generador de secuencia cifrante y por lo tanto no pertenece a ningún sistema LFSR.

Cuestiones de Teoría nº 4 (0.5 pts. Tiempo recomendado 10 minutos)En un protocolo de correo seguro basado en S/MIME, un navegador (cliente) de Internet nos ofrece cifrar los mensajes con el algoritmo RC2 (40 bits de clave) y firmar los mismos con RSA y 512 bits de clave, usando MD5 o SHA-1.

a) Justifique esta diferencia en la longitud de las claves.b) A nivel empresarial y particular, ¿está satisfecho con estos valores de clave?c) ¿Qué función hash usaría y porqué?

SOLUCIÓN:a) Es normal y lógico que la longitud de la clave del sistema simétrico (DES,

IDEA, RC2, etc.) sea mucho menor que la del sistema asimétrico (RSA, ElGamal, etc.) con una relación típica de 1/10 aproximadamente. Esto es debido a que son dos tipos de cifra distintos. En la cifra simétrica la fortaleza reside en que en la práctica debe hacerse un ataque por fuerza bruta, en cambio en el ataque a la cifra asimétrica se pueden utilizar distintos algoritmos de factorización o de logaritmo discreto. Podríamos decir que en muchos casos el espacio efectivo de claves es mayor en el primer caso de cifra simétrica al ser los 2n valores equiprobables.

b) Estos valores (que son los que entregan por defecto los clientes Netscape y Explorer para correo electrónico bajo S/MIME fuera de los EEUU) sólo son apropiados para uso personal y en documentos que tengan poco valor comercial o bien cuyo tiempo de caducidad del secreto sea pequeño. Una empresa hoy en día no puede aceptar este nivel tan bajo de seguridad en las claves simétrica y asimétrica. Lo normal son 128 bits mínimo de clave simétrica y 1.024 bits mínimo de clave asimétrica.

c) Puestos a elegir, se usaría SHA-1 pues con 160 bits de resumen ofrece mejor nivel de seguridad que MD5 que sólo tiene 128. Las probabilidades de colisiones son menores y además en MD5 se han detectado últimamente ciertas anomalías y debilidades.

Ejercicio Nº 2: (2.0 pts. Tiempo recomendado 30 minutos)Para el polinomio primitivo f(x) = (x5 + x2 + 1) se pide:a) Dibujar el registro de desplazamiento LFSR si la semilla es S1S2S3S4S5 =

10011. b) Terminar la secuencia cifrante Si y mostrar los estados del registro a partir

de la última posición que se indica: 10101.Si = 11001 10100 10000 10101 ...

c) ¿Qué tipo de secuencia se obtiene y cuál es su período?d) Independientemente de la longitud del registro que en este caso (n = 5) es

muy pequeña, ¿es segura este secuencia para una cifra? Justifíquelo.

SOLUCIÓN:

a)

Si

a) Como los últimos 5 bits transmitidos son 10101 esos serán los bits de la semilla en ese este orden, el primero S5 = 1, luego S4 = 0, luego S3 = 1, luego S2 = 0 y finalmente S1 = 1. Esa será la semilla con la que partimos en la

S1 S2 S3 S4 S5

continuación de la secuencia, que se escribe en bloques de 4 y de arriba hacia abajo.Semilla Bit Si Semilla Bit Si Semilla Bit Si Semilla Bit Si

10101 1 10111 1 00011 1 11110 011010 0 11011 1 10001 1 11111 111101 1 01101 1 11000 0 01111 101110 0 00110 0 11100 0 00111 1Después de 00111 el registro queda cargado como 10011 que

es la semilla inicial.

Luego Si = 11001 10100 10000 10101 11011 00011 1b) Es una m-secuencia al ser generada por un polinomio primitivo y su período es

T = 2n – 1 = 25 – 1 = 32 – 1 = 31. El período es el máximo posible para este número de celdas pues todas las semillas son válidas excepto 00000.c) No es seguro, no importa cuántas celdas tenga el registro, porque se puede

atacar con el algoritmo de Berlekamp-Massey. Con sólo 2n bits de la secuencia (en este caso 10) podemos plantear un sistema de n ecuaciones independientes y encontrar la conexión de las celdas con la función XOR y de esta forma generar la secuencia completa de 2n – 1 bits.

Cuestiones de Práctica nº 1 (0.5 pts. Tiempo recomendado 10 minutos)Nos piden que usemos el algoritmo DES en modo ECB para

cifrar un documento en Word:

a) ¿Es una buena elección? ¿Por qué? Si ahora nos dicen que usemos un cifrado DES múltiple:

b) ¿Se puede hacer? ¿Qué opción elegiría, dos o tres etapas? ¿Por qué?

SOLUCIÓN:a) Es muy mala elección porque al cifrar en modo Libro Electrónico de Códigos,

un mensaje con muchos bloques de 64 bits iguales da origen a bloques de 64 bits de criptograma también iguales. Los archivos con formato (aplicaciones, programas, etc.) poseen muchas y largas cadenas de caracteres ANSI repetidas que dan pistas al criptoanalista al aparecer también en el criptograma. Permite el ataque por repetición de bloque. Debe usarse un modo de cifra con encadenamiento o realimentación.

b) Sí se puede hacer DES múltiple porque, al no formar un grupo, cada cifrado en cascada con una nueva clave no es igual a un cifrado de una sola etapa con una clave resultado de las dos anteriores como sucede, por ejemplo, en Vigenère. En este caso se elige tres etapas, TripleDES, con una clave real de tamaño 2xK.= 112 bits. No se usa el “doble DES” porque permite el ataque denominado “Encuentro a Medio Camino” cuyo efecto es reducir la clave de longitud supuesta 22n bits a sólo 2n+1 bits, es decir una mejora de sólo un bit en la fortaleza de la clave, lo que no tiene sentido.

Ejercicio nº 2: (2.0 puntos. Tiempo recomendado 30 minutos)Se usa parte del algoritmo DES como función resumen de la siguiente manera:

i) El mensaje se divide en bloques de 48 bits (6 bytes).ii) Se añade al final tantos ceros como sea necesario para alcanzar

congruencia módulo 48.iii) Cada bloque de 48 bits constituye la entrada a un sistema estándar

de Cajas S del DES.iv)Las salidas de dichas cajas (32 bits) se van sumando OR exclusivo

hasta el final, entregando por la tanto un resumen de 32 bits.a) Si el mensaje es M = PARA BAILAR ESTO ES UNA BOMBA, encuentre el

resumen de la función.(Continúe la solución entregada en hoja aparte).b) ¿Cumple este algoritmo con la característica de función de un solo sentido

necesaria para el hash? Justifique su respuesta.c) Analice el comportamiento de esta función hash en cuanto a su resistencia

fuerte y débil ante colisiones.

SOLUCIÓN:a) Teníamos un resumen Ri con tres bloques de texto igual a: Ri = 1111 1011 1011 1100 0000 0000 1111 1000. Siguiendo el método: M4 = 010100 110010 000001 010101 010011 100100 000100 100000 (dato dado) M5 = 010000 100100 111101 001101 010000 100100 000100 000000 (dato dado)

Salida de las Cajas S para cada bloque de 6 bits de Mi: Fila (F) y Columna (C)M4 = 010100 110010 000001 010101 010011 100100 000100 100000M4 010100 S1(F=0, C=10) = 6 = 0110(8 bloques de 6 bits)

110010 S2(F=2, C= 9) = 8 = 1000000001 S3(F=1, C= 0) =13 = 1101010101 S4(F=1, C=10) = 2 = 0010010011 S5(F=1, C= 9) = 0 = 0000100100 S6(F=2, C= 2) =15 = 1111000100 S7(F=0, C= 2) = 2 = 0010100000 S8(F=2, C= 0) = 7 = 0111

R4 = 0110 1000 1101 0010 0000 1111 0010 0111(8x4 = 32 bits de resumen)

M5 = 010000 100100 111101 001101 010000 100100 000100 000000M5 010000 S1(F=0, C= 8) = 3 = 0011(8 bloques de 6 bits)

100100 S2(F=2, C= 2) = 7 = 0111111101 S3(F=3, C=14) = 2 = 0010001101 S4(F=1, C= 6) = 0 = 0000010000 S5(F=0, C= 8) = 8 = 1000100100 S6(F=2, C= 2) =15 = 1111000100 S7(F=0, C= 2) = 2 = 0010000000 S8(F=0, C= 0) =13 = 1101

R5 = 0011 0111 0010 0000 1000 1111 0010 1101 (8x4 = 32 bits de resumen)Para obtener el Resumen final R aplicamos XOR a Ri, R4 y R5:

Ri = 1111 1011 1011 1100 0000 0000 1111 1000R4 = 0110 1000 1101 0010 0000 1111 0010 0111R5 = 0011 0111 0010 0000 1000 1111 0010 1101R = 1010 0100 0100 1110 1000 0000 1111 0010

b) Sí cumple con la unidireccionalidad pedida a las funciones hash. La no linealidad de las Cajas S hace que la salida de una de ellas (S i) pueda ser debido a cuatro posibles entradas. Por ejemplo, la salida decimal seis (0110) de la caja S1 puede ser resultado de cualquiera de estas cuatro entradas:

010100 Fila 0, Columna 10010011 Fila 1, Columna 9101010 Fila 2, Columna 5111101 Fila 3, Columna 14

Luego, para la salida de 8 cajas S concatenadas, el número de iteraciones para una única salida correcta será 48 = 65.536. Aunque entran 5 bloques de 48 bits a las cajas S para formar el resumen –que podría inducir a pensar que el total de estados posibles sería en este caso (48)5 = 440 = 280 lo que es falso– hay que recordar que el resumen tiene sólo 32 bits por lo que el sistema sucumbe ante un ataque por fuerza bruta de sólo 232.

c) El peor inconveniente de esta propuesta es su baja representación en bits por lo que habrá muchos mensajes distintos que tengan igual resumen. La resistencia débil ante colisiones, conocido un mensaje encontrar otro con igual resumen, será de 232 y la resistencia fuerte ante colisiones (en este caso la coincidencia de resúmenes de dos mensajes distintos elegidos al azar) será solamente de 216, valores extremadamente bajos. No obstante, no resulta tan sencillo invertir el algoritmo por fuerza bruta.

Byte Carácter Byte Carácter Byte Carácter0010 0000 Espacio 0100 0000 @ 0110 0000 `0010 0001

!

0100 0001 A 0110 0001 a

0010 0010 “ 0100 0010 B 0110 0010 b0010 0011 # 0100 0011 C 0110 0011 c0010 0100 $ 0100 0100 D 0110 0100 d0010 0101 % 0100 0101 E 0110 0101 e0010 0110 & 0100 0110 F 0110 0110 f0010 0111 ‘ 0100 0111 G 0110 0111 g0010 1000 ( 0100 1000 H 0110 1000 h0010 1001 ) 0100 1001 I 0110 1001 i0010 1010 * 0100 1010 J 0110 1010 j0010 1011 + 0100 1011 K 0110 1011 k0010 1100 , 0100 1100 L 0110 1100 l0010 1101 - 0100 1101 M 0110 1101 m0010 1110 . 0100 1110 N 0110 1110 n0010 1111 / 0100 1111 O 0110 1111 o0011 0000 0 0101 0000 P 0111 0000 p0011 0001 1 0101 0001 Q 0111 0001 q0011 0010 2 0101 0010 R 0111 0010 r0011 0011 3 0101 0011 S 0111 0011 s0011 0100 4 0101 0100 T 0111 0100 t0011 0101 5 0101 0101 U 0111 0101 u0011 0110 6 0101 0110 V 0111 0110 v0011 0111 7 0101 0111 W 0111 0111 w0011 1000 8 0101 1000 X 0111 1000 x0011 1001 9 0101 1001 Y 0111 1001 y0011 1010 : 0101 1010 Z 0111 1010 z0011 1011 ; 0101 1011 [ 0111 1011 {0011 1100 < 0101 1100 \ 0111 1100 |0011 1101 = 0101 1101 ] 0111 1101 }0011 1110 > 0101 1110 ^ 0111 1110 ~0011 1111 ? 0101 1111 _ 0111 1111

Códigos ASCII / ANSI de nivel bajo (128 bits) más

utilizados

0

0000

1

0001

2

0010

3

0011

4

0100

5

0101

6

0110

7

0111

8

1000

9

1001

A

1010

B

1011

C

1100

D

1101

E

1110

F

1111

Codificación en hexadecimal / binario

Valor Carácter6 bits codificado




0 000000 A 16 010000 Q 32 100000 g 48 110000 w1 000001 B 17 010001 R 33 100001 h 49 110001 x2 000010 C 18 010010 S 34 100010 i 50 110010 y3 000011 D 19 010011 T 35 100011 j 51 110011 z4 000100 E 20 010100 U 36 100100 k 52 110100 05 000101 F 21 010101 V 37 100101 l 53 110101 16 000110 G 22 010110 W 38 100110 m 54 110110 27 000111 H 23 010111 X 39 100111 n 55 110111 38 001000 I 24 011000 Y 40 101000 o 56 111000 49 001001 J 25 011001 Z 41 101001 p 57 111001 510 001010 K 26 011010 a 42 101010 q 58 111010 611 001011 L 27 011011 b 43 101011 r 59 111011 712 001100 M 28 011100 c 44 101100 s 60 111100 813 001101 N 29 011101 d 45 101101 t 61 111101 914 001110 O 30 011110 e 46 101110 u 62 111110 +15 001111 P 31 011111 f 47 101111 v 63 111111 /

(Relleno) =Código Base-64

Ejercicio Nº 3 (2,5 puntos. Tiempo recomendado: 45 minutos)Para firmar digitalmente un mensaje M con el método de

ElGamal o con el método RSA, usamos primeramente una

función resumen especial H(M) basada en las cajas S del

DES. Esta función consiste en agrupar el mensaje M en

bloques de 6 bytes (48 bits) que entran en las cajas S

estándar, dando como salida un primer resumen de 32 bits.

El segundo bloque de 48 bits de texto en claro produce un

segundo resumen de 32 bits que se suma or exclusivo al

primer resumen y así sucesivamente hasta llegar al final

del texto, dando un resumen final H(M) de 32 bits. Si hay

que usar relleno en el último bloque, esto se hace con un

conjunto de ceros.

Para M = “AQUI NO HAY PLAYA” (texto de 17 caracteres) los

dos primeros resúmenes son:

r1 = 0011 0001 0000 0010 0101 1101 1101 0001

r2 = 0110 1000 1101 0000 1000 1101 1011 0111

a) Calcule el resumen del tercer bloque de texto r3 y el resumen final H(M).

b) En este entorno de resumen H(M) deseamos firmar con RSA siendo p = 25.621; q = 187.163; e = 770.011 y d = 2.658.042.571. ¿Son válidos este cuerpo de trabajo y esas claves?

c) ¿Podría firmar con ElGamal en este entorno con p = 2.147.483.647? Justifique su respuesta.Datos: 232 = 4.294.967.296; p y q son primos; 770.011 =

1170.001 (ambos primos)

770.0112.658.042.571 = 2.046.722.018.138.281 =

426.8374.795.090.440 + 1.

SOLUCIÓN: M = AQUÍ_NO_HAY_PLAYA (usamos el carácter _ como espacio en

blanco)A = 0100 0001N = 0100 1110H = 0100 1000P =0101 0000Q = 0101 0001O = 0100 1111A = 0100 0001L =0100 1100

U = 0101 0101_ = 0010 0000Y = 0101 1001A =0100 0001I = 0100 1001 _ = 0010 0000Y =0101 1001

_ = 0010 0000 A = 0100 0001

Primer bloque de resumen (primeros 48 bits: AQUÍ_N)Caja S1 Caja S2 Caja S3 Caja

S4

Entrada: 010000 Entrada: 010101 Entrada: 000101 Entrada: 010101

Fila: 0 Fila: 1 Fila: 1Fila: 1

Columna: 8 Columna: 10 Columna: 2 Columna: 10

Salida: 3 Salida: 1 Salida: 0Salida: 2Bits: 0011 Bits: 0001 Bits: 0000 Bits:

0010Caja S5 Caja S6 Caja S7 Caja

S8





0001Resumen r1 = 0011 0001 0000 0010 0101 1101 1101 0001Segundo bloque de resumen (próximos 48 bits: O_HAY_)

Caja S1 Caja S2 Caja S3 Caja S4





0000

Caja S5 Caja S6 Caja S7 Caja S8





0111Resumen r2 = 0110 1000 1101 0000 1000 1101 1011 0111a) El tercer bloque de 48 bits que es el que se pide es PLAYA (

es un relleno de 8 ceros)Caja S1 Caja S2 Caja S3 Caja

S4





1101Caja S5 Caja S6 Caja S7 Caja

S8





1101Resumen r3 = 0110 1000 0100 1101 1111 0011 0010 1101El resumen final H(M) será r1 r2 r3 es decir:

Resumen r1 = 0011 0001 0000 0010 0101 1101 1101 0001

Resumen r2 = 0110 1000 1101 0000 1000 1101 1011 0111

Resumen r3 = 0110 1000 0100 1101 1111 0011 0010 1101 H(M) = 0011 0001 1001 1111 0010 0011 0100 1011

H(M)16 = 31 9F 23 4B1,5 Puntos

b) Para un sistema de firma RSA tenemos que n = pq = 25.621187.163 = 4.795.303.223, valor que es ligeramente superior a 232 = 4.294.967.296 dado como dato, luego el cuerpo de trabajo es correcto ya que podrán cifrarse (firmarse) todos los resúmenes posibles. En este sistema, (n) = (p-1)(q-1) = (25.620)(187.162) = 4.795.090.440. La clave pública e se elige de forma que no tenga factores en común con (n) y se cumple puesto que 4.795.090.440 no es divisible por 11 ni por 70.001 dados como dato. La clave privada d debe ser la inversa de la clave pública e en (n) de forma que se cumpla que ed mod (n) = 1. Según los datos dados en el examen se ve que esto se cumple. Luego el sistema es correcto. 0,5 Puntos

c) En este entorno no puede usarse la firma de ElGamal con un valor primo p = 2.147.483.647 puesto que, aunque cumple con la condición de ser primo, es menor que el valor máximo del resumen que podemos obtener que sería una cadena de 32 unos (232 – 1) y el valor dado aquí es justo un bit menos (231 – 1). La única solución en este caso sería dividir la función hash H(M) en, por ejemplo, dos bloques de 16 bits cada uno y hacer la firma del documento por partes.

0,5 Puntos

Ejercicio Nº 2 (2,5 puntos - 0,5 c/u. Tiempo recomendado: 45 minutos)Usamos el algoritmo de las cajas S del DES para generar

claves. Si la entrada a esas cajas S1-S8 es la cadena de bits

indicada 101011 010010 111010 001011 011111 110100

110111 100001:

a) Encuentre la salida en hexadecimal de cada una de las cajas S.

b) ¿Podríamos usar el valor de salida anterior como una clave DES? ¿Por qué?

c) ¿Podríamos usar el valor de salida anterior como una clave IDEA? ¿Por qué?

d) ¿Sucede algo especial si la entrada en ASCII es UUUUUU? ¿Cuál es la salida hexadecimal?

e) ¿Con qué esfuerzo podríamos reconstruir la entrada a partir de la salida por fuerza bruta?

Solución: a) Salida cajas S si entrada = 101011 010010 111010 001011

011111 110100 110111 100001: S1 1010112: Fila = 112 = 3; Columna = 01012 = 5 Salida

celda = 9 = 11012 = 916

S2 0100102: Fila = 002 = 0; Columna = 10012 = 9 Salida celda = 7 = 01112 = 716

S3 1110102: Fila = 102 = 2; Columna = 11012 = 13 Salida celda = 10 = 10102 = A16

S4 0010112: Fila = 012 = 1; Columna = 01012 = 5 Salida celda = 15 = 11112 = F16



S7 1101112: Fila = 112 = 3; Columna = 10112 = 11 Salida celda = 15 = 11112 = F16


La salida en hexadecimal de las cajas S será: 97AF 64F2b) No, porque DES usa una clave de 64 bits con paridad o 56 bits

sin paridad y la salida de estas cajas S son sólo 32 bits.c) Menos aún porque IDEA usa una clave de 128 bits.d) Como el valor ASCII de la letra U = 8510 = 010101012, esta

cadena de ceros y unos se repetirá desde el bit primero hasta el último en la entrada, por lo que todas las entradas a las cajas Si serán iguales, el valor 010101. Luego, en todas las cajas Si deberá leerse en las celdas de la fila 012 = 1 y columna 10102 = 10. La salida hexadecimal será ahora C152 FD56.

e) En DES, para cada valor de salida de cada caja Si hay cuatro valores de entrada posibles. Por ejemplo, en la caja S1 la salida 11112 = F se obtiene independientemente para entradas 001010, 000011, 110000 y 100001. Por lo tanto, para una salida cualesquiera de 32 bits, habrá 48 = 262.144 posibles entradas, un valor bajo que permitiría hacer un ataque por fuerza bruta. Nota: recuerde que el algoritmo DES entrega un bloque de texto cifrado después de 16 vueltas por lo que este tipo de ataque (aunque haya otras operaciones en dicho algoritmo y con tamaños de cadenas de bits distintas) se vuelve computacionalmente imposible.

Ejercicio Nº 1 2,0 puntos (1,0 c/u). Tiempo recomendado: 30 minutosSi en una de las vueltas del DES la entrada a las cajas S es la secuencia hexadecimal que se indica Mhex = A06F 8626 9C52, se pide:a) Encuentra la salida en binario y en hexadecimal de cada

una de las cajas S.b) ¿Cuántos cálculos habría que hacer para romper por

fuerza bruta esta parte de 8 valores de cajas S, de forma que podamos volver desde esta salida de las cajas a la entrada original Mhex = A06F 8626 9C52?

SOLUCIÓN:Apartado a)

A06F86269C52 = 1010 0000 0110 1111 1000 0110 0010 0110 1001 1100 0101 0010Entrada Cajas Si: 101000 000110 111110 000110 001001 101001 110001 010010En hoja anexa al examen se han entregado las tablas S del DES.Entradas Fila/Columna Caja Si: S1 S2 S3 S4 S5 S6 S7

S8

2/4 0/3 2/15 0/3 1/4 3/4 3/80/9

Salida decimal de Cajas Si: 13 14 7 3 4 9 99

Salida binario de Cajas Si: 1101 1110 0111 0011 0100 1001 10011001

Salida hexadecimal de Cajas Si: DE73 4999Apartado b)Cada salida (valores de 0 a 15) de una caja Si tiene cuatro posible entradas. Por ejemplo, para la caja S1 la salida 15 se obtiene para estas cuatro entradas de Filas/Columnas: 0/5, 1/1, 2/8 y 3/0.Por lo tanto, para 8 cajas Si concatenadas, deberemos realizar 48 = 65.536 intentos en el pero de los casos por fuerza bruta para volver de la salida DE734999 a la entrada A06F86269C52. Para una vuelta completa del DES serían (48)16 = 1,16 x 1077 intentos, un valor ya desmesurado.

Ejercicio Nº 1 2,0 puntos (1,0 c/u). Tiempo recomendado: 30 minutosLa salida de las cajas S (SCS) de la primera vuelta del DES es SCS = AF32 7B13Se pide:c) Calcula la entrada (en binario) a cada una de las 8 cajas S a partir de esa salida, suponiendo que ha coincidido en este caso que en cada caja se ha activado siempre la fila 0.

d) En una sola vuelta, ¿cuántas combinaciones de entrada (sólo el número) darían esta salida?


SCS = AF32 7B13 = 1010 1111 0011 0010 0111 1011 0001

0011

Salida caja S1 = A = 10102 = 10 Fila 0; Columna 9

Entrada caja S1 = 0 1001 0

Salida caja S2 = F = 11112 = 15 Fila 0; Columna 0


Salida caja S3 = 3 = 00112 = 3 Fila 0; Columna 5






Salida caja S6 = B = 10112 = 11 Fila 0; Columna 15






Apartado b)Como hay cuatro entradas posibles para cada salida de las cajas S -una para cada fila- existirán 48 posibles combinaciones, es decir 65.536 en cada vuelta.FUERA DEL EXAMEN (no se considera ni se evalúa): Las cuatro combinaciones de cada caja Si que entregarían el valor indicado de AF32 7B13 serán las siguientes (F = fila; C = columna):

Caja S1 = A = 10102 = 10 (F0, C9); (F1, C8); (F2, C13); (F3, C12) Caja S2 = F = 11112 = 15 (F0, C0); (F1, C4); (F2, C15); (F3, C5) Caja S3 = 3 = 00112 = 3 (F0, C5); (F1, C4); (F2, C6); (F3, C11) Caja S4 = 2 = 00102 = 2 (F0, C9); (F1, C10); (F2, C13); (F3, C14) Caja S5 = 7 = 01112 = 7 (F0, C4); (F1, C5); (F2, C6); (F3, C3) Caja S6 = B = 10112 = 11 (F0, C15); (F1, C13); (F2, C14); (F3, C8) Caja S7 = 1 = 00012 = 1 (F0, C15); (F1, C6); (F2, C0); (F3, C4) Caja S8 = 3 = 00112 = 3 (F0, C10); (F1, C5); (F2, C13); (F3, C12)

Ejercicio Nº 2 2,5 puntos (0,5 c/u). Tiempo recomendado: 45 minutos

Para generar una clave en un cifrado en flujo, vamos a usar

dos LFSR primitivos de 2 y 3 celdas, caracterizados por los

polinomios p1 = x2 + x + 1 (con semilla 11) y p2 = x3 + x +

1 (con semilla 101). La salida de estos LFRS se conecta a

una puerta XOR que entrega la secuencia cifrante S.

a) Encuentra las secuencias de S1 y S2.b) ¿Cuál es el período de S1 y S2? ¿Cuál será el periodo de S?

c) Encuentra la secuencia de clave S.d) Con esa secuencia S cifra el mensaje M = OK. e) ¿Cumple la cifra anterior la condición estipulada por Vernam para estos cifradores? ¿Por qué?


Generador S1 con polinomio p1 = x2 + x + 1 (semilla 11): Semilla 11 1

01 110 011 semilla ... luego S1 = 110.

Generador S2 con polinomio p1 = x3 + x + 1 (semilla 101): Semilla 101 1

010 0001 1100 0110 0111 1011 1101 semilla ... luego S1 = 1010011.

Apartado b)El período de S1 es igual a 3, el período de S2 es igual a 7 y el período de S será el mcm (S1, S2) es decir mcm (3, 7) = 21.Apartado c)Como el período de S1 = 110 es el más pequeño (3) haremos la suma xor de tres en tres de S1 con la secuencia S2 = 1010011 hasta que se repitan los operandos y por tanto la secuencia de salida:

110 101 = 011110 001 = 111110 110 = 000110 100 = 010110 111 = 001

110 010 = 100110 011 = 101110 101 = se repiten los operandos.

Luego S = 011 111 000 010 001 100 101 (período 21)Apartado d)M = OK = 0100 1111 0100 1011

C = M SM 0 1 0 0 1 1 1 1 0 1 0 0 1 0 1 1S 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 C = 0 0 1 1 0 0 1 1 0 1 1 0 1 0 0 0

Apartado e)Se puede cifrar el mensaje M de 16 bits pues la clave S de 21 bits es mayor que el mensaje, una condición que debería cumplirse para que este cifrado verificase el diseño de Vernam. Si ciframos un texto mayor, ya no debería usarse esta clave en tanto sería de longitud menor que el mensaje y por tanto estaríamos ante un cifrado con clave periódica, algo no recomendable en estos sistemas.

Ejercicio Nº 2 2,5 puntos (0,5 c/u). Tiempo recomendado: 45 minutos

Creamos una función hash que agrupa bloques de 6 bytes, los

pasa por las cajas S del DES y a esa salida le aplica un

XOR con el vector inicial ABCD de valor hexadecimal

FFFF0000. El mensaje en ASCII es M = AMIGOS.

Se pide:

f) Encuentra la función hash h(M).g) Sólo indica –sin calcularlo- qué habría que hacer para obtener h(M) si ahora M = COLEGAS.

h) ¿Cuál sería el vector ABCD de la segunda vuelta si el mensaje M tuviese más de 6 bytes?

i) Si el vector ABCD fuese otro, por ejemplo D5F95AB3, ¿sería más seguro el hash?

j) Aceptando que el valor de bloque a tratar es bajo, ¿sería adecuada y segura esta función?


AMIGOS = 01000001 01001101 01001001 01000111 01001111 01010011Estos 48 bits entrarán en bloques de 6 bits a las 8 cajas S del DES agrupados así: Entrada cajas S1-S8: 010000 010100 110101 001001 010001 110100 111101 010011

Entrada caja S1 = 0 1000 0 Fila 0; Columna 8

Salida caja S1 = 3 = 0011















Haciendo el XOR con el vector ABCD se obtiene:

Cajas S 0011 0010 1110 0110 0101 0100 0011

0101

ABCD 1111 1111 1111 1111 0000 0000 0000

0000

Resumen 1100 1101 0001 1001 0101 0100 0011 0101 h(M) C D 1 9 5 4 3 5Apartado b)Como el mensaje COLEGAS tiene 7 bytes, habrá que usar dos bloques para calcular

el hash, un primer bloque con los caracteres COLEGA y un segundo bloque con los caracteres S###### en donde # significa un relleno de 8 ceros.Apartado c)El vector ABCD de la segunda vuelta será precisamente la salida o hash encontrado en el apartado primero,. es decir, ABCD = 11001101 00011001 01010100 00110101Apartado d)No sería más seguro porque la seguridad de las funciones hash, y de esta función hash en particular, deberá residir en la no linealidad de las operaciones que se realizan (en este caso en las cajas S) y no en la aleatoriedad del valor del vector inicial.Apartado e)En principio sí; porque está basada en una función no lineal (cajas S) al igual que las operaciones que usan por ejemplo MD5 y SHA-1. No obstante, tiene en su contra que las operaciones son pocas y muy sencillas y no hay tanta mezcla de bits como en estas funciones por lo que cabría esperar que su efecto de avalancha (cambio de un bit en la entrada significa un cambio de más de la mitad de los bits de salida) no fuera tan significativo como en estas últimas. Resulta entonces un algoritmo muy elemental y además propenso a demasiadas colisiones por su pequeño resumen.

Ejercicio Nº 2 2,5 puntos. Tiempo recomendado: 45 minutos

Una entrada a las cajas S del DES activa las siguientes filas (F) y columnas (C) como se indica:

S1F,C = 0,9; S2F,C = 0,10; S3F,C = 3,12; S4F,C = 1,4; S5F,C = 0,8; S6F,C = 2,10; S7F,C = 3,2; S8F,C = 1,7.

Tabla con cajas S del DES en el anverso del examen.

Se pide:

e) Los 48 bits de entrada a las cajas S (be) y la palabra en ASCII que forma. [1,0 p]

f) Los 32 bits de salida (bs) de esas cajas S. [1,0 p]g) El número de entradas (be) posibles que podrían dar lugar a esa salida (bs) en una vuelta. [0,5 p]


Como las cajas S se activan seleccionando filas F y

columnas C a partir de 6 bits b6b5b4b3b2b1 de forma que los

bits b6b1 indican la fila F y los bits b5b4b3b2 la columna C,

entonces:

S1F,C = 0,9 0 1001 0; S2F,C = 0,10 0 1010 0; S3F,C =

3,12 1 1100 1; S4F,C = 1,4 0 0100 1;

S5F,C = 0,8 0 1000 0; S6F,C = 2,10 1 1010 0; S7F,C =

3,2 1 0010 1; S8F,C = 1,7 0 0111 1.

Agrupando los 48 bits en bloques de 8 bits (un byte) se

tiene:

Entrada bits: 01001001 01001110 01001001 01000011

01001001 01001111

Entrada ASCII: I N I

C I O

Apartado b)S1F,C = 0,9 Salida 10 Salida2 = 1010 S2F,C = 0,10 Salida 2 Salida2 = 0010S3F,C = 3,12 Salida 11 Salida2 = 1011 S4F,C = 1,4

Salida 6 Salida2 = 0110S5F,C = 0,8 Salida 8 Salida2 = 1000 S6F,C = 2,10 Salida 4 Salida2 = 0100S7F,C = 3,2 Salida 13 Salida2 = 1101 S8F,C = 1,7

Salida 4 Salida2 = 0100Luego bs = 1010 0010 1011 0110 1000 0100 1101 0100Apartado c)En una vuelta cada una de las cajas S tiene 4 posibles entradas para una única salida; por lo tanto, habrá 48 = 65.536 entradas be que entregan una misma salida bs.

Se 06

Ejercicio Nº 1 2,0 puntos. Tiempo recomendado: 30 minutos

Se intenta criptoanalizar las cajas S del DES. Si en una de las vueltas del algoritmo, la salida de las cajas en hexadecimal es igual a B5AF8D1F = 10110101 10101111 10001101 00011111.Se pide:h) Encuentra en binario todas las entradas posibles de la caja S8.

i) ¿Es más fácil atacar por fuerza bruta la cifra o romper las cajas S en 16 vueltas? ¿Por qué?

j) ¿Qué pasaría si el algoritmo tuviese sólo 3 vueltas?

Caja S8 C O L U M N A

Fila 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7

1 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2

2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8

3 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11

SOLUCIÓN:Apartado a: (1,0 punto)

La salida de la caja S8 serán los últimos 4 bits del valor entregado, es decir F = 1111. Luego, habrá que buscar en dicha caja las filas y columnas que entreguen el valor decimal 15.

Fila 0 Columna 5 Valores de entrada para esta combinación: 0 0101 0



Fila 3 Columna 8 Valores de entrada para esta combinación: 1 1000 1Apartado b: (0,5 puntos)Hay que realizar un mayor trabajo para hacer un seguimiento hacia atrás de las cajas S en 16 vueltas que atacar la clave del DES por fuerza bruta (256). Como en cada caja hay 4 entradas posibles para cada salida, existirán 48 = 216 combinaciones de entrada. Como tenemos 16 vueltas, deshacer todas las operaciones de las cajas S en un bloque de cifra del DES implicaría (216)16 = 2256 intentos, un valor muchísimo mayor que 256.Apartado b: (0,5 puntos)Si sólo tenemos 3 vueltas, independiente de que el algoritmo sea muy básico y poco seguro, atacar las cajas S será ahora mucho más fácil porque significaría tan sólo (216)3 = 248 intentos, un valor bastante menor que 256.

Ejercicio Nº 1 2,0 puntos. Recomendado: 30 minutos

Un nuevo algoritmo de cifra simétrica incluye en una etapa intermedia el uso de las cajas S del DES para así aumentar su fortaleza. En una de las 20 vueltas de ese algoritmo, los 48 bits que entran en estas cajas vienen representados en hexadecimal por C83A 8E9A F5D0.Se pide:

k) Encontrar la salida de cada caja S y representarla en hexadecimal (1,0 punto)

l) ¿Qué cadena en hexadecimal se obtiene como salida? (0,5 puntos)

m) ¿Se puede recuperar con facilidad la entrada a partir de la salida? ¿Por qué? (0,5 puntos)

SOLUCIÓN:Apartado a:

Pasamos la entrada C83A 8E9A F5D0 a binario y nos queda1100 1000 0011 1010 1000 1110 1001 1010 1111 0101 1101 0000Agrupando de 6 bits que son los que entran en cada caja S:

110010 000011 101010 001110 100110 101111 010111 010000 S1 S2 S3 S4 S5 S6 S7 S8

Leyendo los bits de los extremos para las filas F y los cuatro centrales para columnas C, tenemos:

S1 S2 S3 S4 S5 S6 S7 S8(F,C) (2,9) (1,1) (2,5) (0,7) (2,3) (3,7) (1,11) (0,8)Que corresponde a las salidas: 12, 13, 15, 10, 11, 10, 12, 10 respectivamente.Apartado b:

Pasando estos valores a hexadecimal se tiene: CDFABACA.Apartado c:

Para una sola vuelta sí sería muy fácil porque para cada salida hay 4 entradas posibles y así tendríamos que hacer sólo 4^8 = 65.536 intentos con todas las combinaciones. Pero si, como se indica en el enunciado, el algoritmo realiza 20 vueltas, intentar atacar las cajas S (de valores conocidos) por fuerza bruta significaría realizar (4^8)^20 = 2,14 x 1096 intentos, un valor muy alto.

Ejercicio Nº 1 2,0 puntos (0,5 c/u). Recomendado: 30 minutos

Tras una vuelta del algoritmo DES, nos encontramos que la salida en hexadecimal de las cajas S es SCajasS = FB12FA34Se pide:k) Indica si alguna de estas posibles 8 entradas es la verdadera.Entrada 1) 110000 001010 100001 111010 010110 101111

010000 100110

Entrada 2) 110000 001010 100001 111010 010110 101111

001000 100100

Entrada 3) 110000 001010 100001 111010 010110 101101

010000 100100

Entrada 4) 110000 001010 100001 111010 110110 101111

010000 100100

Entrada 5) 110000 001010 100001 101010 010110 101111

010000 100100

Entrada 6) 110000 001010 100111 111010 010110 101111

010000 100100

Entrada 7) 110000 011010 100001 111010 010110 101111

010000 100100

Entrada 8) 110000 001010 100001 111010 010110 101111

010000 100100

Ninguna de las anteriores.

b) Justifica porqué has descartado cada una de las entradas

o todas.


Para que la salida de la primera caja S1 sea F = 1111, la

entrada a S1 debe ser (2,8) = 1 1000 0

Las 8 entradas comienzan con esta cadena de seis bits.

Todas lo cumplen.

Para que la salida de la segunda caja S2 sea B = 1011, la


Fallo: la entrada 7 = 011010 no cumple con esta cadena

de bits.

Para que la salida de la tercera caja S3 sea 1 = 0001, la


Fallo: la entrada 6 = 100111 no cumple con esta

cadena de bits.

Para que la salida de la cuarta caja S4 sea 2 = 0010, la


Fallo: la entrada 5 = 101010 no cumple con esta

cadena de bits.

Para que la salida de la quinta caja S5 sea F = 1111, la



de bits.

Para que la salida de la sexta caja S6 sea A = 1010, la



de bits.

Para que la salida de la séptima caja S7 sea 3 = 0011, la



de bits.

Para que la salida de la octava caja S8 sea 4 = 0100, la



de bits.

La entrada que da como resultado SCajasS = FB12FA34 es la

número 8,

Apartado b:

Se llega a esta conclusión porque todas las demás entradas

fallan, en sólo una caja S diferente en cada caso si bien

todas las demás estás correctas. La entrada número 8 es la

única que cumple con el resultado buscado.

Ejercicio 1 2,0 puntos. Tiempo máximo recomendado: 30 minutosEn una vuelta del DES a las cajas S (ver anverso) entran los 48 bits que se indican ya agrupados en bloques de 6 bits: 000000 000010 000100 000110 001000 001010 001100 001110.Se pide:l) ¿Qué salida entregarán las cajas S a esa entrada? (0,5 puntos)

m) ¿Qué salida entregarían las cajas S si esa entrada fuese de todo 1s? (0.5 puntos)

n) Razonar porqué se dice que la seguridad del DES reside en las cajas S. (1,0 punto)


La entrada es: 000000 000010 000100 000110 001000 001010 001100 001110.Observamos que los bits de los extremos (el 1º y el 6º) de todas las entradas a las cajas S son siempre 0, luego se tratará de la fila cero en cada una de ellas. Y luego los bits centrales (2º al 5º) van desde 0000 al 0111 (de 0 a 7) avanzando de uno en uno. Por lo tanto serán la columna 0 para S1, la columna 1 para S2, la columna 2 para S3, la columna 3 para S4, la columna 4 para S5, la columna 5 para S6, la columna 6 para S7 y la columna 7 para S8.La salida será entonces: S1 = 14; S2 = 1; S3 = 9; S4 = 3; S5 = 7; S6 = 2; S7 = 8; S8 = 1.Apartado b:

En este caso, al ser todos unos la fila de cada caja será siempre la 3 y la columna será siempre la 15; es decir, el último valor de cada caja S. Así, S1 = 13; S2 = 9; S3 = 12; S4 = 14; S5 = 3; S6 = 13; S7 = 12; S8 = 11.Apartado c:

En una vuelta del DES, la salida cada una caja S puede provenir de 4 entradas posibles; por tanto tendremos 48 permutaciones. Como en cada bloque de cifra se realizan 16 vueltas, ir hacia atrás en las cajas S significaría un máximo de (48)16 = 2(16)16 = 2256 operaciones, un valor muy superior a los 256 intentos necesarios para atacar por fuerza bruta la clave efectiva del DES. Además, las cajas S son la única parte del algoritmo que no es lineal y por eso lo hace seguro; todas las demás operaciones son lineales y por tanto muy fáciles de deshacer en tanto el código debe ser público.

Documents

Ejercicios DES