Cryptology

• stejně dlouhý nebo delší než šifrovaná zpráva
• je skutečně náhodně generován
• je použit jednou a pouze jednou

Pak máte prokazatelně bezpečnou šifru zvanou one time pad. Váš skutečný algoritmus může používat polyalfabetickou substituci nebo dokonce prosté xorování zprávy s klíčem, pokud splňujete tři výše uvedená kritéria.

Jednorázovou podložku nelze nikdy prolomit. Z matematického hlediska je to každopádně dokonalé šifrovací schéma.

Playfair

Jedná se o příklad polygrafické substituční šifry. Klíčem je permutace {A..I,K..Z},například:

 Z C B M L G D A Q E T U O K H F S X V N P I Y R W

Chcete-li zašifrovat, vypište otevřený text (bez mezer a interpunkce), přičemž mezi zdvojená písmena a v případě potřeby na konec vložte křížek, aby měl text sudou délku.Pak pro každou dvojici písmen:

• Nechť $(a,b)$ je řádek a sloupec prvního znaku a $(c,d)$ je řádek a sloupec druhého.
• Pokud $a \neq c$ a $b \neq d$, pak vraťte $(a,d)(b,c)$.
• Pokud $a = c$, pak vrátíme $(a,(b+1) \bmod 5)(c,(d+1) \bmod 5)$.
• Pokud $b = d$, pak vrátíme $((a+1) \bmod 5,b)((c+1) \bmod 5,d)$.

Dekódování probíhá podle opačných pravidel. Playfairova šifra je dost nezabezpečená.

Čtyřčtverec

Šifruje digrafy jako Playfair, ale o něco silnější, protože umožňuje zdvojená písmena a nevydává obrácené digrafy šifrového textu pro obrácené digrafy jednoduchého textu. Příklad

 a b c d e G I V E M f g h i k L B R T Y l m n o p O D A H C q r s t u F K N P Q v w x y z S U W X Z P R E M A a b c d e T U O I Z f g h i k N S H F L l m n o p V B C D G q r s t u K Q W X Y v w x y z

Okay, takže o něco silnější než Playfair, ale co? Počítače to rozlousknou za pár vteřin nebo možná minut (při dostatečném množství šifrového textu).

Jednoduchá bloková transpozice

Nejjednodušší transpoziční šifra rozdělí zprávu do bloků o velikosti n a pak každý blok zakóduje podle permutace $(1..n)$.

Sloupcová transpozice

Zprávu vypíšeme po řádcích do mřížky a pak ji přečteme po sloupcích. Naprosto nezabezpečené. Klíčem je právě počet řádků. Uhádněte to.

Železniční plot

Železniční plot není o nic lepší než ten předchozí, jen funkčnější. Klíčem je počet kolejnic, na které zapisujete otevřený text způsobem nahoru a dolů, přičemž šifrový text generujete čtením po jedné kolejnici.

Příklad: Pro zakódování "fill out and file a WS2475 form" na 4 kolejnicích:

 f t l 4 m i u a i e 2 7 r l o n f a s 5 o l d w f

poté přečtete šifrový text "ftl4miuaie27rlonfas5oldwf". To je triviální k prolomení. Stačí odhadnout $k$.

Kombinace substituce a transpozice

Samotná transpozice je velmi slabá; substituce je slabá; jejich kombinace je lepší. Můžete kombinovat spoustu klasických substitučních šifer s různými transpozicemi nebo použít některé speciální kombinační šifry, například bifid. Také většina slavných rotorových strojů a moderních šifer používá tuto kombinaci; ve skutečnosti tyto transformace používají mnohokrát.

Bifid

Tato nahrazuje písmena jejich souřadnicemi v mřížce a na souřadnicích provádí sloupcovou transpozici. Příklad:

 Z C B M L G D A Q E T U O K H F S X V N P I Y R W

Napište souřadnice (řádek, sloupec) pod každé písmeno otevřeného textu (např, „A“ je v řádku 1, sloupci 2; „T“ je v řádku 2, sloupci 0 atd.):

 ATTACKATDAWN 122102121143 200213201244

Poté odečtěte v řádcích, seskupte po dvou a vyhledejte písmena šifrového textu:

 122102121143200213201244 A U B A D R T B Q T A W

Trifid

Podobně jako Bifid, ale na kostce. Příklad:

 Z C B M L F V N P G D A Q E X I R W T U O K H S Y . J

Chcete-li šifrovat, napište nejprve souřadnice:

 ATTACKATDAWN 000001000022 122102121110 200210201221

 000001000022122102121110200210201221 Z C Z O S F H Q V I N .

Enigma

Enigma byl slavný německý rotorový stroj z druhé světové války (ve skutečnosti rodina strojů). většina verzí implementovala polyalfabetickou substituční šifru s periodou 16900 plus zásuvnou desku pro skramblování (transpozici). Klíč se skládal z pořadí rotorů, počáteční pozice každého rotoru, nastavení kroužků a nastavení plugboardu (asi 1,6 × 1020 možností). Každý den byl v kódových knihách (víceméně) předem zveřejněn nový klíč.

Spojenci jej dokázali rozlousknout díky některým slabinám v jeho konstrukci…

• Žádné písmeno se nezašifrovalo samo do sebe
• Samoreciprocita znamenala, že bylo méně možností nastavení šifrátoru

…ale hlavně mnoho slabin ve způsobu jeho použití…

• Bylo opravdu snadné najít šifry. Většina zpráv začínala zprávou o počasí.
• Brzy se objevily klíče zpráv dvakrát po sobě.

…a získáním kódových knih ze zajatých plavidel.

O tom, jak byla Enigma prolomena, se můžete dočíst zNSA,a zWikipedie.

Moderní kryptografické metody

Teď, když máme Shannonovu teorii informace, velmi výkonné počítače a staletí teorie a praxe za sebou, je většina moderních technik:

• pracují s bitovými řetězci, nikoliv s řetězci znaků
• pečlivě maskují vzory a redundance v otevřeném textu
• používají náhodné klíče (které lze použít i opakovaně)
• zajišťují, že velmi malé změny v otevřeném textu ovlivní velkou část šifrového textu (a naopak). Tomu se říká lavinový efekt.

Dále je dobré, když je šifra:

• účinná
• odolná proti chybám

Většina šifer jsou buď blokové, nebo proudové šifry. Blokové šifry vyžadují vyplňování a mohou pracovat v různých režimech (viz Schnierova kniha nebo článek na Wikipedii.)

• ECB – Elektronická kódová kniha
• CBC – Cipher Block Chaining
• CFB – Cipher Feedback
• OFB – Výstupní zpětná vazba

.

• CTR – Counter
• BC – Block Chaining
• PCBC – Propagating Cipher Block Chaining
• CBCC – Cipher Block Chaining s kontrolním součtem

DES

Na Wikipedii

IDEA

Na Wikipedii

RC4

Na Wikipedii

RC6

Na Wikipedii

Blowfish

At Wikipedia

Twofish

At Wikipedia

AES

At Wikipedia

AES je nový standard, který nahradil DES. Stal se vítězem soutěže (v roce 2001), kde byl předložen pod názvem Rijndael, a porazilRC6, Serpent, MARS a Twofish.

Výměna klíčů

Diffie a Hellman (vítězové Turingovy ceny za rok 2015) a jejich přítelMerkle v roce 1976 ukázali, že je možné, aby si dva lidé vyměnili tajný klíč, aniž by se museli skutečně tajně setkat:

• Alice vybere prvočíslo $n$ a pošle ho nepokrytě Bobovi
• Alice vybere prvočíslo mod $n$ (jak najít), zvané $g$, a pošle ho nepokrytě Bobovi
• Alice vybere tajné celé číslo $a$, a pošle čistě $g^a \bmod n$ Bobovi
• Bob vybere tajné celé číslo $b$ a pošle čistě $g^b \bmod n$ Alici
• Alice vypočítá ($g^b \bmod n)^a \bmod n$ a Bob vypočítá ($g^a \bmod n)^b \bmod n$. To je klíč! (Je to $g^{ab} \bmod n$)

Toto je pravděpodobně bezpečné za předpokladu, že $n$ je velmi velké a $\frac{n-1}{2}$ je také prvočíslo, protože i když Eva zná $g$, $n$, $g^a \bmod n$ a $g^b \bmod n$, není znám žádný účinný způsob, jak z nich získat $a$ nebo $b$.To je problém diskrétního logaritmu, pamatujete?

Příklad s malým $n$:

• Alice vybere $n=208799$ a $g=13$ a pošle je Bobovi
• Alice vybere $a=152335$ a Bob vybere $b=98113$
• Alice pošle Bobovi $13^{152335}. \bmod 208799 = 73033$
• Bob pošle Alici $13^{98133}. \bmod 208799 = 147540$
• Alice vypočítá $147540^{152335} \bmod 208799 = 8435$
• Bob vypočítá $73033^{98133}. \bmod 208799 = 8435$
• Tajný klíč je $8435$.

S malými hodnotami $n$ to skutečně nedělejte.

Všeobecně platí, že pokud nezískáte nějakou certifikaci,nepokoušejte se sami zabezpečit žádné systémy reálného světa. Ale samozřejmě se do toho pusťte a naučte sealgoritmy a zatím si procvičte kódování.

Kryptografie s veřejným klíčem

Šifry s veřejným klíčem řeší noční můru správy klíčů u šifer s tajným klíčem, ovšem na úkor rychlosti. Ve skupině $n$ lidí stačí $n$ veřejných klíčů a $n$ soukromých klíčů.

Kryptosystém RSA

Diffie-Hellman nešifruje, pouze vyměňuje klíč, RSA umí šifrovat i dešifrovat. Tady je návod, jak na to. Každá osoba

• Vygeneruje dvě velká prvočísla, $p$ a $q$.
• Vybere si hodnotu $e$ relativně prvočíselnou k $(p-1)(q-1)$.
• Zveřejní svůj veřejný klíč $(N,e)$, kde $N = pq$.
• Vypočítá $d$ = modulární inverzní hodnotu $e$ vzhledem k $(p-1)(q-1)$ a uchová ji v tajnosti.
• Zničí $p$ a $q$.

Teď se podívejte na toto:

• Ali chce Alice poslat zprávu $m$ Bobovi, pošle $c = m^e \bmod N$.
• Bob to snadno dekóduje, protože $m = c^d \bmod N$.

Triviální příklad:

POZOR!
Tento příklad je pouze ilustrační. Nikdy neimplementujte vlastní šifrovací algoritmus. Také se ujistěte, že chápete, jak hrozná je kryptografie s veřejným klíčem s tak malými klíči. Skutečné klíče by měly mít tisíce bitů.

Použijeme 16bitový klíč (NEDĚLEJTE TO IHNED). Vygenerujte dvě náhodná 8bitová prvočísla:

$p = 163\\q = 173$

Vygenerujte 16bitové prvočíslo pro kódovací exponent:

$e = 64013$

Nyní:

$n = pq = 28199 \\d = \mathsf{modInverse}(e, (p-1)(q-1)) = 6797$

Zakódujme řetězec ¿Dónde está ud.?. Zde je v UTF-8:

c2 bf 44 c3 b3 6e 64 65 20 65 73 74 c3 a1 20 75 64 2e 3f

V desítkové soustavě:

194 191 68 195 179 110 100 101 32 101 115 116 195 161 32 117 100 46 63

Nyní na každý aplikujme kódovací funkci::

$194^{64013} \bmod 28199 = 15626$
$191^{64013} \bmod 28199 = 19945$
$68^{64013} \bmod 28199 = 27982$
$\vdots$
$63^{64013} \bmod 28199 = 18384$

Šifrový text je:

15626 19445 27982 22746 2679 7739 16824 23107 9054 23107 8378 16412 22746 5566 9054 881 16824 17864 18384

K dekódování:

$15626^{6797} \bmod 28199 = 194$
$19445^{6797} \bmod 28199 = 191$
$27982^{6797} \bmod 28199 = 68$
$\vdots$
$16824^{6797} \bmod 28199 = 63$

Původní zprávu dostaneme zpět!

Mimochodem
Protože symetrické šifrování je mnohem rychlejší, můžete nejprve vygenerovat tajný klíč a přenášet ho po lince zabezpečené kryptografií s veřejným klíčem. Nyní může veškerá budoucí komunikace používat tento tajný klíč.

Kryptografické hašování

Haš, neboli otisk prstu, kontrolní součet, digest zprávy je bitový vzor (obvykle kolem 160 bitů), který je generován ze zprávy kryptografickou hašovací funkcí. Aby byl hash bezpečný neboli kryptografický, musí být výpočetně nemožné

• najít zprávu, která se hashuje na danou hodnotu (jednosměrnost)
• najít dvě zprávy, které se hashují na stejnou hodnotu (odolnost proti kolizi)

Matematicky řečeno, kryptografická hashovací funkce $H$ vytváří hash ze zprávy, $H(m) = c$, takovou, že $m$ nelze efektivně určit z $c$ a nelze efektivně najít $m_1 \neq m_2$ takovou, že $H(m_1) = H(m_2)$,

Obvykle změna pouhého jediného bitu ve zprávě způsobí, že digest bude vypadat zcela a úplně jinak.

$ cat willThis is my will.I leave 1000 dollars to Aliceand everything else to Bob.Signed, Eve.$ md5sum willc18feb890752c9e680c99d1e909fd761 will$ sed "s/1/9/g" will > Will$ cat WillThis is my will.I leave 9000 dollars to Aliceand everything else to Bob.Signed, Eve.$ md5sum Will85570bc2d0458b1f98f484261dee7d4d Will

Zabezpečený hash poskytuje způsob, jak zjistit, zda se zprávou nebylo manipulováno.

Viz Steve Friedl’s Illustrated Guide to Cryptpgraphic Hashes.

Ověřovací kódy zpráv

Ty jsou podobné kryptografickým hashům s tím rozdílem, že používají tajný klíč, zatímco hashe používají pouze samotnou zprávu.

$MAC(m, k) = c$

Další informace:

• Kódy MAC vs. Hashe na StackOverflow
• Digitální podpisy na Wikpedii
• MAC na Wikipedii

Digitální podpisy

Jak si může být Bob jistý, že zpráva pochází od Alice a ne od někoho jiného? tím, že ji Alice podepíše; tak. V praxi se obvykle podepisuje hash, nikoli celá zpráva.

RSA pro digitální podpisy

Pokud Alice pošle zprávu Bobovi,

• Alice zašifruje m svým soukromým klíčem
• Alice zašifruje Bobovým veřejným klíčem
• Bob dešifruje svým soukromým klíčem
• Bob dešifruje pomocí Aliciným veřejným klíčem

$m = A(B'(B(A'(m)))$

DSA

Na Wikipedii

Kryptanalýza

Jedná se o rozsáhlé téma, kterému se zde nebudeme věnovat. Místo toho je zde uveden seznam technik.

• Frekvenční analýza
• Útok na známý otevřený text
• Útok na známý šifrový text
• Útok na vybraný otevřený text
• Útok na vybraný text. klíčový útok
• Lineární kryptoanalýza
• Diferenciální kryptoanalýza
• Krádež
• Podplácení
• Vydírání

Příklady programování

He, nebudeme si ukazovat, jak si nacvičit vlastní kryptoanalýzu. Podíváme se na některé skutečné exsitující knihovny.

Přenášíte data přes IP síť?
Použijte TLS.
Přečtěte si ale, jestli chcete používat nějaké zábavné kryptografické knihovny.

Příklady v jazyce JavaScript

Reference: Node crypto.

Příklady pro Python

Reference:Kryptografické knihovny Python -Python hashlib -Python secrets

Příklady pro Javu

.