Cifrado de transposición

En criptografía, un cifrado de transposición (también conocido como cifrado de permutación) es un método de cifrado que codifica las posiciones de los caracteres (transposición) sin cambiar los caracteres mismos.. Los cifrados de transposición reordenan unidades de texto sin formato (normalmente caracteres o grupos de caracteres) de acuerdo con un sistema regular para producir un texto cifrado que es una permutación del texto sin formato. Se diferencian de los cifrados de sustitución, que no cambian la posición de las unidades de texto sin formato, sino que cambian las unidades mismas. A pesar de la diferencia entre las operaciones de transposición y sustitución, a menudo se combinan, como en cifrados históricos como el cifrado ADFGVX o métodos complejos de cifrado de alta calidad como el estándar de cifrado avanzado (AES) moderno.

Principio general

Los textos sin formato se pueden reorganizar en un texto cifrado usando una clave, codificando el orden de los caracteres como las piezas mezcladas de un rompecabezas. El mensaje resultante es difícil de descifrar sin la clave porque hay muchas maneras de organizar los caracteres.

Por ejemplo, el texto sin formato "ESTO ES WIKIPEDIA" podría cifrarse en "TWDIP SIHII IKASE". Para descifrar el mensaje encriptado sin la clave, un atacante podría intentar adivinar posibles palabras y frases como DIÁTESIS, DISIPAR, ANCHO, etc., pero le llevaría algún tiempo reconstruir el texto sin formato porque hay muchas combinaciones de letras y palabras. Por el contrario, alguien con la clave podría reconstruir el mensaje fácilmente:

C I P H E R Key
1 4 5 3 2 6 Secuencia (cartas clave en orden alfabético)
T H I S I S Plaintext
W I K I P E
D I A *

Ciphertext por columna:
#1 TWD, #2 IP, #3 SI, #4 HII, #5 IKA, #6 SE
Ciphertext in groups of 5 for readability:
TWDIP SIHII IKASE

En la práctica, un mensaje tan corto y con una palabra clave predecible se rompería casi de inmediato con técnicas de criptoanálisis. Los cifrados de transposición tienen varias vulnerabilidades (consulte la sección sobre "Detección y criptoanálisis" a continuación), y pequeños errores en el proceso de cifrado pueden hacer que todo el texto cifrado pierda sentido.

Sin embargo, dadas las condiciones adecuadas (mensajes largos (por ejemplo, más de 100 a 200 letras), contenido impredecible, claves únicas por mensaje, métodos de transposición sólidos, etc.), adivinar las palabras correctas podría ser computacionalmente imposible sin más información. En su libro sobre decodificación de cifrados históricos, Elonka Dunin y Klaus Schmeh describen la transposición de doble columna (ver más abajo) como "uno de los mejores cifrados manuales conocidos".

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 valla de riel, el texto sin formato se escribe hacia abajo y en diagonal en "rieles" sucesivos. de una cerca imaginaria, luego subiendo cuando llegamos al fondo. A continuación, el mensaje se lee en filas. Por ejemplo, usando tres "rieles" y un mensaje de "SOMOS DESCUBIERTOS, HUYEMOS DE UNA VEZ", 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 utilizada para hacer que el cifrado sea más fácil de leer. El espaciado no está relacionado con los espacios en el texto sin formato y, por lo tanto, no lleva información sobre el texto sin formato.)

Escitalo

El cifrado de valla ferroviaria sigue un patrón similar al del scytale, (pronunciado "SKIT-uhl-ee"), 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 envolvía alrededor del cilindro. El mensaje a cifrar estaba escrito en la cinta enrollada. Las letras del mensaje original se reorganizarían cuando la cinta se desenrollara 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 tres letras pueden caber 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. A. T. O. N. C. E.

En este ejemplo, el cilindro corre 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 y luego se lee en un patrón dado en la clave. Por ejemplo, usando el mismo texto sin formato que usamos para 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 podría 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 ferrocarril. 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 teclas son igual de buenas. Las rutas mal elegidas dejarán demasiados fragmentos de texto sin formato, 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, dichas palabras primero serían ocultadas por el código. El empleado de cifrado también puede agregar palabras nulas completas, que a menudo se eligieron para hacer que el texto cifrado fuera 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 estar definidos por 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 en la palabra clave. En este caso, el orden sería "6 3 2 4 1 5".

En un cifrado de transposición columnar normal, los espacios libres se rellenan con valores 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 NOS DESCUBRIERON. HUYE DE UNA VEZ. 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 A T O N C
E Q K J E U

proporcionando cinco nulos (QKJEU), estas letras se pueden seleccionar aleatoriamente 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 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 escribir el mensaje en columnas nuevamente, 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 ya cada segmento se le aplica la misma permutación (dada por la clave). Esto es equivalente a una transposición columnar donde la lectura es por filas en lugar de columnas.

La transposición en columnas se siguió utilizando con fines serios como componente de cifrados más complejos al menos hasta la década de 1950.

Transposición doble

Una transposición de una sola columna podría atacarse adivinando las posibles longitudes de columna, escribiendo el mensaje en sus columnas (pero en el orden incorrecto, ya que aún no se conoce la clave) y luego buscando posibles anagramas. Por lo tanto, para hacerlo más fuerte, a menudo se usaba una doble transposición. Esto 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 de columnas irregulares en la sección anterior y realizar un segundo cifrado con una palabra clave diferente, STRIPE, que proporciona 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 por columnas para dar el texto cifrado:

CAEEN SOIAE DRLEF WEDRE EVTOC

Si varios mensajes de exactamente la misma longitud se cifran con las mismas claves, se pueden anagramar simultáneamente. Esto puede conducir 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 fue resuelto regularmente por los franceses, llamándolo Übchi, que generalmente podían encontrar rápidamente las claves una vez que interceptaban una cantidad 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, tras 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 cifrado de emergencia para el ejército y la marina alemanes.

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

Cripanálisis

El cifrado de doble transposición se puede tratar como una sola transposición con una clave tan larga como 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 se atacaba 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 fuera la siguiente letra en orden alfabético, por ejemplo, la palabra clave TOMATO produce una cadena de clave numérica de "532164."

En la transposición de Myszkowski, las letras de palabras clave recurrentes se numeran de forma idéntica, TOMATO produce una cadena de clave 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 A T O N C
E

Las columnas de texto sin formato con números únicos se transcriben hacia abajo; los que tienen 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 el relleno irregular de las filas de la matriz, es decir, con algunos espacios intencionalmente dejados en blanco (o ennegrecidos como en el Rasterschlüssel 44), o llenados más tarde con otra parte del texto sin formato o letras al azar.

Enfoque de peine

Un algoritmo posible es comenzar una nueva fila cada vez que el texto sin formato alcance un carácter de contraseña. Por ejemplo,

F O R E V E R J I G S A W
4 8 9 2 12 3 10 7 6 5 11 1 13 Mantas después de no:
C O M P L I C A T E S T * 1
H E T R * * * * * * * * * * * 2
A N S P O S * * * * * * * 3
* * * * * * * * * * * * * * * *
T I O N P A T T E R * * 5
N L I K E A C O M * * * 6
B _ _ _ * * * * * 7

Luego, las columnas se eliminan según la transposición de columnas regular: TPRPN, KISAA, CHAIT, NBERT, EMATO, etc.

Enfoque de secuencia numérica

Otra opción sencilla sería utilizar una contraseña que coloque espacios en blanco según su secuencia numérica. P.ej. "SECRETO" se decodificaría en una secuencia de "5,2,1,4,3,6" y tache el quinto campo de la matriz, luego vuelva a contar y tache el segundo campo, etc. El siguiente ejemplo sería una matriz configurada para la transposición de columnas con la clave de columnas "CRYPTO" y rellenado con campos tachados según la clave de interrupción "SECRETO" (marcado con un asterisco), después de lo cual el mensaje "somos descubiertos, huir de inmediato" se coloca en los espacios sobrantes. El texto cifrado resultante (las columnas se leen de acuerdo con 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 por 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 en secreto una clave física. 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 la transposición simple haciendo un conteo de frecuencia. Si el texto cifrado muestra una distribución de frecuencias muy similar al texto sin formato, lo más probable es que se trate de una transposición.

En general, los métodos de transposición son vulnerables a los anagramas: deslizar fragmentos de texto cifrado, luego buscar secciones que parezcan anagramas de palabras en inglés o en cualquier idioma en el que se haya escrito el texto sin formato y resolver 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 a menudo adolecen de la propiedad de que las claves muy cercanas a la clave correcta revelarán largas secciones de texto claro legible intercaladas con galimatías. En consecuencia, tales cifrados pueden ser vulnerables a los algoritmos de búsqueda óptimos, como los algoritmos genéticos y los algoritmos de escalada.

Existen varios métodos específicos para atacar mensajes codificados mediante un cifrado de transposición. Éstos incluyen:

1. Ataque de pretexto conocido: Utilizando partes conocidas o conjeturadas del texto (por ejemplo, nombres, lugares, fechas, números, frases) para ayudar a la ingeniería inversa el orden probable de las columnas utilizadas para llevar a cabo la transposición y/o el tema probable del texto.
2. Ataque de la fuerza bruta: Si las claves se derivan de palabras de diccionario o frases de libros u otras fuentes disponibles públicamente, puede ser posible forzar la solución mediante la tentativa de miles de millones de palabras posibles, combinaciones de palabras y frases como claves.
3. Depth attack: Si dos o más mensajes de la misma longitud se codifican con las mismas teclas, los mensajes pueden ser alineados y anagramados hasta que los mensajes muestren texto significativo en los mismos lugares, sin necesidad de conocer los pasos de transposición que han tenido lugar.
4. Ataque estadístico: Las estadísticas sobre la frecuencia de las combinaciones de 2 letras, 3 letras, etc. en un idioma pueden utilizarse para informar una función de puntuación en un algoritmo que revierte gradualmente las posibles transposiciones basadas en las cuales los cambios producirían las combinaciones más probables. Por ejemplo, el QU de 2 letras es más común que el QT en texto Inglés, por lo que un cryptanalyst intentará transposiciones que colocan QU juntos.

Una descripción detallada del criptoanálisis de un cifrado de transposición alemán se puede encontrar 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 la diagonal "movimiento de caballero" transposición, 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. Anagramar 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 tales 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 sin formato en dos o más símbolos de texto cifrado. Por ejemplo, el alfabeto de texto sin formato podría escribirse en una cuadrícula, y cada letra del mensaje reemplazada por sus coordenadas (ver el cuadrado de Polibio y el tablero de ajedrez a caballo). 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. Repetir el proceso de codificación en la cadena binaria varias veces antes de cambiarlo a caracteres ASCII probablemente haría que fuera más difícil de descifrar. Muchos cifrados de bloque modernos utilizan formas de transposición más complejas relacionadas con esta idea simple.