Análisis de frecuencia - Frequency analysis

Para otros usos, consulte Análisis de frecuencia (desambiguación) .
Una distribución típica de letras en un texto en inglés . Los cifrados débiles no enmascaran suficientemente la distribución, y esto podría ser aprovechado por un criptoanalista para leer el mensaje.

En el 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 , UN y O son los más comunes, mientras que Z , Q , X y J son raros. Igualmente, TH , ER , EN y UN son los pares de letras más comunes (denominados bigramas o dígrafos ), y SS , EE , TT y FF son las repeticiones más comunes. 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 letra mi conviértase en la carta 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ás X s 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 un también son muy comunes en inglés, por lo que X podría ser cualquiera de ellos también. Es poco probable que sea un texto sin formato z o q que son menos comunes. Por lo tanto, el criptoanalista puede necesitar probar varias combinaciones de asignaciones entre texto cifrado y letras de texto plano.

Se puede concebir un uso más complejo de las estadísticas, como considerar el número 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: 

LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM
WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ
GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV
IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE
PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP
XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX

Para este ejemplo, se usan letras mayúsculas para denotar texto cifrado, letras minúsculas para denotar texto sin formato (o conjeturas 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 yo es la letra única más común, SG bigrama más común , y XLI es 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 la es el trigrama más común. Esto sugiere fuertemente que X ~ t , L ~ h y yo ~ mi . La segunda letra más común del criptograma es mi ; desde la primera y segunda letras más frecuentes en el idioma inglés, mi y t se tienen en cuenta, Eve adivina que mi ~ un , la tercera letra más frecuente. Haciendo tentativamente estas suposiciones, se obtiene el siguiente mensaje descifrado parcial. 

heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM
WQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJ
GSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV
eZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMtha
PPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPP
thMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMt

Con estas suposiciones iniciales, Eve puede detectar patrones que confirman sus elecciones, como " ese ". Además, otros patrones sugieren más conjeturas". Rtate " puede ser " estado ", lo que significaría R ~ s . Similar " atthattMZe "podría adivinarse como" En ese tiempo ", cediendo METRO ~ yo y Z ~ metro . Además, " heVe " puede ser " aquí ", dando V ~ r . Al completar estas suposiciones, Eve obtiene: 

hereTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGasei
WQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJ
GSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtr
emitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQitha
PPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPP
thiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYit

A su vez, estas suposiciones sugieren otras más (por ejemplo, " remarA " podría ser " observación ", Insinuando UN ~ k ) y así sucesivamente, y es relativamente sencillo deducir el resto de las letras, lo que finalmente produce el texto sin formato. 

hereuponlegrandarosewithagraveandstatelyairandbroughtmethebeetlefromaglasscasei
nwhichitwasencloseditwasabeautifulscarabaeusandatthattimeunknowntonaturalistsof
courseagreatprizeinascientificpointofviewthereweretworoundblackspotsnearoneextr
emityofthebackandalongoneneartheotherthescaleswereexceedinglyhardandglossywitha
lltheappearanceofburnishedgoldtheweightoftheinsectwasveryremarkableandtakingall
thingsintoconsiderationicouldhardlyblamejupiterforhisopinionrespectingit

En este punto, sería una buena idea que Eve insertara espacios y puntuación: 

Hereupon Legrand arose, with a grave and stately air, and brought me the beetle
from a glass case in which it was enclosed. It was a beautiful scarabaeus, and, at
that time, unknown to naturalists—of course a great prize in a scientific point
of view. There were two round black spots near one extremity of the back, and a
long one near the other. The scales were exceedingly hard and glossy, with all the
appearance of burnished gold. The weight of the insect was very remarkable, and,
taking all things into consideration, I could hardly blame Jupiter for his opinion
respecting it.

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 suposiciones iniciales son incorrectas. Puede que sea necesario revertir 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

Primera página del manuscrito del siglo IX de Al-Kindi sobre el descifrado de mensajes criptográficos
Distribución de frecuencia de letras árabes .

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 . 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. Su uso se extendió y los sistemas similares se utilizaron ampliamente en los estados europeos en la época del Renacimiento . En 1474, Cicco Simonetta había escrito un manual sobre el descifrado de cifrados de texto latino e italiano .

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 lleva 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 correctamente los mensajes de algunas de esas máquinas.

Frecuencias de letras en español.

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 resolver 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 el 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 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 del recuento y análisis de letras ha sido reemplazado por software de computadora , que puede realizar 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

Parte del criptograma en The Dancing Men

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 frecuencias para atacar cifrados de sustitución simples. El cifrado de 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

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

  1. ^ Singh, Simon . "La cámara negra: consejos y sugerencias" . Consultado el 26 de octubre de 2010 .
  2. ^ "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 .
  3. ^ Ibrahim A. Al-Kadi "Los orígenes de la criptología: las contribuciones árabes", Cryptologia , 16 (2) (abril de 1992) págs. 97-126.
  4. ^ "En nuestro tiempo: criptografía" . BBC Radio 4 . Consultado el 29 de abril de 2012 .
  5. ^ 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