miércoles, 4 de marzo de 2015

Estadística contra Criptografía

Matemáticas contra Matemáticas


Un mensaje cifrado siempre tiene un atractivo poderoso que hace difícil sustraerse a la tentación de intentar descifrarlo. Lo misterioso es muy sexy.


Raúl Ibáñez es profesor de Geometría y Topología en la Universidad del País Vasco y uno de los más importantes divulgadores de las Matemáticas en castellano. Descubierto recientemente por el público no especialista por sus aportaciones matemáticas al programa de divulgación científica Órbita Laika que emite TVE2 y que son muy recomendables, por cierto.

Hace unos días Raúl publicó en su cuenta de Twitter, como reto matemático, un tweet con el siguiente mensaje cifrado:

UOGRBSG EOGO EGWBQWEWOBISH SH SZ GSUOZD RSZ EGDPZSAO RS SHIO HSAOBO, FJS QDBHWHIS SB RSHQWTGOG SHIS ASBHOXS. TWGAORD GOJZ.

Lo primero que se me ocurrió, como es propio de nuestra "era Google", fue tratar de encontrar en internet el mensaje sin cifrar, dando por supuesto que alguien ya lo habría descifrado y publicado. Afortunadamente no fue así, no encontré la versión desencriptada. Sin embargo, sí que hallé un artículo haciendo referencia al mensaje en el blog Ciencia al pil pil. Se trata del blog del programa de radio Euskadi La mecánica del caracol, dedicado a la divulgación de la ciencia, la tecnología y la historia, en el que Raúl Ibáñez colabora cada dos martes.

En el programa del pasado 17 de febrero Raúl habló sobre "mensajes cifrados y criptografía" dejando como reto la desencriptación del mencionado mensaje. Puedes escuchar el programa aquí. La participación de Raúl va desde el minuto 27:35 hasta el 49:37. También es posible descargar el audio del programa completo aquí.


Matemáticas, codificación y cifrado de información


Entre las funciones de las Matemáticas, además de ordenar y contar, y de medir, está la de codificar, que tiene cada vez mayor importancia en nuestra sociedad.


Codificar una información es transformarla mediante una serie de signos y reglas de forma que pueda ser transmitida, almacenada o analizada. Decodificar sería el proceso inverso y complementario del anterior por el cual la señal codificada es transformada en la información original. Codificar una información no implica voluntad de protegerla, impidiendo accesos no autorizados a la misma.

La Criptografía es un área, inicialmente de las Matemáticas y en la actualidad también de la Informática y la Telemática, que hace uso de métodos y técnicas con el objeto principal de proteger un mensaje o archivo por medio de un algoritmo, usando una o más claves. Con ello se consigue asegurar las condiciones básicas de la seguridad de la información: confidencialidad: la información solo es accesible para quien esté autorizado; integridad: la información no sufrió modificaciones después de su emisión; autenticidad del emisor: el receptor identifica al emisor y está seguro de que no ha sido suplantado; no repudio: es imposible para el emisor y el receptor negar su participación en el intercambio de información porque quedan evidencias.

El hecho de codificar un mensaje para que sea secreto se llama cifrado. El método inverso, que consiste en recuperar el mensaje original, se llama descifrado.

El Criptoanálisis, es la técnica de descifrar textos cifrados sin tener autorización para ello. Criptografía y Criptoanálisis forman la ciencia llamada Criptología.

En la actualidad las Matemáticas juegan un papel fundamental en el diseño de los complejos sistemas que garantizan la integridad y confidencialidad de la información y las comunicaciones.


Descifrando el reto


Lo primero que hay que determinar para desencriptar un mensaje es el idioma original y el tipo de método de cifrado utilizado. Considerando que en este caso es un desafío planteado para que con un poco de pericia y esfuerzo sea posible su solución, hay que conjeturar que el mensaje original está en castellano y que el método no debe ser muy complicado y que muy posiblemente sea alguno de los mencionados por Raúl Ibáñez en el programa. Los espacios y signos de puntuación hacen pensar que Raúl no quiere ponerlo muy difícil y llevan a la hipótesis de trabajo de que el mensaje ha sido cifrado usando un método de sustitución simple, en el que cada letra del alfabeto ha sido reemplazada por otra letra.


Ánálisis de frecuencias: Estadística contra Criptografía.


1.- Comenzamos el análisis de frecuencias computando las veces que aparece cada carácter en el texto cifrado y calculando las correspondientes frecuencias relativas. Para ello podemos utilizar alguna herramienta online como ésta de Richard Knights.


Posteriormente comparamos las frecuencias obtenidas con las frecuencias de aparición de letras en castellano. Tomamos como referencia la tabla de frecuencias que aparece en la Wikipedia.

La siguiente tabla muestra el resultado obtenido:


Frecuencia de aparición de letras en el texto cifrado
Letra S O G H B W R Z A D E I Q J T U F P X C K L M N V Y Ñ
Nº veces 18 13 10 9 7 6 5 5 4 4 4 4 3 2 2 2 1 1 1 0 0 0 0 0 0 0 0
Frec. (%) 17.8 12.9 9.9 8.9 6.9 5.9 5.0 5.0 4.0 4.0 4.0 4.0 3.0 2.0 2.0 2.0 1.0 1.0 1.0 0 0 0 0 0 0 0 0
Frecuencia de aparición de letras en Castellano
Letra E A O S R N I D L C T U M P B G V Y Q H F Z J Ñ X W K
Frec. (%) 13,7 12,5 8,7 8,0 6,9 6,7 6,3 5,9 5,0 4,7 4,6 3,9 3,2 2,5 1,4 1,0 0,9 0,9 0,9 0,7 0,7 0,5 0,4 0,3 0,2 0,0 0,0

Las frecuencias son más precisas cuanto más extenso es el texto cifrado. En el caso que nos ocupa no lo es mucho y por lo tanto debemos ir avanzando paso a paso.

En adelante escribiremos en mayúsculas el texto cifrado y en minúsculas el texto sin cifrar.

2.- En un primer vistazo a los resultados del análisis de frecuencias deducimos que muy probablemente S=e y O=a. Con ello tendríamos:


UaGRBeG EaGa EGWBQWEWaBIeH eH eZ GeUaZD ReZ EGDPZeAa Re eHIa HeAaBa, FJe QDBHWHIe eB ReHQWTGaG eHIe AeBHaXe. TWGAaRD GaJZ.


3.- Las palabras eH, eZ, ReZ, Re, eB que son candidatas a artículos y conjunciones, nos llevan a pensar que la Z se corresponden con una l, n o s. Y lo mismo pasa con la B y la H. Además ReZ y Re apunta la correspondencia R=d. Después de alguna prueba nos decantamos por la correspondencia R=d y Z=l, con lo que tenemos:

UaGdBeG EaGa EGWBQWEWaBIeH eH el GeUalD del EGDPleAa de eHIa HeAaBa, FJe QDBHWHIe eB deHQWTGaG eHIe AeBHaXe. TWGAadD GaJl.


4.- Las palabras eHIa, eHIa, eH junto con lo apuntado en el punto 3 de que H se debe corresponder con la n o con la s, nos llevan a H=s. Quedando:

UaGdBeG EaGa EGWBQWEWaBIes es el GeUalD del EGDPleAa de esIa seAaBa, FJe QDBsWsIe eB desQWTGaG esIe AeBsaXe. TWGAadD GaJl.


5.- Las palabras esIa, esIe sugieren la correspondencia I=t. Lo que hace:

UaGdBeG EaGa EGWBQWEWaBtes es el GeUalD del EGDPleAa de esta seAaBa, FJe QDBsWste eB desQWTGaG este AeBsaXe. TWGAadD GaJl.


6.- Por lo apuntado en el punto 3 nos queda B se debe corresponder con n. Quedando:

UaGdneG EaGa EGWnQWEWantes es el GeUalD del EGDPleAa de esta seAana, FJe QDnsWste en desQWTGaG este AensaXe. TWGAadD GaJl.


7.- seAana sugiere la correspondencia A=m, con lo que tenemos:

UaGdneG EaGa EGWnQWEWantes es el GeUalD del EGDPlema de esta semana, FJe QDnsWste en desQWTGaG este mensaXe. TWGmadD GaJl.


8.- FJe sugiere las correspondencias F=q y J=u, quedando:

UaGdneG EaGa EGWnQWEWantes es el GeUalD del EGDPlema de esta semana, que QDnsWste en desQWTGaG este mensaXe. TWGmadD Gaul.


9.- Volviendo a los datos de las frecuencias tenemos como probable G=o ó G=r. Tras descartar la primera y sustituir G=r nos queda:

Uardner Eara ErWnQWEWantes es el reUalD del ErDPlema de esta semana, que QDnsWste en desQWTrar este mensaXe. TWrmadD raul.


10.- Eara y ErDPlema sugieren E=p, quedando:

Uardner para prWnQWpWantes es el reUalD del prDPlema de esta semana, que QDnsWste en desQWTrar este mensaXe. TWrmadD raul.


El texto ya parece algo claro, más si tenemos en cuenta que se trata de un mensaje autoreferente. Su contenido alude al regalo por descifrarlo. Una buena broma ;-)

Con un poco más de esfuerzo y tras algunas pruebas llegamos a descifrar el mensaje:

Gardner para principiantes es el regalo del problema de esta semana, que consiste en descifrar este mensaje. Firmado Raúl.


Cifrado César

Después de las tres primeras sustituciones que hemos hecho en el proceso de descifrado, la correspondencia entre los alfabetos utilizados para el mensaje encriptado y el mensaje sin cifrar es:

Cifrado* A B C D E F G H I J K L M N Ñ O P Q R S T U V W X Y Z
Original*














a

de







Ello podía habernos hecho plantearnos en algún momento la posibilidad de que Raúl en su afán por facilitar la solución, al encriptar hubiera hecho corresponde la a con la O, la b con la P y hubiera seguido con esa traslación del alfabeto, como finalmente hemos comprobado que ha sucedido. Lo cual nos habría llevado a desencriptar el mensaje mucho más rápidamente.

Cifrado César con desplazamiento + 15  ( a => O )
Cifrado* A B C D E F G H I J K L M N Ñ O P Q R S T U V W X Y Z
Original* mnñopqrstuvwxyzabcdefgh
ijk l
* En negrita aparecen las letras usadas en el mensaje

Podemos apreciar que se trata de una encriptación basada en un cifrado César con desplazamiento +15.


Descifrado "asistido"

No lleva mucho tiempo encontrar en internet herramientas que facilitan en gran medida el proceso de desencriptado de este tipo de mensajes, como por ejemplo The_Black_Chamber Substitution Cracking Tool o Cryptogram solver de Rumkin.

Es nuestra decisión utilizarlas o no, pero claramente usarlas no es lo mejor que podemos hacer si lo que queremos es entender cómo funciona la técnica de análisis de frecuencias. Además hay que considerar los placeres de pasar un buen rato ejercitando nuestra mente, de enfrentarse a un reto, y a veces ... vencerlo.


La facilidad con que se descifra este tipo de criptografía, de la que hemos visto un ejemplo, hace que no sea utilizada desde hace mucho tiempo cuando son necesarias unas comunicaciones realmente seguras. Sin embargo fue un sistema considerado seguro durante muchos siglos hasta que se recurrió a los métodos estadísticos del análisis de frecuencias.


Para saber más:

Simon Singh: http://simonsingh.net/cryptography/
Información y utilidades criptográficas en el sitio web de Simon Singh.

The_Black_Chamber: http://www.simonsingh.net/The_Black_Chamber
Sitio de Simon Singh, donde se puede aprender criptografía y criptoanálisis, y practicar con herramientas interactivas de cifrado.

CrypTool: https://www.cryptool.org
Sitio web dedicado a la divulgación de la criptografía y el criptoanálisis. "CrypTool" es un software libre que ilustra conceptos criptográficos muy usado en entornos formativos. El sitio ofrece gran cantidad de material didáctico e incluye el proyecto CrypTool-Online: http://www.cryptool-online.org

Joan Gómez. "Matemáticos, espías y piratas informáticos. Codificación y criptografía". RBA Libros. Barcelona 2010.


P.D.: "Estadística contra Criptografía II - Sigue la batalla: Kasiski contra Vigenère" es la continuación de este artículo con un ejemplo de desencriptación de un mensaje cifrado con el método Vigenère.

30 ;-)

No hay comentarios:

Publicar un comentario