Cifrado de sustitución

En criptografía, un cifrado de sustitución es un método de cifrado en el que las unidades de texto plano se reemplazan con el texto cifrado, de manera definida, con la ayuda de una clave; las "unidades" pueden ser letras sueltas (las más comunes), pares de letras, trillizos de letras, mezclas de las anteriores, etc. El receptor descifra el texto realizando el proceso de sustitución inversa para extraer el mensaje original.

Los cifrados por sustitución se pueden comparar con los cifrados por transposición. En un cifrado de transposición, las unidades del texto sin formato se reorganizan en un orden diferente y, por lo general, bastante complejo, pero las unidades en sí no se modifican. Por el contrario, en un cifrado por sustitución, las unidades del texto sin formato se conservan en la misma secuencia en el texto cifrado, pero las unidades mismas se modifican.

Hay varios tipos diferentes de cifrado de sustitución. Si el cifrado opera con letras individuales, se denomina cifrado de sustitución simple; un cifrado que opera en grupos más grandes de letras se denomina poligráfico. Un cifrado monoalfabético utiliza una sustitución fija en todo el mensaje, mientras que un cifrado polialfabético utiliza una serie de sustituciones en diferentes posiciones del mensaje, donde una unidad del texto sin formato se asigna a una de varias posibilidades en el texto cifrado y viceversa.

Sustitución simple

ROT13 es un cifrado César, un tipo de cifrado de sustitución. En ROT13, el alfabeto se rota 13 pasos.

La sustitución de letras individuales por separado (sustitución simple) se puede demostrar escribiendo el alfabeto en algún orden para representar la sustitución. Esto se denomina alfabeto de sustitución. El alfabeto cifrado puede cambiarse o invertirse (creando los cifrados César y Atbash, respectivamente) o codificarse de una manera más compleja, en cuyo caso se denomina alfabeto mixto o alfabeto trastornado. Tradicionalmente, los alfabetos mixtos se pueden crear escribiendo primero una palabra clave, eliminando las letras repetidas y luego escribiendo todas las letras restantes del alfabeto en el orden habitual.

Usando este sistema, la palabra clave "cebras" nos da los siguientes alfabetos:

Un mensaje

Huye de inmediato. ¡Estamos descubiertos!

cifra a

SIAA ZQ LKBA. ¡VA ZOA RFPBLUAOAR!

Por lo general, el texto cifrado se escribe en bloques de longitud fija, omitiendo la puntuación y los espacios; esto se hace para ocultar los límites de las palabras del texto sin formato y ayudar a evitar errores de transmisión. Estos bloques se denominan "grupos" y, a veces, un "recuento de grupos" (es decir, el número de grupos) se proporciona como una verificación adicional. A menudo se utilizan grupos de cinco letras, que datan de cuando los mensajes se transmitían por telégrafo:

SIAAZ QLKBA VAZOA RFPBL UAOAR

Si la longitud del mensaje no es divisible por cinco, se puede rellenar al final con "nulos". Estos pueden ser cualquier carácter que se descifre a tonterías obvias, para que el receptor pueda detectarlos fácilmente y descartarlos.

El alfabeto del texto cifrado a veces es diferente del alfabeto del texto sin formato; por ejemplo, en el cifrado de la pocilga, el texto cifrado consta de un conjunto de símbolos derivados de una cuadrícula. Por ejemplo:

Sin embargo, tales características hacen poca diferencia en la seguridad de un esquema; como mínimo, cualquier conjunto de símbolos extraños se puede volver a transcribir en un alfabeto de la A a la Z y tratar con normalidad.

En listas y catálogos para vendedores, a veces se usa un cifrado muy simple para reemplazar dígitos numéricos por letras.

Ejemplo: MAT se usaría para representar 120.

Seguridad para cifrados de sustitución simples

Aunque el método tradicional de palabras clave para crear un alfabeto de sustitución mixta es simple, una seria desventaja es que las últimas letras del alfabeto (que en su mayoría son de baja frecuencia) tienden a permanecer al final. Una forma más sólida de construir un alfabeto mixto es generar el alfabeto de sustitución completamente al azar.

Aunque el número de posibles alfabetos de sustitución es muy grande (26! ≈ 2^88.4, o alrededor de 88 bits), este cifrado no es muy fuerte y se descifra fácilmente. Siempre que el mensaje tenga una longitud razonable (ver más abajo), el criptoanalista puede deducir el significado probable de los símbolos más comunes analizando la distribución de frecuencia del texto cifrado. Esto permite la formación de palabras parciales, que se pueden completar tentativamente, expandiendo progresivamente la solución (parcial) (ver análisis de frecuencia para una demostración de esto). En algunos casos, las palabras subyacentes también se pueden determinar a partir del patrón de sus letras; por ejemplo, atraer, óseo, y las palabras con esas dos como raíz son las únicas palabras comunes en inglés con el patrón ABBCADB. Muchas personas resuelven estos cifrados por diversión, como con los acertijos de criptogramas en el periódico.

Según la distancia de unicidad del inglés, se requieren 27,6 letras de texto cifrado para descifrar una sustitución simple de alfabeto mixto. En la práctica, normalmente se necesitan alrededor de 50 letras, aunque algunos mensajes se pueden romper con menos si se encuentran patrones inusuales. En otros casos, se puede diseñar el texto sin formato para que tenga una distribución de frecuencia casi plana, y el criptoanalista requerirá textos sin formato mucho más largos.

Nomenclador

El mensaje de nomenclador falsificado utilizado en el Plot Babington

Una tabla de código de nomenclator francés

Una variante común del cifrado de sustitución es el nomenclador. Nombrado en honor al funcionario público que anunció los títulos de los dignatarios visitantes, este cifrado utiliza una pequeña hoja de código que contiene tablas de sustitución de letras, sílabas y palabras, a veces homofónicas, que normalmente convierten los símbolos en números. Originalmente, la parte del código estaba restringida a los nombres de personas importantes, de ahí el nombre del cifrado; en años posteriores, también cubrió muchas palabras comunes y nombres de lugares. Los símbolos de palabras completas (palabras clave en el lenguaje moderno) y letras (cifrado en el lenguaje moderno) no se distinguían en el texto cifrado. Los Rossignols' Gran cifrado utilizado por Luis XIV de Francia fue uno.

Los nomencladores fueron la norma de la correspondencia diplomática, el espionaje y la conspiración política avanzada desde principios del siglo XV hasta finales del siglo XVIII; la mayoría de los conspiradores eran y han seguido siendo menos criptográficamente sofisticados. Aunque los criptoanalistas de inteligencia del gobierno rompían sistemáticamente los nomencladores a mediados del siglo XVI, y había sistemas superiores disponibles desde 1467, la respuesta habitual al criptoanálisis era simplemente hacer las tablas más grandes. A fines del siglo XVIII, cuando el sistema comenzaba a extinguirse, algunos nomencladores tenían 50.000 símbolos.

Sin embargo, no se rompieron todos los nomencladores; Hoy en día, el criptoanálisis de textos cifrados archivados sigue siendo un área fructífera de investigación histórica.

Sustitución homofónica

Un primer intento de aumentar la dificultad de los ataques de análisis de frecuencia en los cifrados de sustitución fue disfrazar las frecuencias de las letras del texto sin formato mediante homofonía. En estos cifrados, las letras de texto sin formato se asignan a más de un símbolo de texto cifrado. Por lo general, los símbolos de texto sin formato de mayor frecuencia reciben más equivalentes que las letras de menor frecuencia. De esta manera, la distribución de frecuencias se aplana, lo que dificulta el análisis.

Dado que se requerirán más de 26 caracteres en el alfabeto del texto cifrado, se emplean varias soluciones para inventar alfabetos más grandes. Quizás lo más simple es usar una sustitución numérica 'alfabeto'. Otro método consiste en variaciones simples del alfabeto existente; mayúsculas, minúsculas, al revés, etc. De forma más artística, aunque no necesariamente más segura, algunas cifras homofónicas empleaban alfabetos totalmente inventados de símbolos fantasiosos.

El cifrado de libro es un tipo de cifrado homofónico, un ejemplo son los cifrados de Beale. Esta es una historia de un tesoro enterrado que se describió en 1819-1821 mediante el uso de un texto cifrado que estaba relacionado con la Declaración de Independencia. Aquí, cada carácter del texto cifrado estaba representado por un número. El número se determinó tomando el carácter del texto sin formato y encontrando una palabra en la Declaración de Independencia que comenzara con ese carácter y usando la posición numérica de esa palabra en la Declaración de Independencia como la forma cifrada de esa letra. Dado que muchas palabras en la Declaración de Independencia comienzan con la misma letra, el cifrado de ese carácter podría ser cualquiera de los números asociados con las palabras en la Declaración de Independencia que comienzan con esa letra. Descifrar el carácter de texto cifrado X (que es un número) es tan simple como buscar la palabra X de la Declaración de Independencia y usar la primera letra de esa palabra como el carácter descifrado.

Stahl describió otro cifrado homofónico y fue uno de los primeros intentos de brindar seguridad informática a los sistemas de datos en las computadoras a través del cifrado. Stahl construyó el cifrado de tal manera que el número de homófonos para un carácter dado era proporcional a la frecuencia del carácter, lo que dificultaba mucho más el análisis de frecuencia.

Francesco I Gonzaga, duque de Mantua, usó el ejemplo más antiguo conocido de un cifrado de sustitución homofónica en 1401 para la correspondencia con Simone de Crema.

Sustitución polialfabética

El trabajo de Al-Qalqashandi (1355-1418), basado en el trabajo anterior de Ibn al-Durayhim (1312-1359), contenía la primera discusión publicada sobre la sustitución y transposición de cifras, así como la primera descripción de un cifrado polialfabético, en el que a cada letra del texto sin formato se le asigna más de un sustituto. Los cifrados de sustitución polialfabéticos fueron descritos más tarde en 1467 por Leone Battista Alberti en forma de discos. Johannes Trithemius, en su libro Steganographia (griego antiguo para "escritura oculta") introdujo la forma ahora más estándar de un tableau (ver más abajo; ca. 1500 pero no publicado hasta mucho después). Una versión más sofisticada que utiliza alfabetos mixtos fue descrita en 1563 por Giovanni Battista della Porta en su libro, De Furtivis Literarum Notis (en latín, "Sobre caracteres ocultos en la escritura").

En un cifrado polialfabético, se utilizan varios alfabetos cifrados. Para facilitar el cifrado, todos los alfabetos suelen escribirse en una tabla grande, tradicionalmente llamada tableau. El cuadro suele ser de 26 × 26, por lo que hay disponibles 26 alfabetos de texto cifrado completo. El método de llenar el cuadro y de elegir qué alfabeto usar a continuación define el cifrado polialfabético particular. Todos estos cifrados son más fáciles de descifrar de lo que se creía, ya que los alfabetos de sustitución se repiten para textos sin formato suficientemente grandes.

Uno de los más populares fue el de Blaise de Vigenère. Publicado por primera vez en 1585, se consideró indescifrable hasta 1863 y, de hecho, se le llamó comúnmente le chiffre indéchiffrable (en francés, "cifrado indescifrable").

En el cifrado de Vigenère, la primera fila del cuadro se completa con una copia del alfabeto del texto sin formato, y las filas sucesivas simplemente se desplazan un lugar a la izquierda. (Un cuadro tan simple se llama tabula recta, y matemáticamente corresponde a agregar el texto sin formato y las letras clave, módulo 26). Luego se usa una palabra clave para elegir qué alfabeto de texto cifrado usar. Cada letra de la palabra clave se usa por turnos y luego se repiten nuevamente desde el principio. Entonces, si la palabra clave es 'CAT', la primera letra del texto sin formato se cifra con el alfabeto 'C', la segunda con 'A' y la tercera con 'T', el cuarto bajo 'C' de nuevo, y así sucesivamente. En la práctica, las claves de Vigenère eran a menudo frases de varias palabras.

En 1863, Friedrich Kasiski publicó un método (probablemente descubierto en secreto e independientemente por Charles Babbage antes de la guerra de Crimea) que permitía calcular la longitud de la palabra clave en un mensaje cifrado de Vigenère. Una vez hecho esto, las letras del texto cifrado que habían sido codificadas bajo el mismo alfabeto podían seleccionarse y atacarse por separado como una serie de sustituciones simples semiindependientes, complicadas por el hecho de que dentro de un alfabeto las letras estaban separadas y no formaban palabras completas. pero simplificado por el hecho de que normalmente se había empleado una tabula recta.

Como tal, incluso hoy en día, un cifrado de tipo Vigenère debería ser teóricamente difícil de descifrar si se utilizan alfabetos mixtos en el cuadro, si la palabra clave es aleatoria y si la longitud total del texto cifrado es inferior a 27,67 veces la longitud de la palabra clave.. Estos requisitos rara vez se entienden en la práctica, por lo que la seguridad de los mensajes cifrados de Vigenère suele ser menor de lo que podría haber sido.

Otros polialfabéticos notables incluyen:

• El cifrado de Gronsfeld. Esto es idéntico al Vigenère excepto que sólo se utilizan 10 alfabetos, por lo que la "palabra clave" es numérica.
• El código de Beaufort. Esto es prácticamente igual que el Vigenère, excepto el tabula recta es reemplazado por uno atrasado, matemáticamente equivalente a ciphertext = clave - texto llano. Esta operación es auto-inverso, por lo que la misma tabla se utiliza tanto para la encriptación como para la desencriptación.
• El cifrado autokey, que mezcla el texto claro con una clave para evitar la periodicidad.
• El cifrado clave de funcionamiento, donde la clave se hace muy larga utilizando un pasaje de un libro o texto similar.

Los cifrados de flujo modernos también pueden verse, desde una perspectiva lo suficientemente abstracta, como una forma de cifrado polialfabético en el que todo el esfuerzo se ha centrado en hacer que el flujo de claves sea lo más largo e impredecible posible.

Sustitución poligráfica

En un cifrado de sustitución poligráfico, las letras del texto sin formato se sustituyen en grupos más grandes, en lugar de sustituir las letras individualmente. La primera ventaja es que la distribución de frecuencias es mucho más plana que la de las letras individuales (aunque en realidad no es plana en los idiomas reales; por ejemplo, 'TH' es mucho más común que 'XQ' en Inglés). En segundo lugar, el mayor número de símbolos requiere correspondientemente más texto cifrado para analizar productivamente las frecuencias de las letras.

Sustituir pares letras tomarían un alfabeto de sustitución 676 símbolos largos (${displaystyle 26^{2}$). En el mismo De Furtivis Literarum Notis mencionado anteriormente, della Porta realmente propuso tal sistema, con una mesa de 20 x 20 (para las 20 letras del alfabeto italiano/latino que estaba utilizando) llena de 400 glifos únicos. Sin embargo, el sistema era poco práctico y probablemente nunca se utilizaba.

El primer cifrado digráfico práctico (sustitución por pares) fue el llamado cifrado Playfair, inventado por Sir Charles Wheatstone en 1854. En este cifrado, una cuadrícula de 5 x 5 se llena con las letras de un alfabeto mixto (dos letras, generalmente I y J, se combinan). Luego se simula una sustitución digráfica tomando pares de letras como dos esquinas de un rectángulo y usando las otras dos esquinas como texto cifrado (consulte el artículo principal de cifrado de Playfair para ver un diagrama). Las reglas especiales manejan letras dobles y pares que caen en la misma fila o columna. Playfair estuvo en uso militar desde la Guerra de los Bóers hasta la Segunda Guerra Mundial.

Félix Delastelle introdujo varios otros poligráficos prácticos en 1901, incluidos los cifrados bífido y de cuatro cuadrados (ambos digráficos) y el cifrado trífido (probablemente el primer trigráfico práctico).

El Cipher Hill, inventado en 1929 por Lester S. Hill, es una sustitución poligráfica que puede combinar grupos mucho más grandes de letras simultáneamente utilizando álgebra lineal. Cada letra se trata como un dígito en la base 26: A = 0, B =1, y así sucesivamente. (En una variación, se agregan 3 símbolos adicionales para hacer la base principal.) Un bloque de letras n se considera entonces como un vector de dimensiones n, y multiplicado por una matriz n x n, modulo 26. Los componentes de la matriz son la clave, y debe ser al azar siempre que la matriz sea invertible en ${displaystyle mathbb {Z} _{26}{n}$ (para asegurar la descifración es posible). En 1929 se patentó una versión mecánica del Cifra Hill de la dimensión 6.

El cifrado de Hill es vulnerable a un ataque de texto sin formato conocido porque es completamente lineal, por lo que debe combinarse con algún paso no lineal para derrotar este ataque. La combinación de pasos difusivos lineales débiles cada vez más anchos como un cifrado de Hill, con pasos de sustitución no lineales, en última instancia conduce a una red de sustitución-permutación (por ejemplo, un cifrado de Feistel), por lo que es posible, desde esta perspectiva extrema, considerar cifrados de bloques modernos como un tipo de sustitución poligráfica.

Cifrados de sustitución mecánica

Enigma cipher machine as used by the German military in World War II

Entre alrededor de la Primera Guerra Mundial y la disponibilidad generalizada de computadoras (para algunos gobiernos esto fue aproximadamente en la década de 1950 o 1960; para otras organizaciones fue una década o más después; para las personas no fue antes de 1975), las implementaciones mecánicas de Los cifrados de sustitución polialfabéticos se utilizaron ampliamente. Varios inventores tenían ideas similares casi al mismo tiempo, y las máquinas de cifrado de rotor se patentaron cuatro veces en 1919. La más importante de las máquinas resultantes fue la Enigma, especialmente en las versiones utilizadas por el ejército alemán desde aproximadamente 1930. Los Aliados también desarrollaron y máquinas de rotor usadas (por ejemplo, SIGABA y Typex).

Todos estos eran similares en el sentido de que la letra sustituida se elegía eléctricamente entre la gran cantidad de combinaciones posibles resultantes de la rotación de varios discos de letras. Dado que uno o más de los discos giraban mecánicamente con cada letra de texto sin formato cifrada, la cantidad de alfabetos utilizados era astronómica. Sin embargo, las primeras versiones de estas máquinas eran frágiles. William F. Friedman, del SIS del Ejército de los EE. UU., descubrió vulnerabilidades en la máquina de rotor de Hebern, y Dillwyn Knox, de GC&CS, resolvió versiones de la máquina Enigma (aquellas sin el "plugboard& #34;) mucho antes de que comenzara la Segunda Guerra Mundial. Los criptoanalistas aliados, sobre todo los de Bletchley Park, rompieron el tráfico protegido por prácticamente todos los Enigmas militares alemanes, comenzando con la variante del ejército alemán utilizada a principios de la década de 1930. Esta versión fue descifrada por la inspiración matemática de Marian Rejewski en Polonia.

Hasta donde se sabe públicamente, ningún mensaje protegido por las máquinas SIGABA y Typex se rompió durante o cerca del tiempo en que estos sistemas estaban en servicio.

El bloc de notas de una sola vez

Un tipo de cifrado de sustitución, el bloc de notas de un solo uso, es único. Fue inventado cerca del final de la Primera Guerra Mundial por Gilbert Vernam y Joseph Mauborgne en los Estados Unidos. Claude Shannon demostró matemáticamente que era irrompible, probablemente durante la Segunda Guerra Mundial; su trabajo se publicó por primera vez a fines de la década de 1940. En su implementación más común, el bloc de notas de un solo uso puede denominarse cifrado de sustitución solo desde una perspectiva inusual; normalmente, la letra del texto sin formato se combina (no se sustituye) de alguna manera (por ejemplo, XOR) con el carácter de material clave en esa posición.

El bloc de notas de una sola vez es, en la mayoría de los casos, poco práctico, ya que requiere que el material clave sea tan largo como el texto sin formato, realmente aleatorio, usado una vez y solo una vez, y se mantuvo en secreto para todos, excepto para el remitente y el destinatario previsto. Cuando se violan estas condiciones, aunque sea marginalmente, la libreta de una sola vez ya no es irrompible. Los mensajes de bloc de notas de un solo uso soviéticos enviados desde los EE. UU. Por un breve tiempo durante la Segunda Guerra Mundial utilizaron material clave no aleatorio. Los criptoanalistas de EE. UU., a partir de finales de los años 40, pudieron, total o parcialmente, descifrar unos pocos miles de mensajes de varios cientos de miles. (Ver proyecto Venona)

En una implementación mecánica, similar al equipo Rockex, el bloc de notas de un solo uso se utilizó para los mensajes enviados en la línea directa Moscú-Washington establecida después de la crisis de los misiles en Cuba.

Sustitución en criptografía moderna

Los cifrados de sustitución, como se mencionó anteriormente, especialmente los cifrados manuales más antiguos de lápiz y papel, ya no se usan con seriedad. Sin embargo, el concepto criptográfico de sustitución continúa incluso hoy. Desde una perspectiva suficientemente abstracta, los cifrados de bloques modernos orientados a bits (por ejemplo, DES o AES) pueden verse como cifrados de sustitución en un alfabeto binario enormemente grande. Además, los cifrados en bloque a menudo incluyen tablas de sustitución más pequeñas llamadas S-boxes. Véase también red de sustitución-permutación.

Cifrados de sustitución en la cultura popular

• Sherlock Holmes rompe un cifrado de sustitución en "The Adventure of the Dancing Men". Allí, el cifrado permaneció indescifrado durante años si no décadas; no debido a su dificultad, sino porque nadie sospechaba que era un código, en lugar de considerarlo garabatos infantiles.
• El idioma Al Bhed en Final Fantasy X es en realidad un cifrado de sustitución, aunque se pronuncia fonéticamente (es decir, "usted" en inglés se traduce a "oui" en Al Bhed, pero se pronuncia de la misma manera que "oui" se pronuncia en francés).
• El alfabeto de Minbari Babylon 5 serie es un cifrado de sustitución del inglés.
• El idioma en Starfox Adventures: Planeta dinosaurio hablada por los nativos Saurians y Krystal es también un cifrado de sustitución del alfabeto inglés.
• El programa de televisión Futurama contenía un cifrado de sustitución en el que las 26 letras fueron reemplazadas por símbolos y llamadas "Alien Language". Esto fue descifrado bastante rápidamente por los espectadores duros de la muerte mostrando un anuncio "Slurm" con la palabra "Beber" tanto en inglés claro como en el lenguaje alienígena dando así la llave. Más tarde, los productores crearon un segundo idioma alienígena que utilizó una combinación de Cifras de reemplazo y matemáticas. Una vez que se descifra la letra inglesa del idioma extranjero, entonces se añade el valor numérico de esa carta (0 para "A" a 25 para "Z" respectivamente) al valor de la carta anterior que muestra la letra deseada. Estos mensajes se pueden ver a lo largo de cada episodio de la serie y las películas posteriores.
• Al final de cada temporada 1 episodio de la serie de dibujos animados Gravity Falls, durante el rollo de crédito, hay uno de los tres códigos de sustitución simples: A -3 ciférico César (referido por "3 cartas de vuelta" al final de la secuencia de apertura), un ciférico Atbash, o un ciférico de sustitución simple de letras a números. El final de la temporada 1 codifica un mensaje con los tres. En la segunda temporada, los cíferos Vigenère se utilizan en lugar de los diversos cíferos monoalfabéticos, cada uno utilizando una clave oculta en su episodio.
• En la serie Artemis Fowl de Eoin Colfer hay tres cifrados de sustitución; Gnommish, Centaurean y Eternean, que corren por el fondo de las páginas o están en otro lugar dentro de los libros.
• In Bitterblue, la tercera novela de Kristin Cashore, los cifrados de sustitución sirven como una forma importante de comunicación codificada.
• En el videojuego de 2013 BioShock Infinite, hay cifrados de sustitución escondidos a lo largo del juego en el que el jugador debe encontrar libros de código para ayudar a descifrarlos y obtener acceso a un excedente de suministros.
• En el anime adaptación de ¡El Diablo es un tiempo parcial!, el lenguaje de Ente Isla, llamado Entean, utiliza un cifrado de sustitución con el alfabeto de cifertexto AZYXEWVTISRLPNOMQKJHUGFDCB, dejando sólo A, E, I, O, U, L, N, y Q en sus posiciones originales.