Kryptoanalýza

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 11. prosince 2021; kontroly vyžadují 2 úpravy .

Kryptoanalýza (z jiného řeckého κρυπτός „skrytý“ + „ analýza “) je věda o metodách dešifrování zašifrovaných informací bez klíče k tomu určeného , stejně jako o samotném procesu takového dešifrování.

Ve většině případů kryptoanalýza znamená zjištění klíče; kryptoanalýza také zahrnuje metody pro odhalování zranitelnosti kryptografických algoritmů nebo protokolů .

Pokus prolomit konkrétní šifru pomocí metod kryptoanalýzy se nazývá kryptografický útok na tuto šifru. Kryptografický útok, který prolomí šifru, se nazývá „crack“ nebo „crack“ šifry.

Termín zavedl americký kryptograf William F. Friedman v roce 1920 jako součást své knihy The Elements of Cryptanalysis [1] .

Zpočátku byly metody kryptoanalýzy založeny na jazykových vzorcích přirozeného textu a byly implementovány pouze pomocí tužky a papíru. Postupem času roste v kryptoanalýze role čistě matematických metod, k jejichž implementaci se využívají specializované kryptoanalytické počítače .

Historie kryptoanalýzy

Kryptoanalýza se vyvíjela spolu s rozvojem kryptografie: nové, pokročilejší šifry nahradily již prolomené kódovací systémy pouze pro kryptoanalytiky, aby vynalezli sofistikovanější metody pro prolomení šifrovacích systémů. Pojmy kryptografie a kryptoanalýza jsou neoddělitelně propojeny: pro vytvoření systému odolného proti hackingu je nutné vzít v úvahu všechny možné způsoby jeho napadení.

Klasická kryptoanalýza

Přestože koncept kryptoanalýzy byl zaveden relativně nedávno, některé metody hackování byly vynalezeny před desítkami století. První známá písemná zmínka o kryptoanalýze je „ Rukopis o dešifrování kryptografických zpráv “, který napsal arabský vědec Al-Kindi již v 9. století. Tato vědecká práce obsahuje popis metody frekvenční analýzy .

Frekvenční analýza je hlavním nástrojem pro prolomení většiny klasických permutačních nebo substitučních šifer. Tato metoda je založena na předpokladu existence netriviálního statistického rozložení symbolů a také jejich sekvencí, a to jak v otevřeném, tak v šifrovém textu. Navíc bude tato distribuce zachována až do nahrazení znaků jak v procesu šifrování, tak v procesu dešifrování. Stojí za zmínku, že za podmínky dostatečně velké délky zašifrované zprávy jsou monoalfabetické šifry snadno přístupné frekvenční analýze: pokud frekvence výskytu písmene v jazyce a frekvence výskytu určitého znaku přítomné v šifrovém textu jsou přibližně stejné, pak v tomto případě lze s vysokou mírou pravděpodobnosti předpokládat, že tento znak a bude stejné písmeno. Nejjednodušším příkladem frekvenční analýzy by bylo jednoduše spočítat počet každého z nalezených znaků, poté následovat postup vydělení výsledného počtu znaků počtem všech znaků v textu a vynásobení výsledku stem. konečná odpověď v procentech. Dále jsou získané procentuální hodnoty porovnány s tabulkou pravděpodobnostního rozložení písmen pro předpokládaný původní jazyk.

Během období 15.-16. století byly v Evropě vytvořeny a vyvinuty polyalfabetické substituční šifry . Nejznámější je šifra francouzského diplomata Blaise de Vigenère, která byla založena na použití sekvence několika Caesarových šifer s různými hodnotami posunu. Po tři staletí byla Vigenèrova šifra považována za zcela kryptograficky stabilní, dokud v roce 1863 Friedrich Kasiski nenavrhl vlastní metodu prolomení této šifry. Hlavní myšlenka metody Kasiska je následující: pokud je v prostém textu mezi dvěma identickými znakovými sadami takový blok textu, že jeho délka je násobkem délky klíčového slova, pak tyto identické sady prostého textu znaky během šifrování přejdou do stejných segmentů šifrovaného textu. V praxi to znamená, že pokud jsou v šifrovém textu shodné segmenty tří a více znaků, je vysoká pravděpodobnost, že tyto segmenty odpovídají stejným segmentům otevřeného textu. Jak se aplikuje metoda Kasiska: v šifrovém textu se hledají dvojice identických segmentů o délce tři nebo více, poté se vypočítá vzdálenost mezi nimi, tedy počet znaků, které oddělují počáteční pozice spárovaných segmentů. Jako výsledek analýzy všech dvojic identických segmentů dostaneme množinu vzdáleností d 1 , d 2 , d 3 , ... Délka klíčového slova bude dělitel pro každou ze vzdáleností, a proto pro jejich největšího společného dělitele.

Další etapa ve vývoji kryptoanalýzy je spojena s vynálezem rotačních šifrovacích strojů, jako je například Enigma , kterou vynalezl Arthur Scherbius . Účelem takových zařízení bylo minimalizovat počet opakujících se segmentů šifrového textu, jejichž statistiky výskytu byly použity k prolomení Vigenèrovy šifry. Polským kryptoanalytikům se podařilo postavit prototyp dešifrovacího stroje pro verzi Enigmy používanou nacistickým Německem . Stroj dostal název „ Bomba “ za to, že během provozu vydával zvuky podobné tikání hodin. Později byl dokončen a přijat anglickými kryptoanalytiky.

Moderní kryptoanalýza

S rozvojem nových šifrovacích metod se matematika stávala stále důležitější. Takže například při frekvenční analýze musí mít kryptoanalytik znalosti jak lingvistiky, tak statistiky. Zatímco teoretické práce na kryptoanalýze Enigmy prováděli převážně matematici, jako je Alan Mathison Turing . Přesto díky stejné matematice dosáhla kryptografie takového rozvoje, že počet elementárních matematických operací nutných k hackování začal dosahovat astronomických hodnot. Moderní kryptografie se stala mnohem odolnější vůči kryptoanalýze než kdysi používané zastaralé techniky, které stačily rozbít perem a kusem papíru. Může se zdát, že čistá teoretická kryptoanalýza není schopna efektivněji prolomit moderní šifry. Nicméně historik David Kahn ve své poznámce k 50. výročí Národní bezpečnostní agentury píše :

„Dnes stovky firem nabízejí mnoho různých kryptosystémů, které nelze prolomit žádnou ze známých metod kryptoanalýzy. Takové systémy jsou totiž odolné i vůči zvolenému útoku v prostém textu, to znamená, že porovnání holého textu a jeho odpovídajícího šifrovaného textu neodhalí šifrovací klíč, který by umožnil dešifrování jiných zpráv. V jistém smyslu je tedy kryptoanalýza mrtvá. Ale to není konec. Kryptoanalýza může být mrtvá, ale přeneseně řečeno, kočku lze stáhnout z kůže několika způsoby.“

Dále ve své poznámce popisuje zvýšený význam zachycování dat, chyb, útoků na postranní kanály a kvantových počítačů jako technik, které nahrazují tradiční metody kryptoanalýzy. V roce 2010 bývalý CTO ředitelství národní bezpečnosti Brian Snow poznamenal, že komerční kryptografie téměř dosáhla úrovně technologie používané zpravodajskými službami a nyní společně „velmi pomalu postupují v již plně prozkoumané oblasti“.

Na odpis je však ještě příliš brzy. Za prvé, není známo, jak účinné jsou metody kryptoanalýzy používané speciálními službami , a za druhé, v průběhu let formování a zdokonalování moderní počítačové kryptografie bylo učiněno mnoho požadavků na teoretická i praktická kryptografická primitiva:

v roce 1998 byla objevena zranitelnost vůči útokům založeným na šifrovém textu v blokové šifře MADRYGA , navržené již v roce 1984, ale ne široce používané;
celá řada útoků vědecké komunity, z nichž mnohé byly zcela praktické, doslova zničila blokovou šifru FEAL , navrženou jako náhrada za DES jako standardní šifrovací algoritmus, ale také málo používanou;
bylo také zjištěno, že s široce dostupnými výpočetními nástroji lze A5/1 , A5/2 , blokovou šifru CMEA a šifry DECT používané k zabezpečení mobilní a bezdrátové telefonní komunikace prolomit během hodin nebo minut a někdy i reálně čas;
Útok hrubou silou pomohl prolomit některé aplikované bezpečnostní systémy, jako je CSS , systém pro ochranu digitálního mediálního obsahu na médiích DVD .

I když jsou tedy nejbezpečnější z dnešních šifer mnohem odolnější vůči dešifrování než Enigma, přesto dešifrování stále hraje důležitou roli v rozsáhlé oblasti informační bezpečnosti.

Metody kryptoanalýzy

Bruce Schneier identifikuje 4 hlavní a 3 doplňkové metody kryptoanalýzy za předpokladu, že kryptoanalytik zná šifrovací algoritmus (v souladu s Kerckhoffsovým principem ):

Základní metody kryptoanalýzy

Útok založený na šifrovaném textu .
Útok založený na otevřených textech a odpovídajících šifrovaných textech.
Zvolený útok v otevřeném textu (možnost vybrat text k šifrování).
Adaptivní útok na prostý text .

Další metody kryptoanalýzy

Základní metody kryptoanalýzy

Útoky šifrovaným textem

Předpokládejme, že kryptoanalytik má určitý počet šifrovaných textů získaných v důsledku použití stejného šifrovacího algoritmu. V tomto případě může kryptoanalytik provést pouze útok založený na šifrovaném textu. Cílem kryptografického útoku je v tomto případě najít co nejvíce otevřených textů, které odpovídají dostupným šifrovým textům, nebo ještě lépe najít klíč použitý při šifrování.

Vstupní data pro tento typ útoku může získat kryptoanalytik jako výsledek jednoduchého zachycení zašifrovaných zpráv. Pokud je přenos prováděn přes otevřený kanál, je implementace úkolu sběru dat relativně snadná a triviální. Útoky založené na šifrovaném textu jsou nejslabší a nejnepohodlnější.

Útok založený na otevřených textech a odpovídajících šifrovaných textech

Nechť má kryptoanalytik k dispozici nejen šifrové texty, ale i odpovídající otevřené texty.

Pak existují dvě možnosti, jak problém vyřešit:

Najděte klíč používaný k převodu prostého textu na šifrovaný.
Vytvořte algoritmus schopný dešifrovat jakoukoli zprávu zakódovanou tímto klíčem.

Získávání otevřených textů hraje při provádění tohoto útoku zásadní roli. Prosté texty jsou získávány z různých zdrojů. Takže například můžete odhadnout obsah souboru podle jeho přípony.

V případě hacknuté korespondence můžeme předpokládat, že dopis má strukturu jako:

"Pozdravy";
"hlavní text";
„konečná forma zdvořilosti“;
"podpis".

Útok lze tedy zorganizovat výběrem různých typů „Pozdravy“ (například „Ahoj!“, „Dobré odpoledne“ atd.) a/nebo „Konečné formy zdvořilosti“ (jako „S úctou“, „S pozdravem“ S pozdravem" " atd.). Tento útok je silnější než útok využívající pouze šifrovaný text.

Zvolený útok v otevřeném textu

K provedení tohoto typu útoku potřebuje kryptoanalytik mít nejen určitý počet otevřených textů a z nich odvozených šifrovaných textů. Mimo jiné v tomto případě musí být kryptoanalytik schopen zachytit několik otevřených textů a získat výsledek jejich šifrování.

Úkoly kryptoanalytika opakují úkoly pro útok v otevřeném textu, tedy získat šifrovací klíč nebo vytvořit dešifrovací algoritmus pro daný klíč.

Vstupní data pro tento typ útoku můžete získat například takto:

Vytvořte a odešlete falešnou, nešifrovanou zprávu, která předstírá, že je od jednoho z uživatelů, kteří běžně používají šifrování.
V některých případech můžete získat odpověď, která obsahuje šifrovaný text citující obsah falešné zprávy.

Při provádění útoku tohoto typu má kryptoanalytik možnost vybrat bloky otevřeného textu, které za určitých podmínek umožňují získat více informací o šifrovacím klíči.

Adaptivní útoky na prostý text

Tento typ útoku je vhodnější speciální případ útoku se zvoleným prostým textem. Výhodou adaptivně zvoleného útoku s otevřeným textem je to, že kromě možnosti zvolit otevřený text se může kryptoanalytik rozhodnout zašifrovat ten či onen otevřený text na základě již získaných výsledků šifrovacích a následných dešifrovacích operací. Jinými slovy, při útoku s vybraným prostým textem kryptoanalytik vybere pouze jeden velký blok prostého textu pro následné šifrování a poté začne analyzovat systém na základě těchto dat. V případě organizování adaptivního útoku může kryptoanalytik obdržet výsledky šifrování libovolných bloků otevřeného textu, aby shromáždil data, která ho zajímají a která budou zohledněna při výběru dalších bloků otevřeného textu odeslaných k šifrování, a již brzy. Přítomnost zpětné vazby dává útoku založenému na adaptivně zvoleném šifrovém textu výhodu oproti všem výše uvedeným typům útoků.

Další metody kryptoanalýzy

Zvolený útok šifrovaného textu

Předpokládejme, že kryptoanalytik má dočasný přístup k šifrovacímu nástroji nebo zařízení. V tomto případě může kryptoanalytik po omezenou dobu získat ze šifrových textů, které jsou mu známé, odpovídající otevřené texty, po kterých bude muset kryptoanalytik začít analyzovat systém. U tohoto typu útoku je cílem analýzy získat šifrovací klíč.

Tento problém lze stručně formulovat následovně.

Vzhledem k tomu: $C_{1},P_{1}=D_{k}(C_{1});C_{2},P_{2}=D_{k}(C_{2});C_{3}, P_{3}=D_{k}(C_{3});\tečky ;C_{n},P_{n}=D_{k}(C_{n}),$

kde je dostupný šifrovaný text, je odpovídající otevřený text a je funkce dešifrování pomocí klíče . $C_{n}$ $n$ $P_{n}$ $C_{n}$ $D_{k}$ $k$

Najít: použitý šifrovací klíč . $k$

Zajímavé je, že vybraný útok pomocí šifrovaného textu lze také nazvat „ útok v době oběda “ nebo „ útok o půlnoci “. Řekněme, že název „ Lunchtime Attacks “ odráží skutečnost, že legitimní uživatel může během oběda nechat svůj dešifrovací stroj bez dozoru a kryptoanalytik toho může využít.

Key-uhádnutý útok

Na rozdíl od svého názvu útok zvoleným klíčem neznamená, že se kryptoanalytik zabývá jednoduchým výčtem klíčů v naději, že najde ten správný. Útok tohoto typu je založen na skutečnosti, že kryptoanalytik může pozorovat činnost šifrovacího algoritmu, který používá několik klíčů. Kryptanalytik zpočátku neví nic o přesném významu klíčů, ale zná nějaký matematický vztah, který klíče spojuje dohromady. Příkladem toho je situace, kdy kryptoanalytik zjistil, že posledních 80 bitů všech klíčů je stejných, ačkoli hodnoty samotných bitů mohou být neznámé.

Banditská kryptoanalýza

Kryptanalytik může využít tzv. „ lidský faktor “, tedy pokusit se pomocí vydírání, úplatkářství, mučení či jiných prostředků získat informace o šifrovacím systému nebo dokonce o samotném šifrovacím klíči. Například poskytnutí úplatku jako jednu z odrůd gangsterské kryptoanalýzy lze nazvat „Otevření koupí klíče“. Technika pitvy je tedy postavena na slabosti lidí jako nedílná součást systému bezpečnosti informací.

Banditská kryptoanalýza je považována za velmi účinný způsob, jak prolomit systém, a často za nejlepší způsob, jak prolomit šifry.

Různé typy útoků

Viz také

American Cryptogram Association

Poznámky

↑ David Kahn . Přerušovače kódů . — M.: Tsentrpoligraf , 2000. — 473 s. — ISBN 5-227-00678-4 .

Literatura

David Kahn, Poznámky k 50. výročí Národní bezpečnostní agentury , 1. listopadu 2002.
Schneier B. Kryptoanalýza // Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M .: Triumf, 2002. - S. 19-22. — 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 .
Pilidi V. S. Kryptografie. Úvodní kapitoly . - Rostov na Donu: SFU, 2009. - 110 s.
Alex Biryukov a Eyal Kushilevitz: Od diferenciální kryptoanalýzy k útokům pouze na šifrovaný text

Odkazy

Kryptoanalýza: včera, dnes, zítra | otevřené systémy. DBMS | Nakladatelství "Otevřené systémy" (ruština)

Slovníky a encyklopedie	velká čínština Britannica (online)
V bibliografických katalozích	GND : 4830502-9