martes, 26 de julio de 2016

Criptografía (XXIV): cifrado de Hill y criptoanálisis Gauss Jordan (II)

En un post anterior expliqué brevemente el cifrado de Hill, propuesto por el matemático Lester S. Hill en 1929, y en éste intento explicar, como siempre de la forma más comprensible de la que sea capaz, lo que he entendido sobre su vulnerabilidad y, por consiguiente, sobre el criptoanálisis de mensajes cifrados con este criptosistema.

La gran vulnerabilidad de este criptosistema radica en que es muy débil ante un ataque con texto claro conocido, es decir, si el criptoanalista conoce parte del texto en claro correspondiente al texto cifrado del que dispone no tendrá mayor problema para obtener la matriz K con la que se cifró esa parte del texto en claro y, por tanto, estaría en disposición de descifrar todos los mensajes cifrados con dicha clave (K). Esta vulnerabilidad se debe a la linealidad de este criptosistema, por lo que con texto claro conocido y empleando el método de Gauss Jordan no es muy difícil obtener la matriz clave (K).

Veamos un ejemplo: supongamos que un criptoanalista se hace con un pequeño fragmento de texto en claro y su correspondiente texto cifrado, los del ejemplo del post anterior, es decir:

Texto en claro: "EJEMPLODECIFRADOHILLX".
Criptograma: "ZFMLUHJHGLOCJDJZMPIEZ".

Supongamos también que el croptoanalista sabe o sospecha que el cifrado se ha realizado sobre trigramas del texto en claro, es decir, utilizando como clave una matriz cuadrada (K) de orden 3 (tres filas y tres columnas). Por tanto, sustituyendo cada una de las letras, tanto del texto en claro como del criptograma, por la posición que ocupa cada una de ellas en el alfabeto español, tendría el siguiente sistema de ecuaciones lineales:

(4 x k11 + 9 x k12 + 4 x k13) mod 27 = 26.
(4 x k21 + 9 x k22 + 4 x k23) mod 27 = 5.
(4 x k31 + 9 x k32 + 4 x k33) mod 27 = 12.
(12 x k11 + 16 x k12 + 11 x k13) mod 27 = 11.
(12 x k21 + 16 x k22 + 11 x k23) mod 27 = 21.
(12 x k31 + 16 x k32 + 11 x k33) mod 27 = 7.
...
(11 x k11 + 11 x k12 + 24 x k13) mod 27 = 8.
(11 x k21 + 11 x k22 + 24 x k23) mod 27 = 4.
(11 x k31 + 11 x k32 + 24 x k33) mod 27 = 26.

Sistema de ecuaciones lineales que en notación matricial podría expresarse de la siguiente manera (M · = C):
Y para resolverlo, el criptoanalista podría crear la matriz aumentada o ampliada (M|C) combinando ambas matrices, siendo M la matriz de coeficientes y C la matriz de términos independientes, de la siguiente manera:
Ahora, el criptoanalista aplicando operaciones elementales a esta matriz aumentada o ampliada iría obteniendo sistemas equivalentes, que no alteran las soluciones del sistema lineal de ecuaciones, hasta transformar las tres primeras líneas de la matriz M en la matriz identidad de orden 3 (I3), aquella en la que todos sus elementos son 0 excepto los de la diagonal principal que son todos ellos 1, con lo que obtendría la matriz (K) que se utilizó como clave en el cifrado.

Antes que nada, comentar que la operaciones elementales que se pueden realizar sobre una matriz ampliada y que no alteran las soluciones de un sistema lineal de ecuaciones son las siguientes:

- Intercambiar entre sí dos filas de la matriz ampliada (equivale a intercambiar entre sí dos ecuaciones).
- Multiplicar una fila de la matriz ampliada por un número distinto de cero (equivale a multiplicar una ecuación por ese número).
- Sumar a una fila de la matriz ampliada una combinación lineal de otra (equivale a sumar a una ecuación otra multiplicada por un número cualquiera).

Dicho lo cual, el criptoanalista actuaría de la siguiente forma (las operaciones las realizaría siempre en módulo 27):

1.- Partiendo de la matriz ampliada (M|C):
Multiplicaría la primera fila por el inverso de 4 mod 27 = 7, para obtener un 1 en la primera columna de la primera fila:

(4 x 7) mod 27 = 28 mod 27 = 1.
(9 x 7) mod 27 = 63 mod 27 = 9.
(4 x 7) mod 27 = 28 mod 27 = 1.
(26 x 7) mod 27 = 182 mod 27 = 20.
(5 x 7) mod 27 = 35 mod 27 = 8.
(12 x 7) mod 27 = 84 mod 27 = 3.

Obteniéndose:
2.- Sumaría a cada una del resto de las filas la primera fila multiplicada por el opuesto del primer elemento (primera columna) de cada una de ellas, para obtener un cero en la primera columna del resto de filas:

2ª fila = (2ª fila + (-12) x 1ª fila) mod 27.
3ª fila = (3ª fila + (-15) x 1ª fila) mod 27.
...
7ª fila = (7ª fila + (-11) x 1ª fila) mod 27.

Obteniéndose:
3.- Intercambiaría entre sí las filas 2ª y 6ª:
4.- Multiplicaría la segunda fila por el inverso de 7 mod 27 = 4, para obtener un 1 en la segunda columna de la segunda fila:
5.- Sumaría a cada una del resto de las filas la segunda fila multiplicada por el opuesto del segundo elemento (segunda columna) de cada una de ellas, para obtener un cero en la segunda columna del resto de filas:

1ª fila = (1ª fila + (-9) x 2ª fila) mod 27.
3ª fila = (3ª fila + (-3) x 2ª fila) mod 27.
...
7ª fila = (7ª fila + (-20) x 2ª fila) mod 27.

Obteniéndose:
6.- Restaría a la 3ª la 6ª fila (3ª fila = 3ª fila + (-1) x 6ª fila):
7.- Multiplicaría la tercera fila por el inverso de 4 mod 27 = 7, para obtener un 1 en la tercera columna de la tercera fila:
8.- Y finalmente, sumaría a cada una del resto de las filas la tercera fila multiplicada por el opuesto del tercer elemento (tercera columna) de cada una de ellas, para obtener un cero en la tercera columna del resto de filas:

1ª fila = (1ª fila + (-10) x 3ª fila) mod 27.
2ª fila = (2ª fila + (-26) x 3ª fila) mod 27.
...
7ª fila = (7ª fila + (-6) x 3ª fila) mod 27.

Obteniéndose:
Con lo que el criptoanalista obtendría que:

1 x k11 + 0 x k12 + 0 x k13 = 2; k11 = 2.
1 x k21 + 0 x k22 + 0 x k23 = 22; k21 = 22.
1 x k31 + 0 x k32 + 0 x k33 = 9; k31 = 9.
0 x k11 + 1 x k12 + 0 x k13 = 11; k12 = 11.
0 x k21 + 1 x k22 + 0 x k23 = 4; k22 = 4.
0 x k31 + 1 x k32 + 0 x k33 = 4; k32 = 4.
0 x k11 + 0 x k12 + 1 x k13 = 0; k13 = 0.
0 x k21 + 0 x k22 + 1 x k23 = 4; k23 = 4.
0 x k31 + 0 x k32 + 1 x k33 = 12; k33 = 12.

Es decir, la parte derecha de la matriz ampliada que corresponde a la parte izquierda con la matriz identidad de orden 3 (I3) nos revela la matriz transpuesta de la matriz (K) que se utilizó como clave para cifrar el texto en claro. Por tanto, la matriz K sería:
Que como se puede ver en el post anterior es efectivamente la matriz utilizada como clave en el ejemplo.

jueves, 21 de julio de 2016

Criptografía (XXIII): cifrado de Hill (I)

En este post me propongo explicar de forma comprensible lo que he entendido sobre el cifrado de Hill, propuesto por el matemático Lester S. Hill, en 1929, y que se basa en emplear una matriz como clave para cifrar un texto en claro y su inversa para descifrar el criptograma correspondiente.

Hay tres cosas que me gustan de la criptografía clásica, además de que considero que ésta es muy didáctica a la hora de comprender los sistemas criptográficos modernos: la primera de ellas es que me "obliga" a repasar conceptos de matemáticas aprendidos hace mucho tiempo y, desgraciadamente, olvidados también hace demasiado tiempo, y, por consiguiente, que, como dice Dani, amigo y coautor de este blog, me "obliga" a hacer "gimnasia mental"; la segunda es que, en la mayoría de las ocasiones, pueden cifrarse y descifrase los mensajes, e incluso realizarse el criptoanálisis de los criptogramas, sin más que un simple lápiz y papel, es decir, para mi es como un pasatiempo: como resolver crucigramas, acertijos, etc.; y la tercera es que, por deformación profesional, tiendo a automatizar dichos procesos (cifrado, descifrado y criptoanálisis), lo que también me sirve para no olvidar los principios de programación aprendidos hace también mucho tiempo.

Pero, volvamos al cifrado de Hill:

1.- Cifra el texto en claro considerando bloques de k símbolos del mismo (bigramas, trigramas, etc.).

2.- Propone un criptosistema utilizando como clave (Kuna matriz cuadrada de orden k, es decir, una matriz con el mismo número de filas (k) y de columnas (k), de tal forma que los caracteres de la clave se disponen en filas y columnas (de izquierda a derecha y de arriba a abajo), y el algoritmo de cifrado para el primer bloque de k símbolos del texto en claro sería el siguiente:
Donde:
kij: caracter de la fila i columna j de la matriz (K) que se utilizará como clave para cifrar el texto en claro.
mi: carácter i-ésimo del mensaje a cifrar o texto en claro.
ci: carácter i-ésimo del mensaje cifrado o criptograma.
n: tamaño del alfabeto.

3.- Conforme a este criptosistema, la matriz K debe tener inversa K-1 mod n, que será la que se use en el descifrado del criptograma.

Para comprender mejor este criptosistema, repasemos ahora algunos conceptos de álgebra lineal:

3.1..- Dadas dos matrices K y M éstas se pueden multiplicar sí y sólo sí el número de columnas de K es igual al número de filas de M (como es nuestro caso) y el elemento cij de la matriz producto (C) se obtiene como el sumatorio de los productos de cada elemento de la fila i de la matriz K por cada elemento de la columna j de la matriz M. Es decir:
En nuestro caso, como la matriz K tiene k filas y k columnas, y la matriz M tiene k filas y 1 columna, la matriz producto (C) tendrá k filas y 1 columna:
3.2.- Por otra parte, para que la matriz K tenga inversa (K-1) se debe cumplir la siguiente condición (necesaria pero no suficiente):
Donde:
K: matriz que se utilizará como clave para cifrar el texto en claro.
K-1: matriz inversa de K, que se utilizará para descifrar el mensaje cifrado o criptograma.
In: matriz identidad de orden n.

Como sabemos la matriz identidad es aquella en la que todos sus elementos son 0 excepto los de la diagonal principal que son todos ellos 1:
Por lo que esto impone una condición (tal y como he dicho necesaria pero no suficiente): sólo las matrices cuadradas tienen matriz inversa y, por tanto, la matriz K que se utilice como clave debe ser cuadrada (mismo número de filas que de columnas), como también es nuestro caso.

3.3.- La inversa de una matriz K, si existe (K-1), es única.

3.4.- Si  K-1 es la matriz inversa de K, entonces: (K-1)-1 = K.

3.5.- Para que una matriz cuadrada (K) tenga inversa (K-1) se debe cumplir como condición adicional (en este caso necesaria y, además, suficiente) que su determinante (det K = |K|) sea distinto de cero, y su cálculo (K-1) puede realizarse aplicando la siguiente fórmula:
Donde:
K-1: matriz inversa de K.
CT: matriz de cofactores de K transpuesta.
|K|: determinante de la matriz K.

3.6.- Y, por último y para terminar este repaso de matemáticas, me tengo que referir a los números primos entre sí (coprimos o primos relativos), es decir, aquellos cuyo máximo común divisor (mcd) es 1 o -1, o, lo que es lo mismo, aquellos que no tienen un divisor en común diferente de 1 y -1, ya que |K| y n (tamaño del alfabeto) deben ser coprimos para que la matriz K sea invertible en módulo n.  

4.- Veamos un ejemplo de cifrado y de descifrado:

4.1.- Cifrado:

Texto en claro: "EJEMPLO DE CIFRADO HILL".
Longitud texto en claro = 20.
Clave de cifrado: "CLAVEEJEM".
Longitud de la clave: 9.

Considerando el alfabeto español:
 Tamaño del alfabeto (n) = 27

Como clave (K) vamos a utilizar una matriz cuadrada de orden k = 3 (3 filas y 3 columnas), para lo que distribuimos las letras de la clave en tres filas de tres caracteres cada una y sustituimos cada uno de los caracteres por el número correspondiente a la posición que ocupa en el alfabeto español, de la siguiente manera:
Antes que nada, vamos a comprobar si esta matriz (K) tiene inversa (K-1) mod 27, ya que si no es así no se podría utilizar como clave:

Para ello, calculamos su determinante: det K = |K| = 2 x 4 x 12 +  11 x 4 x 9 + 0 x 22 x 4 - 9 x 4 x 0 - 4 x 4 x 2 - 12 x 22 x 11 = 96 + 396 + 0 - 0 - 32 - 2.904 = -2.444.

det K mod 27= |K| mod 27 = -2.444 mod 27 = -14, por lo que la matriz K es invertible en módulo 27, ya que su determinante es distinto de cero y -14 y 27 son coprimos.

Posteriormente, como la longitud del texto en claro no es múltiplo de k (3), rellenamos el texto en claro con caracteres sin sentido en él (por ejemplo "X"), hasta que lo sea:

Texto en claro: "EJEMPLO DE CIFRADO HILLX".
Longitud texto en claro = 21 (múltiplo de 3).

Después troceamos el texto en claro en bloques de k (3) caracteres (trigramas):

"EJE MPL ODE CIF RAD OHI LLX".

Y distribuimos los caracteres del primer trigrama ("EJE") en una columna de 3 filas (ky los sustituimos por el número correspondiente a la posición que ocupa cada uno de ellos en el alfabeto español, de tal forma que el cifrado se realizaría de la siguiente manera:
O, lo que es lo mismo, la función de cifrado (EK) seria:
Es decir, para el primer trigrama del texto en claro:

c1 = (k11 x m1k12 x m2 + k13 x m3) mod 27 = (2 x 4 + 11 x 9 + 0 x 4) mod 27 = 107 mod 27 = 26 = Z.
c2 = (k21 x m1 + k22 x m2 + k23 x m3) mod 27 = (22 x 4 + 4 x 9 + 4 x 4) mod 27 = 140 mod 27 = 5 = F.
c3 = (k31 x m1 + k32 x m2 + k33 x m3) mod 27 = (9 x 4 + 4 x 9 + 12 x 4) mod 27 = 120 mod 27 = 12 = M.

Después repetimos lo mismo con el segundo trigrama del texto en claro ("MPL"), de tal forma que el cifrado se realizaría de la siguiente manera:
Es decir, para el segundo trigrama del texto en claro:

c4 = (k11 x m4 + k12 x m5 + k13 x m6) mod 27 = (2 x 12 + 11 x 16 + 0 x 11) mod 27 = 200 mod 27 = 11 = L.
c5 = (k21 x m4 + k22 x m5 + k23 x m6) mod 27 = (22 x 12 + 4 x 16 + 4 x 11) mod 27 = 372 mod 27 = 21 = U.
c6 = (k31 x m4 + k32 x m5 + k33 x m6) mod 27 = (9 x 12 + 4 x 16 + 12 x 11) mod 27 = 304 mod 27 = 7 = H.

Y así sucesivamente, obteniéndose el siguiente texto cifrado o criptograma:

"ZFMLUHJHGLOCJDJZMPIEZ".

4.2.- Descifrado:

Criptograma: "ZFMLUHJHGLOCJDJZMPIEZ".
Clave de descifrado: matriz inversa (K-1) mod 27. La calculamos con la fórmula ya vista anteriormente:
Donde:
K-1: matriz inversa de K.
CT: matriz de cofactores de K transpuesta.
|K|: determinante de K, que debe calcularse en mod n (tamaño del alfabeto), en nuestro caso en módulo 27, y que tal y como hemos calculado antes, en nuestro ejemplo, es -14.
(|K|)-1: inverso del determinante de la matriz K, es decir: 1/|K|. Debe calcularse en mod n (tamaño del alfabeto), en nuestro caso en módulo 27, y que sería -2, ya que -2 es el inverso multiplicativo de -14 en módulo 27.

Por tanto:
Y una vez hecho estos cálculos obtenemos la matriz de descifrado:

Y ahora ya sólo nos queda descifrar el criptograma:

La función de descifrado (DK) sería:
Es decir, para el primer trigrama del criptograma:

m1 = (k-111 x c1 + k-112 x c2 + k-113 x c3) mod 27 = (17 x 26 + 21 x 5 + 20 x 12) mod 27 = 787 mod 27 = 4 = E.
m2 = (k-121 x c1 + k-122 x c2 + k-123 x c3) mod 27 = (24 x 26 + 6 x 5 + 16 x 12) mod 27 = 846 mod 27 = 9 = J.
m3 = (k-131 x c1 + k-132 x c2 + k-133 x c3) mod 27 = (4 x 26 + 7 x 5 + 9 x 12) mod 27 = 247 mod 27 = 4 = E.

Después repetimos lo mismo con el segundo trigrama del criptograma ("LUH"), de tal forma que el descifrado se realizaría de la siguiente manera:
Es decir, para el segundo trigrama del texto en claro:

m4 = (k-111 x c4 + k-112 x c5 + k-113 x c6) mod 27 = (17 x 11 + 21 x 21 + 20 x 7) mod 27 = 768 mod 27 = 12 = M.
m5 = (k-121 x c4 + k-122 x c5 + k-123 x c6) mod 27 = (24 x 11 + 6 x 21 + 16 x 7) mod 27 = 502 mod 27 = 16 = P.
m6 = (k-131 x c4 + k-132 x c5 + k-133 x c6) mod 27 = (4 x 11 + 7 x 21 + 9 x 7) mod 27 =  254 mod 27 = 11 = L.

Y así sucesivamente, obteniéndose el siguiente mensaje descifrado o texto en claro:

"EJEMPLODECIFRADOHILLX".

Conforme a las definiciones dadas en esta serie de post, en cuanto a la clasificación de los sistemas criptográficos, podemos decir que el cifrado de Hill es un sistema de sustitución monoalfabética, ya que cada bloque de k símbolos del mensaje en claro (bigramas, trigramas,...) se sustituye siempre por el mismo bloque de k símbolos en el texto cifrado, pero debido a que la clave que se emplea para descifrar (K-1) es diferente de la que se usa para cifrar (K): ¿podríamos decir que se trata de un sistema asimétrico?. Pues no, ya que en este post comenté que en los criptosistemas simétricos la clave para descifrar un criptograma es la misma o se calcula a partir de la clave que se utiliza para cifrar el texto en claro, y viceversa, y, por tanto, estaríamos en el caso de un sistema criptográfico simétrico.

En un próximo post hablaré de la vulnerabilidad de este sistema criptográfico y de su criptoanálisis.

jueves, 14 de julio de 2016

Criptografía (XXII): criptología para todos (III)

En este post introduzco ciertos conceptos básicos que nos ayudarán a comprender mejor los sistemas criptográficos modernos; como se verá, algunos de ellos basados en técnicas no tan nuevas.

Como en todos los posts que he escrito sobre criptografía en este blog, intentaré explicar lo que he entendido de la forma más sencilla posible, espero que sin cometer demasiados errores, con objeto de divulgar esta materia de la forma más comprensible de la que sea capaz.

Tal y como nos cuenta la Wikipedia, podemos considerar que la criptografía moderna comienza con Claude Shannon, cuyos trabajos a mediados del siglo XX establecieron una sólida base teórica para la criptografía y el criptoanálisis.

- Confusión: es una de las dos técnicas básicas, utilizada ya desde los orígenes de la criptografía, para ocultar la relación entre un mensaje sin cifrar o texto en claro y el texto cifrado o criptograma. Evidentemente, la clave (K) establece una relación entre ambos, y podemos decir que lo que realmente pretende la confusión es que a un criptoanalista le resulte lo más complicado posible el establecer la relación existente entre el criptograma y la clave (K) empleada en el cifrado.

El mecanismo empleado para conseguir la confusión es la sustitución, que, como ya sabemos, consiste en sustituir cada elemento de un texto en claro por otro u otros elementos en el texto cifrado.

- Difusión: es la otra técnica básica, también empleada desde los inicios de la criptografía, para ocultar la relación entre un mensaje sin cifrar o texto en claro y el texto cifrado o criptograma. En este caso, consistente en difundir o diluir las características del texto en claro a lo largo de todo el criptograma.

El mecanismo empleado para conseguir la difusión es la transposición, que, como también sabemos, consiste en cambiar de posición en el texto cifrado los elementos correspondientes a un texto en claro.

- Criptografía simétrica o de clave privada o secreta: en este tipo de criptosistemas la clave para descifrar un criptograma (K') se calcula a partir de la clave (K) que se utilizó para cifrar el texto en claro, y viceversa. Lo habitual en los criptosistemas de este tipo es que ambas claves (K y K') coincidan, es decir, que se utilice la misma clave para cifrar un mensaje y para su descifrado.
Por tanto, la clave debe mantenerse en secreto entre el emisor y el receptor, ya que si se conociera por parte de terceras personas éstas no tendrían ningún problema para descifrar el criptograma.

El principal problema de estos criptosistemas es precisamente lo anterior, es decir, mantener secreta la clave, ya que si se emplea un canal no seguro para enviarla se incurre en el mismo riesgo de que la intercepten que si enviáramos el texto en claro.

Todos los algoritmos de cifrado clásicos son simétricos, lo que no quiere decir que algunos de los modernos no lo sean también. La mayoría de los algoritmos de cifrado simétrico modernos se apoyan en los conceptos de confusión y difusión, comentados anteriormente y propuestos por Claude Shannony se denominan cifrados de producto.

- Criptografía asimétrica o de clave pública: en este tipo de criptosistemas la clave para descifrar un criptograma (K') es diferente de la clave (K) que se utilizó para cifrar el texto en claro (de ahí el nombre de cifrado asimétrico) y, además, aunque no son independientes, del conocimiento de K no es posible deducir K', o al menos hasta el momento no se conoce que nadie lo haya logrado.

Me explico: este tipo de criptosistemas se caracterizan porque tanto el emisor como el receptor tienen un par de claves (K y K'); la primera de ellas (K) se utiliza para cifrar los mensajes y es pública (denominada clave pública), mientras que la segunda se emplea para descifrar los mensajes y es secreta (denominada clave privada), y por tanto esta última no debe ser revelada bajo ninguna circunstancia a nadie, ni siquiera a las personas con las que vamos a intercambiar mensajes cifrados.
De esta forma, tal y como se observa en el gráfico anterior, para cifrar un mensaje el emisor lo hace con la clave pública del receptor (que como su nombre indica es pública y debe estar en posesión de cualquier persona que pretenda enviarle un mensaje cifrado) y sólo el receptor podrá descifrarlo utilizando su clave privada (que como su nombre indica sólo él posee).

Por tanto, en este tipo de criptosistemas se elimina el principal problema indicado para los criptosistemas de cifrado simétrico, ya que se evita la necesidad de que el emisor envíe al receptor la clave de descifrado.

Además, otra de las principales ventajas de este tipo de criptosistemas es que posibilitan comprobar la autenticidad de la información recibida, tanto en lo que se refiere a la verificación de la identidad del remitente (el emisor es quien dice ser) como a la comprobación de que ésta no ha sido modificada desde que se generó (integridad de la información, es decir, que el contenido es exactamente el que el emisor nos envió).

Mientras que en un criptosistema simétrico la autenticidad del mensaje cifrado radica en el secreto de la clave (sólo emisor y receptor la conocen y, por tanto y en principio, sólo el emisor legítimo puede cifrar un mensaje que pueda ser descifrado por el receptor utilizando la clave compartida por ambos), en un criptosistema asimétrico el emisor puede añadir al mensaje a enviar, cifrándolo con su clave privada, un resumen del mismo (que se obtiene mediante una función 'hash'), de tamaño fijo mucho menor que el del mensaje original y asociado unívocamente a este último (es prácticamente imposible encontrar otro mensaje que dé lugar al mismo resumen), para que el receptor compruebe tanto que realmente es el emisor quien ha enviado el mensaje, como que el mensaje no ha sido interceptado y modificado por una tercera persona.

Sin embargo, los criptosistemas asimétricos presentan también un inconveniente fundamental respecto a los criptosistemas simétricos, ya que la complejidad de cálculo que comportan los hace significativamente más lentos que los de cifrado simétrico, razón por la cual en la práctica se utilizan sistemas criptográficos híbridos (ver siguiente concepto).

Criptografía híbrida: en este tipo de criptosistemas el texto en claro se cifra mediante una clave de sesión (criptografía simétrica), correspondiente a cada mensaje particular y generada aleatoriamente, y la clave de sesión se cifra utilizando la clave pública del receptor (criptografía asimétrica), de tal manera que sólo el receptor puede obtener la clave de sesión mediante su clave privada (criptografía asimétrica) y posteriormente descifrar el texto cifrado mediante la clave de sesión (criptografía simétrica).
El proceso de cifrado híbrido incorporando la firma digital y el de posterior descifrado incorporando la verificación de la autenticidad del emisor y de la integridad de la información recibida serían como se muestra en la siguiente figura:
Hasta aquí, por no hacerlo muy extenso, este primer post sobre criptografía moderna, en el que he introducido los conceptos más básicos, y en los siguientes introduciré más conceptos, tanto referidos a la criptografía como al criptoanálisis.

lunes, 11 de julio de 2016

Criptografía (XXI): cifrado Vigenère y criptoanálisis IC (II)

Decía en el post anterior que iba a poner un ejemplo de un ataque basado en el Índice de Coincidencia (ICa un criptograma cifrado con un sistema de sustitución polialfabética con clave periódica, método de criptoanálisis desarrollado por William Friedman en 1920. Pues vamos allá con el ejemplo.

Supongamos que interceptamos el siguiente mensaje cifrado:
Longitud texto cifrado = 426.

Y supongamos también que creemos que, con casi toda certeza, el texto en claro está escrito en español y que sospechamos que se ha empleado para cifrarlo un sistema de sustitución monoalfabética o uno de sustitución polialfabética con clave periódica. Veamos que información podría aportarnos el IC.

En primer lugar recordar que el IC que se espera obtener de un texto escrito en español, o lo que es lo mismo la probabilidad de que dos letras tomadas al azar de un texto escrito en dicho idioma resulten ser iguales, debe estar próximo a 0,0775 y que en un sistema de cifrado de sustitución monoalfabética este IC se mantiene en el texto cifrado, mientras que si se emplea un sistema de cifrado de sustitución polialfabética éste será significativamente menor en el texto cifrado que en el texto en claro.

Pues bien, con la fórmula y siguiendo el procedimiento indicados en el post anterior obtenemos los siguientes resultados para cada una de las posibles longitudes de la clave:

- Longitud de la clave (t) = 1:

Se trataría realmente de un cifrado de sustitución monoalfabética, ya que todos los caracteres del texto en claro habrían sido cifrados por el alfabeto correspondiente al único carácter de la clave, por lo que calculamos el IC correspondiente a todo el texto cifrado (C).
IC(C) = 0,0487
Donde:
C: criptograma.

Tal y como se observa, este IC está bastante alejado del que se espera encontrar en un texto cifrado utilizando una sustitución monoalfabética, o lo que es lo mismo empleando una sustitución polialfabética con un período o longitud de la clave (t) igual a 1, por lo que podríamos descartar esta longitud de la clave.

Longitud de la clave (t) = 2:

Calculamos el IC de los dos subcriptogramas cuyos caracteres del texto en claro habrían sido cifrados con el alfabeto correspondiente a cada uno de los caracteres de la clave, respectivamente. En cada uno de ambos subcriptogramas el cifrado sería una sustitución monoalfabética.

Por tanto, calculamos:

IC(Ci) = IC(cici+tci+2tci+3t,...)

Donde:
t: período o longitud de la clave.
Ci: subcriptograma i-ésimo del que hay que calcular el IC (1 ≤ i ≤ t).
m: longitud del criptograma o mensaje cifrado.
ci: carácter i-ésimo del criptograma o texto cifrado (1 ≤ i ≤ m).

Es decir:

IC(C1) = IC(c1c3c5c7..., c425) = IC(GTIF... H).
IC(C2) = IC(c2c4c6c8,..., c426) = IC(DZUN... Q).

Obteniéndose como resultado:
IC(C1) = 0,0469
IC(C2) = 0,0504

Por tanto, en este caso también podemos descartar un cifrado polialfabético con periodo o longitud de la clave (t) igual a 2, ya que ambos IC están alejados del que se espera encontrar en un texto cifrado utilizando sustitución monoalfabética (en cada uno de los dos subcriptogramas).

Longitud de la clave (t) = 3:

De forma análoga que en el caso anterior calculamos:

IC(Ci) = IC(cici+tci+2tci+3t,...)

Donde:
t: período o longitud de la clave.
Ci: subcriptograma i-ésimo del que hay que calcular el IC (1 ≤ i ≤ t).
m: longitud del criptograma o mensaje cifrado.
ci: carácter i-ésimo del criptograma o texto cifrado (1 ≤ i ≤ m).

Es decir:

IC(C1) = IC(c1c4c7c10..., c424) = IC(GZFN... V).
IC(C2) = IC(c2c5c8c11,..., c425) = IC(DING... H).
IC(C3) = IC(c3c6c9c12,..., c426) = IC(TUZW... Q).

Obteniéndose como resultado:
IC(C1) = 0,0495
IC(C2) = 0,0460
IC(C3) = 0,0489

Por tanto, nuevamente podemos descartar un cifrado polialfabético con periodo o longitud de la clave (t) igual a 3, ya que el IC de los tres subcriptogramas está lejos del que se espera encontrar en un texto cifrado utilizando sustitución monoalfabética (en cada uno de los tres subcriptogramas).

Longitud de la clave (t) = 4:

Calculamos:

IC(Ci) = IC(cici+tci+2tci+3t,...)

Donde:
t: período o longitud de la clave.
Ci: subcriptograma i-ésimo del que hay que calcular el IC (1 ≤ i ≤ t).
m: longitud del criptograma o mensaje cifrado.
ci: carácter i-ésimo del criptograma o texto cifrado (1 ≤ i ≤ m).

Es decir:

IC(C1) = IC(c1c5c9c13..., c425) = IC(GIZP... H).
IC(C2) = IC(c2c6c10c14,..., c426) = IC(DUNG... Q).
IC(C3) = IC(c3c7c11c15,..., c423) = IC(TFGS... R).
IC(C4) = IC(c4c8c12c16,..., c424) = IC(ZNWF... V).

Obteniéndose como resultado:
IC(C1) = 0,0448
IC(C2) = 0,0441
IC(C3) = 0,0501
IC(C4) = 0,0602

En este caso también podemos descartar un cifrado polialfabético con periodo o longitud de la clave (t) igual a 4, ya que el IC de los cuatro subcriptogramas está lejos del que se espera encontrar en un texto cifrado utilizando sustitución monoalfabética (en cada uno de los cuatro subcriptogramas).

Longitud de la clave (t) = 5:

Volvemos a hacer los cálculos:

IC(Ci) = IC(cici+tci+2tci+3t,...)

Donde:
t: período o longitud de la clave.
Ci: subcriptograma i-ésimo del que hay que calcular el IC (1 ≤ i ≤ t).
m: longitud del criptograma o mensaje cifrado.
ci: carácter i-ésimo del criptograma o texto cifrado (1 ≤ i ≤ m).

Es decir:

IC(C1) = IC(c1c6c11c16..., c426) = IC(GUGF... Q).
IC(C2) = IC(c2c7c12c17,..., c422) = IC(DFWO... P).
IC(C3) = IC(c3c8c13c18,..., c423) = IC(TNPA... R).
IC(C4) = IC(c4c9c14c19,..., c424) = IC(ZZGO... V).
IC(C5) = IC(c5c10c15c20,..., c425) = IC(INSE... H).

Obteniéndose como resultado:
IC(C1) = 0,0728
IC(C2) = 0,0829
IC(C3) = 0,0826
IC(C4) = 0,0737
IC(C5) = 0,0770

Como se observa, el IC obtenido para cada subcriptograma se acerca bastante al que se espera encontrar en un texto cifrado correspondiente a un texto en claro escrito en español (0,0775) utilizando sustitución monoalfabética (en cada uno de los cinco subcriptogramas), por lo que podemos concluir que muy probablemente se trate de un cifrado de sustitución polialfabética con periodo o longitud de la clave (t) igual a 5.

Pero, antes de proceder a realizar un análisis de frecuencias de los caracteres de los cinco subcriptogramas, veamos qué resultado obtendríamos para la longitud de la clave si utilizamos el método Kasiski. Recordar que para ello, ver este post, hay que localizar secuencias de caracteres, de longitud 3 o mayor, repetidas en el criptograma, ya que dichas secuencias repetidas, con casi toda probabilidad, eran las mismas también antes del cifrado y la clave ha debido coincidir en la misma posición en el momento de cifrarlas. Con nuestro criptograma:
Es decir:

- 2 cadenas "GDT" separadas por 210 posiciones.
- 2 cadenas "IOOL" separadas por 155 posiciones.
- 2 cadenas "QFSC" separadas por 185 posiciones.
- 2 cadenas "OEE" separadas por 25 posiciones.
- 2 cadenas "COX" separadas por 340 posiciones.
- 2 cadenas "XMHCAYS" separadas por 120 posiciones.
- 2 cadenas "USS" separadas por 160 posiciones.
- 2 cadenas "ÑON" separadas por 185 posiciones.
- 2 cadenas "GXC" separadas por 40 posiciones.
- 2 cadenas "SYI" separadas por 20 posiciones.
- 2 cadenas "AGM" por 10 posiciones.
- 2 cadenas "GVOÑ" separadas por 15 posiciones.
- 2 cadenas "GEEVAQI" separadas por 30 posiciones.
- 2 cadenas "FORVW" separadas por 65 posiciones.

Por lo que la longitud más probable de la clave sería el máximo común divisor o mayor número entero que divide a todas esas posiciones sin dejar resto, es decir, mcd(10, 15, 20, 25, 30, 40, 65, 120, 155, 160, 185, 210, 340) = 5.

Circunstancia que nos viene a confirmar, casi con total seguridad, que el mensaje o texto en claro ha sido cifrado utilizando un sistema de sustitución polialfabética con clave periódica y longitud de la clave igual a 5.

Realicemos ahora el análisis de frecuencias sobre los caracteres de cada uno de los cinco subcriptogramas (en cada uno de ellos los caracteres del texto en claro habrían sido cifrados con una misma letra de la clave, es decir, en cada uno de ellos la sustitución realizada sería monoalfabética):
¿Qué información nos aporta este análisis de frecuencias?: el carácter más frecuente en cada subcriptograma es el candidato a ser la "E" en el texto en claro (la letra más frecuente en español), el siguiente más frecuente es el candidato a ser la "A" (la segunda letra más frecuente), el tercero es el candidato a ser la "O" (la tercera letra más frecuente) y así sucesivamente. Esto es así, con bastante probabilidad, para los caracteres más frecuentes en textos muy grandes (en un texto en español se espera encontrar aproximadamente: 13,68% de caracteres "E", 12,53% de caracteres "A" y 8,68% de caracteres "O",...), aunque en un texto no suficientemente extenso esto podría no ser necesariamente así, por lo que tendremos que afinar los resultados obtenidos en este análisis de frecuencias de las letras con los correspondientes al análisis de frecuencias de bigramas y trigramas.

En cualquier caso veamos que información podemos obtener en un primer análisis de las frecuencias obtenidas:

- En el primer subcriptograma (C1) yo diría que el número de ocurrencias de la letra "G" (16 veces), significativamente muy superior a cualquier otra, hace que lo más probable es que se corresponda con la "E" en el texto en claro y, además, creo que es razonable pensar que la "A" debe corresponderse con la "C", "F" o "O" (las letras que después de la "G" aparecen significativamente con mayor frecuencia, en 8 ocasiones cada una de ellas).

- En el segundo subcriptograma (C2) la letra "O" (16 veces) podría corresponderse con la "E" y la "C" (12 veces) con la "A".

- En el tercer subcriptograma (C3), a simple vista, reconozco un patrón que me resulta familiar: las tres letras que aparecen con significativa mayor frecuencia presentan el siguiente desplazamiento entre ellas: 0, +4, +11, pero es que además se da la circunstancia de que éstas son la "A", "E" y "O" (las tres letras más frecuentes en español). ¿Qué casualidad, no?. Pues no lo sé, pero a mí me hace pensar que esta doble "casualidad" podría indicarnos que el sistema empleado para cifrar el mensaje en claro bien podría ser el cifrado de Vigenère y, además, que el tercer carácter de la clave utilizada sería una "A" (según la tabla del citado método de cifrado la fila correspondiente a la letra "A" de la clave cifra el carácter del texto en claro como ese mismo carácter).

Si esto es así podríamos evitarnos realizar con mayor detalle el análisis de frecuencias, ya que estaríamos en disposición de obtener la clave y después descifrar el mensaje.

Veamos: si el sistema empleado para cifrar el mensaje ha sido el cifrado de Vigenère, ese desplazamiento (0, +4, +11) se mantendrá en todos los subcriptogramas para los caracteres cuya suma de sus frecuencias relativas sea la mayor (o cerca de ser la mayor); el primero se correspondería con la "A" en el texto en claro, el segundo con la "E" y el tercero con la "O", y conforme a la tabla que emplea este sistema el primero de esos caracteres se correspondería con el carácter de la clave. Es decir:

C1: La suma mayor de frecuencias teniendo en cuenta esa distribución (0, +4, +11) se corresponde con la de los caracteres:  fC + fG + fQ = (8 + 16 + 5) = 29, pero hay otra suma de frecuencias que se le aproxima: fG + fK + fU = (16 + 3 + 5) = 24, por lo que en este caso me surge la duda de si el primer carácter de la clave sería la "C" o la "G", aunque es más probable que sea la "C".

C2: La suma mayor de frecuencias teniendo en cuenta esa distribución (0, +4, +11) se corresponde con la de los caracteres:  fL + fO + fZ = (7 + 16 + 5) = 28 y con la de los caracteres: fO + fS + fD = (16 + 7 + 5) = 28, por lo que me surge la duda de si el segundo carácter de la clave sería la "L" o la "O", ambas letras con igual probabilidad de serlo.

C3: La suma mayor de frecuencias teniendo en cuenta esa distribución (0, +4, +11) se corresponde con la de los caracteres  fA + fE + fO = (14 + 10 + 10) = 34. No hay otros tres caracteres que cumplan con esa distribución cuya suma de sus frecuencias relativas sea mayor que ésta (ni siquiera que se le aproxime), lo que nos indica, con casi toda probabilidad, que la "A" se correspondería con la "A" en el texto en claro, la "E" con la "E" y la "O" con la "O", y que el tercer carácter de la clave (la fila de la tabla del cifrado de Vigenère con la que se habría cifrado el texto en claro) sería la "A".

C4: La suma mayor de frecuencias teniendo en cuenta esa distribución (0, +4, +11) se corresponde con la de los caracteres:  fZ + fD + fÑ = (11 + 10 + 7) = 28, pero hay otra suma de frecuencias que se le aproxima: fV + fZ + fK = (9 + 11 + 5) = 25, por lo que en este caso también me surge la duda de si el cuarto carácter de la clave sería la "Z" o la "V", aunque es más probable que sea la "Z".

C5: La suma mayor de frecuencias teniendo en cuenta esa distribución (0, +4, +11) se corresponde con la de los caracteres:  fE + fI + fS = (10 + 12 + 9) = 31pero hay otra suma de frecuencias que, aunque se encuentra algo alejada, apunto por si acaso: fI + fM + fW = (12 + 7 + 6) = 25, por lo que en este caso, aunque es más probable que el quinto carácter de la clave sea "E", anoto también la posibilidad de que sea "I". No obstante, no consideraré a esta última, al menos en un primer intento de averiguar cuál es la clave correcta.

Por tanto, tenemos 8 posibilidades para la clave empleada: "CLAZE", "COAZE", "CLAVE", "COAVE", "GLAZE", "GOAZE", "GLAVE" y "GOAVE".

A la vista de las claves más probables parece claro que la realmente empleada fue: "CLAVE", por lo que intentaré descifrar el mensaje utilizando ésta en primer lugar y, si no lo consigo, utilizaré las otras.

Con clave = "CLAVE" y utilizando la tabla del cifrado de Vigenère (caracteres del español, "Ñ" incluido) o, lo que es lo mismo, la expresión indicada en el post anterior para la función de descifrado (DK),  obtenemos el siguiente texto en claro: