Cifrado de Vigenère

El cifrado Vigenère se llama después Blaise de Vigenère (pictured), aunque Giovan Battista Bellaso lo había inventado antes de que Vigenère describiera su cifrado de autokey.

Reproducción del disco cifrado de la Confederación utilizado en la Guerra Civil Americana en exhibición en el Museo Nacional Cryptologic

El cifrado Vigenère (Pronunciación en francés: [viʒnɛːʁ]) es un método para cifrar texto alfabético mediante el uso de una serie de cifrados César entrelazados, basados en las letras de una palabra clave. Emplea una forma de sustitución polialfabética.

Descrito por primera vez por Giovan Battista Bellaso en 1553, el cifrado es fácil de entender e implementar, pero resistió todos los intentos de descifrarlo hasta 1863, tres siglos después. Esto le valió la descripción le chiffrage indéchiffrable (en francés, 'el cifrado indescifrable'). Mucha gente ha tratado de implementar esquemas de cifrado que son esencialmente cifrados de Vigenère. En 1863, Friedrich Kasiski fue el primero en publicar un método general para descifrar las cifras de Vigenère.

En el siglo XIX, el esquema se atribuyó erróneamente a Blaise de Vigenère (1523–1596) y adquirió su nombre actual.

Historia

La primera descripción bien documentada de un cifrado polialfabético fue realizada por Leon Battista Alberti alrededor de 1467 y utilizó un disco de cifrado de metal para cambiar entre alfabetos cifrados. El sistema de Alberti solo cambiaba de alfabeto después de varias palabras, y los cambios se indicaban escribiendo la letra del alfabeto correspondiente en el texto cifrado. Más tarde, Johannes Trithemius, en su obra Polygraphiae (que se completó en forma manuscrita en 1508 pero se publicó por primera vez en 1518), inventó la tabula recta, un componente crítico del cifrado Vigenère. El cifrado Trithemius, sin embargo, proporcionó un sistema progresivo, bastante rígido y predecible para cambiar entre alfabetos cifrados.

En 1586, Blaise de Vigenère publicó un tipo de cifrado polialfabético llamado cifrado de clave automática, porque su clave se basa en el texto sin formato original, ante la corte de Enrique III de Francia. Sin embargo, el cifrado que ahora se conoce como el cifrado de Vigenère es el descrito originalmente por Giovan Battista Bellaso en su libro de 1553 La cifra del Sig. Giovan Battista Bellaso. Se basó en la tabula recta de Trithemius, pero agregó una "contraseña" (una tecla) para cambiar los alfabetos cifrados de cada letra. Mientras que Alberti y Trithemius usaban un patrón fijo de sustituciones, el esquema de Bellaso significaba que el patrón de sustituciones podía cambiarse fácilmente, simplemente seleccionando una nueva clave. Las claves eran típicamente palabras sueltas o frases cortas, conocidas por ambas partes de antemano, o transmitidas 'fuera de banda'. junto con el mensaje. Por lo tanto, el método de Bellaso requería una fuerte seguridad solo para la clave. Como es relativamente fácil asegurar una frase clave corta, como una conversación privada previa, el sistema de Bellaso era considerablemente más seguro.

En el siglo XIX, la invención del cifrado de Bellaso se atribuyó erróneamente a Vigenère. David Kahn, en su libro, The Codebreakers lamentó esta atribución errónea, diciendo que la historia había "ignorado esta importante contribución y, en cambio, nombró un cifrado regresivo y elemental para él [Vigenère] aunque no tenía nada que objetar". hacer con eso".

El cifrado Vigenère se ganó la reputación de ser excepcionalmente fuerte. El célebre autor y matemático Charles Lutwidge Dodgson (Lewis Carroll) calificó el cifrado de Vigenère como irrompible en su obra de 1868 "The Alphabet Cipher" en una revista infantil. En 1917, Scientific American describió el cifrado Vigenère como "imposible de traducir". Esa reputación no era merecida. Se sabe que Charles Babbage descifró una variante del cifrado ya en 1854, pero no publicó su trabajo. Kasiski descifró por completo el cifrado y publicó la técnica en el siglo XIX, pero incluso en el siglo XVI, algunos criptoanalistas hábiles ocasionalmente podían descifrar el cifrado.

Regla de diapositivas críptográficas utilizada como ayuda de cálculo por el ejército suizo entre 1914 y 1940.

El cifrado de Vigenère es lo suficientemente simple como para ser un cifrado de campo si se usa junto con discos de cifrado. Los Estados Confederados de América, por ejemplo, utilizaron un disco de cifrado de latón para implementar el cifrado Vigenère durante la Guerra Civil Estadounidense. Los mensajes de la Confederación estaban lejos de ser secretos y la Unión descifraba regularmente sus mensajes. A lo largo de la guerra, el liderazgo confederado se basó principalmente en tres frases clave: "Manchester Bluff", "Victoria completa" y, cuando la guerra llegó a su fin, 'Come Retribution'.

Un cifrado Vigenère con una clave completamente aleatoria (y no reutilizable) siempre que el mensaje se convierta en un bloc de notas de un solo uso, un cifrado teóricamente indescifrable. Gilbert Vernam intentó reparar el cifrado roto (creando el cifrado Vernam-Vigenère en 1918), pero la tecnología que utilizó era tan engorrosa que resultaba impracticable.

Descripción

La mesa Vigenère o Vigenère, también conocida como tabula recta, se puede utilizar para encriptación y desencriptación.

En un cifrado César, cada letra del alfabeto se desplaza a lo largo de cierto número de lugares. Por ejemplo, en un cifrado César de turno 3, a se convertiría en D, b se convertiría en E, y se convertiría en B y así sucesivamente. El cifrado Vigenère tiene varios cifrados César en secuencia con diferentes valores de desplazamiento.

Para cifrar, se puede utilizar una tabla de alfabetos, denominada tabula recta, cuadrado de Vigenère o tabla de Vigenère. Tiene el alfabeto escrito 26 veces en diferentes filas, cada alfabeto desplazado cíclicamente hacia la izquierda con respecto al alfabeto anterior, correspondiente a los 26 cifrados César posibles. En diferentes puntos del proceso de cifrado, el cifrado utiliza un alfabeto diferente de una de las filas. El alfabeto utilizado en cada punto depende de una palabra clave repetitiva.

Por ejemplo, suponga que el texto sin formato que se va a cifrar es

attackatdawn.

La persona que envía el mensaje elige una palabra clave y la repite hasta que coincide con la longitud del texto sin formato, por ejemplo, la palabra clave "LEMON":

LEMONLEMONLE

Cada fila comienza con una letra clave. El resto de la fila contiene las letras de la A a la Z (en orden desplazado). Aunque se muestran 26 filas de teclas, un código usará solo tantas teclas (diferentes alfabetos) como letras únicas haya en la cadena de claves, aquí solo 5 teclas: {L, E, M, O, N}. Para letras sucesivas del mensaje, se tomarán letras sucesivas de la cadena clave y se cifrará cada letra del mensaje utilizando su fila de clave correspondiente. Se elige la siguiente letra de la clave, y esa fila continúa para encontrar el encabezado de columna que coincide con el carácter del mensaje. La letra en la intersección de [key-row, msg-col] es la letra cifrada.

Por ejemplo, la primera letra del texto sin formato, a, se empareja con L, la primera letra de la clave. Por lo tanto, se utilizan la fila A y la columna L del cuadrado de Vigenère, es decir, L. De manera similar, para la segunda letra del texto sin formato, se usa la segunda letra de la clave. La letra en la fila T y la columna E es X. El resto del texto sin formato está cifrado de manera similar:

El descifrado se realiza yendo a la fila de la tabla correspondiente a la clave, buscando la posición de la letra del texto cifrado en esa fila y luego usando la etiqueta de la columna como texto sin formato. Por ejemplo, en la fila L (de LEMON), el texto cifrado L aparece en la columna A , por lo que a es la primera letra del texto sin formato. A continuación, en la fila E (de LEMON), el texto cifrado X se encuentra en la columna T. Por lo tanto, t es la segunda letra del texto sin formato.

Descripción algebraica

Vigenère también se puede describir algebraicamente. Si las cartas A–Z se toman para ser los números 0–25 (A=^ ^ 0{displaystyle A,{widehat {=},0}, B=^ ^ 1{displaystyle B,{widehat {=},1}, etc.), y la adición se realiza modulo 26, encriptación Vigenère E{displaystyle E} usando la llave K{displaystyle K} puede ser escrito como

Ci=EK()Mi)=()Mi+Ki)mod26{displaystyle ¿Qué?

y desciframiento D{displaystyle D} usando la llave K{displaystyle K} como

Mi=DK()Ci)=()Ci− − Ki)mod26,{displaystyle ¿Qué?

en que M=M1...... Mn{displaystyle M=M_{1}dots M_{n} es el mensaje, C=C1...... Cn{displaystyle C=C_{1}dots C_{n} es el cifertexto y K=K1...... Kn{displaystyle K=K_{1}dots K_{n} es la clave obtenida repitiendo la palabra clave ⌈ ⌈ n/m⌉ ⌉ {displaystyle lceil n/mrceil } tiempos en que m{displaystyle m} es la longitud de la palabra clave.

Así, utilizando el ejemplo anterior, para encriptar A=^ ^ 0{displaystyle A,{widehat {=},0} con carta clave L=^ ^ 11{displaystyle L ',{widehat {=},11} el cálculo daría lugar a 11=^ ^ L{fnMicrosoft, {fnMicrosoft Sans Serif}.

11=()0+11)mod26{displaystyle 11=(0+11){bmod {2}6}

Por lo tanto, para descifrar R=^ ^ 17{displaystyle R,{widehat {=},17} con carta clave E=^ ^ 4{displaystyle E,{widehat {=},4}, el cálculo resultaría en 13=^ ^ N{displaystyle 13,{widehat {=},N}.

13=()17− − 4)mod26{displaystyle 13=(17-4){bmod {2}6}

En general, si .. {displaystyle Sigma } es el alfabeto de longitud l l {displaystyle ell }, y m{displaystyle m} es la longitud de la llave, encriptación y desciframiento Vigenère se puede escribir:

Ci=EK()Mi)=()Mi+K()imodm))modl l ,{displaystyle ¿Qué?

Mi=DK()Ci)=()Ci− − K()imodm))modl l .{displaystyle ¿Qué? }}

Mi{displaystyle M_{i} denota la compensación del i- el carácter del texto M{displaystyle M} en el alfabeto .. {displaystyle Sigma }. Por ejemplo, tomando los 26 caracteres ingleses como el alfabeto .. =()A,B,C,...... ,X,Y,Z){displaystyle Sigma =(A,B,C,ldotsX,Y,Z)}, la compensación de A es 0, la compensación de B es 1 etc. Ci{displaystyle C_{i} y Ki{displaystyle K_{i} son similares.

Cripanálisis

La idea detrás del cifrado Vigenère, como todos los demás cifrados polialfabéticos, es disfrazar la frecuencia de las letras del texto sin formato para interferir con una aplicación directa del análisis de frecuencia. Por ejemplo, si P es la letra más frecuente en un texto cifrado cuyo texto sin formato está en inglés, uno podría sospechar que P corresponde a e ya que e es la letra más utilizada en inglés. Sin embargo, al usar el cifrado Vigenère, e se puede cifrar como diferentes letras de texto cifrado en diferentes puntos del mensaje, lo que anula el análisis de frecuencia simple.

La principal debilidad del cifrado Vigenère es la naturaleza repetitiva de su clave. Si un criptoanalista adivina correctamente la longitud de la clave n, el texto cifrado se puede tratar como cifrados César intercalados n, que se pueden romper fácilmente de forma individual. La longitud de la clave se puede descubrir mediante una prueba de fuerza bruta de cada valor posible de n, o el examen de Kasiski y la prueba de Friedman pueden ayudar a determinar la longitud de la clave (ver a continuación: § Examen de Kasiski y § Prueba de Friedman).

Examen de Kasiski

En 1863, Friedrich Kasiski fue el primero en publicar un ataque general exitoso al cifrado de Vigenère. Los ataques anteriores se basaban en el conocimiento del texto sin formato o en el uso de una palabra reconocible como clave. El método de Kasiski no tenía tales dependencias. Aunque Kasiski fue el primero en publicar un relato del ataque, está claro que otros estaban al tanto. En 1854, Charles Babbage fue incitado a descifrar el cifrado de Vigenère cuando John Hall Brock Thwaites presentó un "nuevo" cifra al Diario de la Sociedad de las Artes. Cuando Babbage demostró que Thwaites' El cifrado era esencialmente otra recreación del cifrado de Vigenère, Thwaites presentó un desafío a Babbage: dado un texto original (de La tempestad de Shakespeare: acto 1, escena 2) y su versión cifrada, debía encontrar las palabras clave que Thwaites había utilizado para cifrar el texto original. Babbage pronto encontró las palabras clave: "dos" y "combinado". Luego, Babbage cifró el mismo pasaje de Shakespeare usando diferentes palabras clave y desafió a Thwaites a encontrar las palabras clave de Babbage. Babbage nunca explicó el método que usó. Los estudios de las notas de Babbage revelan que había usado el método publicado más tarde por Kasiski y sugieren que había estado usando el método ya en 1846.

El examen de Kasiski, también llamado prueba de Kasiski, aprovecha el hecho de que, por casualidad, las palabras repetidas a veces se cifran con las mismas letras clave, lo que da lugar a grupos repetidos en el texto cifrado. Por ejemplo, considere el siguiente cifrado usando la palabra clave ABCD:

Clave: ABCDABCDABCDABCDABCDABCD
Plaintext: cryptoisshortforcryptografito
Ciphertext: CSASTPKVSIQUTGQUCSASTPIUAQJB

Hay una repetición fácilmente perceptible en el texto cifrado, por lo que la prueba de Kasiski será efectiva.

La distancia entre las repeticiones de CSASTP es 16. Si se supone que los segmentos repetidos representan los mismos segmentos de texto sin formato, eso implica que la clave es 16, 8, 4, 2 o 1 caracteres largos. (Todos los factores de la distancia son longitudes de clave posibles; una clave de longitud uno es solo un cifrado César simple, y su criptoanálisis es mucho más fácil). Dado que las longitudes de clave 2 y 1 son irrealmente cortas, uno necesita probar solo las longitudes 16, 8 y 4. Los mensajes más largos hacen que la prueba sea más precisa porque normalmente contienen más segmentos de texto cifrado repetidos. El siguiente texto cifrado tiene dos segmentos que se repiten:

Ciphertext: VHVSSPQUCEMRVBVBBBVHVSURQGIBDUGRNICJQUCERVUAXSSR

La distancia entre las repeticiones de VHVS es 18. Si se supone que los segmentos repetidos representan los mismos segmentos de texto sin formato, eso implica que la clave es 18, 9, 6, 3, 2, o 1 caracteres de largo. La distancia entre las repeticiones de QUCE es de 30 caracteres. Eso significa que la longitud de la clave podría ser de 30, 15, 10, 6, 5, 3, 2 o 1 carácter. Al tomar la intersección de esos conjuntos, se podría concluir con seguridad que la longitud de clave más probable es 6, ya que 3, 2 y 1 son irrealmente cortos.

Prueba de Friedman

La prueba de Friedman (a veces conocida como la prueba de kappa) fue inventada durante los años veinte por William F. Friedman, quien utilizó el índice de coincidencia, que mide la desigualdad de las frecuencias de la letra de cifrado para romper el cifrado. Conociendo la probabilidad κ κ p{displaystyle kappa _{p}} que cualquier dos letras de origen escogidas aleatoriamente son las mismas (alrededor de 0.067 para el inglés insensible en caso de caso) y la probabilidad de una coincidencia para una selección uniforme aleatoria del alfabeto κ κ r{displaystyle kappa _{text{r}} ()1.26 = 0,0385 para inglés), la longitud clave se puede estimar como la siguiente:

κ κ p− − κ κ rκ κ o− − κ κ r{displaystyle {frac {kappa ###{text{p}-kappa {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} ¿Qué? ¿Qué?

de la tasa de coincidencia observada

κ κ o=.. i=1cni()ni− − 1)N()N− − 1){displaystyle kappa _{text{o}={frac {sum ¿Por qué?

donde c es el tamaño del alfabeto (26 para inglés), N es la longitud del texto y n1 a nc son las frecuencias de letras del texto cifrado observadas, como números enteros.

Sin embargo, eso es solo una aproximación; su precisión aumenta con la longitud del texto. En la práctica, sería necesario probar varias longitudes de clave cercanas a la estimación. Un mejor enfoque para los cifrados de clave repetida es copiar el texto cifrado en filas de una matriz con tantas columnas como longitud de clave supuesta y luego calcular el índice promedio de coincidencia con cada columna considerada por separado. Cuando se hace eso para cada longitud de clave posible, el índice de coincidencia promedio más alto corresponde a la longitud de clave más probable. Dichas pruebas pueden complementarse con información del examen de Kasiski.

Análisis de frecuencia

Una vez que se conoce la longitud de la clave, el texto cifrado se puede reescribir en tantas columnas, con cada columna correspondiente a una sola letra de la clave. Cada columna consta de texto sin formato que ha sido encriptado por un solo cifrado César. La tecla César (shift) es solo la letra de la tecla Vigenère que se usó para esa columna. Usando métodos similares a los que se usan para descifrar el cifrado César, se pueden descubrir las letras del texto cifrado.

Una mejora del examen Kasiski, conocido como Kerckhoffs' método, hace coincidir las frecuencias de las letras de cada columna con las frecuencias desplazadas del texto sin formato para descubrir la letra clave (desplazamiento César) de esa columna. Una vez que se conocen todas las letras de la clave, todo lo que el criptoanalista tiene que hacer es descifrar el texto cifrado y revelar el texto sin formato. Kerckhoffs' El método no es aplicable si la tabla de Vigenère ha sido codificada, en lugar de usar secuencias alfabéticas normales, pero el examen de Kasiski y las pruebas de coincidencia todavía se pueden usar para determinar la longitud de la clave.

Eliminación de llaves

El cifrado de Vigenère, con alfabetos normales, utiliza esencialmente aritmética de módulo, que es conmutativa. Por lo tanto, si se conoce (o se adivina) la longitud de la clave, al sustraer el texto cifrado de sí mismo, compensado por la longitud de la clave, se obtendrá el texto simple sustraído de sí mismo, también compensado por la longitud de la clave. Si alguna "palabra probable" en el texto plano se conoce o se puede adivinar, se puede reconocer su autosustracción, lo que permite recuperar la clave sustrayendo el texto plano conocido del texto cifrado. La eliminación de claves es especialmente útil contra mensajes cortos. Por ejemplo, usando LION como la clave a continuación:

Luego reste el texto cifrado de sí mismo con un cambio de longitud de clave 4 para LION.

Lo que es casi equivalente a restar el texto sin formato de sí mismo por el mismo cambio.

Que es algebraicamente representado para i▪ ▪ [1,n− − m]{displaystyle iin [1,n-m]} como:

()Ci− − C()i+m))modl l =()EK()Mi)− − EK()M()i+m)))modl l =()()Mi+K()imodm))modl l − − ()M()i+m)+K()()i+m)modm))modl l )modl l =()()Mi+K()imodm))− − ()M()i+m)+K()()i+m)modm)))modl l =()Mi+K()imodm)− − M()i+m)− − K()()i+m)modm))modl l =()Mi− − M()i+m)+K()imodm)− − K()()i+m)modm))modl l =()Mi− − M()i+m)+K()imodm)− − K()imodm))modl l =()Mi− − M()i+m))modl l {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}) {fnMicrosoft {fnMicrosoft}}} {fnunci} {fnK} {b}} {b} {b} {b} {b} {b}}}b}b}b} {b}b} {b}b}}b}}b}b}}b}b}b}b}b}b}b}b}b}b}b}b}b}b}b}b}b}b}b}}b}b} {b} {b} {b}b}b}b}b}b}b}b}b}}b}}b}b}}b}b}b}b}}b}b}}}b}b} {fnMicrosoft Sans Serif}) {fnMicrosoft}fnMicrosoft {fnMicrosoft}}) {bmod {bmod {x}}}bmod {cH00}cH00}}b}b}b}b}b}cH00}cH00}b}b}cH0cH00}b}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00cH00}cH00}cH00}cH00}cH00}cH00}cH00}}cH00}}}}cH00} }\\\cH0}cH00\bmod {m})}-M_{(i+m)}-K_{(i+m){bmod {m}}){bmod {ell ################################################################################################################################################################################################################################################################ ################################################################################################################################################################################################################################################################ ################################################################################################################################################################################################################################################################

En este ejemplo, las palabras brownfox son conocidas.

Este resultado omaz corresponde con las letras 9 a 12 en el resultado de los ejemplos más grandes anteriores. Se verifica la sección conocida y su ubicación.

Reste brow de ese rango del texto cifrado.

Esto produce el resultado final, la revelación de la clave LION.

Variantes

Tecla de ejecución

La variante de clave de ejecución del cifrado Vigenère también se consideró indescifrable en algún momento. Para la clave, esta versión utiliza un bloque de texto tan largo como el texto sin formato. Dado que la clave es tan larga como el mensaje, las pruebas de Friedman y Kasiski ya no funcionan, ya que la clave no se repite.

Si se utilizan varias claves, la longitud efectiva de la clave es el mínimo común múltiplo de las longitudes de las claves individuales. Por ejemplo, utilizando las dos claves GO y CAT, cuyas longitudes son 2 y 3, se obtiene una longitud de clave efectiva de 6 (el mínimo común múltiplo de 2 y 3). Esto puede entenderse como el punto donde ambas teclas se alinean.

Cifrar dos veces, primero con la clave GO y luego con la clave CAT es lo mismo que cifrar una vez con una clave obtenida al cifrar una clave con la otra.

Esto se demuestra cifrando attackatdawn con IOZQGH, para producir el mismo texto cifrado que en el ejemplo original.

Si las longitudes de clave son relativamente principales, la longitud de clave efectiva crece exponencialmente a medida que aumentan las longitudes de clave individuales. Por ejemplo, mientras que la longitud efectiva de las claves de 10, 12 y 15 caracteres es de solo 60, la de las claves de 8, 11 y 15 caracteres es de 1320. Si esta longitud efectiva de la clave es mayor que el texto cifrado, logra la misma inmunidad a las pruebas de Friedman y Kasiski como la variante clave en ejecución.

Si uno usa una clave que es realmente aleatoria, es al menos tan larga como el mensaje cifrado y se usa solo una vez, el cifrado de Vigenère es teóricamente indescifrable. Sin embargo, en ese caso, la clave, no el cifrado, proporciona la fuerza criptográfica, y dichos sistemas se denominan colectivamente como sistemas de libreta de un solo uso, independientemente de los cifrados empleados.

Rueda de cifer Confederate, capturada en la entrega de Mobile, Alabama, en mayo 1865 – Museo Nacional Cryptologic

Variante Beaufort

Una variante simple es cifrar utilizando el método de descifrado de Vigenère y descifrar utilizando el cifrado de Vigenère. Ese método a veces se denomina "Variante Beaufort". Es diferente del cifrado de Beaufort, creado por Francis Beaufort, que es similar a Vigenère pero utiliza un mecanismo de cifrado y un cuadro ligeramente modificados. El cifrado de Beaufort es un cifrado recíproco.

Cifrado de Gronsfeld

A pesar de la aparente solidez del cifrado Vigenère, nunca llegó a ser ampliamente utilizado en toda Europa. El cifrado Gronsfeld es una variante creada por el Conde Gronsfeld (Josse Maximilaan van Gronsveld né van Bronckhorst); es idéntico al cifrado de Vigenère, excepto que utiliza solo 10 alfabetos cifrados diferentes, correspondientes a los dígitos del 0 al 9). Una clave Gronsfeld de 0123 es lo mismo que una clave Vigenere de ABCD. El cifrado de Gronsfeld se fortalece porque su clave no es una palabra, pero se debilita porque solo tiene 10 alfabetos cifrados. Es el cifrado de Gronsfeld que se volvió ampliamente utilizado en toda Alemania y Europa, a pesar de sus debilidades.

Cifrado de clave automática de Vigenère

Vigenère en realidad inventó un cifrado más fuerte, un cifrado de clave automática. El nombre "cifrado de Vigenère" se asoció con un cifrado polialfabético más simple en su lugar. De hecho, los dos cifrados a menudo se confundían y ambos se llamaban a veces le chiffre indéchiffrable. Babbage en realidad rompió el cifrado de clave automática mucho más fuerte, pero generalmente se le atribuye a Kasiski la primera solución publicada para los cifrados polialfabéticos de clave fija.