En criptografía , un cifrado de sustitución es un método de cifrado en el que unidades de texto sin formato se reemplazan con el texto cifrado , de manera definida, con la ayuda de una clave; las "unidades" pueden ser letras individuales (las más comunes), pares de letras, tríos 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 de sustitución se pueden comparar con los cifrados de transposición . En un cifrado de transposición, las unidades del texto claro se reorganizan en un orden diferente y normalmente bastante complejo, pero las unidades mismas no se modifican. Por el contrario, en un cifrado por sustitución, las unidades del texto claro 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 con grupos más grandes de letras se denomina poligráfico . Un cifrado monoalfabético utiliza 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.
La primera descripción publicada sobre cómo descifrar cifrados de sustitución simples la dio Al-Kindi en Un manuscrito sobre el descifrado de mensajes criptográficos, escrito alrededor del año 850 d.C. El método que describió se conoce ahora 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 puede desplazarse 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 una vez. ¡Estamos descubiertos!
cifrados para
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, se proporciona un "recuento de grupos" (es decir, el número de grupos) como verificación adicional. Se suelen utilizar 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 caracteres que se descifran en tonterías obvias, de modo que el receptor pueda detectarlos y descartarlos fácilmente.
El alfabeto de texto cifrado a veces es diferente del alfabeto de texto plano; por ejemplo, en el cifrado pigpen , el texto cifrado consta de un conjunto de símbolos derivados de una cuadrícula. Por ejemplo:
Sin embargo, estas características suponen poca diferencia en la seguridad de un esquema; como mínimo, cualquier conjunto de símbolos extraños se puede volver a transcribir a un alfabeto AZ y tratar con normalidad.
En listas y catálogos para vendedores, a veces se utiliza un cifrado muy sencillo para sustituir dígitos numéricos por letras.
Ejemplo: MAT se usaría para representar 120.
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 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 seguro 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 pueden completarse tentativamente, expandiendo progresivamente la solución (parcial) (consulte el análisis de frecuencia para una demostración de esto). En algunos casos, las palabras subyacentes también pueden determinarse a partir del patrón de sus letras; por ejemplo, atracción , hueso y las palabras con esos dos como raíz son las únicas palabras comunes en inglés con el patrón ABBCADB . Mucha gente resuelve estos cifrados por diversión, como ocurre con los acertijos de criptogramas en los periódicos.
Según la distancia de unicidad del inglés , se requieren 27,6 letras de texto cifrado para descifrar una sustitución simple de un alfabeto mixto. En la práctica, normalmente se necesitan unas 50 letras, aunque algunos mensajes se pueden dividir con menos si se encuentran patrones inusuales. En otros casos, se puede lograr que el texto sin formato tenga una distribución de frecuencia casi plana, por lo que el criptoanalista necesitará textos sin formato mucho más largos.
Una variante que alguna vez fue común del cifrado de sustitución es el nomenclador . Este cifrado, que lleva el nombre del funcionario público que anunció los títulos de los dignatarios visitantes, utiliza una pequeña hoja de códigos que contiene tablas de sustitución de letras, sílabas y palabras, a veces homofónicas, que normalmente convertían 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, cubrió también muchas palabras comunes y nombres de lugares. Los símbolos de palabras completas ( palabras en clave en el lenguaje moderno) y letras ( cifrado en el lenguaje moderno) no se distinguían en el texto cifrado. Uno de ellos fue el Gran Cifrado de Rossignol utilizado por Luis XIV de Francia .
Los nomencladores fueron el estándar 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 siguen siendo menos sofisticados criptográficamente. Aunque los criptoanalistas de inteligencia del gobierno rompían sistemáticamente los nomencladores a mediados del siglo XVI, y desde 1467 se disponía de sistemas superiores, la respuesta habitual al criptoanálisis fue simplemente agrandar las tablas. A finales del siglo XVIII, cuando el sistema comenzaba a desaparecer, algunos nomencladores tenían 50.000 símbolos. [ cita necesaria ]
Sin embargo, no todas las nomencladoras se rompieron; 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 a los cifrados de sustitución fue disfrazar las frecuencias de las letras del texto plano 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 plano 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 necesitarán 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 sencilla sea utilizar 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 empleaban alfabetos totalmente inventados de símbolos fantásticos.
El cifrado de libro es un tipo de cifrado homofónico, siendo un ejemplo los cifrados de Beale . Esta es la historia de un tesoro enterrado que se describió en 1819-1821 mediante el uso de un texto cifrado basado en la Declaración de Independencia. Aquí cada carácter de texto cifrado estaba representado por un número. El número se determinó tomando el carácter de texto plano 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 de 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 de 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 sencillo como buscar la Xª palabra de la Declaración de Independencia y utilizar la primera letra de esa palabra como carácter descifrado.
Stahl [2] [3] describió otro cifrado homofónico y fue uno de los primeros [ cita necesaria ] intentos de proporcionar seguridad informática de los sistemas de datos en las computadoras mediante cifrado. Stahl construyó el cifrado de tal manera que el número de homófonos de un carácter determinado fuera proporcional a la frecuencia del carácter, lo que dificultaba mucho el análisis de frecuencia.
Francesco I Gonzaga , duque de Mantua , utilizó el ejemplo más antiguo conocido de cifrado de sustitución homofónica en 1401 para la correspondencia con una tal Simone de Crema. [4] [5]
María, reina de Escocia , mientras estuvo encarcelada por Isabel I, durante los años de 1578 a 1584 utilizó cifrados homofónicos con cifrado adicional utilizando 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 sobre la sustitución y transposición de cifras, así como la primera descripción de un sistema polialfabético. cifrado, en el que a cada letra de texto plano se le asigna más de un sustituto. [7] Los cifrados de sustitución polialfabética fueron descritos más tarde en 1467 por Leone Battista Alberti en forma de discos. Johannes Trithemius , en su libro Steganographia ( en griego antiguo , "escritura oculta") introdujo la forma ahora más estándar de un cuadro (ver más abajo; ca. 1500, pero no se publicó hasta mucho más tarde). 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 los caracteres ocultos en la escritura").
En un cifrado polialfabético, se utilizan varios alfabetos de cifrado. Para facilitar el cifrado, todos los alfabetos suelen escribirse en una gran tabla , tradicionalmente llamada tableau . El cuadro suele ser de 26 × 26, por lo que hay disponibles 26 alfabetos de texto cifrado completos. El método para completar el cuadro y 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 claros suficientemente grandes.
Uno de los más populares fue el de Blaise de Vigenère . Publicado por primera vez en 1585, se consideró irrompible hasta 1863 y, de hecho, comúnmente se le llamaba le chiffre indéchiffrable ( en francés , "cifrado indescifrable").
En el cifrado Vigenère , la primera fila del cuadro se completa con una copia del alfabeto en texto plano, y las filas sucesivas simplemente se desplazan un lugar hacia 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 utiliza por turno 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 la 'A', la tercera con la 'T', la cuarta nuevamente con la 'C', 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 antes de la Guerra de Crimea por Charles Babbage ) 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 cifradas bajo el mismo alfabeto podían seleccionarse y atacarse por separado como una serie de sustituciones simples semiindependientes, lo que se complicaba 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 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. [8] Estos requisitos rara vez se comprenden 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:
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 invertido 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 de texto plano se sustituyen en grupos más grandes, en lugar de sustituir letras individualmente. La primera ventaja es que la distribución de frecuencia es mucho más plana que la de las letras individuales (aunque en realidad no es plana en idiomas reales; por ejemplo, 'TH' es mucho más común que 'XQ' en inglés). En segundo lugar, la mayor cantidad de símbolos requiere, en consecuencia, más texto cifrado para analizar productivamente las frecuencias de las letras.
Para sustituir pares de letras se necesitaría un alfabeto de sustitución de 676 símbolos de longitud ( ). En el mismo De Furtivis Literarum Notis mencionado anteriormente, della Porta propuso tal sistema, con un cuadro de 20 x 20 (para las 20 letras del alfabeto italiano/latino que estaba usando) lleno de 400 glifos únicos . Sin embargo, el sistema no era 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 (dos letras, generalmente I y J, están combinados). 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 sobre cifrado de Playfair para ver un diagrama). Las reglas especiales manejan letras dobles y pares que se encuentran en la misma fila o columna. Playfair tuvo uso militar desde la Guerra de los Bóers hasta la Segunda Guerra Mundial .
Felix Delastelle introdujo varios otros poligráficos prácticos en 1901 , incluidos los cifrados bífidos y de cuatro cuadrados (ambos digráficos) y el cifrado trífido (probablemente el primer trigráfico práctico).
El cifrado Hill , inventado en 1929 por Lester S. Hill , es una sustitución poligráfica que puede combinar grupos de letras mucho más grandes simultáneamente utilizando álgebra lineal . Cada letra se trata como un dígito en base 26 : A = 0, B = 1, etc. (En una variación, se agregan 3 símbolos adicionales para hacer que la base sea prima ). Luego, un bloque de n letras se considera 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 debe ser aleatorio siempre que la matriz sea invertible (para garantizar que sea posible el descifrado). En 1929 se patentó una versión mecánica del cifrado Hill de dimensión 6. [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 de difusión lineales débiles cada vez más amplios, como un cifrado de Hill, con pasos de sustitución no lineales, conduce en última instancia a una red de sustitución-permutación (por ejemplo, un cifrado de 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 disponibilidad generalizada de computadoras (para algunos gobiernos esto fue aproximadamente en las décadas de 1950 o 1960; para otras organizaciones fue una década o más después; para individuos no fue antes de 1975), las implementaciones mecánicas de cifrados de sustitución polialfabética fueron ampliamente utilizados. Varios inventores tuvieron ideas similares casi 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 aproximadamente a partir de 1930. Los aliados también desarrollaron y máquinas de rotor usadas (por ejemplo, SIGABA y Typex ).
Todos ellos eran similares en 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 discos giraban mecánicamente con cada letra de texto sin formato cifrada, el número de alfabetos utilizados era astronómico. Sin embargo, las primeras versiones de estas máquinas eran frágiles. William F. Friedman, del SIS del ejército estadounidense, encontró tempranamente 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 conexión") mucho antes de que comenzara la Segunda Guerra Mundial . El tráfico protegido por prácticamente todos los Enigmas militares alemanes fue interrumpido por los criptoanalistas aliados, en particular 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 rota por la inspiración matemática de Marian Rejewski en Polonia .
Hasta donde es de conocimiento público, ningún mensaje protegido por las máquinas SIGABA y Typex fue interrumpido durante o cerca del tiempo en que estos sistemas estaban en servicio.
Un tipo de cifrado de sustitución, el bloc de un solo uso , es único. Fue inventado cerca del final de la Primera Guerra Mundial por Gilbert Vernam y Joseph Mauborgne en Estados Unidos. Claude Shannon demostró matemáticamente que era irrompible , probablemente durante la Segunda Guerra Mundial ; su trabajo se publicó por primera vez a finales de la década de 1940. En su implementación más común, el bloc de un solo uso puede denominarse cifrado de sustitución sólo desde una perspectiva inusual; normalmente, la letra de texto plano se combina (no se sustituye) de alguna manera (por ejemplo, XOR ) con el carácter clave del material en esa posición.
El bloc de un solo uso, en la mayoría de los casos, no es práctico ya que requiere que el material clave sea tan largo como el texto sin formato, en realidad aleatorio , usado una y sólo una vez, y mantenido completamente en secreto para todos, excepto para el remitente y el receptor previsto. Cuando se violan estas condiciones, aunque sea marginalmente, la libreta de un solo uso ya no es irrompible. Los mensajes soviéticos de un solo uso enviados desde los EE. UU. durante un breve período durante la Segunda Guerra Mundial utilizaron material de claves no aleatorias . Los criptoanalistas estadounidenses, desde finales de los años 40, pudieron descifrar, total o parcialmente, unos pocos miles de mensajes entre varios cientos de miles. (Ver proyecto Venona )
En una implementación mecánica, 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 en Cuba .
Los cifrados de sustitución, como se analizó anteriormente, especialmente los cifrados manuales más antiguos de lápiz y papel, ya no se utilizan seriamente. Sin embargo, el concepto criptográfico de sustitución continúa aún hoy. Desde una perspectiva abstracta, los cifrados de bloques modernos orientados a bits (por ejemplo, DES o AES ) pueden verse como cifrados de sustitución en un gran alfabeto binario . Además, los cifrados en bloque suelen incluir tablas de sustitución más pequeñas llamadas S-boxes . Véase también red de sustitución-permutación .
