Un cifrado de sustitución es un método de cifrado en el que los elementos del texto sin formato original se reemplazan con texto cifrado de acuerdo con alguna regla. Los elementos de texto pueden ser caracteres simples (el caso más común), pares de letras, triples de letras, una combinación de estos casos, etc. En la criptografía clásica , hay cuatro tipos de cifrado de sustitución [1] :
Como alternativa a los cifrados de sustitución, se pueden considerar los cifrados de permutación . En ellos, los elementos del texto se reorganizan en un orden diferente al original, y los elementos mismos permanecen sin cambios. Por el contrario, en los cifrados por sustitución, los elementos del texto no cambian de secuencia, sino que se cambian a sí mismos.
El uso de cifrados de sustitución tiene su origen en Mesopotamia . Para ocultar información sobre la receta para la producción de esmalte para cerámica, el autor reemplazó algunas de las palabras con números y signos cuneiformes . El emperador romano Cayo Julio César , cuando escribía mensajes secretos, desplazaba cada letra del alfabeto en 3 posiciones. Este tipo de cifrado de sustitución recibió su nombre más tarde, el cifrado César . Otro cifrado no menos famoso de la antigüedad , Atbash , se utilizó en la Biblia para crear mensajes ocultos. Cada letra de la palabra fue reemplazada por su imagen especular en el alfabeto [2] [3] .
Se considera que uno de los primeros dispositivos de cifrado es la regla de Eneas , cuando se usaba un hilo largo que se pasaba a través de una ranura y luego a través de agujeros hechos en la regla. Las letras correspondientes a ellos se ubicaron junto a los agujeros. Se ató un nudo en el hilo en el lugar donde pasó por el agujero. Así, el texto del mensaje fue reemplazado por una secuencia de distancias entre los nudos. Este dispositivo fue inventado por el antiguo comandante griego Eneas Tacticus en el siglo IV a. mi. [4] [5]
Con el uso del análisis de frecuencia para descifrar los cifrados monoalfabéticos en el siglo IX , se hizo necesario cambiar la frecuencia de aparición de los caracteres en el texto sin formato. Para este propósito, se comenzó a utilizar un cifrado de sustitución monosónico , cuya esencia era la comparación de varios caracteres de reemplazo con una letra en proporción a la frecuencia de aparición de esta letra en varios textos. El secretario del antipapa Clementius VII, Gabriel de Lavinda, en el siglo XV , fue el primero en utilizar homófonos para garantizar aproximadamente la misma frecuencia de vocales. Después de 65 años, Leon Battista Alberti describe en detalle el cifrado de sustitución de un solo sonido en su libro Tratado sobre cifrados . El principal problema con la difusión de la sustitución homofónica fue la necesidad de utilizar un alfabeto ampliado para cifrar los mensajes. [6] [7] [8] [9]
Esta deficiencia fue eliminada por las cifras polialfabéticas , la primera de las cuales fue descrita por el monje alemán Johann Trithemius . De acuerdo con el método descrito en su tratado "Impresión", la letra siguiente se reemplazaba por un carácter de su propio alfabeto cifrado, mientras que cada alfabeto siguiente se obtenía del anterior cambiando una letra. El cifrado polialfabético descrito por Blaise de Vigenère en 1585 ganó particular popularidad . Se usó una palabra arbitraria como clave para el cifrado. El conjunto de alfabetos cifrados correspondientes a una palabra determinada se determinó a partir de la tabla de Vigenère. [diez]
En 1854, el físico inglés Charles Wheatstone publicó un cifrado de poligrama , que más tarde recibió el nombre de Lord Lyon Playfair. Este cifrado reemplaza pares de letras (bigramas) con caracteres individuales, lo que aumenta significativamente su resistencia criptográfica al análisis de frecuencia. [once]
Con la llegada de las computadoras , los cifrados polialfabéticos y de poligramas pasaron a un segundo plano y fueron reemplazados por cifrados de bloque nuevos y más seguros . [12]
En los cifrados de sustitución simple , la sustitución se realiza en un solo carácter. Para una demostración visual de un cifrado de sustitución simple, basta con escribir el mismo alfabeto bajo un alfabeto dado, pero en un orden diferente o, por ejemplo, con un desplazamiento. El alfabeto escrito de esta manera se llama alfabeto de sustitución.
Un cifrado de sustitución simple utilizado para el alfabeto hebreo y del cual toma su nombre. El cifrado se produce reemplazando la primera letra del alfabeto con la última, la segunda con la penúltima ( alef (primera letra) se reemplaza por tav (última), bet (segunda) se reemplaza por shin (penúltima); de estas combinaciones el cifrado obtuvo su nombre). [13] Cifrado Atbash para el alfabeto inglés:
Alfabeto fuente: | ABCDEFGHIJKLMNOPQRSTU VWXYZ |
Alfabeto de reemplazo: | ZYXWVUTSRQPONMLKJIHGF EDCBA |
El cifrado César es uno de los cifrados más antiguos. Durante el cifrado, cada letra se reemplaza por otra, que está separada de ella en el alfabeto por un número fijo de posiciones. El cifrado lleva el nombre del emperador romano Gaius Julius Caesar , quien lo usó para la correspondencia secreta. Un desarrollo natural del cifrado César fue el cifrado Vigenère . Cifrado usando una clave :
Alfabeto fuente: | ABCDEFGHIJKLMNOPQRSTU VWXYZ |
Alfabeto de reemplazo: | EFGHIJKLMNOPQRSTUVWXY ZABCD |
Un ejemplo moderno de un cifrado César es ROT13 . Cambia cada carácter del alfabeto inglés en 13 posiciones. Se utiliza en foros de Internet como un medio para ocultar spoilers , puntos principales, soluciones de acertijos y material ofensivo de la vista casual. [catorce]
Cifrar utilizando una palabra claveUn cifrado que utiliza una palabra clave es uno de los más fáciles de implementar y descifrar. La idea es que se elija una palabra clave , que se escribe al frente, luego se escribe el resto de las letras del abecedario en su orden. Cifrar utilizando la palabra clave WORD.
Alfabeto fuente: | ABCDEFGHIJKLMNOPQRSTU VWXYZ |
Alfabeto de reemplazo: | PALABRABCEFGHIJKLMNPQST UVXYZ |
Como podemos ver, cuando usamos una palabra de código corta, obtenemos un reemplazo muy, muy simple. Podemos usar una palabra con letras repetidas como palabra clave, pero solo si eliminamos las letras adicionales de la palabra clave, de lo contrario, esto generará ambigüedad en el descifrado, es decir, la misma letra del texto cifrado corresponderá a dos letras diferentes de el alfabeto original. [quince]
Por tradición, el texto cifrado se escribe en bloques (otro nombre para "grupos") de 5 caracteres, sin tener en cuenta la puntuación y los espacios. Esto ayuda a evitar errores al transmitir un mensaje encriptado y le permite ocultar los límites de las palabras en el texto original. El bloque contiene 6 caracteres, ya que solía ser conveniente enviarlos por telégrafo .
La principal desventaja de este método de cifrado es que las últimas letras del alfabeto (que tienen coeficientes de análisis de baja frecuencia ) tienden a quedarse al final. Una forma más segura de construir un alfabeto de reemplazo es hacer un movimiento de columna (movimiento de columna) en el alfabeto usando una palabra clave, pero esto no se hace con frecuencia.
Aunque el número de claves posibles es muy grande (26! = 288,4 ), este tipo de cifrado se puede descifrar fácilmente. Siempre que el mensaje tenga la longitud suficiente (ver más abajo), el criptoanalista puede adivinar el significado de algunas de las letras más comunes basándose en un análisis de la distribución de frecuencia de los caracteres en el texto cifrado. Esto le permite formar palabras separadas que pueden usarse de antemano para obtener una solución más completa más tarde (ver análisis de frecuencia). Según la distancia de unicidad del idioma inglés, 27,6 letras del texto cifrado deberían ser suficientes para romper el cifrado de sustitución simple. En la práctica, unos 50 caracteres suelen ser suficientes para descifrar, aunque algunos textos cifrados se pueden descifrar con menos caracteres si se encuentran estructuras no estándar. Pero con una distribución uniforme de caracteres en el texto, es posible que se requieran textos cifrados mucho más largos para descifrar.
Uno de los primeros intentos de aumentar la complejidad del análisis de frecuencia de los textos cifrados fue enmascarar las frecuencias reales de los caracteres del texto sin formato utilizando la homofonía. En estos cifrados, las letras del alfabeto original corresponden a más de un carácter del alfabeto de reemplazo. Por lo general, los caracteres del texto fuente de mayor frecuencia reciben más equivalentes que los caracteres más raros. Así, la distribución de frecuencias se vuelve más uniforme, lo que complica enormemente el análisis de frecuencias [17] .
Dado que el alfabeto de reemplazo requería más de 26 caracteres, se necesitaban alfabetos extendidos. Una de las soluciones más simples es reemplazar el alfabeto con números . Otro método consiste en modificaciones simples a un alfabeto existente: letras mayúsculas , letras minúsculas , caracteres invertidos , etc. Más artísticos, aunque no necesariamente más confiables, serían los cifrados homofónicos que usan alfabetos completamente inventados (ficticios) (como el cifrado en un libro "Gold Bug" de E. Poe, o " The Voynich Manuscript ". Sin embargo, estos cifrados no son ejemplos de sustitución homofónica).
Un cifrado emitido por un funcionario medieval, que es un pequeño libro con grandes tablas de sustitución homofónicas. El cifrado se limitó originalmente a los nombres de personas importantes de la época, por lo que siguió el nombre del cifrado; en ediciones posteriores, este cifrado se complementó con una gran cantidad de palabras comunes y nombres de lugares. Sobre la base de este "nomenclador", se compiló el Gran Cifrado de Rossignol, utilizado por el rey Luis XIV de Francia . De hecho, después de que este cifrado dejó de usarse, los archivos franceses estuvieron cerrados durante varios cientos de años.
Los "nomencladores" fueron el estándar para la correspondencia diplomática, los mensajes de espionaje y fueron el principal medio de conspiración antipolítica desde principios del siglo XV hasta finales del siglo XVIII. Aunque los criptoanalistas del gobierno estaban descifrando sistemáticamente los "nomencladores" a mediados del siglo XVI. La salida habitual a esta situación era aumentar el volumen de mesas. Pero a finales del siglo XVIII, cuando el sistema empezó a caer en desuso, algunos "nomencladores" tenían hasta 50.000 caracteres. Sin embargo, no se rompieron todos los "nomencladores".
Gran Cifrado de RossignolAntoine Rossignol y su hijo Bonaventure Rossignol inventaron el Gran Cifrado , que utilizaba 587 números diferentes. [18] El cifrado era tan fuerte que durante muchos siglos nadie pudo descifrarlo, hasta que lo hizo el oficial del ejército francés, el criptógrafo Etienne Bazery en 1893, usando el ejemplo de una carta del Ministro de Guerra Louvois al Rey Luis XIV . . Se dio cuenta de que cada número codificaba no una letra, sino una sílaba completa . Baseri supuso que la secuencia 124-22-125-46-345 codificaba la palabra "les ennemis" (enemigos) y, a partir de esta información, pudo descifrar todo el texto.
Cifrado del libroUn cifrado de libro es un cifrado en el que la clave es un libro o un pequeño fragmento de texto . El principal requisito será que ambos corresponsales no sólo tengan el mismo libro, sino también la misma edición y número. Tradicionalmente, los cifrados de libros funcionan reemplazando palabras en el texto original con la ubicación de las mismas palabras en el libro. Esto funcionará hasta que se encuentre una palabra que no esté en el libro, momento en el cual el mensaje no podrá codificarse. [19] Un enfoque alternativo que evita este problema es reemplazar caracteres individuales en lugar de palabras. Sin embargo, este método tiene un efecto secundario: el texto cifrado se vuelve muy grande (generalmente se usan de 4 a 6 dígitos para cifrar cada carácter o sílaba).
Una continuación adicional de los cifrados de sustitución simple son los cifrados polialfabéticos. Abu Al-Kindi en sus trabajos demostró que los cifrados monoalfabéticos ordinarios son bastante fáciles de criptoanálisis de frecuencia y fue el primero en proponer el uso de cifrados polialfabéticos. En Europa, tales cifrados fueron descritos por primera vez en 1467 por el arquitecto italiano Leon Battista Alberti . En el siglo XVI, el abad alemán Johann Trithemius , en su libro Taquigrafía, presentó un esquema de cifrado polialfabético en forma de tabla. Una versión más compleja que utiliza alfabetos mixtos fue descrita en 1563 por Giambattista della Porta en su libro De Furtivis Literarum Notis (en latín: "Sobre el significado oculto de las letras individuales"). La esencia de los cifrados polialfabéticos radica en la aplicación repetida de varios cifrados de sustitución simple a un cierto número de letras del texto cifrado. Es decir, uno de los cifrados de sustitución simple se aplica a cada letra individualmente.
El cifrado Vigenère consiste en una secuencia de varios cifrados César con diferentes valores de desplazamiento. Para el cifrado, se puede utilizar una tabla de alfabetos llamada tabula recta o cuadrado (tabla) de Vigenère. Con respecto al alfabeto latino, la tabla Vigenère se compone de líneas de 26 caracteres cada una, con cada línea siguiente desplazada varias posiciones. Por lo tanto, hay 26 cifrados César diferentes en la tabla. En diferentes etapas de codificación, el cifrado Vigenère usa diferentes alfabetos de esta tabla. Cada etapa del cifrado utiliza diferentes alfabetos, seleccionados según el carácter de la palabra clave. [20] Por ejemplo, si la palabra clave es 'CAT', la primera letra del texto sin formato se codifica con el alfabeto 'C', la segunda 'A', la tercera 'T', la cuarta nuevamente 'C' y pronto.
Libreta desechableEste tipo de cifrado de sustitución es bastante específico. Fue inventado al final de la Primera Guerra Mundial por Gilbert Vernam . Claude Shannon demostró matemáticamente su fortaleza criptográfica absoluta en su artículo de 1945. Para crear un texto cifrado, el texto sin formato se somete a XOR con una clave (llamada pad de una sola vez o cipherpad). En este caso, el uso de un bloc de notas de un solo uso, en la mayoría de los casos, no es práctico, ya que se requiere que la clave sea del mismo tamaño que el texto sin formato. También requiere que la clave sea completamente aleatoria, se use solo una vez y se mantenga en secreto para todos, excepto para el destinatario y el remitente. En este sentido, el uso comercial del cifrado Vernam no es tan común como los esquemas de clave pública, y se utiliza principalmente para la transmisión de mensajes de particular importancia por parte de las agencias gubernamentales. [21]
En los cifrados de sustitución de poligramas, las letras del texto sin formato se reemplazan no una a la vez, sino en grupos. La primera ventaja de este método es que la distribución de frecuencia de los grupos de letras es mucho más uniforme que la de los caracteres individuales. En segundo lugar, el análisis de frecuencia productivo requiere un tamaño mayor del texto cifrado, ya que el número de diferentes grupos de letras es mucho mayor que solo el alfabeto.
El cifrado de Playfair es una técnica de cifrado simétrico manual que fue pionera en el uso de la sustitución de bigramas . Inventado en 1854 por Charles Wheatstone , pero llamado así por Lord Lyon Playfair, quien introdujo este cifrado en los servicios gubernamentales del Reino Unido. El cifrado proporciona el cifrado de pares de caracteres (bigramas) en lugar de caracteres individuales, como en el cifrado de sustitución y en los sistemas de cifrado Vigenère más complejos. [22] [23] El cifrado de Playfair utiliza una matriz de 5x5 (para el alfabeto latino, para el alfabeto cirílico es necesario aumentar el tamaño de la matriz a 4x8), cuyas celdas se rellenan con un alfabeto mixto (en inglés textos, el carácter "Q" generalmente se omite para reducir el alfabeto, en otras versiones "I" y "J" se combinan en una celda). Luego, el reemplazo se realiza representando los bigramas como dos esquinas de un rectángulo. Las otras dos esquinas del diagrama se utilizan para el cifrado (consulte el artículo principal para obtener más detalles). El cifrado de Playfair fue utilizado tácticamente por el ejército británico en la Segunda Guerra de los Bóers y la Primera Guerra Mundial , y por los australianos y alemanes durante la Segunda Guerra Mundial . La razón para usar el cifrado de Playfair fue que es bastante rápido de usar y no requiere ningún equipo especial.
Cifrado de la colinaEl cifrado de Hill, inventado en 1929 por Lester S. Hill, es un cifrado de poligrama que puede usar grandes grupos usando álgebra lineal . A cada letra se le asigna primero un número. Para el alfabeto latino, a menudo se usa el esquema más simple: A = 0, B = 1, ..., Z = 25. El bloque de n letras se trata como un vector n-dimensional y se multiplica por una matriz de n × n módulo 26. Los componentes de la matriz son la clave y deben ser aleatorios, siempre que la matriz sea invertible para el descifrado. sea posible la operación. [24] El cifrado de Hill es vulnerable a los ataques de texto sin formato porque utiliza operaciones lineales. Por lo tanto, para aumentar la fuerza criptográfica, se le deben agregar algunas operaciones no lineales. La combinación de operaciones lineales, como en el cifrado de Hill, y pasos no lineales condujo a la creación de una red de permutación-permutación (como la red de Feistel ). Por lo tanto, desde cierto punto de vista, los cifrados de bloque modernos pueden considerarse como un tipo de cifrado de poligramas. [25]
El famoso criptógrafo estadounidense Bruce Schneier identifica cuatro métodos principales de criptoanálisis: [26]
Describamos la fuerza criptográfica de los cifrados de sustitución con respecto a estos métodos.
Los cifrados monoalfabéticos se descifran fácilmente utilizando métodos de análisis de frecuencia [ 6] .
El criptoanálisis de los cifrados de sustitución monosónica se lleva a cabo contando las frecuencias de aparición de pares y triples de caracteres [27] .
Para descifrar cifrados polialfabéticos se utiliza el método de Kasiski [28] .
El cifrado del poligrama de Hill se puede descifrar calculando las frecuencias de las secuencias de caracteres [29] .
Dado un texto sin formato de longitud suficiente, romper cifrados monoalfabéticos y monosonidos es trivial [30] .
Para descifrar rápidamente los cifrados polialfabéticos , la longitud del texto sin formato debe exceder la longitud de la clave [31] .
Todos los cifrados de sustitución son vulnerables a los ataques de texto sin formato elegido, excepto el bloc de notas de un solo uso [32] .
El cifrado de Hill estándar , compuesto por n ecuaciones lineales, se puede descifrar en el texto sin formato elegido al interceptar n² pares de mensajes y caracteres de texto cifrado por parte de un criptoanalista. [25]
Uno de los primeros dispositivos de cifrado se inventó en el siglo XV y reemplazó al cifrado César . Su autor fue el arquitecto italiano Leon Battista Alberti , quien realizó una importante contribución al desarrollo de los cifrados por sustitución. Este dispositivo constaba de dos discos de cobre de diferentes tamaños, sujetos con una aguja. Se aplicó un alfabeto a lo largo de los bordes de cada disco. Ambos discos podían girar independientemente el uno del otro, haciendo coincidir así las letras del texto sin formato y el texto cifrado. El disco de Alberti fue ampliamente utilizado durante cinco siglos, incluso durante la Guerra Civil Estadounidense [33] .
A principios del siglo XX, tras la invención de la radio, se hizo necesario desarrollar máquinas de encriptación para uso militar y comercial. Como base para estos dispositivos, se utilizaron cifrados de sustitución polialfabéticos, así como el principio de funcionamiento del disco de cifrado [34] .
Para obtener una señal encriptada, se utilizó un disco hueco con contactos aplicados en ambos lados. El texto obtenido como resultado del cifrado dependía de la conmutación del disco y de su posición angular. Este tipo de dispositivos de cifrado se denominó posteriormente máquinas rotativas [34] [35] .
Las máquinas rotativas fueron utilizadas por varios países durante la Segunda Guerra Mundial . Los más famosos de ellos fueron: el coche americano SIGABA , el alemán ENIGMA , el inglés TYPEX y el japonés PURPLE. [36]
Los sistemas de cifrado rotatorio tenían dos tipos de claves. La soldadura entre los contactos del rotor establece una llave permanente. Para reemplazar las claves permanentes, fue necesario actualizar todas las máquinas de cifrado lanzadas de este modelo, lo que es difícil de implementar en la práctica. Las claves variables a menudo cambiaban todos los días y estaban determinadas por un conjunto de rotores y su posición inicial. [37]
A pesar del desplazamiento de los cifrados de sustitución por cifrados de bloque, los blocs de notas de un solo uso todavía se utilizan a nivel estatal en nuestro tiempo. Se utilizan para proporcionar canales de comunicación de alto secreto. Según los rumores, la línea telefónica entre los jefes de la URSS y los Estados Unidos fue encriptada utilizando un teclado de un solo uso y es muy posible que todavía exista. Los espías de varios estados utilizan blocs de notas desechables para ocultar información especialmente importante. Dichos mensajes no se pueden descifrar en ausencia de una clave escrita en un cuaderno, independientemente de la potencia informática de la computadora. [38] [12]