En criptografía , un cifrado por sustitución es un método de cifrado en el que se sustituyen unidades de texto simple por el texto cifrado , de una manera definida, con la ayuda de una clave; las "unidades" pueden ser letras simples (lo más común), pares de letras, tripletes 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 por transposición, las unidades del texto simple 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 simple se mantienen en la misma secuencia en el texto cifrado, pero las unidades en sí se modifican.
Existen distintos tipos de cifrados por sustitución. Si el cifrado funciona con letras individuales, se denomina cifrado por sustitución simple ; si funciona con grupos más grandes de letras, se denomina cifrado 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 distintas posiciones del mensaje, donde una unidad del texto simple se asigna a una de varias posibilidades en el texto cifrado y viceversa.
La primera descripción publicada de cómo descifrar cifrados de sustitución simples fue dada por Al-Kindi en Un manuscrito sobre descifrado de mensajes criptográficos escrito alrededor del año 850 d. C. El método que describió ahora se conoce como análisis de frecuencia .
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 se puede desplazar o invertir (creando los cifrados César y Atbash , respectivamente) o se puede mezclar de una manera más compleja, en cuyo caso se denomina alfabeto mixto o alfabeto alterado . Tradicionalmente, los alfabetos mixtos se pueden crear escribiendo primero una palabra clave, eliminando las letras repetidas en ella y luego escribiendo todas las letras restantes del alfabeto en el orden habitual.
Utilizando este sistema, la palabra clave " cebras " nos da los siguientes alfabetos:
Un mensaje
¡Huid inmediatamente, nos han descubierto!
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 simple y para ayudar a evitar errores de transmisión. Estos bloques se denominan "grupos" y, a veces, se proporciona un "conteo de grupos" (es decir, el número de grupos) como verificación adicional. A menudo se utilizan grupos de cinco letras, que datan de la época en que 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 " nulo ". Estos pueden ser caracteres que descifren un sinsentido obvio, de modo que el receptor pueda detectarlos fácilmente y descartarlos.
El alfabeto de texto cifrado a veces es diferente del alfabeto de texto simple; por ejemplo, en el cifrado pigpen , el texto cifrado consiste en un conjunto de símbolos derivados de una cuadrícula. Por ejemplo:
Sin embargo, estas características hacen poca diferencia en la seguridad de un sistema: por lo menos, cualquier conjunto de símbolos extraños puede transcribirse nuevamente a un alfabeto de la A a la Z y manejarse con normalidad.
En listas y catálogos para vendedores, a veces se utiliza un cifrado muy simple para sustituir dígitos numéricos por letras.
Ejemplos: MAT se utilizaría para representar 120, PAPR se utilizaría para 5256 y OFTK se utilizaría para 7803.
Aunque el método tradicional de palabras clave para crear un alfabeto de sustitución mixto es simple, una desventaja importante es que las últimas letras del alfabeto (que en su mayoría son de baja frecuencia) tienden a quedarse al final. Una forma más eficaz de construir un alfabeto mixto es generar el alfabeto de sustitución de forma completamente aleatoria.
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 frecuencias del texto cifrado. Esto permite la formación de palabras parciales, que se pueden completar de forma provisional, ampliando progresivamente la solución (parcial) (ver el análisis de frecuencias 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, las palabras inglesas tater , ninth y paper tienen todas el patrón ABACD . Mucha gente resuelve 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 simple sustitución de un alfabeto mixto. En la práctica, normalmente se necesitan unas 50 letras, aunque algunos mensajes se pueden descifrar con menos si se encuentran patrones inusuales. En otros casos, se puede lograr que el texto simple tenga una distribución de frecuencia casi plana, y entonces el criptoanalista necesitará textos simples mucho más largos.
Una variante que alguna vez fue común del cifrado de sustitución es el nomenclador . Este cifrado , que recibe su nombre del funcionario público que anunciaba los títulos de los dignatarios visitantes, 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 generalmente convertían 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 abarcó muchas palabras comunes y nombres de lugares. Los símbolos para palabras completas ( palabras de código en el lenguaje moderno) y letras ( cifrado en el lenguaje moderno) no se distinguían en el texto cifrado. El Gran Cifrado de Rossignols utilizado por Luis XIV de Francia fue uno de ellos.
Los nomencladores fueron el material habitual en la correspondencia diplomática , el espionaje y las conspiraciones políticas avanzadas desde principios del siglo XV hasta finales del siglo XVIII; la mayoría de los conspiradores eran y siguen siendo menos sofisticados criptográficamente. Aunque los criptoanalistas de inteligencia del gobierno estaban descifrando sistemáticamente los nomencladores a mediados del siglo XVI, y se disponía de sistemas superiores desde 1467, la respuesta habitual al criptoanálisis era simplemente hacer las tablas más grandes. A finales del siglo XVIII, cuando el sistema estaba empezando a desaparecer, algunos nomencladores tenían 50.000 símbolos. [ cita requerida ]
Sin embargo, no todos los nomencladores estaban rotos; hoy en día, el criptoanálisis de textos cifrados archivados sigue siendo un área fructífera de investigación histórica .
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 de texto simple mediante homofonía . En estos cifrados, las letras de texto simple se asignan a más de un símbolo de texto cifrado. Por lo general, los símbolos de texto simple 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.
Como se requieren más de 26 caracteres en el alfabeto de texto cifrado, se emplean varias soluciones para inventar alfabetos más grandes. Quizás la más simple es usar un "alfabeto" de sustitución numérica. Otro método consiste en variaciones simples del alfabeto existente: mayúsculas, minúsculas, al revés, etc. De manera más artística, aunque no necesariamente más segura, algunos cifrados homofónicos emplearon alfabetos completamente inventados de símbolos extravagantes.
El cifrado de libro es un tipo de cifrado homofónico, un ejemplo de los cuales son los cifrados de Beale . Se trata de una historia de un tesoro enterrado que se describió entre 1819 y 1821 mediante el uso de un texto cifrado que estaba vinculado a 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 simple 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 [2] [3] describió otro cifrado homofónico que fue uno de los primeros [ cita requerida ] intentos de proporcionar seguridad informática a los sistemas de datos de las computadoras mediante el cifrado. Stahl construyó el cifrado de tal manera que el número de homófonos para un carácter dado fuera proporcional a la frecuencia del carácter, lo que dificultaba mucho el análisis de frecuencias.
Francesco I Gonzaga , duque de Mantua , utilizó el ejemplo más antiguo conocido de un cifrado de sustitución homofónica en 1401 para la correspondencia con un tal Simone de Crema. [4] [5]
María, reina de Escocia , mientras estuvo prisionera de Isabel I, durante los años de 1578 a 1584 utilizó cifras homofónicas con encriptación adicional usando un nomenclador para prefijos, sufijos y nombres propios frecuentes mientras se comunicaba con sus aliados, incluido Michel de Castelnau . [6]
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 de la sustitución y transposición de cifras, así como la primera descripción de una cifra polialfabética, en la que a cada letra de texto simple se le asigna más de un sustituto. [7] Las cifras de sustitución polialfabética fueron descritas 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 usa alfabetos mixtos fue descrita en 1563 por Giovanni Battista della Porta en su libro, De Furtivis Literarum Notis ( latín para "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 gran tabla , tradicionalmente llamada tableau . La tabla suele tener un tamaño de 26×26, de modo que se dispone de 26 alfabetos de texto cifrado completos. El método de llenado de la tabla y de elección del alfabeto que se utilizará a continuación define el cifrado polialfabético en 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 planos suficientemente grandes.
Una de las más populares fue la de Blaise de Vigenère . Publicada por primera vez en 1585, se consideró indescifrable hasta 1863 y, de hecho, se la denominaba comúnmente le chiffre indéchiffrable ( en francés , "cifra indescifrable").
En el cifrado Vigenère , la primera fila del cuadro se rellena con una copia del alfabeto de texto simple y las filas sucesivas se desplazan simplemente un lugar hacia la izquierda. (Un cuadro tan simple se denomina tabula recta y matemáticamente corresponde a la suma del texto simple y las letras clave, módulo 26). A continuación, se utiliza una palabra clave para elegir qué alfabeto de texto cifrado utilizar. Cada letra de la palabra clave se utiliza por turno y, a continuación, se repiten de nuevo desde el principio. Por tanto, si la palabra clave es "CAT", la primera letra del texto simple se cifra bajo el alfabeto "C", la segunda bajo "A", la tercera bajo "T", la cuarta bajo "C" de nuevo, y así sucesivamente, o si la palabra clave es "RISE", la primera letra del texto simple se cifra bajo el alfabeto "R", la segunda bajo "I", la tercera bajo "S", la cuarta bajo "E", y así sucesivamente. En la práctica, las claves Vigenère eran a menudo frases de varias palabras de longitud.
En 1863, Friedrich Kasiski publicó un método (probablemente descubierto en secreto e independientemente antes de la guerra de Crimea por Charles Babbage ) que permitía calcular la longitud de la palabra clave en un mensaje cifrado con el sistema Vigenère. Una vez hecho esto, las letras del texto cifrado que habían sido cifradas con el mismo alfabeto podían seleccionarse y analizarse 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 simplificadas por el hecho de que normalmente se había empleado una tabula recta .
Por ello, 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 la tabla, 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. [8] Estos requisitos rara vez se comprenden en la práctica, por lo que la seguridad de los mensajes cifrados con Vigenère suele ser menor de lo que podría haber sido.
Otros polialfabéticos notables incluyen:
Los cifrados de flujo modernos también pueden verse, desde una perspectiva suficientemente abstracta, como una forma de cifrado polialfabético en el que se ha puesto todo el esfuerzo en hacer que el flujo de claves sea lo más largo e impredecible posible.
En un cifrado de sustitución poligráfica, las letras del texto simple 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, "OS" es mucho más común que "RÑ" en español). En segundo lugar, el mayor número de símbolos requiere una mayor cantidad de texto cifrado para analizar de forma productiva las frecuencias de las letras.
Para sustituir pares de letras se necesitaría un alfabeto de sustitución de 676 símbolos ( ). En el mismo De Furtivis Literarum Notis mencionado anteriormente, della Porta propuso un sistema de este tipo, con un cuadro de 20 x 20 (para las 20 letras del alfabeto italiano/latino que estaba utilizando) lleno de 400 glifos únicos . Sin embargo, el sistema era poco práctico y probablemente nunca se utilizó.
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 (se combinan dos letras, generalmente I y J). 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 del cifrado 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 .
En 1901 , Felix Delastelle introdujo otras poligrafías prácticas , entre ellas las cifras bífida y de cuatro cuadrados (ambas digráficas) y la cifra trífida (probablemente la primera trigráfica práctica).
El cifrado 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 base 26 : A = 0, B = 1, y así sucesivamente. (En una variación, se agregan 3 símbolos adicionales para hacer que la base sea prima ). Un bloque de n letras se considera entonces como un vector de n dimensiones y se multiplica por una matriz xn , módulo 26. Los componentes de la matriz son la clave y deben ser aleatorios siempre que la matriz sea invertible en (para garantizar que sea posible el descifrado). Una versión mecánica del cifrado Hill de dimensión 6 fue patentada en 1929. [9]
El cifrado Hill es vulnerable a un ataque de texto plano 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 y cada vez más amplios como un cifrado Hill, con pasos de sustitución no lineales, en última instancia conduce a una red de sustitución-permutación (por ejemplo, un cifrado Feistel ), por lo que es posible, desde esta perspectiva extrema, considerar los cifrados de bloques modernos como un tipo de sustitución poligráfica.
Entre la Primera Guerra Mundial y la amplia disponibilidad de las 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 los individuos no fue antes de 1975), las implementaciones mecánicas de cifrados de sustitución polialfabética fueron ampliamente utilizadas. Varios inventores tuvieron ideas similares aproximadamente al mismo tiempo, y las máquinas de cifrado de rotor fueron patentadas 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 utilizaron máquinas de rotor (por ejemplo, SIGABA y Typex ).
Todas estas máquinas eran similares en el sentido de que la letra sustituida se elegía eléctricamente de entre la enorme 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 simple cifrada, la cantidad de alfabetos utilizados era astronómica. Las primeras versiones de estas máquinas, sin embargo, eran descifrables. William F. Friedman , del SIS del ejército de los EE. UU. , encontró 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 "tablero de conexiones") mucho antes de que comenzara la Segunda Guerra Mundial . El tráfico protegido por esencialmente todas las máquinas Enigma militares alemanas fue descifrado por criptoanalistas aliados, sobre todo los de Bletchley Park , 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 visión matemática inspirada de Marian Rejewski en Polonia .
Hasta donde se sabe públicamente, ningún mensaje protegido por las máquinas SIGABA y Typex fue violado durante o cerca del momento en que estos sistemas estuvieron en servicio.
Un tipo de cifrado de sustitución, el block de un solo uso , es único. Fue inventado cerca del final de la Primera Guerra Mundial por Gilbert Vernam y Joseph Mauborgne en los EE. UU. Claude Shannon demostró matemáticamente que era indescifrable , 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 block de un solo uso puede llamarse cifrado de sustitución solo desde una perspectiva inusual; por lo general, la letra del texto simple se combina (no se sustituye) de alguna manera (por ejemplo, XOR ) con el carácter material clave en esa posición.
En la mayoría de los casos, el block de un solo uso es poco práctico, ya que requiere que el material de la clave sea tan largo como el texto simple, en realidad aleatorio , utilizado una sola vez y mantenido completamente secreto para todos excepto para el remitente y el destinatario previsto. Cuando se violan estas condiciones, incluso marginalmente, el block de un solo uso ya no es indescifrable. Los mensajes con block de un solo uso soviéticos enviados desde los EE. UU. durante un breve período durante la Segunda Guerra Mundial usaban material de clave no aleatorio . Los criptoanalistas estadounidenses, a partir de fines de los años 40, pudieron descifrar, total o parcialmente, unos pocos miles de mensajes de varios cientos de miles. (Véase el proyecto Venona )
En una implementación mecánica, muy similar al equipo Rockex , el bloc de un solo uso se utilizó para los mensajes enviados a través de la línea directa Moscú - Washington establecida después de la Crisis de los Misiles de Cuba .
Los cifrados por sustitución que se han analizado anteriormente, especialmente los antiguos cifrados a mano con lápiz y papel, ya no se utilizan seriamente. Sin embargo, el concepto criptográfico de sustitución sigue vigente hoy en día. Desde una perspectiva abstracta, los cifrados de bloques orientados a bits modernos (por ejemplo, DES o AES ) pueden considerarse cifrados por sustitución en un gran alfabeto binario . Además, los cifrados de bloques suelen incluir tablas de sustitución más pequeñas llamadas S-boxes . Véase también red de sustitución-permutación .
