Análise de frequência - Frequency analysis

Uma distribuição típica de letras em textos em inglês . Cifras fracas não mascaram suficientemente a distribuição e isso pode ser explorado por um criptanalista para ler a mensagem.

Na criptoanálise , a análise de frequência (também conhecida como contagem de letras ) é o estudo da frequência das letras ou grupos de letras em um texto cifrado . O método é usado como um auxílio para quebrar cifras clássicas .

A análise de frequência é baseada no fato de que, em qualquer extensão da linguagem escrita, certas letras e combinações de letras ocorrem com frequências variadas. Além disso, há uma distribuição característica de letras que é aproximadamente a mesma para quase todas as amostras desse idioma. Por exemplo, dada uma seção do idioma inglês , E , T , UMA e O são os mais comuns, enquanto Z , Q , X e J são raros. Da mesma forma, º , ER , EM e A são os pares de letras mais comuns (denominados bigramas ou dígrafos ), e SS , EE , TT e FF são as repetições mais comuns. A frase sem sentido " ETAOIN SHRDLU " representa as 12 letras mais frequentes em um texto típico do idioma inglês.

Em algumas cifras, essas propriedades do texto simples da linguagem natural são preservadas no texto cifrado, e esses padrões têm o potencial de ser explorados em um ataque apenas de texto cifrado .

Análise de frequência para cifras de substituição simples

Em uma cifra de substituição simples , cada letra do texto simples é substituída por outra, e qualquer letra particular do texto simples sempre será transformada na mesma letra do texto cifrado. Por exemplo, se todas as ocorrências da carta e transformar-se na carta X , uma mensagem de texto cifrado contendo numerosas instâncias da carta X sugeriria a um criptanalista que X representa e .

O uso básico da análise de frequência é primeiro contar a frequência das letras do texto cifrado e então associar as letras do texto simples adivinhadas a elas. Mais X s no texto cifrado do que qualquer outra coisa sugere que X corresponde a e no texto simples, mas isso não é certo; t e uma também são muito comuns em inglês, então X pode ser qualquer um deles também. É improvável que seja um texto simples z ou q que são menos comuns. Assim, o criptanalista pode precisar tentar várias combinações de mapeamentos entre o texto cifrado e as letras do texto simples.

Um uso mais complexo de estatísticas pode ser concebido, como considerar contagens de pares de letras ( bigramas ), trigêmeos ( trigramas ) e assim por diante. Isso é feito para fornecer mais informações ao criptanalista, por exemplo, Q e você quase sempre ocorrem juntos nessa ordem em inglês, embora Q em si é raro.

Um exemplo

Suponha que Eva tenha interceptado o criptograma abaixo e seja conhecido por ser criptografado usando uma cifra de substituição simples da seguinte maneira:

LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM
WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ
GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV
IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE
PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP
XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX

Para este exemplo, letras maiúsculas são usadas para denotar texto cifrado, letras minúsculas são usadas para denotar texto simples (ou suposições), e X ~ t é usado para expressar uma suposição de que a letra do texto cifrado X representa a letra do texto simples t .

Eve poderia usar a análise de frequência para ajudar a resolver a mensagem ao longo das seguintes linhas: a contagem das letras no criptograma mostra que Eu é a letra mais comum, XL bigrama mais comum , e XLI é o trigrama mais comum . e é a letra mais comum no idioma inglês, º é o bigrama mais comum, e a é o trigrama mais comum. Isso sugere fortemente que X ~ t , eu ~ h e Eu ~ e . A segunda letra mais comum no criptograma é E ; desde a primeira e a segunda letras mais frequentes da língua inglesa, e e t são contabilizados, Eve adivinha que E ~ uma , a terceira letra mais frequente. Fazendo essas suposições provisoriamente, a seguinte mensagem parcialmente descriptografada é obtida.

heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM
WQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJ
GSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV
eZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMtha
PPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPP
thMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMt

Usando essas suposições iniciais, Eva pode identificar padrões que confirmam suas escolhas, como " este ". Além disso, outros padrões sugerem mais suposições." Rtate " pode ser " Estado ", o que significaria R ~ s . Similarmente " atthattMZe "poderia ser adivinhado como" naquela hora ", produzindo M ~ Eu e Z ~ m . Além disso, " heVe " pode ser " aqui ", dando V ~ r . Preenchendo essas suposições, Eva obtém:

hereTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGasei
WQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJ
GSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtr
emitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQitha
PPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPP
thiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYit

Por sua vez, essas suposições sugerem ainda outras (por exemplo, " remarA " poderia ser " observação ", implicando UMA ~ k ) e assim por diante, e é relativamente simples deduzir o restante das letras, resultando no texto simples.

hereuponlegrandarosewithagraveandstatelyairandbroughtmethebeetlefromaglasscasei
nwhichitwasencloseditwasabeautifulscarabaeusandatthattimeunknowntonaturalistsof
courseagreatprizeinascientificpointofviewthereweretworoundblackspotsnearoneextr
emityofthebackandalongoneneartheotherthescaleswereexceedinglyhardandglossywitha
lltheappearanceofburnishedgoldtheweightoftheinsectwasveryremarkableandtakingall
thingsintoconsiderationicouldhardlyblamejupiterforhisopinionrespectingit

Nesse ponto, seria uma boa ideia Eva inserir espaços e pontuação:

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.

Neste exemplo de The Gold-Bug , as suposições de Eve estavam todas corretas. No entanto, nem sempre seria esse o caso; a variação nas estatísticas para textos simples individuais pode significar que as suposições iniciais estão incorretas. Pode ser necessário retroceder suposições incorretas ou analisar as estatísticas disponíveis com muito mais profundidade do que as justificativas um tanto simplificadas fornecidas no exemplo acima.

Também é possível que o texto simples não exiba a distribuição esperada de frequências de letras. Mensagens mais curtas tendem a mostrar mais variação. Também é possível construir textos distorcidos artificialmente. Por exemplo, romances inteiros foram escritos que omitem a letra " e "completamente - uma forma de literatura conhecida como lipograma .

História e uso

Primeira página do Manuscrito do século IX de Al-Kindi sobre como decifrar mensagens criptográficas
Distribuição de freqüência de letras árabes .

A primeira explicação conhecida registrada da análise de frequência (na verdade, de qualquer tipo de criptoanálise) foi dada no século 9 por Al-Kindi , um polímata árabe , em A Manuscript on Deciphering Cryptographic Messages . Foi sugerido que um estudo textual detalhado do Alcorão trouxe à luz pela primeira vez que o árabe tem uma freqüência de letras característica. Seu uso se espalhou e sistemas semelhantes foram amplamente usados ​​nos estados europeus na época do Renascimento . Em 1474, Cicco Simonetta havia escrito um manual sobre como decifrar criptografias de textos em latim e italiano .

Vários esquemas foram inventados por criptógrafos para derrotar essa fraqueza nas criptografias de substituição simples. Estes incluíam:

Uma desvantagem de todas essas tentativas de derrotar os ataques de contagem de frequência é que isso aumenta a complicação tanto da codificação quanto da decifração, levando a erros. Notoriamente, um Ministro do Exterior britânico disse ter rejeitado a cifra Playfair porque, mesmo que os meninos da escola pudessem lidar com sucesso como Wheatstone e Playfair mostraram, "nossos adidos nunca poderiam aprender!".

As máquinas de rotor da primeira metade do século 20 (por exemplo, a máquina Enigma ) eram essencialmente imunes à análise direta de frequência. No entanto, outros tipos de análise ("ataques") decodificaram com sucesso as mensagens de algumas dessas máquinas.

Frequências de letras em espanhol.

A análise de frequência requer apenas uma compreensão básica das estatísticas da linguagem do texto simples e algumas habilidades de resolução de problemas e, se realizada manualmente, tolerância para a contabilidade extensa de cartas. Durante a Segunda Guerra Mundial (WWII), tanto os britânicos quanto os americanos recrutaram decifradores colocando palavras cruzadas nos principais jornais e realizando concursos para resolvê-los mais rápido. Várias das cifras usadas pelas potências do Eixo eram quebráveis ​​usando a análise de frequência, por exemplo, algumas das cifras consulares usadas pelos japoneses. Os métodos mecânicos de contagem de letras e análise estatística (geralmente máquinas do tipo cartão IBM ) foram usados ​​pela primeira vez na Segunda Guerra Mundial, possivelmente pelo SIS do Exército dos EUA . Hoje, o árduo trabalho de contagem e análise de cartas foi substituído por um software de computador , que pode realizar essa análise em segundos. Com o poder da computação moderna, é improvável que as cifras clássicas forneçam qualquer proteção real para dados confidenciais.

Análise de frequência na ficção

Parte do criptograma em The Dancing Men

A análise de frequência foi descrita na ficção. " The Gold-Bug ", de Edgar Allan Poe , e " The Adventure of the Dancing Men ", de Sir Arthur Conan Doyle, de Sherlock Holmes, são exemplos de histórias que descrevem o uso da análise de frequência para atacar cifras de substituição simples. A cifra na história de Poe está incrustada com várias medidas de engano, mas este é mais um dispositivo literário do que qualquer coisa significativa criptograficamente.

Veja também

Leitura adicional

  • Helen Fouché Gaines, "Cryptanalysis", 1939, Dover. ISBN   0-486-20097-3
  • Abraham Sinkov , "Elementary Cryptanalysis: A Mathematical Approach", The Mathematical Association of America, 1966. ISBN   0-88385-622-0 .

Referências

  1. ^ Singh, Simon . "A Câmara Negra: Dicas e Sugestões" . Página visitada em 26 de outubro de 2010 .
  2. ^ "Um exemplo prático do método de Bill's" A security site.com " " . Arquivado do original em 20/10/2013 . Página visitada em 2012-12-31 .
  3. ^ Ibrahim A. Al-Kadi "As origens da criptologia: as contribuições árabes", Cryptologia , 16 (2) (abril de 1992) pp. 97–126.
  4. ^ "In Our Time: Cryptography" . BBC Radio 4 . Página visitada em 29 de abril de 2012 .
  5. ^ Kahn, David L. (1996). Os decifradores: a história da escrita secreta . Nova York: Scribner. ISBN   0-684-83130-9 .

links externos