Symetrické šifrování

Kapitola, která nás teď čeká je naplněna algoritmy, které jsou založeny na principu symetrického šifrování.

Symetrické šifrování je takové šifrování, které používá stejného klíče jako pro zašifrování otevřeného textu, tak pro dešifrování zašifrovaného textu. Hlavním problémem je zde transport klíče mezi odesílatelem a adresátem.

Blokové šifry

Jak jste se sami mohli přesvědčit, bezpečné, silné a zároveň těžko prolomitelné šifry jsou ty, které kombinují transpoziční a substituční algoritmus, jejich klíč je v ideálním případě kratší než šifrovaný text a může se použít vícekrát.

Základem pro pochopení symetrického způsobu šifrování je pochopení principu Feistelovy šifry. Pojďme si nejdříve přiblížit některé z klíčových pojmů, které budeme v následující problematice potřebovat a poté se podíváme přímo na Feistelovu šifru.

Blokové šifry jsou zajímavé tím, že pracujeme s celky a operace, které s nimi provádíme, aplikujeme právě na celý celek. Bloky procházejí jednotlivými rundami (podobně jako boxer v ringu). Rundy mají obvykle stejnou funkci, ale probíhají několikrát za sebou. Synonymem pro rundu může být kolo či iterace.

Zkusili byste si na základě Vašich zkušeností formulovat, co to iterace je?

opakování
představuje způsob řešení problému, kdy postupně opakujeme a přibližujeme se k výsledku, při každém opakování se mění počáteční „text“, na který aplikujeme další krok

Další z důležitých a nedílných součástí toho způsobu šifrování je permutace.

„Permutace n prvků je každá uspořádaná n-tice vytvořená z těchto prvků. Každý z n prvků se v této n-tici vyskytuje právě jednou. Jednotlivé permutace se od sebe liší pouze pořadím prvků.“[1]

U permutace je tedy důležité pořadí prvků, které je odlišné před vstupem do této rundy a po jejím průběhu.

Princip Feistelovy šifry

Nyní si přiblížíme jednotlivé operace, které postupně probíhají:

Vstupem do algoritmu je vygenerovaný klíč a otevřený text.
Otevřený text (čili blok, který chceme zašifrovat) rozdělíme na dvě poloviny - pravou (R) a levou (L).
Každá polovina projde x rundami.
Při každém kole je použit speciální podklíč.
Podklíče jsou generovány z klíče zvláštním algoritmem.
Struktura každé iterace je stejná. Probíhají operace jako transpozice či substituce.
Výstupem všech těchto operací je šifrovaný text.

Blok klíče a generování podklíčů lze vidět na schématu obr. 1.

Obr. 1 Blokově znázorněné generování podklíčů

Obdobně poté vstup do algoritmu a probíhající iterace s přičtením příslušného podklíče obr. 2.

Obr. 2 Bloky dat, iterace a přičtení podklíčů

Feistelův způsob šifrování není přímo algoritmus, je to spíš struktura, která je společná pro všechny blokové šifry. Blokovou šifrou zde rozumíme například algoritmus DES, o kterém se blíže dozvíme v dalších aktivitách.

Lucifer & DES

V 60. letech minulého století vyvinul tým pod vedením Horsta Feistela obr. 3 šifrový standard pojmenovaný Lucifer. Lucifer měl klíč o délce 64 bitů a velikost bloku byla 128 bitů. Jednalo se o vůbec první blokovou šifru tohoto typu.V roce 1973 vyhlásil úřad NBS (National Bureau of Standarts) konkurz, ve kterém hledal vhodný šifrovací standard pro ochranu transakcí v obchodních aplikacích. Přihlásilo se několik možných kandidátů, ovšem žádný nevyhovoval přísným kritériím. Až v roce 1975, po příslušných testech a prověřeních, byl upravený Lucifer publikován a v roce 1976 přijat jako DES (Data Encryption Standard). Upravení algoritmu je opředeno řadou nejasností a kritik, ovšem jisté je, že pro svou dobu byl postačující. Klíč byl z původních 64 bitů zkrácen na 56 bitů, a DES byl přijat jako standard pro šifrování neklasifikovaných informací. O rok později byl poté normalizován pro všechny typy dat a používán do roku 2001, a následně nahrazen svým nástupcem - algoritmem AES.

Obr. 3 Horst Feistel

Shrnutí

Z historické části našeho kurzu jsme se přesunuli do relativně současné doby, kdy je důležité a efektivní chránit a šifrovat data, která jsou pro nás hodnotná. Vysvětlili jsme si pojmy jako blokové šifry, či zopakovaliy podstatu symetrického šifrování.

Zdroje

[1] - http://www.priklady.eu/cs/Matematika/Kombinatorika/Permutace.alej - ze dne 9.1.2012DOSTÁLEK, Libor a Marta VOHNOUTOVÁ. Velký průvodce infrastrukturou PKI a technologií elektronického podpisu. vyd. 1. Brno: Computer Press, 2006, 534 s. ISBN 80-251-0828-7.JIROUŠEK, Radim. Principy digitální komunikace. Vyd. 1. Voznice: Leda, 2006, 309 s. ISBN 80-733-5084-X.

2. Princip algoritmu DES

Klíčová slova

Princip algoritmu DES

„DES je typický blokový algoritmus, který bere text určité délky a transformuje ho pomocí mnoha komplikovaných operací na text stejné délky.“ [1]

Vrhneme se na vysvětlení komplikovaných operací.Princip algoritmu můžeme rozdělit na několik částí:

generování klíčů (podklíčů z klíče)
vstup, vstupní permutace a rozdělení na P a L
aplikace rundy (funkce f) na P a L + použití klíče
co se děje v rundě - S-box jako součást
výstupní permutace a výstup

Generování klíčů (podklíčů z klíče)

Abychom mohli DES použít, potřebujeme mít 56 bitů dlouhý hlavní klíč, který se zadává jako 8 bytů (poznámka pro matematiky: 8 bytů = 64 bitů; my potřebujeme pouze 56 bitů dlouhý klíč, vynechají se paritní bity - 8, 16, 24...64). Z tohoto klíče získáme 16 podklíčů (iteračních klíčů, rundových klíčů), které jsou použity v jednotlivých kolech. Generování klíčů se jinak také říká expanze. Rozsah možných klíčů je tedy 2^56 = 72 057 594 037 927 936.Klíč, který vstupuje do algoritmu je označen K obr. 1.

Obr. 1 Expanze klíče K1

Proběhne výběrová permutace PC-1 obr. 2, která přeskupí bity a rozdělí výstupní data z této operace na C₀ a D₀ (přeskupení bitů znamená, 57. bit bude na první pozici, 49. bit na druhé pozici, 41. bit na třetí pozici ..... a konečně 4. bit na poslední pozici; po přeskupení se celý blok rozdělí na dvě poloviny, které jsou zde označeny jako C₀ a D₀).

Obr. 2 DES - Výběrová permutace PC-1

Na obě tyto části je poté aplikován tzv. levý posun (posun jednotlivých bitů podle tabulky - probíhá pro všech 16 iterací, v první iteraci posune o 1 pozici, ve druhé rovněž o jednu pozici, při třetím průchodu o 2 pozice atd) a vzniknou bloky C₁ a D₁ (bloky C₁, D₁ tedy vzniknou aplikací levého posunu na bloky C₀, D₀)_, jak lze vidět v tabulce obr. 3.

Obr. 3 DES - Levý posun

Na bloky C₁, D₁ je poté aplikována permutace PC-2 obr. 4, která opět zpřehází bity (na prvním místě bude 14. bit, na druhém místě bit 17. atd) a zúží na 48 bitů (zúžení probíhá vynecháním některých bitů například 9. bit, 18. bit), výsledkem je první podklíč - označení K₁.

Obr. 4 DES - Výběrová permutace PC-2

Analogicky je takto vytvořeno všech 16 podklíčů - jak můžete vidět na obrázku obr. 5. Část této operace si můžete vyzkoušet v připraveném cvičení.

Obr. 5 Princip expanze všech 16 rundových klíčů

Vstup, vstupní permutace a rozdělení na P a L

Další, co nám vedle klíče vstupuje do algoritmu, je zpráva (bitový řetězec, který musí být rozdělen na 64 bitové bloky - popřípadě poslední blok doplněn na 64 bitů; tyto bity jsou poté uspořádány do tabulky, kam se zapisují po řádcích).Jednotlivé bity jsou „očíslovány“ podle své pozice z důvodu jednoduššího pochopení, co se s tabulkou děje obr. 6.

Obr. 6 Vstupní matice

Tabulka je podrobena vstupní permutaci IP obr. 7,

Obr. 7 Vstupní permutace IP

(vstupní permutace IP zpřehází jednotlivé bity - na prvním místě bude 58. bit, na druhém místě 50. bit, na posledním místě 7. bit.) a výstupem z ní jsou dva 32 bitové bloky - levý (L₁) a pravý (P₁) obr.8.

Obr. 8 Vstup, permutace a rozdělení na L0 a R0 blok

Oba bloky tedy vzniknou rozdělením tabulky, po vstupní permutaci. Tyto dva bloky jsou 32 bitové a je na ně aplikována další permutace.Přehledně je to zobrazeno na obrázku obr. 9.

Obr. 9 Polovina před doplněním

(Nahoře vidíme celkovou tabulku po permutaci, ta je rozdělena na dva bloky. Pro lepší názornost se jednotlivé bity v obou blocích opětovně očíslovaly dle pozice. Následně je na ně aplikována permutace.Př.: první 58 bit je současně v levé polovině, kde se nachází na pozici 1. Po permutaci se bude nacházet ve třetím řádku prvního sloupce, kde je rovněž označen 1)

Aplikace rundy (funkce f) na P a L + použití klíče

V tomto bodě se poprvé setkáme s aplikací vygenerovaného klíče - v první rundě to bude podklíč K₁. Pravá polovina P₀ má 32 bitů. Aby k ní mohl být přičten klíč, jenž má 48 bitů, musí být pravá část rozšířena na 48 bitů obr. 10.

Obr. 10 DES - Expanze - rozšíření 32 bitů na 48 bitů

Toto rozšíření proběhne pomocí tzv. tabulky expanze - všimněte si dvojího zastoupení některých bitů. Takto upravená pravá polovina + podklíč vstupuje do šifrovací funkce f. Povšimněte si také jednotlivého prohazování z levé na pravou stranu.(např. výsledek L₂ se přesune na pravou stranu a tvoří tedy základ pro operace na pravé straně.Poznámka: zápis v celkovém grafu popisuje již to, co naznačují šipky. Neznamená tedy, že se provedou operace s již zmíněnou částí L₂, ta se přesune na pravou stranu a tam proběhnou operace znovu.)

Co se děje v rundě (f) - S-box jako součást

Osm S-boxů tvoří jeden z nejdůležitějších prvků, co se týče bezpečnosti DES obr. 11.

Obr. 11 DES S-Boxy

Vyrobí z 6 příchozích bitů 4 výstupní bity. A záleží právě na vnitřním uspořádání S-boxu. Příklad: na vstupu budeme mít 6bitové slovo 000111 obr. 12

Obr. 12 S-box - příklad

dva krajní bity (první a poslední) určují řádek S-boxu
čtyři zbylé prostřední bity určují sloupec S-boxu
průsečík je poté výstup
v tomto případě se dostaneme na 04 - což binárně je 0100

Do S-boxu vstupuje výsledek, který je rozdělen na osm 6 bitových řetězců. Po transpozici, podle uvedené tabulky, zúží vstupní 6 bitové bloky na 4 bitové výstupní bloky, kterých je opět osm. Po spojení všech osmi řetězců dostaneme 32 bitový řetězec, který je znovu podroben permutaci (P).V roce 1990 v souvislosti s neustálou kritikou přijatého standardu bylo zjištěno, že náhodnou volbou S-boxu se bezpečnost ještě zvětší. (Do té doby byl S-box volen podle předem nastaveného řádu).

Výstupní permutace a výstup

Permutovaný výstup z S-boxů je opětovně permutován (permutace IP-1, inverzní ke vstupní obr. 13) a výstupem z algoritmu je zašifrovaný 64 bitový šifrovaný text.

Obr. 13 Výstupní permutace IP-1

Celkový pohled na algoritmus tedy můžeme vidět zde obr. 14.

Obr. 14 DES a jeho blokové schéma

Shrnutí

Podrobně jsme si přiblížili generování podklíčů z hlavního klíče u algoritmu DES, stejně tak jsme si přiblížili princip celkového algoritmu i aplikaci vygenerovaných podklíčů.

Zdroje

Problematika blokových šifer a algoritmů je velice přehledně a srozumitelně popsána i v knize JIROUŠEK, Radim. Principy digitální komunikace. Vyd. 1. Voznice: Leda, 2006, 309 s. ISBN 80-733-5084-X.[1] - http://www.kryptografie.wz.cz/data/des.html - ze dne 31.12.2011

3. Cvičení: Odvození podklíče

Zadání

Známe klíč a chceme se dostat k zašifrovaným datům.

Algoritmus zašifrovaných dat je známý - DES.

1 0 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0

Nezbývá tedy nic jiného, než získat podklíče.

Tipy pro řešení

aplikujte získané znalosti ohledně permutací, levých posunů a vzniku podklíčů
nezapomeňte na rozdělení klíče na levou a pravou stranu
vzpomeňte si, co všechno jsme si o algoritmu DES říkali

Návrh řešení

4. Dešifrování, kryptoanalýza, prolomení a modifikace DES

Šifrovat pomocí standardu DES už ovládáme, jak se ale dostat k takto zašifrovaným údajům, když neznáme klíč... Je to vůbec možné? A pokud ano, jsou nějaké lepší algoritmy na obdobném principu?

5. Maticový počet

Klíčová slova

Maticový počet

Abychom si mohli objasnit algoritmus AES, který nahradil již dříve jmenovaný DES, podíváme se předtím na některé operace s maticemi.

Co je to matice

Existuje několik definic, které říkají, co je to matice, způsob zapsání či čtení matice - zde je příklad jedné z nich:

matice typu (m, n) je schéma (či zobrazení), kde m, n jsou přirozená čísla, zapsaná do m řádků a n sloupců obr. 1

Obr. 1

a₁₁, a₁₂ až a_jk jsou prvky matice (takovým prvkem matice může být číslo, ale i funkce - pro naši potřebu to budou čísla označující pořadí bitů, či samotné 1 a 0)
indexy_jk u jednotlivých prvků označují polohu prvku - j je řádek, k sloupec

(pro příklad prvek a₂₂ je umístěn ve druhém řádku a druhém sloupci - proto má index₂₂)Existují také různé typy matic. Zkusili byste pojmenovat jednotlivé matice podle obrázku obr. 2?
Obr. 2

matice Q je matice čtvercová
matice E je matice jednotková (označení pro jednotkovou matici může být E, I, J - e jako matice elementární, I z elektrikářských oborů, kde písmenko I značí proud, J jako jednotková)
matice N je matice nulová
matice O pak matice obdélníková

Základní operace

Teď už víme, jak taková matice vypadá, vyvstává tedy otázka, zda si dokážete představit, co všechno se dá s maticemi provádět. Či vymyslet k čemu matice potřebujeme? Myslíte, že je možné s nimi provádět základní matematické operace?Znáte nějaké?

základními operacemi můžeme rozumět sčítání, odčítání, násobení a dělení (dělení budeme rozumět jako inverzní násobení, či násobení inverzní maticí)
pomocí pokročilejších operací nám ale matice umí pomoci při řešení kvadratických rovnic
pro nás mají matice využití v šifrovacím standardu AES - pomocí operací, kterým se budeme blíže věnovat v následujících článcích, dokáží zašifrovat otevřený text - opět symetricky

Základní operace si budete moci vyzkoušet v připravených cvičeních, kde jsou i podrobně vysvětleny.Důležité je si také uvědomit, za jakých podmínek lze s maticemi početní operace provádět. Například sčítat i odčítat matice můžeme, pouze pokud mají stejný počet sloupců a řádek (tudíž stejný počet prvků).Naopak násobit matice můžeme, pokud se délka řádku první matice rovná délce sloupce druhé matice. Jinak je násobení matic nereálné obr. 3. Abychom pochopili princip standardu AES, bylo by dobré osvojit si operace násobení a transponování. V následujících cvičeních jsou připraveny i ostatní operace, abyste se mohli procvičit.

Obr. 3

Shrnutí

Vysvětlili jsme si základní pojmy z oblasti základního maticového počtu. Přiblížili jsme si, jak taková matice vypadá a jaké základní operace s ní můžeme pro naše účely vykonávat.

Zdroje

Pro další informace či rozšíření vědomostí o maticích, determinantech a podobných zajímavostech z této problematiky je doporučena kniha:TESKOVÁ, Libuše. Lineární algebra. 3. vyd. Plzeň: Západočeská univerzita, 2010, 243 s. ISBN 978-80-7043-966-1.

6. Cvičení: Sčítáme, odčítáme...

Zadání

Cvičení je rozděleno na dvě části, v sekci a) si vyzkoušíte sčítání, v sekci b) potom odčítání dvou matic.

a) proveďte operaci sčítání matic A + B. Výsledná matice bude mít označení C.

Obrázek 1. Sčítání matic

b) proveďte odčítání matic E - F. Výsledek bude matice G.

Obrázek 2. Odčítání matic - zadání

Tipy pro řešení

Podívejte se na návodné schéma pro oba typy příkladů.

První schéma obecně zobrazuje postup při sčítání, druhé schéma pak konkrétní postup při odčítání.

U obou schémat jsou znaménka dána jako v ukázkových příkladech.

1. obecný postup při sčítání

Obrázek 1. Obecný postup sčítání

2. Obecný postup při odčítání

Obrázek 2. Obecný postup při odčítání

Návrh řešení

7. Cvičení: Násobíme a transponujeme....

Zadání

Toto cvičení je koncipováno spíš jako vysvětlující. Nejdříve je na jednoduchých příkladech vysvětlen princip a) násobení; b) transponování.

Nejdříve si tedy osvětlíme podstatu násobení:

Násobení matic je dvojího typu - můžeme násobit matici číslem. Postup je jednoduchý - číslem násobíme všechny prvky dané matice a zapisujeme postupně do matice výsledné

Obrázek 1. Násobení matice číslem

Druhým způsobem je násobení matice maticí. Zde se podíváme nejdříve na připravené schéma.

Princip: Vezmete první řádek první matice a první sloupec druhé matice. Nyní vynásobíte první prvek s prvním prvkem a sečtete s násobkem druhého prvku s druhým prvkem a sečtete atd.

Obrázek 2. Součin matic - schéma

Nejlepší zde bude konkrétní příklad.

Obrázek 3. Násobení - 3 matice

Jak jsme získali 36 - jako prvek₁₁ ve výsledné matici? 36 = (1^.4) + (2^.10) + (3^.4) analogicky pro všechny ostatní prvky.

Cvičení: Vynásobte následující matice.

Po vyzkoušení násobení se tedy podíváme na transponování.

Matice transponovaná k matici A je matice A^T, u které platí a_ij = a^T_ji, tj. prvek který byl v i-tém řádku a j-tém sloupci bude v transponované matici na j-tém řádku a i-tém sloupci. Zkrátka zaměníte řádky matice za sloupce.

Obrázek 4. Transponování matic

Cvičení: Transponujte zadanou matici:

Tipy pro řešení

procvičíte si vybrané operace na připravených jednoduchých cvičeních
pozorně si přečtěte „návod“, jak řešit zadané úkoly

Návrh řešení

8. Vybíráme nový standard

Klíčová slova

Vybíráme nový standard

Po cvičeních s maticemi, které budeme u následujícího typu šifrování potřebovat, si představíme soutěž, která předcházela výběru nového šifrovacího standardu.

Abyste mohli porovnat jednotlivé kandidáty na toto prestižní místo, budou vám blíže představeni finalisté, kteří se dostali do druhého kola této soutěže.

Potřebujeme tedy najít vhodný algoritmus, který bude především bezpečný, a nahradí již prolomený standard DES.

Algoritmus DES již dále nebyl udržitelný - proto NIST (National Institute of Standards and Technology) vyhlásil 2. 1. 1997 veřejnou soutěž o přijetí nové šifry AEA (Advanced Encryption Algorithm), která by se následně stalanovým šifrovacím standardem AES (Advanced Encryption Standard). Vítězná šifra se tedy bude jmenovat AES. Tato soutěž byla plně veřejná a otevřená komukoli, kdo podal vlastní návrh, a byl schopen dodržet kritéria daná NIST.

Cílem bylo navrhnout a získat novou velmi silnou šifru pro vládní i komerční použití.

Požadavky NIST

Hlavní požadavky, které NIST položil na novou šifru, byly takové, že AEA bude bloková symetrická šifra s délkoubloku 128 bitů, která musí podporovat délky klíčů 128, 192 a 256 bitů. Při výběru se posuzovala zejménabezpečnost, cena (v širokém smyslu slova - například cena při hardwarové implementaci) a softwarové vlastnosti, popřípadě kompatibilita. Vítaným plusem byly samozřejmě i vlastnosti nad rámec požadavků NIST.

Autorská práva

Protože AES představuje otevřený standard, určený i pro komerční účely, a tedy zaměřený na podporu informačních technologií jejich aplikací a dalšímu rozvoji, byla v podmínkách soutěže zakotvena i povinnost účastníků zřeknout se licenčních poplatků, autorských práv a vyřešit veškeré patentové ochrany tak, aby jejich algoritmus mohl býtkýmkoliv bezplatně použit.

Někteří kandidáti

Zde je výpis některých algoritmů, jejichž autoři poslali svůj návrh do soutěže o nový šifrovací standard

Algoritmus Rijndael, jehož autoři jsou Joan Deamen a Vincent Rijmen (Belgie)

RC6, jehož autory jsou RSA Laboratories (USA)
Twofish, o který se zasloužil tým autorů Bruce Scheiner, John Keisey, Dough Whiting, David Wagner, Chris Hall, Niels Ferguson (USA)
- Magenta od Deutsche Telecom AG (Německo)

MARS vyvinutý společností IBM (USA)
Serpent od autorů Ross Anderson, Eli Biham, Lars Knudsen (UK, Izrael, Norsko)

Crypton od firmy Future Systems, Inc. (Korea)
a samozřejmě několik dalších....

9. června 1999 bylo do druhého kola vybráno pět finalistů. Staly se jimi algoritmy MARS, RC6, Rijndael, Serpent aTwofish. Nyní si tyto finalisty trochu představíme.

Twofish

Algoritmus Twofish je další z řady symetrických algoritmů, které používají Feistelovo schéma. Pamatujete si, jak vypadalo Feistelovo schéma z minulých článků a studijních aktivit?Twofish pracuje s bloky, které projdou 16 rundamiupravené jednobitovou rotací. Tento algoritmus používá různorodé operace, jako násobení, aritmetické sčítání, XOR aS-boxy (substituční boxy).Rundovní funkce používá zmiňované operace na 32bitových slovech, které projdou S-boxy, transformací a přičtením klíče.Substituční tabulky jsou závislé na klíči, který může být volitelně až 256 bitů dlouhý.

MARS

Dle požadavků NIST má MARS volitelnou délku klíče a to 128, 192 nebo 256 bitů. Pracuje s 32bitovými bloky dat.Zašifrování i dešifrování se provádí obdobně, obě činnosti se liší pouze opačným řazením rundovních podklíčů.MARS má několik fází přičítání a odčítání klíčů v 32 rundách, 8 rund dopředného mixování (bez účasti klíče), 16 rund přičítání a odčítání klíčů (za použití klíče) a 8 rund zpětného mixování (bez účasti klíče).Rundy, kde nejsou použity klíče, užívají sčítání a operaci XOR a dvou S-boxů navržených tak, aby odolávaly lineární a diferenciální kryptoanalýze. Klíčované rundy užívají 32bitové násobení a sčítání klíčů a datově závislé rotace (zřetězené rotace).

RC6-w/r/b

Tato šifra má několik volitelných parametrů: w (počet bitů slova), r (počet rund) a b (počet bytů klíče), proto se podle nich přesně označuje jako RC6-w/r/b. Pro kandidáta do soutěže AES bylo stanoveno

w = 32,r = 20,b volitelně 16, 24 nebo 32

Myšlenka RC6 těží z již dříve navržených a prověřených šifer RC5 a RC4 (taktéž z dílny RSA Laboratories). Autoři RC6 tedy postavili dvě RC5 paralelně vedle sebe a propojili je tak, aby každý bit slova 128bitového výstupního bloku závisel na všech bitech 128bitového slova vstupního bloku. K tomu byly využity datově závislé rotace řízené kvadratickou funkcí.RC6 má rundovní schéma vycházejícího též z Feistelova principu. V každé rundě se využije 32bitového násobení a sčítání, XOR a součet klíčů.

Rijndael

Rijndael podporuje volitelně i větší datové bloky a klíče, než požaduje NIST, nicméně pro AES byla na základě požadavků NIST stanovena délka datového bloku na 128 bitů. Délka klíče je pak 128, 192 nebo 256 bitů. Rijndael je velmi flexibilní návrh, který si popíšeme bytově s ohledem na další studijní aktivity, kde budeme rovněž pracovat v tomto typu šifrování s byty.Algoritmus samotný představuje vlastně substitučně-lineární transformační postup s 10, 12 nebo 14 rundami v závislosti na délce klíče (10, 12 nebo 14 rund bylo stanoveno pro odpovídající délky klíče 128, 192 a 256 bitů pro AES, lze pro další modifikace počet rund měnit).V jednotlivých rundách se vstupní blok dělí na pole bytů, které prochází šifrovými bytovými operacemi. Runda osahuje S-box, dvě mixovací lineární vrstvy a XOR rundovních klíčů na výsledné bytové pole, přičemž tento krok je vynechán u poslední rundy.

Serpent

Serpent, podobně jako Rijndael, je substitučně-lineární tranformační algoritmus pracující ve 32 rundách. Podporované jsou libovolné délky klíče do 256 bitů. Návrh šifry je dosti konzervativní, autoři nechtěli použít žádné inovativní prvky jako datově závislé rotace, násobení nebo sčítání místo operace XOR apod.Místo toho aplikovali osvědčené principy tak, aby šifra byla dobře hardwarově i softwarově implementovatelná, důraz byl položen na dobré zpracování jednotlivých bitů a výpočet rundovních klíčů.Runda se skládá ze tří operací: naXORování klíče, aplikace jednoho z 8 S-boxů a lineární transformace. V poslední rundě se místo lineární transformace použije ještě jedno XORování klíče.Dne2. října 2000 NIST ustanovil na základě diskuse a výsledků algoritmus Rijndael vítězem soutěže.Rijndael má podle NIST adekvátní úroveň bezpečnosti. A v současné době je platným standardem pro ochranu dat. Rijndael se tedy stal vítězem celé soutěže o šifrovací standard, a byl přejmenován na AES. A právě AES se budeme věnovat v následujících studijních aktivitách.

Shrnutí

Po úspěšném prolomení DES bylo zapotřebí najít jiný šifrovací algoritmus, který by DES nahradil. Proto NIST vyhlásil veřejnou soutěž, jejímž cílem bylo najít algoritmus, který dokáže zabezpečit data vysokým stupněm ochrany. Tato soutěž byla zcela veřejná a přihlásilo se několik kandidátů. Z nich bylo vybráno pět a vyhrál algoritmus Rijndael. Celá soutěž trvala čtyři roky a Rijndael byl podrobován všemožným testům, aby byl odolný vůči lineární i diferenciální kryptoanalýze. Výsledkem je, že je používán dodnes a je doporučován ve všech svých modifikacích (se 128, 192 i 256 bity dlouhým klíčem).

Zdroje

DOSTÁLEK, Libor a Marta VOHNOUTOVÁ. Velký průvodce infrastrukturou PKI a technologií elektronického podpisu. vyd. 1. Brno: Computer Press, 2006, 534 s. ISBN 80-251-0828-7.

9. Algoritmus AES

Klíčová slova

Algoritmus AES

(Advanced Encryption Standard)

Vítěz vypsané soutěže o nový šifrovací standard, algoritmus Rijndael, je pojmenován přesmyčkou jmen svých autorů Joana Daemena (vlevo) a Vincenta Rijmena (vpravo) obr. 1, představuje symetrickou blokovou šifru. AES nahradil v roce 2002 do té doby platný šifrový standard DES, který byl prolomen a nadále tedy již méně odolný vůči dalším útokům kryptoanalytiků.

Obr. 1 Autoři systému Rijndael - Joan Daemen a Vincent Rijmen

AES dokáže zpracovávat data o velikosti 128 bitů, pomocí šifrovacích klíčů o délce 128, 192 a 256 bitů. (AES tedy existuje ve třech variantách - se 128, 192 a 256 bitovými klíči. My si zde vysvětlíme princip na algoritmu se 128 bitovým klíčem).

Bloky 128 bitového klíče jsou zapisovány jako 16 bytů (1 byte = 8 bitů, 128 : 8 = 16), a zapisujeme je v hexadecimální podobě (tabulka ukazuje převody mezi soustavami obr. 2) do matice.

Obr. 2 Převody mezi soustavami

Dokázali byste si vybavit, jak se zapisují bity do algoritmu DES?

jednotlivé bity se zapisují po řádcích

Velký rozdíl oproti algoritmu DES je, že zde se zapisují jednotlivé byty a že se zapisují po sloupcích.

Před samotným principem šifrování AES se podíváme na jednotlivé operace, které musíme znát, abychom mohli tento standard použít. Jako obvykle potřebujeme z hlavního klíče, jenž má 128 bitů, vytvořit subklíče. Této operaci se opět říká expanze klíčů.

Expanze klíčů

Hlavní klíč je dlouhý 128 bitů, čili 16 bytů. Těchto 16 bytů umístíme do matice po sloupcích.

Princip generování je velmi jednoduchý, ovšem na vysvětlení se může zdáti dost chaotickým.

Musíme vygenerovat deset podklíčů.

Napadlo by vás, jak by mohl takový podklíč vypadat? Jestli je to matice? Jak by mohl být dlouhý? Co s ním vlastně budeme dále dělat a k čemu ho potřebujeme...

klíče potřebujeme k přičtení k upravenému bloku dat, který šifrujeme
jelikož zde mluvíme o bitovém přičtení - čili operaci modulo - musí být klíč stejně dlouhý jako text, ke kterému ho chceme přičíst
každý podklíč tedy musí mít rovněž 16 bytů
a těchto 16 bytů musí být umístěno do matice po sloupcích

Poznámka: Předtím, než se pustíme do samotného generování, je důležité si říci, že podklíče se nedají generovat tak, jak bychom chtěli - například teď bychom chtěli vygenerovat podklíč K5. To nelze. Jednotlivé sloupce totiž generujeme postupně dle vzorečků a ty jsou na sebe navzájem navázané. Tudíž nejdřív musíme vygenerovat sloupce pro podklíč K1, poté sloupce pro podklíč K2 a takhle postupně až pro podklíč K10.

Generování sloupců W4, W8, W12....Kde se vzali sloupce? Hlavní klíč jsme umístili do matice po sloupcích. Tyto sloupce označíme W0, W1, W2 a W3. Podklíč K1 budou tedy logicky tvořit sloupce W4, W5, W6 a W7.Nyní si ukážeme vzorce pro výpočet bytů prvního sloupce každého podklíče. Jedná se tedy o sloupce s označením W4, W8, W12, W16 .... W40. Přehledně je to vyobrazeno na obrázku 3.
Obr. 3

Následně se podíváme na generování zbylých sloupců.Generování sloupců W5, W6....W41, W42, W43Generování ostatních sloupců probíhá takto obr. 4

Obr. 4

Tímto způsobem tedy postupně dostaneme všech deset podklíčů.Pro generování podklíčů jsou připravena zvláštní cvičení.Vedle klíče vstupuje do algoritmu i otevřený text - v tomto případě je zadáván jako blok bitů, které se převedou na byty. Operace, které na otevřený text budou aplikovány, jsou čtyři:

1. SubByte (X, Y) - bytová substituce2. ShiftRow - rotace3. MixColumns - vynásobení mixovací maticí4. AddRoundKey - k transformované matici je přičten klíč.

1. SubByte (X, Y) - bytová substituce

Vstupem do algoritmu je text, tento text uspořádáme do matice podle schématu a operace SubByte nahradí - substituuje každý byte podle tabulky obr. 5. Tím se zabraňuje možnosti použití útoků založených na algebraických vlastnostech.

Obr. 5 Tabulka operace SubByte

Příklad: pokud budeme mít byte 1 a 9, první souřadnice (X) určuje řádek nahrazení, druhá souřadnice (Y) ukazuje sloupec nahrazení. Průsečík je potom výsledný nahrazující byte. Zde je tedy X = 1, Y = 9 a nahrazující byte můžete odečíst z obrázku obr. 6.

Obr. 6 Příklad substituce u operace SubByte

2. ShiftRow - rotace

Po substituci je matice podrobena rotaci. Rotace (či operace ShiftRow) probíhá v jednotlivých řádcích matice a to tak, že první řádek zůstane nezměněn, druhý bude posunut o jednu pozici vlevo, třetí řádek o dvě pozice vlevo a čtvrtý řádek o tři pozice vlevo. Schematicky je to uvedeno zde obr. 7.Operace ShiftRow je pak použita i u generování klíčů, ale je aplikována na sloupce. Jednotlivé byty sloupce tedy „poskočí“ o jednu pozici nahoru a první byte se posune na poslední pozici.

Obr. 7 Operace ShiftRow

3. MixColumns - vynásobení mixovací maticí

Zrotovaná matice se dále upraví operací MixColumns. Vedle zrotované matice je zde vstupem i matice mixovací, která zabezpečí vynásobení. Pokud dojde k přetečení u jednotlivých operací, je zde použito XORování tzv. Galoisovým číslem. Operace MixColumns je výpočetně složitější a je jí věnováno jedno z připravených cvičení, kde je postup podrobně vysvětlen na příkladu. Využívá se zde násobení matice maticí, jak jste si mohli vyzkoušet v minulém jednoduchém cvičení a operace modulo.

4. AddRoundKey - k transformované matici je přičten klíč

K substituované, zrotované a vynásobené matici už tedy nezbývá nic jiného než přičíst subklíč, který jsme získali hned na začátku expanzí. Přičtením zde rozumíme operaci modulo.Celý tento postup je nutno aplikovat v deseti po sobě jdoucích iteracích. Jediný rozdíl poslední iterace je ten, že vynechává operaci MixColumns.Nyní jsme si popsali průběh všech operací, které v algoritmu probíhají, pojďme se tedy podívat přímo na princip, který je demonstrován na příkladu.

Binární operace sčítání modulo a XOR

Jelikož se zde stále bavíme o bytech, které jsou umístěny v matici, bylo by užitečné ukázat si, jak taková matice vypadá binárně, neboť operace, o kterých je řeč, probíhají v oblíbených jedničkách a nulách.Na obrázku jsou tedy dvě matice, první představuje otevřený text (OT), druhá potom znázorňuje matici s klíčem. Obě jsou v hexadecimálním tvaru a poté v binárním tvaru. Na prvních sloupcích obou matic je ukázán postup operace sčítání modulo a poté XOR, čili porovnávání jedinečnosti obr. 8. Poznámka: Binární operace jsou zde nastíněny velmi obecně, protože je připraveno cvičení, kde na sebe logicky navazují a budete si moci jejich aplikaci náležitě vyzkoušet a užít.

Obr. 8 Ukázka operace modulo a XOR

Shrnutí

Obecně jsme si přiblížili podstatu algoritmu AES, který nahradil již nevyhovující DES. Ukázali jsme si jednotlivé operace a dílčí segmenty, které budeme muset při aplikování tohoto algoritmu použít.

Zdroje

DOSTÁLEK, Libor a Marta VOHNOUTOVÁ. Velký průvodce infrastrukturou PKI a technologií elektronického podpisu. vyd. 1. Brno: Computer Press, 2006, 534 s. ISBN 80-251-0828-7.JIROUŠEK, Radim. Principy digitální komunikace. Vyd. 1. Voznice: Leda, 2006, 309 s. ISBN 80-733-5084-X.

10. Cvičení: Operace modulo a XOR

Zadání

Vezmeme stejné zadání, jako je nastíněno při vysvětlování.

Otevřený text je: 34 D4 6B 76 90 12 11 A2 D3 F1 96 25 C1 E3 A6 72

Klíč je: 21 23 13 1A 2B 3C 4D 45 65 87 23 56 98 A4 97

Cvičení má několik bodů, které je třeba splnit:

zapsat byty klíče i otevřeného textu do matic
matice zapsat jak v binární, tak hexadecimální podobě
provést operaci sčítání modulo na všechny prvky matice (sečíst matice k sobě) a výslednou matici zvýraznit
po sloupcích (to znamená na 4 prvky výsledné sečtené matice) aplikovat funkci XOR
výsledné čtyři XORované výsledky opět zvýraznit a převést do obou soustav

Nezapomeňte, že jedničky, které přetečou (dostanete se o řád výš), se u sčítání modulo jednoduše zahazují.

Tipy pro řešení

pozorně si přečtěte zadání
použijte výsledky, které jsou již k dispozici
pro převody mezi soustavami má oblíbený MS Excel výborné funkce, které výrazně urychlí práci
nezapomeňte jednotlivé výsledky zvýraznit

Návrh řešení

11. Princip algoritmu AES

Princip algoritmu AES

Prošli jsme si všechny operace, které potřebujeme pro zašifrování dle tohoto kryptografického systému.

Shrňme si, co víme, co potřebujeme, a co budeme mít k dispozici pro použití::

- vstupem do algoritmu je:
otevřený 128 bitový text, který je rozdělen na 16 bytů a ty umístěny po sloupcích do matice obr. 1
Obr. 1 AES - matice otevřeného textu

klíč (hlavní) obr. 2
Obr. 2 AES - matice klíče

- z hlavního, nám známého klíče, je potřeba expanzí vytvořit subklíče- operace, které probíhají, jsou:

operace, kdy se k matici 128 bitového textu přičte matice uspořádaná z bytů hlavního klíče
operace SubByte - každý byte je substituován obr. 3
operace ShiftRow - substituovaná matice je zrotována obr. 4
operace MixColumns - zrotovaná matice je poté vynásobena mixovací maticí
operace AddRoundKey - přičtení odvozeného klíče, který je pro každou rundu jiný. (Sčítání matice s maticí bylo již ukázáno v předchozím cvičení)

Obr. 3 AES_ operace SubBytes

Obr. 4 AES - operace ShiftRow

- při operacích používáme předem dané prvky

expanzi subklíčů
substituční tabulku (někdy také Rijndaelův S-box)
mixovací matici
přičtení klíče k transponované matici

Takto probíhá deset iterací, přičemž v poslední iteraci se vynechává operace MixColumns.

Schéma jedné iterace lze vidět zde obr. 5.

Obr. 5 AES - schéma jedné rundy

Dešifrování AES

Dešifrování tohoto systému probíhá opět opačným způsobem než kryptografie, při znalosti klíče.

Ke všem operacím, které jsou použité pro šifrování, existují jejich inverzní dvojice, které jsou nedílnou součástí dešifrovacího algoritmu.

K SubByte - InvSubByte; ShiftRow - InvShiftRow; MixColumns - InvMixColumns. Klíče se poté přičítají ve stejném místě, ale v opačném pořadí než při šifrování. Principielně je postup stejný jako jsme si ho ukazovali u algoritmu DES - vzpomínáte?

Kryptoanalýza, útoky a prolomení

Pokud ovšem neznáme klíč, a chceme se k takto zašifrovaným informacím dostat, máme prozatím smůlu.

Jeden z nejvýznamnějších pokusů o útok předpokládá, že lze problém nalezení klíče vyřešit převodem na kvadratické rovnice - těch by bylo kolem 8000, a bylo by potřeba vypočítat přibližně 1600 proměnných.

Dokážete si to představit?

Žádný z útoků, který byl realizován, zatím nepotvrdil, že by tento kryptosystém byl prolomen. O šifře můžeme říci, že je bezpečná, je odolná vůči útoku hrubou silou. Jediné, čeho je možné se obávat, je vývoj kvantových počítačů, které by mohly šifru prolomit.

Slabinou je zde - jako u všech symetrický algoritmů - stejný klíč a jeho transport.

Shrnutí

Ukázali jsme si princip jednoho z dalších symetrických algoritmů, kterým je AES. Přiblížili jsme si jeho konstrukci, generování klíčů i jednotlivé iterace. Dále jsme si řekli, jak vypadá deširování při znalosti klíče, a jak je prozatím nemožné AES „obejít“, pokud klíč nemáme.

Zdroje

DOSTÁLEK, Libor a Marta VOHNOUTOVÁ. Velký průvodce infrastrukturou PKI a technologií elektronického podpisu. vyd. 1. Brno: Computer Press, 2006, 534 s. ISBN 80-251-0828-7.

JIROUŠEK, Radim. Principy digitální komunikace. Vyd. 1. Voznice: Leda, 2006, 309 s. ISBN 80-733-5084-X.

12. Cvičení: Odvozujeme podklíče

Zadání

Nastíníme si problematiku generování podklíčů z klíče.

Klíč je zadáván jako 128 bitový řetězec. Do tabulky ho zapisujeme jako 16 bytů, které nám tedy vytvoří tabulku 4x4. Těchto 16 bytů také zapisujeme po sloupcích.

Je důležité uvědomit si, jak musí vypadat podklíče. Jelikož zde pracujeme s maticemi, musí být dodržována pravidla pro jednotlivé operace (například musí být dodržen stejný počet řádků a sloupců, pokud chceme matice mezi sebou násobit - vzpomínáte z předchozích článků?) Podklíče tedy všechny musí být uspořádány v matici 4x4.

Hlavní klíč máme zadán zatím pouze obecně:

K₀ K₁ K₂ K₃ K₄ K₅ K₆ K₇ K₈ K₉ K₁₀ K₁₁ K₁₂ K₁₃ K₁₄ K₁₅

Nyní se tedy budeme věnovat generování sloupců u prvního podklíče, který bude použit pro první rundu algoritmu AES. Sloupce si označíme W₀, W₁, W₂, W₃, jak je vidět na obrázcích, jinak se generují sloupce W₄, W₈, W₁₂... a stejně by se pokračovalo pro sloupce, jejichž označení je násobkem čísla 4 a jejichž umístění je na první pozici nového podklíče; a odlišným způsobem se generují sloupce W₅, W₆, W₇... které nejsou násobkem čísla 4.

Povšimněte si provázanosti mezi vznikem klíčů - bez sloupce W4 nelze generovat sloupec W5, analogicky bez sloupce W8 nelze generovat následující. Současně s tím nelze ani bez znalosti sloupců W6 generovat W7 atd.

Nebude tedy nic těžkého odvodit odpovídající podklíče, když hlavní klíč bude zadán třeba takto:

1A 7C 15 17 26 AE C1 A6 AB C5 05 90 09 CD 09 3C

1. zapište klíč v hexadecimální i binární podobě do matice

2. vygenerujte sloupec W4

3. následně vygenerujte sloupce W5, W6 a W7 - a máte vytvořený podklíč1

4. použijte sloupec W7 pro vytvoření sloupce W8

5. analogicky pro všech 10 podklíčů

Generování sloupců W4, W8.....

Generování sloupců W5, W6, W7, W9....

Obrázek 1. Generování sloupců W4, W8...

Tipy pro řešení

pozorně si přečtěte zadání

podívejte se také na typovou ukázku, jak se generují jednotlivé sloupce

Návrh řešení

13. Cvičení: Operace MixColumns

Zadání

Operace MixColumns je třetí a nejobsáhlejší operací v jedné rundě u algoritmu AES. Nyní se podíváme na její jednotlivé části.

Vstupem je zrotovaná matice po operaci ShiftRow. Dalším vstupem je poté mixovací matice, která je vždy stejná. Operujeme zde také s tzv. Galoisovým číslem, které je také neměnné a je potřebné pro zúžení bloku dat. Násobení matice maticí jsme již probírali - zde se ovšem násobení převání na polynomické násobení.

Mixovací matice zabezpečuje násobení. Násobení může probíhat třemi způsoby.

Násobení 1 - je klasické opsání čísla (jako u násobení klasického)

Násobení 2 - nám polynomicky vynásobí číslo dvěma (v případě potřeby je již zde aplikováno Galoisovo číslo pro zúžení počtu bitů)

Násobení 3 - uděláme jako násobení 2 a k výsledku ještě jednou modulo přičteme číslo, (v případě potřeby i zde aplikujeme Galoisovo číslo pro zúžení počtu bitů)

Galoisovo číslo se aplikuje na blok bitů pomocí logické funkce XOR.

Výsledné čtyři bloky dat se k sobě přičteme a získáme jednu buňku ve výsledné matici po operaci MixColumns.

Přehledně a srozumitelně je to vyobrazeno zde.

Všimněte si především doprovodných komentářů a vysvětlujících šipek.

Na základě tohoto návodu byste měli být schopni dopočítat všechny buňky ve výsledné matici.

Dbejte na správné pořadí matic (mixovací maticí násobíme zleva), je zapotřebí být opravdu pozorný při sepisování jednotlivých bloků pod sebe. Zvláště pak je důležité ovládat ooperace XOR a sčítání modulo.

Zadání tohoto cvičení tedy zní:

Dopočítejte všechny buňky výsledné matice.

Tipy pro řešení

důkladně si projděte přiložený návod, jak provést operaci MixColumns
je dobré si návodný obrázek opatřit vlastními poznámkami k dané problematice
velmi důležité je být pozorný jak při provádění sepisování, sčítání modulo a operace XOR, tak i u obyčejného opisování (kopírování) bloků dat z jednoho místa na druhý
všímejte si návodných šipek

Návrh řešení

14. IDEA, Blowfish a Twofish

Klíčová slova

IDEA, Blowfish a Twofish

Podrobně jsme se podívali na princip symetrických blokových algoritmů DES a AES. Oba tyto systémy jsou založeny na podobném principu a jejich přínos v oblasti kryptologie je obrovský.

DES i po svém prolomení přináší poznatky do nových oblastí kryptoanalýzy - jinými slovy díky snaze o prolomení DES se rozvinula nová metoda dešifrování - mluvili jsme o ní v minulých článcích?

Vybavíte si ji ještě?

diferenciální kryptoanalýza

AES naopak přináší dočasnou jistotu pro šifrování dat, neboť zatím prolomen ještě nebyl, ačkoli útoky jsou známé.

Ovšem šifrování dat nestojí pouze na těchto dvou standardech. Nyní se spolu podíváme na některé další algoritmy, které mohou být spolehlivé a bezpečné pro šifrování vašich dat. Protože znáte principy blokových symetrických šifer, berte tento výčet opravdu pouze jako přehled dalších možných kryptografických symetrických systémů.

Algoritmus IDEA (International Data Encryption Algorithm)

Algoritmus IDEA představuje symetrickou blokovou šifru, která používá délku bloku 64 bitů a klíč je dlouhý 128 bitů. Pro nekomerční použití je dostupná volně, jinak je patentována v mnoha zemích.

Jako nový kryptosystém byl publikován v roce 1991. Je součástí PGP (Pretty Good Privacy), implementována je ale také v protokolu SSL. O způsobech ochrany bude ještě řeč.

Princip algoritmu

potřebujeme klíč, přičemž pojem klíč opět chápeme ve významu hlavní klíč, ze kterého je generováno x podklíčů
zde potřebujeme pro jednu rundu šest unikátních podklíčů (dohromady tedy z klíče je nutno vygenerovat 52 subklíčů)
hlavní klíč, který má 128 bitů, dá vzniknout prvním osmi klíčům, rozdělením na osm 16 bitových řetězců; poté je klíč rotován o 25 pozic vlevo a opět dělen na osm 16 bitových klíčů; tato operace se opakuje do té doby, než získáme všech 52 subklíčů obr. 1.
Obr. 1 IDEA - generování podklíčů

Tento kryptosystém využívá řadu osmi po sobě následujících iterací, přičemž poslední iterace je někdy nazývánapůlrunda. Celý systém tedy potřebuje 8,5 rundy pro zašifrování. (Proto je zapotřebí 52 klíčů - 6 x 8 + 4)Jeho inovace je v použití tří odlišných grup. Tyto grupy jsou NÁSOBENÍ, SČÍTÁNÍ A NONEKVIVALENCE.Co je to grupa a non....?Zkusili byste si vzpomenout na základě vašich již nabytích znalostí a zkušeností, co to je grupa a axiom?

Axiom je výrok, který se bere za platný a nemusí se již nijak dokazovat. (pro příklad - pravdivostní tabulky funkcí OR, AND, XOR, jsou dané, neměnné a jasné)
Grupa je potom postup, či struktura, která používá dané funkce pro své operace a splňuje při tom použité axiomy.

Po přeložení do češtiny - systém IDEA používá dané bitové operace (AND, OR a XOR) jako součást iterací v souladu s pravidly a tvrzeními, které tyto funkce přináší.

64bitový vstupní otevřený text je rozdělen na čtyři 16bitové bloky.
ty vstupují právě do operací OR, AND a XOR, jejichž pravdivostní tabulky jsou zde obr. 2

Obr. 2 Pravdivostní tabulky vybraných logických funkcí

operace jsou nahrazeny schematickou značkou.

modré kolečko = XORzelený čtvereček = ANDčervené kolečko = OR

k 16bitovému bloku otevřeného textu je přiřazenou operací aplikován vygenerovaný subklíč; takto probíhá všech 8 rund.
v poslední rundě jsou zbylé 4 subklíče operací XOR spojeny s posledními 16bitovými bloky a po jejich sloučení získáváme 64bitový šifrovaný text.

Schéma rundy si můžete prohlédnout zdeobr. 3.

Obr. 3 IDEA - schéma rundy algoritmu

DešifrováníJako u většiny symetrických šifer probíhá dešifrování stejným způsobem jako šifrování - jen opačně. Klíče jsou použity v opačném pořadí (při dešifrování šifrovaného textu v první rundě použijeme poslední klíče, a aplikovat budeme inverzní operace). Inverzními operacemi rozumíme opačné k těm, které byly použity při šifrování.Vzpomněli byste si z matematiky?operace, které tvoří dvojice - jsou negované

AND - NAND (and a negovaný and)
OR -NOR (or a negovaný or)
XOR - IOR (exklusive a inklusive or)

Kryptoanalýza a útokyJelikož nebyla zjištěna matematická slabost, díky použitým funkcím, je šifra odolná do jisté míry jak proti diferenciální tak i lineární kryptoanalýze.Útok, který se může zdát jako nejlepší, je znám od roku 2004. Ovšem problém je, že byl testován na systém, který pracoval „pouze“ s pěti rundami. IDEA šifruje průběhem 8,5 rundy, a je tedy považována za bezpečnou.

Blowfish

Další ze známých, veřejně dostupných a spolehlivých symetrických algoritmů je Blowfish. Byl vytvořen jako náhrada za DES a publikován v roce 1993. Protože není patentovaný, je veřejně dostupný a pro nekomerční účely ho mohou používat všichni.Protože je založen na podobném principu jako DES, používá S-boxy.Zapátrejte nyní v paměti a zkuste si vybavit, co je to takový S-box a k čemu sloužil...

S-box - mění délku vstupního textu
výstupem je pak kratší/delší text, podle potřeby šifry
S-box zaručuje nelineární úpravu
zajišťuje zvýšení bezpečnosti obr. 4

Obr. 4 DES S-Boxy

Vstupem do algoritmu jsou potom 64bitové bloky a délka klíče je zde proměnná. Pohybuje se mezi 32-448 bity.

Twofish

Jak již název napovídá, Twofish je vylepšená verze předchozího algoritmu. Je to opět bloková symetrická šifra avylepšení zde spočívá v rozšíření délky vstupního textu.Two - čili dva - zde znamená dvojnásobná délka vstupního textu - ten zde tedy má 128 bitů. Proměnný klíč může mít až 256 bitů. Zajímavostí je, že při šifrování 256 bitovým klíčem je tento algoritmus rychlejší než nám již známý AES.Publikován byl v roce 1998, a protože není patentován, může být rovněž používán všemi.Twofish se také zúčastnil jedné soutěže, o které již byla řeč. Zapátrejte v paměti, co to bylo za soutěž.

soutěž o nový šifrovací standard vyhlášená NIST
tuto soutěž vyhrál algoritmus Rijndael, který je dnes znám jako AES

Shrnutí

Po podrobnějším vysvětlení algoritmů DES a AES je zde již jen „výčet“ algoritmů, které rovněž spadají do rodiny symetrických šifer.Řekli jsme si také, co je to axiom a grupa a společně zopakovali logické operace.

Zdroje

15. Cvičení: Runda v algoritmu IDEA

Zadání

Jak jsme si říkali ve studijním článku o této šifře, délka otevřeného textu je 64 bitů, délka klíče pak 128 bitů a probíhá 8,5 rundy pro celkové zašifrování.

Cvičení je pouhý zlomek toho, jak celý algoritmus vypadá, nicméně pro ukázku je zcela postačující.

Mějme tedy 8 bitů dlouhý otevřený text a 12 bitů dlouhý klíč.

Otevřený text: 01100101

Klíč: 110101101100

Zadání tedy zní: Použijte uvedený otevřený text a příslušný klíč pro realizaci průběhu první rundy. Šifrovací algoritmus je IDEA.

Tipy pro řešení

vezměte na vědomí, že probíhá pouze první runda, takže s klíčem se toho zase až tolik neděje
připravte si pravdivostní tabulky potřebných logických funkcí
a jednoduše proveďte první iteraci
vzpomeňte si, co již bylo řečeno o tomto algoritmu

Návrh řešení

16. RC4, RC5, RC6...

Klíčová slova

RC4, RC5, RC6...

Přes IDEU, Blowfish a Twofish se podíváme dále...

Algoritmus RC4

Algoritmus, který si představíme nyní, je opět z rodiny symetrických šifer. Byl navržen v roce 1987 a jeho vývoj byl utajován. Autoři se báli, že bude použit pro konkurenční aplikace. Algoritmus je využíván u aplikací společnosti Microsoft Windows, u protokolů SSL (Secure Sockets Layer), WEP (Wired Equivalent Privacy) i WPA (WiFi Protected Access).

Jako obvykle nám do něho vstupují dvě vstupní proměnné - otevřený text a klíč. Klíč má délku mezi 40-256 bity. Otevřený text nám vstupuje do algoritmu v bytech, je rozdělen na bloky po 256 bitech.

A jaký je tedy princip?

Když jsme si zkoušeli algoritmus IDEA, využívali jsme pravdivostní tabulky jisté logické funkce. Vzpomenete, o jakou funkci se jednalo?

XOR (exclusive OR)

Klíč je pomocí této zmíněné logické operace zkombinován s otevřeným textem. Tím se vytvoří šifrovaný text.

Dešifrování

Dešifrujeme symetrickou šifru, takže musíme mít stejný klíč, jako při šifrování otevřeného textu. Musí být tedy vygenerována stejná sekvence po sobě jdoucích bitů, které budou zkombinovány se šifrovým textem a získáme text otevřený. Kombinace probíhá stejnou logickou funkcí.

Podívejte se na pravdivostní tabulku a zamyslete se proč.

XOR - zkouší shodnost/jedinečnost

Ačkoli se tento kryptosystém zdá být dostatečně bezpečný, rychlý i spolehlivý, bohužel nedosahuje dnešních norem pro bezpečnou šifru, protože již je znám způsob možného prolomení. Pokud se používá relativně krátký klíč (v řádů desítek bitů) a používá se delší dobu opakovaně, je prolomení snadné. Když ovšem použijeme dostatečně silný klíč a měníme ho, tak je systém relativně bezpečný a data chráněna.

Známé útoky

RC4-drop(n) - z roku 2001 je znám způsob prolomení právě na základě opakovaného používání klíče. Pokud tedy budeme mít hodně zpráv zašifrovaných pomocí stejného klíče, můžeme zde aplikovat analýzu a postupem zjišťovat správný klíč.

Pamatujete si, kde se tento postup také osvědčil? Bylo to ve 20. století u jednoho známého šifrovacího stroje...

Alan Turing a jeho taháky k Enigmě

Algoritmus RC5

Algoritmus RC5 představuje symetrickou blokovou šifru, která byla publikovaná v roce 1994. Je rozšířením svého předchůdce. Velikost klíče se zde pohybuje mezi 0-2040 bity.

Algoritmus RC6

Jak název již napovídá, tak algoritmus RC6 je vylepšenou verzí RC5. RC6 a byl publikován roku 1998. Zdokonalen je přidáním funkce násobení. Délka klíče se může měnit v závislosti na potřebách uživatele. Klíče mohou být 128, 192 a 256bitové, velikost bloku otevřeného textu je potom 128 bitů.

Algoritmus RC6 se účastnil výběrového řízení na nový šifrovací standard. Tuto soutěž vyhlásil NIST. Vítězem se stal konkurent, algoritmus Rijndael, který je dneska znám a používán jako AES.

Závěrem o symetrických šifrách je nutno říci ještě jednou to, co je nejen zde neustále opakováno. Hlavní úskalí symetrické šifry je bezpečný transport klíče. Všechny symetrické šifry používají stejného klíče jak pro šifrování, tak pro dešifrování, proto je utajení klíče velmi podstatné.

Teď se ovšem podíváme na algoritmy, které jsou založeny na naprosto odlišném principu. Odtajníme si krásy asymetrického šifrování...

Shrnutí

Posledními symetrickými algoritmy, o kterých byla řeč, byly algoritmy RCx.

Zdroje

DOSTÁLEK, Libor a Marta VOHNOUTOVÁ. Velký průvodce infrastrukturou PKI a technologií elektronického podpisu. vyd. 1. Brno: Computer Press, 2006, 534 s. ISBN 80-251-0828-7.

JIROUŠEK, Radim. Principy digitální komunikace. Vyd. 1. Voznice: Leda, 2006, 309 s. ISBN 80-733-5084-X.

Website:	Moodle ZČU
Kurs:	KVD/UIN Úvod do informatiky pro vzdělávání - šablona
Buch:	Symetrické šifrování

Gedruckt von:	Nepřihlášený host
Datum:	Sonntag, 8. November 2026, 17:40

Symetrické šifrování

Inhaltsverzeichnis

1. Feistelova šifra a algoritmus Lucifer

Feistelova šifra a algoritmus Lucifer