S-blok (informatika)

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é 22. března 2015; kontroly vyžadují 30 úprav .

S-box (nebo substituční blok , angl.  s-box z substitučního boxu ) - funkce v programovém kódu nebo hardwarovém systému, která na vstupu vezme n bitů , převede je podle určitého algoritmu a vrátí m bitů na výstup . n a m se nemusí nutně rovnat [1] .

S-boxy se používají v blokových šifrách .

V elektronice můžete přímo použít obvod znázorněný na obrázku . Při programování se vytvářejí substituční tabulky (substituční tabulky , substituční tabulky). Oba tyto přístupy jsou ekvivalentní, tj. data zašifrovaná na počítači lze dešifrovat na elektronickém zařízení a naopak.

S-box se nazývá dokonalý ( perfect s-box ) [2] , pokud jsou hodnoty výstupních bitů vypočítány funkcí ohnut na základě hodnot vstupních bitů a jakákoli lineární kombinace výstupních bitů je ohnutá funkce vstupních bitů.  

Implementace softwaru

Softwarová implementace s-bloku funguje následovně:

Použitá tabulka se nazývá "náhradní tabulka" nebo "substituční tabulka". Stůl může:

Například pro šifru DES (algoritmus) se používá pevná tabulka , zatímco pro šifry Blowfish a Twofish je tabulka vytvořena na základě klíče.

Příklad [3] . Zvažte práci s tabulkou pátého s-bloku ( ) šifry DES . Pátý s-box bere 6 bitů ( ) jako vstup a  vrací 4 bity (  ) jako výstup . Vstupní bity očíslujeme zleva doprava od 1 do 6. Substituční tabulka má následující tvar:

S5 _ Hodnoty 2., 3., 4. a 5. bitu na vstupu
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Hodnoty 1. a 6. bitu na vstupu 00 0010 1100 0100 0001 0111 1010 1011 0110 1000 0101 0011 1111 1101 0000 1110 1001
01 1110 1011 0010 1100 0100 0111 1101 0001 0101 0000 1111 1010 0011 1001 1000 0110
deset 0100 0010 0001 1011 1010 1101 0111 1000 1111 1001 1100 0101 0110 0011 0000 1110
jedenáct 1011 1000 1100 0111 0001 1110 0010 1101 0110 1111 0000 1001 1010 0100 0101 0011

Nechte vstupní bity " 0 1101 1 ". Pojďme najít výstupní bity .

Implementace hardwaru

Hardwarová implementace s-bloku (viz obr. ) se skládá z následujících zařízení:

Dekodér  je zařízení, které převádí n - bitový binární signál na jednobitový základní signál .

Například pro s-box znázorněný na obrázku dekodér převádí tříbitový signál ( ) na osmibitový ( ).

Přepínací systém  – interní připojení, která provádějí výměnu bitů . Pokud m=n , počet připojení je . Každý vstupní bit se mapuje na výstupní bit umístěný ve stejném bitu nebo v jiném bitu . Pokud počet vstupů n a výstupů m není stejný, každý výstup dekodéru může mít nula, jedno, dvě nebo více připojení. Totéž platí pro vstupy kodéru.

Pro s-blok zobrazený na obrázku , je počet připojení .

Kodér  je zařízení, které převádí signál z jednobitovéhona n -bitový binární signál.

Pro s-blok zobrazený na obrázku lze sestavit následující substituční tabulku (substituční tabulku).

0 jeden 2 3 čtyři 5 6 7
Vstupní hodnota dekodéru 000 2 = 0 10 001 2 = 1 10 010 2 = 2 10 011 2 = 3 10 1002 = 410 _ 1012 = 510 _ 1102 = 610 _ 1112 = 710 _
Číslo výstupu dekodéru (podle obrázku ), na kterém je hodnota nastavena na 1 (na ostatních výstupech je hodnota nastavena na 0) 0 jeden 2 3 čtyři 5 6 7
Číslo vstupu kodéru (podle obrázku ), na kterém je hodnota nastavena na 1 (na ostatních vstupech je hodnota nastavena na 0) 3 0 jeden čtyři 6 7 2 5
Hodnota na výstupu kodéru 011 2 = 3 10 000 2 = 0 10 001 2 = 1 10 1002 = 410 _ 1102 = 610 _ 1112 = 710 _ 010 2 = 2 10 1012 = 510 _

Příklad . Nechte číslo 110 2 přivést na vstupy kodéru znázorněného na obrázku (viz obrázek ). Protože dekadická reprezentace binárního čísla 110 2 je 6 10 , bude mít 6. výstup kodéru hodnotu 1 a ostatní výstupy budou mít hodnotu 0 (viz obrázek ). Pomocí soustavy přepínačů se hodnota 1 přenese na 2. vstup dekodéru (bit swap). Protože binární reprezentace dekadického čísla 2 10 je 010 2 , výstupy dekodéru budou číslo 010 2 (viz obrázek ).

Aplikace

S-boxy se používají v blokových šifrách při provádění symetrického šifrování ke skrytí statistického vztahu mezi otevřeným textem a šifrovaným textem .

Analýza n -bitového s-bloku pro velké n je extrémně obtížná, ale implementovat takový blok v praxi je velmi obtížné, protože počet možných spojení je velký ( ). V praxi se „substituční blok“ používá jako prvek složitějších systémů.

S-boxy se používají v následujících šifrách:

Zabezpečení

Při navrhování s-boxu je třeba věnovat zvláštní pozornost sestavení „tabulky náhrad“. Po mnoho let výzkumníci hledali záložky (zranitelnosti známé pouze tvůrcům) v substitučních tabulkách osmi s-bloků šifry DES . Autoři DES řekli [4] o tom, čím se řídili při sestavování substitučních tabulek. Výsledky diferenciální kryptoanalýzy šifry DES ukázaly, že čísla v substitučních tabulkách byla pečlivě vybrána, aby se zvýšila odolnost DES vůči určitým typům útoků. Biham a Shamir zjistili, že i malé změny v tabulkách mohou významně oslabit DES [5] .

Poznámky

  1. ↑ Chandrasekaran, J. et al. Přístup založený na chaosu pro zlepšení nelinearity v návrhu s-box kryptosystémů symetrických klíčů // Pokroky v sítích a komunikacích: první mezinárodní konference o počítačové vědě a informačních technologiích, CCSIT 2011, Bangalore , Indie , 2.–4. ledna 2011 . Sborník, část 2. - Springer, 2011. - S. 516. - ISBN 978-3-642-17877-1 .
  2. ↑ RFC 4086 . Část 5.3 "Použití s-boxů pro míchání"
  3. ↑ Buchmann Johannes A. 5. DES // Úvod do kryptografie. — Corr. 2. tisk.. - New York, NY [ua]: Springer, 2001. - S. 119-120. — ISBN 0-387-95034-6 .
  4. ↑ Coppersmith, Don Data Encryption Standard (DES) a jeho síla proti útokům  //  IBM Journal of Research and Development : deník. - 1994. - Sv. 38 , č. 3 . - S. 243-250 . - doi : 10.1147/rd.383.0243 .
  5. ↑ Gargiulovy „Úpravy S-Boxu a jejich účinek v šifrovacích systémech podobných DES“ Archivováno 20. května 2012 na Wayback Machine . S. 9.

Literatura

Viz také

Odkazy