Criptografía por Transposiciones Geometricas

Criptografía por Transposiciones Geométricas.
--

Buen día.

Siguiendo nuestra metodología anteriormente planteada, vamos a estudiar un concepto y posteriormente vamos a desarrollar una tool, con el cual podamos simular el funcionamiento del mismo. Hoy vamos a estudiar la criptografía basada en Transposiciones Geométricas y no se asusten, el tigre no es como lo pintan :).

Cuando hablamos de criptografía por transposición, hacemos referencia al hecho de que tanto, antes de iniciar el cifrado, como después de aplicarlo vamos a tener los mismos caracteres o el mismo contenido, pero con diferente orden o simetría. Para explicarlo un poco mejor, veamos:

Si examinamos un poco más de cerca ambos resultados, podemos observar que en ambos textos (plano y cifrado) se encuentran exactamente las mismas letras o caracteres, lo que quiere decir que solo hubo un cambio de posición pero no un cambio o sustitución de letras.

Ahora que lo vemos de esta manera, podemos notar que en realidad el único cambio que hubo en el texto plano, fue invertir la cadena (abcd -> dcba). Por esta razón simplemente hubo un cambio en la posición de los caracteres, pero no un cambio de caracteres como tal. (todos los caracteres quedaron intactos excepto su posición y orden).

Y esto es de forma general, cuando nos referimos a cualquier cifrado de transposición siempre debemos tener en cuenta que los caracteres se conservan, y que solamente hubo una traslación o un cambio en el orden de los mismo. Este tipo de cambio de posición generalmente es regido de manera lógica y repetitiva; en el ejemplo anterior invertimos cada letra del texto en claro, pero también pudimos haber organizado primero las letras que estuviesen en posiciones pares y después las que estuviesen en posiciones impares.


TRANSPOSICIONES GEOMÉTRICAS:

Pero ¿A qué nos referimos con Transposiciones Geométricas?. Bueno, en principio por la palabra "Transposición" sabemos que todos los caracteres originales se van a conservar y que solamente sufrirán un cambio en su posición u orden, pero ahora, ¿Geométricas?,  pues esto es lo interesante del tema, ese cambio de posición u orden que tendrá nuestro texto plano, va a seguir el funcionamiento de una figura geométrica, y para eso vamos a ver varios ejemplos de esto, entre las figuras que utilizaremos estaŕan el cuadrado, el rectángulo, el triangulo y algunas un poco particulares como la espiral.

Vamos a representar primero una transposición geométrica cuadrada, para este caso, ordenaremos nuestro texto claro de tal forma que quedé en una tabla de tamaño NxN pues debe ser cuadrada.

Texto claro: TrackMazeHackingGroup

Ahora tenemos una tabla de tamaño NxN (5x5) donde esta contenido todo el mensaje que queremos cifrar, pero hay algo raro en esto :( , nos sobran 4 cuadritos sin letras, pues el mensaje no cubre toda la tabla. Para estos casos es casi "convención", rellenar los cuadros faltantes con "X".

Espacios completados con "X"

-¿Sí lo ven? tiene forma cuadrada!!! ...
-Wiiiiiiiii!!!!...
-¿pero donde está la transposición? ¬_¬''

Buena pregunta, pues ese es precisamente el siguiente paso que vamos a dar; como pueden ver, nosotros organizamos todo el mensaje de forma horizontal osea por filas, entonces una manera de cifrar este mensaje, es volver a leer toda la tabla que acabamos de hacer, pero la leeremos de forma vertical osea por columnas.

El texto en claro y el texto cifrado quedará así:

Texto Claro y Texto Cifrado

Cada espacio en el texto cifrado significa que hemos cambiado de columna, y bien hacen en verificarlo por ustedes mismos. También sería conveniente que verificaran que a pesar de todo lo que hemos hecho, los caracteres del texto original, aun se mantienen en el texto cifrado, a excepción de las "X" que se agregaron; hago énfasis en esto, para que vean que se cumple la definición inicial de transposición.

Veamos algo curioso, si colocamos de nuevo el mensaje cifrado en forma de filas, miren lo que obtenemos.

Obtendremos el texto claro en forma de columnas (O.O)... y así es como ciframos y desciframos.

Notas Mentales:

1. Aunque en principio colocamos el mensaje en forma horizontal (por filas) en la tabla, también pudimos haberlo colocado en forma vertical (por columnas) y al momento de cifrarlo, tendríamos que leerlo en forma horizontal (por filas).
2. Si acomodamos el texto horizontal (por filas), para poderlo cifrar lo leemos en forma vertical (por columnas) y también aplica en sentido contrario, si lo acomodamos en forma vertical (por columnas), para poderlo cifrar lo leemos en forma horizontal (por filas).
3. Ocurre exactamente lo mismo para los rectángulos, solamente que ahora nuestra tabla no será de tamaño NxN sino de NxM. Pero el principio es el mismo, tanto para cifrar como para descifrar. 
4. Es importante tener en cuenta, que el mensaje a cifrar por este procedimiento no debe contener espacios (" "), es por esto que el mensaje se pega todo, eliminando los espacios. 

Ahora que ya hemos dominado al cuadrado y el rectángulo, es hora de dominar al triangulo!!!.. this is sparta!!!..

Texto claro: TrackMazeHackingGroup

Creo que ahora ya vemos el triangulo (pirámide) del cual hablábamos, pero dentro del mismo se encuentra nuestro texto en claro y como podrán observar, también tenemos varias "XXXX" pues el texto no era lo suficientemente largo para poder terminar la base de la pirámide, así que tenemos que "machetearlo" un poco, agregándole las "X".

Forma en que se acomoda el texto claro

La manera para cifrarlo, es leyendo la pirámide por las columnas, de esta manera:

Leyendo por Columnas

Y nuestro mensaje cifrado quedaría así: G HR KAO RMCU TAAKP CZIX ENX GX X

Por aquí les dejo este pequeño script en Python, el cual les dirá qué tamaño debe tener la tabla (matriz) para que el mensaje ocupe toda la pirámide; y también les dirá la cantidad máxima de caracteres que estarán dentro, según el tamaño de la tabla.

for x in range(1,100):
    print "Tamano ",x,"x",x+(x-1)," Para un maximo de ",x*x," caracteres"


y es importante recordar (de nuevo xD) que si su mensaje no cumple con el tamaño requerido, se le pueden agregar "X" para completarlo.

----
Hasta aquí espero que hayan entendido todo lo que he mencionado, pues ahora vamos a pasar a un tema un poco más "complicado" y en el cual haremos uso de todo lo que ya hemos dicho.
----

ADICIONANDO UNA CLAVE PARA EL CIFRADO:

Cuando miramos las transposiciones geométricas (cuadradas y rectangulares), nos dimos cuenta de que era realmente sencillo descifrar el texto cifrado, y así volver a obtener el texto en claro lo cual lo hace un cifrado muy inseguro :( ... pero para mitigar este hecho, a alguien se le ocurrió la utilización de una clave numérica, con la cual se pudiera cifrar y sin la cual no se pudiera descifrar.

Tabla y Clave Numérica

En realidad el uso de la clave es algo muy intuitivo; si recuerdan un poco, nosotros después de organizar la tabla en forma horizontal (por filas) para poder cifrar el texto teníamos que leer la tabla de forma vertical (por columnas), pues esto es básicamente lo mismo, solo que nuestra clave numérica nos especifica el orden de lectura de las columnas. En este caso vamos a empezar leyendo la que tiene el 1, después 2, después 3, 4, hasta que acabemos con todas (5).

Empezamos con la 1

Quedando así:

Texto Claro | Clave | Texto Cifrado

y para poderla descifrar, tenemos que llevar las columnas a su orden inicial y correcto. En este caso nuestra clave numérica no solo especifica el orden de las columnas, sino también la cantidad de las mismas... El sistema de clave para N columnas funciona como una permutación normal, por consiguiente, vamos a tener N! (N factorial) posibles claves para una tabla de N columnas. Y esto tiene un significado en cuanto a seguridad.


¿Es seguro este cifrado? ¿Es segura mi clave?

Juzguen ustedes, si tenemos N! (N factorial) posibles claves todo dependerá de la cantidad de columnas (N) que utilicemos al momento de cifrar, pues un ataque a fuerza bruta aumenta en forma exponencial, como lo podemos observar en la siguiente tabla:

http://es.wikipedia.org/wiki/Factorial

Para nuestros computadores modernos y comerciales, un ataque hasta 10! es un ataque que puede ser realizado en Hmmmm.. 5 minutos como mucho, pero un ataque a 15! no solo requiere muchísimo más tiempo, sino también la debida adecuación de nuestro computador, pues para procesos tan largos, nuestros sistemas operativos cierran o detienen dicho proceso. Aunque en esencia, un ataque a 15! es básicamente una locura :) ..


Notas Mentales: 

1. Hmmm.. La seguridad de nuestro cifrado depende de manera contundente de la cantidad N de columnas, lo que es igual a decir, de la longitud de nuestra clave. 
2. Un ataque a fuerza bruta puede demorarse mucho o quizás muy poco, todo depende de la clave, pues generalmente el ataque es secuencial y va a encontrar primero a la clave 123456 que a la clave 654321, por ende no es fijo el hecho de encontrarla de inmediato o después de un largo tiempo. 
3. Soy guapo y sexy :) ... 

  


ES HORA DE PROGRAMAR... (Python):
-----
Para esta parte vamos a utilizar conceptos de matrices, array bidimensionales o listas bidimensionales, no los hemos tratado en un post concreto pero recomiendo la lectura de un post anterior, donde hacemos una breve introducción al mismo. Aquí
-----

Como nuestra meta es la construcción de una Tool donde estén todas o más opciones de las que ya hemos mencionado, entonces vamos a ir programando las funciones que necesitaremos.

0) Tenemos que dar la posibilidad de ingresar el tamaño N de las columnas.
1) Necesitamos que el mensaje a cifrar se convierta en una matriz
2) Necesitamos que después de tener la matriz creada, la podamos leer por columnas o por filas
3) Necesitamos leer la matriz de una forma determinada por la clave.

Ya que tenemos los propósitos que vamos a lograr, es momento de empezar y pues en el camino iremos detallando las cosas.




1) Convertir el mensaje en una Matriz:

Como lo definimos en el punto 0, será el usuario quien defina la cantidad de columnas que desea y lo denotaremos con la variable (columnas), debemos tener esto muy presente.

Crearemos nuestra función llamada create_matriz, y que recibirá  como parámetros, el texto en claro (mensaje) y la cantidad de columnas que desea (columnas):

def create_matriz(mensaje,columnas):     #creamos la funcion
    mensaje=mensaje.replace(" ","")    #eliminamos los espacios en blanco
    matriz=[]    #aqui estara la matriz final


No debemos olvidar, que el mensaje muchas veces no tiene una longitud exacta para forma la matriz, entonces debemos definir algo para saber si le agregamos o no le agregamos "X" al final del mismo:

    if (len(mensaje)%columnas!=0):
            mensaje=mensaje+"x"*(columnas-(len(mensaje)%columnas))

Como ya le quitamos los espacios al mensaje, con el if estamos preguntando si la longitud del mensaje es perfectamente divisible por la cantidad de columnas, de ser así el mensaje sigue intacto, pero si no son perfectamente divisibles, al mensaje original le agregamos cierta cantidad de "X".

        "x"*(columnas-(len(mensaje)%columnas))

La operación modulo (%) entre la longitud del mensaje y la cantidad de columnas, nos dirá en cuanto nos hemos pasamos de la división perfecta, y ahora, si a la cantidad de columnas le restamos ese resultado, esto nos diŕa cuantas "X" nos hace falta para que la división sea perfecta y podamos ocupar todos los espacios de la matriz. Una vez tenemos el dato de cuantas "X" nos faltan, entonces procedemos a multiplicarlas por el carácter "X" y la agregamos al mensaje original. 

    i=len(mensaje)/columnas    #ahora la division es perfecta, y obtendremos la cantidad de filas

    for x in range (0,i):    #cantidad de filas
            fila=[]    #creamos la fila que almacenara las columnas
            for y in range(0,columnas):    #cantidad de columnas
                fila.append(mensaje[y])    #del mensaje coge el caracter de la columna y
            mensaje=mensaje[columnas:]    #recortamos el mensaje de las columnas ya usadas
            matriz.append(fila)    #agregamos la fila a la matriz final

    return matriz    #retornamos la matriz final


Sí probamos la función que acabamos de crear, nos devuelve lo siguiente (lo acomodaré para que se vea en forma de matriz):

Usando la primera función

2) Leer por columnas o por Filas: 

La base fundamental de este procedimiento, se encuentra en la Iteración de dos ciclos FOR, uno que representa a la cantidad de filas y el otro que representa a la cantidad de columnas, según como los anidemos, podemos recorrer primer fila por fila o columna por columna.

def lectura(opcion,matriz):        #las dos posibles maneras de leer la matriz final por filas o por columnas
    n_fila=len(matriz)    #cantidad de filas
    n_columnas=len(matriz[0])    #cantidad de columnas
    texto=""    #texto final
   
    if (opcion=="horizontal"):    #leemos de forma horizontal, por filas
        for i in range(0,n_fila):    #recorremos las filas
            for j in range(0,n_columnas):    #recorremos las columnas
                texto+=matriz[i][j]    #almacenamos los valores, la fila se mantiene y la columna varia
            texto+=" "    #al terminar una fila, dejamos un espacio
        return texto    #retornamos el texto final
       
    else:     #leemos de forma vertical, por columnas
        for j in range(0,n_columnas):    #recorremos las columnas
            for i in range (0,n_fila):    #recorremos las filas
                texto+=matriz[i][j]    #almacenamos los valores, la columna se mantiene y la fila varia
            texto+=" "    #despues de cada columna, se deja un espacio
        return texto    #retornamos el texto final

Probamos la función con la función anterior y obtenemos lo siguiente:

Usando ambas funciones

El texto que aparece debajo de la matriz es el texto cifrado, pues hemos acomodado el mensaje por filas (de forma horizontal) y lo hemos leído por columnas (de forma vertical). Así que con 2 simples funciones, hemos logrado simular perfectamente el cifrado por transposiciones geométricas básica (sin utilizar clave).

Como este post ya se ha extendido lo suficiente, me saltaré la explicación de toda la tool pero en el código fuente de la misma, estarán comentados los pasos más importantes. (Es importante que realicen sus análisis en papel y lápiz, pues muchos conceptos no son entendibles al instante, o mi código no es muy elegante y simple) Pueden comentar cualquier duda al respecto, pues estamos constantemente pendientes a cada una de ellas, y de ser necesario se harían nuevos post explicando las dudas generadas.

[1] Ver el Código completo de la tool en Pastebin [1]

El funcionamiento de cada opción de la tool es muy intuitivo, pero para continuar con el ejemplo anterior (cifrado por clave), veremos como la tool nos descifra el mensaje:

------------------------------------------------------------------------------------

Creo que hasta aquí llega es este post, espero que haya sido de su agrado y de suma utilidad para usted. Cualquier duda, comentario, corrección  o sugerencia será siempre bienvenida y los integrantes del grupo estamos dispuestos a solucionarla o responderla en el menor tiempo posible.

NOTA: El código se diseño y se probo bajo Python 2.7.3

Qué tengan feliz vida, de mucho hacking y programación (:
Bytez.