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) según 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 operaciones de transposición y sustitución, a menudo se combinan, como en cifrados históricos como el cifrado ADFGVX o métodos de cifrado complejos de alta calidad como el moderno Estándar de cifrado avanzado (AES).
Los textos sin formato se pueden reorganizar en texto cifrado utilizando una clave , alterando 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 como "TWDIP SIHII IKASE". Para descifrar el mensaje cifrado 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:
Clave de cifrado1 4 5 3 2 6 Secuencia (letras clave en orden alfabético)ESTO ES texto sin formatoWIKIPEDÍA * * *Texto cifrado por columna: #1 TWD, #2 IP, #3 SI, #4 HII, #5 IKA, #6 SETexto cifrado en grupos de 5 para facilitar la lectura: 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), contenidos impredecibles, 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 descifrado 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". [1]
El cifrado Rail Fence es una forma de cifrado de transposición que recibe su nombre por la forma en que está codificado. En el cifrado de la valla ferroviaria, el texto claro se escribe hacia abajo y en diagonal sobre "rieles" sucesivos 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, utilizando tres "rieles" y un mensaje de "NOS DESCUBREN HUYEMOS DE INMEDIATO", el cifrador escribe:
W. . . mi. . . C . . . r. . . l. . . T. . . mi. mi. r. D . S . O. mi. mi. F. mi. A . O. C .. . A . . . I . . . V. . . D . . . mi. . . norte. .
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 contiene ninguna información sobre el Texto sin formato.)
El cifrado de la valla de ferrocarril sigue un patrón similar al de la 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 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ó sobre un cilindro del mismo diámetro que el cilindro de cifrado. [2] Utilizando el mismo ejemplo anterior, si el cilindro tiene un radio tal que sólo caben tres letras alrededor de su circunferencia, el cifrador escribe:
W. . mi. . A . . r. . mi. . D . . I . . S . . C. O. . V. . mi. . r. . mi. . D . . F. . l. .. . mi. . mi. . A . . T. . O. . norte. . C . . mi.
En este ejemplo, el cilindro corre horizontalmente y la cinta se enrolla verticalmente. Por lo tanto, el cifrado lee:
WOEEV EAEAR RTEEO DDNIF CSLEC
En un cifrado de ruta, el texto sin formato se escribe primero en una cuadrícula de dimensiones dadas y luego se lee siguiendo un patrón dado en la clave. Por ejemplo, usando el mismo texto sin formato que usamos para la valla ferroviaria :
WRIORFEOEEESVELANJADCEDETCX
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 maquinaria moderna. Sin embargo, no todas las claves son igual de buenas. Las rutas mal elegidas dejarán trozos excesivos 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 se ocultarían mediante código . El encargado del cifrado también puede agregar palabras nulas completas, que a menudo se elegían para darle humor al texto cifrado. [ cita necesaria ]
A mediados del siglo XVII, Samuel Morland introdujo una forma temprana de transposición columnar. Se desarrolló mucho más tarde y se hizo muy popular a finales del siglo XIX y en el siglo XX, y los militares franceses, los diplomáticos japoneses y los espías soviéticos utilizaron este principio.
En una transposición en columnas, el mensaje se escribe en filas de una longitud fija y luego se lee nuevamente 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 mediante una palabra clave. Por ejemplo, la palabra clave CEBRAS 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 de columnas regular, los espacios libres se rellenan con nulos; en un cifrado de transposición de columnas irregulares, 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 CEBRAS y el mensaje ESTAMOS DESCUBRIDOS. HUYE DE INMEDIATO . En una transposición de columnas regular, escribimos esto en la cuadrícula de la siguiente manera:
6 3 2 4 1 5DESGASTEISCOVEREDFLEEATONCEQKJEU
Al proporcionar cinco valores nulos ( QKJEU ), estas letras se pueden seleccionar aleatoriamente ya que solo completan las columnas incompletas y no son parte del mensaje. Luego el texto cifrado se lee como:
EVLNE ACDTK ESEAQ ROFOJ DEECU CABLE
En el caso irregular, las columnas no se completan con nulos:
6 3 2 4 1 5DESGASTEISCOVEREDFLEEATONCmi
Esto da como resultado el siguiente texto cifrado:
EVLNA CDTES EAROF ODEEC CABLE
Para descifrarlo, el destinatario debe determinar la forma de la cuadrícula de cifrado dividiendo la longitud del mensaje por la longitud de la clave para encontrar el número de filas en la cuadrícula. La longitud de la última línea de la cuadrícula viene dada por el resto. La clave se escribe encima de la cuadrícula y el texto cifrado se escribe en las columnas de la cuadrícula en el orden indicado por las letras de la clave. El texto sin formato aparece en las filas. Un descifrado parcial del texto cifrado anterior, después de escribir en la primera columna:
6 3 2 4 1 5. . . . mi.. . . . V.. . . . l.. . . . norte..
En una variación, el mensaje se bloquea en segmentos que tienen la longitud de la clave y a cada segmento se aplica la misma permutación (dada por la clave). Esto equivale a una transposición de columnas en la que la lectura se realiza por filas en lugar de columnas.
La transposición de columnas siguió utilizándose con fines serios como componente de cifrados más complejos al menos hasta la década de 1950.
Se podría atacar una transposición de una sola columna adivinando 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 ello, para hacerlo más fuerte, a menudo se utilizaba una doble transposición. Se trata simplemente de una transposición de columnas aplicada dos veces. Se puede utilizar la misma clave para ambas transposiciones, o se pueden utilizar dos claves diferentes.
En el siguiente ejemplo, utilizamos las claves JANEAUSTEN y AIRPLANES para cifrar el siguiente texto sin formato: " Los cifrados de transposición mezclan letras como piezas de un rompecabezas para crear una disposición indescifrable".
Los colores muestran cómo se mezclan las letras en cada paso de transposición. Mientras que un solo paso sólo provoca una reorganización menor, el segundo paso produce un efecto de codificación significativo si la última fila de la cuadrícula está incompleta.
Como ejemplo, podemos tomar el resultado de la transposición de columnas irregular en 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 1EVLNACDTESEAROFODEECWIREmi
Como antes, esto se lee en columnas para obtener el texto cifrado:
CAEEN SOIAE DRLEF WEDRE EVTOC
Si se cifran varios mensajes de exactamente la misma longitud utilizando 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 (de modo que todos los demás mensajes enviados con esas claves puedan leerse).
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. Los franceses resolvían periódicamente el sistema y lo llamaban Übchi, quienes normalmente podían encontrar rápidamente las claves una vez que interceptaban varios mensajes de la misma longitud, lo que generalmente tomaba sólo unos 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. [3]
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 (SOE) británico, que estaba a cargo de gestionar las actividades clandestinas en Europa. [4] También fue utilizado por agentes de la Oficina Estadounidense de Servicios Estratégicos [5] y como cifrado de emergencia para el ejército y la marina 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 manera confiable en condiciones de campo difíciles.
El cifrado de doble transposición se puede tratar como una transposición única con una clave tan larga como el producto de las longitudes de las dos claves. [6]
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. [7]
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 TOMATE produce una cadena de clave numérica de "532164".
En la transposición de Myszkowski, las letras de las palabras clave recurrentes se numeran de manera idéntica, TOMATO produce una cadena de claves de "432143".
4 3 2 1 4 3DESGASTEISCOVEREDFLEEATONCmi
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
Un cifrado de transposición interrumpido [8] complica aún más el patrón de transposición con el llenado irregular de las filas de la matriz, es decir, con algunos espacios intencionalmente dejados en blanco (o tachados como en el Rasterschlüssel 44 ), o llenados posteriormente con otra parte del texto claro. o letras aleatorias. [8]
Este método (atribuido al general Luigi Sacco [9] ) inicia una nueva fila una vez que el texto sin formato llega a una columna cuyo número de clave es igual al número de fila actual. Esto produce longitudes de fila irregulares. Por ejemplo,
PARA SIEMPRE JIGSAW < Clave4 8 9 2 12 3 10 7 6 5 11 1 13 Espacios en blanco después del n.º:MÁS COMPLICADO * 1HETR * * * * * * * * * 2RESPUESTA * * * * * * * 3Yo * * * * * * * * * * * * 4PATRÓN DE TION * * * 5NLIKEACOM * * * * 6B _ _ _ _ _ _ _ * * * * * 7
Luego, las columnas se eliminan según la transposición de columnas habitual: TPRPN, KISAA, CHAIT, NBERT, EMATO, etc.
Otra opción sencilla [10] sería utilizar una contraseña que coloque espacios en blanco según su secuencia numérica. Por ejemplo, "SECRETO" 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 contaría nuevamente y se tacharía el segundo campo, etc. El siguiente ejemplo sería ser una matriz configurada para transposición de columnas con la clave de columna "CRYPTO" y llena de campos tachados de acuerdo con la clave de interrupción "SECRETO" (marcada con un asterisco), después de lo cual se coloca el mensaje "somos descubiertos, huimos 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".
CRIPTO1 4 6 3 5 2SOMOS* *DES*CUBRIRED*FLECOMERUNA VEZ *
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 rejas se propusieron por primera vez en 1550 y todavía se usaron militarmente durante los primeros meses de la Primera Guerra Mundial.
Dado que la transposición no afecta la frecuencia de los símbolos individuales, el criptoanalista puede detectar fácilmente la transposición simple realizando un recuento de frecuencia. Si el texto cifrado muestra una distribución de frecuencia muy similar a la del 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 esté escrito el texto sin formato y resolver los anagramas. Una vez que se han encontrado dichos anagramas, revelan información sobre el patrón de transposición y, en consecuencia, pueden ampliarse. Las transposiciones más simples a menudo sufren 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, dichos cifrados pueden ser vulnerables a algoritmos de búsqueda óptima, como los algoritmos genéticos [11] y los algoritmos de escalada . [12] [13]
Existen varios métodos específicos para atacar mensajes codificados mediante un cifrado de transposición. Éstas incluyen:
El tercer método fue desarrollado en 1878 por el matemático Edward S. Holden y los periodistas del New-York Tribune John RG Hassard y William M. Grosvenor, quienes lograron descifrar telegramas entre el Partido Demócrata y sus agentes en los estados del sur durante las elecciones presidenciales de 1876 y así probar hechos de compra de votos , que influyeron en las elecciones al Congreso de 1878-1879 . [14]
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 letras por 63 símbolos diferentes 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. [15]
La transposición suele combinarse con otras técnicas, como los métodos de evaluación. Por ejemplo, un cifrado de sustitución simple combinado con una transposición en columnas evita la debilidad de ambos. Reemplazar 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 estos cifrados son considerablemente más laboriosos y propensos a errores que los cifrados más simples.
La transposición es particularmente efectiva 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 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 horcajadas ). [16] Otro método de fraccionamiento es simplemente convertir el mensaje a código Morse , con un símbolo para espacios, así como puntos y rayas. [17]
Cuando se transpone un mensaje tan fraccionado, los componentes de las letras individuales quedan ampliamente separados 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 cambiarla a caracteres ASCII probablemente haría que fuera más difícil de romper. Muchos cifrados de bloques modernos utilizan formas de transposición más complejas relacionadas con esta idea simple.