Linear cryptoanalysis
V kryptografii , lineární kryptoanalýza je obecná forma kryptoanalýzy na základě zjištění affine aproximace působení šifry . Útoky byly vyvinuty problokové šifry a proudových šifer . Lineární kryptoanalýza je jedním ze dvou nejčastěji používaných útoků na blokové šifry, jiná bytost rozdíl dešifrování .
Objev je připisován Mitsuru Matsui , který jako první použil techniku na FEALšifry (Matsui a Yamagishi, 1992). [ 1 ] Následně, Matsui publikoval útok na Data Encryption Standard (DES), nakonec vést k první experimentální dešifrování z šifry zaznamenané v otevřeném společenství (Matsui, 1993; 1994). [ 2 ] [ 3 ] útok na DES není obecně praktické, vyžadující 2 43 známé holé . [ 3 ]
Různé úprav k útoku byly navrženy, včetně použití více lineární aproximace nebo obsahují non-lineární výrazy, což vede k obecné rozdělovacího dešifrování. Doklad o zabezpečení proti lineární kryptoanalýzy je obvykle očekává nových šifrovacích vzorů.
Tam jsou dvě části lineární kryptoanalýzy. Prvním z nich je postavit lineární rovnic líčit holý, ciphertext a klíčové kousky, které mají vysokou zaujatost, to je, jehož pravděpodobnost podniku (v prostoru všech možných hodnot jejich proměnných) jsou tak blízko, jak je to možné na 0 nebo 1. Druhým je použití těchto lineárních rovnic ve spojení se známými plaintext-šifrového párů odvodit bity klíče.
Pro účely lineární kryptoanalýzy, lineární rovnice vyjadřuje rovnost dvou výrazů, které se skládají z binárních proměnných v kombinaci s exkluzivní-nebo (XOR) operace. Například, následující rovnice, z hypotetické šifry, uvádí XOR součet prvního a třetího holého bitů (jako v blokové šifry bloku) a první šifrového bit je roven druhému kousku klíč:
V ideálním šifry, by jakýkoli lineární rovnice o holý, ciphertext a klíčové kousky držet s pravděpodobností 1/2. Vzhledem k tomu, že rovnice řešeny v lineární kryptoanalýzy se bude lišit v pravděpodobnosti, oni jsou více přesně odkazoval se na jako lineární aproximací .
Postup pro výstavbu přiblížení se liší pro každou šifru. V nejzákladnější typ šifry bloku, střídání-permutace sítě , je analýza soustředila především na boxy S- , pouze nelineární část šifry (tj. provoz S-box nelze kódovat v lineární rovnice).Pro dostatečně malé, S-boxy, je možné vyjmenovat všechny možné lineární rovnice vztahu mezi S-box je vstupní a výstupní bity, vypočítat jejich předsudky a vybrat ty nejlepší. Lineární aproximace pro S-boxů pak musí být v kombinaci s šifrovacím ostatními akcemi, jako je permutace a klíčem míchání, aby se dospělo na lineární aproximace pro celou šifru. Hromadí-up lemma je užitečným nástrojem pro tuto kombinaci kroku. K dispozici jsou také techniky pro opakované zlepšení lineární aproximace (Matsui, 1994).
Poté, co obdrží lineární aproximaci ve tvaru:
pak můžeme použít jednoduchý algoritmus (Matsui algoritmus 2), pomocí známých plaintext-ciphertext páry, uhodnout hodnot bitů klíče zapojených do sbližování.
Pro každou množinu hodnot bitů klíče na pravé straně (odkazoval se na jakodílčí klíč ), spočítat, kolikrát sbližování platí ve všech známých plaintext-šifrového párů, volání této počítání T . Částečné klíč, jehož T má největšíabsolutní rozdíl od poloviny počtu plaintext-šifrového páry je určen jako nejpravděpodobnější souboru hodnot těchto bitů klíče. To je proto, že se předpokládá, že správný klíč částečné způsobí přiblížení držet s vysokým zkreslením. Velikost vychýlení je významná tady, na rozdíl od velikosti pravděpodobnosti sám.
Tento postup může být opakován s jinými lineární aproximace, získání odhady na hodnotách bitů klíče, dokud se počet neznámých klíčových bitů je natolik nízká, že může být napaden s hrubou silou .