====== 2. Kryptografické algoritmy ======
Principy základních symetrických blokových algoritmů (Feistelovy šifry, DES, AES) a asymetrických algoritmů (RSA, Diffie-Hellman, DSA/ElGamal). Principy konstrukce hašovacích funkcí. Kryptosystémy založené na principu eliptických křivek.

====== Vypracování ======

<box green|Kerckhoffsův princip>Bezpečnost kryptosystému by měla záviset pouze na utajení klíče, nikoli algoritmu. Algoritmus byl měl být všem znám a všemi ověřitelný, že je bezpečný.</box>

===== Principy základních symetrických blokových algoritmů (Feistelovy šifry, DES, AES) =====

Symetrické blokové algoritmy používají tajný klíč sdílený mezi komunikujícími stranami, pracují s bloky dat stanovené délky, na kterou se data musejí zarovnat pomocí paddingu.

Blokové šifry typicky pracují na principu "confusion and diffusion".
  * Confusion -- statistické závislosti mezi plaintextem a ciphertextem musejí být co nejvíce komplexní, to zajišťují tzv. S-boxy.
  * Diffusion -- každý znak změněný v plaintextu změní celý ciphertext využitím permutací, tzv. P-boxů.

==== Feistelovy šifry ====
{{http://upload.wikimedia.org/wikipedia/commons/thumb/f/fa/Feistel_cipher_diagram_en.svg/410px-Feistel_cipher_diagram_en.svg.png?250 | Feistelova síť}}

Šifry, které jsou navrženy jako Feistelova síť.

Tento přístup umožňuje problém návrhu dobré šifry rozdělit na dva podproblémy:
  - Algoritmus, který určí klíč pro každé kolo.
  - Funkce <math>F</math> aplikovaná v každém kole.

Výhodou je, že šifrování i dešifrování je prakticky stejné. Funkce <math>F</math> nemusí být invertibilní, stačí pouze otočit pořadí subklíčů.

V každém kole se pracuje pouze s polovinou vstupu. Feistelovy šifry tedy předpokládají vstup sudé délky, který je rozdělen na poloviny -- <math>(L_0, R_0)</math>.
  * <math>L_{i+1} = R_i</math>
  * <math>R_{i+1} = L_i \oplus F(R_i, K_i)</math>

Následkem toho mají Feistelovy šifry většinou více kol než jiné algoritmy. Ale v jednotlivých kolech jsou opakovány poměrně jednoduché operace. Pro každé kolo je odvozen čerstvý subklíč z klíče.

Zástupci jsou např. Lucifer, DES, Blowfish, Twofish, CAST-128 a další.

Feistelovy šifry je možné zobecnit tak, že šifra pracuje s nestejně velkými částmi vstupu místo polovin. Také je možné vytvořit nehomogenní Feistelovu síť, kde funkce <math>F</math> není ve všech kolech stejná.

=== Zdroje ===
[[http://en.wikipedia.org/wiki/Feistel_cipher]]
[[http://cs.wikipedia.org/wiki/Feistelova_%C5%A1ifra]].

==== DES ====
Data Encryption Standard

Horst Feistel z IBM navrhnul šifru Lucifer, která se po drobných změnách provedených NSA stala FIPS standardem pod názvem DES v roce 1977.

DES má definovanou délku bloku 64 bitů. Délka klíče je 64 bitů (56 bitů bez parity), původní Lucifer pracoval se 128bitovým klíčem.

Feistelova šifra s 16 koly.

Obsahuje iniciální a finální permutace, které po zveřejnění nepřidávají žádnou bezpečnost.

=== Algoritmus generování subklíčů ===
Klíč je rozdělen na poloviny (28 bitů dlouhé). V každém kole je zvoleno prvních 24 bitů z každé poloviny a použito jako subklíč (délka 48 bitů). Obě poloviny jsou mezi koly rotovány o jeden nebo dva bity doleva v závislosti na kole.

=== Funkce F pro každé kolo ===
Pracuje vždy s polovinou vstupu (32 bitů). Vstup funkce <math>F</math> je rozšířen na 48 bitů. Provede se XOR se subklíčem pro dané kolo. Výsledek projde přes S-boxy, kde se každých 6 bitů nahradí 4 bity podle tabulky (nelineární substituce). Nakonec v každém kole jsou data přeskládána podle dané permutace, P-box.

==== ====
Pro dnešní použití je klíčový prostor <math>2^{56}</math> příliš malý, také velikost bloku není dostatečná.

Nejpraktičtější známý útok je útok hrubou silou. DES šifra je odolná vůči diferenciální kryptoanalýze. Pro prolomení všech 16 kol je potřeba <math>2^{49}</math> zvolených plaintextů. Při použití lineární kryptoanalýzy je potřeba <math>2^{43}</math> známých plaintextů.

Změny provedené NSA se týkaly použitých S-boxů, jejichž kriteria návrhu nebyly zveřejněny. Tyto změny vedly ke spekulacím, že NSA přidala backdoor. Po zveřejnění vyšlo najevo, že takto upravené S-boxy zvýšily bezpečnost DES.

=== Triple DES ===
3DES je varianta DES, která používá klíče větší délky.

Délka bloku je původních 64 bitů. Délka klíče může být 56, 112 a 168 bitů.

<math>ciphertext = E_{K_3}(D_{K_2}(E_{K_1}(plaintext)))</math>
<math>plaintext = D_{K_1}(E_{K_2}(D_{K_3}(ciphertext)))</math>

Pro 56b klíč <math>K_1 = K_2 = K_3</math> a 3DES je stejný jako DES. Pouze z důvodu zpětné kompatibility.
Pro 112b klíč <math>K_1 = K_3</math>.

112b klíč odpovídá asi 80b bezpečnosti kvůli útokům se známým plaintextem, případně se zvoleným plaintextem.
168b klíč odpovídá 112b bezpečnosti kvůli meet-in-the-middle útoku.

=== Zdroje ===
[[http://en.wikipedia.org/wiki/Data_Encryption_Standard]]
[[http://en.wikipedia.org/wiki/Triple_DES]]

==== AES ====

Advanced Encryption Standard

NIST vypsal soutěž o novou symetrickou blokovou šifru, která by nahradila DES. Podmínky byly délka bloku 128 bitů, podporované délky klíče 128, 192 a 256 bitů a nová šifra měla být zároveň výkonnější než DES. Z 15 přihlášených vzešlo 5 finalistů: Rijndael, Serpent, Twofish, RC6 a MARS. V roce 2001 byla vítězem vyhlášena šifra Rijndael.

Původní Rijndael mohl pracovat s libovolnou délkou bloku, která byla násobek 32. V AES je délka bloku fixována na 128 bitů.

AES není Feistelova šifra, ale je to tzv. substitution permutation network, tedy také využívá S-boxy a P-boxy. Počet kol závisí na použité délce klíče.

^ Délka klíče ^ Počet kol ^ Označení     ^
| 128 bitů    | 9+1       | AES-128      | 
| 192 bitů    | 11+1      | AES-192      | 
| 256 bitů    | 13+1      | AES-256      | 

V každém kole se provede:
  * nelineární substituce bytů,
  * posunutí řádků matice,
  * promíchání sloupců matice (neprovádí se v posledním kole),
  * XOR se subklíčem pro dané kolo.

Na rozdíl od DES pro šifrování a dešifrování AES jsou potřeba různé obvody.

=== Známé útoky ===
Side-channel útoky na některé implementace, např. OpenSSL.

Nejlepší známé útoky na vlastní šifru jsou pro 7 kol AES-128, 8 kol AES-192 a 9 kol AES-256.

=== Zdroje ===
[[http://en.wikipedia.org/wiki/Advanced_Encryption_Standard]]

===== Principy asymetrických algoritmů (RSA, Diffie-Hellman, DSA/ElGamal) =====

Při použití asymetrických algoritmů má každá strana vlastní klíčový pár skládající se z veřejného a soukromého klíče. Pro zajištění stejné úrovně bezpečnosti jsou potřeba výrazně delší klíče než u symetrických algoritmů.

Výhodou těchto algoritmů je, že odpadá nutnost ustavit sdílený klíč mezi komunikujícími stranami. Na druhou stranu je nějakým způsobem nutné věrohodně propojit veřejný klíč a identitu jeho majitele. PGP využívá tzv. "web of trust", certifikáty vydané ověřenými certifikačními autoritami, atd.

==== RSA ====

Autoři Ron Rivest, Adi Shamir a Leonard Adleman, 1977.

Podobný systém byl vyvinut britskou tajnou službou v roce 1973.

Použití tohoto algoritmu je možné rozdělit do několika fází

  - Generování klíčového páru
  - Šifrování
  - Dešifrování

=== Generování klíčového páru ===
  - výběr 2 prvočísel <math>p</math> a <math>q</math> podobné bitové délky
  - <math>n = p \cdot q</math>, délka <math>n</math> v bitech je délka klíče
  - <math>\varphi (n) = (p-1)(q-1)</math>, <math>\varphi (n)</math> je Eulerova funkce
  - vyber číslo <math>e : 1 < e < \varphi (n)</math> a <math>\gcd(e,\varphi (n)) = 1</math>, dvojce <math>(n,e)</math> je veřejný klíč
  - <math>d = e^{-1} \mod \varphi (n)</math>, dvojce <math>(n,d)</math> je soukromý klíč

=== Šifrování ===
  * <math>c \equiv m^e \mod n</math> a <math>0 \le m < n</math>

Před šifrováním zprávy je zpráva doplněna paddingem, který zajistí, že plaintext nepatří mezi tzv. "insecure plaintexts". Používal se padding definovaný v PKCS#1, ale bylo ukázáno, že pro některé zprávy tento padding neposkytuje dostatečnou úroveň bezpečnosti. Do PKCS#1 byla přidána definice nového schématu OAEP.

=== Dešifrování ===
  * <math>m \equiv c^d \mod n</math>

==== ====
Kromě šifrování je možné RSA algoritmus použít i pro digitální podpis.

  - <math>sig = h(m)^d \mod n</math> vytvoří digitální podpis, <math>h(m)</math> značí hash zprávy <math>m</math>.
  - <math>hash = sig^e \mod n</math>, pokud <math>hash = h(m)</math>, podpis je úspěšně ověřen.

Stejný klíč by neměl být použit pro šifrování a podepisování zpráv zároveň. Výpočty lze urychlit využitím čínské věty o zbytku (CRT).

=== Bezpečnost ===
RSA je považován za bezpečný algoritmus, protože není známý způsob, jak efektivně faktorizovat velká čísla. Není známý žádný polynomiální algoritmus.

Shorův algoritmus umožňuje faktorizovat čísla v polynomiálním čase na kvantovém počítači, tedy existence kvantového počítače by znamenala rozbití RSA.

Bezpečnost RSA závisí na volbě prvočísel <math>p</math> a <math>q</math> a do jisté míry i volba <math>e</math>. Malé hodnoty <math>e</math> a špatně implementovaný nebo žádný padding zvyšují riziko útoku. Často <math>e = 65537</math>, to je považováno za kompromis mezi předcházením těchto útoků a efektivitou šifrovacích operací (pro velká <math>e</math> jsou výpočty složitější). Také je důležitá volba soukromého klíče <math>d</math>. Pokud je <math>d</math> dostatečně malé, pak je možné jej efektivně spočítat z <math>n</math> a <math>e</math>.

== Timing attack ==
Při znalosti specifikace HW a době trvání operací je možné odvodit hodnotu soukromého klíče <math>d</math>.

Jako obrana před tímto útokem se místo <math>c^d \mod n</math> počítá <math>r^e \cdot c^d \mod n</math>. <math>r^e</math> je potom možné odstranit. Pro každý ciphertext je použita nová náhodná hodnota <math>r</math>. Této metodě se říká "cryptographic blinding".

=== Zdroje ===
[[http://en.wikipedia.org/wiki/RSA_(algorithm)]]

==== Diffie-Hellman ====
Algoritmus pro ustavení sdíleného klíče mezi dvěma stranami na nezabezpečeném kanálu bez žádné předchozí sdílené znalosti.

Autoři Whitfield Diffie a Martin Hellman, 1976. Podobný algoritmus byl opět o něco dříve vyvinut britskou tajnou službou.

  - Alice zvolí <math>p, g, a</math>.
  - Alice pošle <math>p, g</math> Bobovi.
  - Bob zvolí <math>b</math>.
  - Alice spočítá <math>A = g^a \mod p</math> a pošle <math>A</math> Bobovi.
  - Bob spočítá <math>B = g^b \mod p</math> a pošle <math>B</math> Alici.
  - Alice spočítá <math>K = B^a \mod p</math>.
  - Bob spočítá <math>K = A^b \mod p</math>.
  - Obě strany nyní sdílejí <math>K = (g^a)^b \mod p = (g^b)^a \mod p</math>.

Běžně používaná hodnota <math>g</math> je 2, 3 nebo 5. Čísla <math>a</math> a <math>b</math> a prvočíslo <math>p</math> musejí být velká.

Diffie-Hellman využívá problém diskrétního logaritmu.

Algoritmus ve své původní podobě nezahrnuje autentizaci stran, je tedy možný man-in-the-middle útok.

Toto schéma je možné rozšířit i pro libovolný počet stran. Tyto strany pak sdílejí jeden tajný klíč <math>g^{x_1 \cdots x_n} \mod p</math>, kde <math>x_1, \ldots, x_n</math> jsou tajné exponenty všech zůčastněných stran.

=== Zdroje ===
[[http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange]]

==== DSA ====

Digital Signature Algorithm, FIPS standard pro digitální podpisy z roku 1991.

=== Generování klíče ===
  * Zvol kryptografickou hashovací funkci <math>H</math>, například SHA-1 nebo SHA-2.
  * Zvol délku klíče <math>L</math> a <math>N</math>, například 2048 nebo 3072. Doporučené hodnoty pro <math>(L, N)</math> jsou (1024, 160), (2048, 224), (2048, 256) a (3072, 256). <math>N</math> musí být menší nebo rovno délce výstupu hashovací funkce.
  * Zvol <math>N</math>-bitové prvočíslo <math>q</math>.
  * Zvol <math>L</math>-bitové prvočíslo <math>p</math> (modulus) takové, že <math>p - 1</math> je násobek <math>q</math>.
  * Zvol číslo <math>g</math>, jehož stupeň modulo <math>p</math> je <math>q</math>, tedy <math>g^q \equiv 1 \mod p</math>, například <math>g = h^{\frac{p - 1}{q}}</math> mod <math>p</math> pro volitené <math>h</math> (<math>1 < h < p - 1</math>). Je nutno zvolit jiné <math>h</math> pokud je výsledek <math>1</math>.
  * Zvol náhodné <math>x</math>, <math>0 < x < q</math>.
  * <math>y = g^x \mod p</math>

Veřejný klíč je <math>(p, q, g, y)</math>. Soukromý klíč je <math>x</math>.

=== Podepisování ===
  * Zvol (pro zprávu) náhodné <math>k</math>, <math>0 < k < q</math>.
  * <math>r = (g^k \mod p) \mod q</math>
  * Pokud je <math>r = 0</math>, zvol jiné <math>k</math> a začni znovu.
  * <math>s = (k^{-1} \cdot (H(m) + x \cdot r)) \mod q</math>
  * Pokud je <math>s = 0</math>, zvol jiné <math>k</math> a začni znovu.
  * Podpis je <math>(r, s)</math>.

=== OVěření podpisu ===
  * Odmítni podpis pokud není splněno <math>0 < r < q</math> nebo <math>0 < s < q</math>.
  * <math>w = s^{-1} \mod q</math>
  * <math>u_1 = H(m) \cdot w \mod q</math>
  * <math>u_2 = r \cdot w \mod q</math>
  * <math>v = ((g^{u_1} \cdot y^{u_2}) \mod p) \mod q</math>
  * Podpis je platný pokud <math>v = r</math>.

==== ====
Hodnota <math>k</math> je pro DSA kritická. Použití stejného <math>k</math> opakovaně, předvídatelného <math>k</math> nebo prozrazení několika bitů <math>k</math> může vést k rozbití DSA.

=== Zdroje ===
[[http://en.wikipedia.org/wiki/Digital_Signature_Algorithm]]

==== ElGamal ====

Autor je Taher ElGamal, 1984.

=== Generování klíčů ===
  - Popis multiplikativní cyklické grupy <math>G</math> řádu <math>q</math> s generátorem <math>g</math>.
  - Zvol náhodné <math>x</math>, <math>1 \le x \le q-1</math>.
  - <math>h = g^x</math>
  - <math>(h, G, q, g)</math> je veřejný klíč.
  - <math>x</math> je soukromý klíč.

=== Šifrování ===
  - Zvol náhodné <math>y</math>, <math>0 \le y \le q-1</math>.
  - <math>s = h^y</math>
  - <math>c_1 = g^y</math>
  - <math>c_2 = m' \cdot s</math>, <math>m'</math> je prvek <math>G</math>, který odpovídá zprávě <math>m</math>.
  - <math>(c_1, c_2) = (g^y, m' \cdot h^y) = (g^y, m' \cdot (g^x)^y)</math> je ciphertext.

=== Dešifrování ===
  - <math>s = c_1^x</math>
  - <math>m' = c_2 \cdot s^{-1}</math>, protože platí <math>c_2 \cdot s^{-1} = m' \cdot h^y \cdot (g^{x \cdot y})^{-1} = m' \cdot g^{x \cdot y} \cdot g^{-x \cdot y} = m'</math>.

==== ====
ElGamal je většinou využíván v hybridních kryptosystémech, symetrický klíč je zašifrován použitím ElGamal a zpráva samotná je šifrovaná symetrickou šifrou.

Bezpečnost ElGamal je založena na problému diskrétního logaritmu.

Existuje i ElGamal algoritmus pro digitální podpisy, který je podobný DSA.

=== Zdroje ===
[[http://en.wikipedia.org/wiki/ElGamal_encryption]]

===== Principy konstrukce hašovacích funkcí =====
Požadované vlastnosti hashovací funkce:
  * výstup pevné délky pro libovolný vstup,
  * malá změna na vstupu vede k velké změně na výstupu ("avalanche effect"),
  * ideálně jednosměrná funkce -- z hashe je prakticky nemožné zrekonstruovat původní data,
  * pro stejný vstup vrátí vždy stejný výstup,
  * uniformní rozdělení výstupů -- každý možný výstup je generován s přibližně stejnou pravděpodobností,
  * slabá bezkoliznost -- pro dané <math>x</math> najít <math>y</math> tak, že <math>h(x) = h(y)</math>,
  * silná bezkoliznost -- výpočetně je velmi náročné najít <math>x</math> a <math>y</math> takové, že <math>h(x) = h(y)</math>.

Hashovací funkce mohou být vytvořeny ze symetrických blokových šifer například pomocí konstrukcí Miyaguchi-Preneel nebo Matyas-Meyer-Oseas.

===== Kryptosystémy založené na principu eliptických křivek =====
Asymetrická kryptografie, která využívá eliptické křivky nad konečnými tělesy.
  * Eliptické křivky jsou takové, které splňují <math>y^2=x^3 + ax + b</math> a,b racionální nebo integer.
  * Počítá se modulo n
  * Pracujeme jen s křivkami, které nemají vícečetné kořeny. (4a^3 + 27b^2 = 0)
  * 2 možné tvary grafů
  * Lze jednoduše sčítat body na křivce (asi i násobit)
  * Křivky mají konečně mnoho bodů, které lze generovat z daných bodů pomocí sčítání

Problém diskrétního algoritmu na eliptických křivkách:
  * hledat k takové, že A.k = B. A,B jsou body na křivce
  * Není znám takový efektivní algoritmus
  * Je třeba hledat eliptickou křivku nad velkými poli.

Převod diskrétního alg. klasického na EC diskr. alg.
  * Plaintext -> bod na eliptické křivce
  * Změnit krypto protokol z modulární multiplikace na sčítání bodů na křivce, exponenciální fce změň na násobení bodů 
  * Spočítej bod, přiřaď cyphertext.

Založeno na problému hledání diskrétního logaritmu náhodné eliptické křivky s ohledem na zvolený bod.

Např. ECDH (Elliptic curve Diffie–Hellman), ECDSA (Elliptic Curve DSA) a další.

Pro zajištění 128bitové bezpečnosti je potřeba křivka nad <math>F_q</math>, kde <math>q \approx 2^{256}</math>. Pro srovnání RSA potřebuje 3072bitové klíče pro dosažení stejné úrovně bezpečnosti.

====== Materiály ======

  * [[https://is.muni.cz/auth/el/1433/podzim2012/PV181/um/std/|Kapitola o kryptografických standardech, Labak I]]
  * [[https://is.muni.cz/auth/el/1433/jaro2011/PA018/um/PA018_2011_L2.pdf| PA018 - Cryptography, its application, key management, standards]]
  * Něco je ve vypracované [[mgr-szz:in-psk:4-psk|4. otázce oboru PSK]]

====== Vypracoval ======
Ondra Mokoš
Předělané eliptické křivky: Marcel Poul
~~DISCUSSION~~