.svg/1280px-English_letter_frequency_(alphabetic).svg.png)
En criptoanálisis , el análisis de frecuencia (también conocido como conteo de 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 más o menos la misma en casi todas las muestras de esa lengua. Por ejemplo, dada una sección de idioma inglés ,mi,t,Ayohson los más comunes, mientrasz,q,Xyjson raros. Asimismo,TH,urgencias,EN, yUNson los pares de letras más comunes (denominados bigramas o dígrafos ), ySS,EE.UU.,TT, yFFson 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, dichas propiedades del texto sin formato en lenguaje natural se conservan en el texto cifrado y estos patrones tienen el potencial de explotarse en un ataque de solo texto cifrado .
En un cifrado de sustitución simple , cada letra del texto claro se reemplaza por otra, y cualquier letra particular del texto claro siempre se transformará en la misma letra del texto cifrado. Por ejemplo, si todas las apariciones de la letramiconvertirse en la letraX, un mensaje de texto cifrado que contiene numerosas instancias de la cartaXsugeriría a un criptoanalista queXrepresentami.
El uso básico del análisis de frecuencia es contar primero la frecuencia de las letras de texto cifrado y luego asociar con ellas las letras de texto sin formato adivinadas. MásXs en el texto cifrado que cualquier otra cosa sugiere queXcorresponde amien el texto claro, pero esto no es seguro;tyaTambién son muy comunes en inglés, por lo queXpodría ser cualquiera de ellos también. Es poco probable que sea un texto sin formato.zoqque son menos comunes. Por lo tanto, es posible que el criptoanalista necesite probar varias combinaciones de asignaciones entre letras de texto cifrado y texto sin formato.
Se puede concebir un uso más complejo de la estadística, como considerar recuentos de pares de letras ( bigramas ), tripletes ( trigramas ), etc. Esto se hace para proporcionar más información al criptoanalista, por ejemplo,qyUd.casi siempre aparecen juntos en ese orden en inglés, aunqueqen sí es raro.
Supongamos que Eve ha interceptado el siguiente criptograma y se sabe que está cifrado utilizando un cifrado de sustitución simple de la siguiente manera:
LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIMWQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJGSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXVIZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLEPPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPPXLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX
Para este ejemplo, las letras mayúsculas se utilizan para indicar texto cifrado, las letras minúsculas se utilizan para indicar texto sin formato (o conjeturas sobre el mismo) yX~tse utiliza para expresar una suposición de que la letra del texto cifradoXrepresenta la letra de texto planot.
Eve podría usar el análisis de frecuencia para ayudar a resolver el mensaje de la siguiente manera: el recuento de las letras en el criptograma muestra queIes la letra individual más común, [2] SGbigram más común , yXLIIes el trigrama más común .mies la letra más común en el idioma inglés,thes el bigrama más común, yeles el trigrama más común. Esto sugiere fuertemente queX~t,l~hy I~mi. La segunda letra más común en el criptograma esmi; desde la primera y segunda letra más frecuente en el idioma inglés,miytestán contabilizados, Eve supone quemi~a, la tercera letra más frecuente. Haciendo estas suposiciones tentativamente, se obtiene el siguiente mensaje descifrado parcial.
heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReMWQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJGSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtVeZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMthaPPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPPthMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVerCeGtMWYMt
Usando estas conjeturas iniciales, Eve puede detectar patrones que confirman sus elecciones, como "eso". Además, otros patrones sugieren más conjeturas. "tasa" puede ser "estado", lo que significaríaR~s. Similarmente "atthattMZe" podría adivinarse como "En ese tiempo", cediendoMETRO~iyz~metro. Además, "él" puede ser "aquí", donaciónV~r. Al completar estas conjeturas, Eve obtiene:
aquíTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGaseiWQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJGSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtremitFSJtheKaGAaWHaPSWYSWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQithaPPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPPthiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYit
A su vez, estas conjeturas sugieren otras más (por ejemplo, "remarA" podría ser "observación", InsinuandoA~k) y así sucesivamente, y es relativamente sencillo deducir el resto de las letras, lo que finalmente produce el texto sin formato.
Entonces Legranda se levantó con un aire grave y señorial y me trajo el escarabajo de una vitrina.en el cual estaba cerrado era un hermoso carabeo y en ese momento desconocido para los naturalistas decursoungranpremioenunpuntodevistacientíficohabíadospuntosnegrosredondoscercadeunoextremisión de la parte posterior y a lo largo de una cerca de la otra, las escalas eran extremadamente duras y brillantes con unatoda la apariencia de oro bruñido el peso del insecto era muy notable y tomando todolas cosas en consideracióndifícilmente podría culpar a Júpiter por su opinión al respetarla
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 scarabaeus y, alaquel tiempo, desconocido para los naturalistas; por supuesto, un gran premio en un punto científicode vista. Había dos puntos negros redondos cerca de un extremo de la espalda y unde largo uno cerca del otro. Las escamas eran extremadamente duras y brillantes, con todas lasaspecto de oro bruñido. El peso del insecto fue muy notable y,Teniendo todo en cuenta, no puedo culpar a Júpiter por su opinión.respetándolo.
En este ejemplo de The Gold-Bug , todas las conjeturas de Eve fueron correctas. Sin embargo, este no sería siempre el caso; la variación en las estadísticas de textos planos individuales puede significar que las conjeturas iniciales sean incorrectas. Puede que sea necesario retroceder en las conjeturas incorrectas o analizar las estadísticas disponibles con mucha más profundidad que las justificaciones algo simplificadas dadas en el ejemplo anterior.
También es posible que el texto plano no muestre la distribución esperada de frecuencias de letras. Es probable que los mensajes más cortos muestren más variación. También es posible construir textos sesgados artificialmente. Por ejemplo, se han escrito novelas enteras en las que se omite la letra "mi" en total, una forma de literatura conocida como lipograma .
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 Un manuscrito sobre el descifrado de mensajes criptográficos . [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 de letras característica. [4] Su uso se extendió y sistemas similares se utilizaron ampliamente en los estados europeos en la época del Renacimiento . En 1474, Cicco Simonetta había escrito un manual sobre cómo descifrar cifrados de textos en latín e italiano . [5]
Los criptógrafos inventaron varios esquemas para superar esta debilidad en los cifrados de sustitución simples. Estos incluyeron:
Una desventaja de todos estos intentos de derrotar los ataques de conteo de frecuencia es que aumentan la complicación tanto del cifrado como del descifrado, lo que lleva a errores. Es famoso el hecho de que un Ministro de Asuntos Exteriores británico rechazó el cifrado de Playfair porque, incluso si los escolares pudieran arreglárselas 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 mensajes de algunas de esas máquinas. [6]
El análisis de frecuencia requiere sólo 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 una contabilidad extensa de cartas. Durante la 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 ver quién podía resolverlos más rápido. Varios de los cifrados utilizados por las potencias del Eje se podían descifrar mediante análisis de frecuencia, por ejemplo, algunos de los cifrados consulares utilizados por los japoneses. Los métodos mecánicos de recuento 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 estadounidense . Hoy en día, el arduo trabajo de contar y analizar letras ha sido reemplazado por software informático , 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.
El análisis de frecuencia se ha descrito en la ficción. " El insecto de oro " 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.