Dešifrovaný Zimmermann Telegram .
Cryptoanalysis
Dešifrování (od řeckých kryptós , "skrytý", a analýein , "uvolnit" nebo "uvolnit") je umění a věda o analýzuinformačních systémů , aby mohl studovat skryté aspekty systémů.[ 1 ] Dešifrování se používá porazitkryptografických bezpečnostní systémy a získat přístup k obsahu šifrovaných zpráv, i když šifrovací klíč je neznámý.
Kromě matematické analýzy kryptografických algoritmů, dešifrování také zahrnuje studii o boční kanál útoky , které necílí nedostatky v kryptografických algoritmů samotných, ale místo toho využívají slabých míst v jejich provádění.
I když cílem bylo stejný, metody a techniky dešifrování měnili se drasticky přes minulost kryptografie, přizpůsobovat se rostoucí cryptographic složitosti, sahat od pera-a-tapetovat metody minulosti, přes stroje jako Bombes a Colossus počítače v Bletchley Parku v druhé světové válce , na matematicky pokročilé počítačové systémy současnosti. Metody na lámání moderní kryptografickéčasto zahrnují řešení pečlivě vystavěný problémy v čisté matematice , best-known být faktorizace celého čísla .
Vzhledem k tomu, některé šifrovaná data ( "ciphertext" ), cílem cryptanalyst je získat co možná nejvíce informací o původní, nešifrovaná data ( "plaintext" ).
Útoky mohou být klasifikovány podle toho, jaký typ informací má útočník k dispozici. Jako základní východisko to je normálně předpokládal, že pro účely analýzy, obecné algoritmus je znám, to je Shannon Maxim "nepřítel zná systém" - podle jeho pořadí, což odpovídá zásadě Kerckhoffs " . To je rozumný předpoklad v praxi - v průběhu dějin, existuje nespočet příkladů tajných algoritmů spadající do širších znalostí, různě přes špionáž , zradu a reverzní inženýrství . (A příležitostně, kódy byly rekonstruované přes čisté odečtení, například německý Lorenz šifru a japonské Purple kód , a paleta klasických schémat). [ 2 ] :
Ciphertext pouze : cryptanalyst má přístup pouze ke sbírce ciphertextsnebo codetexts .
Známý-holý : útočník má soubor ciphertexts, na které je mu známo, odpovídající otevřený text .
Zvolený-plaintext ( volený-ciphertext ): útočník může získat ciphertexts (holé), což odpovídá libovolný soubor holé (ciphertexts) podle vlastního výběru.
Adaptivní volený-holý : jako volený-útok holého textu, může kromě útočníka vybrat následné holé na základě informací získaných během předchozích šifrování. Podobně Adaptivní zvolen ciphertext zaútočí .
Související-key útok : Jako volený-útok holého textu, může kromě útočníka získat ciphertexts šifrovány pod dvěma různými klíči. Klíče jsou neznámé, ale vztah mezi nimi je známý, například, dva klíče, které se liší v jednom bitu.
Útoky mohou také být charakterizovány zdroje, které vyžadují. Tyto zdroje zahrnují: [ pochvalná zmínka potřebovaný ]
Čas - počet výpočetních kroků (jako šifrování), které se musí provádět.
Paměť - množství skladování vyžaduje provedení útoku.
Data - množství holé a ciphertexts požadovaných.
Je to někdy těžké předvídat tyto množství přesně, zvláště když útok není praktické skutečně provádět pro testování. Ale akademické cryptanalysts mají tendenci poskytovat alespoň odhad řádově obtížnosti jejich útoků ", řekl, například," SHA-1 kolize nyní 2 52 . " [ 3 ]
Bruce Schneier konstatuje, že i výpočetně nepraktické útoky mohou být považovány za přerušení: "Breaking šifru jednoduše znamená najít slabinu v kódu, které lze využít se složitostí méně než hrubá síla Nevadí to hovado-síla by mohla vyžadovat 2. 128 šifrování; útok vyžaduje 2 110 šifrování by bylo považováno za přestávku ... jednoduše řečeno, může být jen přestávka certificational slabost:. důkaz, že kód nehraje jak inzeroval " [ 4 ]
Výsledky dešifrování mohou také se lišit v užitečnosti. Například, kryptografLars Knudsen (1998) klasifikován různé druhy útoku na blokové šifry podle množství a kvality utajovaných informací, které bylo objeveno:
Celkem přestávka - útočník odvodí tajný klíč .
Globální dedukce - útočník objeví funkčně ekvivalentní algoritmus pro šifrování a dešifrování, ale bez znalosti klíče.
Instance (místní) dedukce - útočník objeví další holé (nebo ciphertexts) dříve známé.
Informace o odpočet - útočník získá nějakou Shannon informace o holé (nebo ciphertexts) dříve známých.
Rozlišovací algoritmus - útočník může rozlišit šifru z náhodné permutace .
Akademické útoky jsou často proti oslabeným verzemi kryptografický, jako je blokové šifry nebo hash funkce s některými odstraněny kolech. Mnoho, ale ne všechny, útoky se exponenciálně obtížnější provést jako kola jsou přidány do kryptografický, [ 5 ] , takže je možné, aby plně šifrovací být silný, i když se sníženým kulaté varianty jsou slabé. Nicméně, může dílčí přestávky, které přicházejí v blízkosti rozbití původní šifrovací znamená, že úplné přerušení bude následovat, úspěšné útoky na DES , MD5 , a SHA-1 byly všechny předcházelo útoky na oslabené verzi.
V akademickém kryptografii, slabost nebo přerušení je v systému obvykle definován docela konzervativně: to by mohlo vyžadovat nepraktické množství času, paměť nebo známé holé texty. To také může vyžadovat být útočník schopen dělat věci, mnoho z reálného světa útočníci nemohou: například, může být útočník potřeba vybrat konkrétní holé být šifrována, nebo dokonce požádat o holé být zašifrován pomocí několika tlačítek týkajících se tajemství klíč.Navíc, to by mohlo odhalit pouze malé množství informací, stačí dokázat, že šifrovací nedokonalé, ale příliš málo, aby byly užitečné v reálném světě útočníků. Konečně, může útok vztahovat pouze na oslabené verzi kryptografických nástrojů, jako sníženou kulaté blokové šifry, jako krok k rozbití celého systému. [ 4 ]
Hlavní článek: Historie kryptografie
Dešifrování se coevolved spolu s kryptografií, a zápas může být stopován přes historii kryptografie -nových šifer je určeny k nahrazení staré zlomené designy a nové cryptanalytic techniky vynalezené k prasklině zdokonalené systémy. V praxi, oni jsou viděni jako dvě strany téže mince: aby vytvořil bezpečnou kryptografii, vy máte k designu proti možnému dešifrování.[ pochvalná zmínka potřebovaný ]
Úspěšné dešifrování nepochybně ovlivnil historii, schopnost číst předpokládal-tajné myšlenky a plány jiných mohou být rozhodující výhodou. Například, v Anglii v roce 1587, Marie, královna Skotů byl souzen a popraven za zradu na své účasti ve třech pozemcích zavraždit Elizabeth já Anglie , které byly známy, protože její kódování korespondence s spoluspiklenci byl dešifrován Phelippes Thomas .
V první světové válce , lámání Telegram Zimmermann byl pomocný v přinášení Spojené státy do války. V druhé světové válce , se spojenci těžili enormně od jejich společného úspěšnosti dešifrování německých šifer - včetně Enigma aLorenz šifře - a japonských šifer, zejména "Purple" a JN-25 . "Ultra" má inteligenci byl připočítán se vším mezi zkracovat konec evropské války až do dvou let, aby určení eventuálního výsledku. Válka v Pacifiku byla podobně pomohl "magic" inteligence. [ 6 ]
Vlády dlouho rozpoznaly potenciální výhody dešifrování pro inteligenci , jak vojenské a diplomatické, a založil oddané organizace oddané rozluštění kódů a kódy jiných národů, například, GCHQ a NSA , organizace, které jsou stále velmi aktivní dnes. V roce 2004, to bylo hlásil, že Spojené státy se členííránské šifry. (To je neznámo, nicméně, zda toto bylo čisté dešifrování, nebo zda jiné faktory byly zahrnovány: [ 7 ] ).
Viz také: Frekvenční analýza ,index koincidence , a Kasiski vyšetření
Ačkoli aktuální slovo "kryptoanalýza "je relativně nedávný (to bylo vytvořeno William Friedmanv roce 1920), metody pro prolomeníkódů a šifry jsou mnohem starší.První známý zaznamenaný vysvětlení dešifrování bylo dáno 9. století arabský polymath , Al-Kindi(také známý jako "Alkindus" v Evropě), v Rukopis na rozluštění Cryptographic zpráv . Toto pojednání zahrnuje popis metody analýzy frekvence ( Ibrahim Al-Kadi , 1992 - ref-3). Italská učenec Giambattista della Porta byl autor seminární práci na dešifrování . "De Furtivis Literarum Notis" [ 8 ]
Frekvenční analýza je základním nástrojem pro porušení většinu klasických šifer . V přirozených jazycích, jisté dopisy abecedy objevují častěji než jiné, vangličtině , " E "je pravděpodobně nejvíce obyčejný dopis v nějakém vzorkuprostého textu . Podobně, digraph "TH" je nejvíce pravděpodobný pár dopisů v angličtině, a tak dále. Frekvenční analýza spoléhá na nedostatek kódu skrýt tyto statistiky . Například, v jednoduchém substitučním kódu (kde každý dopis je prostě nahradit jiným), nejčastější dopis v ciphertext by pravděpodobně kandidátem "E". Frekvenční analýza takového kódu je tedy poměrně snadné, za předpokladu, že šifrový text je dost dlouho na to, aby rozumně reprezentativní počet písmen v abecedě, které obsahuje. [ 9 ]
V Evropě během 15. a 16. století, myšlenka polyalphabetic substituční šifryvyvinul, mimo jiné francouzský diplomat Blaise de Vigenère (1523-1596). [ 10 ] U některých tři staletí, Vigenère kód , který používá opakující se Klíčem k výběru různých šifrovacích abeced v rotaci, byl považován za zcela bezpečný ( Le Chiffre indéchiffrable - "nerozluštitelný šifra"). Nicméně, Charles Babbage , (1791-1871) a později nezávisle, Friedrich Kasiski (1805-1881) podařilo prolomit tuto šifru. [ 11 ] Během světové války já , vynálezci v několika zemích vyvinulrotoru šifrovací stroje , jako je Arthur Scherbius " Enigma , ve snaze minimalizovat opakování, které bylo využito k přerušení Vigenère systému. [ 12 ]
Viz také: Dešifrování hádanky a dešifrování se Lorenz šifry
Dešifrování nepřátelských zpráv hrál významnou roli v Allied vítězství ve druhé světové válce. FW Winterbottomová , citoval západní nejvyšší spojenecký velitel, Dwight D. Eisenhower , na konci války jako popis Ultra inteligenci jak mít been "rozhodující" k vítězství Spojenců. [ 13 ] Sir Harry Hinsley , oficiální historik britské rozvědky v druhé světové válce, se dopustil podobné posouzení o Ultra, pověst, že to zkrátil válku "o ne méně než dva roky, a pravděpodobně o čtyři roky", navíc, řekl, že v absence Ultra, to je nejisté jak válka by skončila.[ 14 ]
V praxi, frekvenční analýza spoléhá jak hodně na jazykové znalosti, jak to dělá na statistikách, ale jak kódy se staly více komplexem, matematika stal se více důležitý v dešifrování. Tato změna byla zvláště evidentní již před a během druhé světové války , kde úsilí rozlousknout Axis kódy vyžadovala nové úrovně matematického sophistication. Navíc, automatizace byla nejprve aplikován na dešifrování se v té době s polským Bomba zařízení, British Bombe , používáníděrovaného karty zařízení, a v Colossus počítače -. první elektronické digitální počítače je možné ovládat pomocí programu [ 15 ] [ 16 ]
Viz také: Enigma machine: Indikátor
S vzájemných stroje šifer jako Lorenz šifry a hádanky stroje používanénacistickým Německem během druhé světové války , každá zpráva měla svůj vlastní klíč. Obvykle, přenos provozovatel informoval přijímající operátor této zprávy klíči přenosu nějaké holý nebo šifrový text před šifrovaném zprávy. Tato látka se nazývá ukazatel , protože naznačuje, přijímající subjekt, jak nastavit svůj stroj dešifrovat zprávu. [ 17 ]
To bylo špatně navržen a realizován systém ukazatelů, které umožnily první sePoláci [ 18 ] , a poté Britové u Bletchley parku [ 19 ] rozbít Enigma šifer systému.Podobné chudé Systémy indikátorů mohou Britové identifikovat hloubky , které vedly k diagnóze Lorenz SZ40/42 šifry systému, a komplexní lámání svých zpráv bez cryptanalysts vidí cipher zařízení. [ 20 ]
Vysláním dvou nebo více zpráv se stejným klíčem je nejistá proces. Chcete-li cryptanalyst zprávy jsou pak řekl, aby byl "do hloubky" . [ 21 ] To může být detekována zpráv, které mají stejný ukazatel , kterým vysílající subjekt informuje přijímající subjekt o klíčových nastavení generátoru počátečních pro zprávy. [ 22 ]
Obecně platí, že může být cryptanalyst využívat seřazovat identické šifrováním operace mezi soubor zpráv. Například v Vernamova šifer zašifruje od bit po bitu kombinování prostý text s dlouhým klíčem pomocí " exkluzivní nebo "operátor, který je také známý jako" modulo-2 navíc "(symbolizovaný ⊕):
Plaintext ⊕ Key = Šifrový
Rozluštění spojuje stejné bity klíče s ciphertext rekonstruovat holý text:
Šifrový ⊕ Key = Prostý text
(. Ve modulo-2 aritmetické sčítání je stejný jako snížení) Jsou-li dvě takové ciphertexts zarovnány do hloubky, kombinování eliminuje společný klíč, odcházející jen kombinaci dvou holé:
Ciphertext1 ⊕ Ciphertext2 = Plaintext1 ⊕ Plaintext2
Jednotlivé holé pak mohou být zpracovány jazykově a snaží pravděpodobné slova (nebo fráze) na různých místech; správný odhad, v kombinaci s sloučené proudu holého textu, vytváří srozumitelný text z druhé holého textu komponenty:
(Plaintext1 ⊕ Plaintext2) ⊕ Plaintext1 = Plaintext2
Zpět fragment druhého otevřeného textu mohou často být prodloužena v jednom nebo obou směrech, a další znaky mohou být kombinovány s sloučené holého proudu k rozšíření první holý. Práce tam a zpět mezi dvěma holé, pomocí srozumitelnost kritéria pro kontrolu odhady, může analytik obnovit hodně nebo všechny původní holé. (S pouhými dvěma holé do hloubky, může analytik neví, který z nich odpovídá, na které ciphertext, ale v praxi to není velký problém.) Pokud je obnoven holý pak v kombinaci s jeho ciphertext, je odhalen klíč:
Plaintext1 ⊕ Ciphertext1 = klíč
Znalost klíče samozřejmě umožňuje analytik číst další zprávy šifrované se stejným klíčem, a znalosti ze souboru souvisejících klíčů může dovolit cryptanalysts diagnostikovat systém používaný pro výstavbu je. [ 23 ]
I když byl výpočet zvyklý na velký efekt v dešifrování na Lorenz šifry a jiných systémů během druhé světové války, je také možné nové metody kryptografie řádů složitější než kdy předtím. Jako celek, moderní kryptografie je mnohem více odolný proti dešifrování než pero-a-tapetovat systémy minulosti, a nyní se zdá, že má navrch proti čistému dešifrování.[ pochvalná zmínka potřebovaný ]Historik David Kahn poznámky:
"Mnoho jsou kryptografické nabídnuty stovkami komerčních prodavačů dnes, které nemohou být rozděleny nějakými známými metodami dešifrování. Ve skutečnosti v takových systémech i volený holý útok , ve kterém je vybrán holý uzavřeno proti jeho ciphertext, nemůže přinést klíč že unlock [s] další zprávy V tomto smyslu, pak, dešifrování je mrtvé, ale to není konec příběhu Dešifrování může být mrtvé, ale tam je -... míchat mé metafory - víc než jeden způsob, jak stáhnout kočku . ". [ 24 ]
Kahn pokračuje se zmínit o více příležitostí k odposlechu, odposlouchávání ,útokům postranního kanálu , a kvantové počítače jako náhrada za tradiční prostředky k dešifrování. V roce 2010, bývalý technický ředitel NSA Brian Snow řekl, že jak akademických a vládních cryptographers jsou "velmi pomalu vpřed v vyzrálém poli." [ 25 ]
Nicméně, může být jakékoliv pitev pro dešifrování bylo předčasné. Zatímco účinnost kryptoanalytických metod použitých zpravodajských agentur zůstává neznámý, mnoho závažných útoků proti akademických i praktických kryptografických primitivů byla zveřejněna v moderní éře počítačové kryptografie: [ pochvalná zmínka potřebovaný ]
Bloková šifra Madryga , navržené v roce 1984, ale ne široce použitý, bylo zjištěno, že je citlivý na ciphertext-jediné útoky v roce 1998.
FEAL-4 , navržena jako náhrada za DES standardní šifrovací algoritmus, ale ne široce použitý, byl zničen spoustou útoků od akademické obce, z nichž mnohé jsou zcela praktické.
A5 / 1 , A5 / 2 , RVHP , a DECT systémy používané v mobilních a bezdrátových telefonů mohou všichni být rozděleny v hodinách, minutách nebo dokonce v reálném čase pomocí běžně dostupné počítačové vybavení.
Brute-force keyspace vyhledávání porušil některé reálné šifry a aplikace, včetně jednoho-DES (viz ERF DES cracker ), 40-bit "export-pevnosti" kryptografie , a obsah DVD Scrambling System .
V roce 2001, Wired Equivalent Privacy (WEP), protokol používaný k zajištění Wi-Fi bezdrátové sítě byla, ukazuje se rozlomit na praxi z důvodu slabosti v RC4 šifry a aspektů WEP designu, který z spřízněnými útoky klíče praktické. WEP byl později nahrazen Wi-Fi Protected Access .
V roce 2008, výzkumníci provedli proof-of-concept přestávku SSL pomocí slabých míst v MD5 hash funkce a postupy vystavitele certifikátu, která to umožňuje využívat kolize na hašovací funkce. Osvědčení Emitenti zapojit změnily své praktiky, aby se zabránilo útoku z opakování.
Tak, zatímco nejlepší moderní šifry mohou být daleko více odolný proti dešifrování než Enigma , dešifrování a širší oblasti informační bezpečnostizůstávají poměrně aktivní. [ pochvalná zmínka potřebovaný ]
![[Ikona]](http://en.wikipedia.org/wiki/File:Wiki_letter_w_cropped.svg){kind=small} | Tato část vyžaduje rozšíření . (duben 2012) |
Asymetrická kryptografie (nebo kryptografie veřejného klíče ) je kryptografie, která se spoléhá na používání dva klíče, jeden soukromý, a jedna veřejná.Takové kódy trvale spoléhají na "tvrdé" matematických problémů jako východisko pro jejich bezpečnost, tak zřejmý bod útoku je vyvinout metody pro vyřešení problému. Bezpečnost dva-kryptografie klíče závisí na matematických otázkách tak, aby jeden-klíčová kryptografie obecně dělá ne, a naopak spojí dešifrování se širším matematickým výzkumem v novým způsobem.[ pochvalná zmínka potřebovaný ]
Asymetrická schémata jsou navrženy kolem (tušené) obtíže vyřešení různých matematických problémů. Pokud zlepšený algoritmus může být najit řešit problém, pak systém je oslaben. Například, bezpečnost Diffie-Hellman klíčová výměna systému závisí na obtížnosti výpočtu diskrétního logaritmu . V roce 1983, Don Coppersmith našel rychlejší způsob, jak najít jednotlivé logaritmy (v jistých skupinách), a požaduje cryptographers používat větší skupiny (nebo různé druhy skupin). RSA bezpečnost závisí (z části) na obtížnosti faktorizace celého čísla - průlom v factoring by ovlivnil bezpečnost RSA.[ pochvalná zmínka potřebovaný ]
V roce 1980, jeden mohl by faktor těžký 50-číslo číslice na úkor 10 12 základní počítačové operace. V roce 1984 stav umění v factoring algoritmy postoupila do bodu, kdy 75-místné číslo mohlo být factored v 10 12 operací. Pokroky v počítačové technologii také znamenalo, že operace by mohla být provedena mnohem rychleji, taky. Mooreův zákon předpovídá, že rychlosti počítače budou nadále zvyšovat. Factoring techniky mohou tak činit i nadále stejně, ale bude s největší pravděpodobností záviset na matematickém nahlédnutí a kreativitě, z nichž ani jeden nebyl nikdy úspěšně předvídatelný. 150-místná čísla druhu jednou používala v RSA byli factored. Úsilí bylo větší než nahoře, ale byl ne nesmyslný na rychlých moderních počítačích. Do začátku 21. století, 150-čísla číslice byla již za dostatečně velká velikost klíče pro RSA. Čísla s několik sto číslic byly stále považovány za příliš těžko k faktoru v roce 2005, i když metody budou pravděpodobně i nadále zlepšovat v průběhu času, vyžadovat velikost klíče držet krok nebo jiné metody, jako eliptických křivek kryptografiekteré mají být použity. [ pochvalná zmínka potřebovaný ]
Další charakteristický rys asymetrických schémat je to, na rozdíl od útoků na kryptografické systémy symmetric, každý dešifrování má možnost využívat znalostí získaných z veřejného klíče . [ pochvalná zmínka potřebovaný ]
| Tato část vyžaduje rozšíření . (duben 2012) |
Hlavní článek: Side channel attack
| Tato část vyžaduje rozšíření . (duben 2012) |
Kvantové počítače , které jsou stále v počátečních fázích výzkumu, mají potenciální použití v dešifrování. Například, Shorův algoritmus by zohledňovat velké množství v polynomiálním čase , v podstatě poškádlit běžně používané formy veřejného klíče šifrování. [ pochvalná zmínka potřebovaný ]
Pomocí Grover je algoritmus na kvantovém počítači, můžete brute-force klíč vyhledat být kvadraticky rychleji. To by však mohlo být zvrácen zdvojnásobením délku klíče. [ pochvalná zmínka potřebovaný ]
Informační bezpečnost , Zastřešujícím cílem většiny kryptografie
Chyba zabezpečení ; zranitelnosti mohou obsahovat šifrovací nebo jiné nedostatky
Bezpečnostní inženýrství , design aplikací a protokolů
Informace o pojištění , termín pro informační bezpečnost je často používán ve vládě
William F. Friedman , otec moderní kryptologie
Joseph Rochefort , jejichž příspěvky ovlivnil výsledek bitvy o Midway
Giovanni Soro , renesanční první vynikající cryptanalyst
John Wallis - 17. století anglický matematik
