El cifrado polialfabético es vulnerable al análisis de frecuencia de aparición de las letras. Para evitarlo se han desarrollado los cifrados poligráficos, que están basados en cifrar bloques de letras de una cierta longitud fija
El cifrado polialfabético supera la debilidad que tienen los cifrados monográficos al analizar la frecuencia de las letras
Para evitarlo se han desarrollado esquemas basados en cifrar bloques de letras de una cierta longitud fija
El cifrado Vigenère es un cifrado basado en diferentes series de caracteres o letras del cifrado del César formando estos caracteres una tabla, llamada tabla de Vigenère, que se usa como clave
El cifrado de Vigenère es un cifrado de sustitución simple polialfabético
El primer cifrado polialfabético fue el llamado cifrado de Alberti, creado por Leone Battista Alberti hacia 1467
Para facilitar los cálculos se aprovechaba de un disco de metal que permitía cambiar fácilmente entre los diferentes alfabetos disponibles
El sistema de Alberti sólo cambiaba entre alfabetos después de muchas palabras, y los cambios se indicaban escribiendo la letra del correspondiente alfabeto en el mensaje cifrado
Más tarde, en 1508, Johannes Trithemius, en su trabajo Poligraphia, inventó la tabula recta, que es básicamente la tabla de Vigenère
Trithemius, sin embargo, sólo proporcionó un progresivo, rígido y predecible sistema de cambio entre alfabetos
Lo que ahora se conoce como el cifrado de Vigenère fue originalmente descrito en 1533 por Giovan Battista Belasso en su libro La cifra del Sig. quien construyó el cifrado basándose en la tabula recta de Trithemius, pero añadió una clave repetida para cambiar cada carácter entre los diferentes alfabetos
Blaise de Vigenère publicó su descripción de un cifrado de autoclave parecido, pero más robusto, antes del reinado de Enrique III de Francia, en 1586
Más tarde, en el siglo XIX, la invención del cifrado dejó de atribuirse a Vigenère
El cifrado Vigenère ganó una gran reputación por ser excepcionalmente robusto
Incluso el escritor y matemático Charles Lutwidge Dodgson (más conocido como Lewis Carroll) dijo que el cifrado Vigenère era irrompible en el artículo The Alphabet Cipher para una revista de niños
En 1917, Scientific American describió el cifrado Vigenère como imposible de romper
Esta reputación fue mantenida hasta que el método Kasiski resolvió el cifrado en el siglo XIX y algunos criptoanalistas habilidosos pudieron romperlo en varias ocasiones en el siglo XVI
El cifrado Vigenère es lo suficientemente simple si se usa con discos de cifrado. Los Estados confederados de América, por ejemplo, utilizaron un disco de cifrado para implementar el cifrado Vigenère durante la Guerra Civil estadounidense
Los mensajes confederados fueron poco secretos, ya que los miembros de la Unión solían descifrar los mensajes
Gilbert Vernam trató de arreglar el cifrado (creando el cifrado Vernam-Vigenère en 1918), pero no importa lo que hiciera, el cifrado sigue siendo vulnerable al criptoanálisis (No hay que confundirlo con el cifrado de Vernam)
A lo largo de este articulo usaré por simplicidad el alfabeto inglés estándar de 26 letras:
\tiny\begin{pmatrix} 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17& 18& 19& 20& 21& 22& 23& 24& 25 \\ 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 \\ \end{pmatrix}
Y el siguiente cuadro correspondiente al cifrado de Vigenère
El cifrado puede expresarse con la siguiente fórmula:
M(X_i)=(X_i+K_i-1)\pmod{L}
Donde X_i es la letra en la posición i del texto a cifrar, K_i es el carácter de la clave correspondiente a X_i, pues se encuentran en la misma posición, y L es el tamaño del alfabeto. En este caso L = 26
Para descifrar realizaremos la operación inversa:
D(C_i)=(C_i-K_i+1)\pmod{L}
Donde C_i es el carácter en la posición i del texto cifrado, K_i viene siendo el carácter de la clave correspondiente a C_i, y L el tamaño del alfabeto
Hay que tener en cuenta que a una misma letra en el texto en claro le pueden corresponder diferentes letras en el texto cifrado
Tenemos el siguiente mensaje que queremos cifrar:
C=MENSAJE ENVIADO AYER
L = 26 porque vamos a usar el alfabeto inglés
Tomamos como clave:
K = ESTOY ABURRIDO
Es aconsejable que la clave sea de tamaño inferior al mensaje. Juntamos mensaje y clave, repitiendo tantas veces como sea necesaria la clave
\tiny\begin{pmatrix} M& E& N& S& A& J& E& E& N& V& I& A& D& O& A& Y& E& R \\ E& S& T& O& Y& A& B& U& R& R& I& D& O& E& S& T& O& Y \\ \end{pmatrix}
Vamos a la tabla de cifrado y tomamos la fila de la primera letra de la palabra clave en la tabla de Vigénere y la columna de la primera letra del mensaje
La intersección de ambas será la letra que se usará para cifrado
Repetiremos el proceso hasta obtener el mensaje cifrado
Así nos queda que el mensaje cifrado es:
M=QWGGYJFYEMQDRSSRSP
Desciframos el M anterior
Vamos a la tabla de cifrado y tomamos la columna de la primera letra de la palabra clave en la tabla de Vigénere y buscamos la primera letra del mensaje
La fila de la intersección de ambas será la letra que se usará en el mensaje descifrado
Repetiremos el proceso hasta obtener el mensaje en claro
\tiny\begin{pmatrix} E& S& T& O& Y& A& B& U& R& R& I& D& O& E& S& T& O& Y \\ Q& W& G& G& Y& J& F& Y& E& M& Q& D& R& S& S& R& S& P \\ \end{pmatrix}
Obteniendo el C original:
C=MENSAJEENVIADOAYER
El cifrado de Gronsfeld surgió como una mejora al cifrado Vigenère, ya que era susceptible a un análisis críptico con ciertas condiciones previstas. Al evaluar algunas características, era posible definir la longitud de la clave, y luego, al analizar las filas de letras, cifradas por la misma fila de la tabla, uno podía emplear un método estándar basado en la frecuencia de ciertas letras del lenguaje
El primero en efectuar un ataque exitoso en la modificación del cifrado Vigenère en 1854, fue Charles Babbage, un pionero de la informática, pero el análisis fue publicado nueve meses después por otro investigador, Friedrich Kasiski
Por más extraño que parezca, esto ayudó a fortalecerlo, dando lugar al cifrado de Gronsfeld. Una de las mejoras fue el uso de la palabra clave, el cual es igual a la longitud del propio mensaje, eliminando de este modo, la posibilidad de un análisis de frecuencia
Sin embargo, esta actualización trajo otra vulnerabilidad: el uso de texto sensible como frase clave, aportaba al criptoanalista información estadística sobre la clave, sirviendo como una pista al momento de querer descifrar el texto
Como está basado en el cifrado Vigenère, es también un cifrado de sustitución simple polialfabético. Esto significa que se usa más de un alfabeto cifrado para poner en clave el mensaje y que se cambia de uno a otro según se pasa de una letra del texto en claro a otra. Es decir que deben tenerse un conjunto de alfabetos cifrados y una forma de hacer corresponder cada letra del texto original con uno de ellos
El número de alfabetos cifrado está limitado a 10, codificados del 0 al 9 y la clave se genera con una combinación de esos dígitos, sin repeticiones. Altera la frecuencia de las letras del texto, pues por ejemplo la letra más corriente en castellano, la E, se cifra de forma diferente según su posición en el texto original
A lo largo de este articulo usaré por simplicidad el alfabeto inglés estándar de 26 letras:
\tiny\begin{pmatrix} 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17& 18& 19& 20& 21& 22& 23& 24& 25 \\ 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 \\ \end{pmatrix}
Y el siguiente cuadro correspondiente al cifrado de Gronsfeld
este cuadro no es el único posible, se ha usado como desplazamiento los 9 primeros números primos, pudiendo usar otro método para crear los 10 alfabetos
Tenemos el siguiente mensaje que queremos cifrar:
C=MENSAJE ENVIADO AYER
Tomamos como clave:
K = 1203456987
Es aconsejable que la clave sea de tamaño inferior al mensaje. Juntamos mensaje y clave, repitiendo tantas veces como sea necesaria la clave
\tiny\begin{pmatrix} M& E& N& S& A& J& E& E& N& V& I& A& D& O& A& Y& E& R \\ 1& 2& 0& 3& 4& 5& 6& 9& 8& 7& 1& 2& 0& 3& 4& 5& 6& 9 \\ \end{pmatrix}
Vamos a la tabla de cifrado y tomamos la fila del primer número de la clave en la tabla de Gronsfeld y la columna de la primera letra del mensaje. La intersección de ambas será la letra que se usará para cifrado. Repetiremos el proceso hasta obtener el mensaje cifrado
Así nos queda que el mensaje cifrado es:
M=PJPZLWVGKOLFFVLLVT
Desciframos el M anterior
Vamos a la tabla de cifrado y tomamos la fila del primer número de la clave en la tabla de Gronsfeld y buscamos la primera letra del mensaje. La fila de la intersección de ambas será la letra que se usará en el mensaje descifrado. Repetiremos el proceso hasta obtener el mensaje en claro
\tiny\begin{pmatrix} 1& 2& 0& 3& 4& 5& 6& 9& 8& 7& 1& 2& 0& 3& 4& 5& 6& 9 \\ P& J& P& Z& L& W& V& G& K& O& L& F& F& V& L& L& V& T \end{pmatrix}
Obteniendo el C original:
C=MENSAJEENVIADOAYER
Este sistema está basado en el álgebra lineal y es muy importante en la historia de la criptografía. Fue Inventado por Lester S. Hill en 1929, y fue el primer sistema criptográfico polialfabético que trabajaba con más de tres símbolos simultáneamente
Este sistema es polialfabético pues puede darse que un mismo carácter en un mensaje a enviar se cifra en dos caracteres distintos en el mensaje encriptado
Quisiera empezar con un sistema muy sencillo que puede explicarse matemáticamente hablando mediante aritmética modular. A lo largo de este articulo usaré por simplicidad el alfabeto inglés estándar de 26 letras:
\tiny\begin{pmatrix} 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17& 18& 19& 20& 21& 22& 23& 24& 25 \\ 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 \\ \end{pmatrix}
Se elige un entero d que determina bloques de d elementos que serán tratados como un vector de d dimensiones. De forma aleatoria, se elige una matriz de d × d elementos los cuales serán la clave a utilizar. Los elementos de la matriz d × d serán enteros entre 0 y 25, además la matriz M debe ser invertible en \mathbb{Z}^n_{26}
Para la encriptación, el texto es dividido en bloques de d elementos los cuales se multiplican por la matriz d × d. Así M\cdot P_i \equiv C \pmod{26} donde hemos asignado a la A el número 0 a la B el 1, … , a la Z el 25, y \pmod{26} indica que debemos tomar el resto de dividir por 26 (en lenguaje C utilizamos el operador % ) M es la matriz d x d, C es el texto cifrado y P el original
CODIGO rompemos la estructura en bloques de 3 caracteres cada uno (en este caso d = 3), eliminando signos ortográficos si los hubiera y obtenemos los equivalentes numéricos de estas letras
P_1=COD=\begin{pmatrix} 2 \\ 14 \\ 3 \end{pmatrix}, P_2=IGO=\begin{pmatrix} 8 \\ 6 \\ 14 \end{pmatrix}
Elegimos M=\begin{pmatrix} 5& 17& 20 \\ 9& 23& 3& \\ 2& 11& 13 \end{pmatrix} como matriz de claves
Antes de aplicar el cifrado debemos asegurarnos de que M es invertible \mod{26}. Hay una forma relativamente sencilla de averiguar esto a través del cálculo del determinante. Si el determinante de la matriz es 0 o tiene factores comunes con el módulo (en el caso de 26 los factores son 2 y 13), entonces la matriz no puede utilizarse. Al ser 2 uno de los factores de 26 muchas matrices no podrán utilizarse (no servirán todas en las que su determinante sea 0, un múltiplo de 2 o un múltiplo de 13)
\det(M) = \begin{vmatrix} 5& 17& 20 \\ 9& 23& 3& \\ 2& 11& 13 \end{vmatrix} = 5 \cdot(23 \cdot 13 - 3 \cdot 11) - 17 \cdot (9 \cdot 13 - 3 \cdot 2) + 20 \cdot (9 \cdot 11 - 23 \cdot 2) =
= 1215 - 1734 + 1060 = 503
Ahora comprobamos \pmod{26}:
503 = 9\pmod{26}
La matriz A es invertible en \mod{26}, ya que 26 y 9 son coprimos
Calculamos el primer bloque:
M\cdot P_1=\begin{pmatrix} 5& 17& 20 \\ 9& 23& 3& \\ 2& 11& 13 \end{pmatrix}\cdot \begin{pmatrix} 2 \\ 14 \\ 3 \end{pmatrix} = \begin{pmatrix} 308 \\ 349 \\ 197 \end{pmatrix}
\begin{pmatrix} 308 \\ 349 \\ 197 \end{pmatrix} = \begin{pmatrix} 22 \\ 11 \\ 15 \end{pmatrix}\pmod{26}
\begin{pmatrix} 22 \\ 11 \\ 15 \end{pmatrix} = WLP
Así el mensaje cifrado del bloque uno es:
C_1=WLP
Calculamos el segundo bloque:
M\cdot P_2=\begin{pmatrix} 5& 17& 20 \\ 9& 23& 3& \\ 2& 11& 13 \end{pmatrix}\cdot \begin{pmatrix} 8 \\ 6 \\ 14 \end{pmatrix} = \begin{pmatrix} 422 \\ 252 \\ 264 \end{pmatrix}
\begin{pmatrix} 422 \\ 252 \\ 264 \end{pmatrix} = \begin{pmatrix} 6 \\ 18 \\ 4 \end{pmatrix}\pmod{26}
\begin{pmatrix} 6 \\ 18 \\ 4 \end{pmatrix} = GSE
Así el mensaje cifrado del bloque uno es:
C_2=GSE
Unimos ambos mensajes cifrados para obtener el mensaje cifrado C:
C=WLPGSE
Desciframos el C anterior, el método es el mismo, pero necesitamos calcular M^{-1}. Para ello lo calculamos a partir de esta fórmula:
M^{-1}=C^t\cdot (\det(M))^{-1}
Donde C^t es la matriz de cofactores de M transpuesta y (\det(M))^{-1} debe realizarse como \mod{26}, que en este caso es 3 ya que:
9\pmod{26} \cdot 3\pmod{26}=27 \pmod{26}=1 \pmod{26}
Calculamos los cofactores de M
C_{1 1}= + \begin{vmatrix} 23& 3 \\ 11& 13 \end{vmatrix} C_{1 2}= - \begin{vmatrix} 9& 3 \\ 2& 13 \end{vmatrix} C_{1 3}= + \begin{vmatrix} 9& 23 \\ 2& 11 \end{vmatrix}
C_{2 1}= - \begin{vmatrix} 17& 20 \\ 11& 13 \end{vmatrix} C_{2 2}= + \begin{vmatrix} 5& 20 \\ 2& 13 \end{vmatrix} C_{2 3}= - \begin{vmatrix} 5& 17 \\ 2& 11 \end{vmatrix}
C_{3 1}= + \begin{vmatrix} 17& 20 \\ 23& 3 \end{vmatrix} C_{3 2}= - \begin{vmatrix} 5& 20 \\ 9& 3 \end{vmatrix} C_{3 3}= + \begin{vmatrix} 5& 17 \\ 9& 23 \end{vmatrix}
C=\begin{pmatrix} 266& -111& 53 \\ -1& 25& -21& \\ -409& 165& -38 \end{pmatrix} C^t= \begin{pmatrix} 266& -1& -409 \\ -111& 25& 165 \\ 53& -21& -38 \end{pmatrix}
Ahora aplicamos la fórmula de la inversa:
M^{-1}=C^t\cdot (\det(M))^{-1}=\begin{pmatrix} 266& -1& -409 \\ -111& 25& 165 \\ 53& -21& -38 \end{pmatrix} \cdot 3=\begin{pmatrix} 798& -3& -1227 \\ -333& 75& 495 \\ 159& -63& -114 \end{pmatrix}
M^{-1}\pmod{26}=\begin{pmatrix} 798& -3& -1227 \\ -333& 75& 495 \\ 159& -63& -114 \end{pmatrix} \pmod{26} =\begin{pmatrix} 18& 23& 21 \\ 5& 23& 1 \\ 3& 15& 16 \end{pmatrix}
Calculamos el primer bloque:
M\cdot P_1=\begin{pmatrix} 18& 23& 21 \\ 5& 23& 1& \\ 3& 15& 16 \end{pmatrix}\cdot \begin{pmatrix} 22 \\ 11 \\ 15 \end{pmatrix} = \begin{pmatrix} 964 \\ 378 \\ 471 \end{pmatrix}
\begin{pmatrix} 964 \\ 378 \\ 471 \end{pmatrix} = \begin{pmatrix} 2 \\ 14 \\ 3 \end{pmatrix}\pmod{26}
\begin{pmatrix} 2 \\ 14 \\ 3 \end{pmatrix} = COD
Así el mensaje cifrado del bloque uno es:
P_1=COD
Calculamos el segundo bloque:
M\cdot P_2=\begin{pmatrix} 18& 23& 21 \\ 5& 23& 1& \\ 3& 15& 16 \end{pmatrix}\cdot \begin{pmatrix} 6 \\ 18 \\ 4 \end{pmatrix} = \begin{pmatrix} 606 \\ 448 \\ 352 \end{pmatrix}
\begin{pmatrix} 606 \\ 448 \\ 352 \end{pmatrix} = \begin{pmatrix} 8 \\ 6 \\ 14 \end{pmatrix}\pmod{26}
\begin{pmatrix} 8 \\ 6 \\ 14 \end{pmatrix} = IGO
Así el mensaje cifrado del bloque uno es:
P_2=IGO
Unimos ambos mensajes cifrados para obtener el mensaje cifrado C: