Cifrado monoalfabético

Un sistema de cifrado es monoalfabético cuando cada carácter se sustituye siempre por un determinado carácter del alfabeto del texto cifrado

Desde la antigüedad hasta nuestros días se han mandado mensajes secretos

La necesidad de comunicarse secretamente ha ocurrido en la diplomacia y entre militares

Con la llegada de las comunicaciones electrónicas el interés por mantener mensajes ininteligibles para todos salvo el receptor no ha hecho sino aumentar

Para introducir unos términos antes de entrar en materia, diremos que criptología es la disciplina dedicada a comunicarse secretamente

Criptografía es la parte de la criptología que trata del diseño e implementación de sistemas secretos y criptoanálisis la que se dedica a romper dichos sistemas

Quisiera empezar con un sistema muy sencillo que puede explicarse matemáticamente hablando mediante aritmética modular

Quizás el primero de estos sistemas tuvo su origen con Julio César, su cifrado consistía simplemente en sustituir una letra por la situada tres lugares más allá en el alfabeto esto es la A se transformaba en D, la B en E y así sucesivamente hasta que la Z se convertía en C

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}

Lo cual es suficiente para la mayoría de los cifrados basados en texto y tiene la ventaja de que ocupan posiciones sucesivas en el código ASCII lo que lo hace muy ventajoso para programar

Pues bien, el cifrado de Julio César podría expresarse así C\equiv P+3\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 % ) C es el texto cifrado y P el original

Frecuencia de letras

En el criptoanálisis de algunos métodos clásicos es interesante conocer la frecuencia de letras, pares de letras y palabras en el idioma en que suponemos que está escrito dicho mensaje

He aquí algunos datos útiles para el idioma español:

Letras de alta frecuencia

Letra	Frecuencia %
E	16,78
A	11,96
O	8,69
L	8,37
S	7,88
N	7,01
D	6,87

 

Letras de frecuencia media

Letra	Frecuencia %
R	4,94
U	4,80
I	4,15
T	3,31
C	2,92
P	2,76
M	2,12

 

Letras de frecuencia baja

Letra	Frecuencia %
Y	1,54
Q	1,53
N	0,92
H	0,89

El resto de las letras G, F, V, W, J, Z, X, K y Ñ tienen frecuencias inferiores a 0,5% y se pueden considerar por tanto «raras»

Resumiendo los datos anteriores y aplicándolos por grupos de letras podríamos decir que:

• Las vocales ocupan alrededor del 47% del texto
• Sólo la E y la A se identifican con relativa fiabilidad porque destacan mucho sobre las demás
• Las letras de frecuencia alta suponen un 68% del total
• Las consonantes más frecuentes son L, S, N, D (alrededor del 30%)
• Las letras menos frecuentes son G, F, V, W, J, Z, X, K y Ñ (poco más del 1%)

Palabras más frecuentes

Palabra	Frecuencia (por diez mil)
DE	778
LA	460
EL	339
EN	302
QUE	289
Y	226
A	213
LOS	196
DEL	156
SE	119
LAS	114

 

Palabras de dos letras

Palabra	Frecuencia (por diez mil)
DE	778
LA	460
EL	339
EN	302
SE	119
UN	98
NO	74
SU	64
AL	63
ES	47

 

Palabras de tres letras

Palabra	Frecuencia (por diez mil)
QUE	289
LOS	196
DEL	156
LAS	114
PAR	110
CON	82
UNA	78
MAS	36
SUS	27
HAN	19

 

Palabras de cuatro letras

Palabra	Frecuencia (por diez mil)
PARA	67
COMO	36
AYER (*)	25
ESTE	23
PERO	18
ESTA	17
AÑOS (*)	14
TODO	11
SIDO	11
SOLO	10

(*) Estas palabras parecen exageradamente frecuentes, lo que se debe al tipo de textos elegidos para la estadística

Ejemplo de cifrado monoalfabético

MENSAJE ENVIADO AYER rompemos la estructura en palabras del mensaje eliminando signos ortográficos si los hubiera, poniendo por ejemplo MENSAJEENVIADOAYER y obtenemos los equivalentes numéricos de estas letras:

\tiny\begin{pmatrix} 12& 4& 13& 18& 0& 9& 4& 4& 13& 21& 8& 0& 3& 14& 0& 24& 4& 17 \\ M& E& N& S& A& J& E& E& N& V& I& A& D& O& A& Y& E& R \\ \end{pmatrix}

aplicando la transformación P+3\pmod{26} se convierten en

\tiny\begin{pmatrix} 15& 7& 16& 21& 3& 12& 7& 7& 16& 24& 11& 3& 6& 17& 3& 1& 7& 20 \\ P& H& Q& V& D& M& H& H& Q& Y& L& D& G& R& D& B& H& U \\ \end{pmatrix}

es decir el mensaje cifrado es ahora PHQVDMHHQYLDGRDBHU

Un cifrado de este tipo es ridículamente fácil de romper (pero recordad que también fue muy fácil de hacer), basta con probar los 25 posibles desplazamientos desde P + 1 hasta P + 25 y con una ojeada sabremos cual es el mensaje

Hemos utilizado en este caso un criptoanálisis llamado de «fuerza bruta» porque probamos todas las claves (en este caso desplazamientos) posibles

Hay algunas formas de mejorar este método sin complicarlo demasiado, la primera se basa en elegir una palabra clave con todas sus letras diferentes, supongamos que elegimos VIRTUAL ZONE

Escribimos entonces el alfabeto normal junto con el transformado siguiente:

\tiny\begin{pmatrix} 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 \\ V& I& R& T& U& A& L& Z& O& N& E& B& C& D& F& G& H& J& K& M& P& Q& S& W& X& Y \\ \end{pmatrix}

y ahora el mensaje junto con el cifrado sería

\tiny\begin{pmatrix} M& E& N& S& A& J& E& E& N& V& I& A& D& O& A& Y& E& R \\ C& U& D& K& V& N& U& U& D& Q& O& V& T& F& V& X& U& J \\ \end{pmatrix}

ahora un ataque de fuerza bruta es «algo» más costoso pues se debería intentar con todos los alfabetos de sustitución posibles que son 26!=403291461126605635584000000 o sea unos cuantos más que los 25 de antes

Este método tiene la siguiente debilidad: con ciertas claves, las letras finales del alfabeto quedan sin modificar y esto facilita mucho la labor del criptoanalista

La clave en nuestro ejemplo está escogida de modo que aparezcan en ella letras como V, U, Z cercanas al final del alfabeto y que producen un mayor «desorden» en el alfabeto transformado

En todo caso en un cifrado como este se utiliza lo que se llama un análisis de frecuencias. Consiste en: sabiendo la frecuencia de las letras en español (si no sabes en qué idioma en que está escrito el original te puede costar más trabajo) intentar adivinar a que letra corresponde cada una de ellas

Por ejemplo en el último mensaje cifrado CUDKVNUUDQOVTFVXUJ se observa que la letra más repetida es la U, como la letra más frecuente en español es la E podríamos conjeturar que U se corresponde con la E como en efecto así es, siguiendo con las demás letras pueden averiguarse las suficientes como para poder leer el mensaje original

Cifrado del César

En el siglo I A. C. aparece un cifrador básico conocido con el nombre genérico de cifrado del César en honor al emperador Julio César y en el que ya se aplica una transformación al texto en claro de tipo monoalfabética

El cifrador del César aplica un desplazamiento constante de b caracteres al texto en claro

Ejemplo de cifrado del César

Tomamos b igual a 3, de forma que el alfabeto de cifrado es el mismo que el alfabeto del texto en claro pero desplazado 3 espacios hacia la derecha módulo n, con n el número de letras del mismo

Para cifrar usaremos:

C_i\equiv(M_i+b)\pmod{n}

Para descifrar usaremos:

M_i\equiv(C_i+n-b)\pmod{n}

En el alfabeto castellano, como hay 27 letras, n será 27

Tenemos el siguiente mensaje que queremos cifrar:

C=MENSAJE ENVIADO AYER

Sus caracteres en claro corresponden a la siguiente matriz:

\tiny\begin{pmatrix} 12& 4& 13& 19& 0& 9& 4& 4& 13& 22& 8& 0& 3& 15& 0& 25& 4& 18 \\ M& E& N& S& A& J& E& E& N& V& I& A& D& O& A& Y& E& R \\ \end{pmatrix}

Obtenemos los siguientes resultados:

\begin{array}{l} (12+3)\pmod{27}\equiv 15 \\ (4+3)\pmod{27}\equiv 7 \\ (13+3)\pmod{27}\equiv 16 \\ (19+3)\pmod{27}\equiv 22 \\ (0+3)\pmod{27}\equiv 3 \\ (9+3)\pmod{27}\equiv 12 \\ (4+3)\pmod{27}\equiv 7 \\ (4+3)\pmod{27}\equiv 7 \\ (13+3)\pmod{27}\equiv 16 \\ (22+3)\pmod{27}\equiv 25 \\ (8+3)\pmod{27}\equiv 11 \\ (0+3)\pmod{27}\equiv 3 \\ (3+3)\pmod{27}\equiv 6 \\ (15+3)\pmod{27}\equiv 18 \\ (0+3)\pmod{27}\equiv 3 \\ (25+3)\pmod{27}\equiv 1 \\ (4+3)\pmod{27}\equiv 7 \\ (18+3)\pmod{27}\equiv 21 \end{array}

aplicando la transformación P+3\pmod{27} se convierten en

\tiny\begin{pmatrix} 15& 7& 16& 22& 3& 12& 7& 7& 16& 25& 11& 3& 6& 18& 3& 1& 7& 21 \\ O& H& P& V& D& M& H& H& P& Y& L& D& G& R& D& B& H& U \\ \end{pmatrix}

Así el mensaje cifrado es: M=OHPVDMHHPYLDGRDBHU

Desciframos el M anterior:

\begin{array}{l} (15+27-3)\pmod{27}\equiv 12 \\ (7+27-3)\pmod{27}\equiv 4 \\ (16+27-3)\pmod{27}\equiv 13 \\ (22+27-3)\pmod{27}\equiv 19 \\ (3+27-3)\pmod{27}\equiv 0 \\ (12+27-3)\pmod{27}\equiv 9 \\ (7+27-3)\pmod{27}\equiv 4 \\ (7+27-3)\pmod{27}\equiv 4 \\ (16+27-3)\pmod{27}\equiv 13 \\ (25+27-3)\pmod{27}\equiv 22 \\ (11+27-3)\pmod{27}\equiv 8 \\ (3+27-3)\pmod{27}\equiv 0 \\ (6+27-3)\pmod{27}\equiv 3 \\ (18+27-3)\pmod{27}\equiv 15 \\ (3+27-3)\pmod{27}\equiv 0 \\ (1+27-3)\pmod{27}\equiv 25 \\ (7+27-3)\pmod{27}\equiv 4 \\ (21+27-3)\pmod{27}\equiv 18 \end{array}

Obteniendo el c original: C=MENSAJEENVIADOAYER

Este sistema de cifrado sencillo, apropiado e incluso bastante ingenioso para la época, presenta un nivel de seguridad muy débil

Criptoanálisis del cifrado del César

Al producirse una sustitución fija de cada carácter del alfabeto en claro por un único carácter del alfabeto de cifrado, el criptograma podrá romperse fácilmente aplicando técnicas de estadística del lenguaje, siempre y cuando contemos con una cantidad suficiente de texto cifrado

La distancia de unicidad viene dada por la relación entre la entropía de la clave H(K) y la redundancia del lenguaje D. Por tanto, si n = 27, existirán sólo 26 posibles combinaciones de alfabetos, por lo tanto H(K)=\log_2{26}=4,70

Como la redundancia D era igual a 3,4 entonces se tiene que N=\frac{H(K)}{D}\approx\frac{4,70}{3,4}\approx 1,38. Por lo tanto, necesitamos como mínimo 2 caracteres

Una forma elemental de criptoanálisis consiste en escribir bajo el texto cifrado todas las combinaciones de frases, con o sin sentido, que se obtienen al aplicar a dicho criptograma desplazamientos de 1, \cdots, n-1 caracteres, siendo n el número de caracteres del alfabeto utilizado. Una de estas combinaciones dará con el texto en claro y esto será válido independientemente del valor asignado a la constante de desplazamiento

b	Cifrado
1	PIQWENIIQZMEHSECIV
2	QJRXFÑJJRANFITFDJW
3	RKSYGOKKSBÑGJUGEKX
4	SLTZHPLLTCOHKVHFLY
5	TMUAIQMMUDPILWIGMZ
6	UNVBJRNNVEQJMXJHNA
7	VÑWCKSÑÑWFRKNYKIÑB
8	WOXDLTOOXGSLÑZLJOC
9	XPYEMUPPYHTMOAMKPD
10	YQZFNVQQZIUNPBNLQE
11	ZRAGÑWRRAJVÑQCÑMRF
12	ASBHOXSSBKWORDONSG
13	BTCIPYTTCLXPSEPÑTH
14	CUDJQZUUDMYQTFQOUI
15	DVEKRAVVENZRUGRPVJ
16	EWFLSBWWFÑASVHSQWK
17	FXGMTCXXGOBTWITRXL
18	GYHNUDYYHPCUXJUSYM
19	HZIÑVEZZIQDVYKVTZN
20	IAJOWFAAJREWZLWUAÑ
21	JBKPXGBBKSFXAMXVBO
22	KCLQYHCCLTGYBNYWCP
23	LDMRZIDDMUHZCÑZXDQ
24	MENSAJEENVIADOAYER
25	NFÑTBKFFÑWJBEPBZFS
26	ÑGOUCLGGOXKCFQCAGT

Es fácil deducir que un sistema de cifrado por sustitución monoalfabética como el del César presenta un nivel de seguridad mínimo en tanto que para romperlo nos ha bastado con un lápiz, papel y un poco de paciencia para confeccionar el cuadro anterior, nada del otro mundo

Esta debilidad se debe a que el número de desplazamientos posibles es muy pequeño, al contar sólo con los 26 valores que corresponden a los caracteres del alfabeto; esto es, se cumple que 1\leq b\leq 26, pues un desplazamiento igual a cero o bien múltiplo de veintisiete sería igual que transmitir en claro

Se cumplirá por tanto la siguiente operación de descifrado D a partir de un cifrado E en el anillo n:

D_b=E_{n-b}\Rightarrow D_3=E_{27-3}=E_{24}

Cifrado del César con clave

El cifrado del César con clave surge para aumentar la seguridad del cifrado del César, es decir, la distancia de unicidad, incluimos en el alfabeto de cifrado una clave k que consiste en una palabra o frase que se escribe a partir de una posición p_0 del alfabeto en claro

Los caracteres repetidos de la clave no se utilizan. Una vez posicionada la clave en la posición indicada, se añaden las demás letras del alfabeto en orden y de forma modular, para obtener así el alfabeto de cifrado

En este tipo de cifrado se deja de cumplir la condición de desplazamiento constante

Ejemplo de cifrado del César con clave

Tomamos p_0 = 3 y la clave va a ser:

k = ESTOY ABURRIDO

Para cifrar usaremos:

C_i\equiv(M_i+b)\pmod{n}

Para descifrar usaremos:

M_i\equiv(C_i+n-b)\pmod{n}

En el alfabeto castellano, como hay 27 letras, n será 27

Tenemos el siguiente mensaje que queremos cifrar:

C=MENSAJE ENVIADO AYER

Sus caracteres en claro corresponden a la siguiente matriz:

A la matriz anterior le añadimos la clave, teniendo en cuenta que hay que eliminar los repetidos

Ahora le añadimos las demás letras del alfabeto en orden y de forma modular, para obtener así el alfabeto de cifrado completo

Obtenemos los siguientes resultados:

\begin{array}{l} (12+3)\pmod{27}\equiv 15 \\ (4+3)\pmod{27}\equiv 7 \\ (13+3)\pmod{27}\equiv 16 \\ (19+3)\pmod{27}\equiv 22 \\ (0+3)\pmod{27}\equiv 3 \\ (9+3)\pmod{27}\equiv 12 \\ (4+3)\pmod{27}\equiv 7 \\ (4+3)\pmod{27}\equiv 7 \\ (13+3)\pmod{27}\equiv 16 \\ (22+3)\pmod{27}\equiv 25 \\ (8+3)\pmod{27}\equiv 11 \\ (0+3)\pmod{27}\equiv 3 \\ (3+3)\pmod{27}\equiv 6 \\ (15+3)\pmod{27}\equiv 18 \\ (0+3)\pmod{27}\equiv 3 \\ (25+3)\pmod{27}\equiv 1 \\ (4+3)\pmod{27}\equiv 7 \\ (18+3)\pmod{27}\equiv 21 \end{array}

aplicando la transformación P+3\pmod{27} y consultando la segunda parte de la matriz se convierten en

\tiny\begin{pmatrix} 15& 7& 16& 22& 3& 12& 7& 7& 16& 25& 11& 3& 6& 18& 3& 1& 7& 21 \\ F& Y& G& N& E& I& Y& Y& G& Q& R& E& O& J& E& X& Y& M \\ \end{pmatrix}

Así nos queda que el mensaje cifrado es:

M=FYGNEIYYGQREOJEXYM

Desciframos el M anterior:

\begin{array}{l} (15+27-3)\pmod{27}\equiv 12 \\ (7+27-3)\pmod{27}\equiv 4 \\ (16+27-3)\pmod{27}\equiv 13 \\ (22+27-3)\pmod{27}\equiv 19 \\ (3+27-3)\pmod{27}\equiv 0 \\ (12+27-3)\pmod{27}\equiv 9 \\ (7+27-3)\pmod{27}\equiv 4 \\ (7+27-3)\pmod{27}\equiv 4 \\ (16+27-3)\pmod{27}\equiv 13 \\ (25+27-3)\pmod{27}\equiv 22 \\ (11+27-3)\pmod{27}\equiv 8 \\ (3+27-3)\pmod{27}\equiv 0 \\ (6+27-3)\pmod{27}\equiv 3 \\ (18+27-3)\pmod{27}\equiv 15 \\ (3+27-3)\pmod{27}\equiv 0 \\ (1+27-3)\pmod{27}\equiv 25 \\ (7+27-3)\pmod{27}\equiv 4 \\ (21+27-3)\pmod{27}\equiv 18 \end{array}

Consultamos la primera parte de la matriz

\tiny\begin{pmatrix} 12& 4& 13& 19& 0& 9& 4& 4& 13& 22& 8& 0& 3& 15& 0& 25& 4& 18 \\ M& E& N& S& A& J& E& E& N& V& I& A& D& O& A& Y& E& R \\ \end{pmatrix}

Obteniendo el C original:

C=MENSAJEENVIADOAYER

Al tener un mayor número de combinaciones de alfabetos, existe una mayor incertidumbre respecto de la clave. La distancia de unicidad de este cifrador será mayor y, por consiguiente, el sistema presentará una mayor fortaleza

Criptoanálisis del cifrado del César con clave

Es imposible establecer una relación matemática única y directa entre el alfabeto en claro y el alfabeto de cifrado. El único camino que nos queda consiste en llevar las estadísticas del lenguaje al criptograma, observando por ejemplo la frecuencia relativa de aparición de los caracteres en el texto cifrado

Este tipo de ataque estadístico será válido tanto para los cifrados de tipo monoalfabético con clave como para aquellos que no la tienen. Ahora bien, en la gran mayoría de los casos será necesario contar con una cantidad de criptograma bastante mayor que la del ejemplo anterior, una pizca de intuición y un poco de suerte

La distancia de unicidad viene dada por la relación entre la entropía de la clave H(K) y la redundancia del lenguaje D. Por tanto, si el alfabeto tiene n caracteres, existirán n! combinaciones de elementos de n, por tanto N=\frac{H(K)}{D}=\frac{\log_2{n!}}{D}

Si utilizamos la aproximación de Sterling tenemos que \log_2{n!}\approx n\cdot\log_2{\frac{n}{e}} por lo tanto, la distancia de unicidad será N=\frac{n\cdot\log_2{\frac{n}{e}}}{D}. Como la redundancia D era igual a 3,4 y n = 27 se tiene que N=\frac{27\cdot\log_2{\frac{27}{e}}}{3,4}\approx 26,3. Por lo tanto, necesitamos como mínimo 27 caracteres

Al establecerse en la operación de cifrado una correspondencia directa entre los caracteres del texto en claro y del alfabeto de cifrado, se mantiene la misma relación de frecuencia relativa característica del lenguaje. Por lo tanto, es muy probable que la letra C_i del texto cifrado con mayor frecuencia relativa se corresponda con la letra M_i de mayor frecuencia relativa del lenguaje.

Por tanto, si la letra W es la de mayor frecuencia en el criptograma, podemos suponer con muy buenas expectativas de éxito, que sea la letra E del texto en claro y que, por lo tanto, el desplazamiento aplicado haya sido igual a 19, la distancia que separa ambas letras en el alfabeto

Estas suposiciones sólo tendrán cierta validez si la cantidad de texto cifrado es grande y por tanto se cumplen las propiedades estadísticas del lenguaje. En el fondo se está realizando una comparación de la distribución de frecuencias de todos los elementos del criptograma con la característica del lenguaje, con el objeto de encontrar ese desplazamiento constante

Cifrado de Polibio

El historiador griego Polibio (203-120 A. C.), creó un sistema de enviar mensajes por medio de antorchas encendidas

El método consistía básicamente en la creación de una matriz cuadrada de 5 \times 5 tal como la siguiente

\begin{pmatrix}&1&2&3&4&5\\1&A&B&C&D&E\\2&F&G&H&I/J&K\\3&L&M&N&O&P\\4&Q&R&S&T&U\\5&V&W&X&Y&Z\end{pmatrix}

El mensaje es representado por los números que forman la fila y columna cuya intersección da como resultado la letra que se quiere enviar

Si bien el método de Polibio no tenía inicialmente un propósito criptográfico, sí que es la base de sistemas posteriores y el primer caso conocido de sustitución monoalfabética multiliteral

Una variante del cifrado de Polibio, utilizado por los comunistas en la guerra civil española consistía en generar una tabla con tres filas de diez columnas

La primera fila no tenía numeración y la segunda y tercera filas se numeraban respectivamente con dos de los números no utilizados en las columnas de la primera fila

Las columnas se numeraban con una permutación de los dígitos del cero al nueve

El proceso de cifrado consistía en poner una palabra de ocho o menos letras diferentes en la primera fila

En esta palabra se eliminaban las letras repetidas y el resto, hasta completar el alfabeto, se disponían en las dos filas siguientes

El cifrado es similar al de Polibio, pero aquí las letras pueden codificarse como uno o dos números

Ejemplo de la variante comunista del cifrado de Polibio

Los comunistas españoles tenían que enviar el siguiente mensaje que no querían que las tropas franquistas interceptasen

C=EN PIE FAMELICA LEGION

Tomando como clave:

K=FUSIL

Usando la siguiente tabla

\tiny\begin{pmatrix}&8&3&0&2&4&6&1&7&5&9\\&F&U&S&I&L\\5&A&B&C&D&E&G&H&J&K&M\\1&N/\widetilde{N}&O&P&Q&R&T&V&X&Y&Z \end{pmatrix}

Así nos queda que el mensaje cifrado es:

M=54 18 10 2 54 8 58 59 54 4 2 50 58 4 54 56 2 13 18

Desciframos el M anterior

Vamos a la tabla de cifrado, si tenemos dos cifras, comprobamos cual es su fila y la segunda corresponde a la columna

La fila de la intersección de ambas será la letra que se usará en el mensaje descifrado

Si tenemos una cifra, es la correspondiente a la columna y la fila es la correspondiente a la clave

Puede haber confusión en el caso del 18, ya que comparten posición la N y la Ñ, todo dependerá del contexto del mensaje (en este caso se toma la N)

Repetiremos el proceso hasta obtener el mensaje en claro

Obteniendo el C original:

C=ENPIEFAMELICALEGION