První strana Al-Kindi je 9. století Rukopis na rozluštění Cryptographic zpráv
Frequency analysis
Vkryptoanalýzy ,frekvenční analýza je studie ofrekvenci písmen nebo skupin dopisů vciphertext .Tato metoda se používá jako pomůcka pro rozbitíklasických šifer.
Frekvenční analýza je založena na tom, že v každém daném úseku psaného jazyka, některá písmena a kombinace písmen vyskytují s různou frekvencí. Navíc je zde charakteristické rozdělení písmen, která je zhruba stejné pro téměř všechny vzorky toho jazyka. Například, daný úsek anglického jazyka , E , T , a O jsou nejčastější, přičemž Z , Q a X jsou vzácné. Stejně tak, TH , ER , ON , a jsou nejčastější dvojice písmen (nazývanébigrams nebo digraphs ), a SS , EE , TT , a FF jsou nejčastější opakuje. [ 1 ]nesmysl Fráze " ETAOIN SHRDLU "představuje v 12 nejčastější dopisy v typickém anglického textu.
V některých šifer, jsou tyto vlastnosti přirozeného jazyka holého textu zachovány v ciphertext a tyto vzory mají potenciál být využíván v ciphertext-jediný útok .
V jednoduchém substituční šifry , každé písmeno otevřeného textu se nahrazuje jiným, a všechny zvláštní dopis v holém textu bude vždy transformován do stejného dopisu v ciphertext. Například, pokud jsou všechny výskyty písmene e přelomu do písmene X , zpráva ciphertext obsahující četné případy písmenem X by navrhnout cryptanalyst, že X představuje e .
Základní použití frekvenční analýzy je nejprve počítat frekvenci ciphertext dopisů a pak přidružit uhodnuto holého dopisy s nimi. Více X 'je v ciphertext než cokoli jiného vyplývá, že X odpovídá e v holém textu, ale toto není jisté, t , a jsou také velmi časté v angličtině, takže X může být buď z nich také. Je pravděpodobné, že by holý z nebo q , které jsou méně časté. Tak cryptanalyst muset vyzkoušet několik kombinací mapování mezi šifrového a otevřeného textu písmen.
Složitější použití statistik může být chápána, jako je s ohledem na počty dvojic znaků ( schématy ), triplety ( trigramů ), a tak dále. To se provádí, aby poskytla více informací o cryptanalyst, například, Q a U téměř vždy vyskytují společně v tomto pořadí v angličtině, i když Q sám je vzácný.
Předpokládejme, že Eva je zachytil kryptogram dole, a je známo, být zašifrován pomocí jednoduchého substituční šifru:
LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX
V tomto příkladu, jsou velká písmena slouží k označení ciphertext, malá písmena jsou používána naznačovat holý (nebo hádá na takový), a X ~ t je zvyklý na expres odhad, který ciphertext dopis X představuje písmeno holého textu t .
Eva by se použít frekvenční analýzu, aby pomohla řešit zprávu podél následujících řádků: počítá dopisů v kryptogramu ukazují, že jsem je nejčastější jedno písmeno, XL nejčastější bigram , a XLI je nejčastější trigram. e je nejčastější dopis v anglickém jazyce, th je nejčastější bigram, anejčastější trigram. To silně naznačuje, že X ~ t , L ~ h a já ~ e . Druhou nejčastější dopis v kryptogramu je E ; od první a druhé nejčastější dopisy v anglickém jazyce, e a t jsou účtovány, Eve odhady, že E ~ a , třetí nejčastější dopis. Pokusně provádění těchto předpokladů, je získán po částečné dešifrovaná zpráva.
heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM WQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJ GSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV eZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMtha PPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPP thMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMt
Pomocí těchto počátečních odhadů, může Eve místě vzory, které potvrzují její rozhodnutí, jako například " , že ". Navíc, jiné vzory navrhnou další odhady. "Rtate "může být" stát ", což by znamenalo, R ~ s. . Podobně "atthattMZe "může být uhodnout jako" atthattime ", dávat M ~ i a Z ~ m .Navíc, " heVe "může být" tady ", což V ~ r . Vyplnění těchto odhadů, Eve dostane:
hereTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGasei WQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJ GSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtr emitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQitha PPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPP thiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYit
Na druhé straně, tyto odhady naznačují, ještě jiní (např., " remarA "by mohlo být" poznámka ", z čehož vyplývá, A ~ k. ) a tak dále, a to je relativně jednoduché odvodit zbytek dopisů, nakonec dávat holý text.
hereuponlegrandarosewithagraveandstatelyairandbroughtmethebeetlefromaglasscasei nwhichitwasencloseditwasabeautifulscarabaeusandatthattimeunknowntonaturalistsof courseagreatprizeinascientificpointofviewthereweretworoundblackspotsnearoneextr emityofthebackandalongoneneartheotherthescaleswereexceedinglyhardandglossywitha lltheappearanceofburnishedgoldtheweightoftheinsectwasveryremarkableandtakingall thingsintoconsiderationicouldhardlyblamejupiterforhisopinionrespectingit
Na tomto místě by bylo dobré pro Evu vložit mezery a interpunkci:
Hereupon Legrand vznikly, s vážnou a majestátní vzduchu, a přinesl mi brouka od skleněné vitríně, ve kterém byla uzavřena se. Bylo to krásné Scarabaeus, a na že čas, neznámý přírodovědců-samozřejmě velkou cenu ve vědecké bodu pohledu. Tam byly dva kulaté černé skvrny poblíž jednom konci hřbetu a dlouhá blízko druhé. Váhy byly mimořádně tvrdé a lesklé, se všemi vzhled leštěného zlata. Hmotnost hmyzu byla velmi pozoruhodná, a, přičemž všechny věci v úvahu, mohl jsem jen stěží vyčítat Jupiter na jeho názor respektovat ji.
V tomto příkladu z The Gold-Bug , předvečera odhady byly všechny správné. To by nebylo vždy případ, nicméně; změna ve statistikách jednotlivých holé může znamenat, že počáteční odhady jsou nesprávné. To může být nutné, abyBacktrack nesprávných pokusů nebo analyzovat dostupné statistiky v mnohem větší hloubky, než je poněkud zjednodušené vysvětlení podaných ve výše uvedeném příkladu.
Je také možné, že otevřený text nevykazuje očekávanou distribuci poštovních frekvencí. Kratší zprávy jsou pravděpodobně ukazují více variace. Je také možné vytvořit uměle šikmý texty. Například, celé romány byly psané, že vynecháte písmeno " e "úplně - forma literatury známé jako lipogram .
První známý zaznamenaný vysvětlení frekvenční analýzy (opravdu, nějakého druhu dešifrování) byl uveden v 9. stoletíAl-Kindi , Arab polyhistora , vRukopis na rozluštění Cryptographic zpráv . [ 2 ] To bylo navrhl, že blízko textové studium Koránu první přinesl na světlo, že arabština má charakteristický dopis kmitočtu [ 3 ]. Jeho použití šíření, a podobné systémy byly široce používány v evropských státech v doběrenesance . Od 1474 Cicco Simonetta napsal návod na rozluštění šifrování z latinského aitalské znění. [ 4 ] Arabic Dopis Frekvence a podrobné studium dopisu a slovní frekvenční analýza celého knihy Koránu jsou poskytovány články Intellaren .[ 5 ]
Několik schémat byly vynalezeny cryptographers porazit tuto slabinu jednoduchých substitučních šifrování. Patří mezi ně:
Použití homofona - několik alternativ na nejčastější písmena v jinak monoalphabetic substitučních šifer (např. pro angličtinu, mohli oba X a Y ciphertext znamená plaintext E).
Polyalphabetic substituční , to znamená, že použití několika abeced - volený v nejrůznějších, více či méně křivolaký, cesty ( Leone Alberti Zdá se, že jako první navrhnout to), a
Polygrafické substituce , schémata, kde jsou páry nebo triplets dopisů holého léčených jako jednotky pro náhradu, spíše než jednoduchá písmena (například, Playfair kód vynalezl Charles Wheatstone v polovině 19. století).
Nevýhodou všech těchto pokusů porazit útoky frekvenční počítání je to, že se zvyšuje komplikace jak zašifrovat a dekódování, což vede k chybám. Skvěle, je britský ministr zahraničí řekl, aby odmítli Playfair kód, protože i když školáci mohli vypořádat úspěšně jako Wheatstone a Playfair se ukázal, "naše atašé by nikdy se to naučit!".
Tyto rotorové stroje z první poloviny 20. století (např. stroj hádanky ) byly v podstatě imunní na prostou frekvenční analýzy. Nicméně, jiné druhy analýzy ("útoky") úspěšně dekódovány zprávy z některé z těchto strojů.
Frekvenční analýza vyžaduje pouze základní znalosti ze statistiky jazyka holého textu a některé řešení problémů, dovednosti, a pokud se provádí ručně, někteří tolerance pro rozsáhlé písmeno účetnictví. Běhemdruhé světové války (WWII), jakbritské a Američané přijati codebreakers tím křížovky puzzle v hlavních novinách a běží soutěže o to, kdo by mohl vyřešit jim nejrychlejší. Několik šifry, kterémocností Osy byly rozbitné pomocí frekvenční analýzy (například, některé z šifer konzulárních používaných japonštině). Mechanické metody počítání dopisu a statistické analýzy (obecně IBM karta typu stroje) byly poprvé použity v druhé světové válce, případně americké armády SIS . Dnes je tvrdá práce dopisu počítání a analýzy byly nahrazeny počítačového softwaru , který může provádět takovou analýzu v sekundách. Díky moderní výpočetní výkon, klasické šifry jsou nepravděpodobné poskytovat nějakou skutečnou ochranu důvěrných údajů.
Frekvenční analýza byla popsána v beletrii. Edgar Allan Poe 's " Gold-Bug ", a sira Arthura Conana DoyleaSherlock Holmes příběh "Dobrodružství mužů tančení "jsou příklady příběhů, které popisují použití frekvenční analýzy k útoku jednoduché substituční šifry. Šifra v příběhu Poea je pokrytý několika úskoky opatření, ale to je více literární zařízení než něco významné kryptograficky.
