El sistema perfecto de criptografía, o al menos eso dice su inventor

Por Arturo Quirantes, el 20 enero, 2013. Categoría(s): Ingeniería • Tecnología

Hace unos días leí una noticia que, de ser cierta, supondría una revolución en el campo de las comunicaciones. Un físico valenciano llamado Vicent Martínez Sancho ha patentado lo que parece ser un sistema criptográfico indescifrable. La noticia se ha publicado en diversos medios, pero la mayoría se limita a reproducir la misma nota de prensa de EFE (El Mundo, ABC, La Información). El periodista de El País se lo ha currado un poco más, pero tampoco da demasiados detalles. Lo único que puedo hacer es leerse las 41 páginas de la patente, y a partir de ahí intentar sacar algo. Confieso que cuando le eché el primer vistazo terminé desistiendo (tenía una película de Godzilla pendiente). Sin embargo, cada vez veo más noticias al respecto, la gente pregunta, y claro ¿qué puede hacer este que firma? Pues meterse en el fregado.

Quede claro de partida que yo no soy un criptólogo profesional. Al igual que el señor Martínez, yo también soy profesor de Física (él en Valencia, yo en Granada), y ambos somos aficionados a la criptografía. Sé de lo que es capaz un físico versátil (en efecto, no tenemos abuela). Con todo, una de las primeras cosas que aprende un aficionado al tema es que es muy fácil diseñar un sistema criptográfico que uno mismo sea incapaz de descifrar … lo que no significa que sea indescifrable. Crear un criptosistema sólido y a prueba de atacantes es una labor terriblemente difícil, y es un campo en el que incluso los mejores han fallado.

Así que una de dos: o el profesor Martínez es un absoluto genio en el campo, o ha caído en la misma trampa que muchos antes de ellos. Ya hay debates abiertos en la excelente web de Kriptópolis (aquí y aquí), pero incluso sin meternos en detalles técnicos un examen de la patente muestra, al menos en mi opinión, que hay mucho ruido y pocas nueces. Comencemos.

Lo primero que advierto conforme leo es que quien escribe no parece estar muy ducho en criptografía, incluso para ser un aficionado. Hay fallos, errores y malas interpretaciones tan sólo en la descripción previa que efectúa de la criptografía en general. Por ejemplo, afirma que el cifrado asimétrico (o de clave pública) puede romperse mediante fuerza bruta. Eso no es del todo cierto. La “fuerza bruta” es la forma que tienen los criptólogos de decir “probemos todas las claves.” En el caso de los sistemas de clave pública, la forma de atacarlos suele pasar por intentar resolver el problema matemático en que basan su seguridad. En particular, el sistema RSA se basa en la dificultad de factorizar grandes números primos. Pero nadie intenta reventar un sistema de clave pública probando todas las claves posibles. Es precisamente en los sistemas de cifra simétrica en los que este procedimiento es factible.

También me sorprendió leer en la patente que “DES es uno de los lenguajes más solventes.” DES es un sistema de clave simétrica (no un “lenguaje”), y se considera obsoleto por la corta longitud de su clave. Su afirmación de que “un ordenador probando un millón de claves por segundo tardaría más de 2.200 años en obtener la clave correcta” pudo ser válida en los años noventa, pero ahora hay sistemas muchísimos más rápidos. Hay otros algoritmos más usados en la actualidad (como AES, el estándar federal USA), ¿por qué no los menciona? Y por cierto, DES no utiliza claves de 128 bits, como afirma en un párrafo de la patente. Pero no quiero criticar los detalles, eso es tan sólo anecdótico.

Un problema más gordo radica en lo que el profesor Martínez denomina Criptograma Seguro de Shannon. No existe ese término en el artículo clásico de Shannon (Communication Theory of Secrecy Sistems” 1949), pero sí aparece un concepto llamado “secreto perfecto” (Perfect Secrecy) que es el que Martínez describe. Básicamente, viene a decir que un sistema se puede considerar de secreto perfecto si el enemigo, al capturar un mensaje cifrado, no aprende absolutamente nada sobre el mensaje original. Bien hasta aquí. Martínez también afirma que, según Shannon, una condición para la existencia de secreto perfecto es que el número de posibles clave sea superior al de posibles mensajes, suponiendo que el número de mensajes es finito. De acuerdo también con esto.

El problema en esto es que Martínez salta sin red al afirmar que “si consideramos todos los textos claros [llanos, es decir, sin cifrar] de un determinado idioma hemos de concluir que dicho número es infinito.”

Eso me parece una temeridad. Siete mil millones de personas pueden crear un gran número de mensajes, pero incluso si reclutásemos monos, políticos, banqueros, incluso si movilizásemos todos nuestros recursos informáticos, el número de mensajes que podríamos generar sería necesariamente finito. Enorme, pero finito.

Seamos generosos y admitamos que, al menos en teoría, el número posible de mensajes sea infinito, lo que implica que necesitaríamos un conjunto de claves infinitamente grande para garantizar el secreto perfecto. Según esa descripción, los criptosistemas de clave pública (concretamente, los que usan números primos) son del tipo “infinitas claves” porque los números primos son infinitos en cantidad. Martínez lo acepta, pero dice que en la práctica eso no sirve porque “tenemos el inconveniente insuperable de que no podemos generar números primos mediante una expresión matemática.” Creo que este profesor no conoce los tests de primalidad, que nos permite comprobar si un número natural, cualquiera sea su longitud, es primo o no. Noto aquí una cierta confusión en su deseo de demostrar que los criptosistemas de clave pública no son aceptables. En cuanto a los criptosistemas de clave simétrica, Martínez acepta como a regañadientes su eficacia, pero no los considera del tipo “secreto perfecto” porque el número de posibles claves que utilizan es finito. Técnicamente de acuerdo.

Como digo, no quiero quedarme en menudencias, así que vamos a ver en qué consise el criptosistema Martínez. Si se trata de un algoritmo de cifrado criptoanalíticamente sólido y su espacio de claves es muy grande, tendremos algo potable. Tendrá una ardua labor por delante, ya que hay muchos tipos de técnicas criptoanalíticas (como el criptoanálisis lineal o diferencial, por nombrar dos) que permiten reducir la seguridad de la cifra, y en segundo lugar ha despreciado sistemas como AES por tener claves finitas, así que si 2^256 claves le parecen pocas deberá darnos gran cantidad de posibles claves ¿lo consigue?

Veámoslo. Para evitar ataques criptoanalíticos, Martínez aboga por una gran novedad. A lo largo de la Historia, desde Julio César hasta los ordenadores digitales, se han utilizados, solos o en combinación, dos formas principales de cifrado: cambiar unos signos por otros (sustitución) o bien reordenarlos (transposición). He aquí un ejemplo de transposición. Digamos que queremos cifrar la expresión CRIPTOGRAFIA PERFECTA. Voy a escribirla en fila a fila:

C R I P T

O G R A F

I A P E R

F E C T A

Ahora lo que hago es leer por columnas, y obtengo la frase cifrada COIF RGAE IRPC PAET TFRA. Y ahora un ejemplo de sustitución. Voy a cambiar cada letra por la que se encuentra tres posiciones a la derecha en el alfabeto. Es decir, la A se convierte en D, la B en E y así sucesivamente. En ese caso, CRIPTOGRAFIA PERFECTA se convierte en FULSWRJDILD SHUIHFWD. Y por supuesto, puedo combinar ambos métodos. Eso es lo que, de una forma u otra, hacen los sistemas criptográficos de clave simétrica modernos.

Bien, pues lo que el profesor Martínez afirma haber descubierto, tras dos mil años de historia de la criptografía, es una tercera forma de ofuscar información. Además de la transposición y la sustitución, él propone una técnica llamada transformación. Esta nueva técnica está basad en algo que llama “Teorema de los Residuos,” un nombre que llama a confusión porque ya existe un Teorema de los Residuos en el campo del análisis complejo, y no tiene nada que ver con esto. La ventaja de esta nueva “criptografía de residuos” es que permite obtener un número de claves infinito, lo que haría que su criptosistema cumpliese la condición de secreto perfecto de Shannon.

La verdad, esto último resulta algo sorprendente: nada menos que un sistema criptográfico de clave simétrica con un número infinito de claves. No grande, no enorme, no gigantesco, sino infinito. Y sin embargo, necesariamente debemos partir de una clave muy grande pero finita. ¿Cómo conseguimos una cantidad infinita de claves de longitud infinita?

Mediante los residuos, dice el autor, quien llama “residuo” a un número natural entre el 1 y el 9. A partir de ahí, construye una “matriz de residuos” como cualquier ordenación de residuos, pares de residuos, tríos de residuos, etc. Si lo he leído bien, lo que nos está describiendo no es sino la numeración en base 10. Cada “elemento de la matriz de residuos numéricos de orden n” es simplemente un número decimal con n dígitos.

Cuando lo leí puse cara de WTF, pero seguí leyendo. Habrá más, me dije. Y ciertamente lo hay. Entra en acción la primera de las dos claves del sistema Martínez, la llamada Clave de Equivalencia. Dice el autor que esa clave va a reordenar la matriz de residuos y la convertirá en una matriz de residuos reordenada. Pero resulta que la reordenación consiste, sencillamente, en permutar filas. Y ahora voy a decirlo lento y claro para que no haya confusión alguna: permutar filas en una matriz es reordenar. ¡La famosa “transformación” no es más que un método de transposición! Y de lo más burdo, además. No necesito echar mano a ningún libro de historia de la criptografía para saber que el método de transformación tiene siglos de antigüedad.

Es en este punto donde Martínez comete un error no ya de novato, sino de ignorante. Afirma que, con una matriz de “residuos” ternarios (es decir, números de tres dígitos), el número de posibles posibles ordenaciones es de 729!, un número de casi dos mil cifras. No voy a discutir sus cálculos, porque el fallo consiste en hacer la suposición de que, puesto que hay muchísimas claves posibles, el sistema es seguro.

¡Error! Un criptosistema con muchas claves es solamente seguro si está bien diseñado. Por ejemplo, supongamos un sistema que cambie las letras del alfabeto según esta secuencia:

abcdefghijklmnopqrstuvxyzñ

XÑUTVZHKEADORYMCILJBOFQGNS

Para cifrar, basta con tomar la letra del texto llano (fila superior) y sustituirla por la letra correspondiente de texto cifrado (fila inferior).  De ese modo, la palabra zodiac se convierte en NMTEXU. Este sistema se denomina cifra de sustitución monoalfabética, y tiene un total de 27! posibilidades. Eso son más de diez mil cuatrillones. Sin embargo, la sustitución monoalfabética es de lo más inseguro, ya que preserva la estructura del texto llano. La debilidad de este sistema se conoce desde hace casi seiscientos años, y sólo un tonto se dejará engañar. Si quieren más detalles, les recomiendo mi libro sobre criptografía, pero baste aquí si les digo que se trata de un sistema con muchas, muchas claves, y no por eso deja de ser más débil que una jaula de cartón.

En nuestro caso, el inventor ha caído en la trampa de crear un sistema con un número inmenso de claves, y deducir de algún modo que su sistema es seguro, sin hacer el menor estudio sobre la fortaleza del sistema. Nada de utilizar sistemas de criptoanálisis, o analizar la entropía, y según parece ya se han encontrado debilidades claras. Por añadidura, queda el detalle de que el número de claves es grande pero no infinito, con lo que la pretensión de que el método Martínez cumple la condición de secreto perfecto se queda en agua de borrajas.

Para terminar, el criptosistema del profesor Martínez es de lo más ineficaz. Las trasposiciones y sustituciones parecen hechas sin pensar en la velocidad de cifrado, el número de operaciones matemáticas o la eficacia en general. Después de criticar los sistemas de clave pública por ser muy lentos y exigir claves muy largas, el autor incluye el cifrado de la frase “la reunión es mañana jueves” siguiendo su novedoso método. ¿Saben cuál es el resultado? Una ristra de 462 dígitos. ¡Cuatrocientos veintiséis dígitos para cifrar una frase de veintisiete letras, incluidos los espacios! Shannon debe estar revolviéndose en su tumba.

Uno de mis hobbies es el estudio de la historia de la criptografía, y he visto demasiados ejemplos de sistemas criptográficos malos diseñados por aficionados. Hace algunos años, los chicos de la Oficina Española de Patentes y Marcas tuvieron la amabilidad de abrirme las puertas y mostrarme todas las patentes antiguas sobre sistemas de cifrado. Algunos, como la máquina Enigma, resultaron ser vulnerables pero brillantes; otros eran sencillamente vulnerables, cuando no una completa estupidez. Recuerdo una que consistía en poco más que cambiar las letras de orden en una máquina de escribir, y el inventor se creía que había descubierto la pólvora. Es evidente a mis ojos que el profesor Martínez va por el mismo camino, y mira que lo lamento porque es colega tanto de profesión como de afición. Sospecho que la noticia ha sido poco más que un anuncio en plan relaciones públicas con el único fin de conseguir publicidad gratuita.

La verdad, estoy decepcionado. Menos mal que me queda Godzilla. Ese nunca me falla.



Por Arturo Quirantes, publicado el 20 enero, 2013
Categoría(s): Ingeniería • Tecnología