Úvod do kryptografie

V letním semestru 2018/2019 přednáším Úvod do kryptografie [NDMI100]. Budeme se zabývat základy jak teoretické, tak praktické kryptografie a také trochu šířeji počítačovou bezpečností.

Přednáška se koná každou středu od 9:00 v S10.

Průběžně scanuji své poznámky k přednášce. Neslibuji, nakolik přesně odpovídají tomu, co nakonec zaznělo, ale pro základní přehled by mohly být užitečné. Z některých přednášek jsou k dispozici videozáznamy.

Pokud se mnou chcete cokoliv probrat, jste vítáni v mé pracovně S322 na Malé Straně. Případně napište e-mail na adresu mares@kam.mff.cuni.cz.

datum téma poznámky video
27. 2. Kryptografická primitiva (symetrické a asymetrické šifry, hešovací funkce, náhodné generátory). Protokoly a role. Kerckhoffsův princip. Jednoduché protokoly: komunikace více osob, podpisy, autentikační kódy (MAC), hybridní šifry, challenge-response autentikace. Vymýšlíme protokol na aukci: padding, nonce, sekvenční čísla, podpis; co může aktivní útočník. Hádanka: Jak si hodit korunou po telefonu? [P01]
6. 3. Obecné úvahy o bezpečnosti (co chráníme a před kým?). Základní druhy kryptografických útoků. Security level. Různé podoby „narozeninových“ útoků. Jednorázové klíče (one-time pad) a Vernamova šifra. Perfektní bezpečnost a její meze. Rozdělování tajemství a prahová schémata (konstrukce s polynomy). Nástin symetrických šifer: proudové a blokové. Hádanka: Proč šifrování dvěma symetrickými šiframi po sobě nezvyšuje bezpečnost? [P01] [V03]
13. 3. Blokové šifry: triviální příklady, pokus o definici bezpečnosti a ideální bloková šifra. Obecné konstrukce blokových šifer: iterované šifry, substitučně-permutační sítě, Feistelovy sítě. DES: historie, struktura, rozvrh klíčů, kritika, pokusy o záchranu (3-DES). Podobně o AES a.k.a. Rijndael. Na okraj: Vizuální dělení tajemství, proč nechceme používat ECB. [P01] [V04]
20. 3. Jak (ne)používat blokovou šifru: padding, módy ECB, CBC, OFB a CTR, ciphertext stealing. Prosakování informací z CBC a OFB/CTR. Útok na CBC pomocí padding orákula. Další finalisté AES: Serpent a Twofish. Proudové šifry: konstrukce odvozené z LFSR, Trivium, RC4, ChaCha20. [P02] [V05]
27. 3. Hešovací funkce: požadavky, Merkleova-Damgårdova konstrukce iterací kompresní funkce. Různé druhy narozeninových útoků na heše. Kde vzít kompresní funkci: Daviesova-Meyerova konstrukce z blokové šifry, MD5, SHA-1, SHA-2. Houbovité funkce: Keccak, SHA-3, SHAKE-n a další varianty. [P03] [V06]
3. 4. Paralelní hešování: Merkleovy stromy, Sakura. Symetrické podpisy (MAC): konstrukce z hešovacích funkcí (HMAC), různé způsoby kombinace MAC s šifrou, CBC-MAC. Informačně-teoretický MAC z 2-nezávislých lineárních funkcí nebo z polynomů. Implementace pomocí blokových šifer: mód GCM, funkce Poly1305. Generování náhodných bitů: pseudonáhodné generátory ze symetrických šifer, fyzikální náhodnost (LavaRand, kruhové oscilátory, …), kombinace obojího – Fortuna, RDRAND, /dev/random. [P04] [V07]
10. 4. Teorie čísel z šinkansenu. Výpočetní složitost aritmetiky. Euklidův algoritmus a Bézoutovy koeficienty. Multiplikativní grupa modulo N. Malá Fermatova a Eulerova věta. Lagrangeova věta o podgrupách. Čínská zbytková věta a její konstruktivní verze. Výpočet Eulerovy funkce. Faktorizace vs. prvočíselnost. Fermatův a Rabinův-Millerův test, Carmichaelova čísla, zmínka o Agarwalově deterministickém testu. Generování velkých prvočísel. Cykličnost multiplikativní grupy, diskrétní logaritmy, kde vzít generátor. [P05] [V08]
17. 4. Plán: Teorie čísel: diskrétní odmocniny, Legendreovy a Jacobiho symboly. RSA: definice, triky pro zrychlení, k čemu vedou chyby při výpočtu. Vlastnosti RSA: komutativita, prohození klíčů, homomorfismus vzhledem k násobení (aplikace: slepé podpisy). Útoky: krátké zprávy, nízký tajný exponent, meet in the middle, podobná prvočísla, podobné zprávy, víc klíčů se stejným modulem, tatáž zpráva zašifrovaná více klíči. Sémantická bezpečnost: RSA zachovává Jacobiho symbol, zjistit nejnižší bit nebo polovinu intervalu je těžké. [P05] [P06]
24. 4. Plán: RSA: padding a Bleichenbacherův útok. Rabinův kryptosystém. Diffeho-Hellmanova výměna klíčů. ElGamalův kryptosystém.
1. 5. Přednáška odpadá, náhradní bude 2. 5. od 17:20 v S11.
9. 5. Přednáška odpadá, náhradní bude 29. 5. od 10:40 v S10.
16. 5. Přednáška odpadá.

Literatura

Stránku spravuje Martin Mareš