Class4crypt© jorgeramio 2021
Class4cryptAula virtual de criptografía aplicada
Class4crypt c4c10.9a - © jorgeramio 2021
Profesor Dr. Jorge Ramió A.
Clase c4c10.9aAtaques teóricos y
prácticos a RSA parte 1
Madrid, lunes 12 de julio de 2021
Temario de las clases Class4crypt
Class4crypt c4c10.9a - © jorgeramio 2021 Lección 10.9a - página 3
• 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
• 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
Clases publicadas en Class4crypt (1/4)
Class4crypt c4c10.9a - © jorgeramio 2021 Lección 10.9a - página 4
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
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
Clases publicadas en Class4crypt (2/4)
Class4crypt c4c10.9a - © jorgeramio 2021 Lección 10.9a - página 5
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
26. ECB y CBC, modos de cifra con confidencialidad
27. CFB, OFB y CTR, modos de cifra con confidencialidad
28. Ataques al DES, DES Challenge y 3DES
29. Clasificación de los sistemas de cifra clásica
30. Vulnerabilidades de la información y amenazas
31. Seguridad informática vs seguridad de información
32. Tríada confidencialidad, integridad y disponibilidad
33. Raíces primitivas en un primo p
34. Fundamentos de complejidad algorítmica
35. El problema de la mochila
36. El problema del logaritmo discreto
Clases publicadas en Class4crypt (3/4)
Class4crypt c4c10.9a - © jorgeramio 2021 Lección 10.9a - página 6
37. El problema de la factorización entera
38. Cantidad de información e incertidumbre
39. Entropía de la información y codificador óptimo
40. Ratio y redundancia del lenguaje
41. Cifrado aleatorio y distancia de unicidad
42. Métodos de difusión y confusión en criptografía
43. Reto 1 Navidades 2021
44. Definiendo criptografía y criptoanálisis + pista Reto 1
45. Esquema y elementos de un criptosistema
46. Principios de Kerckhoffs y fortaleza de la cifra
47. Introducción a la esteganografía
48. Mecanismos y máquinas de cifra
49. Reto 2 Módulo 5 Máquinas de cifra
50. Cifrado por permutación o transposición parte 1
51. Cifrado por permutación o transposición parte 2
52. Criptoanálisis a la cifra por permutación
53. Cifrado por sustitución
54. Criptoanálisis a la sustitución monoalfabética
55. Cifrado digrámico de Playfair
56. Cifrado poligrámico con matrices de Hill
Clases publicadas en Class4crypt (4/4)
Class4crypt c4c10.9a - © jorgeramio 2021 Lección 10.9a - página 7
57. Criptoanálisis a la cifra de Hill por Gauss-Jordan
58. Reto 3 Módulo 6 Algoritmos de criptografía clásica
59. Funciones hash en la criptografía
60. Función hash MD5: estructura y operaciones
61. Función hash SHA-1
62. Colisiones en funciones hash MD5 y SHA-1
63. SHA-2, SHA-3 y resumen de funciones hash
64. Reto 4 Módulo 7 Funciones hash
65. Algoritmo AES parte 1: visión general y fortaleza
66. Algoritmo AES parte 2: funciones y expansión clave
67. Algoritmo AES parte 3: SubBytes, ShiftRows,
MixColumns, AddRoundKey
68. Reto 5 Módulo 8 Criptografía simétrica en bloque
69. Complejidad en LFSR, A5, RC4 y Chacha20
70. Reto 5 Módulo 9 Criptografía simétrica en flujo
71. Números no cifrables en RSA
72. Claves parejas y números piratas en RSA
73. Ataques teóricos y prácticos a RSA parte 1
12/07/2021 > 49.000 visualizaciones
Class4crypt c4c10.9a - © jorgeramio 2021 Lección 10.9a - página 8
¡COMENZAMOS!
Módulo 10. Criptografía asimétrica
Lección 10.9a. Ataques teóricos y prácticos a RSA parte 1
1. Ataques significativos a RSA
2. Ataque por factorización entera del módulo n
3. Ataque por cifrado cíclico
Próxima lección 10.9b Ataques teóricos y prácticos a RSA parte 21. Ataque por la paradoja del cumpleaños
2. Ataque acústico por canal lateral
3. Conclusiones de la lección 10.9
Class4crypt c4c10.9a
Class4crypt c4c10.9a - © jorgeramio 2021 Lección 10.9a - página 9
Ataques a RSA
Lección 10.9a - página 10Class4crypt c4c10.9a - © jorgeramio 2021
• Ataques teóricos más conocidos• Ataque basado en la factorización del módulo n
• Resolviendo el Problema de la Factorización Entera PFE, se encuentra la clave privada d
• Ataque por cifrado cíclico• Conociendo el criptograma, se realiza un cifrado cíclico usando siempre la clave pública de la
víctima y es posible romper el secreto cifrado con confidencialidad pero no la clave privada d
• Ataque por la paradoja del cumpleaños• Conociendo solamente los datos públicos de la víctima, es posible encontrar la clave privada d
o una clave privada pareja d’ aunque pueden aparecer falsos positivos muy poco frecuentes
• Existen otros ataques: de exponente público e bajo, de módulo n en común, etc.
• Ataques reales• Ataque acústico por canal lateral
• La ejecución del algoritmo de exponenciación modular provoca sonidos entre los 30 KHz y los 40 KHz que permiten descubrir los bits ceros y unos de la clave privada d
Ataque por factorización entera
Lección 10.9a - página 11Class4crypt c4c10.9a - © jorgeramio 2021
• Objetivo• El atacante quiere conocer la clave secreta d a partir del conocimiento de
los valores públicos de la clave, es decir, n y e
• ¿A qué se enfrenta el atacante?• Al Problema de la Factorización Entera PFE
• La complejidad asociada al problema de la factorización entera para un número n, viene dada por una ecuación exponencial en donde los bits del número n a factorizar se encuentran en su exponente, un problema NP
• ¿Por qué esto rompería el algoritmo RSA?• Al factorizar n se obtienen los primos p y q, se calcula (n) = (p-1)(q-1) y
se encuentra la clave privada calculando d = inv [e, (n)]
Problema de la factorización entera PFE
Lección 10.9a - página 12Class4crypt c4c10.9a - © jorgeramio 2021
• Temática ya abordada en la Class4crypt c4c3.4 El problema de la factorización entera
https://www.youtube.com/watch?v=of_5ioayJo0
Desafíos de factorización módulos RSA
Lección 10.9a - página 13Class4crypt c4c10.9a - © jorgeramio 2021
• RSA-250 (829 bits), febrero de 2020
• Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, Paul Zimmermann
• Computadores Francia, USA, Alemania
• “This computation was performed with the Number Field Sieve algorithm, using the open-source CADO-NFS software
• The total computation time was roughly 2700 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz):• RSA-250 sieving: 2450 physical core-years
• RSA-250 matrix: 250 physical core-years”https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html
Decenas de miles de máquinas en pocos meses
Ataque a RSA por cifrado cíclico
Lección 10.9a - página 14Class4crypt c4c10.9a - © jorgeramio 2021
• Objetivo• Se trata de encontrar, a partir de un criptograma C, el número secreto N
que se ha cifrado con la clave pública e de destino o víctima, sin necesidad de conocer la clave privada d de ese receptor
• ¿Cómo se logra esto?• Como C = Ne mod n, a partir de este criptograma al que llamaremos C0,
realizaremos cifrados sucesivos con la clave pública e del receptor hasta volver a obtener el criptograma inicial C0
• Entonces• Si en el cifrado i-ésimo se encuentra nuevamente el criptograma inicial C0,
lógicamente el cifrado anterior (Ci-1) será el número secreto N buscado
Ejemplo de ataque a RSA por cifrado cíclico
Lección 10.9a - página 15Class4crypt c4c10.9a - © jorgeramio 2021
• Sea p = 13, q = 19, n = pq = 247 y (n) = (p-1)(q-1) = 216. Elegimos e = 5 y encontramos como clave privada d = 173, un valor desconocido
• Sea el número secreto a cifrar N = 123, entonces C = 1235 mod 247 = 54
C0 = 54 (valor que se captura) C4 = 65 mod 247 = 119
C1 = 545 mod 247 = 175 C5 = 1195 mod 247 = 123
C2 = 1755 mod 247 = 93 El atacante no se sabe que 123 era el secreto
C3 = 935 mod 247 = 6 C6 = 1235 mod 247 = 54 (ahora sí lo sabe)
• El ataque ha prosperado rápidamente porque son números muy pequeños
• Si usamos primos seguros, el ataque va a requerir una búsqueda mayor. Sean p = 11 y q = 23 ambos primos seguros, n = 253 y con e = 3. El secreto 123 que se cifra como 1233 mod 253 = 52, se recupera ahora en la vuelta 9 en vez de 5
Formación de varios anillos de números
Lección 10.9a - página 16Class4crypt c4c10.9a - © jorgeramio 2021
• Anillos clave RSA p = 41, q = 53, n = 2.173, e = 3
• Al realizar una cifra cíclica Ab mod n , en la que el nuevo resultado A’ (o C) se vuelve a cifrar con la misma clave pública e, se forman anillos de números
• En esos anillos, de longitudes distintas, se van ubicando todos los restos del módulo n o grupo de cifra, desde 0 hasta n-1
• Habrá anillos de corta longitud (pocos números) y anillos de larga longitud (muchos números)
• Uno de los 128 anillos de longitud 12 es el que se indica con estos doce números {2, 8, 512, 210, 1.847, 336, 1.168, 538, 1.519, 1.853, 840, 866}
LongitudNº Anillos
Prob.
12 128 70,69%
6 60 16,57%
4 40 7,36%
3 24 3,31%
2 18 1,66%
1 9 0,41%
Clave RSAn = 2.173, e = 3
Anillos de números con RingRSA: 24 bits
Lección 10.9a - página 17Class4crypt c4c10.9a - © jorgeramio 2021
95.852 anillos para clave de 24 bits resuelto en 9 segundos
Anillos de números con RingRSA: 32 bits
Lección 10.9a - página 18Class4crypt c4c10.9a - © jorgeramio 2021
18.791 anillos para clave de 32 bits resuelto en 432 minutos
Ataque cifrado cíclico a 40 bits: RingRSA
Lección 10.9a - página 19Class4crypt c4c10.9a - © jorgeramio 2021
http://www.criptored.upm.es/software/sw_m001q.htm
• Sea la clave RSA de 40 bits con• p = 757.507
• q = 940.957
• n = 712.781.514.199
• e = 65.537
• d = 281.742.544.313
• Y el secreto a cifrar N = 13
• 1365.537 mod 712.781.514.199 = 456.683.604.573
• El ataque cíclico al criptograma 456.683.604.573 requiere 77.610.060 operaciones en un grupo de cifra n mayor que 712 mil millones (tan solo el 0,0001 %) y éste se resuelve en 95 segundos de cómputo con una tasa de 820.000 cif/seg
Tanto N como C se encuentran en un anillo de 77.610.060 números
Ataque cifrado cíclico a 40 bits: genRSA
Lección 10.9a - página 20Class4crypt c4c10.9a - © jorgeramio 2021
• Para la misma clave de 40 bits de n = 712.781.514.199, con clave pública e = 65.537
• Con C = 456.683.604.573, genRSA v2.1 encuentra el secreto 13 en un tiempo de 69 segundos, con una tasa de cómputo de 1.125.000 cif/seg
• El texto en claro N y el criptograma C se encuentran en un anillo de 77.610.060 números diferentes
Esta clase continúa en la lección 10.9b
• Esta clase continuará en la lección c4c10.9b
• Ataques teóricos y prácticos a RSA parte 2
• De próxima publicación en este canal y en la que se tratarán los siguientes temas:• Ataque por la paradoja del cumpleaños• Ataque acústico por canal lateral• Lectura recomendada de la lección 10.9• Conclusiones generales de la lección 10.9
Class4crypt c4c10.9a - © jorgeramio 2021 Lección 10.9a - página 21
Un proyecto sin ánimo de lucro
• Class4crypt es un proyecto sin ánimo de lucro
• Si te ha gustado el vídeo, has aprendido algo nuevo o bien has podido reforzar algún conocimiento que ya tenías
• Entonces, por favor, pon un “Me gusta” al vídeo
• Si deseas expresar alguna opinión sobre el contenido de esta clase o tienes alguna duda, hazlo por favor en YouTube. Todos los comentarios serán muy bien recibidos y las dudas que plantees serán contestadas a la mayor brevedad posible
¡Muchas gracias!
Class4crypt c4c10.9a - © jorgeramio 2021 Lección 10.9a - página 22
Más lecciones en el canal Class4crypt
• https://www.youtube.com/user/jorgeramio
Fuera webcam y dentro música
> 2.560 suscriptoresal 12 de julio 2021
Lección 10.9a - página 23Class4crypt c4c10.9a - © jorgeramio 2021
Licencia y créditos
• Estas videoclases y la documentación utilizada en ellas están publicadas bajo licencia CreativeCommons tipo CC BY-NC-ND 4.0• Reconocimiento - No Comercial - Sin Obra Derivada
• Esto 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 c4c10.9a - © jorgeramio 2021 Lección 10.9a - página 24
Class4crypt c4c10.9a - © jorgeramio 2021 Lección 10.9a - página 25
La próxima semana, una nueva clase de Class4crypt
Criptosaludos