María Isabel González Vasco

Las matemáticas

de la criptología

Secretos demostrables

y demostraciones secretas

diseño de cubierta: estudio sánchez/Lacasta

© María Isabel González Vasco, 2018

© Federación Española de Sociedades de Profesores

de Matemáticas (FESPM), 2018

Servicio de Publicaciones

Avda. de la Mancha s/n

02006 Albacete

www.fespm.es

© Instituto de Ciencias Matemáticas (ICMAT), 2018

Nicolás Cabrera, nº 13-15

Campus de Cantoblanco, UAM

28049 Madrid

www.icmat.es

© Los libros de la Catarata, 2018

Fuencarral, 70

28004 Madrid

Tel. 91 532 20 77

www.catarata.org

Las matemáticas de la criptología.

Secretos demostrables y demostraciones secretas

ISBN: 978-84-9097-505-3

e-ISBN: 978-84-9097-513-8

DEPÓSITO LEGAL: M-19.825-2018

IBIC: PDZ/GPJ

este libro ha sido editado para ser distribuido. La intención de los editores es que sea utilizado lo más ampliamente posible, que sean adquiridos originales para permitir la edición de otros nuevos y que, de reproducir partes, se haga constar el título y la autoría.

A Carlos, María y Nacho, mis usuarios honestos, pero infinitamente curiosos.

A Palmira, depositaria de todos los secretos.

Introducción

Como casi todas las cosas importantes en la vida, la criptografía me encontró en un pupitre del colegio. Mi amiga Sara, sentada dos filas delante, tenía algo que contarme y escribía pequeños renglones en fragmentos de papel cuadriculado que intentaba hacerme llegar escondidos en su goma o en la caña de un bolígrafo. Sin duda, burlar la vigilancia de al menos dos potenciales entidades interesadas en nuestros mensajes (a la sazón, mi compañero de pupitre y don Primitivo, nuestro profesor de cuarto) era la principal razón de ser de este intercambio de información. Nuestra técnica fue, por tanto, ganando en sofisticación: una vez vimos claro que no bastaba con intentar esconder la existencia de la transmisión que nos ocupaba, comenzamos a pensar en ocultar no la presencia de los mensajes, sino su contenido.

Este tipo de procesos se repiten cada día en miles de aulas de educación primaria a lo largo del mundo. Esto no es sorprendente, pues la criptología, definida como “ciencia y práctica del diseño de sistemas de comunicación que son seguros en presencia de adversarios”1, surge de modo inseparable de la necesidad de comunicación del ser humano. Existen evidencias históricas de métodos para la ocultación de la transmisión de la información (técnicas esteganográficas)2 y esquemas de cifrado elementales contemporáneos de los lenguajes más antiguos conocidos. Por ejemplo, la escritura cuneiforme de los sumerios o el lenguaje jeroglífico de los egipcios son métodos de comunicación cuyo fin es transmitir información no de manera universal, sino a ciertos receptores autorizados. Un esquema de cifrado, la herramienta criptográfica más conocida y antigua, persigue exactamente eso: no el ocultar que existe transmisión de información, sino limitar el acceso a la información transmitida por medio de instrumentos matemáticos.

La criptología tiene dos vertientes bien diferenciadas: una constructiva y otra crítica o destructiva. La primera, llamada criptografía, se ocupa del diseño de herramientas, mientras que la segunda, el criptoanálisis, es el estudio crítico de las mismas. Criptógrafos y criptoanalistas llevan siglos enzarzados en una pugna cuyo resultado son construcciones cada vez más seguras para todo tipo de aplicaciones relacionadas con la gestión, transmisión y almacenamiento de información. Ambos buscan sus armas en un arsenal inagotable y precioso: las matemáticas. El papel de las matemáticas en criptología es central desde dos puntos de vista. Por un lado, como fuente de problemas cuya dificultad mantendrá bajo control a adversarios externos y usuarios maliciosos de un cierto sistema. Por otro, las matemáticas proporcionan el único lenguaje formal adecuado para la cimentación de demostraciones rigurosas e irrefutables de seguridad.

Hasta finales del siglo pasado, las construcciones criptográficas eran fundamentalmente esquemas de cifrado, diseñados para conseguir transmitir de manera segura información entre dos usuarios. En los últimos cuarenta años, sin embargo, las reglas del juego han cambiado radicalmente. La forma en que hoy compartimos, gestionamos y almacenamos la información plantea escenarios de aplicación fascinantes que suponen un reto constante para criptógrafos y criptoanalistas.

Este libro es una introducción a la criptología desde una perspectiva moderna. En cada capítulo presentaremos al lector un tipo de construcción criptográfica, profundizando en las herramientas matemáticas que pueden usarse para su implementación. Queremos acercar al lector a la criptología de manera amena y divulgativa, y presentarle además las ideas y conceptos matemáticos que subyacen en diferentes construcciones criptográficas. Nuestra ambición es proporcionar al lector un beneficio doble: aprender matemáticas a través de la criptología y desarrollar la inquietud por la criptología moderna desde el placer del formalismo matemático. Así, este libro proporciona a los profesores de educación secundaria algunos ejemplos novedosos con los que motivar a sus alumnos en el aprendizaje. Con ese fin plantearemos distintos retos o ejercicios sencillos, que pueden ser abordados con éxito por estudiantes de este nivel.

Capítulo 1

Criptografía simétrica.

Al César lo que es del César

Volvamos atrás, quizá no tantos años, hacia un pasado sin internet, sin mensajería instantánea, sin móviles. Un pasado en el que los mensajes eran complejos en fondo y forma, redactados con paciencia y pulcritud. Entonces, los destinatarios eran pocos y selectos, y en la mayoría de los casos no se enviaba más de una carta cada mes, precedida de varios encuentros cara a cara. Este escenario, que parece rescatado de una infancia en blanco y negro, era el marco habitual de la comunicación hasta hace menos de treinta años. Es en cierta manera el ideal al que se aspira: cada día se intenta simular cientos de veces a través de la comunicación digital. La razón es sencilla; querríamos confiar en la autenticidad y confidencialidad de un archivo de datos recibido por e-mail igual que hacemos al recibir un sobre inmaculado (sin trazas de manipulación) por correo ordinario.

Este escenario en blanco y negro es el hábitat natural de la llamada criptografía simétrica (también llamada criptografía clásica o de clave privada). Parte del supuesto de que los interlocutores involucrados comparten un secreto grande, acordado en una fase previa completamente confiable, como podría ser un encuentro en persona. En este contexto, grande significa difícil de predecir o, en términos técnicos, de alta entropía. Actualmente, se considera que una cadena de ceros y unos (bits) es de alta entropía si su longitud es, al menos, de 180 bits. En contraposición, cadenas de 30 bits o menos suelen considerarse de baja entropía; ese es, por ejemplo, el caso de las contraseñas que somos capaces de memorizar. La entropía puede definirse rigurosamente como una medida para cuantificar la incertidumbre: en física, por ejemplo, sirve para medir el desorden, la desorganización de un sistema.

El secreto que comparten los dos usuarios, emisor y receptor, es la consigna que servirá para enviar mensajes entre ellos. Esta clave servirá tanto para cifrar (transformar el mensaje original en otro que, en caso de ser interceptado, sea inteligible si no se dispone de la clave) como para descifrar los mensajes (recuperar el mensaje original, a partir del mensaje cifrado, para poder leerlo).

En lenguaje matemático

Formalicemos matemáticamente esta idea. Nombramos, como es habitual en los libros de criptología, Alice a nuestra emisora y Bob al receptor. Todos los objetos involucrados en la transmisión viven en una estructura algebraica X, es decir, un conjunto en el que está definida una cierta operación * (por ejemplo, los números enteros y la operación suma). Tanto el conjunto de posibles mensajes sin cifrar (al que llamaremos M) como el de mensajes ya cifrados (llamémosle C) están contenidos en X. Distinguiremos un subconjunto especial, K, dentro de X, donde estarán las llamadas claves simétricas. Estas claves son los elementos indispensables para transformar un texto claro en un texto cifrado, y también para revertir esta transformación.

Formalmente, un esquema de cifrado se definirá haciendo explícitos tres procesos o algoritmos3:

Un algoritmo de generación de clave, denotado KeyGen, que sirva para seleccionar cada una de las claves utilizadas a partir de un valor prefijado, llamado parámetro de seguridad. Este suele ser una medida de la fortaleza del esquema en cuestión.

Un algoritmo de cifrado, que denotaremos Enc, que recibe como entrada una clave y un mensaje claro y da como salida un texto cifrado.

Un algoritmo de descifrado, denotado por Dec, que recibe como entrada una clave y un texto cifrado y da como salida un mensaje claro.

Así, un esquema de cifrado Π = (KeyGen, Enc, Dec) será correcto si el algoritmo de descifrado permite recuperar el texto claro m que subyace a un texto cifrado c, siempre que se le dé como entrada la clave k que sirvió para construir c. En símbolos:

Enc(k, m) = c ⇒ Dec(k, c) = m

para toda clave k que haya sido seleccionada por KeyGen.

Alice será la encargada de ejecutar Enc, mientras que Bob tendrá que usar el algoritmo Dec para descifrar. En principio, si ambos usan la misma clave y nadie más la conoce, todo irá bien.

Un poco de historia

Un ejemplo clásico de cifrado simétrico usando la notación anterior es el cifrado de César. Gracias a los escritos de Suetonio4, datados en el siglo segundo antes de Cristo, sabemos que el emperador romano Julio César empleaba un sencillo sistema para cifrar sus misivas más delicadas. Simplemente, César sustituía cada letra del alfabeto latino por la que ocupaba tres posiciones más adelante, volviendo a las primeras letras desde el final para cifrar las tres últimas. Así, podemos decir que efectuaba una simple sustitución utilizando una tabla como esta:

Tabla 1

Cifrado de César

A

B

C

D

….

W

X

Y

Z

D

E

F

G

X

A

B

C

La primera fila contendría las letras del texto claro y la segunda el resultado tras cifrar. Así, el mensaje “TAMBIÉN TÚ, BRUTO” —obviando la coma y los acentos— quedaría cifrado como “WDPELHQ WX EUXWR”.

Este método es muy sencillo, pero presenta ciertos problemas. El primero es que no hay variabilidad, es decir, al cifrar el mismo texto claro siempre obtendremos el mismo texto cifrado como resultado. Esta característica, llamada determinismo, es evidentemente una debilidad. Todo aquel que conozca el descifrado de un texto concreto podrá identificar las palabras contenidas en este que se repitan en envíos posteriores. Por ejemplo, la cadena “QR” en los textos cifrados siempre quiere decir “NO”. Un espía que sepa que una respuesta “QR” de César es negativa, sabrá reconocer la palabra “NO” contenida en cualquier mensaje que se envíe, pues el cifrado de esta siempre será “QR”.

En lenguaje matemático

Pasemos a describir formalmente el esquema de César para así entender de manera más general dónde está el problema. El conjunto X que nos sirve de estructura básica será el alfabeto latino, que codificaremos con los números del 0 al 25.

La operación de cifrado es, por tanto, sumar 3 al número que representa cada letra del texto claro. Pero al llegar a la última letra, se vuelve a empezar desde el comienzo. Así, la X se cifraría con la A, la Y con la B y la Z con la C (como pasa con el reloj, al llegar al 12, se vuelve a pasar al 1). Esta operación se llama suma módulo 26. Operamos, por tanto, identificando cada número con el resto que da al dividirse por 26. En el caso concreto de sumar tres, cuando el resultado de la suma sea superior a 25, restamos a este 26 (para obtener, de nuevo, un número en el rango adecuado). Para manejarnos con este tipo de aritmética es útil pensar que el 26 se transforma en un cero. Así, al sumar o restar —las veces que queramos— 26 a un número X, nos quedamos en el mismo número.

Tabla 2

Codificación para el cifrado de César

A

B

C

D

….

X

Y

Z

0

1

2

3

23

24

25

Para descifrar, de nuevo, utilizamos la codificación numérica descrita en la tabla 2 y restamos a cada número recibido el 3, ajustando (sumando 26, si obtenemos un número negativo) para tener siempre números entre 0 y 25.

Así, nuestro conjunto X es el de los enteros {0, 1, …, 25}, y la operación de cifrado puede describirse como

Enc(m) = m + 3 mod 26

siendo el descifrado

Dec(m) = m – 3 mod 26

donde la expresión “mod 26” se traduce como “divide entre 26, y quédate con el resto”. En efecto, estamos usando, en realidad, una estructura algebraica clásica, el grupo aditivo que se define en el conjunto de números enteros {0, …, n – 1} denotado por Zn con la operación suma mod n anteriormente descrita (para n = 26).

Y, en este caso, ¿cuál es la clave? Dicho de otra forma: ¿qué valor de X = Z26 es imprescindible conocer para cifrar y descifrar? La respuesta es sencilla: el número 3. El tamaño del “salto” con el que ciframos y desciframos determina la clave y, además, se mantiene estable. Esto nos permite deducir que Julio César, o bien no tenía demasiadas ocasiones para acordar claves de cifrado con sus homólogos, o no tenía un elevado concepto del talento matemático de sus adversarios.

En lenguaje matemático

En términos modernos, una descripción de este método que nos dejaría más tranquilos sería una terna de algoritmos descritos como sigue:

KeyGen(n) = k ∈ Zn

Enc(k, m) = m + k mod n

Dec(k, c) = c – k mod n

El parámetro de seguridad, n, fijaría el tamaño del alfabeto utilizado en la comunicación y la seguridad del método dependería esencialmente del diseño del algoritmo KeyGen. Si para un n fijado (por ejemplo, n = 26) la salida de KeyGen fuese siempre el mismo número (otra vez, por no llevar la contraria al César, el 3), estaríamos de nuevo con una construcción determinista. Yéndonos al extremo contrario, forzaríamos que cualquier valor entre 0 y 25 tuviese la misma probabilidad de resultar como salida de KeyGen. Esta es, evidentemente, la mejor estrategia para ganar seguridad en un diseño de este tipo5.

Demos a la construcción recién descrita una vuelta más, concretamente, cifrando cada letra con un método como el anterior, pero con clave distinta. Esta evolución del cifrado de César se conoce con el nombre de cifrado de Vigenère, más conocido como el código indescifrable (le chiffre indéchiffrable, en francés).

En lenguaje matemático

Veamos cómo funciona. Para cifrar mensajes de longitud t, esta sería la descripción de los algoritmos involucrados:

KeyGen(n, t) = k = (k1, …, kt) con ki ∈ Zn para i = 1, …, t

Enc(k, m) = c

siendo m = (m1, …, mt) y c = (c1, …, ct)

donde para i = 1, …, t

ci = mi + ki mod n

Dec(k, c) = m,

donde para i = 1, …, t,

mi = ci – ki mod n

Este método, del que se tiene constancia desde el siglo XVI, heredó la debilidad del método usado por Julio César. De nuevo, el algoritmo KeyGen utilizado era esencialmente determinista, pues la clave quedaba fijada a través de una tabla que, además, en muchos casos, se resumía utilizando una palabra clave corta. La tabla 3 ejemplifica este método, donde las claves asociadas k = (k1,…, kt) van de 0 a 25 en la primera columna de la izquierda. La tabla 4 representa la misma clave, pero sin codificación numérica6.

Tabla 3

Tabla Vigenère numérica

Tabla 4

Tabla Vigenère alfabética

Ejemplo 1

Así, para cifrar la palabra “FÁCIL”, si utilizáramos la secuencia de clave (0, 1, 2, 3, 4), tendríamos como resultado el texto cifrado “FBELP”. Si queremos que la secuencia de clave no sea siempre de la forma (0, 1, …, t), podemos usar una palabra clave que señale qué filas de la tabla Vigenère se usarán para cada letra. Por ejemplo, si usamos la palabra clave “MISTERIO”, estamos señalando a las filas 12, 8, 18, 19, 4, 17, 8 y 14. Así, por ejemplo, para cifrar la palabra “ALMA” haremos:

m = (A, L, M, A), k = (12, 8, 18, 19) y así, el texto

cifrado c = (c1, …, ct) se construirá con la fórmula

ci = mi + ki mod 26

de donde obtenemos, codificando numéricamente el texto claro m como (0, 11, 12, 0):

• c1 = 0 + 12 mod 26 = 12, y en letras c1 = M

• c2 = 11+ 8 mod 26 = 19, y en letras c2 = T

• c3 = 12 + 18 mod 26 = 4, y en letras c3 = E

• c4 = 0 + 19 mod 26 = 19, y en letras c4 = T

Así, el resultado del cifrado es la palabra “MTET”. En este caso, el texto que ciframos tenía menor longitud que la palabra clave. Si la longitud del texto claro es mayor que la palabra clave, habitualmente se repite la palabra clave el número de veces necesario (es decir, después de la O de “MISTERIO”, empezamos de nuevo por la M).

Regreso al futuro

Ahora que conocemos dos ejemplos de cifrado simétrico históricos, avancemos unos siglos. ¿Qué aspecto tienen los esquemas actuales? En realidad, su estructura formal sigue encajando en la definición que hemos dado como una terna de algoritmos. Existen, sin embargo, enormes diferencias, que tienen mucho que ver con los avances en computación del siglo XX y con el (apasionante) desarrollo del criptoanálisis durante la Segunda Guerra Mundial.

Una de las piezas esenciales de muchos de los esquemas de cifrado simétrico moderno son las llamadas redes de Feistel. Horst Feistel fue un criptógrafo de IBM que pasó a la historia como diseñador de uno de los métodos de cifrado más utilizados mundialmente, el cifrado DES7. No nos detendremos en las entrañas de este diseño, sino en su esqueleto básico, que es el armazón que sustenta otros muchos esquemas (vivos y muertos), como Lucifer, Gost, Simon o Camellia.

Una red de Feistel sirve para cifrar bloques de texto claro, es decir, cadenas de bits de un cierto tamaño t, transformándolas en bloques de texto cifrado del mismo tamaño. Su principal ventaja es la llamada reversibilidad: las operaciones de cifrado y descifrado siguen exactamente la misma estructura, realizan las mismas operaciones, pero involucrando la clave en “orden inverso”.

En lenguaje matemático

Veamos una descripción formal (aunque simplificada) del proceso: tenemos como antes el texto claro, la clave y el texto cifrado dividido en bloques. Vamos a ver cómo se opera en un solo bloque de texto claro M, que va a ser una cadena de r bits (con r par). Tenemos también una clave K fragmentada en n claves parciales (K1, …, Kn), cada una de r/2 bits y, además, una misteriosa función f que servirá para “mezclar” trozos de M con claves parciales. Podemos considerar que tanto n como r forman el parámetro de seguridad, y la clave K = (K1, …, Kn) es el resultado de ejecutar el algoritmo KeyGen.

En lo que sigue, denotaremos por ⨁ la suma de cadenas binarias en base dos, es decir, atendiendo a las reglas

1 ⨁ 1 = 0, 0 ⨁ 0 = 0, 1 ⨁ 0 = 1, 0 ⨁ 1 = 1

Vamos a cifrar el texto M con la clave K; es decir, veamos cómo se construye la salida del algoritmo Enc si la entrada es el par (K, M):

Primero, se divide M en dos mitades (cada una de r/2 bits), denotadas L0 y R0 (parte izquierda y parte derecha).

Después, para i = 1 hasta n se define:

Li := Ri-1

Ri := Li-1 ⨁ f(Ri-1, Ki )

Por último, se construye la salida:

C := ( Ln, Rn )

Lo mejor es que, independientemente de cómo se defina f, el algoritmo de descifrado hace esencialmente lo mismo que Enc, pero ordenando las claves al revés, es decir, Dec(K, C):

Divide C en dos mitades (cada una de r/2 bits), denotadas Ln y Rn (parte izquierda y parte derecha).

Después, define para i = n hasta 1 (con paso decreciente) los valores:

Ri-1 := Li

Li-1 := Ri ⨁ f(Li, Ki )

Proporciona la salida: M = ( L0, R0 )

Cada paso (designado con la letra i en la instrucción “para” anterior) en el cifrado de una red de Feistel suele llamarse ronda, y por eso la función f (que en muchos diseños no es la misma para todas las rondas) suele llamarse función de ronda. La seguridad de los cifrados basados en redes de Feistel depende, en gran medida, de la estructura de la función de ronda subyacente.

¿Es mi esquema seguro?

Ahora que sabemos un poco sobre esquemas de cifrado simétrico, es momento de pasar a una pregunta importante: ¿cómo se evalúa su seguridad? Si puedo elegir, ¿qué sistema utilizo para enviar mis mensajes? Para responder a esta pregunta, lo primero es que pensemos detenidamente en la razón por la que utilizamos un esquema de cifrado. Sara, en el colegio, lo tenía muy claro: para que nadie más que yo (la legítima receptora de sus envíos) pudiera leer el contenido de los mensajes. Ni siquiera nuestro estupendo profesor de cuarto, don Primitivo, que, desde luego, sabía muchas más matemáticas que nosotras. Pero ¿es aceptable que alguien que intercepte el mensaje pueda obtener alguna información sobre su contenido, aunque sea pequeña? Y ¿podemos suponer que el presunto espía no conoce qué método concreto estamos utilizando para cifrar? Sin dar una respuesta precisa a estas preguntas, nuestro análisis de seguridad será incompleto (y, en muchas ocasiones, peligroso). Volveremos sobre estas preguntas y sus posibles respuestas en numerosas ocasiones.

Ejemplo 2

Pero retrocedamos de nuevo a los tiempos de Julio César. Pensemos cuál sería nuestra estrategia, como adversarios, si interceptamos un texto cifrado con este método cuya clave desconocemos (pues Julio César, en algún momento, ha abandonado su querido 3). Este es nuestro texto cifrado objetivo:

LS WLYYV KL ZHU YVXBL UV APLUL YHIV WVYXBL YHTVU YVKYPNBLG ZL SV OH JVYAHKV

Si sabemos que el texto claro está en castellano, podemos intentar averiguar la clave analizando la frecuencia de aparición de las distintas letras en el texto. En castellano, las letras más frecuentes son la e y la a. En este texto, las letras que más se repiten son la L y la V (ambas aparecen 9 veces). Si asumimos que la L cifra la E, la clave utilizada sería K = 7, y en caso de pensar que es la V quien cifra la E, deduciríamos que K vale 17. Al probar con las dos claves, inmediatamente vemos que K = 17 da un texto inteligible, mientras que con K = 7 obtenemos la frase (obviando los acentos):

EL PERRO DE SAN ROQUE NO TIENE RABO PORQUE RAMÓN RODRÍGUEZ SE LO HA CORTADO

Ahora bien, ¿por qué es tan efectivo este sencillo análisis de frecuencias? ¿Ocurriría lo mismo con el cifrado de Vigenère? Evidentemente, el éxito de nuestro método radica en el determinismo del cifrado de César: el cifrado de una letra siempre da como resultado la misma. Vigenère no tiene esta debilidad, pero, desde luego, va a distar mucho de ser un cifrado indescifrable8; por ejemplo, un análisis de frecuencias puede ayudarnos a detectar la longitud de la palabra clave con la que se ha cifrado el texto. Conocido esto, solo tenemos que separar los caracteres cifrados con cada fila de la tabla 4 para luego averiguar, como hicimos en el texto anterior, con qué desplazamiento concreto se corresponde cada una.

Así, el análisis de frecuencias parece una herramienta poderosa; pero solo lo es contra los esquemas clásicos con cierto grado de determinismo. Un cifrado construido con una red de Feistel robusta es mucho más difícil de romper, aunque, por supuesto, todo depende de la frecuencia con la que “refresquemos” las claves criptográficas. Pensemos cuál sería el escenario ideal, por ejemplo, en el cifrado Vigenère. La respuesta es sencilla: lo ideal es no reutilizar ninguna clave y, por tanto, cifrar cada letra con una fila distinta de la tabla. Esto solo es posible si nuestros mensajes son, a lo sumo, del mismo tamaño (t) que la clave asociada.

Hemos descubierto uno de los principios que subyacen a la seguridad: reutilizar lo menos posible cada clave secreta, que además se elige uniformemente al azar9.

El llamado cifrado Vernam o one-time pad es el primer esquema de cifrado simétrico para el que existe una demostración formal de seguridad. Se basa justamente en utilizar claves de un solo uso del mismo tamaño del texto que se va a cifrar. Las construcciones actuales basadas en redes de Feistel intentan, en cierto sentido, emular la utilización de claves de un solo uso. Otro recurso para esquivar el poderoso análisis de frecuencias es utilizar una codificación de mensajes cuyos patrones no sean tan transparentes como el alfabeto latino en castellano. A lo largo de la historia, se han utilizado lenguas muertas o muy poco conocidas para codificar mensajes que luego se cifrarían. Por ejemplo, el idioma navajo fue utilizado por los americanos durante la Segunda Guerra Mundial (como puede verse en la película Windtalkers, dirigida por John Woo). En cierto sentido, confiar en que este tipo de estrategia robustezca una construcción criptográfica va contra el principio de Kerckhoffs.

Pero ¿acaso no hay alguna forma mejor de esquivar el fastidioso análisis de frecuencias? ¿Podríamos de alguna manera refrescar continuamente las claves sin tener que tatuarlas en el cuero cabelludo de cientos de soldados etruscos u obligar a valientes agentes de inteligencia a cruzar la Alsacia en tren noche tras noche? La respuesta, que supuso el fin de muchos quebraderos de cabeza para esforzados criptógrafos (y el comienzo de otros muchos), aguarda en el próximo capítulo.

Capítulo 2

Criptografía asimétrica.

Alice y Bob tienen que hablar

Volvamos a nuestra casilla de salida, en la que Alice quiere enviar un mensaje a Bob a través de un canal de comunicación inseguro. Vamos ahora a ponérselo un poco más difícil: supongamos que no es posible realizar un intercambio previo de información que les permita acordar una clave secreta. Seguimos, sin embargo, empeñados en proteger su comunicación. ¿Es esto posible? En la segunda mitad del siglo XX, dos (atípicos) equipos científicos dieron la misma respuesta a esta pregunta creando la llamada criptografía asimétrica.

El nacimiento de la criptografía de clave pública

Whitfield Diffie y Martin Hellman publicaron en 1976 el artículo “New Directions in Cryptography” (‘Nuevas direcciones en criptografía’), en el que por primera vez se desarrolla formalmente la idea de comunicación segura sin secretos compartidos a priori10. Un año atrás, Malcolm Williamson, matemático del servicio secreto británico, conocido por las siglas GCHQ (Great Britain’s Government Communications Headquarters) había llegado exactamente a la misma idea, intentando refutar el primer diseño de cifrado de clave pública propuesto en 1973 por Clifford Cocks, también del GCHQ. Ambos trabajaban sobre las ideas de James Ellis, cuyos primeros resultados al respecto ya circulaban por los pasillos de la inteligencia británica desde finales de los sesenta. Veamos un sencillo símil, con cofres, cerraduras y llaves, de la idea fundamental que rondaba la cabeza de todos ellos.

Ahí tenemos a Alice, que no ha podido encontrarse en persona con Bob, y tiene un precioso objeto que querría enviarle por correo ordinario. Evidentemente, el servicio de correos es susceptible de ser interceptado. Supondremos que, en todo caso, solo existen adversarios curiosos pero cautos, que quieren ver el objeto sin que se note su intromisión. Tanto Alice como Bob disponen de un cofre que puede cerrarse con un candado de cuya llave disponen, pero ambos candados son diferentes y ninguno tiene la llave del otro. ¿Qué pueden hacer? Sencillamente, plantearse el envío en varias etapas, de la siguiente forma:

Alice mete el objeto en su cofre, le pone su candado, lo cierra y lo envía por correo a Bob.

Bob, que no puede quitar el candado de Alice (pues no dispone de la llave), añade su candado al cofre, cerrándolo así doblemente y se lo envía a Alice por correo.

Alice abre su candado y envía de nuevo a Bob el cofre por correo, ahora solo cerrado con el candado que este había puesto.

Bob, por fin, quita su candado del cofre y recupera el objeto enviado por Alice.

Esta simple idea puso de manifiesto que era posible eliminar el acuerdo previo de una clave secreta y diseñar un tipo distinto de criptografía. Esta reflejaría la asimetría de los papeles que desempeñan a veces las personas involucradas en la tarea criptográfica; el que escribe frente al que quiere ser el único capaz de leer, el que genera una firma digital que presume infalsificable frente al que ha de verificarla, etc. Buscar cofres, llaves y candados en el inmenso arsenal de las matemáticas era el siguiente y apasionante paso.

El esquema de Diffie-Hellman

Dentro de las muchas ideas esbozadas en el artículo original de Diffie y Hellman, se encuentra un diseño para un protocolo de intercambio de clave entre dos usuarios. El objetivo de este esquema criptográfico es permitir a Alice y Bob acordar una clave secreta, un valor de alta entropía, comunicándose a través de un canal vulnerable. Hecho el intercambio, ambos podrían utilizar ese valor como clave secreta para comunicarse usando un esquema de cifrado simétrico. Uno de los puntos más brillantes de este diseño es el hecho de que el secreto acordado es un valor que Alice y Bob construyen cooperativamente, de modo que ninguno de los dos tiene más influencia del otro sobre la clave que finalmente utilizarán en la comunicación11.

Tenemos que introducir algunos conceptos elementales de teoría de grupos antes de continuar. Un grupo es una estructura algebraica definida a través de un conjunto (una colección de elementos), que llamaremos G, en el que existe una operación que cumple tres propiedades: asociativa, existencia de elemento neutro y existencia de inversos. Por ejemplo, los números enteros con la operación suma son un grupo; se cumple la propiedad conmutativa (el orden de los sumandos no altera el resultado), la asociativa (no es necesario, cuando hacemos sumas de varios sumandos, hacer los cálculos en un orden prefijado) y la existencia del elemento neutro (el 0, que sumado a cualquier otro número lo deja igual). También forman un grupo los posibles restos módulo m (con m un número natural) con respecto a la operación suma módulo m que presentamos en el capítulo anterior. Más aún, si m es un número primo12, eliminando un cero del conjunto anterior tenemos también un grupo con respecto a la multiplicación (también mod m).

Veamos, por ejemplo, cómo se opera en el grupo Z5. Si hablamos de la operación suma, el conjunto subyacente son los números {0, 1, 2, 3, 4}. Escribiendo estos números en la primera fila y columna de una tabla podemos representar la operación de modo que la casilla en la que se cortan la fila que empieza por i y la columna que empieza por j sea el resultado de hacer i + j mod 5.

De manera similar, representamos la operación producto, ahora tomando los elementos {1, 2, 3, 4}, puesto que el 0 no tiene inverso con respecto a la multiplicación.

Decimos, además, que un grupo G es cíclico si existe un elemento especial g ∈ G de modo que es posible construir todo el grupo operando g consigo mismo. Por ejemplo, el grupo de los números naturales con la suma es cíclico y el elemento generador sería el 1, ya que cualquier número natural puede escribirse como una suma de unos (2 = 1 + 1, 3 = 1 +1 + 1…).

Así, si G está generado por g y tiene n elementos, solemos escribir

G = (g) = {g0 = 1, g, g2, …., gn-1}

donde 1 es el neutro multiplicativo del grupo (es decir, al elemento que al ser multiplicado por cualquier otro del grupo lo deja como estaba).

En ese caso, si tomamos cualquier elemento h del grupo, existe un exponente x de modo que h = gx. Solemos referirnos a g como generador del grupo. Por ejemplo, para todo primo p es fácil ver que Zp* (la estrella indica que eliminamos el cero del conjunto), con el producto módulo p, es un grupo cíclico que puede generarse a partir de cualquiera de sus elementos.

Ahora bien, dados el elemento h y el generador g, ¿es fácil calcular el exponente x? Resulta que algunas veces, sí, y otras, no tanto. Diffie y Hellman encontraron su martillo en la dificultad de obtener estos exponentes. Un martillo que sigue, a día de hoy, remachando infinidad de clavos.

Ejemplo 1

Consideramos el grupo Z37* con la operación multiplicación. El número 12 es un generador del mismo, luego tiene que existir un exponente y de modo que 12y = 16 mod 37. Vamos a buscarlo calculando potencias sucesivas:

122 = 144, luego, al reducir módulo 37 (es decir, dividir entre 37 y quedarnos el resto, tenemos 122 = 24 mod 37.

Ahora, 123 = 12 · 122 = 12 · 144 = 12 · 24 = 15 mod 37. En la operación anterior, como “vivimos” módulo 37, hemos sustituido el 144 por su resto al dividirse por 37, es decir, por 24. De manera similar, podemos calcular

124 = 122 · 122 = 24 · 24 = 16 mod 37, luego el exponente buscado, nuestro ansiado valor y, es igual a 16.

Consideremos ahora la estructura aditiva del grupo, y resolvamos el mismo problema, es decir, buscamos y tal que 12 operado consigo mismo y veces nos dé 16. En otras palabras, hemos de resolver la ecuación y · 12 = 16 mod 37. Si caemos en la cuenta de que 12 · 3 = 36, y 36 = -1 mod 37, podemos multiplicar toda la ecuación anterior por 3 y la transformamos en otra equivalente pero más simple: (-1) y = 3 · 16 = 48 = 11 mod 37, luego y = -11 = 26 mod 37. Aunque con números tan pequeños quizá no es fácil apreciar la diferencia, lo cierto es que este segundo problema es mucho más sencillo que el que teníamos cuando el escurridizo valor y se escondía como un exponente.

En lenguaje matemático

Vamos ahora describir la versión más básica del protocolo de Diffie-Hellman. Supongamos que el grupo cíclico multiplicativo G es público, así como su tamaño (llamado orden), que es un número primo p, y un generador g. Alice y Bob dan los siguientes pasos:

Alice elige un exponente secreto a entre todos los posibles {0, …, p-1}, construye el elemento ga y se lo envía a Bob.

Bob elige b entre todos los posibles exponentes {0, …, p-1}, construye el elemento gb y se lo envía a Alice.

Tanto Alice como Bob pueden calcular el elemento

K = gab = gba = (ga)b = (gb)a

y extraer de él una clave común de alta entropía13.

Ejemplo 2

Veamos un ejemplo con números. Supongamos que trabajamos en Z37* y que el generador público es g = 12. Una posible ejecución del protocolo sería como sigue:

1. Alice elige como exponente el 9, calcula 129 mod 37 = 34 y se lo envía a Bob.

2. Bob elige como exponente el 5, calcula 125 mod 37 = 17 y lo envía a Alice.

3. Tanto Alice como Bob pueden calcular el elemento

K = 20 = 1245 = (125)9 = (129)5

y extraer de él una clave común de alta entropía.

Por supuesto, aunque los cálculos módulo 37 puedan parecerte tediosos a mano, son insignificantes para un ordenador. Para que despejar los exponentes secretos de Alice y Bob sea un problema computacionalmente difícil, el módulo utilizado ha de ser un primo mucho mayor que 37, en torno a 2160.

Aunque los argumentos matemáticos expuestos sean convincentes, el protocolo anterior es completamente inseguro si los adversarios potenciales son activos, es decir, si pueden inyectar mensajes en el canal. Un adversario de este tipo (llamémoslo Nacho) puede montar un ataque de los llamados de hombre en el medio. Estos ataques, conocidos como MIM (por las siglas de su denominación en inglés: man in the middle), se efectúan suplantando ante cada participante a su interlocutor legítimo. Es decir, Nacho se mete “entre” Alice y Bob, se queda con sus mensajes ga y gb (que nunca llegan a su destinatario original) y les envía a ambos el elemento gc, donde c es un exponente de su elección. Así, Nacho compartirá con Alice la clave gac y con Bob la clave gbc, mientras que Alice y Bob no tienen ninguna clave en común (y, lo que es peor, ¡creen tenerla!). Por supuesto, existen medidas para dejar a Nacho fuera de combate autenticando el canal a través de otras herramientas criptográficas; ¡podemos respirar tranquilos! (por unas páginas…)

Cifrando con mochilas

Ya hemos visto cómo es posible intercambiar una clave simétrica sin el engorroso acuerdo previo entre usuarios que suponía la criptografía clásica. Ahora, claro, podríamos usar cifrado simétrico para blindar nuestra comunicación, pero ¿existe otra manera? La respuesta es afirmativa; podemos diseñar directamente métodos que sirvan para cifrar sin necesidad de intercambiar una clave previamente.

Veamos una de las primeras propuestas que se hicieron a este respecto: el criptosistema de Merkle-Hellman. Es simple, elegante y está basado en un bonito problema combinatorio. Por desgracia, es además completamente inseguro.

En lenguaje matemático

Recuperemos la nomenclatura del capítulo anterior y describamos el esquema como una terna de algoritmos (KeyGen, Enc, Dec). Nuestro objetivo es cifrar mensajes que, para simplificar, son siempre cadenas de n bits.

El algoritmo KeyGen recibe como entrada el parámetro n y selecciona una secuencia supercreciente de n números enteros, que llamaremos X. Esto quiere decir que X es una ristra de números (x1, …, xn), con cada xi estrictamente mayor que la suma de los números anteriores de la secuencia, esto es:

xi > x1 + … + xi-1.

Nos sirve, por ejemplo, la secuencia (2, 37, 95, 150).

Además, KeyGen selecciona dos números enteros q y r que cumplan dos condiciones:

q > x1 + … + xn.

q y r son primos entre sí, es decir, su máximo común divisor es el 1.

Para nuestra secuencia (2, 37, 95, 150), podemos tomar q = 285 y r = 7.

Por último, se construye la secuencia Y = (y1, …, yn), donde cada número se calcula con la fórmula

yi = r xi mod q

KeyGen, como todos los cifrados de clave pública, no devuelve una única clave, sino una pareja de claves: la clave pública (en este caso, Y) y la clave secreta (X, q, r).

El algoritmo de cifrado, Enc, recibe ahora un texto claro de n-bits, m = (m1, …, mn) y la clave pública Y como entrada. Supongamos que el texto es m = (1, 0, 1, 0).

Enc construye el cifrado c sumando los elementos de la secuencia pública Y que indican los bits del mensaje, es decir:

c = m1 y1 + … + mn yn.

En nuestro ejemplo, tenemos que c = 14 + 95 = 109.

La salida de Enc(Y, m) es dicho valor c.

El algoritmo de descifrado Dec necesita la clave secreta como parte de su entrada. Así, con entrada (X, q, r, c), realiza las siguientes operaciones:

Calcula s, el inverso de r módulo q. Como q y r no tienen divisores comunes (salvo el uno), existe un número s tal que rs = 1 mod q. Además, s es fácil de calcular por medio de un algoritmo conocido como el algoritmo extendido de Euclides.

En nuestro ejemplo, el inverso de 7 módulo 285 es 163, pues 163 · 7 - 1 es múltiplo de 285.

Calcula c’ = cs mod q, que es una suma de los elementos de la secuencia secreta X, guiada por los bits del mensaje, es decir:

c’ = m1 x1 + … + mn xn.

Recupera los bits de m a partir de c’.

Para nuestro ejemplo, c’ = 109 · 163 = 17.763 = 97 mod 285 que se escribe como 1 · 2 + 0 · 37 + 1 · 95 + 0 · 150, obteniéndose así el texto cifrado inicialmente, m = (1, 0, 1, 0).

Inicialmente, se pensó que este esquema podría ser seguro porque resolver el llamado problema de la mochila, que consiste en decidir qué números de una cierta secuencia hay que sumar para obtener un valor prefijado, es fácil si la secuencia es supercreciente y difícil para una secuencia arbitraria. Si se dispone de la clave secreta, recuperar m a partir de c es resolver este problema para la secuencia X y el valor c’, mientras que sin ella tenemos que calcular m a partir de la secuencia Y y el valor c.

Fíjate en que los receptores legítimos de un mensaje pueden, a través de la clave secreta, esquivar la dificultad del problema general de la mochila. Para descifrar, si se tiene la clave secreta, es suficiente resolver una versión simplificada del mismo. Este sencillo mecanismo es el quid de toda construcción de clave pública; el adversario se enfrenta a un problema matemático difícil, que, mágicamente, con la intervención de la clave secreta, puede transformarse en un problema fácilmente resoluble.

Por otro lado, la criptografía de clave pública se llama también asimétrica porque precisamente se desarrolla trasladando a las matemáticas la asimetría que existe entre las tareas que ejecutan distintos usuarios. En el caso del cifrado, Bob quiere recibir mensajes de todo el mundo; esta tarea ha de ser sencilla matemáticamente y, por eso, le interesa que la clave necesaria para cifrar sea pública. Sin embargo, Bob quiere limitar el acceso a los mensajes que se envían, por lo que se guarda la clave secreta en exclusiva para ser el único capaz de descifrar. Sin ella, el problema matemático que hay que resolver para descifrar resulta inabordable.

Firmas y compromisos

Hemos esbozado la naturaleza asimétrica de las tareas criptográficas y cómo puede implementarse esta asimetría a través de las matemáticas. Ahora se abre un mundo de posibilidades excitantes más allá del cifrado. Los esquemas de firma digital son una de las primeras herramientas que encajan en este puzle mental14. Está claro que, cuando firmamos un documento, lo ideal es que todo el mundo pueda verificar la validez de esta firma. Sin embargo, no queremos dar a nadie la capacidad de firmar en nuestro nombre. Así, en un esquema de firma digital, la clave pública sirve para verificar las firmas, mientras que la clave secreta sirve para firmar.

Algo similar ocurre con los llamados esquemas de compromiso. Estas construcciones (quizá poco conocidas, pero muy utilizadas) sirven para neutralizar la asincronía que es tantas veces inherente a la comunicación digital. En otras palabras, neutralizan la ventaja que podría tener algún usuario en un determinado proceso en el que el orden en el que se envían o reciben los mensajes no pueda controlarse. Pensemos en una institución que saca a concurso una cierta obra pública; por ejemplo, un Ayuntamiento que plantea construir un puente sobre el río que cruza la ciudad. Distintas empresas preparan sus propuestas siguiendo el pliego de condiciones publicado, y las envían antes de la fecha límite al Ayuntamiento. Este envío puede hacerse por e-mail o subiendo un archivo a un cierto repositorio digital. Evidentemente, si algún funcionario malicioso15 quiere favorecer a una empresa concreta, le pasará información acerca de las propuestas de las demás para que elabore su propia propuesta con ventaja. ¿Cómo evitar esto? Una solución podría ser que las propuestas no se hagan llegar al Ayuntamiento en claro, sino cifradas con algún método (simétrico o asimétrico). Pasada la fecha límite, cada empresa publicaría la clave necesaria para descifrar su propuesta. Pero ¿seguro que esto es suficiente? La respuesta es que no. Cifrar las propuestas, efectivamente, dejaría al funcionario indiscreto con pocas opciones de ganarse un sobresueldo. Por otro lado, nada en la definición de un esquema de cifrado evita que el mismo texto cifrado c pueda, a partir de dos claves distintas, descifrarse y dar lugar a dos textos claros distintos. Así, la empresa Chanchullos, S. L. podría construir un cifrado c del precio final de su propuesta, que con una cierta clave k1 se descifrase a “500.000 €” y con una clave k2 a “1.000.000 €”. En función de los precios que se fuesen revelando de las propuestas de la competencia, Chanchullos, S. L. podría elegir cuál de las dos claves, k1 o k2, le enviará al Ayuntamiento en la segunda fase del proceso.

Los esquemas de compromiso son herramientas criptográficas que permiten construir un valor c asociado a un mensaje m con las dos propiedades que se requieren en el ejemplo anterior:

Ocultación (hiding): a la vista del valor c, no es posible obtener información sobre m.

Vínculación (binding): dado el valor c, existe una clave k que permite vincular c con m y no es posible encontrar una clave que vincule c con otro mensaje.

Solo son un ejemplo entre tantos posibles de herramientas criptográficas poco conocidas que muchos utilizamos, sin saberlo, a diario.

Esquemas provablemente seguros. Cifrado RSA

Tan solo hemos mirado por la cerradura de la emocionante mansión de la criptografía asimétrica, y ya vemos claro que evaluar la seguridad no es una tarea sencilla. César vivía feliz en la ignorancia, pensando que cifrar era seguro si la clave era imprescindible para recuperar el mensaje en claro enviado. Nosotros ahora nos preguntamos, ¿cuánto es posible saber sobre dicho mensaje sin la clave? ¿Qué capacidad de cómputo he de suponerle a mi adversario? Más aún: incluso aunque no obtenga información sobre el mensaje que he enviado, ¿puede hacer otras cosas en las que no he pensado? Imaginad, por ejemplo, un empleador que envía al banco cada mes el importe de la nómina que paga a un cierto empleado X. Evidentemente, si esa cantidad está cifrada, el sueldo sx del empleado se mantiene en secreto. Sin embargo, no podemos olvidar que el propio señor X es un adversario potencial al que, claro está, no le interesa averiguar cuánto gana (pues ya lo sabrá al cobrar). Por otro lado, sin duda, puede apetecerle transformar el cifrado que está en el canal en otro cifrado válido que se corresponda con, digamos, 100 veces la cantidad sx. Nuestro nivel de paranoia se dispara, más aún si pensamos en herramientas más complejas que el cifrado entre dos usuarios.

La teoría de seguridad demostrable16 aborda el ingente reto de proporcionar definiciones formales para las distintas nociones de seguridad deseables para un esquema criptográfico. Dichas definiciones permiten luego elaborar demostraciones matemáticas de seguridad. Estas especifican qué cosas podrá (o no) hacer un adversario, en función del tamaño del parámetro de seguridad seleccionado para la generación de claves. Aunque es un área de trabajo fascinante con incuestionables implicaciones en la práctica, muchos desarrollos de herramientas pasan por alto sus preceptos. Esto tiene consecuencias: a veces evidentes y otras apenas perceptibles, pero casi siempre peligrosas.

Vamos a hablar un poco de seguridad demostrable a través de un esquema de cifrado muy conocido: el RSA. El cifrado RSA debe su nombre a Ronald Rivest, Adi Shamir y Leonard Adleman. Estos publicaron en 1977 un diseño para cifrar que, de nuevo, tenía mucho en común con otro trabajo (fechado en 1973) realizado por un investigador del GCHQ, Clifford Cocks. Rivest, Shamir y Adleman recibieron en 2002 el Premio Turing por este diseño, que es el máximo galardón otorgado en ciencias de la computación (Cocks hubo de conformarse con la gloria tardía tras la desclasificación de su diseño en 1997).

En lenguaje matemático

Veamos una descripción superficial del RSA:

El algoritmo generador de claves, KeyGen, recibe un parámetro n de entrada. Calcula dos números primos, p y q, cuya expresión en binario tiene n bits, y su producto, N. Obtiene además un número entero e que no tiene divisores en común con el número (p-1)(q-1).

Después, KeyGen genera un valor d tal que de-1 es múltiplo de (p-1)(q-1); es decir, d es inverso de e módulo (p-1)(q-1).

La clave pública es el par (N, e), siendo d la clave secreta,

KeyGen(n) = (N, e, d)

Para cifrar un mensaje m (que suponemos es un entero entre 0 y N-1), Enc calcula la potencia me mod N, es decir:

Enc(N, e, m) = c = me mod N

Para descifrar, se “elimina” el exponente e elevando el cifrado a la clave secreta d, pues puede comprobarse la igualdad17:

Dec(d, c) = cd = med = m mod N

Es conocido que la seguridad del RSA se basa en el problema de factorización de enteros. Pero ¿qué quiere decir esto? Desafortunadamente, mucho menos de lo que el subconsciente colectivo parece haber asimilado. Es relativamente fácil demostrar que todo aquel que conozca los primos p y q puede calcular el inverso modular d y, por tanto, romper el RSA. Además, para una generación de claves razonable, existen algoritmos que a partir de los valores (N, d, e) calculan los primos p y q (pero, insistimos, no en todos los casos). Así, podemos decir que calcular claves secretas RSA a partir de la información pública es más o menos tan difícil como factorizar N.

Pero ¿acaso un adversario no puede hacer mucho daño sin necesidad de calcular d? Para empezar, como buenos criptoanalistas, subrayemos que el RSA de libro de texto tiene un alto grado de determinismo. En efecto, con la misma clave pública, un mensaje m origina siempre el mismo cifrado. Esto no nos deja muy tranquilos; sin conocer cómo funciona KeyGen exactamente no podemos saber cuánta variabilidad hay en las claves utilizadas.

Más aún, si recordamos el ejemplo anterior de “manipulación de nóminas”, es sencillo ver que este esquema tiene un problema de maleabilidad. Efectivamente, dados dos cifrados c1 y c2, su producto es un cifrado válido para el producto de los mensajes claros que esconden. En este punto, en el que estamos al borde del desánimo absoluto, es importante resaltar dos cuestiones. La primera es que el esquema que hemos descrito es el llamado RSA “de libro de texto”18, y no la versión del RSA utilizada e implementada por doquier, conocida como RSA-OAEP19. La segunda es que si aceptamos que factorizar es difícil, hay una noción de seguridad que sí cumple el esquema original de Rivest y compañía. Puede demostrarse que un adversario pasivo (que solo mira el canal), cuyo único objetivo es recuperar el texto claro completo, no tendrá éxito. Por supuesto, si aceptamos que resolver el problema de factorización subyacente no es posible.

La seguridad demostrable no es un área fácil. Conjuga el formalismo matemático con la modelización rigurosa del posible comportamiento de un adversario. Los criptógrafos cuentan, sin embargo, con un sustrato sólido para apoyarse: la llamada teoría de complejidad, a caballo entre las matemáticas y la informática. En el próximo capítulo tendremos oportunidad de verla en acción.

Capítulo 3

Sistemas de prueba. Solo sé que

no he aprendido nada

Reflexionemos sobre un hecho extraordinario: las matemáticas proporcionan demostraciones verificables sin necesidad de interacción con el autor. Es decir, una vez un científico encuentra la solución a un problema y la describe en lenguaje formal, bastará con leer su argumentación para verificar que su razonamiento es correcto. No puede ser de otra manera, pensaréis algunos (incluso aunque en muchos casos os hubiese gustado coger a Hilbert por las solapas e interrogarle con respecto a algún paso en sus deducciones). En matemáticas, se determina si un hilo de razonamiento es o no una demostración partiendo de una serie de axiomas (¡inamovibles!) sobre los que actúan unas reglas de deducción establecidas. Faltaría más.

Ahora, una sorpresa: este esqueleto lógico admite revisiones. La teoría de complejidad moderna permite otro tipo de validaciones o sistemas de prueba, en los que la computación desempeña un papel fundamental y que, además, ¡pueden ser interactivos! Esto nos viene fenomenal: en criptografía es con frecuencia necesario establecer la validez de una afirmación usando no solo principios estáticos, sino también procesos dinámicos y participativos. Además, a menudo, hemos de permitir que dicha validación admita cierta probabilidad de error. En este capítulo hablaremos de estos procesos de verificación, llamados sistemas de prueba probabilísticos. Estos no son únicamente formalismos teóricos, sino que son esquemas criptográficos de pleno derecho.

Sistemas de prueba probabilísticos

Alice, Bob y Nacho descansan en este capítulo. En el escenario tenemos ahora a dos usuarios, Pedro y Vera, que realizan juntos una tarea bien descrita. Lamentablemente, Vera no se fía de Pedro, y piensa que no va a realizar su parte correctamente. Pedro además es todopoderoso en un sentido computacional: factoriza enteros de cinco mil bits en un segundo, almacena exabytes20 de información sin problemas… Vamos, un portento de chico.

Centremos nuestra atención en un problema concreto: tenemos un conjunto S público y para Vera es difícil determinar si un elemento x dado está o no en S. Por ejemplo, S podría ser el conjunto de números primos y Pedro quiere demostrar a Vera que el 20.507 forma parte del mismo. Y, a Vera, que apenas sabe dividir, no es fácil convencerla. Una opción es que Pedro le pida a Vera que le pase varios “candidatos” a divisores de 20.507. Él hará la división en un encerado para que Vera vea que el resto no da cero para ningún candidato de su elección y tal vez, tras unas cuantas pruebas, Vera acepte que 20.507 es primo. De esta manera se concluiría la demostración interactiva.

Volvamos a nuestra descripción general, donde S es cualquier conjunto, y formalicemos la idea de demostración interactiva que acabamos de plantear.

Un sistema de prueba interactivo (IPS, acrónimo del término en inglés, interactive proof system) se define como un proceso que involucra a dos actores V y P (nuestros Vera y Pedro) que interactúan. Al finalizar, V declarará su conformidad (aceptará) o no con el resultado de la interacción.

Informalmente, un IPS ha de cumplir las siguientes condiciones:

V, el verificador, solo puede ejecutar estrategias acotadas (es decir, tiene alguna limitación computacional razonable).

P, el probador, puede ejecutar cualquier estrategia (para eso es todopoderoso).

Para cada elemento s del conjunto S, después de interactuar con P, V aceptará (completitud).

Para cada x que no esté en S, después de interactuar con P, V no aceptará (coherencia)21.

En lenguaje matemático

Veamos un ejemplo concreto que nos sirve además para hablar de un problema fantástico: el problema de la residuosidad cuadrática. Dado un número entero n, queremos saber si otro número x ∈ {1, …, n-1} es el cuadrado perfecto módulo n de algún otro elemento en la estructura (hemos vuelto a Zn*). Resulta que si n no es primo, decidir si efectivamente hay un w del conjunto {1, …, n-1} tal que x = w2 mod n es un problema difícil salvo que se sepa factorizar n.

Aquí están Vera y Pedro; supongamos que ambos conocen n y x en el contexto anterior y que Pedro insiste en que x es efectivamente un residuo cuadrático módulo n (pues conoce una raíz cuadrada, es decir, un valor w de {1, …, n-1} con x = w2 mod n). Por otro lado, Pedro no quiere revelar w (pasándole este valor a Vera se zanjaría la discusión, por supuesto). Veamos si puede convencer a Vera realizando los siguientes pasos:

Pedro elige un valor al azar en Zn*, que llamaremos u, y envía a Vera y = u2 mod n.

Vera elige también uniformemente al azar un bit (cero o uno), b, y se lo manda a Pedro.

Pedro envía el elemento z = wbu mod n a Vera. Es decir, si el bit es un uno, Pedro envía el resultado de multiplicar w por u. Si el bit es un cero, Pedro envía el u que generó en el paso 1 (que, por cierto, nada tiene que ver con w).

Al finalizar la interacción, Vera ha de decidir si acepta o no la afirmación de Pedro. Si el bit elegido en el paso 2 es un cero, aceptará cuando z2 mod n coincida con el valor “y” que Pedro envió en el paso 1. Si el bit elegido es un uno, solo aceptará si se verifica la ecuación xy = z2 mod n.

Ejemplo 1

Veamos un ejemplo desarrollado del esquema anterior: supongamos que Pedro quiere convencer a Vera de que el número 8 es un cuadrado módulo 17. En este caso, el valor w de Pedro sería el número 5, pues 52 = 25 = 8 mod 17.

Así, una iteración del proceso sería de la siguiente forma:

1. Pedro elige un valor u al azar, por ejemplo, u = 6, y envía a Vera y = 62 = 36 = 2 mod 17.

2. Supongamos que Vera elige el bit b = 1 y se lo envía a Pedro.

3. Pedro enviará el elemento z = 5 · 6 = 30 = 13 mod 17 a Vera.

Ahora, Vera comprueba la ecuación x · y = z2 mod 17, que es en este caso 2 · 8 = 16 = 132 mod 17, que se verifica por ser 132 = 169 = 16 mod 17. Así, Vera acepta esta iteración.

¿Está Vera tomando bien sus decisiones? Veamos qué ocurre si Pedro dice la verdad. Ciertamente, si x es un cuadrado módulo n las comprobaciones de Vera serán correctas, independientemente del bit b que elija. Así, el IPS descrito cumple la propiedad de completitud. Ahora, supongamos que x no es un residuo cuadrático módulo n; ciertamente, si b = 1, Vera siempre rechazará la prueba, pues es imposible que xy = z2 mod n. Si esto fuese cierto, tendríamos

x = z(u-1) z(u-1) = z2(u-2) = z2(y-1) mod n

Luego x tendría que ser un residuo cuadrático, lo que es falso. Además, si b = 0 y el valor elegido por Pedro en el paso 1 tampoco está bien construido (no es un residuo cuadrático), Vera también rechazará (esto es algo más difícil de ver, pero puede también demostrarse). Así, la probabilidad de que Vera rechace la prueba es de (al menos) ½. Si repetimos la interacción k veces, la probabilidad de que Vera rechace se amplifica; solo tenemos que aumentar k hasta que esta sea prácticamente uno22.

Parece un buen plan. Sin embargo, en este punto, cabe preguntarse: ¿y por qué Pedro no se deja de líos y le da el valor w directamente a Vera? Eso, estimado lector, le haría perder toda la gracia al asunto. Tras la interacción, Vera tendría tanta información como Pedro, con lo que la utilidad práctica del IPS se vería muy limitada. El uso fundamental de los IPS en criptografía es facilitar que un usuario demuestre que ciertos valores que quiere mantener en secreto son correctos en un determinado sentido. Por ejemplo, Pedro quizá está intentando demostrar a Vera que está eligiendo una clave de firma (w) correctamente, para un protocolo que exija que dichas claves sean raíces cuadradas de un cierto valor público (s) módulo n. Desde luego, Pedro no quiere soltar w, pues estaría delegando su firma a todo el que conozca dicho valor.

Pruebas de conocimiento cero

Sigamos pensando un poco en la tozudez de Pedro, que no quiere que Vera aprenda nada. La idea de conocimiento cero (en inglés, zero knowledge) aparece por doquier en criptografía moderna. Un protocolo interactivo gana esa etiqueta si puede argumentarse que, tras la interacción, ninguno de los usuarios involucrados ha obtenido información que no tuviese antes, con excepción del resultado final que se define como output o salida del protocolo. El IPS que acabamos de describir, por ejemplo, tiene esta propiedad. Demostrarlo no es nada fácil; es necesario argumentar que las respuestas que Pedro va pasándole a Vera no dejan escapar ni un solo bit de información acerca de w. Pero veamos ejemplos más sencillos para entender mejor este concepto.

En el artículo “Applied Kid Cryptography or How To Convince Your Children You Are not Cheating” (‘Criptografía aplicada para niños o cómo convencer a tus hijos de que no haces trampas’) se explica esta noción con un caso de uso fantástico. Este artículo fue publicado en 1999 por dos criptógrafos actuales extraordinarios: Moni Naor y Omer Reingold (y la que, suponemos, es la hija del primero, Yael Naor23). Pedro y Vera están ahora jugando a encontrar a Wally en una lámina gigante. En la lámina, como es habitual, se encuentran un montón de figuras de colores que hacen muy difícil distinguir la imagen de Wally, un personaje delgado, con gafas, que lleva un gorro bastante ridículo. Pedro (que, recordemos, es muy espabilado) ha encontrado a Wally rápidamente y quiere que Vera lo reconozca como ganador del reto. Sin embargo, no quiere decirle a Vera dónde está (para que ella, seguidamente, no pueda ir con la lámina retando a otros amigos sabiendo de partida la ubicación de Wally).

La estrategia de Pedro es muy sencilla. Necesita una cartulina opaca de tamaño superior a la lámina (esto es importante si queremos la propiedad de zero knowledge). En esa cartulina, hará un agujero en el que encaja exactamente la cara de Wally y poniendo la lámina detrás mostrará a Vera, a través de este, la imagen de Wally. Es importante que por el agujero no pueda verse nada más que revele información acerca de la ubicación del simpático personaje. En el artículo, Naor y Reingold dicen que esa es la solución “low-tech” y proponen también una “mid-tech”, que involucra una fotocopiadora y unas tijeras. Mis hijos, Carlos y María, prefieren una solución “high-tech” similar que utiliza una cámara digital y la capacidad de ampliar fragmentos de imagen de la misma. Uno de ellos sacará una foto de la lámina y luego, el que descubra a Wally, puede coger la cámara y ampliar (a solas) la imagen hasta que solo pueda verse la cara sonriente de este24. En cualquiera de los casos es fácil ver que el protocolo descrito es completo y coherente; además, Vera se convencerá en una única ejecución, sin necesidad de iterar.

El ejemplo de Wally es estupendo, pero hay otro caso de uso que deja aún más patente el ideal de una prueba de conocimiento cero25. Supongamos que Vera es ciega. Pedro quiere convencerla de que dos bolas de billar, con las que están jugando, son de distinto color. ¿Cómo puede hacerlo? Pongamos que una bola es azul y la otra naranja. Vera cogerá una bola en cada mano (la azul, por ejemplo, en la derecha y la naranja en la izquierda). Pedro y Vera se sitúan frente a frente y Vera esconde sus manos tras la espalda. Ahora Vera elige; cambia las bolas de mano o las mantiene en su posición inicial, y mueve las manos de nuevo al frente. Pedro, mirando las bolas, le dirá “has cambiado las bolas de mano” o “todo sigue igual”. Evidentemente, si las bolas son de distinto color, Pedro siempre será capaz de decir qué es lo que ha hecho Vera. Si las bolas son iguales, Pedro responderá al azar, acertando con probabilidad ½. Repitiendo el proceso k veces, sin embargo, su probabilidad de acertar todas las veces será (½)k (que va disminuyendo rápidamente a medida que k aumenta). Por tanto, con un número razonable de repeticiones en las que Pedro acierte, Vera se dará por convencida. En este ejemplo, de nuevo, es fácil ver la propiedad de completitud. Como decíamos, la coherencia es probabilística, pues hay una probabilidad (aunque muy pequeña, si k es grande) de que Pedro engañe a Vera si las bolas son del mismo color. El hecho de que la prueba es de conocimiento cero es obvio; tras la prueba, Vera no aprende nada que no supiese antes de jugar con Pedro. En una nueva ejecución del protocolo, eligiendo de nuevo dos bolas de billar, la probabilidad que tiene Vera de acertar si tienen o no el mismo color no ha cambiado por haber jugado anteriormente.

Otro ejemplo magnífico que ilustra este concepto puede encontrarse en el libro Computational Complexity, de Oded Goldreich. En una leyenda “no descrita en la Odisea” (como el propio autor dice al presentar este ejemplo), se habla del laberinto de la isla de Eea. La hechicera Circe reta a Ulises a atravesar dicho laberinto de la puerta norte a la puerta sur. Ulises, desconfiado, duda de que eso sea posible y le pide a Circe evidencias de la existencia de un camino que conecte ambas puertas. Circe se niega, diciendo que eso facilitaría que Ulises ganase el reto, pero este le replica proponiéndole una prueba especial: “Transpórtame mágicamente a un punto elegido al azar en el laberinto. Luego, yo elegiré ‘norte’ o ‘sur’ y tú guiarás mis pasos por el laberinto hasta la puerta de mi elección. Si hacemos esto bastantes veces, quedaré convencido de que, efectivamente, hay un camino que atraviesa el laberinto de la puerta norte a la puerta sur”. Circe, que por lo visto sabía bastante de pruebas de conocimiento cero, acepta el trato.

IPS: en la teoría y en la práctica

Los ejemplos anteriores son, sin duda, un buen ejercicio mental, pero quizá no permiten ver la importancia de los IPS. Sin embargo, lo cierto es que gracias a ellos se han obtenido resultados muy relevantes en teoría de complejidad. Dicha teoría persigue clasificar los problemas matemáticos en función de su dificultad computacional, con lo que es fácil imaginar el enorme impacto de esta teoría en criptología. Todo buen criptógrafo aspira a encontrar un problema matemático abstracto que, al concretarse, origine una gran cantidad de casos particulares de elevada complejidad computacional. Si, además, estos casos pueden resolverse fácilmente utilizando algún dato adicional, miel sobre hojuelas26.

Tradicionalmente, sin embargo, la teoría de complejidad se preocupa de la dificultad de los problemas en el peor de los casos, mientras que la criptografía necesita problemas que sean difíciles casi seguro. Tratemos de entenderlo a través de un ejemplo. El problema de factorización de enteros es uno de los favoritos de los criptógrafos porque, en la mayoría de los casos, su dificultad aumenta esencialmente al mismo ritmo que los números que definen cada caso concreto. Obviamente, factorizar el número 35 no es muy difícil. El 11.663 nos da algo más de miedo. Y si queremos factorizar un número N que es producto de dos primos grandes de verdad (digamos que N está cerca de 22056), la cosa cambia radicalmente. Pero, lo que es mejor, si cogemos N aún mayor, la dificultad del problema también aumentará27. En contraposición, existen muchos problemas para los que no hay algoritmos eficientes por culpa de unos cuantos casos aislados en los que las cosas se complican. En otras ocasiones, no tenemos ni idea de cuál es la proporción real de casos difíciles entre todos los posibles (ni de cómo encontrarlos). Así, aunque la teoría de complejidad etiquete algunos problemas como intrincados, esto no garantiza que puedan usarse en criptografía28. Dejando esto a un lado, los avances en teoría de complejidad son, en cualquier caso, fundamentales para los criptógrafos. Y el recíproco también es cierto: los resultados obtenidos (por criptógrafos) acerca de IPS desde los años noventa han ampliado los horizontes de la teoría de complejidad. Muchos de estos resultados tienen que ver con problemas relacionados con grafos.

Un grafo es una estructura simple; se define sencillamente como un conjunto de vértices que están conectados por aristas. De manera formal, un grafo G se hace explícito describiendo V, su conjunto de vértices, y E, el conjunto de aristas que los conectan. Si escribimos, por ejemplo, V como {v1, v2, v3, v4, v6}, una arista se representa como un par —por ejemplo, {v6, v2}— de nodos. A través de grafos se modelan gran número de estructuras, como redes sociales, de comunicación o transporte.

El mejor ejemplo para ver la potencia de los IPS está basado en el problema de decidir si dos grafos dados representan esencialmente la misma estructura (usando la terminología correcta, diríamos, si son o no isomorfos). Vamos a comentar, sin embargo, un protocolo IPS algo más sencillo, relacionado con el llamado problema de coloración de un grafo.

Supongamos que el grafo 1 representa un mapa en el que aparecen seis países, uno representado por cada vértice. Las fronteras vendrán indicadas a través de las aristas, es decir, pintaremos una arista conectando dos vértices si los países asociados comparten frontera.

Grafo 1

Así, el país v2 tiene frontera con v1 y v6, pero no con v3, v4 ni v5. Si ahora quisiéramos pintar el mapa de modo que países vecinos queden de distinto color, ¿cuántos colores hemos de utilizar? En este caso, serían tres. No parece una pregunta demasiado difícil de contestar, pero, de hecho, para un grafo arbitrario sí lo es. Hoy sabemos que cualquier mapa (definido con unas ciertas condiciones para limitar el número de países vecinos) puede ser coloreado usando tan solo cuatro colores diferentes. Una demostración formal de este hecho solo se obtuvo a mediados de los años setenta del siglo pasado, más de cien años después de que el problema fuese planteado.

Por otro lado, es conocido que, dado un grafo arbitrario, decidir si es posible colorearlo con solo tres colores es un problema de complejidad muy elevada. Podemos, sin embargo, dar un sencillo IPS de manera que, si Pedro conoce una forma de pintar el grafo con solo tres colores, pueda convencer a Vera de que es posible hacerlo sin revelar la coloración.

Imaginemos que la coloración que conoce Pedro es la del grafo 2.

Grafo 2

Coloración de Pedro

Lo primero que hará Pedro es elegir una permutación29 (uniformemente al azar) del conjunto de colores, es decir, una identificación del tipo:

Blanco → negro

Gris → blanco

Negro → gris

Llamemos a esta identificación Π. Pedro publica ahora un compromiso a Π (usando un esquema de compromiso de los que vimos en el capítulo anterior).

Vera ahora elige una arista al azar, por ejemplo {v1, v2} y le pide a Pedro la “coloración espejo” de estos vértices. Dicho de otro modo, no le dice cómo los ha pintado, sino los colores que la permutación Π les asigna.

Pedro contesta (en este caso, como v1 era blanco y v2 negro) {Π(blanco), Π(negro)}, es decir {negro, gris}. Además, tiene que enviar información suficiente para que Vera pueda verificar el compromiso publicado sobre Π con respecto a estos dos valores.

Vera aceptará la prueba si los dos colores que le pasa Pedro son distintos y, además, el compromiso publicado en el punto 1 es coherente con estos (en otro caso, según le convenga, Pedro podría decir en unos casos que Π (gris) es blanco y en otros que es negro).

Aunque no sea fácil explicar las propiedades de este IPS (¡y aún menos demostrarlas!), podemos intuir que funciona. Por un lado, Vera no aprende nada sobre cómo ha coloreado Pedro el grafo. Esto es porque los colores que Pedro declara para los vértices por los que esta pregunta, en realidad, no son los que él ha usado para colorearlos, sino sus “imágenes especulares” por Π. Por otro lado, debido al esquema de compromiso, una vez que Pedro ha fijado una permutación de colores ya no puede adaptarla para engañar a Vera. Aunque este ejemplo no sea fácil de entender por completo, deja patente que la interacción cambia radicalmente las reglas del juego a la hora de emitir demostraciones y verificarlas.

Además de su innegable valor teórico, los IPS y la noción de conocimiento cero son esenciales en numerosas aplicaciones criptográficas. A través de las pruebas de conocimiento (interactivas o no), podemos generar “testigos digitales” que permiten verificar la validez de distintos tipos de procesos. Estas herramientas son esenciales en computación segura en la nube, en los llamados protocolos blockchain (como el que subyace a la criptomoneda bitcoin) y, en general, en todo tipo de esquemas criptográficos en los que no queremos fiarnos de nuestros interlocutores ni de una autoridad exterior que audite la computación. Estos testigos son, por tanto, fundamentales: como habrás notado a estas alturas, la desconfianza es la seña de identidad de un buen criptólogo30.

Capítulo 4

Compartición de secretos.

Cuadrados latinos, polinomios y otras herramientas para la conspiración

There are many ways to tell your secrets. I think that a decent man who has discovered valuable secrets is under some obligation to share them. But I think that the technique of sharing them is a great study. And there are great masters who know how to impact the secrets they’ve learned. […] Now, you can reveal secrets in many ways. One way is to say this is the secret I have discovered. I think that this way is often less successful because when that certain kind of conscious creative mind brings itself to bear on this information, it distorts it, it makes it very inaccessible. Sometimes it’s just in the voice, sometimes just in the style, in the length of the paragraph; it’s in the tone, rather than in the message31.

Leonard Cohen

An Interview with Leonard Cohen, por Michael Harris (1969)

Carlos tiene un secreto. Un secreto pesado que necesita revelar, pero no de una manera irreflexiva y directa; no a una sola persona que pudiese (como tanto preocupaba a Leonard Cohen) dejar su impronta en el mismo y distorsionarlo. Carlos tiene un secreto que quiere revelar simultáneamente a varias personas, pero a condición de que cooperen para conseguirlo. Una vez más, por suerte para Carlos, tenemos una herramienta criptográfica que puede ayudarlo.

Los esquemas de compartición de secretos (representados en la literatura por las siglas SSS, del inglés secret sharing schemes) consideran la siguiente situación: un usuario (Carlos) posee un secreto, que quiere revelar a ciertos subconjuntos autorizados dentro de una lista de interlocutores. Esta colección de subconjuntos autorizados se llama estructura de acceso. Por ejemplo, si los interlocutores de Carlos son Iván, Ana y Héctor, una estructura de acceso posible es la formada por los tres subconjuntos {Ana}, {Héctor, Ana} y {Ana, Iván}.

Otras veces, como en los ejemplos que veremos a continuación, la estructura de acceso se define a través de un umbral que marca el tamaño mínimo de un conjunto autorizado; por ejemplo, Carlos podría autorizar a cualquier conjunto de interlocutores formado por al menos dos personas.

Así, un SSS será un protocolo criptográfico que permita a Carlos repartir fragmentos del secreto de modo que:

cualquier conjunto de usuarios en la estructura de acceso puede recuperar, cooperativamente, el secreto a partir de sus fragmentos;

cualquier conjunto de interlocutores que no esté en la estructura de acceso no podrá obtener información alguna del secreto32.

¿Son realmente útiles los esquemas de compartición de secretos? En el aula suelen utilizarse ejemplos impactantes de aplicación, como la distribución de la clave de acceso a un ordenador que controla cabezas nucleares o el reparto de la contraseña que abre la caja fuerte central de un banco. Suena importante, pero lo cierto es que hay muchas situaciones (bastante más mundanas) en las que los SSS desempeñan un papel esencial. Pensemos en todas las veces que introducimos nuestro usuario y contraseña para acceder a un cierto servicio a través de internet. ¿Dónde va esa contraseña? ¿Cómo se comprueba que es correcta? Primera opción: en algún lugar hay almacenada una lista de contraseñas autorizadas; si la secuencia que introducimos por teclado se encuentra en dicha lista, se permite el acceso. Este sistema, aunque plausible, no es especialmente eficiente. En realidad, la lista puede ser enorme, y la búsqueda asociada llevar bastante tiempo (para un adolescente frente a una pantalla, siete segundos son una eternidad). Segunda opción: en la lista no ponemos contraseñas, sino resúmenes de las mismas, para agilizar las búsquedas. Estos resúmenes se calculan a partir de las llamadas funciones hash criptográficas, y permiten acelerar notablemente la velocidad de identificación. Ahora bien, ¿es buena idea que esta lista (de contraseñas o resúmenes) esté en un único sitio? Esto dejaría a un adversario con pocas dudas acerca de qué máquina debe intentar controlar. A menos que dispongamos de los medios para blindar completamente de accesos indeseados a un servidor, es más sensato distribuir esa lista entre varias máquinas. La mejor forma de hacerlo es con un SSS: así, al menos, no hemos de preocuparnos si un fragmento de la lista cae en malas manos.

Veamos un ejemplo muy sencillo de SSS que, por otro lado, presenta una estructura de acceso bastante pobre: solo con que dos usuarios colaboren, podrán recuperar el secreto.

Carlos tiene un secreto, que es el número S. Lo va a compartir con n usuarios, U1, …, Un y, para ello, elige al azar n-1 números r1, …, rn-1 y define por último rn como el resultado de restarle estos al secreto, rn = S -r1 -…- rn-1 .

Ahora, a cada usuario Ui le hace llegar el fragmento s(i) consistente en todos los r’s, salvo el que tiene el subíndice i, es decir:

s(i) = (r1, …, ri-1, ri+1, …, rn)

Como S se construye sumando todos los valores ri, si dos o más usuarios colaboran pueden obtener S = r1 + …+ rn. Pero ¿y un usuario que no colabora con nadie? ¿Qué sabrá del secreto? Pues depende de dónde vivan los números utilizados para la implementación. Pensemos que son números naturales, es decir, enteros positivos (seguramente Carlos es informático, y no tiene muchas ganas de andar explicándole al ordenador cómo representar decimales). Así, tanto S como los valores r1 , …, rn son enteros positivos, luego cada usuario Ui tiene un puñado de números (r1, …, ri-1, ri+1, …, rn) que, sumados a uno desconocido (ri), llegan a S.

No es cierto, por tanto, que Ui no tenga ninguna información sobre el secreto. Conoce una cota inferior; el valor r1 + … + ri-1 + ri+1 + … + rn que es inferior a S, así que este sistema no sirve. Podemos, sin embargo, arreglarlo muy fácilmente; tomando otra estructura algebraica como base. En lugar de trabajar con todos los números enteros, hagámoslo con los de un cierto Zn. Como en capítulos anteriores, trabajamos con los números {0, 1, …, n-1} identificando cada número entero con su resto al dividir entre n. De este modo, puede demostrarse que un solo usuario no obtiene información sobre el secreto S. Esto es consecuencia de que al ir agregando números, si trabajamos módulo n, el resultado no siempre es un número mayor que aquellos que sumamos. Por ejemplo, módulo 36, si sumamos 14 + 12 + 19 obtenemos el número 9.

Veamos un ejemplo. Supongamos que Carlos quiere repartir el secreto S = 19 entre cuatro amigos, trabajando en Z23. Empezará por elegir al azar tres valores:

r1 = 5, r2 = 16, r3 = 8

y construye a partir de ellos

r4 = 19 - 5 - 16 - 8 = 13.

Efectivamente, sumando los cuatro valores anteriores se obtiene el secreto, pues

19 = 5 + 16 + 8 +13 mod 23,

Así, los fragmentos repartidos por Carlos son: S(1) = (16, 8, 13), s(2) = (5, 8, 13), s(3) = (5, 16, 13) y S(4) = (5, 16, 8); es obvio que con dos de estos fragmentos se tienen los cuatro valores cuya suma es exactamente S.

Una pregunta legítima en este punto es: ¿por qué no utilizar números reales? Si los valores r1, …, rn pueden ser tanto positivos como negativos, no se filtran cotas para el secreto a partir de los fragmentos s(i). Existe una explicación, que tiene que ver con el hecho de que los valores r1, …, rn-1 que elige Carlos han de seleccionarse al azar. Estas dos (aparentemente inocentes) palabras esconden un requerimiento titánico; de hecho, si queremos que el SSS funcione, dicha selección tiene que darse según una distribución uniforme33. Así, cualquier número de la estructura debería tener las mismas oportunidades de desempeñar el papel de un cierto ri. Si elegimos números en un conjunto finito —como es {0, 1, ..., n-1}—, este requisito es relativamente fácil de cumplir. Carlos se compra un dado perfecto con n caras, y listo: si el dado es en efecto completamente regular, cada cara tiene la misma probabilidad de ser la que queda boca arriba (que es 1/n). Así, si el dado tiene 6 caras, al tirarlo, es igual de probable que salga cualquiera de los números entre 1 y 6. Igual que lanzando una moneda se elige de manera justa entre dos alternativas, con dados de n caras podemos elegir entre n opciones posibles34. Pero ¿qué ocurre si la estructura algebraica es infinita? Simular una distribución uniforme no es en absoluto tarea sencilla (ni entender qué quiere esto decir exactamente). Mejor, por tanto, quedarnos con nuestros (a estas alturas, ya conocidos) conjuntos de clases de restos, que tan grácilmente han acompañado (por estas, y otras muchas razones) a los criptógrafos en las últimas décadas.

Polinomios que esconden secretos

Pasemos a hablar de esquemas de compartición de secretos algo más realistas. George Blackley y Adi Shamir fueron los primeros en concebir este tipo de herramienta, de manera independiente, a finales de los años setenta del pasado siglo. En estos primeros trabajos, la estructura de acceso se definía en función del tamaño, es decir, existía un valor T de manera que, si al menos T de los n interlocutores cooperaban, siempre podrían recuperar el secreto.

Adi Shamir, uno de nuestros criptógrafos favoritos, utilizó una idea muy sencilla basada en la interpolación. La interpolación es una técnica numérica para aproximar (o determinar por completo) un conjunto de puntos si solo conocemos algunos de ellos. Nuestro cerebro interpola constantemente. Por ejemplo, si no conocemos el trazado de una carretera pero sí varias ciudades por las que pasa, mentalmente uniremos esos puntos en el mapa mediante una línea poligonal que identificamos con la carretera. De manera más rigurosa, el llamado método de interpolación de Lagrange permite aproximar un polinomio y, de hecho, reconstruirlo correctamente si conocemos suficientes puntos por los que pasa.

Un polinomio es una expresión formal de este tipo:

f(x) = a0 + a1 x + a2 x2 + … + an xn

donde los valores ai, llamados coeficientes, están en una cierta estructura algebraica (por ejemplo, son enteros) y la x representa un valor variable (que solemos llamar, de hecho, variable o indeterminada). El número n se llama grado del polinomio.

Por ejemplo, 3 + x o Πx2 son polinomios sobre los números reales (es decir, sus coeficientes son números reales).

Si al cambiar la aparición de la x en la expresión anterior por un valor t y realizar las cuentas obtenemos el valor y, decimos que f(t) = y o que el polinomio f(x) pasa por el punto (t, y). Por ejemplo, 3 + x pasa por el punto (0, 3). De hecho, como todos los polinomios de grado uno, 3 + x representa una recta en el plano. Efectivamente, todos los puntos (t, y) por los que pasa están alineados en una recta. Como es bien sabido, con dar dos puntos de esta —por ejemplo (0, 3) y (-1, 2)— la estamos describiendo completamente. Esta sencilla idea animó a Lagrange en el siglo XIX a buscar una fórmula que describiese a partir de n + 1 puntos cualquier polinomio de grado n y, dos siglos más tarde, a Adi Shamir a esconder secretos en polinomios.

En lenguaje matemático: interpolación de Lagrange

Volvamos a la idea de Lagrange; si conocemos n + 1 puntos distintos

(t0, y0) (t1, y1), …, (tn, yn)

podemos reconstruir el polinomio f(x) calculando y0 m0(x) + … + yn mn(x) donde para cada j = 0, …, m se tiene

Ejemplo 2

Vamos a interpolar el polinomio f(x) = 2+ 3 x + 9 x2, trabajando en Z37 (como siempre, somos más felices trabajando módulo algo, qué le vamos a hacer…). Para ello, puesto que el polinomio tiene grado dos, harán falta tres puntos por los que pase; como f(0) = 2, f(1) = 14 y f(2) = 7 —recuerda que trabajamos módulo 37—, podemos coger los puntos (0, 2), (1, 14) y (2, 7).

Ahora, veamos si la fórmula de Lagrange funciona:

m0(x) = ; m1(x) = y m2(x) =

en nuestro caso, t0 = 0, t1 = 1 y t2 = 2, luego

m0(x) = ; m1(x) = y m2(x) =

y como y0 = 2, y1 = 14 e y2 = 7,

la fórmula dice f(x) = 2 - 14 + 7

Ahora, trabajando módulo 37, podemos sustituir ½ por 19, pues multiplicando 19 por 2 obtenemos 38, que es 1 módulo 37 (es decir, 19 es el inverso multiplicativo del 2 en Z37). En efecto, tenemos

f(x) = (x - 1)(x - 2) - 14x(x - 2) + 19 · 7 x(x - 1) =

= (x - 1)(x - 2) - 14x(x - 2) + 22 x(x - 1) = 9x2 + 3x + 2,

luego, conocidos los tres puntos, hemos obtenido el polinomio inicial.

¿Cómo funciona, pues, el esquema de Shamir? Muy sencillo. Supongamos que el secreto de Carlos es un número en un cierto Zp (con p un número primo, para poder hacer las cuentas como es debido). Carlos esconderá el secreto como el término libre de un polinomio, es decir, el que no lleva x, que hemos llamado a0. Luego, completará el polinomio hasta un cierto grado n eligiendo coeficientes al azar35. De este modo, fija la exigencia de que al menos n+1 de sus interlocutores tengan que colaborar para reconstruir el secreto. Después, solo ha de repartir los puntos (fragmentos) a sus interlocutores, por supuesto, dando solo un punto de la forma (t, f(t)) a cada uno.

Como la fórmula de Lagrange es correcta, podemos asegurar que se cumple la propiedad (1), es decir, dados n + 1 participantes, interpolando con sus puntos pueden reconstruir el polinomio construido por Carlos y obtienen, por tanto, el secreto. ¿Qué pasa con la propiedad (2)? Pues, ciertamente, también se verifica. Conocidos n puntos o menos por los que pasa f, hay tantos polinomios posibles como elementos en Zp. Así, las coaliciones de usuarios que pretendan averiguar el secreto con menos de n + 1 puntos, por muchas cuentas que hagan, siguen sin tener ni idea de cuál es el secreto de Carlos. Y, además (y esto es algo para reflexionar), no tenemos que suponer nada sobre la capacidad computacional de esos usuarios no autorizados: hagan lo que hagan, no saben nada del secreto. Genial, ¿verdad?

El esquema de Shamir es uno de los más utilizados; no solo por su sencillez, sino también por tener propiedades estupendas que permiten operar con los fragmentos de un secreto de manera útil. Pero existen muchas otras construcciones que utilizan ingeniosos recursos combinatorios; veamos una de ellas.

Compartamos un sudoku

Cooper, Donovan y Seberry propusieron en 1994 un ingenioso esquema de compartición de secretos combinatorio. Aunque sus propiedades distan mucho de hacerlo atractivo para la práctica, nos da una excusa fantástica para alejarnos (aunque no del todo) de las construcciones criptográficas centradas en teoría de números.

Ahora es María la dueña del secreto. Como no podía ser de otra manera, su secreto es más complicado que el de Carlos, pues es una tabla con n filas y n columnas rellena con números. En esta tabla, cada número aparece exactamente una vez en cada fila y columna. Podemos, pues, pensar que el secreto que María guarda celosamente es un sudoku simplificado36, donde se reparten los dígitos del 1 al 9 siguiendo la propiedad descrita, como este:

La estructura de la que hablamos tiene un nombre en combinatoria: se trata de un cuadrado latino. De manera general, se define un cuadrado latino como una tabla de elementos tomados de un conjunto de tamaño N37, de modo que cada elemento aparezca exactamente una vez en cada fila y columna. Usando esta notación, escribiremos la terna (i, j, k) para representar que el número k está en la fila i, columna j. Por ejemplo, la terna (1, 2, 6) indica que en el cuadrado anterior la posición (1, 2) está ocupada por el 6. Informalmente, diremos que un cuadrado latino parcial es un cuadrado latino a medio rellenar, es decir, con posiciones vacías. Un cuadrado latino parcial se dice que forma un conjunto crítico para un cuadrado latino L si cumple dos propiedades:

solo puede rellenarse de una manera para dar lugar a un cuadrado latino completo (que es justamente L);

si vaciamos alguna de sus entradas (es decir, borramos el número escrito en una posición de las que no estaban vacías), se pierde la propiedad anterior.

Veamos ahora cómo funciona el esquema de Cooper et al., para ver si ayuda a María a compartir su cuadrado latino.

En lenguaje matemático

Como decíamos, María tiene un secreto, que es un cuadrado latino nxn. Las dimensiones del cuadrado son conocidas por todos. María construye los fragmentos como sigue:

Selecciona un conjunto S, que es la unión de varios conjuntos críticos para L. Este conjunto S puede verse como una colección de ternas (i, j, k) como las que describíamos antes.

A cada interlocutor, María le dice cómo rellenar un hueco del cuadrado usando S, es decir, le hace llegar una terna de S de la forma (i, j, k).

Ahora, si unos cuantos participantes ponen en común sus ternas y resulta que tienen un conjunto crítico para L, pensando un poco y rellenando las casillas vacías de la única manera posible, recuperan el secreto de María. Sin embargo, si las ternas que tienen son compatibles con muchos cuadrados latinos, no sabrán a ciencia cierta cuál es el repartido inicialmente.

Veamos un pequeño ejemplo (tomado del artículo original de Cooper et al., “Secret Sharing Schemes Arising from Latin Squares”). El secreto de María es el siguiente cuadrado:

María, que es muy buena en combinatoria, define el conjunto S como el formado por las ternas {(2, 1, 2); (3, 2, 1); (1, 3, 3)}. Ahora, a cada participante le dará una de esas ternas. Es fácil ver que si dos participantes colaboran, recuperan el secreto. La razón es que cualquier conjunto de dos elementos de S define un conjunto crítico del cuadrado de María.

Por ejemplo, con los dos primeros fragmentos tenemos la siguiente disposición:

Esta solo puede completarse de una manera para llegar a un cuadrado latino, reconstruyendo precisamente el cuadrado de María. Sin embargo, el participante (solitario) que solo tiene el fragmento (1, 3, 3) ha de completar esta tabla:

Y puede hacerlo de varias formas distintas:

¿Cuál es, entonces, el cuadrado de María? El tercer participante no tiene ni idea, pues ambos son posibles. De todas formas, como seguramente ya te has dado cuenta, este esquema no cumple exactamente la condición (2) que exigíamos a un SSS. Esto es porque hay información parcial que se filtra a partir de cualquier fragmento; cada participante conoce con certeza, al menos, una posición en el cuadrado de María. Esto, desde luego, es algo que ningún criptógrafo de bien estaría dispuesto a tolerar. Definir además la estructura de acceso de un esquema de este tipo no es baladí; ¿cómo calcular, en general, conjuntos críticos de un cuadrado latino de dimensión n? Y ¿cuántos conjuntos críticos hay? En la realidad, por mucho que nos gusten los cuadrados latinos, es necesario recurrir a estructuras combinatorias algo más intrincadas (en concreto, matroides y polimatroides) si queremos hacer SSS útiles de verdad.

Un mundo lleno de secretos

A lo largo de este capítulo hay un personaje fundamental del que no hemos hablado (al menos de manera explícita). ¿Dónde está aquí el adversario? Un sistema criptográfico que se precie siempre tiene que protegernos, en algún sentido, de alguien. En este caso, ¿de quién? Pensemos un poco. La propiedad (2) de los SSS plantea la exigencia de que los usuarios que no formen un conjunto autorizado no obtengan información alguna sobre el secreto. Por muchos cálculos que hagan no tendrán información alguna sobre el secreto. Todo esto está muy bien, pero esconde una hipótesis poco realista sobre el comportamiento de los usuarios; estamos suponiendo que van a seguir a pies juntillas las instrucciones del protocolo. Si un usuario es realmente malicioso podría estafar fácilmente a todos sus compañeros de fatigas. Supongamos, por ejemplo, que forma parte de un conjunto autorizado. En la fase de puesta en común, nuestro usuario perverso recoge los fragmentos de sus compañeros, pero en lugar de proporcionarles el suyo, se inventa un fragmento distinto (de hecho, puede proporcionar uno diferente a cada interlocutor). Lo hace además de tal forma que nadie (salvo él, claro está) será capaz de recuperar el secreto.

Un cosa más (por si aún no te has preocupado lo suficiente); también estamos suponiendo que los canales de comunicación entre el dueño del secreto (Carlos o María) y sus interlocutores son muy de fiar. Cuando me llega un mensaje (por ejemplo, en la distribución inicial de fragmentos), ¿puedo estar seguro de su origen? ¿Solo yo lo estoy recibiendo?

El planteamiento general a la hora de trabajar con SSS es empezar por el escenario que (quizá) has tenido en la cabeza en las páginas anteriores. Se declara a los usuarios honestos, pero curiosos38, indicando que en todo momento asumimos que seguirán la especificación del protocolo. Después, tomamos también como hipótesis que hay canales privados y autenticados (es decir, “blindados” frente a lecturas y falsificaciones de un tercero), establecidos entre cada par de usuarios del esquema. Una vez hemos conseguido diseñar y demostrar seguro un SSS partiendo de estas hipótesis, tratamos de restringir el modelo eliminando tan optimistas premisas y pasando al llamado modelo malicioso, donde los usuarios pueden hacer (casi) cualquier cosa. Y luego, claro, está el dueño del secreto, que también puede tener aviesas intenciones y transmitir a algunos usuarios fragmentos manifiestamente inservibles. Así, los resultados en SSS nos plantean una plétora de escenarios distintos; casi siempre el dueño del secreto va a ser honesto39, a veces se supone que hay una mayoría de usuarios honestos, otras que ⅔ de los participantes son honestos pero curiosos, etc. Lo más habitual, en cualquier caso, es confiar en que los canales de comunicación son bastante buenos. Recuerda, por tanto, que para compartir un secreto con personajes de los que no te fías, has de armarte al menos con un esquema de cifrado y una buena firma digital.

Capítulo 5

Criptografía omnipresente.

Emparejamiento online,

votaciones electrónicas y otras

historias magníficas y aterradoras

Es estupendo tener el escenario lleno. Repleto de actores y hasta arriba de pintorescos cachivaches. ¿Qué podemos hacer con todo esto? Tenemos métodos para cifrado y firma, pruebas de conocimiento cero, esquemas de compartición de secretos y otros muchos artefactos (muy a mi pesar, no mencionados en este libro). Además, en el escenario hay personajes diversos que ostentan distintas etiquetas según su (presunto) nivel de honestidad. Ahora, a escena.

Computación multiparte: computando con tu enemigo

Empezamos con el decorado del capítulo anterior, donde un grupo de personas colaboraban para reconstruir cooperativamente un secreto. Nos ha gustado este planteamiento, más complejo que el que teníamos en los primeros capítulos. Entonces, como en una película americana clásica, había buenos (Alice y Bob) y malos (sin nombre, pero siempre de aspecto desaliñado). Héroes y antihéroes claramente señalados desde el principio40. Nos gusta más pensar que, en el mundo real, lo más habitual es que haya personas esencialmente buenas que en ocasiones se desvían hacia el mal. Así funciona por ejemplo el escenario HBC o semihonesto que ya hemos comentado, en el que se sitúan muchos protocolos de computación multiparte41. En él, siempre habrá varios usuarios persiguiendo un objetivo común que, sin embargo, tienen intereses contrapuestos. En un primer enfoque —HBC—, los usuarios seguirán la especificación del protocolo, sin perder de vista sus intereses particulares. Un paso más allá, en el modelo malicioso (a veces llamado, para enfatizar, completamente malicioso) puede también ocurrir que algunos se desvíen de la especificación del protocolo.

Matemáticamente, muchos trabajos en computación multiparte se formalizan hablando de evaluación segura de funciones. Se parte de n usuarios de un sistema U1, …., Un, cada uno dueño de un cierto valor (que quiere mantener en secreto), el input privado al protocolo (que denotamos xi, de cada usuario Ui). Nuestro grupo quiere evaluar una cierta función F, que depende de varias variables, en la ristra que forman los valores de los usuarios involucrados, es decir, quiere obtener el valor y = F(x1, …, xn). A la vez, todos quieren mantener su input privado (haciendo honor a su nombre) en secreto.

Pongamos un ejemplo; varios bancos están planteándose una fusión. Para saber si llevándola a cabo aumentarían significativamente su número de clientes, querrían conocer cuántas personas tienen productos en alguno de los bancos involucrados. Si llamamos xi al número de clientes del banco Ui, lo que necesitan es un protocolo para evaluar de manera segura la función suma (que dará el total de los clientes). Tras ejecutar el protocolo, todos sabrían cuántos clientes tendría (potencialmente) la entidad resultante de la fusión. Si el protocolo es seguro, nada (salvo lo que puede inferirse al conocer el número total de clientes) habrá podido obtenerse a través de la interacción. De ese modo, por ejemplo, un banco podría aceptar fusionarse con un grupo de entidades pese a que muchas no le aporten clientes nuevos —la computación multiparte tiene estas cosas.

Un ejemplo clásico en este contexto es el llamado problema de los millonarios, propuesto por Andrew Yao en 1982. Andrew Yao es un informático teórico chino, también ganador de un Premio Turing, que ha sido profesor en algunos de los centros más prestigiosos del planeta (MIT, Berkeley, Stanford, Princeton…). Hoy, a sus más de 70 años, es decano del Institute for Interdisciplinary Information Science de la Universidad de Tsinghua, en Beijing. Pues bien, Yao planteó la siguiente cuestión: dos millonarios quieren saber cuál de los dos es más rico, sin revelar al otro cuánto dinero tienen. A ser posible, querrían que, tras la computación, nada innecesario se filtrase a su interlocutor.

Vamos a darles nombre, llamémoslos Donald y Rupert. Un protocolo para resolver este problema serviría para calcular el máximo de dos valores dados; por tanto, si Rupert es más rico que Donald, tras la ejecución, Donald solo conocería ese hecho (no sabría si Rupert tiene un solo euro o un trillón de euros más que él). Si pensamos un momento, es probable que se nos ocurra una solución (y también, lamentablemente, es muy posible que esta no sea correcta).

Uno de los caminos más habituales a la hora de plantear un protocolo para el problema de Yao es sugerir algo de este estilo: un árbitro comienza con una cierta cantidad C0 (pongamos, C0 = 10 millones de euros), que seguro ambos tienen. Después, suma sucesivamente a esta un valor fijo T, de modo que en el paso i-ésimo, Ci valdrá 10 + i T. Tras cada suma, Donald y Rupert levantan la mano si tienen (al menos) Ci euros en sus cuentas, y así, seguimos aumentando la cantidad considerada hasta que uno de los dos levanta la mano, y el otro no.

Ejemplo 1

Comenzamos con C0 = 10, y vamos a tomar T = 5. Así, tendremos C1 = 15, C2 = 20, etc. Supongamos que, en el paso 300, Donald levanta la mano, pero Rupert no. Donald es más rico, pero, ¿sabemos algo más? Por supuesto. Como los dos levantaron la mano en el paso 299, sabemos que ambos tienen, al menos, C299 = 10 + 299 · 5 = 1505 millones de euros. Como, además, Rupert no levantó la mano en el paso 300, su fortuna es inferior a C300 =1510 millones de euros.

Podemos ver fácilmente dos inconvenientes grandes que presenta esta idea. Por un lado, nos proporciona un intervalo de tamaño T en el que sabemos con certeza que está la fortuna del perdedor. Por otro, el protocolo no sirve para detectar al ganador en muchos casos, ¿verdad?

Tampoco parecía una idea tan mala, y el resultado, sin embargo, es bastante penoso. No nos desanimemos; encontrar protocolos seguros en computación multiparte no es en absoluto sencillo. Veremos en seguida una forma de terminar con la desazón de nuestros dos millonarios; pero, para ello, hemos de avanzar un poco más.

Markus Jakobsson y Moti Yung propusieron, doce años después del planteamiento de Yao, una magnifica solución para un problema relacionado, que llamaron problema de los millonarios socialistas42. En él, Donald y Rupert no quieren determinar quién es más rico, solo les interesa saber si poseen o no exactamente la misma cantidad de dinero. La solución de Jacobsson y Yung es breve y elegante, pero utiliza un arsenal considerable: intercambios de Diffie-Hellman y pruebas de conocimiento cero. Lejos de simplificarnos la vida, perseguir objetivos aparentemente más modestos a menudo nos lleva a protocolos más complejos. Este mantra alcanza cotas insufribles de verdad cuando consideramos la computación multiparte para operaciones entre conjuntos.

Bajamos a Rupert y Donald del escenario (puesto que ya no hablaremos más de dinero), y suben Camino y Pablo, que persiguen el amor. Ambos están buscando pareja y les gustaría, a ser posible, encontrar a alguien con quien compartir una afición inconfesable: el gusto por las canciones de rock ochentero presentadas por países nórdicos a Eurovisión. Se animan a utilizar una herramienta para buscar pareja a través de internet, que llamaremos CRYNDER. Lo que hace a CRYNDER especial es que propone a los usuarios emparejarse entre sí revelándoles exclusivamente las características que comparten. Es decir, si llamamos C al conjunto de características que declara Camino al abrir un perfil en CRYNDER y P al que confiesa Pablo, cada uno recibirá el perfil del otro conteniendo exclusivamente las características compartidas, es decir, con los elementos de la intersección de los dos conjuntos, P∩C.

Lo que CRYNDER lleva detrás es un protocolo MPC para el cálculo de la intersección de dos conjuntos (problema que, como no podía ser de otro modo, se etiqueta con siglas: PSI del inglés, Private Set Intersection).

En los últimos diez años se han propuesto infinidad de protocolos para PSI con distintas propiedades; muchos son asimétricos (solo Camino conoce la intersección y a Pablo se le deja in albis) y en la mayoría de los modelos se considera admisible que se filtren los tamaños de los conjuntos involucrados. Estos protocolos utilizan maquinaria pesada: oráculos aleatorios, esquemas de compromiso, cifrado homomórfico y filtros de Bloom son algunas de las armas exóticas con las que cada propuesta pretende desbancar al protocolo anterior. Esta proliferación de diseños se debe a sus múltiples aplicaciones prácticas (muchas no precisamente enfocadas al cortejo). Gracias a protocolos PSI, es posible contrastar, por ejemplo, la lista de pasajeros de un vuelo con una que enumera sospechosos de terrorismo. Las agencias de inteligencia de distintos países encuentran en estas técnicas la forma de compartir información altamente sensible. También, gracias a un esquema de este tipo, dos empresas que compiten pueden ver si tienen clientes en común (lo cual es útil, por ejemplo, para detectar incumplimientos de contratos en exclusiva).

En nuestro caso, vamos a ver cómo un protocolo PSI es suficiente para resolver el problema de los millonarios propuesto por Yao.

Esta solución fue presentada por Lin y Tzeng, en el congreso ACNS de 200543.

En lenguaje matemático

Desginemos con la letra A a la fortuna de Donald, y con la J a la de Rupert (ambos son, pues, números enteros positivos). Queremos saber si A > J y, para ello, comenzamos por escribirlos en binario, obteniendo dos secuencias:

A = an an-1 …a1 y J = jn jn-1 …j1

(Estamos suponiendo que ambas tienen la misma longitud, n, lo cual puede imponerse de antemano cogiendo n suficientemente grande)44.

Llamamos ahora 0-codificación de J al conjunto J0 que se construye cogiendo “fragmentos” de J, de izquierda a derecha, que acaban por 0, y sustituyendo ese último cero por un 1. Así, si J = 8, en binario, escribimos J = 1000, si cogemos las secuencias que terminan en 0 (de izquierda a derecha), estas son: 10; 100; 1000. Cambiando los últimos ceros por unos, construimos los elementos de J0, por tanto:

J0 = {11, 101, 1001}

Por otro lado, se define la 1-codificación de una secuencia A = an an-1 …a1 como el conjunto A1 que se construye cogiendo “fragmentos” de A, de izquierda a derecha, que acaban por 1 (y ahora, sin hacer nada más). Así, si A = 6, en binario se representa como A = 0110 (añadimos un cero delante para representarlo usando cuatro bits). Las cadenas que acaban en 1 son, por tanto, 01, 011, y por eso tenemos que

A1 = {01, 011}

Ahora viene la magia de este método: puede demostrarse que A es mayor que J si y solo si A1 y J0 tienen elementos en común, es decir, si y solo si tienen intersección no vacía.

En nuestro caso, como, de hecho, J es mayor que A, A1 y J0 no tienen ni un elemento en común (esto, usando el teorema de Lin y Tzeng, indicaría que J es al menos tan grande como A).

Ahora sí que nos quedamos tranquilos: si Donald y Rupert tienen a mano un protocolo para efectuar PSI, podrán usar este método para resolver el dilema que los tortura.

El disputado voto del sr. Criptógrafo

Vamos a hablar ahora de otro de los griales de la criptografía moderna: la búsqueda de la votación electrónica segura. La idea de modernizar los sistemas de votación tradicionales a través de las nuevas tecnologías de la información es tremendamente atractiva (por distintas razones) para políticos e ingenieros.

Aunque resulte increíble, la primera patente de un sistema para votación electrónica es de 1884 y tiene por autor nada menos que a Thomas Edison. Por lo visto, Edison intentó vender su método a las autoridades de Massachusetts sin demasiada fortuna. Según a quién se pregunte, distintos tipos de votaciones electrónicas (usando más o menos recursos tecnológicos y combinándolos con otros más tradicionales) llevan en uso desde los años sesenta en todo el mundo. Los criptógrafos, cautos ellos, se han resistido a utilizar sistemas de votación electrónica hasta 2010, cuando por primera vez se utilizó el protocolo Helios para elegir a la dirección de la IACR (International Association for Cryptologic Research). ¿Por qué esta reticencia? Al fin y al cabo, el resultado de unas elecciones puede formalizarse como un protocolo de computación multiparte, área bien conocida y desarrollada. Pensemos en los votos como el input privado de los usuarios, y en el resultado de la votación como una cierta función de esos valores. Ahora, elijamos el mejor protocolo MPC disponible para esa función. ¿Qué puede salir mal?

Lo cierto es que muchas cosas: las garantías que proporciona la MPC se nos quedan cortas. Tendríamos la seguridad de que nuestro input (el voto) se mantiene secreto y también de que la función (resultado) se computa correctamente. Hay muchos elementos (razonables o no) que exigimos a un proceso democrático que no podemos dar por sentados usando MPC “cruda”. Las características que se exigen a un protocolo para votación electrónica superan con creces a lo que exigimos a un proceso tradicional. Según Canetti y Rivest, un esquema de votación aceptable debe ser45:

Democrático: todo votante en el censo debe tener la posibilidad de votar. Además, solo debe contabilizarse de manera efectiva un voto por votante censado.

Privado: nadie debe obtener información alguna sobre qué ha votado cada usuario (aunque sí puede publicarse quién ha votado).

Libre de coacciones: no puede ser posible coaccionar a alguien para que vote en un cierto sentido. En particular, ningún votante podrá demostrar a alguien que ha votado por una u otra opción.

Correcto: el resultado final de la votación está bien calculado (ningún voto se altera, sustituye o anula de manera maliciosa en el proceso).

Verificable: cada usuario puede verificar que su voto se ha contado. Todos los usuarios pueden verificar que el resultado final de la votación se ha computado correctamente.

Robusto: un grupo de votantes maliciosos no puede alterar el proceso de votación (en particular, no puede impedir que esta se lleve a cabo).

Justo: ningún resultado parcial de la votación se filtra antes del cómputo final.

Usable: cualquiera46 tiene que ser capaz de votar, fácilmente, desde distintas plataformas.

Esta lista debería, cuando menos, escandalizar a un aprendiz de criptógrafo. ¿Por qué se exigen tantas cosas a una votación electrónica? ¿Cuándo hemos podido verificar —sin depositar nuestra confianza en un número enorme de personas— el resultado de unas elecciones tradicionales? ¿Cómo puede garantizarse que un sistema —clásico o electrónico— protege a los votantes ante posibles coacciones?

En realidad, no hay razones para el escándalo; las exigencias anteriores están bien justificadas. La implantación descuidada de un sistema de votación electrónica es mucho más peligrosa que el desarrollo de sistemas clásicos cuestionables. Pese a esto, inasequibles al desaliento, muchos criptógrafos se han embarcado en diseños de este tipo. Dejando el debate social a un lado, el reto técnico es, sin duda, fascinante.

En lenguaje matemático

Veamos una idea general para construir un sistema de votación electrónica usando un tipo especial de esquemas de cifrado de clave pública47. Consideraremos un escenario en el que cada votante votará por un único candidato dentro de una lista.

Sea ahora (KeyGen, Enc, Dec) un esquema de cifrado de clave pública, con dos peculiaridades:

El descifrado es distribuido y depende de un umbral, es decir, existe un valor T de manera que la clave secreta sk (secret key) está distribuida (quizá con un SSS) entre varios receptores (2T + 1), por lo que, para poder descifrar, al menos T + 1 de ellos han de colaborar.

El cifrado es homomórfico en un cierto sentido. Sin entrar en detalles, por ejemplo, es suficiente que sea “compatible” con la suma. Una opción típica es pedir que al multiplicar dos cifrados se obtenga un cifrado válido de la suma de los textos subyacentes, es decir:

Enc(a) · Enc(b) = Enc(a +b)

Supongamos ahora que cada voto vi es un número natural (es decir, a cada candidato le asignamos un número). Ahora, cada votante coge la clave pública pk (public key) y cifra el resultado de elevar a un número “especial” —que llamaremos base— al número correspondiente con su candidato. Así, su “voto en sobre” sería, matemáticamente, el valor

bi = Enc(pk, basevi)

Pues bien, todos estos votos enmascarados se exponen al público (por ejemplo, en una página web). Después, se construye el producto

y = b1 · b2 · … · bn

de todos los valores cifrados. Al menos T+1 servidores colaboran para descifrar ese valor y recuperan el número

a1 · basev1 + a2 · basev2 + … + an · basevn

En esa expresión a1 es, de hecho, el número de votos del candidato “1”, a2, los votos que ha obtenido el candidato “2”, y así sucesivamente. Todos estos valores han de poder extraerse sin ambigüedad del valor obtenido tras descifrar. Las propiedades del valor “base” y la estructura algebraica en la que nos movamos tienen que garantizar esto. Parece complejo y, de hecho, lo es.

Llegados a este punto, creo que es justo decir que nuestras aspiraciones iniciales eran demasiado elevadas (al menos en lo que implicaría a nuestros abuelos). Sin embargo, su elevada complejidad no es la razón fundamental de que los sistemas de votación electrónica no estén, a estas alturas, ampliamente instaurados. Más difícil que garantizar usabilidad y verificabilidad (en un sentido alocadamente amplio) es conseguir el tercer objetivo de nuestra lista. ¿Por qué nos preocupan tanto las coacciones? ¿Acaso las elecciones habituales no están expuestas a sobornos y a todo tipo de oscuras presiones? Seguramente, sí, pero no de una manera masiva. Acompañar al votante en la cabina para comprobar que, efectivamente, vota bajo nuestra inspiración no es un sistema fácilmente aplicable a miles (o millones) de electores. Comprobar (en remoto) que han votado según nuestros deseos es mucho más fácil gracias a las garantías de verificabilidad que exigimos implacablemente a los sistemas electrónicos. En el ejemplo anterior, si mi “voto enmascarado” bi es de dominio público, ¿puedo demostrarle a un observador externo —llamémoslo Vladi— que es un cifrado del candidato vi? Si la respuesta es afirmativa, Vladi estará de acuerdo en pagarme el precio pactado. Lo cierto es que, en muchos casos, este tipo de “confirmación” a terceros es posible. En el ejemplo que hemos esbozado, solo tengo que demostrarle que bi es un cifrado válido construido con el algoritmo Enc y la clave pública pk, lo cual es posible (y sencillo) para muchos esquemas de cifrado. Además, por mucho que nos sorprenda, es posible que Vladi sepa bastante de cifrado homomórfico, y estará encantado de usar sus conocimientos.

Epílogo (aftercrypt)

Independientemente del nivel de conocimientos que llevemos en la mochila, la criptografía moderna nos enfrenta a preguntas y escenarios irresistibles. Más allá de los planteamientos técnicos, nos lleva a cuestionar las consecuencias de la forma en que gestionamos y difundimos información. Nos hace dudar de la inocuidad de ideas y procedimientos que hemos dado por sentados. Nos vuelve más críticos, más escépticos y, en última instancia, menos vulnerables.

Cuando por primera vez leí la traducción de la palabra inglesa aftermath (literalmente, ‘después de las matemáticas’) como ‘secuela’, pensé que era necesario incluir en algún diccionario la palabra aftercrypt (‘después de la criptología’). Aftercrypt como consecuencia irreversible y extraordinaria, resaca que sin remedio nos lleva a nuevas y fascinantes maneras de plantearnos problemas en matemáticas. Todo matemático que entra en contacto con el mundo de la criptología ve cómo su manera de percibir un razonamiento se ve afectada para siempre. En mi caso, y en el de tantos que conozco y admiro profundamente, las secuelas han sido irreversibles.

Espero que las páginas anteriores hayan sido un ojo de cerradura que permita atisbar toda la diversión que hay tras la puerta.

Bibliografía

Barkee, B. et al. (1994): “Why You Cannot Even Hope to Use Groebner Bases in Public-Key Cryptography? An Open Letter to a Scientist Who Failed and a Challenge to Those Who Have Not Yet Failed”, Journal of Symbolic Computations, 18 (6), pp. 497–501.

Cramer, R.; Damgaard, I. B. y Nielsen, J. B. (2015): Secure Multiparty Computation and Secret Sharing, Cambridge University Press, Cambridge.

Goldreich, O. (2008): Computational Complexity: A Conceptual Perspective, Cambridge University Press, Cambridge.

Hernández Encinas, L. (2016): La criptografía, CSIC/Los Libros de la Catarata, Madrid.

Katz, J. y Lindell, Y. (2014): Introduction to Modern Cryptography, CRC Press, Florida.

León, M. de y Timón, Á. (2014): Rompiendo códigos: vida y legado de Turing, CSIC/Los Libros de la Catarata, Madrid.

Lin, H. Y. y Tzeng, W. G. (2005): “An Efficient Solution to the Millionaires’ Problem Based on Homomorphic Encryption”, Proceedings of Applied Cryptography and Network Security, vol. 3.531, pp. 456-466.

Lipmaa, H. (2005): “Secure Electronic Voting Protocols”, Handbook of Information Security, John Wiley & Sons, Chinchester.

Singh, S. (2000): Los códigos secretos: el arte y la ciencia de la criptografía, desde el antiguo Egipto a la era de Internet, Debate, Madrid.

Young, A. y Yung, M. (2004): Malicious Cryptography: Exposing Cryptovirology, Wiley, Hoboken.

Notas

1 . “Cryptology is the science and practice of designing computation and communication systems which are secure in the presence of adversaries”, International Association for Cryptologic Research, www.iacr.org

2 . El término esteganografía proviene de las palabras griegas steamos (‘oculto’) y graphos (‘escritura’). Se aplica a los métodos para el envío y entrega de mensajes camuflados dentro de un objeto o contenedor, de forma que no se detecte su presencia y consigan pasar desapercibidos.

3 . Un algoritmo es un procedimiento descrito con exactitud para realizar una tarea en pasos bien diferenciados. Habitualmente, hay un valor o valores de entrada que determinan el desarrollo de dichos pasos. Tras el último paso, el algoritmo devuelve algún valor de salida. La notación A(input) = output se suele utilizar para expresar que el algoritmo A con valores de entrada input proporciona como salida los valores output.

4 . La obra fundamental de Suetonio es Vida de los Césares (De vita Caesarum), que contiene las biografías de doce emperadores romanos, de Julio César a Domiciano.

5 . Malas noticias: en cualquier caso, ese esquema no es muy seguro.

6 . Eliminamos la letra ñ de estas tablas.

7 . Las siglas DES proceden de la denominación en inglés del cifrador, llamado Data Encryption Standard, por ser declarado el estándar para cifrado simétrico en Estados Unidos de 1977 a 1999. Su sucesor, el algoritmo AES (Advanced Encryption Standard), no utiliza una red de Feistel como base.

8 . Con gran tristeza, es obligado contradecir aquí a Lewis Carroll, quien, junto a otros muchos matemáticos, científicos y criptógrafos, utilizó el término cifrado indescifrable para referirse a Vigenère.

9 . Informalmente, elegir un elemento uniformemente al azar en un conjunto implica que todos los elementos del conjunto tengan la misma probabilidad de ser elegidos. Así, tirando una moneda perfecta al aire elegimos uniformemente al azar entre cara y cruz.

10 . Las ideas contenidas en este artículo estaban en gran parte inspiradas por el trabajo de Ralph Merkle, compañero en Standford de Diffie y Hellman y considerado también uno de los padres de la criptografía moderna.

11 . En este aspecto nos alejamos del símil de los candados y las llaves, pues dicha idea serviría para transportar una clave elegida por Alice hasta Bob (con lo que más le vale a Bob que Alice sea de fiar…).

12 . Decimos que un número entero p es primo si no podemos escribirlo como producto de otros dos enteros (salvo que uno de estos sea p · –p, pues obviamente p = 1 · p y también p = (-1) · (-p)). Son primos, por ejemplo, los siguientes números: 2, 3, 5, 7, 11, 13, 17, 19, 23.

13 . Habitualmente, llamaremos a K la clave, si bien rara vez va a usarse el elemento en cuestión “en crudo”, sin posprocesamiento.

14 . Existen también esquemas simétricos para firma digital (aunque siendo precisos, deberíamos hablar de construcciones para firma digital que usan herramientas simétricas).

15 . Este término es parte de la jerga criptográfica habitual, donde distinguimos entre usuarios HBC (honestos, pero curiosos) y usuarios maliciosos. Los primeros siguen la especificación del esquema, pero intentan sacar toda la información posible de los datos que manejan, mientras que los segundos pueden hacer, esencialmente, cualquier cosa (mientras nadie les pille).

16 . En inglés provable security; término que desafortunadamente se traduce a menudo como ‘seguridad provable’ (que es inquietantemente parecido a seguridad probable).

17 . Para ello, Rivest, Shamir y Adleman usaron el llamado pequeño teorema de Fermat, que dice que si p es primo y no divide a un entero a, ap-1 = 1 mod p.

18 . De hecho, así llamado con frecuencia en la literatura en inglés: textbook RSA.

19 . OAEP son las siglas de optimal asymmetric encryption padding, que (alocadamente) podemos traducir como ‘relleno óptimo para cifrado asimétrico’.

20 . La capacidad de los discos duros suele medirse en gigabytes. 1.024 gigabytes son un terabyte y 1.024 terabytes, un exabyte. Se estima que toda la información que circula por internet ocupa entre 100 y 300 exabytes.

21 . Si se le permite aceptar en este caso con una probabilidad no nula (aunque ha de ser muy pequeña), decimos que el IPS es probabilístico.

22 . Si llamamos α a la probabilidad de que Vera acepte en una ejecución aunque x no esté en S, α < ½ y tras k ejecuciones, dicha probabilidad es αk, que va disminuyendo rápidamente a medida que k aumenta.

23 . Dicha autora agradece el apoyo de sus padres para la realización del artículo.

24 . En la memoria de la cámara no puede haber ninguna otra imagen que contenga a Wally. Además, en aras de la paz doméstica, es importante que cada vez se permita sacar la foto a uno de los dos competidores.

25 . Lamentablemente, aunque este ejemplo aparece en numerosos textos de criptografía, no he podido identificar a la fuente original del mismo. De hecho, con frecuencia es citado como “folclore criptográfico”.

26 . A este dato adicional suele llamársele trampilla, traduciendo del inglés la palabra trapdoor.

27 . Salvo que uno tenga muy mala suerte y caiga en un producto de primos “especiales”.

28 . A menudo, ha sido necesario explicar vehementemente por qué un problema difícil a veces no es apropiado para criptografía. Un ejemplo paradigmático es el artículo “¿Por qué no puedes ni soñar con usar bases de Groebner para criptografía? Una carta abierta a un científico que fracasó y un reto para aquellos que aún no han fracasado”, publicado en el Journal of Symbolic Computations por B. Barkee et al. en 1994.

29 . Una permutación es una aplicación biyectiva, por lo que podemos entenderla como una ley que “reordena” el conjunto. Por ejemplo, una permutación de las letras de una palabra nos lleva a otra palabra que se construye exactamente con las mismas letras, pero en distinto orden (salvo si esta permutación es la identidad, que también es una aplicación biyectiva digna).

30 . Junto con el GDS (gusto desmedido por las siglas).

31 . “Hay muchas maneras de revelar tus secretos. Creo que un hombre decente que ha descubierto secretos valiosos tiene, en cierta medida, la obligación de compartirlos. Pero la técnica para esta compartición es digna de estudio. Y hay grandes maestros en el arte de dejar huella en los secretos que han descubierto. […] Ya sabes, se puede revelar un secreto de muchas maneras. Una es decir: este es el secreto que he descubierto. Creo que esa es la que suele tener menos éxito, pues cuando una mente creativa desvela información, la distorsiona y la vuelve muy inaccesible. A veces es solo por la voz, otras por el estilo del discurso, la longitud de un párrafo; a veces la huella queda en el tono, más que en el mensaje”.

32 . Esta condición se incluye en la definición de los llamados SSS perfectos. Si no perseguimos la “perfección”, se puede relajar.

33 . Como en capítulos anteriores, de nuevo se persigue buscar la máxima entropía en este tipo de selecciones.

34 . Siempre suponiendo que el dado o la moneda sean perfectos.

35 . De nuevo, persiguiendo alcanzar la máxima entropía posible en esta elección.

36 . Pues solo imponemos condiciones sobre filas y columnas, no sobre tablas interiores como habitualmente se hace en los sudokus.

37 . Para el caso del sudoku, el conjunto es {1, 2, ..., 9}, por tanto, N = 9.

38 . Llamados también, a veces, semihonestos y representados, como ya mencionamos, con las siglas HBC.

39 . Aunque hay esquemas, llamados verificables —VSSS—, en los que cada usuario puede verificar que el fragmento que recibe de un secreto es correcto (en un cierto sentido).

40 . Los “malos”, en realidad, también tienen nombre en la literatura criptográfica. La que espía un canal siempre es Eva (del inglés eavesdropper), la que hace análisis de tráfico de datos es Tracy. Curiosamente, la mayoría de los nombres que designan adversarios son femeninos.

41 . Referida de nuevo con siglas: en este caso MPC, del inglés multiparty computation.

42 . De hecho, en el fantástico artículo “Proving without knowing: On oblivious, agnostic and blindfolded provers” (publicado en los Proceedings de la conferencia internacional Crypto de 1996), hablan también del problema de los millonarios socialistas y extravagantes, variante en la que a uno de los millonarios no le importa revelar su fortuna pero al otro sí.

43 . Lin, H. Y. y Tzeng, W. G. (2005): “An Efficient Solution to the Millionaires’ Problem Based on Homomorphic Encryption”, Proceedings of Applied Cryptography and Network Security, vol. 3531, pp. 456-466.

44 . Y ya estamos filtrando algo: un valor que supera a ambas fortunas, ¿verdad?

45 . Listado extraído de las notas del curso “Special Topics in Cryptography” impartido en el MIT por Ran Canetti y Ron Rivest en 2004.

46 . Sí, sí; tu abuelo también.

47 . Extraído de Lipmaa, H. (2005): “Secure Electronic Voting Protocols”, Handbook of Information Security, John Wiley & Sons, Chinchester.

Federación Española de Sociedades de Profesores

de Matemáticas (FESPM)

Se constituyó en Sevilla en el año 1988 con la vocación de aunar los esfuerzos de cuantos trabajan por mejorar la educación matemática y a ella pueden adherirse todas aquellas asociaciones de profesores de Matemáticas que compartan los fines de esta Federación. Desde su creación y hasta la fecha, la federación ha seguido un proceso continuo de crecimiento, hasta llegar a estar formada en la actualidad por veinte sociedades.

La FESPM forma parte de la Federación Europea de Asociaciones de Profesores de Matemáticas (FEAPM) y de la Federación Iberoamericana de Sociedades de Educación Matemática (FISEM).

ICMAT

El ICMAT es un centro mixto del Consejo Superior de Investigaciones Científicas (CSIC) y tres universidades de Madrid: la Autónoma (UAM), Carlos III (UC3M) y Complutense (UCM). Su principal objetivo es el estímulo de la investigación matemática de alta calidad y de la investigación interdisciplinar. Es uno de los centros españoles del programa de excelencia Severo Ochoa, lo que acredita la alta calidad de su proyecto investigador. Además, sus investigadores han obtenido once de las prestigiosas ayudas del Consejo Europeo de Investigación (ERC), en las modalidades “Starting”, “Consolidator” y “Advancex”, y una Cátedra Permanente del AXA Research Fund.