Algoritmo de Shor y factorización

Adolfo García Yagüe | En mi profesión, que un cliente dedique una hora de su tiempo a escucharte es un privilegio. Si de ese tiempo quieres reservar al menos 15 minutos para escuchar su opinión o contrastar alguna información relevante, la exposición se queda en unos 45 minutos, de los que solo 40 son realmente útiles: pequeños retrasos, introducción de por qué estamos aquí, etc.

Siendo optimista, cuentas con 40 minutos para recorrer 26 diapositivas, lo que significa que dispones de apenas 1 minuto y medio por slide. Es evidente que, en cuanto intentes profundizar en ciertos temas, consumirás el tiempo en explicaciones en las probablemente quedarás atrapado…

Esta introducción me permite hablar de la presentación que compartí hace unas semanas sobre Computación Cuántica y PQC. Aunque está siendo muy bien recibida y, desde que la liberé en mayo, la he presentado ya en una docena de clientes con un feedback satisfactorio, es una presentación de elevado riesgo por su densidad conceptual y las ramificaciones hacia temas que suscitan numerosas preguntas… con el temido riesgo de hacer descarrilar cualquier planificación de tiempos…

Aun así, hasta el momento no se ha producido ninguna catástrofe. Al contrario, cada exposición se ha convertido en un ejercicio de mejora continua que me permite afianzar conceptos que antes tenía algo difusos. Esa evolución me ha llevado incluso a construir en Excel un sencillo modelo del Algoritmo de Shor, que me ha servido para entender con mayor precisión su funcionamiento y explicar sus fundamentos de forma más clara. Os lo dejo para que podáis experimentar con él; además, me apoyaré en este ejemplo para repasar paso a paso cómo funciona el algoritmo.

Cifrado de clave pública RSA
Para este ejercicio he tomado como punto de partida el sistema de cifrado RSA (Rivest, Shamir y Adleman), desarrollado en 1977 y todavía ampliamente utilizado. Recordemos que el elemento público más importante de RSA es el número N, obtenido como el producto de dos números primos, p y q. Si un atacante consiguiera factorizar N y recuperar esos dos números primos, podría reconstruir la clave privada.

Aunque algunos podéis pensar —con razón— que RSA está siendo sustituido poco a poco por algoritmos basados en criptografía de curva elíptica (ECC, Elliptic Curve Cryptography), ambos comparten la misma idea fundamental: su seguridad descansa en problemas matemáticos que un ordenador clásico no puede resolver en un tiempo razonable.

La ventaja de usar RSA como ejemplo está en que parte de su base matemática resulta más intuitiva que la de ECC. Al fin y al cabo, tod@s hemos trabajado con números primos en el colegio y, cuando llega el momento de aplicar Shor, no resulta confuso calcular un máximo común divisor o construir una función periódica. Como veréis, estos conceptos se asimilan fácilmente y permiten percibir la gravedad del problema con mayor claridad.

Antes de seguir y así evitar que alguien se frote las manos pensando que vamos a enseñar a romper RSA con Shor, es importante recordar que nuestro ejercicio toma números muy pequeños de 2 y 3 cifras. Esto, en el mundo actual de la seguridad, es ridículo y cualquier número empleado en RSA es superior a las 600 cifras (2048 bits) llegando incluso a superar las 1200 cifras (4096 bits).

Esto es así porque, para un ordenador convencional, recuperar p y q a partir de un N lo suficientemente grande es computacionalmente inabordable. El método básico de criptoanálisis por fuerza bruta obligaría a buscar divisores de forma secuencial y, aunque se empleen algoritmos como General Number Field Sieve (GNFS), el problema sigue siendo descomunal ya que romper un módulo RSA de 2048 bits continúa siendo una tarea computacionalmente inabordable con la tecnología actual.

Algoritmo de Shor
En 1994, el matemático Peter Shor (1959) demostró que la factorización de números no tenía por qué resolverse mediante una búsqueda exhaustiva. Su algoritmo transformó el citado problema de factorización de N en el de hallar el período de una determinada función. Para ello, el primer paso consiste en construir una función a partir del número N —recordemos, el módulo público del sistema RSA— y estudiar su período.

A primera vista puede parecer una idea extraña. ¿Qué tiene que ver el período de una función con la factorización de un número? Antes de responder a esa pregunta conviene olvidarnos por un momento de los ordenadores cuánticos. De hecho, podemos comprender la idea utilizando únicamente la hoja de cálculo adjunta.

El primer concepto que necesitamos conocer es la aritmética modular, también conocida como “la matemática de los relojes”. En un reloj, cuando pasan doce horas volvemos a empezar desde la una. No importa cuántas vueltas demos; el reloj siempre muestra un número comprendido entre 1 y 12.

La aritmética modular funciona exactamente igual. Si trabajamos, por ejemplo, módulo 12, cualquier resultado que supere ese valor vuelve a empezar desde el principio. Así, 9 + 5 = 14, pero como 14 deja un resto de 2 al dividirlo entre 12, escribimos simplemente:

14 mod 12 = 2

La criptografía RSA utiliza precisamente este tipo de matemáticas. En lugar de trabajar con números cada vez más grandes, realiza continuamente operaciones “módulo N”. Gracias a ello, aunque las cifras intermedias sean gigantescas, el resultado final siempre queda comprendido entre 0 y N − 1.

La función que empleó Shor es sorprendentemente sencilla:

f(x) = aˣ mod N

donde N es el módulo público de RSA y a es un número entero elegido de forma que no comparta factores con N. Para comprobarlo utilizamos una operación muy conocida en matemáticas: el máximo común divisor (MCD), que indica cuál es el mayor número que divide exactamente a otros dos. Si el MCD de a y N es igual a 1, decimos que ambos números son coprimos y podemos continuar. Curiosamente, si el MCD fuese mayor que 1, habríamos encontrado directamente uno de los factores de N, resolviendo el problema incluso antes de empezar. Veamos un ejemplo muy sencillo:

En nuestro ejemplo, supongamos que el módulo público es N = 15 y elegimos a = 2. Como el MCD de 2 y 15 es 1, podemos construir la función y empezar a calcular sus valores (podéis cambiar estos valores en la hoja hasta un máximo de N=101).

En esta tabla lo interesante es el resultado de la segunda columna. Si nos fijamos, en ella observaremos un patrón que se repite 1, 2, 4, 8, 1, 2, 4, 8… La función ha entrado en un bucle. Decimos entonces que su período r es igual 4, porque cada cuatro valores la secuencia vuelve exactamente al mismo punto.

Y aquí aparece la idea brillante de Peter Shor. Ese número, que a primera vista parece un simple dato más, contiene en realidad la información necesaria para recuperar los factores primos de N.

Sin entrar en la demostración matemática, basta saber que, cuando el período es par y se cumplen determinadas condiciones, tomamos el mismo valor de a que elegimos al principio y lo elevamos a la mitad del período (r/2).

En nuestro caso:

r = 4     y    a = 2

Por tanto:

2 ^(4/2) = 4

Nota: En este ejemplo ocurre una curiosidad ya que el período r vale 4 y el cálculo de a^(r/2) también da como resultado 4. Es una simple coincidencia. En general, ambos valores no tienen por qué guardar ninguna relación. Dicho esto, a partir de ese resultado solo tenemos que realizar dos cálculos utilizando el máximo común divisor.

Primero restamos una unidad:

MCD(4 − 1, 15) = 3

Después sumamos una unidad:

MCD(4 + 1, 15) = 5

Y, casi sin darnos cuenta, hemos recuperado los dos factores primos del número:

15 = 3 × 5

Una vez conocido el período, factorizar el número deja de ser un problema complicado. La verdadera dificultad consiste en descubrir ese período cuando N tiene cientos o miles de bits, como ocurre en las claves RSA reales.

Nuestra hoja de cálculo reproduce el método clásico: incrementa el valor de x, calcula aˣ mod N y espera hasta que la secuencia empieza a repetirse. Con números pequeños funciona perfectamente, pero con una clave RSA real esa búsqueda puede resultar prácticamente inabordable.

¿Cómo evita ese problema un ordenador cuántico? La clave está en la Transformada Cuántica de Fourier (Quantum Fourier Transform o QFT). Aunque su nombre resulte complejo, su función es muy sencilla: poner de manifiesto la periodicidad de la función.

Una buena analogía es la música. Cuando escuchamos una orquesta percibimos una única melodía, aunque en realidad está formada por muchos instrumentos. La transformada de Fourier actúa como una herramienta capaz de separar esos sonidos y revelar el patrón que había oculto. En el algoritmo de Shor hace algo parecido: utiliza la superposición cuántica para trabajar con muchos valores de x simultáneamente y, mediante la Transformada Cuántica de Fourier, hace visible el período de la función.

Esa es la auténtica revolución del algoritmo de Shor. El ordenador cuántico no factoriza números por arte de magia ni calcula las potencias modulares mucho más deprisa; simplemente encuentra el período de la función de una forma mucho más eficiente. Una vez conocido ese período, el resto del algoritmo vuelve a ser completamente clásico y permite obtener los factores primos mediante unas sencillas operaciones con el máximo común divisor. Y precisamente por eso ha sido necesario desarrollar una nueva generación de algoritmos PQC (Post-Quantum Cryptography) resistentes a este tipo de ataques.

[Descargar hoja de cálculo]

Computación Cuántica y Criptografía Postcuántica

Adolfo García Yagüe | Cuando hace unos meses hablábamos de radiotelegrafía, algunos lectores repararon en que entre los documentos de la colección hay un estadillo militar de 1912 donde se contabilizaban los mensajes cifrados del año anterior. Aquello, lejos de ser una singularidad, es una pequeña muestra de la relación que ha existido desde la antigüedad entre el cifrado y el mundo militar.

Desde los sacerdotes egipcios, que reservaban la escritura jeroglífica a una élite, hasta los espartanos del siglo V a. C., que empleaban la escítala para enviar órdenes secretas, la necesidad de ocultar información ha sido constante. Durante siglos, la criptografía fue un arte reservado a gobernantes, diplomáticos y militares. Hoy, sin embargo, forma parte de nuestra vida cotidiana, aunque la mayoría no seamos conscientes de ello: cada conexión con un servidor en Internet, cada pago electrónico, cada instalación de una app en el smartphone o, por ejemplo, cualquier procedimiento para certificar nuestra identidad digital dependen de la criptografía.

La complejidad y el oscurantismo que la rodean no son casuales, pues entender sus fundamentos exige conocimientos de matemáticas, informática, estadística y, antaño, lingüística. Aun así, su evolución puede narrarse como una sucesión de cambios de paradigma en los que historia y tecnología se entrelazan con acontecimientos decisivos. En este sentido, conviene recordar que hace un siglo la criptografía clásica quedó obsoleta frente a las máquinas de rotores y las técnicas inspiradas en el cifrado de Vernam. Más tarde, en los años setenta, ambas cedieron el paso al cifrado computacional basado en problemas matemáticos difíciles de resolver.

Hoy vivimos otro momento de transición en el que la computación cuántica amenaza esos problemas «difíciles» que sustentan a Diffie-Hellman, RSA (Rivest–Shamir–Adleman) y ECC (Elliptic Curve Cryptography), ya que un ordenador cuántico capaz de ejecutar el algoritmo de Shor podría factorizar números enteros y resolver logaritmos discretos con una eficiencia imposible para la computación clásica. Incluso los algoritmos simétricos robustos, como AES (Advanced Encryption Standard), o las funciones criptográficas, como SHA (Secure Hash Algorithm), se verán afectados por el algoritmo de Grover, al reducir el esfuerzo de fuerza bruta a su raíz cuadrada y obligar a duplicar los tamaños de clave para mantener el mismo nivel de seguridad. Por estas razones, y aunque aún hoy no existan máquinas cuánticas capaces de hacerlo a gran escala, el riesgo HNDL (Harvest Now, Decrypt Later) ya es real: los datos cifrados hoy podrían ser descifrados mañana.

En este contexto se enmarca esta presentación. Su objetivo es ayudar a los clientes de Axians —y a cualquier interesad@— a comprender la amenaza cuántica, explorando cómo funciona actualmente un ordenador cuántico y a qué desafíos se enfrenta esta tecnología. A continuación, explicaremos en qué se basan los nuevos algoritmos PQC (Post-Quantum Cryptography) estandarizados por el NIST (National Institute of Standards and Technology, EE. UU.) y cómo se integran en un certificado X.509 y en la negociación TLS (Transport Layer Security), IKE (Internet Key Exchange) e IPSec. Más adelante revisaremos las iniciativas impulsadas por diversas instituciones europeas y su impacto en la normativa vigente: DORA (Digital Operational Resilience Act), NIS2 (Network and Information Security Directive 2) y eIDAS (Electronic Identification, Authentication and Trust Services). Por último, presentaremos una estrategia de referencia para abordar la transición hacia PQC y analizaremos cómo algunos fabricantes de soluciones de seguridad están afrontando este reto.

No lo olvidemos: la criptografía es la capa matemática que garantiza la confidencialidad, la integridad y la autenticidad de los datos, además de salvaguardar la identidad y la confianza digital. Y, por primera vez en medio siglo, nos vemos obligados a replantear sus cimientos.

[Descargar presentación]

Introducción a la Ciberseguridad

Adolfo García Yagüe | Hacia el final de este año escolar, me pidieron que diera una pequeña charla a jóvenes que estaban terminando la ESO. El objetivo era que conocieran una profesión y les ayudara a enfocar su carrera profesional.

En la presentación, intenté resumir algunos conceptos clave de la ciberseguridad: su evolución histórica, cómo se desarrolla un ataque y qué es MITRE ATT&CK. 40 diapositivas no dan para mucho y sé que me dejé miles, quizás millones, de cosas en el tintero.

Espero haber despertado alguna inquietud o, al menos, haber contribuido a que todos seamos más cuidadosos cuando hacemos clic. Si alguien se aburre este verano se puede descargar el PDF, está limpio 😉

Introducción

• Perspectiva histórica
• Automatización, Criptomonedas, Darknet e IA
• Adversario

Desarrollo de un Ciberataque

• Activos
• Superficie de exposición
• Riesgo
• Información
• Vulnerabilidades
• Exploits
• Malware
• Movimiento Lateral
• Ransomware
• Herramientas

Modelos de Amenazas y Marcos de Referencia

• Cyber Kill Chain
• Pirámide del Dolor
• MITRE ATT&ACK

[Descargar presentación]

Pila de Volta

Irene García Fierro | Hola, tengo 11 años y estoy acabando 6 de Primaria. En las últimas lecciones de Ciencias Naturales hemos estudiado la electricidad y la profesora nos ha pedido que hiciésemos un circuito eléctrico. Yo he elegido fabricar una Pila de Volta para ver cómo se genera electricidad mediante un proceso químico, a la vez que hago un pequeño circuito de encendido y apagado de una bombilla. Os voy a contar la historia de esta pila y como funciona.

Todo empezó en 1780 cuando Luigi Galvani (1737-1798), que era un famoso médico, estaba haciendo experimentos con ancas de ranas muertas a las que, aplicando una corriente eléctrica, se movían. En estos experimentos también comprobó que acercando ciertos metales a las ancas de rana estas se también movían. Aquello dio mucho que hablar y se empezó a pensar en la relación entre los cuerpos de los animales y la electricidad. Incluso se pensó que aplicando electricidad a un muerto este se podía resucitar. Estas ideas inspiraron a Mary Shelly (1797-1851) a escribir la famosa novela de terror Frankenstein de 1818. En ella se cuenta como un doctor revive el cuerpo de un monstruo que está formado por las partes de varios muertos.

Los experimentos de Galvani eran conocidos por su colega el químico Alessandro Volta (1745-1827) quien profundizó en el experimento de la aproximación de los metales y el movimiento del anca. Quería entender porque se producía este movimiento y su relación con ciertos metales. En 1800 fabricó un aparato al que llamó “Órgano Eléctrico Artificial” y con él demostró que la electricidad se producía en los metales, no en el anca de la rana. Aquel invento fue presentado a todos los científicos e introdujo a la humanidad en una nueva era de aplicaciones de la electricidad y el invento se renombró como “Pila de Volta”.

La Pila de Volta que he fabricado está compuesta por 5 celdas. Cada celda consta de un vasito de agua con un poco de sal al que llamamos electrolito. Dentro de ese electrolito hay dos electrodos: una moneda de cobre antigua y una arandela de zinc. Si te das cuenta en la foto los electrodos de cobre y zinc están conectados entre sí por cables. Por estos cables circulan los electrones que hacen que se encienda una bombilla cuando enciendo y apago un interruptor.

En reconocimiento del gran descubrimiento de Alessandro Volta se puso el nombre de voltio a la unidad eléctrica que mide la tensión eléctrica. Todos los días usamos baterías y consumimos voltios gracias a Volta.

Construcción de un Telégrafo

En la presentación anterior daba unas pinceladas del funcionamiento de un circuito eléctrico y su aplicación en un telégrafo. Ahora, como segunda parte, es el momento de construirlo.

He intentado que los componentes y herramientas sean fáciles de conseguir. Quizás, el menos común, sea el manipulador telegráfico pero es posible comprarlo a través de eBay o Amazon por unos pocos euros. Evidentemente, para la construcción se requiere el uso de algunas herramientas que, potencialmente, son peligrosas como el taladro y el soldador. Por favor, tienes que ser prudente y, si no te sientes seguro usando la herramienta o conectando el telégrafo a tierra, pide ayuda a una persona con conocimientos. Es tu responsabilidad. Gracias.

Colección | Descargar presentación | Telégrafo y Telecomunicación | Marconi y el Día Internacional de la Radio | Telegrafía y Telefonía | La radio en España. Pioneros (1) | La radio en España. Radiotelegrafía (2)

Telégrafo y Telecomunicación

A mi hija de 10 años le ha tocado estudiar los componentes básicos de un circuito eléctrico. Para quien no lo sepa es una lección más del temario de Ciencias Naturales de 5º de Primaria. Mientras repasábamos, noté que es dificil encontrar un circuito eléctrico básico a nuestro alrededor y, dejando a un lado el encendido y apagado de la iluminación o el secador de pelo, echaba en falta una aplicación donde analizar cada uno de sus componentes. Fue en ese momento cuando, sin poder evitarlo, recurrí a ingenios del pasado como el Telégrafo para ilustrar el tema de estudio. Mi hija me miraba sorprendida cuando le contaba la epopeya y adversidades de los primeros tendidos de cable submarino o las dificultadas para amplificar una ruta.

Alguna de estas explicaciones las puse en orden en un PowerPoint recordando a Samuel Morse. Lo sé, me emocioné un poco pero aquello era un ejemplo claro y práctico de un circuito eléctrico, además sentaba las bases de otra revolución de la humanidad: las Telecomunicaciones.

Colección | Descargar presentación | Construcción de un Telégrafo | Marconi y el Día Internacional de la Radio | Telegrafía y Telefonía | La radio en España. Pioneros (1) | La radio en España. Radiotelegrafía (2)

La Impresora Láser

Irene García Fierro | He escrito esta presentación porque creo que la impresora láser es muy útil y porque me gusta mucho imprimir dibujos y textos. También quiero que conozcáis a su inventor, Gary Starkweather y lo importante que han sido los inventos de Xerox y, por supuesto, para que veáis como funciona una impresora.

Haz click para descargar la presentación

Aquí podéis visitar el espacio de la galería donde voy colocando más presentaciones

Los seres microscópicos

Irene García Fierro | Esta es la segunda presentación que cuelgo en ccapitalia. Va sobre un tema que siempre me ha interesado: las células y las enfermedades. Todas las fotos las he sacado yo con el microscopio que tengo en casa y las preparaciones que mi padre ha ido consiguiendo de diferentes sitios. Espero que os guste y sirva de ayuda.

Aquí podéis visitar el espacio de la galería donde voy colocando más imágenes.

Los Móviles

Irene García Fierro | Me llamo Irene, tengo 9 años y es la primera vez que escribo en Internet. Esta presentación la he hecho para que mis amigos del colegio conozcan cómo han cambiado los teléfonos móviles desde que se inventaron. También me he llevado estos móviles a clase para que los compañeros los conozcan.

Mis padres no me quieren regalar un móvil y me tengo con conformar con antigüedades ¡Qué rollo, yo quiero un móvil moderno!

Descargar presentación | Colección | 1G o primera generación de telefonía móvil | HarmonyOS y los Sistemas Operativos Móviles | GTP y la seguridad en redes 4G y 5G NSA

Ciberseguridad e IoT

Adolfo García Yagüe | Estos días estoy dando un curso sobre Ciberseguridad e IoT en Fuenlabrada. Se enmarca en un proyecto impulsado por el propio Ayuntamiento y la Unión Europea. Se pretende formar a los asistentes en nuevas capacidades con el fin de reforzar y actualizar su curriculum. Es una iniciativa admirable que ayuda a crear sociedad y, sobre todo, porque me está permitiendo conocer la realidad de otras personas. En este módulo denominado “IoT” comparto el papel de formador junto a otros profesionales de Flexbot, la Fundación Telefónica y la Fundación Santa Maria la Real. Como digo es un privilegio estar ahí.

Os dejo la presentación del curso que estoy dando por si os resulta de interés. Como digo va sobre IoT, economía de datos, comunicaciones y seguridad. Muchas de las cosas que aquí trato son totalmente trasladables a nuestra cotidianeidad como usuarios de un equipo informático o un Smartphone. También, como no, se aclaran conceptos acerca de la importancia de los datos o 5G y como puede cambiar el entorno en el que vivimos. Milma Fuenlabrada. Laboratorio IoT

Agenda

Acerca del TELNET
Conceptos de IoT y Sistemas Embebidos

• Telemetría y telecontrol
• Smartphones
• Internet de las Cosas
• Tratamiento y economía de datos, Big Data
• Dispositivos basados en Microcontrolador y Microprocesador
• Arduino
• Raspberry PI
• TELNET BabelGate
• Riesgos Amenazas y Ataques

Software y Hardware

• Seguridad Física
• Identificación de vulnerabilidades
• Bootloader, Kernel, drivers y librerias
• Aplicaciones
• Cifrado
• Repositorios de claves
• Puertos Abiertos, Banners y Port-Knocking
• API (Application Program Interface)
• Ejemplo de instalación y mantenimiento desatendido
• Electrónica y Buses
• Memorias SD
• SIM (Subscriber Identity Module)
• TPM (Trusted Planform Module)

Conectividad Inalámbrica de un dispositivo IoT

• Conectividad Radio
• Frecuencias
• Topología, seguridad y radio
• Servicios M2M de Operador
• Sigfox
• LoRa
• Zigbee
• Z-Wave
• Bluetooth
• IEEE 802.11

Buses y Redes Industriales

• Seguridad lógica en Redes Industriales
• PRIME/COSEM

[Descargar ponencia]