En criptoanálisis , el análisis de frecuencia (también conocido como contar letras ) es el estudio de la frecuencia de letras o grupos de letras en un texto cifrado . El método se utiliza como ayuda para descifrar cifrados clásicos .
El análisis de frecuencia se basa en el hecho de que, en cualquier tramo dado del lenguaje escrito, ciertas letras y combinaciones de letras ocurren con frecuencias variables. Además, existe una distribución característica de letras que es aproximadamente la misma para casi todas las muestras de ese idioma. Por ejemplo, dada una sección del idioma inglés ,mi, T, A y O son los más comunes, mientras que Z, Q, X y Json raros. Igualmente,TH, ER, EN, y UNson los pares de letras más comunes (denominados bigramas o dígrafos ), ySS, EE, TT, y FFson las repeticiones más comunes. [1] La frase sin sentido " ETAOIN SHRDLU " representa las 12 letras más frecuentes en un texto típico en inglés.
En algunos cifrados, estas propiedades del texto sin formato del lenguaje natural se conservan en el texto cifrado, y estos patrones tienen el potencial de ser explotados en un ataque de solo texto cifrado .
Análisis de frecuencia para cifrados de sustitución simple
En un cifrado de sustitución simple , cada letra del texto sin formato se reemplaza por otra, y cualquier letra en particular en el texto sin formato siempre se transformará en la misma letra en el texto cifrado. Por ejemplo, si todas las apariciones de la letrami conviértase en la letra X, un mensaje de texto cifrado que contiene numerosas instancias de la carta X Sugeriría a un criptoanalista que X representa mi.
El uso básico del análisis de frecuencia es contar primero la frecuencia de las letras de texto cifrado y luego asociar las letras de texto sin formato adivinadas con ellas. MásXs en el texto cifrado que cualquier otra cosa sugiere que X corresponde a mi en el texto llano, pero esto no es seguro; t y a también son muy comunes en inglés, por lo que Xpodría ser cualquiera de ellos también. Es poco probable que sea un texto sin formato.z o qque son menos comunes. Por lo tanto, es posible que el criptoanalista deba probar varias combinaciones de asignaciones entre texto cifrado y letras de texto sin formato.
Se puede concebir un uso más complejo de la estadística, como la consideración de recuentos de pares de letras ( bigramas ), tripletes ( trigramas ), etc. Esto se hace para proporcionar más información al criptoanalista, por ejemplo,Q y U casi siempre ocurren juntos en ese orden en inglés, aunque Q en sí mismo es raro.
Un ejemplo
Supongamos que Eve ha interceptado el siguiente criptograma y se sabe que está cifrado mediante un cifrado de sustitución simple de la siguiente manera:
LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIMWQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJGSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXVIZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLEPPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPPXLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX
Para este ejemplo, las letras mayúsculas se utilizan para denotar texto cifrado, las letras minúsculas se utilizan para denotar texto sin formato (o suposiciones sobre tal), y X~t se usa para expresar una suposición de que la letra de texto cifrado X representa la letra de texto plano t.
Eve podría usar el análisis de frecuencia para ayudar a resolver el mensaje de la siguiente manera: los recuentos de las letras en el criptograma muestran que Ies la letra única más común, [2] SGbigrama más común , yXLIes el trigrama más común .mi es la letra más común en el idioma inglés, th es el bigrama más común, y laes el trigrama más común. Esto sugiere fuertemente queX~t, L~h y I~mi. La segunda letra más común del criptograma esmi; desde la primera y segunda letras más frecuentes en el idioma inglés,mi y t se tienen en cuenta, Eva adivina que mi~a, la tercera letra más frecuente. Haciendo tentativamente estas suposiciones, se obtiene el siguiente mensaje descifrado parcial.
heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReMWQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJGSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtVeZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMthaPPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPPthMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMt
Con estas suposiciones iniciales, Eva puede detectar patrones que confirman sus elecciones, como "que". Además, otros patrones sugieren más conjeturas".Rtate" puede ser "Expresar", lo que significaría R~s. Similar "atthattMZe"podría adivinarse como"En ese tiempo", cediendo METRO~I y Z~metro. Además, "heVe" puede ser "aquí", donación V~r. Al completar estas suposiciones, Eve obtiene:
aquíTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGaseiWQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJGSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtremitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQithaPPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPPthiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYit
A su vez, estas suposiciones sugieren otras más (por ejemplo, "remarA" podría ser "observación", Insinuando A~k) y así sucesivamente, y es relativamente sencillo deducir el resto de las letras y, finalmente, obtener el texto sin formato.
por lo tanto, la abuela se levantó con una tumba y un aire majestuoso y me trajo el escarabajo de un estuche de vidrionque estaba cerrado era una hermosa carabaeus y ese tiempo desconocido para los naturalistas decursogran premioenpunto de vista científicohay dos puntos negroscerca de unoextremityofthebackandalongoneneartheotthertheescalaswereexcedly harddandllossywithhalla aparición del oro quemadoel peso del insecto fue muy notable y llevándose todoLas cosas en consideración difícilmente podrían culpar a Júpiter por su opinión
En este punto, sería una buena idea que Eve insertara espacios y puntuación:
Entonces Legrand se levantó, con aire grave y majestuoso, y me trajo el escarabajo.de una vitrina en la que estaba encerrado. Era un hermoso escarabajo y, enesa vez, desconocido para los naturalistas, por supuesto, un gran premio en un punto científicode vista. Había dos manchas negras redondas cerca de una extremidad de la espalda, y unalargo uno cerca del otro. Las escamas eran extremadamente duras y brillantes, con todos losapariencia de oro bruñido. El peso del insecto fue muy notable y,teniendo en cuenta todas las cosas, difícilmente podría culpar a Júpiter por su opiniónrespetándolo.
En este ejemplo de The Gold-Bug , todas las conjeturas de Eve eran correctas. Sin embargo, este no siempre sería el caso; la variación en las estadísticas para textos simples individuales puede significar que las conjeturas iniciales son incorrectas. Puede ser necesario retroceder sobre las suposiciones incorrectas o analizar las estadísticas disponibles con mucha más profundidad que las justificaciones algo simplificadas que se dan en el ejemplo anterior.
También es posible que el texto sin formato no muestre la distribución esperada de frecuencias de letras. Es probable que los mensajes más cortos muestren más variaciones. También es posible construir textos sesgados artificialmente. Por ejemplo, se han escrito novelas enteras que omiten la letra "mi"en conjunto - una forma de literatura conocida como lipograma .
Historia y uso
La primera explicación registrada conocida del análisis de frecuencia (de hecho, de cualquier tipo de criptoanálisis) fue dada en el siglo IX por Al-Kindi , un erudito árabe , en A Manuscript on Deciphering Cryptographic Messages . [3] Se ha sugerido que un estudio textual detallado del Corán sacó a la luz por primera vez que el árabe tiene una frecuencia característica de letras. [4] Su uso se extendió, y sistemas similares fueron ampliamente utilizados en los estados europeos en la época del Renacimiento . Hacia 1474, Cicco Simonetta había escrito un manual sobre el descifrado de cifrados de textos latinos e italianos . [5]
Los criptógrafos inventaron varios esquemas para vencer esta debilidad en los cifrados de sustitución simple. Estos incluyeron:
- Sustitución homofónica : uso de homófonos : varias alternativas a las letras más comunes en cifrados de sustitución monoalfabéticos. Por ejemplo, para el inglés, tanto el texto cifrado X como el Y pueden significar texto sin formato E.
- Sustitución polialfabética , es decir, el uso de varios alfabetos, elegidos de formas variadas, más o menos tortuosas ( Leone Alberti parece haber sido el primero en proponer esto); y
- Sustitución poligráfica , esquemas en los que los pares o tripletes de letras de texto plano se tratan como unidades de sustitución, en lugar de letras individuales, por ejemplo, el cifrado de Playfair inventado por Charles Wheatstone a mediados del siglo XIX.
Una desventaja de todos estos intentos de derrotar los ataques de conteo de frecuencia es que aumenta la complicación tanto del cifrado como del descifrado, lo que conduce a errores. Se dice que un ministro de Relaciones Exteriores británico rechazó el cifrado de Playfair porque, incluso si los niños de la escuela pudieran hacer frente con éxito, como habían demostrado Wheatstone y Playfair, "¡nuestros agregados nunca podrían aprenderlo!".
Las máquinas de rotor de la primera mitad del siglo XX (por ejemplo, la máquina Enigma ) eran esencialmente inmunes al análisis de frecuencia sencillo. Sin embargo, otros tipos de análisis ("ataques") decodificaron con éxito los mensajes de algunas de esas máquinas.
El análisis de frecuencia requiere solo una comprensión básica de las estadísticas del lenguaje de texto plano y algunas habilidades para la resolución de problemas y, si se realiza a mano, tolerancia para la contabilidad de letras extensas. Durante la Segunda Guerra Mundial (Segunda Guerra Mundial), tanto los británicos como los estadounidenses reclutaron descifradores de códigos colocando crucigramas en los principales periódicos y organizando concursos para determinar quién podía resolverlos más rápido. Varios de los cifrados utilizados por las potencias del Eje se podían romper utilizando análisis de frecuencia, por ejemplo, algunos de los cifrados consulares utilizados por los japoneses. Los métodos mecánicos de conteo de letras y análisis estadístico (generalmente maquinaria tipo tarjeta de IBM ) se utilizaron por primera vez en la Segunda Guerra Mundial, posiblemente por el SIS del Ejército de los EE. UU . Hoy en día, el arduo trabajo de contar y analizar letras ha sido reemplazado por software de computadora , que puede llevar a cabo dicho análisis en segundos. Con la potencia informática moderna, es poco probable que los cifrados clásicos proporcionen una protección real para los datos confidenciales.
Análisis de frecuencia en la ficción
El análisis de frecuencia se ha descrito en la ficción. " The Gold-Bug " de Edgar Allan Poe y el cuento de Sherlock Holmes de Sir Arthur Conan Doyle " La aventura de los bailarines " son ejemplos de historias que describen el uso del análisis de frecuencia para atacar cifrados de sustitución simples. El cifrado en la historia de Poe está incrustado con varias medidas de engaño, pero esto es más un recurso literario que algo significativo criptográficamente.
Ver también
- ETAOIN SHRDLU
- Frecuencias de letras
- Frecuencia de letras árabes
- Índice de coincidencia
- Temas de criptografía
- Ley de Zipf
- Un vacío , novela de Georges Perec . El texto original en francés está escrito sin la letra e , al igual que la traducción al inglés. La versión en español no contiene a .
- Gadsby (novela) , una novela de Ernest Vincent Wright . La novela está escrita como un lipograma , que no incluye palabras que contengan la letra E.
Otras lecturas
- Helen Fouché Gaines, "Criptoanálisis", 1939, Dover. ISBN 0-486-20097-3
- Abraham Sinkov , "Criptoanálisis elemental: un enfoque matemático", The Mathematical Association of America, 1966. ISBN 0-88385-622-0 .
Referencias
- ^ Singh, Simon . "La cámara negra: consejos y sugerencias" . Consultado el 26 de octubre de 2010 .
- ^ "Un ejemplo trabajado del método de Bill's" A security site.com " " . Archivado desde el original el 20 de octubre de 2013 . Consultado el 31 de diciembre de 2012 .
- ^ Ibrahim A. Al-Kadi "Los orígenes de la criptología: las contribuciones árabes", Cryptologia , 16 (2) (abril de 1992) pp. 97-126.
- ^ "En nuestro tiempo: criptografía" . BBC Radio 4 . Consultado el 29 de abril de 2012 .
- ^ Kahn, David L. (1996). Los descifradores de códigos: la historia de la escritura secreta . Nueva York: Scribner. ISBN 0-684-83130-9.
enlaces externos
- Herramientas gratuitas para analizar textos: herramienta de análisis de frecuencia (con código fuente)
- Herramientas para analizar texto árabe
- Distribuciones estadísticas de letras en árabe
- Distribuciones estadísticas de texto en inglés
- Distribuciones estadísticas del texto checo
- Frecuencias de caracteres y sílabas de 33 idiomas y una herramienta portátil para crear distribuciones de frecuencias y sílabas
- Análisis de frecuencia en inglés basado en un flujo de datos en vivo de publicaciones de un foro.
- Descifrar texto
- Frecuencia de letras en alemán