Hackeando a Vigenère! (Cifrado + Python)

Al final de la Edad Media, en Francia, el diplomático francés Blaise de Vigenère (que obviamente tenía interés en las matemáticas) desarrolló un algoritmo que nadie pudo romper durante más de 250 años.

Vigenère presentó su método (probablemente en gran medida inspirado en el trabajo del criptoanalista italiano Giovan Battista Bellaso ) antes de la corte de Enrique III en 1586. El algoritmo es particularmente difícil para los científicos y estudiosos de la época que intentan descifrar el , lo que le hará ganar el apodo de figura indescifrable .

No fue sino hasta 1854 que un primer matemático, Charles Babbage , de Londres , llegó al final. En paralelo, el oficial prusiano retirado Friedrich Wilhelm Kasiski también tiene éxito en este tour de force y publica un método completo para hacer el sistema obsoleto en 1863.

Pero el sistema, incluso cuando se vio comprometido, continuó siendo utilizado, particularmente por los soldados de la Confederación, durante la Guerra Civil Americana (1861-1865).

El método de Vigenère consistió en elegir una clave y usarla para cifrar el mensaje en sí. Por ejemplo, imagine la siguiente situación:

Mensaje: la figura indescifrable
Clave: pitón
Así es como haríamos para encriptar nuestro mensaje en Excel. Las primeras dos líneas representan nuestro alfabeto con el número correspondiente a cada letra (en Python, siempre comenzamos nuestras listas por 0).

Luego tenemos la línea de nuestro mensaje, con el número de cada letra, luego nuestra clave, que se repite para cubrir todo el mensaje, y nuevamente con el número correspondiente a cada letra.

Para cifrar nuestro mensaje, simplemente sume los números correspondientes a la letra en el claro y la letra de nuestra clave. Por ejemplo, la primera letra del mensaje es "L", que está asociada con 11. La letra correspondiente a nuestra tecla es "P", que es el número "15". 11 + 15 = 26. No tenemos una letra 26, así que volvemos al principio, lo que nos da la letra "A".

La gran fortaleza de esta técnica reside en el hecho de que una letra se puede usar para encriptar varias otras. Por ejemplo, la "Y" de nuestra tecla "PYTHON" se utiliza para encriptar "E", "R", "C" y "A". Por el contrario, las letras encriptadas también pueden referirse a letras múltiples en el claro. En el mensaje cifrado, "A" devuelve tanto "L" como "C" y "H".

¡Además, con seis letras, hay 26 ^ 6 = 308 915 776 claves posibles! Y si hubiésemos hecho un pequeño esfuerzo adicional con una clave de 10 letras, hubiéramos tenido la posibilidad de elegir entre 141 167 095 653 376 combinaciones diferentes. No es de extrañar que los matemáticos hayan roto sus dientes durante casi tres siglos con este algoritmo. ¡Hay demasiadas posibilidades para probarlas todas, incluso con una computadora!

Durante más de 250 años, muchas personas creían que De Vigenère había ideado un algoritmo perfecto, pero eso equivalía a subestimar el maravilloso poder del ingenio humano y las matemáticas, como veremos.

Cifrar a la manera de Vigenère
Imagine que Blaise de Vigenère, al regresar de la corte, decide enviar el siguiente mensaje a Enrique III, para evitar que el rey lo olvide. Obviamente cifró el mensaje con la tecla Louise , que corresponde al nombre de la reina.

"Su Alteza Enrique III, Rey de Francia y todos los Franceses, espero que hayan encontrado divertido descifrar el siguiente mensaje. Fue cifrado en secreto con la técnica que te mostré durante mi última visita al tribunal. ¡Podría ser muy útil para su correspondencia, cuando la mayor discreción es necesaria! Tu eternamente fiel Blaise de Vigenère".

Aquí está el código en Python para encriptar todo. Mis comentarios comienzan en la línea 4. Notarás que estoy trabajando con un alfabeto sin caracteres. Es para simplificar. ¡Pero no dudes en complicarte la vida si tu corazón te lo dice!

Una vez lanzado en su terminal, debe tener un resultado idéntico al siguiente:

Una vez recibido, Enrique III (o más probablemente uno de sus servidores) debería haber descifrado todo a mano. ¡Afortunadamente, hoy tenemos Python! Aquí está el código para descifrar el mensaje. Solo comenté los pasajes que difieren.

Esto es lo que da una vez en la terminal. ¡Todo es legible de nuevo!

Hacker Vigenère!
Imposible probar todas las posibilidades clave, hay demasiadas. Por lo tanto, para hackear el algoritmo Vigenère, debe encontrar la manera de descartar algunas posibilidades clave para aislar solo un número pequeño, que luego puede probarse.

La primera pregunta que se debe hacer para hackear es: ¿Cuáles son las posibles longitudes de la clave?

En 1863, el oficial prusiano retirado, Friedrich Wilhelm Kasiski, encontró una manera muy elegante de tener una pequeña idea de ello y esta técnica ahora lleva su nombre. Se dio cuenta de que el algoritmo creaba repeticiones en el texto encriptado. Por ejemplo, en nuestro mensaje para Henry III:

GC NZW EWH YAK I SSHZA MTW, LWA HP TLIFGP SN LW XZIM TWW QFUVÇSMD, X'YAHÈVP MOE NSFG UDWD EFICNÉ EXIMIFX OS XÉKZMQTLMJ PP Un YAK ERS MCAZLBN. QD E Eee GYKJÈXPAYVL GSWZNJÉ EGSW TS XPQBVA UFS KCW NP Jick Y AIVLVÉP ZIZK HP AIV VICBCMJ TLGMIYI En el documento WO WWMV. TZ JWMVCOCB NSFG Ê NZW H'FBY OJEYRY CLMWWNÉ XGYC AIJ USCFYAHSYRUVUID, ZIZK UFS FI HPFG AZSROS XQKGCÉHCWF IDH HÉKWWDOCZW! ZZHLM ÉLICBYTDIXSHB XMOÈZY JDETGY LW ZTUYVÈJI.
Kasiski se dio cuenta de que si contamos el número de caracteres entre cada repetición, y que buscábamos factores comunes de estos "distancias", los factores comunes correspondían a la posible duración de la llave.

La razón es simple: cuanto más largo es el texto, más probable es que las mismas letras de la tecla estén alineadas con las mismas letras del texto que se codificará. Por lo tanto, las repeticiones aparecen en el mensaje secreto.

Entonces, no hay necesidad de probar cada longitud de clave imaginable. ¡El método de Kasiski elimina millones o incluso miles de millones de posibilidades!

Si sabemos que la clave probablemente estará compuesta de 6 caracteres ("Louise", por ejemplo), entonces sabemos que las letras en la posición 1, 7, 13, 19, 25, etc., fueron todas encriptado con la primera letra de la tecla ("L" en nuestro caso). Lo mismo para las letras en la posición 2, 8, 14, 20, 26, y así sucesivamente. Coloreé en azul las letras que se habrían codificado con el primer carácter de una clave con una longitud de 6, para el comienzo de nuestro texto encriptado.

G NZW E W HYAKI S S HZA M T W , LWA H P TLIFG P S N LW X Z IM TWW Q COMBUSTIBLE M D ...

Posteriormente, agrupamos estas letras en azul. Como sabemos que solo hay 26 letras posibles que las encriptan, podemos probar estas posibilidades una por una y realizar un análisis de frecuencia.

En francés, sabemos que las letras más usadas son E (14%), S (8%), A (7%), I (7%) y T (7%). Por lo tanto, al probar las 26 letras del alfabeto que podrían usarse para encriptar el mensaje, podemos verificar si el resultado de nuestra prueba está cerca de una distribución normal. Si es así, sabremos que la carta probada tiene buenas posibilidades de estar en la clave.

Después de probar y compilar los resultados de todas las letras primera, segunda, tercera, cuarta, quinta y sexta, deberíamos tener una buena idea de qué letras tienen más probabilidades de terminar en la clave.

Así que tendremos más para probar todas las combinaciones posibles para las letras sospechosas, para una clave de 6 caracteres.

En nuestro caso, cuando sabemos que la clave tiene 6 caracteres, hay 26 ^ 6 = 308 915 776 claves posibles. Sin embargo, con este método y nuestro script en Python, podemos encontrar la clave en ... ¡81 intentos!

Usted no me cree? Aquí está el guión completo. ¡Haz la prueba tú mismo!

Mis explicaciones en el comentario son bastante breves aquí. Este código está directamente inspirado en el de Hacking Secret Ciphers con Python , escrito por Al Sweigart. Te sugiero que vayas a ver si quieres más detalles. Mis principales cambios han sido hacer que el programa sea bilingüe, de modo que descifre ambos mensajes secretos en francés y en inglés. Además, el ejemplo de Al Sweigart es un conjunto de cinco scripts que funcionan en conjunto. Puse todo junto en un guión.

PD: Codigo Incompleto si deseas el código completo hazlo saber en los comentarios

¡Y eso es lo que da en la terminal!

Conclusión

Obviamente, estos algoritmos son tan antiguos como famosos y nadie debe usarlos. Hoy en día, los algoritmos de encriptación son mucho más complicados y mucho más seguros. Animo a todos a proteger sus datos personales. Pero tenga cuidado y permanezca atento, porque nadie está a salvo de una violación de seguridad ...!