Class4cryptVideoclases de criptografía aplicada
Class4crypt c4c8.3 - © jorgeramio 2020
Profesor Dr. Jorge Ramió A.
Clase c4c8.3Algoritmo DES: expansión
de clave, cifra y rellenosMadrid, martes 16 de junio de 2020
Temario de las clases Class4crypt
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 2
• Módulo 1: Principios básicos de la seguridad
• Módulo 2: Matemáticas discretas en la criptografía
• Módulo 3: Complejidad algorítmica en la criptografía
• Módulo 4: Teoría de la información en la criptografía
• Módulo 5: Fundamentos de la criptografía
• Módulo 6: Algoritmos de criptografía clásica
• Módulo 7: Funciones hash en la criptografía
• Módulo 8: Criptografía simétrica en bloque
• Módulo 9: Criptografía simétrica en flujo
• Módulo 10: Criptografía asimétrica
• Módulo11: Certificados digitales y protocolos criptográficos
• Módulo12: Temas avanzados en criptografía
Clases publicadas en Class4crypt (1)
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 3
1. Presentación de Class4crypt
2. Ciberseguridad y criptografía
3. Algoritmo RSA
4. Operaciones modulares y conjunto de restos
5. Percepción de la inseguridad según las décadas
6. Criptografía asimétrica y la analogía de los candados
7. Protocolo de intercambio de clave de Diffie y Hellman
8. Ataque man in the middle al intercambio de clave de Diffie y Hellman
9. Cifrado por sustitución polialfabética: algoritmo de Vigenère
10. Criptoanálisis al cifrado de Vigenère por el método Kasiski
11. El homomorfismo de los enteros en la criptografía
12. Inverso aditivo, inverso xor e inverso multiplicativo
Clases publicadas en Class4crypt (2)
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 4
13. Cálculo de inversos con el algoritmo extendido de Euclides
14. Algoritmo de exponenciación modular rápida
15. Generación de claves RSA y estándar PKCS#1
16. Cifrado y descifrado con RSA parte 1
17. Cifrado y descifrado con RSA parte 2
18. Introducción a la criptografía moderna
19. Comparación entre cifra simétrica y cifra asimétrica
20. Fundamentos de la cifra simétrica en flujo
21. Registros de desplazamiento realimentados lineales y no lineales
22. Aleatoriedad en registros LFSR con polinomio primitivo
23. Fundamentos de la cifra simétrica en bloque
24. Algoritmo DES: redes de Feistel y cajas S
25. Algoritmo DES: expansión de clave, cifra y rellenos
12.570 visualizaciones al 16/06/20
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 5
¡COMENZAMOS!
Módulo 8. Criptografía simétrica en bloque
Lección 8.3. Algoritmo DES: expansión de clave, cifra y rellenos
1. Los bits de paridad en la clave del DES
2. Generación de las 16 subclaves de ronda k1 a k16 en cifrado y descifrado
3. Operaciones de cifrado y descifrado
4. Relleno zero padding
5. Claves débiles y semidébiles
Class4crypt c4c8.3
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 6
Los bits de paridad en el algoritmo DES
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 7
• DES elimina el octavo bit de cada byte de la clave de 64 bits, al suponer que se trata de un bit de paridad: quita los bits 8, 16, 24, 32, 40, 48, 56 y 64
• Quita 8 bits en total y la clave real se queda en 56 bits. Por lo tanto, el espacio de claves real del algoritmo DES es igual a 256 = 72.057.594.037.927.936
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
• Esto lo hace con la tabla de PC-1 de permutación y selección
• Los 56 bits de la clave del DES y que se dividirán en dos mitades, izquierda y derecha de 28 bits cada una, para generar las 16 subclaves k1 a k16, una para cada vuelta
Tabla PC-1 Permuted Choice en clave DES
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 8
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
Desaparecen los 8 bits de paridad:
8, 16, 24, 32, 40, 48, 56 y 64
Tabla PC-1 (56 bits)28 bits 28 bits
Tabla PC-2 Permuted Choice en clave DES
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 9
4 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
Tabla PC-2 (48 bits) k1, k2, … k15, k16
Se han eliminado 8 bits:
9, 18, 22, 25, 35, 38, 43 y 54
28 bits 28 bits
48 bits
48 bits
48 bits
Desplazamientos para cálculo de subclaves
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 10
Vuelta i Bits Despl. Izda.
k1 -1
k2 -1
k3 -2
k4 -2
k5 -2
k6 -2
k7 -2
k8 -2
Vuelta i Bits Despl. Izda.
k9 -1
k10 -2
k11 -2
k12 -2
k13 -2
k14 -2
k15 -2
k16 -1
Se produce un desplazamiento total igual a 28, todos los bits de cada bloque Ci (izquierda) y Di (derecha)
28 bits28 bits
Left Shift: LF1, LF2, ... LF15, LF16
= 28
Como en la cifra se ha aplicado un desplazamiento de 28 bits en cada uno de los dos bloques de la clave:• D16 = D0
• C16 = C0
Descifrado en DES con claves k16 a k1
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 11
Vuelta i Bits Despl. Dcha.
k16 +1
k15 +2
k14 +2
k13 +2
k12 +2
k11 +2
k10 +2
k9 +1
Vuelta i Bits Despl. Dcha.
k8 +2
k7 +2
k6 +2
k5 +2
k4 +2
k3 +2
k2 +1
k1 +1
Right Shift: RH1, RH2, ...RH15, RH16
Sabemos que C16 = C0 y D16 = D0. Ahora se desplaza hacia la derecha y en sentido inverso para volver desde k16 a k1
Cla
ves
par
a d
esci
frad
o
28 bits28 bits
28 bits28 bits Charles Perrault
Cifrado, descifrado y rellenos en DES
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 12
• En DES se cifran bloques de 8 bytes, 64 bits
• Si el último bloque de texto en claro no tiene 8 bytes, se rellenará con tantos ceros como sea necesario
• Este relleno se conoce como Zero padding (hexadecimal)
• Por ejemplo M1 = Buenas tardes serán dos bloques a cifrar con 3 bytes de relleno y M2 = ¡Eureka! un solo bloque sin relleno:• M1 = 42 75 65 6E 61 73 20 74 61 72 64 65 73 00 00 00
• M2 = A1 45 75 72 65 6B 61 21
Claves débiles y semidébiles
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 13
• Por teoría de la información, si una cifra es C = Ek(M), donde Ek significa cifrar con la clave k, el único descifrado válido será M = Dk(C), donde Dk significa descifrar con la clave k
• M = Dk(Ek(M)) Cualquier otra opción, es una Solución Falsa
• Una clave es débil si se verifica que M = Ek(Ek(M)), es decir, se recupera el texto en claro volviendo a cifrar el criptograma
• Una clave es semidébil si se verifica que M = Eky(Ekx(M)), es decir, se recupera el texto en claro si se cifra el criptograma con una clave k diferente a la usada en la primera cifra
Claves débiles en DES
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 14
• En DES habrá 6 claves débiles: M = Ek(Ek(M))
• Los bloques C y D de 28 bits tienen todo ceros o todo unos• Caso 1a: 0x 0000000000000000 Caso 1b: 0x FFFFFFFFFFFFFFFF
• Caso 2a: 0x 0101010101010101 Caso 2b: 0x FEFEFEFEFEFEFEFE
• Caso 3a: 0x E0E0E0E0F1F1F1F1 Caso 3b: 0x 1F1F1F1F0E0E0E0E
• Los bits de C y D en 1a serán todo 0s y en 1b serán todo 1s
• Lo mismo sucede en 2a y 2b al eliminar el bit de paridad
• Por la permutación PC-1, en 3a la cadena C serán 1s y la cadena D serán 0s, y en 3b la cadena C serán 0s y la cadena D serán 1s
Claves semidébiles en DES
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 15
• En DES habrá 6 claves semidébiles: M = Eky(Ekx(M))
• Estas son las 6 claves kx y ky semidébiles• kx = 0x 01FE01FE01FE01FE ⇨ ky = 0x FE01FE01FE01FE01
• kx = 0x 1FE01FE00EF10EF1 ⇨ ky = 0x E01FE01FF10EF10E
• kx = 0x 01E001E001F101F1 ⇨ ky = 0x E001E001F101F101
• kx = 0x 1FFE1FFE0EFE0EFE ⇨ ky = 0x FE1FFE1FFE0EFE0E
• kx = 0x 011F011F010E010E ⇨ ky = 0x 1F011F010E010E01
• kx = 0x E0FEE0FEF1FEF1FE ⇨ ky = 0x FEE0FEE0FEF1FEF1
• Siempre vienen en parejas x, y
Prácticas con software safeDES
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 16
• Cifrado y descifrado de textos en modo ECB
• Observación de rellenos
• Cifrado y descifrado de archivos en modo ECB
• Comprobación de claves débiles y semidébiles
Píldora formativa Thoth nº 28
https://www.youtube.com/watch?v=XwUOwqSHzyo
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 17
Antes de terminar, por favor colabora…
• Si, en general, te ha gustado el vídeo…
• Si has aprendido algo nuevo…
• Si has podido reforzar algún conocimiento que ya tenías…
• Entonces, por favor, ponle un “Me gusta” al vídeo
• Si deseas expresar alguna opinión sobre el contenido de esta clase o tienes alguna duda, hazlo aquí en YouTube. Todos los comentarios serán muy bien recibidos y las dudas contestadas a la mayor brevedad posible
• Muchas gracias
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 18
Conclusiones de la lección 8.3
• Expansión de clave: una vez se han eliminado los (supuestos) bits de paridad, los 56 bits de la clave se dividen en dos mitades C y D de 28 bits cada una
• Se aplican desplazamientos hacia la izquierda a cada cadena de 28 bits C y D para obtener las claves k1 a k16 necesarias para cada una de las 16 vueltas del DES. Como esos desplazamientos suman 28, entonces las cadenas de bits C0 y C16 así como D0 y D16 estarán en fase, serán las mismas
• Por lo tanto, en el descifrado de una red Feistel (hacer el recorrido inverso), las claves k16 a k1 se obtienen realizando ahora los desplazamientos hacia la derecha: cuento Pulgarcito y sus guijarros (migas de pan) para volver a casa
• El relleno en DES es del tipo Zero padding
• Existen 6 claves débiles y 6 claves semidébiles en DES
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 19
Lectura extra recomendada
• The DES Algorithm Illustrated, J. Orlin Grabbe• http://page.math.tu-berlin.de/~kant/teaching/hess/krypto-ws2006/des.htm
• Key Expansion Function and Key Schedule of DES (Data Encryption Standard) Algorithm, Ritul (2019)• https://medium.com/@artistritul1995/key-expansion-function-and-key-schedule-of-des-data-
encryption-standard-algorithm-1bfc7476157
• Padding (cryptography), Wikipedia• https://en.wikipedia.org/wiki/Padding_(cryptography)
• Guion píldora formativa 28: ¿Cómo funcionan los algoritmos DES y 3DES?, proyecto Thoth, Jorge Ramió, 2015• http://www.criptored.upm.es/thoth/material/texto/pildora028.pdf
• ASCII Text to Hex Code Converter, Rapid Tables• https://www.rapidtables.com/convert/number/ascii-to-hex.html
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 20
Fin de la lección
Otras videoclases del proyecto Class4crypt
• https://www.youtube.com/user/jorgeramio
• Más información en canal Twitter• https://twitter.com/class4crypt
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 21
Licencia y créditos
• Estas videoclases y la documentación utilizada en ellas, se encuentran bajo licencia CreativeCommons tipo CC BY-NC-ND 4.0
• Reconocimiento - No Comercial - Sin Obra Derivada
• Permite que otros puedan descargar esta obra y compartirla con otras personas, siempre que se reconozca su autoría, pero no se puede cambiar de ninguna manera su contenido ni se puede utilizar comercialmente
• Música:
• Enter_Blonde, Max Surla, Media Right Productions, YouTube Audio Library - Free Music https://www.youtube.com/audiolibrary/music?nv=1
Class4crypt c4c8.3 - © jorgeramio 2020 Lección 8.3 - página 22