Criptografía Esencial

AGRADECIMIENTOS

Querríamos expresar nuestro agradecimiento, en primer lugar, a nuestros alumnos, en especial a aquellos que han cursado la asignatura Criptografía del Grado en Ingeniería de la Ciberseguridad y la asignatura Criptografía y Criptoanálisis del Máster en Ciberseguridad y Privacidad de la Universidad Rey Juan Carlos. Gracias por padecernos con una sonrisa, criticarnos, animarnos, y ayudarnos a ver qué conceptos resultan más difíciles de entender dentro de la Criptografía moderna y qué dificultades confrontan aquellos que se acercan a esta disciplina por primera vez.

Gracias también a nuestros maestros (en el sentido más amplio de la palabra), por ayudarnos a enfrentarnos a esos mismos obstáculos y empujarnos al abismo maravilloso de la investigación en Criptografía Matemática.

Y, gracias, siempre, a nuestras familias, que han soportado estoicamente nuestra deliciosa e irritante obsesión por la Criptografía Matemática, sus métodos, sus aplicaciones, y sus desafíos constantes sin los que, seguro, seríamos mucho más aburridos.

María Isabel González Vasco

Ángel Luis Pérez del Pozo

Alcorcón, Madrid. Noviembre de 2020.

AUTORES

MARÍA ISABEL GONZÁLEZ VASCO

Doctora y Licenciada en Matemáticas por la Universidad de Oviedo, obteniendo en ambos casos el Premio Extraordinario. Desde 2003 es profesora del área de Matemática Aplicada de la Universidad Rey Juan Carlos, en el que es Titular desde marzo de 2009. Ha impartido cursos de Criptografía y Criptoanálisis en diferentes contextos (grado, postgrado y máster), y es coautora de CryptoGo, un juego de cartas para enseñar Criptografía simétrica.

Su área de trabajo es la Criptografía Matemática, cuyo fin es establecer los modelos adecuados para proporcionar demostraciones formales que sirvan para determinar el nivel real de seguridad de distintas herramientas criptográficas. En particular, en criptoanálisis (análisis crítico) destacan sus resultados identificando vulnerabilidades en esquemas de cifrado construidos a partir de teoría de grupos así como señalando problemas en protocolos para intercambio de clave en entornos multiusuario. Entre sus trabajos constructivos destacan los marcos formales para conseguir reutilizar claves manteniendo propiedades demostrables de seguridad, las propuestas para calcular la intersección entre dos conjuntos con garantías de privacidad y los diseños para establecimiento de clave entre varios usuarios con autenticación por contraseñas.

María Isabel González Vasco ha publicado dos libros, más de 50 artículos en revistas y actas de congresos especializados, así como dos patentes. Ha participado y dirigido numerosos proyectos de investigación, destacando su papel actual como codirectora del proyecto Secure Communication in the Quantum Era financiado por el programa Science for Peace and Security de la OTAN.

Es miembro del comité editorial de las revistas Journal of Mathematical Cryptology e International Journal of Computer Mathematics: Computer Systems Theory. Sirve de manera habitual como recensora de revistas de referencia en Criptología (Journal of Cryptology, AAECC, Designs Codes and Cryptology, etc.) y participa frecuentemente en comités de programa de conferencias internacionales de referencia dentro de la criptología de clave pública (PKC, ACISP, ICITS). Además, ha formado parte del comité organizador de dos escuelas internacionales en Criptología Matemática (2008) y seguridad demostrable (2009), además de organizar en 2007 en Madrid el congreso internacional ICITS de seguridad basada en Teoría de la Información. A nivel nacional, pertenece periódicamente al comité de programa de la Reunión Española sobre Criptología y Seguridad de la Información, así como a distintos comités involucrados en las Jornadas Nacionales de Investigación en Ciberseguridad. Es, además, miembro de la IACR (International Association for Cryptologic Research) y vocal de la Junta de Gobierno de la Real Sociedad Matemática Española, a cuya comisión de publicaciones pertenece.

ÁNGEL LUIS PÉREZ DEL POZO

Licenciado en Matemáticas en 2001, con premio extraordinario por la Universidad Complutense de Madrid y Doctor en Matemáticas en 2005 por la misma universidad. Durante un año fue Profesor Ayudante en el Departamento de Biomatemática de Universidad Complutense. Desde septiembre de 2007 su carrera académica ha estado vinculada a la Universidad Rey Juan Carlos, donde ha ocupado plazas de Profesor Visitante y Profesor Ayudante Doctor, que es la que ostenta en la actualidad. Durante este periodo ha impartido clases en varias titulaciones científico-técnicas de asignaturas como Matemática Discreta, Álgebra Lineal, Lógica y Estrcuturas Algebraicas. En los últimos años ha sido también profesor de Criptografía en el Grado en Ingeniería de la Ciberseguridad y de Criptografía y Criptoanálisis en el Máster en Ciberseguridad y Privacidad, ambos impartidos por la URJC. Desde 2012 a 2014 trabajó como consultor de seguridad senior en las empresas Solium e Innovation for Security, ambas vinculadas al grupo BBVA.

Su línea de investigación principal es la Criptografía Matemática, dentro de la que ha realizado trabajos en las áreas del criptoanálisis de esquemas basados en grupos, el cifrado broadcast, los protocolos de computación muliparte para el cálculo privado de la intersección de conjuntos, el intercambio de claves de grupo y los esquemas de compartición de secretos. Ha publicado más de 20 artículos en revistas indexadas y actas de congresos internacionales y es coautor de dos patentes. Ha participado en varios proyectos de investigación con financiación nacional e internacional, entre los que puede destacarse el proyecto Secure Communication in the Quantum Era en el marco del programa Science for Peace and Security de la OTAN. Colabora habitualmente con miembros del Departamento de Informática de la Univesità degli Studi di Salerno, en la que ha realizado varias estancias de investigación. Ha participado en diversas actividades para la divulgación de la Criptografía, entre las que destacan un taller dentro del curso de verano Mates por todas partes de la UNED y varios talleres apoyados en el juego CrytpoGo.

Prólogo

El ecosistema en el que discurren nuestras vidas hoy en día es computacional. Está, en efecto, poblado de múltiples dispositivos de diferentes dimensiones, pesos, costes, consumos energéticos y propiedades específicas, que comparten la capacidad de almacenar información en formato digital, elaborarla y transmitirla a través de redes de diversa naturaleza.

Un ecosistema radicalmente distinto del de hace algunas décadas. Los instrumentos físicos analógicos para la reproducción de música o vídeo, por ejemplo, han desaparecido, suplantados por un único tipo de dispositivo, que trata los datos representados únicamente de un modo, en digital. Y muchas actividades que requerían alguna forma de interacción real, son a menudo sustituidas por operaciones equivalentes y más rápidas que el usuario efectúa a través de uno de esos dispositivos con el que está conectado a la red y que requiere simplemente cómputo y comunicación.

Vivimos, por tanto, en un ecosistema en el que muchísimas actividades han perdido fisicalidad y existen sólo en forma de transacciones digitales o de objetos representados mediante un flujo de bits que puede ser procesado y transmitido. En este nuevo ecosistema, los problemas de seguridad y de privacidad no han desaparecido: tenemos la necesidad de garantizar para todas las actividades reproducidas digitalmente las mismas propiedades de seguridad que garantizábamos en el mundo físico.

En el mundo físico, a menudo, eran de ayuda distintos tipos de soportes: candados y cajas fuertes para proteger material sensible, papeles especiales resistentes a falsificaciones para elaborar billetes bancarios y documentos importantes, sobres opacos para proteger nuestra oferta en una subasta, cabinas en los colegios electorales para proteger la privacidad de nuestro voto, procedimientos de identificación para reconocer nuestra identidad, procedimientos de autenticación para certificar la autoría de documentos y actos... y la lista podría continuar alargándose. Y estos soportes eran para nosotros tranquilizadores: teníamos confianza en ellos porque nos garantizaban, con buenos resultados, las propiedades de seguridad y de privacidad que deseábamos en el ejercicio de nuestra actividad.

En el ecosistema computacional en el que vivimos hoy no disponemos de todo esto. Pero disponemos de un potentísimo instrumento matemático que nos permite dar respuesta a los problemas de seguridad y de privacidad que surgen en el nuevo contexto: este instrumento es la Criptografía.

La Criptografía moderna proporciona, en efecto, técnicas matemáticas útiles para proteger la información digital, los sistemas de procesado y la computación distribuida de ataques adversarios. Permite garantizar la confidencialidad de las comunicaciones, la integridad de los mensajes intercambiados y la autenticación de los mensajes y los participantes en juego. Y, es más, permite la creación de protocolos que implementan de forma segura bases de datos distribuidas, autenticadas y persistentes, que implementan dinero digital, que soportan subastas electrónicas o juego on-line, que implementan formas de voto electrónico. En general, la Criptografía moderna se convierte en el instrumento que corrobora la confianza en la actividad y los procesos que hemos reproducido o creado desde cero en el mundo digital.

Este volumen presenta a los estudiantes, de forma sencilla, los principios y las técnicas básicas de la Criptografía moderna. De los preliminares de teoría de números y teoría de la complejidad a la seguridad demostrable y los protocolos avanzados, el tratamiento es siempre riguroso y preciso. Está escrito con riqueza de detalles por dos excelentes criptógrafos, figuras de referencia en la comunidad científica nacional y bien conocidos y apreciados en la comunidad internacional, como atestigua su curriculum vitae. La Profesora María Isabel González Vasco y el profesor Ángel Pérez del Pozo llevan años comprometidos con la investigación básica, con publicaciones en actas de importantes conferencias y prestigiosas revistas, así como con la enseñanza y la divulgación de la Criptografía a través de libros, proyectos y programas de trabajo que unen a entidades públicas y privadas.

He tenido el placer de colaborar con ellos durante cerca de 15 años. Aprecio profundamente su capacidad científica, profesionalidad y cualidades humanas: el cuidado que ponen en su trabajo y la atención que prestan a las personas con las que interactúan los convierten en un sólido punto de referencia.

Sin ninguna sombra de duda, escrito con competencia y pasión, este texto puede ser verdaderamente útil a los estudiantes: podrán apreciar la importancia de la Criptografía, aprender sus elementos básicos y ser capaces de utilizarla en todos los contextos en los que resulte necesario.

Salerno, a 20 de octubre de 2020

Paolo D’Arco,

Professore Associato, Universitá degli studi di Salerno, Italia.

Prefacio

La Criptografía, ciencia (y arte) de la gestión, transmisión, almacenamiento y procesado de información en entornos hostiles, es una disciplina fascinante en la que confluyen las Ciencias de la Computación, las Matemáticas, la Física y distintas áreas de Ingeniería. Resulta sorprendente analizar su evolución a lo largo de la historia, viendo cómo se ha desarrollado en paralelo a los diferentes sistemas de comunicación. Las primeras civilizaciones desarrollaron, a medida que avanzaban en nuevas formas de lenguaje y transmisión de mensajes a distancia, métodos más o menos ingeniosos para restringir el acceso a la información. Así, la llamada Criptografía simétrica, clásica o de clave secreta, se considera tan antigua como el lenguaje. Algunos jeroglíficos egipcios (datados hacia el 1900 a.C.) ya utilizaban simbología que era sólo conocida por ciertas clases de sacerdotes, en un intento de limitar el acceso al contenido de inscripciones consideradas delicadas. Hay también multitud de ejemplos de métodos de cifrado elementales utilizados por las antiguas civilizaciones del Mediterráneo, generalmente utilizados para enviar órdenes a los ejércitos manteniendo cierto nivel de confidencialidad. Este tipo de Criptografía clásica se cimenta en el principio de que sólo aquellos que conocen cierta información restringida (la clave) podrán tener acceso a los mensajes transmitidos a través de un cierto sistema de comunicación. En contraposición, la llamada Criptografía asimétrica o de clave pública, surge en los años setenta del siglo pasado partiendo de un escenario abierto en el que no podemos suponer el intercambio seguro de secretos a priori. En los últimos años, la proliferación de métodos y dispositivos para comunicarnos en entornos cada vez más complejos ha supuesto un reto fascinante para el desarrollo de herramientas criptográficas. También, esta proliferación ha traído la necesidad imperiosa de disponer de métodos formales para la validación de herramientas criptográficas que permitan perfilar con precisión cuál es más adecuado para cada contexto.

Esta obra es uno de los libros con más contenido matemático de la colección de Ingeniería de la Ciberseguridad de la editorial RAMA. Dicho contenido, minimalista en cierto sentido, es a nuestro juicio fundamental para cualquier ingeniero en ciberseguridad. Igual que no es posible ser un excelente arquitecto sin poder validar la calidad y robustez de los materiales de construcción, resulta impensable que un experto en ciberseguridad pueda desempeñar su labor sin conocer cómo funcionan las piezas básicas con las que se implementan soluciones en este ámbito: las herramientas criptográficas. Perseguimos pues con este volumen distintos objetivos:

Familiarizar al lector con la terminología y nociones fundamentales que se utilizan en Criptografía moderna,

Presentar los paradigmas de Criptografía simétrica y asimétrica, su filosofía y las primitivas esenciales que permiten conseguir los objetivos básicos de confidencialidad, integridad y autenticación.

Exponer, de manera sencilla y comprensible, las nociones elementales de seguridad demostrable, de modo que el lector pueda comprender demostraciones matemáticas sencillas de seguridad y entienda las implicaciones prácticas de los teoremas en este campo.

Permitir al lector asomarse al fascinante mundo de los protocolos criptográficos, ver distintos ejemplos de diseños adaptados a aplicaciones actuales en los que la Criptografía juega un papel esencial (y, a menudo, insospechado).

El material que presentamos se estructura en cinco capítulos. Cada uno finaliza con un breve test sobre los contenidos expuestos, y con una lista de lecturas sugeridas para profundizar en los temas tratados a lo largo del capítulo. Comenzamos en el Capítulo 1 dando una breve introducción a distintos fundamentos matemáticos y computacionales necesarios para la comprensión del resto del libro. Esta introducción es suficiente, pero en modo alguno exhaustiva, si bien seguramente sea prescindible para la mayoría de los lectores que hayan cursado asignaturas básicas de Álgebra Lineal, Matemática Discreta y Programación. El Capítulo 2 se centra en Criptografía simétrica o de clave secreta, dedicándose el Capítulo 3 a la Criptografía asimétrica o de clave pública. En ambos casos proporcionamos descripciones teóricas de diferentes tipos de construcciones, ilustrando dichas definiciones con ejemplos concretos cuidadosamente seleccionados. La seguridad demostrable, centrada en el caso asimétrico, se introduce en el Capítulo 4, donde hablamos fundamentalmente de seguridad para esquemas de cifrado. El Capítulo 5 contiene una muestra ilustrativa de diferentes tipos de herramientas criptográficas, quizá menos conocidas, pero sin duda esenciales para muchas aplicaciones actuales.

Finalizamos con un breve apéndice que contiene las soluciones a los tests presentados al final de cada capítulo.

1

PRELIMINARES

FUNDAMENTOS MATEMÁTICOS

Para afrontar el estudio de la Criptografía de manera seria es imprescindible manejar con soltura algunas nociones matemáticas. Muchas de ellas no están presentes en las enseñanzas previas a los estudios universitarios. En esta primera sección revisamos las que son necesarias para seguir el resto del libro.

Conjuntos, funciones y estructuras algebraicas

Definición. [Conjunto. Pertenencia] Un conjunto se define, de manera informal, como una colección de objetos, que reciben el nombre de elementos de ese conjunto. Se dice también que esos objetos pertenecen al conjunto.

Una opción habitual para describir un conjunto es enumerar sus elementos, que se escriben entre llaves y separados por comas. Así, por ejemplo, podemos escribir el conjunto formado por los 5 primeros números impares positivos como . Para denotar que pertenece al conjunto podemos escribir mientras que quiere decir que no es un elemento de .

Definición. [Contenido. Subconjunto] Dados dos conjuntos y , diremos que está contenido en si todo elemento de es también elemento de ; también se dice que es un subconjunto de y se escribe .

Definición. [Conjunto vacío] Necesitaremos un conjunto caracterizado por la propiedad de no tener elementos. A ese conjunto lo llamaremos conjunto vacío y utilizaremos el símbolo para representarlo. Es fácil convencerse de que, dado como hemos definido la relación de contenido, siempre se cumple que para cualquier conjunto .

Ejemplo. [Conjuntos numéricos] Será frecuente que trabajemos con conjuntos formados por números, que seguramente el lector ya conocerá. El más sencillo es el formado por los números naturales, los números de contar. Consideraremos que es el primer número de este conjunto; así escribiremos

,

donde los puntos suspensivos indican que este conjunto nunca termina de enumerarse ya que es infinito. A continuación tenemos el conjunto de los números enteros, que se obtiene añadiendo a el y los números negativos. Se denota

.

El conjunto de los números racionales se denota y está formado por las fracciones cuyo numerador y denominador son números enteros, siendo el denominador distinto de . Dos fracciones se consideran iguales con la noción habitual de equivalencia, es decir, si el producto cruzado de ambas coincide. Los números enteros se pueden considerar fracciones con denominador . Todo número racional tiene una expresión en base 10, que puede tener decimales. Esa parte decimal puede ser finita o infinita pero periódica. Si consideramos todos los números que tienen expresión decimal, siendo esta finita, infinita periódica o infinita no periódica, obtenemos el conjunto de los números reales . Algunos ejemplos de números reales que no son racionales son Usaremos para referirnos al conjunto de los números reales positivos, es decir, aquellos tales que: . Nótese que cada uno de estos conjuntos está contenido en el siguiente; así pues:

.

Otra forma de describir un conjunto, en lugar de mediante enumeración, es especificando las propiedades que cumplen sus elementos. Así, por ejemplo, el conjunto es el formado por los números reales del intervalo y es el conjunto infinito formado por los números primos (recordemos que un número entero es primo si y sus únicos divisores positivos son y