Cifrado de transposición - Transposition cipher

En criptografía , un cifrado de transposición es un método de cifrado mediante el cual las posiciones que ocupan las unidades de texto sin formato (que suelen ser caracteres o grupos de caracteres) se cambian de acuerdo con un sistema regular, de modo que el texto cifrado constituye una permutación del texto sin formato. Es decir, se cambia el orden de las unidades (se reordena el texto sin formato). Matemáticamente , se utiliza una función biyectiva en las posiciones de los caracteres para cifrar y una función inversa para descifrar.

A continuación se muestran algunas implementaciones.

Cifrado de valla ferroviaria

El cifrado Rail Fence es una forma de cifrado de transposición que recibe su nombre de la forma en que se codifica. En el cifrado de la valla de riel, el texto sin formato se escribe hacia abajo y en diagonal en sucesivos "rieles" de una valla imaginaria, y luego se mueve hacia arriba cuando llegamos al final. A continuación, el mensaje se lee en filas. Por ejemplo, usando tres "rieles" y un mensaje de 'SOMOS DESCUBIERTOS HUYE INMEDIATAMENTE', el cifrador escribe:

W . . . E . . . C . . . R . . . L . . . T . . . E
. E . R . D . S . O . E . E . F . E . A . O . C .
. . A . . . I . . . V . . . D . . . E . . . N . .

Luego lee:

WECRL TEERD SOEEF EAOCA IVDEN

(El cifrado ha dividido este texto cifrado en bloques de cinco para ayudar a evitar errores. Esta es una técnica común que se utiliza para hacer que el cifrado sea más fácil de leer. El espaciado no está relacionado con los espacios en el texto plano y, por lo tanto, no contiene información sobre el Texto sin formato.)

Scytale

El cifrado de la valla de riel sigue un patrón similar al del scytale , un sistema mecánico para producir un cifrado de transposición utilizado por los antiguos griegos . El sistema constaba de un cilindro y una cinta que se enrollaba alrededor del cilindro. El mensaje a cifrar estaba escrito en la cinta enrollada. Las letras del mensaje original se reorganizarían cuando se desenrollara la cinta del cilindro. Sin embargo, el mensaje se descifró fácilmente cuando la cinta retrocedió en un cilindro del mismo diámetro que el cilindro de cifrado. Usando el mismo ejemplo que antes, si el cilindro tiene un radio tal que solo caben tres letras alrededor de su circunferencia, el cifrador escribe:

W . . E . . A . . R . . E . . D . . I . . S . . C
. O . . V . . E . . R . . E . . D . . F . . L . .
. . E . . E . . A . . T . . O . . N . . C . . E .

En este ejemplo, el cilindro se ejecuta horizontalmente y la cinta se enrolla verticalmente. Por lo tanto, el cifrador luego lee:

WOEEV EAEAR RTEEO DDNIF CSLEC

Cifrado de ruta

En un cifrado de ruta, el texto sin formato se escribe primero en una cuadrícula de dimensiones dadas, luego se lee en un patrón dado en la clave. Por ejemplo, usando el mismo texto sin formato que usamos para la cerca de riel :

W R I O R F E O E 
E E S V E L A N J 
A D C E D E T C X 

La clave puede especificar "espiral hacia adentro, en el sentido de las agujas del reloj, comenzando desde la parte superior derecha". Eso daría un texto cifrado de:

EJXCTEDEC DAEWRIORF EONALEVSE

Los cifrados de ruta tienen muchas más claves que una valla de riel. De hecho, para mensajes de longitud razonable, el número de claves posibles es potencialmente demasiado grande para ser enumerado incluso por la maquinaria moderna. Sin embargo, no todas las claves son igualmente buenas. Las rutas mal elegidas dejarán fragmentos excesivos de texto plano, o texto simplemente invertido, y esto dará a los criptoanalistas una pista sobre las rutas.

Una variación del cifrado de ruta fue el cifrado de ruta de la Unión, utilizado por las fuerzas de la Unión durante la Guerra Civil estadounidense . Esto funcionó de manera muy similar a un cifrado de ruta ordinario, pero transpuso palabras completas en lugar de letras individuales. Debido a que esto dejaría expuestas ciertas palabras altamente sensibles, tales palabras primero serían ocultadas por código . El secretario de cifrado también puede agregar palabras nulas completas, que a menudo se eligieron para hacer que el texto cifrado sea divertido.

Transposición columnar

En una transposición en columnas, el mensaje se escribe en filas de una longitud fija, y luego se vuelve a leer columna por columna, y las columnas se eligen en algún orden codificado. Tanto el ancho de las filas como la permutación de las columnas suelen definirse mediante una palabra clave. Por ejemplo, la palabra clave ZEBRAS tiene una longitud de 6 (por lo que las filas tienen una longitud de 6) y la permutación se define por el orden alfabético de las letras de la palabra clave. En este caso, el orden sería "6 3 2 4 1 5".

En un cifrado de transposición en columnas normal, los espacios libres se rellenan con nulos; en un cifrado de transposición columnar irregular, los espacios se dejan en blanco. Finalmente, el mensaje se lee en columnas, en el orden especificado por la palabra clave. Por ejemplo, supongamos que usamos la palabra clave ZEBRAS y el mensaje ESTAMOS DESCUBIERTOS. HUYA DE INMEDIATO . En una transposición columnar regular, escribimos esto en la cuadrícula de la siguiente manera:

6 3 2 4 1 5
W E A R E D
I S C O V E 
R E D F L E 
E A T O N C 
E Q K J E U 

proporcionando cinco nulos ( QKJEU ), estas letras se pueden seleccionar al azar, ya que solo completan las columnas incompletas y no forman parte del mensaje. El texto cifrado se lee como:

EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE

En el caso irregular, las columnas no se completan con nulos:

6 3 2 4 1 5
W E A R E D 
I S C O V E 
R E D F L E 
E A T O N C 
E 

Esto da como resultado el siguiente texto cifrado:

EVLNA CDTES EAROF ODEEC WIREE

Para descifrarlo, el destinatario tiene que calcular la longitud de las columnas dividiendo la longitud del mensaje por la longitud de la clave. Luego, pueden volver a escribir el mensaje en columnas y luego reordenar las columnas reformando la palabra clave.

En una variación, el mensaje se bloquea en segmentos que tienen la longitud de la clave y a cada segmento se le aplica la misma permutación (dada por la clave). Esto es equivalente a una transposición en columnas donde la lectura es por filas en lugar de columnas.

La transposición en columnas continuó utilizándose para propósitos serios como un componente de cifrados más complejos al menos hasta la década de 1950.

Doble transposición

Una sola transposición columnar podría atacarse adivinando posibles longitudes de columna, escribiendo el mensaje en sus columnas (pero en el orden incorrecto, ya que la clave aún no se conoce) y luego buscando posibles anagramas . Por lo tanto, para hacerlo más fuerte, a menudo se utilizó una doble transposición. Esta es simplemente una transposición columnar aplicada dos veces. Se puede usar la misma clave para ambas transposiciones, o se pueden usar dos claves diferentes.

Como ejemplo, podemos tomar el resultado de la transposición en columnas irregular de la sección anterior y realizar un segundo cifrado con una palabra clave diferente, STRIPE , que da la permutación "564231":

5 6 4 2 3 1 
E V L N A C
D T E S E A
R O F O D E
E C W I R E
E

Como antes, esto se lee en columnas para dar el texto cifrado:

CAEEN SOIAE DRLEF WEDRE EVTOC

Si se cifran varios mensajes de exactamente la misma longitud con las mismas claves, se pueden anagramar simultáneamente. Esto puede llevar tanto a la recuperación de los mensajes como a la recuperación de las claves (para que se puedan leer todos los demás mensajes enviados con esas claves).

Durante la Primera Guerra Mundial , el ejército alemán utilizó un cifrado de transposición de doble columna, cambiando las claves con poca frecuencia. El sistema lo resolvían regularmente los franceses, llamándolo Übchi, que por lo general eran capaces de encontrar rápidamente las claves una vez que habían interceptado una serie de mensajes de la misma longitud, lo que generalmente tomaba solo unos pocos días. Sin embargo, el éxito francés se hizo ampliamente conocido y, después de una publicación en Le Matin , los alemanes cambiaron a un nuevo sistema el 18 de noviembre de 1914.

Durante la Segunda Guerra Mundial, el cifrado de doble transposición fue utilizado por los grupos de la Resistencia holandesa , los Maquis franceses y el Ejecutivo de Operaciones Especiales Británico (SOE), que estaba a cargo de administrar las actividades clandestinas en Europa. También fue utilizado por agentes de la Oficina Estadounidense de Servicios Estratégicos y como un cifrado de emergencia para el Ejército y la Armada Alemanes.

Hasta la invención del cifrado VIC , la doble transposición se consideraba generalmente como el cifrado más complicado que un agente podía operar de forma fiable en condiciones de campo difíciles.

Criptoanálisis

El cifrado de doble transposición se puede tratar como una sola transposición con una clave siempre que sea el producto de las longitudes de las dos claves.

A finales de 2013, George Lasry resolvió un desafío de doble transposición, considerado por su autor como indescifrable, utilizando un enfoque de divide y vencerás, en el que cada transposición fue atacada individualmente.

Transposición de Myszkowski

Una forma variante de transposición columnar, propuesta por Émile Victor Théodore Myszkowski en 1902, requiere una palabra clave con letras recurrentes. En la práctica habitual, las apariciones posteriores de una letra de palabra clave se tratan como si la siguiente letra en orden alfabético, p. Ej., La palabra clave TOMATE arroja una cadena de teclado numérica de "532164".

En la transposición de Myszkowski, las letras de palabras clave recurrentes se numeran de manera idéntica, TOMATO produce una cadena de teclas de "432143".

4 3 2 1 4 3
W E A R E D
I S C O V E
R E D F L E
E A T O N C
E

Las columnas de texto sin formato con números únicos se transcriben hacia abajo; aquellos con números recurrentes se transcriben de izquierda a derecha:

ROFOA CDTED SEEEA CWEIV RLENE

Transposición interrumpida

Un cifrado de transposición interrumpido complica aún más el patrón de transposición con un relleno irregular de las filas de la matriz, es decir, con algunos espacios en blanco intencionalmente (o ennegrecidos como en Rasterschlüssel 44 ), o rellenados más tarde con otra parte del texto plano o letras al azar . Un posible algoritmo es comenzar una nueva fila cada vez que el texto sin formato alcanza un carácter de contraseña. Otra opción sencilla sería utilizar una contraseña que coloque espacios en blanco de acuerdo con su secuencia numérica. Por ejemplo, "SECRET" se decodificaría en una secuencia de "5,2,1,4,3,6" y se tacharía el quinto campo de la matriz, luego se volvería a contar y se tacharía el segundo campo, etc. El siguiente ejemplo sería ser una matriz configurada para la transposición en columnas con la clave de columnas "CRYPTO" y rellenada con campos tachados de acuerdo con la clave de interrupción "SECRET" (marcada con un asterisco), después de lo cual se coloca el mensaje "somos descubiertos, huir de inmediato" en los espacios sobrantes. El texto cifrado resultante (las columnas leídas según la clave de transposición) es "WCEEO ERET RIVFC EODN SELE ADA".

C R Y P T O
1 4 6 3 5 2
W E A R * E
* * D I S *
C O * V E R
E D * F L E
E * A * * T
O N * C E *

Rejillas

Otra forma de cifrado de transposición utiliza rejillas o máscaras físicas con recortes. Esto puede producir una transposición muy irregular durante el período especificado por el tamaño de la rejilla, pero requiere que los corresponsales mantengan una clave física en secreto. Las rejillas se propusieron por primera vez en 1550 y todavía estaban en uso militar durante los primeros meses de la Primera Guerra Mundial.

Detección y criptoanálisis

Dado que la transposición no afecta la frecuencia de los símbolos individuales, el criptoanalista puede detectar fácilmente una transposición simple haciendo un recuento de frecuencias. Si el texto cifrado muestra una distribución de frecuencia muy similar al texto sin formato, lo más probable es que se trate de una transposición. A menudo, esto puede ser atacado mediante anagramas: deslizando fragmentos de texto cifrado, luego buscando secciones que parezcan anagramas de palabras en inglés y resolviendo los anagramas. Una vez que se han encontrado tales anagramas, revelan información sobre el patrón de transposición y, en consecuencia, pueden ampliarse.

Las transposiciones más simples también sufren a menudo de la propiedad de que las claves muy cercanas a la clave correcta revelarán largas secciones de texto plano legible intercaladas por galimatías. En consecuencia, dichos cifrados pueden ser vulnerables a los algoritmos de búsqueda óptimos, como los algoritmos genéticos .

Se puede encontrar una descripción detallada del criptoanálisis de un cifrado de transposición alemán en el capítulo 7 de "The American Black Chamber" de Herbert Yardley.

Un cifrado utilizado por Zodiac Killer , llamado "Z-340", organizado en secciones triangulares con sustitución de 63 símbolos diferentes para las letras y transposición diagonal de "movimiento de caballero", permaneció sin resolver durante más de 51 años, hasta que un equipo internacional de ciudadanos privados lo descifró el 5 de diciembre de 2020 utilizando un software especializado.

Combinaciones

La transposición a menudo se combina con otras técnicas, como los métodos de evaluación. Por ejemplo, un cifrado de sustitución simple combinado con una transposición columnar evita la debilidad de ambos. Reemplazar los símbolos de texto cifrado de alta frecuencia con letras de texto sin formato de alta frecuencia no revela fragmentos de texto sin formato debido a la transposición. Anagramando la transposición no funciona debido a la sustitución. La técnica es particularmente poderosa si se combina con el fraccionamiento (ver más abajo). Una desventaja es que dichos cifrados son considerablemente más laboriosos y propensos a errores que los cifrados más simples.

Fraccionamiento

La transposición es particularmente eficaz cuando se emplea con fraccionamiento, es decir, una etapa preliminar que divide cada símbolo de texto plano en varios símbolos de texto cifrado. Por ejemplo, el alfabeto en texto plano podría escribirse en una cuadrícula y cada letra del mensaje podría reemplazarse por sus coordenadas (ver Cuadrado de Polibio y tablero de ajedrez a caballo entre las dos ). Otro método de fraccionamiento es simplemente convertir el mensaje a código Morse , con un símbolo para espacios, así como puntos y guiones.

Cuando se transpone un mensaje tan fraccionado, los componentes de las letras individuales se separan ampliamente en el mensaje, logrando así la difusión de Claude E. Shannon . Ejemplos de cifrados que combinan fraccionamiento y transposición incluyen el cifrado bífido , el cifrado trífido , el cifrado ADFGVX y el cifrado VIC .

Otra opción sería reemplazar cada letra con su representación binaria, transponerla y luego convertir la nueva cadena binaria en los caracteres ASCII correspondientes. Hacer un bucle del proceso de codificación en la cadena binaria varias veces antes de cambiarlo a caracteres ASCII probablemente dificultaría la ruptura. Muchos cifrados de bloques modernos utilizan formas más complejas de transposición relacionadas con esta simple idea.

Ver también

Notas

Referencias

  • Kahn, David. Los descifradores de códigos: la historia de la escritura secreta. Rev Sub. Scribner, 1996.
  • Yardley, Herbert. La Cámara Negra Estadounidense. Bobbs-Merrill, 1931.