16.2: Cifras de sustitución

Última actualización
Guardar como PDF

Page ID: 110462

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Un método de cifrado simple se llama cifrado de sustitución.

Cifrado de sustitución

Un cifrado de sustitución reemplaza cada letra del mensaje por una letra diferente, siguiendo algún mapeo establecido.

$Una imagen de dos alfabetos con un mapeo entre: A mapea a D, B mapas a E, y C mapas a F.$ Un ejemplo sencillo de un cifrado de sustitución se llama el cifrado César, a veces llamado cifrado por turnos. En este enfoque, cada letra es reemplazada por una letra algún número fijo de posiciones más adelante en el alfabeto. Por ejemplo, si usamos un turno de 3, entonces la letra A sería reemplazada por D, la letra 3 posiciones más adelante en el alfabeto. Todo el mapeo se vería así: [1]

Original:$\mathrm{ABCDEFGHIJKLMNOPQRSTUVWXYZ}$

Mapas a:$\mathrm{DEFGHIJKLMNOPQRSTUVWXYZABC}$

Ejemplo 1

Usa el cifrado César con turno de 3 para cifrar el mensaje: “Montamos al mediodía”

Solución

Utilizamos el mapeo anterior para reemplazar cada letra. W se reemplaza por Z, y así sucesivamente, dando el mensaje cifrado: ZH ULGH DW QRRQ.

Observe que la longitud de las palabras podría dar una pista importante sobre el cambio de cifrado utilizado. Si viéramos una sola letra en el mensaje encriptado, asumiríamos que debe ser una A o I cifrada, ya que esas son las únicas letras simples que forman palabras válidas en inglés.

Para oscurecer el mensaje, las letras a menudo se reordenan en bloques de igual tamaño. El mensaje ZH ULGH DW QRRQ podría escribirse en bloques de tres caracteres como

ZHU LGH DWQ RRQ.

Ejemplo 2

Descifrar el mensaje GZD KNK YDX MFW JXA si fue encriptado usando un cifrado por turnos con shift de 5.

Solución

Comenzamos escribiendo el mapeo de caracteres cambiando el alfabeto, con A mapeando a F, cinco caracteres más tarde en el alfabeto.

Original:$\mathrm{ABCDEFGHIJKLMNOPQRSTUVWXYZ}$

Mapas a:$\mathrm{FGHIJKLMNOPQRSTUVWXYZABCDE}$

Ahora trabajamos hacia atrás para descifrar el mensaje. La primera letra G está mapeada por B, por lo que B es el primer carácter del mensaje original. Continuando, nuestro mensaje descifrado es

COMPRAR FIF TYS HAR ESA.

Eliminando espacios obtenemos COMPRA FIFTYSHARESA. En este caso, al parecer se agregó un carácter extra al final para hacer que los grupos de tres salieran parejos, y que el mensaje original era “Comprar cincuenta acciones”.

Pruébalo ahora 1

Descifrar el mensaje BNW MVX WNH si fue encriptado usando un cifrado de turno con shift 9 (mapeo A a J).

Contestar: ENVIAR DINERO

$Una imagen de un disco de cifrado, con un anillo exterior de letras y números, y un anillo interior de letras.$

Observe que en ambos cifrados anteriores, la parte extra del alfabeto se envuelve al principio. Debido a esto, una versión práctica del cifrado por turnos es un disco de cifrado, como el disco de cifrado Alberti que se muestra aquí [2] de los 1400s. En un disco de cifrado, la rueda interna podría girarse para cambiar el cambio de cifrado. Este mismo enfoque se utiliza para los “anillos de decodificador secretos”.

La seguridad de un método criptográfico es muy importante para la persona que confía en que su mensaje se mantenga en secreto. La seguridad depende de dos factores:

La seguridad del método que se utiliza
La seguridad de la clave de cifrado utilizada

En el caso de un cifrado por turnos, el método es “se usa un cifrado por turnos”. La clave de cifrado es la cantidad específica de turno utilizada.

Supongamos que un ejército está usando un cifrado de turno para enviar sus mensajes, y uno de sus oficiales es capturado por su enemigo. Es probable que el método y la clave de cifrado se vean comprometidos. Es relativamente difícil cambiar los métodos de cifrado, pero relativamente fácil cambiar las claves de cifrado.

Durante la Segunda Guerra Mundial, las máquinas de cifrado Enigma de los Alemanes fueron capturadas, pero tener detalles sobre el método de cifrado solo ayudó ligeramente a los Aliados, ya que las claves de cifrado aún eran desconocidas y difíciles de descubrir. En última instancia, la seguridad de un mensaje no puede depender de que el método se mantenga en secreto; necesita confiar en que la clave se mantenga en secreto.

Seguridad de encriptación

La seguridad de cualquier método de cifrado debe depender únicamente de que la clave de cifrado sea difícil de descubrir. No es seguro confiar en que el método de cifrado (algoritmo) se mantenga en secreto.

Con eso en mente, analicemos la seguridad del cifrado César.

Ejemplo 3

Supongamos que interceptas un mensaje, y sabes que el remitente está usando un cifrado César, pero no sabes el turno que se está usando. El mensaje inicia EQZP. ¿Qué tan difícil sería descifrar este mensaje?

Solución

Dado que solo hay 25 turnos posibles, solo tendríamos que probar 25 posibilidades diferentes para ver cuál produce resultados que tengan sentido. Si bien eso sería tedioso, una persona podría hacerlo fácilmente a mano en pocos minutos. Una computadora moderna podría probar todas las posibilidades en menos de un segundo.

\ (\ begin {array} {|l|l|l|l|l|l|l|l|l|}
\ hline\ textbf {Shift} &\ textbf {Mensaje} &\ textbf {Shift} &\ textbf {Mensaje} &\ textbf {Shift} &\ textbf {Mensaje} &\ textbf {Mensaje}\ textbf
\ hline 1 &\ texto {DPYO} & 7 &\ texto {XJSI} & 13 &\ texto {RDMC} & 19 &\ texto {LXGW}\
\ hline 2 &\ texto {COXN} & 8 &\ texto {WIRH} & 14 &\ texto {QCLB} & 20 &\ texto {KWFV}
\\ hline 3 &\ texto {BNWM} & 9 &\ texto {VHQG} & 15 &\ texto { PBKA} & 21 &\ texto {JVEU}\
\ hline 4 &\ texto {AMVL} & 10 &\ texto {UGPF} & 16 &\ texto {OAJZ} & 22 &\ texto {IUDT}\
\ hline 5 &\ texto {ZLUK} & 11 &\ texto {TFOE} & 17 &\ texto {NZIY} & 23 &\ texto {HTCS}\ \
\ hline 6 &\ texto {YKTJ} &\ mathbf {1 2} &\ textbf {ENVIAR} & 18 &\ texto {MYHX} & 24 &\ texto {GSBR}\\
\ hline & & & & & & & & & 25 &\ texto {FRAQ}\
\\ hline
\ end {array}\)

En este caso, un desplazamiento de 12 (asignación A a M) descifra EQZP a ENVIAR. Debido a esta facilidad de probar todas las claves de cifrado posibles, el cifrado César no es un método de cifrado muy seguro.

Ataque de Fuerza Bruta

Un ataque de fuerza bruta es un método para romper el cifrado al probar todas las claves de cifrado posibles.

Para hacer más difícil un ataque de fuerza bruta, podríamos hacer un cifrado de sustitución más complejo usando algo que no sea un cambio del alfabeto. Al elegir un mapeo aleatorio, podríamos obtener un cifrado más seguro, con la compensación de que la clave de cifrado es más difícil de describir; la clave ahora sería el mapeo completo, en lugar de solo la cantidad de turno.

Ejemplo 4

Utilice la asignación de sustitución a continuación para cifrar el mensaje “March 12 0300”

Original:$mathrm{ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789}$

Mapas a:$\mathrm{2BQF5WRTD8IJ6HLCOSUVK3A0X9YZN1G4ME7P}$

Solución

Usando la asignación, el mensaje se cifraría a 62SQT ZN Y1YY

Pruébalo ahora 2

Utilice la asignación de sustitución del Ejemplo 4 para descifrar el mensaje C2SVX2VP

Contestar: FIESTA A LAS 9

Si bien solo había 25 posibles claves de cifrado por turnos (35 si hubiéramos incluido números), hay alrededor de 10 ⁴⁰ posibles cifrados de sustitución [3]. Eso es mucho más que un billón de billones. Sería esencialmente imposible, incluso con supercomputadoras, probar todas las combinaciones $Un gráfico de frecuencias que muestra cada letra del alfabeto en la horizontal, y la frecuencia de esa letra en la vertical. El listón más alto está en la letra E.$ posibles. Tener una gran cantidad de claves de cifrado posibles es una parte importante de la seguridad de las claves.

Desafortunadamente, este cifrado aún no es seguro, debido a una técnica llamada análisis de frecuencia, descubierta por el matemático árabe Al-Kindi en el ^siglo IX. El inglés y otros idiomas tienen ciertas letras que aparecen con más frecuencia por escrito que en otros. [4] Por ejemplo, la letra E aparece con mayor frecuencia en inglés. El gráfico de la derecha muestra la distribución típica de los caracteres.

Ejemplo 5

$Un gráfico de barras que muestra las letras del alfabeto en la horizontal en orden aleatorio, y la frecuencia en la vertical. La primera letra con mayor frecuencia es S, seguida por W.$ El gráfico de la derecha muestra la frecuencia de diferentes caracteres en algún texto cifrado. ¿Qué se puede deducir sobre el mapeo?

Solución

Debido a la alta frecuencia de la letra S en el texto encriptado, es muy probable que la sustitución mapee E a S. Dado que W es el segundo carácter más frecuente, es probable que T o A mapee a W. Debido a que C, A, D y J aparecen raramente en el texto cifrado, es probable que se mapeen a partir de J, Q, X y Z.

Además de mirar letras individuales, ciertos pares de letras aparecen con mayor frecuencia, como el par “th”. Al analizar la frecuencia con la que diferentes letras y pares de letras muestran un mensaje cifrado, se puede deducir el mapeo de sustitución utilizado [5].

[1] es.wikipedia.org/w/index. php*title=Archivo:CAESAR3.svg&page=1. PD

[2] es.wikipedia.org/wiki/Archivo:Alberti_Cipher_Disk.jpg

[3] Hay 35 opciones para lo que A mapea, luego 34 opciones para lo que B mapea, y así sucesivamente, por lo que el número total de posibilidades es 35*34*33*... *2*1 = 35! = alrededor de 10 ⁴⁰

[4] es.wikipedia.org/w/index. php*title=file:english_letter_frequency_ (alfabético) .svg&page=1 PD

[5] Para ver un ejemplo de cómo se hace esto, consulte en.wikipedia.org/wiki/Frequency_analysis