Tutoriales

Introducción a la criptozoología – Cifrado Vigenère: Rack

existir Mi primera publicación en un blog sobre criptografía Introduje algunas definiciones y conceptos, uno de los cuales es el concepto substitution ciphers.

En resumen, estas contraseñas reemplazan los tokens de texto sin formato con algún método dependiente de la contraseña. key.

Olvidé mencionar que los métodos de cifrado y descifrado pueden ser ligeramente diferentes, pero las claves se utilizarán para cifrar y descifrar; estos cifrados se llaman symmetric ciphers.

Ya hemos visto ejemplos de esto. monoalphabetic substitution ciphers – Estas son contraseñas alternativas una carta cada vez.También vimos cómo utilizar frequency analysis romper el código.

En este artículo quiero mostrar un ejemplo de un cifrado de sustitución que no es monoletra, explicar por qué falla el análisis de frecuencia ingenuo y cómo la gente todavía intenta descifrar el cifrado.

Poseer conocimientos de aritmética modular. Mi entrada de blog anterior¡Esto debería ser muy fácil!

Tabla de Contenidos

Publicaciones relacionadas

motivación

Hemos visto que los cifrados monoalfabéticos son susceptibles de análisis de frecuencia porque las mismas letras del texto claro se cifran como letras del texto cifrado.

Puede crear un cifrado de sustitución simple pero más complejo, por ejemplo, haciendo coincidir cada dos letras con otras dos letras.esos se llaman digraphs Un ejemplo famoso de gráfico dirigido es código de juego limpio.

Este tipo de cifrado es mucho más seguro que un cifrado de sustitución de una sola letra, pero aún es susceptible a ciertos análisis de frecuencia (p. ej. th El inglés es más común que el inglés. zx).

Existen otras técnicas más sofisticadas para hackear Playfair; no las discutiré aquí.

La mayor ventaja es Playfair (y otros digraph ciphers) está distribuido de manera más uniforme en el texto cifrado, por lo que se necesita más texto para un análisis de frecuencia serio.

Puede ir más allá (hacer algo similar con 3 letras, 4 letras, etc.), pero también puede hacer una declaración similar: suficiente texto cifrado para realizar un análisis de frecuencia.

contraseña

El cifrado Vigenère hizo algo novedoso: en lugar de cifrar con constantes n-gram (3 letras, etc.) Cifra cada letra utilizando una letra diferente del alfabeto derivada de la clave de cifrado.

Por tanto, podemos clasificar esta contraseña como polyalphabetic substitution cipher La frecuencia depende de la longitud de la clave, lo que hace que el análisis de frecuencia simple no sea práctico.

Veamos un ejemplo.Para esto usaremos Tabula Recta (también conocido como Vigenère squareesto es hermoso

La idea es simple: digamos que la primera letra que queremos cifrar es D La primera letra de la clave es Q.

Miramos Tabula Recta y miramos las columnas. D Hechizar Q obtenemos un Tentonces sumamos T a nuestro texto secreto. Sigue surgiendo la misma idea (por ejemplo, cifrar la segunda letra de texto plano usando una tabla con la segunda letra clave como una fila).

Por supuesto, la clave puede ser mucho más corta que el texto sin formato, por lo que simplemente usamos la clave en forma circular.
Podemos simplificar usando aritmética modular:

import string

def encrypt(plaintext, key):
    """
        Encrypts the plaintext (discarding any non-uppercase English letters).
        This assumes the key is already all uppercase English letters.
    """

    uppers = [ c for c in plaintext if c in string.ascii_uppercase ]
    return ''.join([ chr(ord('A') + ((ord(uppers[i]) - ord('A') + ord(key[i % len(key)]) - ord('A')) % 26)) for i in range(len(uppers)) ])

¡Observa lo simple que es la contraseña!línea definida uppers La variable simplemente descarta todos los caracteres que no sean mayúsculas, pero la esencia del algoritmo es return Términos:

  1. Iteramos sobre el índice del texto plano (uppers después del filtrado), cada índice se llama i.
  2. Obtenemos el índice de la carta (p. ej. A, B1 etc.) a través de subestructuras ord('A') a partir de letras de texto sin formato y agregarlas a keyEl índice alfabético actual de .
  3. La llave se recicla, por eso utilizamos key[i % len(key)].
  4. Dado que la adición de viñetas (2) puede exceder 25usamos % 26 Luego simplemente agrega ord('A') Que vuelva a ser una carta.

Si lees este algoritmo con atención, encontrarás algo interesante: es exactamente Caesar cipher ¡Úselo individualmente para cada letra clave!

Por ejemplo, si la longitud de la clave es 4, las letras 1.ª, 5.ª, 9.ª (y así sucesivamente) del texto sin formato simplemente se desplazarán con el mismo desplazamiento.

Esta es exactamente la ventaja y desventaja del cifrado Vigenère: el análisis de frecuencia simple falla (porque el mapeo depende en gran medida de la longitud de la clave)… pero si conocemos la longitud de la clave, ¡es trivial!

romper el código

El análisis estadístico del texto cifrado puede revelar la longitud de la clave y, una vez conocida, se puede aplicar el análisis de frecuencia.

Una herramienta útil para afrontar polyalphabetic ciphers se llama cheque kassky.

En esencia, la idea es muy simple: si encontramos apariciones repetidas en el texto cifrado (al menos 3 caracteres son útiles), entonces la distancia entre estas apariciones probablemente sea un múltiplo de la longitud de la clave.

Si encontramos varios candidatos duplicados, podemos tomar el máximo común divisor de todas estas distancias.

Tomemos como ejemplo el siguiente texto cifrado:

MNBBMIJHBQGBBHEMZVFTBLFCAMGMLYWAIJMVQPNXJVKMSQNNOJVSKFQSGMIMFVCYPHBJVUKWYEFKFRVTZTAPSJVSKFQSGMIEXMSDBNVPXSFDQRVVLHSFBWIQAYLWRFQAYTFPADSNUGLNHQHIUNLWZVLAFQECQJGWIGKCUWQSYROZDFBJGZGCNRNQSINXFFAXMFPGHYNEUQSHLASQYRATJLASTAPSJVVBRKOHMAIJPCZDRZBLSMAMDRPNQLBQWWUIYJGKQQSFPFTWWVUMJPFXETMTAIMRSDWSPHVUNEETVMCXMWIFMSDMLETVDWAUNRQXEOHFXDGPFXTXUUNFENXZLQTOBTNQKFODTRZYLSGAASGWKXZXCFHRZPMVLHTIFKWEHMVQYGMFGZNGNOEMXQWWOYNHVIIJTQTIRDJVLASKRRIQPSEWWEVUNRBNBUOEPNKZHFTITPXGZHCXIIMQMKMSZEQBTXWTQTEEAJBHEOUNSWWXZXTUFGMJRLAHUMRPTALHFQDHKJEXKOOTVWSMMGRQRFBFRVBHZOZAXQAMVUDVLSXKACIMLETVCBRUDVBNRERVQAQLFQFDWPPEWGETEMOOCQJHAMHTELZJEDEOXIXMNQSWSMDVAHSNXFKTBLFCAYCGNQIHSEIIFEEEFMLTGQCBVIXZBGUSPWTPAMRAEFEMELBKMNGQYXGBTUTZIPIKTAUSGIPIAMGNEPIZWWBGORREJHAMIBNBBGIUTIEEVBISWLBFLVSJQWHFRERTXXZKSMTRVJHTRAQOEBMMFDGUMNAREJMOESBZISWLBFLVSJXWTQTIAOFRVLVAUYLSXTXVQRRLFQFDWPAYTMIVHSEIFXQEQZOYEFBMIQKSMLYIQMCXOZDGPJRAMVMPCMSIVTRAOEWUIFXRFONETVDWFGSUQSKLAFAUTPYLWIVANRTNRWEWWEUMWSAGHTRBCLLSGOPDVKYWNXWZSNVJPWVHDOAQHTMEGQIFAJRLHIFAEMKYYXTDOZBMIVTMFOQIDMFVCYPRBJRUBSEIFATYYAHMBBIWHALTAUALYLALWEIGBMMKBGIHRZJMTXZANTQPRGPSHEEGTRWASDERDJRAYWHEAMAIJFSFTUMRRWOSDTNTPIVMCFHRUREQGSHEEPJEJYFAMGPJQSZOUNVSSSORCGAYTIEEGYUDGGNRYNDFHRXMSFXZUNRILEAGHTELZJEDEOXIXMDSMUSFYBCWEKLKQRRIQPSEWWEJMAITXSZSCWTRXXRNAOGKSGWOFSPPTSDPVQNJMMYFZSDEQNTVKMSMKGPJFAMGAFZMFXLAOFYBCIMVESFSYQUXZKCGGUEJVWIFQCUMBIVTBPTNAYIDXGEWRDJFWXBPOZQSELXRNYFIIMKMGARVOSSJXRNYGPJEHTHTEGQHXZXTQWGPFXZTREOZMYLAGUFOGMFGZYCGNQCXAAEZUNTXZTAEGNUGBMSKXTQWNZJPADSPRBXXSXPOFEEQSXZXRQSRZYXZBGUSBCWAGKZPNBEYLWPCDLQWKXZXSXEPBWSFTBPTUMXAAMQTTUMGISNHKOSBMITTIPWRUFOWNGQOSIXIJOWOENTWISWMQXVAYMFZKUTUWZXHTMUNTNTVOAOFCBCQHTXRURGKMISIWRIGEFWFMFGNOGUVGYWFERZNRYZZGTGWSWSGRKOHKFPDNGORVUNRSEGIERFUPGKSMNQGTYUTZXUFKWMEBBMLFEJWWXYMFGMWOFHKXEQOJEFWMAUPIQPMLQDIZQSEDLKQEKQXXOBHTOHBXOAGQALBZBMLACGTAIYMGGOXIGGBMLACGTEMQMYBCGSOQFWSGRKOHKFPDNGORVUNRSEGKOHJZMDWOFOZQHFGFPEYBCBEYXKMRFGTYENFPEEKMISMOZDYQJXGNGMNQBWCLHAMKRCXFWEWQVRQYWXHFAUEWBRYHCPYRBBIJXHTEPZNQAGOXSLMXMSFOORVUNRSEAKCEQRIALHTAGWKGMKWASVBDQQVFUMRQXXZTHAFWCIKAGUBEBXQITRKTAGBMIQLOKAALYLAGYZOGEMELMVQYYWTODBYQMLKWMEXWETUIYSXHIFSZIWXAGUKOHATQWMVUNTBMELRCGWVTQRWOSDFBZLMNXAQFBZNEETVMCXMWEFWHTIFQXQQFOZISMXXGRCGMNGXXGIHTIFQSHAOWPUNTGYLRCGCNVYWLHDGSNTQEXMSDAYTBIJXOXLNTNOW

¡Busquemos algunos caracteres repetidos en el texto cifrado! Para la longitud 7, aquí hay un enfoque muy ingenuo (solo elegí 7, pero normalmente comenzarías con 3):

repeats = [ ciphertext[i:i+7] for i in range(0, len(ciphertext) - 7) if ciphertext.count(ciphertext[i:i+7]) > 1 ]

Ahora podemos comprobar las distancias y obtenerlas. gcd (Máximo común divisor):

repeats = [ ciphertext[i:i+7] for i in range(0, len(ciphertext) - 7) if ciphertext.count(ciphertext[i:i+7]) > 1 ]
distances = [ len(ciphertext.split(entry)[1])+7 for entry in repeats ]
import math
candidate = math.gcd(*distances)

Este conjunto candidate es 9, por lo que creemos firmemente que la longitud de la clave es 9.

Suponiendo que la longitud de la clave es 9, dividimos el texto cifrado en 9 bloques y realizamos un análisis de frecuencia en cada bloque.

No me tomaré la molestia de este análisis (ya lo he hecho Mi primera publicación en un blog sobre criptografía) – pero el resultado debería ser así:

ANOTHERONEGOTCAUGHTTODAYITSALLOVERTHEPAPERSTEENAGERARRESTEDINCOMPUTERCRIMESCANDALHACKERARRESTEDAFTERBANKTAMPERINGDAMNKIDSTHEYREALLALIKEBUTDIDYOUINYOURTHREEPIECEPSYCHOLOGYANDSTECHNOBRAINEVERTAKEALOOKBEHINDTHEEYESOFTHEHACKERDIDYOUEVERWONDERWHATMADEHIMTICKWHATFORCESSHAPEDHIMWHATMAYHAVEMOLDEDHIMIAMAHACKERENTERMYWORLDMINEISAWORLDTHATBEGINSWITHSCHOOLIMSMARTERTHANMOSTOFTHEOTHERKIDSTHISCRAPTHEYTEACHUSBORESMEDAMNUNDERACHIEVERTHEYREALLALIKEIMINJUNIORHIGHORHIGHSCHOOLIVELISTENEDTOTEACHERSEXPLAINFORTHEFIFTEENTHTIMEHOWTOREDUCEAFRACTIONIUNDERSTANDITNOMSSMITHIDIDNTSHOWMYWORKIDIDITINMYHEADDAMNKIDPROBABLYCOPIEDITTHEYREALLALIKEIMADEADISCOVERYTODAYIFOUNDACOMPUTERWAITASECONDTHISISCOOLITDOESWHATIWANTITTOIFITMAKESAMISTAKEITSBECAUSEISCREWEDITUPNOTBECAUSEITDOESNTLIKEMEORFEELSTHREATENEDBYMEORTHINKSIMASMARTASSORDOESNTLIKETEACHINGANDSHOULDNTBEHEREDAMNKIDALLHEDOESISPLAYGAMESTHEYREALLALIKEANDTHENITHAPPENEDADOOROPENEDTOAWORLDRUSHINGTHROUGHTHEPHONELINELIKEHEROINTHROUGHANADDICTSVEINSANELECTRONICPULSEISSENTOUTAREFUGEFROMTHEDAYTODAYINCOMPETENCIESISSOUGHTABOARDISFOUNDTHISISITTHISISWHEREIBELONGIKNOWEVERYONEHEREEVENIFIVENEVERMETTHEMNEVERTALKEDTOTHEMMAYNEVERHEARFROMTHEMAGAINIKNOWYOUALLDAMNKIDTYINGUPTHEPHONELINEAGAINTHEYREALLALIKEYOUBETYOURASSWEREALLALIKEWEVEBEENSPOONFEDBABYFOODATSCHOOLWHENWEHUNGEREDFORSTEAKTHEBITSOFMEATTHATYOUDIDLETSLIPTHROUGHWEREPRECHEWEDANDTASTELESSWEVEBEENDOMINATEDBYSADISTSORIGNOREDBYTHEAPATHETICTHEFEWTHATHADSOMETHINGTOTEACHFOUNDUSWILLINGPUPILSBUTTHOSEFEWARELIKEDROPSOFWATERINTHEDESERTTHISISOURWORLDNOWTHEWORLDOFTHEELECTRONANDTHESWITCHTHEBEAUTYOFTHEBAUDWEMAKEUSEOFASERVICEALREADYEXISTINGWITHOUTPAYINGFORWHATCOULDBEDIRTCHEAPIFITWASNTRUNBYPROFITEERINGGLUTTONSANDYOUCALLUSCRIMINALSWEEXPLOREANDYOUCALLUSCRIMINALSWESEEKAFTERKNOWLEDGEANDYOUCALLUSCRIMINALSWEEXISTWITHOUTSKINCOLORWITHOUTNATIONALITYWITHOUTRELIGIOUSBIASANDYOUCALLUSCRIMINALSYOUBUILDATOMICBOMBSYOUWAGEWARSYOUMURDERCHEATANDLIETOUSANDTRYTOMAKEUSBELIEVEITSFOROUROWNGOODYETWERETHECRIMINALSYESIAMACRIMINALMYCRIMEISTHATOFCURIOSITYMYCRIMEISTHATOFJUDGINGPEOPLEBYWHATTHEYSAYANDTHINKNOTWHATTHEYLOOKLIKEMYCRIMEISTHATOFOUTSMARTINGYOUSOMETHINGTHATYOUWILLNEVERFORGIVEMEFORIAMAHACKERANDTHISISMYMANIFESTOYOUMAYSTOPTHISINDIVIDUALBUTYOUCANTSTOPUSALLAFTERALLWEREALLALIKE

esto es lo que se sabe Manifiesto de los hackers!

generalizar

Esta publicación de blog nos ha presentado algunos conceptos nuevos y hemos visto cómo los cifrados de tablas múltiples pueden hacer que el análisis de frecuencia simple sea un desafío, pero aún susceptible al análisis estadístico.

En las próximas publicaciones de blog sobre criptografía, planeo comenzar a hablar sobre criptografía más moderna: la criptografía Vigenère es todo menos moderna.

Aún así, creo que es valioso discutir estos conceptos desde una perspectiva de «forma de pensar» sobre los pros y los contras de la criptografía.

LEER  Cómo guardar y salir de archivos en los editores Vi/Vim en Linux

Publicaciones relacionadas

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Botón volver arriba