miércoles, 18 de marzo de 2015

Estadística contra Criptografía II

Sigue la batalla: Kasiski contra Vigenère


En este artículo, continuación de "Estadística contra Criptografía - Matemáticas contra Matemáticas", veremos un ejemplo de desencriptación de un mensaje cifrado con el método Vigenère.

Raúl Ibáñez dedicó su colaboración del 3 de marzo en el programa de radio Euskadi La mecánica del caracol a seguir tratando el tema "mensajes cifrados y criptografía" incluyendo algunos ejemplos de métodos de cifrado de mensajes un poco más complejos que los de la primera entrega. Concretamente, habló del cifrado Alberti, primer método conocido de cifrado por sustitución que utilizó dos alfabetos. Y del cifrado Vigenère, más sofisticado, que pretende evitar el análisis de frecuencias manteniendo la sencillez del cifrado de Julio César.

Puedes escuchar el programa aquí. La participación de Raúl va desde el minuto 27:42 hasta el 50:12.
También es posible descargar el audio del programa completo aquí.

En la parte final del programa Raúl propuso como reto la desencriptación del siguiente mensaje:


LNU DVMUYR MUD VL LPXAFZ UEF AIOVWVMU OV MUEVMUEZCUD VS YW CIVCF GUCUNYC GALL GRCYTIJTRNNPJ QOP JE MZITYLIA YYKRY EFDUD CAM AVRMZEAM BLE XPJCCQIEH PJTY XVNMLAE ZTIMUOF RUFC


Descifrando el reto


Traicté des chiffres
Gallica - Bibliothèque nationale de France
Como ya indicamos en el artículo dedicado al anterior reto criptográfico, lo primero que hay que determinar para desencriptar un mensaje es el idioma original y el tipo de método de cifrado utilizado. Es razonable conjeturar que también en este segundo desafío el mensaje original está en castellano y el método de cifrado es alguno de los tratados por Raúl Ibáñez. La mayor parte del tiempo estuvo dedicada al cifrado Vigenère. Vamos a estudiar la posibilidad de que haya sido éste el método de cifrado utilizado.

El cifrado Vigenère debe su nombre a una atribución errónea a Blaise de Vigenère que en 1586 publicó "Traicté des chiffres ou secrètes manières d’escrire", en el que explica este método. En realidad el método fue descrito originalmente por Giovan Battista Belasso en su libro de 1553 "La cifra del Sig. Giovan Battista Belasso".

Para entender cómo funciona el sistema de cifrado Vigenère puedes consultar la explicación del propio Raúl Ibánez en el blog del programa.

¿Cuál es la fortaleza del sistema Vigenère? La misma letra se cifra de modo diferente para tratar de evitar el análisis de frecuencias. ¿De cuántas? Tantas como la longitud de la clave utilizada. Cuanto mayor se la longitud de la clave, mayor es la dificultad para desencriptar el mensaje.


Kasiski contra Vigenère

Traicté des chiffres - Pág 50
Gallica - Bibliothèque nationale de France
Pero su fortaleza es al mismo tiempo su mayor debilidad. Cada letra, y lo que es más importante, cada palabra no puede ser cifrada de más maneras distintas que la longitud de la clave utilizada. Por lo tanto, las palabras más frecuentes en el texto original aparecerán repetidas también en el texto cifrado, menos veces, pero es inevitable que aparezcan. Además en el texto cifrado, el número de caracteres que separan la misma forma de cifrar una palabra es un número exacto de veces, es decir, un múltiplo de la longitud de la clave. Ésta es la grieta de seguridad que permite realizar un ataque criptográfico al cifrado de Vigenère y la idea clave del método Kasiski, que debe su nombre al oficial prusiano Friedrich Kasiski que lo publicó en 1863.

Comencemos por un análisis de las cadenas que se repiten y su espaciamiento para determinar las longitudes de la clave más probables:
  • "UDV" se repite 2 veces (aparece 3 veces) separadas por 8 y 32 posiciones.
  • "MUE" se repite 1 vez separada por 4 posiciones.       
  • "MUO" se repite 1 vez separada por 108 posiciones.
  • "VMU" se repite 3 veces separadas por 24, 4 y 4 posiciones.
  • "VMUE" se repite 1 vez separada por 4 posiciones.
Los divisores comunes a todas las separaciones son: 2 y 4. Vamos a suponer que Raúl no ha usado una clave de 2 letras porque haría el reto demasiado fácil. Así que separamos el mensaje cifrado en 4 partes:


1.- Nos quedamos con las letras que ocupan las posiciones 1,5,9, ...

2.- Nos quedamos con las letras que ocupan las posiciones 2,6,10, ...

3.- Nos quedamos con las letras que ocupan las posiciones 3,7,11, ...

4.- Nos quedamos con las letras que ocupan las posiciones 4,8,12, ...


Ahora se trata de aplicar en cada una de las cuatro partes en las que ha quedado dividido el mensaje encriptado un análisis de frecuencias, como al tratar de romper el cifrado César, computando las veces que aparece cada carácter en el texto cifrado, calculando las correspondientes frecuencias relativas y teniendo en cuenta las frecuencias de aparición de letras en castellano. Las letras que más aparecen son, por este orden: E, A, O, S, ... Lo que nos lleva a conjeturar que la clave utilizada ha sido "RAUL".

Al descifrar el mensaje utilizando el método Vigenère con esta clave obtenemos como mensaje original:

una semana mas el regalo del problema de matematicas es el libro gardner para principiantes que se sorteara entre todas las personas que descifren este mensaje firmado raul

Muy en la línea de la autoreferencia y de dar facilidades, como en el anterior programa. La última palabra de 4 letras ayuda bastante.

Descifrado "asistido"

Es fácil encontrar en internet herramientas que facilitan en gran medida el proceso de desencriptado de este tipo de mensajes, como por ejemplo The_Black_Chamber Vigenère Cracking Tool.

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 Kasiski de ataque al cifrado Vigenère. 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.

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.

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 ;-)