cifrado de transposición

En criptografía , un cifrado por transposición (también conocido como cifrado por permutación) es un método de encriptación que reordena las posiciones de los caracteres ( transposición ) sin modificar los caracteres en sí. Los cifrados por transposición reordenan unidades de texto plano (normalmente caracteres o grupos de caracteres) según un sistema regular para producir un texto cifrado que es una permutación del texto plano. Se diferencian de los cifrados por sustitución , que no cambian la posición de las unidades de texto plano, sino que modifican 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 en métodos de encriptación complejos y de alta seguridad como el Estándar de Cifrado Avanzado (AES).

Los textos planos se pueden transformar en textos cifrados mediante una clave , alterando el orden de los caracteres como las piezas de un rompecabezas . El mensaje resultante es difícil de descifrar sin la clave, ya que existen muchas maneras de ordenar los caracteres.

Por ejemplo, el texto plano "THIS IS 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 DIATHESIS, DISSIPATE, WIDTH, etc., pero le llevaría tiempo reconstruir el texto plano debido a la gran cantidad de combinaciones de letras y palabras. En cambio, alguien con la clave podría reconstruir el mensaje fácilmente.

Clave de cifrado 1 4 5 3 2 6 Secuencia (letras clave en orden alfabético) ESTO ES Texto plano WIKIPE DIA * * * Texto cifrado por columna: #1 TWD, #2 IP, #3 SI, #4 HII, #5 IKA, #6 SE Texto cifrado en grupos de 5 para facilitar su lectura: TWDIP SIHII IKASE

En la práctica, un mensaje tan corto y con una palabra clave tan predecible sería descifrado casi de inmediato con técnicas de criptoanálisis .

Los cifrados por transposición presentan varias vulnerabilidades (véase la sección sobre "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, de más de 100 a 200 letras), contenido impredecible, claves únicas por mensaje, métodos de transposición robustos, etc.), adivinar las palabras correctas podría ser computacionalmente imposible sin información adicional. En su libro sobre el descifrado de cifrados históricos, Elonka Dunin y Klaus Schmeh describen la transposición columnar doble (véase más abajo) como «uno de los mejores cifrados manuales conocidos». ^{[ 1 ]}

El cifrado Rail Fence es una forma de cifrado por transposición que recibe su nombre de la manera en que se codifica. En este cifrado, el texto plano se escribe hacia abajo y en diagonal sobre los sucesivos "rieles" de una cerca imaginaria, y luego se mueve hacia arriba al llegar al final. El mensaje se lee en filas. Por ejemplo, usando tres "rieles" y el mensaje "WE ARE DISCOVERED FLEE AT ONCE", quien cifra escribe:

O . . . 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 facilitar la lectura del cifrado. El espaciado no está relacionado con los espacios en el texto original y, por lo tanto, no contiene ninguna información sobre este.)

El cifrado de la cerca de riel sigue un patrón similar al de la escítala (pronunciada / ˈ s k ɪ t əl iː / o / ˈ s k aɪ t eɪ l / ), 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 reordenaban 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 ]} Usando el mismo ejemplo anterior, 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 extiende horizontalmente y la cinta se enrolla verticalmente a su alrededor. Por lo tanto, el cifrador lee lo siguiente:

WOEEV EAEAR RTEEO DDNIF CSLEC

En un cifrado de ruta, el texto plano 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 plano que usamos para rail fence :

WRIORFEOE EESVELANJ ADCEDETCX

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

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 claves son igual de buenas. Las rutas mal elegidas dejarán fragmentos excesivos de texto plano, o texto simplemente invertido, lo que 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 . Este funcionaba de forma muy similar a un cifrado de ruta común, pero transponía palabras completas en lugar de letras individuales. Dado que esto dejaría expuestas ciertas palabras de alta sensibilidad, estas se ocultaban previamente mediante un código . El descifrador también podía añadir palabras vacías completas, que a menudo se elegían para dar un toque de humor al texto cifrado.

Una transposición columnar simple podía ser atacada adivinando posibles longitudes de columna, escribiendo el mensaje en sus columnas (pero en el orden incorrecto, ya que la clave aún se desconocía) y luego buscando posibles anagramas . Por lo tanto, para hacerla más segura, a menudo se utilizaba una doble transposición. Esta consiste simplemente en aplicar la transposición columnar dos veces. Se puede usar la misma clave para ambas transposiciones, o bien dos claves diferentes.

5 6 4 2 3 1 EVLNAC DTESEA ROFODE ECWIRE mi

CAEEN SOIAE DRLEF WEDRE EVTOC

Una variante de la 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 la palabra clave se tratan como si fuera la siguiente letra en orden alfabético; por ejemplo, la palabra clave TOMATO produce la cadena numérica "532164".

En la transposición de Myszkowski, las letras clave recurrentes se numeran de forma idéntica, lo que da como resultado la cadena de claves "432143".

4 3 2 1 4 3 USADO ISCOVE PULGA ROJA EATONC mi

Las columnas de texto plano con números únicos se transcriben de arriba hacia abajo; las que tienen números recurrentes se transcriben de izquierda a derecha:

ROFOA CDTED SEEEA CWEIV RLENE

Un cifrado de transposición interrumpido ^{[ 10 ]} 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 llenados posteriormente con otra parte del texto plano o letras aleatorias. ^{[ 10 ]}

ROMPECABEZAS PARA SIEMPRE < Clave 4 8 9 2 12 3 10 7 6 5 11 1 13 Espacios en blanco después del n.º: MÁS COMPLICADO * 1 HETR * * * * * * * * * 2 ANSPOS * * * * * * * 3 Yo * * * * * * * * * * * * 4 PATRÓN DE CIÓN * * * 5 NLIKEACOM * * * * 6 B _ _ _ _ _ _ _ * * * * * 7

CRIPTO 1 4 6 3 5 2 SOMOS * * DIS * CUBRIR ED * FLE COMER UNA 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 rejillas se propusieron por primera vez en 1550 y todavía se utilizaban en el ámbito militar 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 mediante un conteo de frecuencias. Si el texto cifrado presenta una distribución de frecuencias muy similar a la del texto plano, 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 : se mueven fragmentos de texto cifrado, se buscan secciones que parezcan anagramas de palabras en inglés o en el idioma en que se escribió el texto original, y se resuelven dichos anagramas. Una vez encontrados, estos anagramas revelan información sobre el patrón de transposición y, por lo tanto, pueden extenderse. Las transposiciones más simples suelen presentar el problema de que las claves muy cercanas a la correcta revelan largas secciones de texto legible intercaladas con galimatías. En consecuencia, estos cifrados pueden ser vulnerables a algoritmos de búsqueda óptima, como los algoritmos genéticos ^{[ 13 ]} y los algoritmos de ascenso de colinas ^{[ 14 ] [ 15 ]} .

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

1. Ataque de texto plano conocido : Utilizar partes conocidas o adivinadas del texto plano (por ejemplo, nombres, lugares, fechas, números, frases) para ayudar a deducir el orden probable de las columnas utilizadas para llevar a cabo la transposición y/o el tema probable del texto plano.
2. Ataque por fuerza bruta : Si las claves se derivan de palabras de diccionario o frases de libros u otras fuentes disponibles públicamente, puede ser posible descifrar la solución por fuerza bruta probando miles de millones de posibles palabras, combinaciones de palabras y frases como claves.
3. Ataque en profundidad: Si dos o más mensajes de la misma longitud se codifican con las mismas claves, los mensajes se pueden alinear y anagramar hasta que muestren un texto significativo en los mismos lugares, sin necesidad de conocer los pasos de transposición que se hayan producido.
4. Ataque estadístico: Las estadísticas sobre la frecuencia de combinaciones de dos, tres, etc., letras en un idioma pueden utilizarse para alimentar una función de puntuación en un algoritmo que invierte gradualmente las posibles transposiciones en función de qué cambios producirían las combinaciones más probables. Por ejemplo, el par de dos letras QU es más común que QT en textos en inglés, por lo que un criptoanalista intentará transposiciones que coloquen QU juntas.

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 , influyendo en las elecciones al Congreso de 1878-1879 . ^{[ 16 ]}

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

Un cifrado utilizado por el Asesino del Zodiaco , llamado "Z-340", organizado en secciones triangulares con sustitución de 63 símbolos diferentes por las letras y transposición diagonal "movimiento de caballo", permaneció sin resolver durante más de 51 años, hasta que un equipo internacional de ciudadanos particulares lo descifró el 5 de diciembre de 2020, utilizando software especializado. ^{[ 17 ]}

La transposición se suele combinar 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 las debilidades de ambos. Reemplazar símbolos de alta frecuencia del texto cifrado con letras de alta frecuencia del texto plano no revela fragmentos del texto plano debido a la transposición. El anagrama de la transposición no funciona debido a la sustitución. La técnica es particularmente potente si se combina con la fragmentación (véase más adelante). 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 la fragmentación, es decir, una etapa preliminar que divide cada símbolo del texto plano en dos o más símbolos del texto cifrado. Por ejemplo, el alfabeto del texto plano podría escribirse en una cuadrícula y cada letra del mensaje reemplazarse por sus coordenadas (véase el cuadrado de Polibio y el tablero de ajedrez cruzado ). ^{[ 18 ]} Otro método de fragmentación consiste simplemente en convertir el mensaje a código Morse , con un símbolo para los espacios, así como para los puntos y las rayas. ^{[ 19 ]}

Cuando se transpone un mensaje fraccionado de este tipo, los componentes de las letras individuales se separan ampliamente en el mensaje, logrando así la difusión descrita por Claude E. Shannon . Algunos ejemplos de cifrados que combinan fraccionamiento y transposición son el cifrado bífido , el cifrado trífido , el cifrado ADFGVX , el cifrado JN-40 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 de la cadena binaria varias veces antes de convertirla en caracteres ASCII probablemente dificultaría su descifrado. Muchos cifrados de bloques modernos utilizan formas de transposición más complejas relacionadas con esta idea simple.

• cifrado de sustitución
• Prohibición (unidad)
• Temas de criptografía

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