viernes, 23 de diciembre de 2011

Instalador CryptoHill

Han sido varios meses intensos. Durante este tiempo no he escrito más sobre los avances de mi proyecto por falta de tiempo. Sin embargo lo prometido es deuda y os traigo la aplicación CryptoHill construida durante el desarrollo del proyecto fin de carrera, el cual he aprobado (aún no conozco con qué nota). El instalador se encuentra disponible en el siguiente enlace público: CRYPTOHILL. Se encuentra comprimido en formato RAR.
Espero que os sea de utilidad.

miércoles, 29 de junio de 2011

Parte 2 (descifrado de Hill) completada

La parte 2 (descifrado de texto cifrado usando el criptosistema de Hill) ya está completada.

Captura de pantalla: Descifrado de hill

En esta imagen podemos ver como el programa ha descifrado el texto cifrado "FVVHZQMCAJPGZVMPDUGXGNMUSVVKMYJOSSVG". El texto claro que se ha obtenido es "ATACAREMOSALASVEINTETREINTAYOCHOUTCX", que claramente se interpreta como "Atacaremos a las 20:38 (hora UTC) X". El receptor recibió y descifró el texto cifrado que el emisor le envió para hacerle saber la hora en la que piensa atacar.

Analizando la imagen podemos observar una particularidad del descifrado: El último carácter del texto claro es una "X". ¿De dónde salió esa "X"? No se trata de un error, ya que previamente está calculado que ocurra lo que ha ocurrido. Para explicarlo tendremos que volver a la etapa de cifrado explicada en la entrada anterior (¿Recuerdan cuando en la entrada anterior avisé de la incongruencia de que el tamaño del texto claro y el del texto cifrado fueran distintos? Pues bien, tiene mucho que ver con esa extraña "X" que apareció al final del texto claro descifrado como seguidamente veremos).

Supongamos que vamos a cifrar un texto que contiene m caracteres. Para ello usaremos una matriz clave privada con una dimensión n (tamaño del bloque a cifrar). Si m no es divisible por n, en el último paso del cifrado quedarán menos de n caracteres por computar. ¿Qué hacemos? Fácil. Agregamos tantos caracteres como sean necesarios hasta que m sea divisible por n. ¿Qué carácter agregamos? Cualquiera. Nosotros hemos convenido que agregaremos el carácter "X", ya que es un carácter poco usual en lengua española.

Por ejemplo, el texto claro "ATACAREMOSALASVEINTETREINTAYOCHOUTC" tiene 35 caracteres. Como estamos usando una matriz clave privada de dimensión 3 (véase la imagen) tenemos que 35 no es divisible entre 3, ya que obtenemos un resto 2. Para que sea divisible basta con que agreguemos al texto claro un carácter "X". De esta forma tendremos 36 caracteres y 36 sí es divisible por 3. Tras cifrar obtendremos el texto cifrado "FVVHZQMCAJPGZVMPDUGXGNMUSVVKMYJOSSVG", el cual tiene 36 caracteres. Una vez que descifremos el texto cifrado obtendremos el texto claro esperado más el carácter "X" que fue agregado al texto claro antes de cifrar por convenio. Basta con eliminar los últimos caracteres "X" que aparecen en nuestro texto claro recién descifrado (en el caso de que dichos caracteres "X" estén fuera del contexto de la frase) para conseguir el auténtico texto claro inicial y esperado.

¿Qué procedimiento se sigue para descifrar en el criptosistema de Hill? Veámoslo paso a paso:
  1. Primero calculamos la matriz inversa Kinversa de la matriz clave privada K.
  2. A continuación traducimos el texto cifrado en su equivalente numérico teniendo en cuenta que el carácter A corresponde al número 0, el B al 1, el C al 2, etc.
  3. Una vez obtenido el texto cifrado numérico tomamos sus primeros n números, donde n es la dimensión de la matriz clave privada K (número de filas o columnas de la matriz), es decir, el tamaño del bloque a cifrar. 
  4. Los n números obtenidos del paso anterior conforman los elementos de una matriz C de una única columna y n filas. Los elementos se colocan de forma ordenada en la matriz C.
  5. Se realiza el producto de la matriz Kinversa por la matriz C, obteniéndose una nueva matriz P de una única columna y n filas.
  6. Se traduce cada elemento numérico de la matriz P en su carácter equivalente teniendo en cuenta que el número 0 corresponde al carácter A, el 1 al B, el 2 al C, etc.
  7. Los caracteres obtenidos en el paso anterior corresponden al texto claro. Si queda texto cifrado por descifrar volvemos al paso 3 para volver a iterar con los siguientes n números del texto cifrado.
Lo veremos más claro con un simple ejemplo. Descifraremos el texto "YFSN" con una matriz clave privada formada por los elementos 4, 9, 13 y 18. NOTA: Recuérdese que estamos trabajando con aritmética modular 26.
    Matriz K
  1. Calculamos la matriz inversa de K, obteniéndose la siguiente matriz Kinversa:
    Matriz inversa de K
  2. El equivalente numérico del texto claro "YFSN" es 24, 5, 18 y 13. 
  3. ITERACIÓN 1. La dimensión de la matriz clave privada es 2, por tanto n = 2 en este ejemplo. Tomamos los 2 primeros números del texto claro numérico. Estos 2 números son 24 y 5.
  4. La matriz C que se obtiene del paso anterior está formada por los elementos 24 y 5. Estos elementos se colocan formando una única columna y 2 filas.
  5. Realizamos el producto Kinversa por C, obteniéndose P.
  6. Iteración 1
  7. Los elementos 7 y 14 que conforman la matriz P corresponden a los caracteres "H" y "O".
  8. Por tanto se ha obtenido el texto claro "HO". Como queda texto cifrado por descifrar (18 y 13) volvemos al paso 3.
  1. ITERACIÓN 2. Tomamos los 2 siguientes números del texto claro numérico. Estos 2 números son 18 y 13.
  2. La matriz C que se obtiene del paso anterior está formada por los elementos 18 y 13. Estos elementos se colocan formando una única columna y 2 filas.
  3. Realizamos el producto Kinversa por C, obteniéndose P.
  4. Iteración 2
  5. Los elementos 11 y 0 que conforman la matriz P corresponden a los caracteres "L" y "A".
  6. Por tanto se ha obtenido el texto claro "LA". Como no queda texto cifrado por descifrar terminamos.
Al descifrar el texto cifrado "YFSN" con la matriz clave privada K se ha obtenido el texto claro "HOLA" (que era lo esperado, ya que en la entrada anterior realizamos el cifrado de "HOLA" y obtuvimos "YFSN" con la misma matriz clave privada K).
    Como vimos en la entrada anterior, la matriz clave privada usada en el ejemplo cumple la restricción de tener obligatoriamente matriz inversa (su determinante es 7, con lo cual es distinto de cero; y además mcd(7,26) = 1).

    martes, 28 de junio de 2011

    Parte 1 (cifrado de Hill) completada

    La parte 1 (cifrado de texto claro usando el criptosistema de Hill) ya está completada.

    Captura de pantalla: Cifrado de Hill

    En esta imagen podemos ver como el programa ha cifrado el texto claro "ATACAREMOSALASVEINTETREINTAYOCHOUTC", que claramente se interpreta como "Atacaremos a las 20:38 (hora UTC)". El texto cifrado que se ha obtenido es "FVVHZQMCAJPGZVMPDUGXGNMUSVVKMYJOSSVG". Enviaremos este texto a nuestro receptor para que lo descifre siguiendo las reglas adecuadas.

    Si hemos sido muy meticulosos con la imagen de arriba hemos podido advertir que el texto claro está formado por 35 caracteres, mientras que el texto cifrado contiene 36 caracteres. Si se supone que en el criptosistema de Hill el texto claro debe tener el mismo tamaño que el texto cifrado, ¿cómo se explica que en este caso ambos textos difieran su tamaño en un carácter? Esto ocurre sólo en algunos casos. En la próxima entrada, cuando analicemos el descifrado también explicaremos el motivo por el cual el tamaño del texto cifrado es mayor que el del texto claro. Olvidemos esta "anomalía" por ahora (entrecomillo anomalía porque lejos de serlo, ocurre con bastante frecuencia) .

    ¿Qué procedimiento se sigue para cifrar en el criptosistema de Hill? Veámoslo paso a paso:
    1. Primero traducimos el texto claro en su equivalente numérico teniendo en cuenta que el carácter A corresponde al número 0, el B al 1, el C al 2, etc.
    2. Una vez obtenido el texto claro numérico tomamos sus primeros n números, donde n es la dimensión de la matriz clave privada K (número de filas o columnas de la matriz), es decir, el tamaño del bloque a cifrar. 
    3. Los n números obtenidos del paso anterior conforman los elementos de una matriz P de una única columna y n filas. Los elementos se colocan de forma ordenada en la matriz P.
    4. Se realiza el producto de la matriz clave privada K por la matriz P, obteniéndose una nueva matriz C de una única columna y n filas.
    5. Se traduce cada elemento numérico de la matriz C en su carácter equivalente teniendo en cuenta que el número 0 corresponde al carácter A, el 1 al B, el 2 al C, etc.
    6. Los caracteres obtenidos en el paso anterior corresponden al texto cifrado. Si queda texto claro por cifrar volvemos al paso 2 para volver a iterar con los siguientes n números del texto claro.
    Lo veremos más claro con un simple ejemplo. Cifraremos el texto "HOLA" con una matriz clave privada formada por los elementos 4, 9, 13 y 18. NOTA: Recuérdese que estamos trabajando con aritmética modular 26.
      Matriz K
    1. El equivalente numérico del texto claro "HOLA" es 7, 14, 11 y 0. 
    2. ITERACIÓN 1. La dimensión de la matriz clave privada es 2, por tanto n = 2 en este ejemplo. Tomamos los 2 primeros números del texto claro numérico. Estos 2 números son 7 y 14.
    3. La matriz P que se obtiene del paso anterior está formada por los elementos 7 y 14. Estos elementos se colocan formando una única columna y 2 filas.
    4. Realizamos el producto K por P, obteniéndose C.
    5. Iteración 1
    6. Los elementos 24 y 5 que conforman la matriz C corresponden a los caracteres "Y" y "F".
    7. Por tanto se ha obtenido el texto cifrado "YF". Como queda texto claro por cifrar (11 y 0) volvemos al paso 2.
    1. ITERACIÓN 2. Tomamos los 2 siguientes números del texto claro numérico. Estos 2 números son 11 y 0.
    2. La matriz P que se obtiene del paso anterior está formada por los elementos 11 y 0. Estos elementos se colocan formando una única columna y 2 filas.
    3. Realizamos el producto K por P, obteniéndose C.
    4. Iteración 2
    5. Los elementos 18 y 13 que conforman la matriz C corresponden a los caracteres "S" y "N".
    6. Por tanto se ha obtenido el texto cifrado "SN". Como no queda texto claro por cifrar terminamos.
    Al cifrar el texto claro "HOLA" con la matriz clave privada K se ha obtenido el texto cifrado "YFSN".
      Una restricción para que el criptosistema de Hill funcione es que la matriz clave privada tenga matriz inversa asociada. Esto, en aritmética modular, quiere decir que:
      • El determinante de la matriz clave privada tiene que ser distinto de cero. En nuestro ejemplo el determinante de la matriz inversa es 7, es decir, distinto de cero.
      • El máximo común divisor entre el determinante de la matriz clave privada y 26 (aritmética modular con la que trabajamos) tiene que ser igual a 1. Esto quiere decir que el determinante de la matriz clave privada debe ser coprimo con todos los factores de 26 (que son 2 y 13). Como ya hemos dicho, en nuestro ejemplo el determinante es 7. Sabemos que mcd(7,26) = 1 (lo que es equivalente a afirmar que 7 y 2 son coprimos, y que 7 y 13 también son coprimos) .
      La clave que tomamos en nuestro ejemplo cumple esta restricción y por tanto tiene matriz inversa asociada. Esta restricción realmente afecta al descifrado y no al cifrado como veremos más adelante. Pero si no podemos descifrar, ¿de qué nos sirve cifrar?...

      sábado, 18 de junio de 2011

      Partes del proyecto

      Las partes en las que se divide el PFC son las siguientes:
      1. Cifrado de texto claro usando el criptosistema de Hill.
      2. Descifrado de texto cifrado usando el criptosistema de Hill.
      3. Criptoanálisis del criptosistema de Hill. Posibles ataques:
        • Ataque con texto claro conocido: El criptosistema es muy débil si se conoce un texto cifrado y su correspondiente texto en claro. El ataque que se estudiará es:
          • Método de la matriz inversa.
        1. Ataque con sólo texto cifrado conocido. El sistema es bastante más robusto si sólo conocemos el texto cifrado. Un ataque de fuerza bruta es inviable debido al extenso espectro de posibles casos que tiene una matriz como vemos a continuación (recordemos que estamos trabajando en aritmética modular 26):

          Dimensión Número de matrices claves posibles
          1 12
          2 157248
          3 1634038189056
          4 12303585972327392870400

          Por tanto tras desechar un ataque por fuerza bruta debemos afrontar nuevas posibilidades y aquí es donde nos encontramos ante el método que llamaremos de Bauer-Millward. En este método es donde reside lo novedoso de mi PFC. Esta forma de atacar al criptosistema de Hill fue publicada hace apenas 4 años y reduce considerablemente el espectro de posibles casos a estudiar conduciendo a la viabilidad del algoritmo. Por tanto, veremos 2 posibles ataques con sólo texto cifrado conocido:
          • Fuerza bruta (sólo para claves privadas de dimensión 1x1 ó 2x2).
          • Método de Bauer-Millward.

      Consideraciones previas

      El PFC constará de las siguientes consideraciones previas:
      1. Trabajaremos en aritmética modular 26. Esto quiere decir que nuestro criptosistema nunca usará valores mayores de 25.
      2. El alfabeto que usaremos estará formado por 26 letras (de ahí que usemos aritmética modular 26) que son las siguientes: 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.
      3. El cifrado de cada letra es el siguiente:

        Letra Cifrado Letra Cifrado Letra Cifrado Letra Cifrado
        A 0 B 1 C 2 D 3
        E 4 F 5 G 6 H 7
        I 8 J 9 K 10 L 11
        M 12 N 13 O 14 P 15
        Q 16 R 17 S 18 T 19
        U 20 V 21 W 22 X 23
        Y 24 Z 25

      No obstante el cifrado, descifrado y criptoanálisis del criptosistema de Hill funcionaría igualmente si tomamos una aritmética modular distinta, si escogemos otras letras del alfabeto y si cambiamos el cifrado de estas letras.

      El programa a desarrollar será implementado en el entorno de desarrollo Microsoft Visual Studio 2008. Para ello usaremos la interfaz de programación de aplicaciones gráfica denominada Windows Forms, que está basada en la programación de ventanas típicas de Windows usadas como formularios. Esta interfaz gráfica es parte de Microsoft .NET Framework y su código está escrito en su totalidad en C#. La versión de .NET Framework usada es la 3.5. Es bastante probable que utilicemos otros frameworks de libre distribución conforme vayamos avanzando en la programación del sistema. Cada framework nuevo usado será especificado en siguientes entradas de este blog.

      En la última entrada de este blog (que debe estar para finales de Septiembre) debe contener un enlace para la descarga de la aplicación desarrollada. ¡Esperemos que así sea!

      viernes, 17 de junio de 2011

      ¡Comenzamos!

      He creado este blog con el objetivo de describir el progreso en la creación de mi Proyecto Fin de Carrera de Ingeniería Informática. A día de hoy, el Proyecto Fin de Carrera (PFC en adelante) es la última traba que me queda por superar para convertirme en uno de esos ingenieros que engrosan las largas listas de paro actualmente. Pero dejemos a un lado la negatividad...

      El proyecto que he elegido tiene por nombre "Criptoanálisis del criptosistema de Hill" y consta de 18 créditos. Mi tutor, Gerardo Valeiras, es doctor en matemáticas y director del departamento de Matemática Aplicada I de la Universidad de Sevilla. Mi idea inicial es entregarlo en la convocatoria de Septiembre. En principio mañana firmo la adjudicación del PFC y ya no habrá vuelta atrás; de forma que no quedará más remedio que ponerse a desarrollarlo durante este próximo verano que comienza en apenas 4 días.

      El PFC trata el estudio del criptosistema de Hill (en inglés: Hill cipher), el cual fue propuesto por el estadounidense Lester S. Hill en el año 1929 (aquel año negro para la economía mundial). La seguridad de este criptosistema recae en una matriz cuadrada usada como clave privada. Se sabe que es vulnerable a un ataque por texto en claro conocido, y por tanto su uso es inseguro y poco recomendable. Además, veremos que también es débil a un ataque por texto cifrado conocido, como han demostrado recientemente (año 2007) los matemáticos Craig Bauer y Katherine Millward. Es, por tanto, un criptosistema sin aplicación real, pero sí interesante desde el punto de vista académico.

      Por último, aclarar que el nombre del blog (CryptoHill) hace referencia al nombre con el que he bautizado a la aplicación a implementar como parte del PFC.