En criptografía , un cifrado de transposición (también conocido como cifrado de permutación) es un método de cifrado que altera las posiciones de los caracteres ( transposición ) sin cambiar los caracteres en sí. Los cifrados de transposición reordenan unidades de texto simple (normalmente caracteres o grupos de caracteres) según un sistema regular para producir un texto cifrado que es una permutación del texto simple. Se diferencian de los cifrados de sustitución , que no cambian la posición de las unidades de texto simple, sino que cambian las unidades en sí. A pesar de la diferencia entre las operaciones de transposición y sustitución, a menudo se combinan, como en los cifrados históricos como el cifrado ADFGVX o en métodos de cifrado complejos de alta calidad como el moderno Estándar de cifrado avanzado (AES).
Los textos simples se pueden reorganizar en un texto cifrado utilizando una clave , lo que altera el orden de los caracteres como si fueran las piezas desordenadas de un rompecabezas . El mensaje resultante es difícil de descifrar sin la clave porque hay muchas formas de organizar los caracteres.
Por ejemplo, el texto simple "ESTA ES WIKIPEDIA" podría estar cifrado 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 simple porque hay muchas combinaciones de letras y palabras. Por el contrario, alguien con la clave podría reconstruir el mensaje fácilmente:
Clave CIFRADA1 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 breve y con una palabra clave predecible se descifraría casi inmediatamente con técnicas de criptoanálisis . Los cifrados por transposición tienen varias vulnerabilidades (consulte la sección "Detección y criptoanálisis" más adelante) y pequeños errores en el proceso de cifrado pueden hacer que todo el texto cifrado carezca de sentido.
Sin embargo, dadas las condiciones adecuadas (mensajes largos (por ejemplo, más de 100-200 letras), contenidos impredecibles, claves únicas por mensaje, métodos de transposición fuertes, etc.), adivinar las palabras correctas podría ser computacionalmente imposible sin más información. En su libro sobre descifrado de códigos 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 de la forma en que se codifica. En el cifrado Rail Fence, el texto simple se escribe hacia abajo y en diagonal sobre sucesivos "rieles" de una cerca imaginaria, y luego se mueve hacia arriba cuando llegamos al final. Luego, el mensaje se lee en filas. Por ejemplo, utilizando tres "rieles" y un mensaje de "NOS DESCUBRIERON, HUYAMOS INMEDIATAMENTE", el cifrador escribe:
W . . . E . . . C . . . R . . . L . . . T . . . E. E . R . D . S . O . E . E . F . E . A . O . C .. . A . . . Yo . . . V . . . D . . . E . . . N . .
Luego lee:
WECRL TEERD SOEEF EAOCA IVDEN
(El cifrador 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 simple y, por lo tanto, no contiene ninguna información sobre el texto simple).
El cifrado de la cerca de riel 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 consistía en un cilindro y una cinta que se enrollaba alrededor del cilindro. El mensaje a cifrar se escribía en la cinta enrollada. Las letras del mensaje original se reorganizaban cuando la cinta se desenrollaba del cilindro. Sin embargo, el mensaje se descifraba fácilmente cuando la cinta se enrollaba en un cilindro del mismo diámetro que el cilindro de cifrado. [2] Utilizando 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 desplaza horizontalmente y la cinta se enrolla verticalmente. Por lo tanto, el codificador lee:
¡GUAU! RECUERDE QUE DDNIF CSLEC
En un cifrado de ruta, el texto simple se escribe primero en una cuadrícula de dimensiones determinadas y luego se lee según un patrón indicado en la clave. Por ejemplo, si se utiliza el mismo texto simple que usamos para la cerca de rieles :
ESCRITORIOEESVELANIADCEDETCX
La clave podría especificar "espiral hacia adentro, en el sentido de las agujas del reloj, comenzando desde la esquina superior derecha". Eso daría como resultado un texto cifrado como el siguiente:
EJXCTEDEC DAEWRIORF EONALEVSE
Los cifrados de ruta tienen muchas más claves que una valla de ferrocarril. De hecho, para mensajes de longitud razonable, la cantidad de claves posibles es potencialmente demasiado grande para ser enumerada incluso por la maquinaria moderna. Sin embargo, no todas las claves son igualmente buenas. Las rutas mal elegidas dejarán fragmentos excesivos de texto simple, o texto simplemente invertido, y esto dará a los criptoanalistas una pista sobre las rutas.
Una variante 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 . Funcionaba de forma muy similar a un cifrado de ruta normal, pero transponía palabras completas en lugar de letras individuales. Como esto dejaría expuestas ciertas palabras muy sensibles, dichas palabras se ocultarían primero mediante un código . El encargado del cifrado también podía añadir palabras nulas completas, que a menudo se elegían para hacer que el texto cifrado fuera gracioso. [ cita requerida ]
A mediados del siglo XVII, Samuel Morland introdujo una forma temprana de transposición en columnas. Se perfeccionó mucho más tarde y se hizo muy popular a finales del siglo XIX y en el siglo XX, cuando el ejército francés, 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 vuelve a leer columna por columna, y las columnas se eligen en un orden desordenado. 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 mediante 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 regular, los espacios libres se rellenan con valores nulos; en un cifrado de transposición en columnas 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 utilizamos la palabra clave CEBRAS y el mensaje NOS DESCUBRIERON. HUYAMOS INMEDIATAMENTE . En una transposición en columnas regular, escribimos esto en la cuadrícula de la siguiente manera:
6 3 2 4 1 5DESGASTADOISCOVEFlecha rojaComerEQKJEU
Si se proporcionan cinco valores 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 entonces de la siguiente manera:
EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE
En el caso irregular, las columnas no se completan con valores nulos:
6 3 2 4 1 5DESGASTADOISCOVEFlecha rojaComermi
Esto da como resultado el siguiente texto cifrado:
EVLNA CDTES EAROF ODEEC WIREE
Para descifrarlo, el destinatario tiene que calcular 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 de 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 a lo largo de las columnas de la cuadrícula en el orden dado por las letras de la clave. El texto sin formato aparece en las filas. Un desciframiento parcial del texto cifrado anterior, después de escribir en la primera columna:
6 3 2 4 1 5. . . mi .. . . V .. . . yo .. . . . norte ..
En una variante, el mensaje se divide en segmentos con 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 se realiza por filas en lugar de columnas.
La transposición en columnas siguió utilizándose para fines serios como componente de cifrados más complejos al menos hasta la década de 1950.
Una transposición de una sola columna podía ser atacada adivinando las posibles longitudes de las columnas, 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 hacerla más fuerte, a menudo se usaba una transposición doble. Esto es simplemente una transposición de columnas aplicada dos veces. La misma clave puede usarse para ambas transposiciones, o pueden usarse dos claves diferentes.
En el siguiente ejemplo, utilizamos las claves JANEAUSTEN y AEROPLANES para cifrar el siguiente texto simple: " Los cifrados de transposición mezclan letras como piezas de un rompecabezas para crear una disposición indescifrable".
Los colores muestran cómo se desordenan las letras en cada paso de transposición. Si bien un solo paso solo provoca una reorganización menor, el segundo paso produce un efecto de desorden significativo si la última fila de la cuadrícula está incompleta.
Como ejemplo, podemos tomar el resultado de la transposición columnar 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 1EVLNACDTESEAROFODECABLE ECOLÓGICOmi
Como antes, esto se lee columna por columna 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 dar lugar tanto a la recuperación de los mensajes como a la recuperación de las claves (de modo que se pueda leer cualquier otro mensaje enviado 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, quienes normalmente podían encontrar rápidamente las claves una vez que habían interceptado una cantidad de mensajes de la misma longitud, lo que generalmente tomaba solo unos 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. [3]
Durante la Segunda Guerra Mundial, el cifrado de doble transposición fue utilizado por los grupos de la Resistencia holandesa , el Maquis francés y el Special Operations Executive (SOE) británico, encargado de gestionar las actividades clandestinas en Europa. [4] También fue utilizado por agentes de la Oficina de Servicios Estratégicos estadounidense [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 puede tratarse como una transposición simple 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 fue atacada individualmente. [7]
Una forma variante de transposición en columnas, 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 una 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 palabras clave recurrentes se numeran de forma idéntica, y TOMATO produce una cadena de claves de "432143".
4 3 2 1 4 3DESGASTADOISCOVEFlecha rojaComermi
Las columnas de texto simple con números únicos se transcriben hacia abajo; aquellas 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 un llenado irregular de las filas de la matriz, es decir, con algunos espacios dejados intencionalmente en blanco (o tachados como en el Rasterschlüssel 44 ), o rellenados posteriormente con otra parte del texto simple o letras al azar. [8]
Este método (atribuido al general Luigi Sacco [9] ) inicia una nueva fila una vez que el texto simple 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,
ROMPECABEZAS PARA SIEMPRE < Clave4 8 9 2 12 3 10 7 6 5 11 1 13 Espacios en blanco después del n.º:MÁS COMPLICADO * 1HETR * * * * * * * * * * 2RESPUESTAS * * * * * * * 3Yo * * * * * * * * * * * * * 4PATRÓN DE ACTIVIDADES * * * 5NLIKEACOM * * * * 6B _ _ _ _ _ _ _ * * * * * 7
Luego se eliminan las columnas según la transposición columnar regular: 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 una matriz configurada para la transposición en columnas con la clave de columna "CRYPTO" y llena de campos tachados según la clave de interrupción "SECRETO" (marcada con un asterisco), después de lo cual se coloca el mensaje "nos han descubierto, huyan de inmediato" en los espacios sobrantes. El texto cifrado resultante (las columnas se leen según la clave de transposición) es "WCEEO ERET RIVFC EODN SELE ADA".
CRIPTO1 4 6 3 5 2SOMOS* * DIS *CUBRIRED*FLECOMERUNA VEZ *
Otra forma de cifrado por transposición utiliza rejillas o máscaras físicas con cortes. 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 se usaban con fines militares 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 una transposición simple haciendo un recuento de frecuencias. Si el texto cifrado muestra una distribución de frecuencias muy similar a la del texto simple, lo más probable es que se trate de una transposición.
En general, los métodos de transposición son vulnerables a la anagramación (deslizar fragmentos de texto cifrado por el texto y luego buscar secciones que parezcan anagramas de palabras en inglés o en cualquier idioma en el que se haya escrito el texto simple, 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, se pueden ampliar. Las transposiciones más simples a menudo sufren la propiedad de que las claves muy cercanas a la clave correcta revelarán largas secciones de texto simple legible intercaladas con galimatías. En consecuencia, estos cifrados pueden ser vulnerables a algoritmos de búsqueda óptima, como los algoritmos genéticos [11] y los algoritmos de escalada de colinas [12] [13 ]
Existen varios métodos específicos para atacar mensajes codificados mediante un cifrado de transposición, entre ellos:
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 operativos en los estados del Sur durante las elecciones presidenciales de 1876 y así probar hechos de compra de votos , influyendo en las elecciones al Congreso de 1878-1879 . [14]
Una descripción detallada del criptoanálisis de un cifrado de transposición alemán se puede encontrar en el capítulo 7 de "La cámara negra americana" de Herbert Yardley.
Un código utilizado por el Asesino del Zodíaco , llamado "Z-340", organizado en secciones triangulares con sustitución de 63 símbolos diferentes por las letras y transposición diagonal de "movimiento de caballo", 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 simple de alta frecuencia no revela fragmentos de texto simple debido a la transposición. La anagramación de 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 eficaz cuando se emplea con fraccionamiento, es decir, una etapa preliminar que divide cada símbolo de texto simple en dos o más símbolos de texto cifrado. Por ejemplo, el alfabeto de texto simple podría escribirse en una cuadrícula y cada letra del mensaje podría reemplazarse por sus coordenadas (véase el cuadrado de Polibio y el tablero de ajedrez ). [16] Otro método de fraccionamiento es simplemente convertir el mensaje a código Morse , con un símbolo para los espacios, así como para los puntos y las rayas. [17]
Cuando se transpone un mensaje fraccionado de este tipo, los componentes de las letras individuales se separan ampliamente en el mensaje, con lo que se logra la difusión de Claude E. Shannon . Entre los ejemplos de cifrados que combinan el fraccionamiento y la transposición se 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. Si se repite el proceso de codificación en la cadena binaria varias veces antes de convertirla en caracteres ASCII, probablemente sea más difícil de descifrar. Muchos cifradores de bloques modernos utilizan formas más complejas de transposición relacionadas con esta idea simple.