Matematická kryptografie


Plán přednášek

Kompletní playlist videonahrávek z přednášek najdete zde .

  1. Úvod do kryptografie a kryptoanalýzy. Počítání v Z a v Z_n. Handout č.1 a verze k tisku.
    Videozáznam přednášky: část MKR01a, část MKR01b a část MKR01c
    Scan z 1.cvičení s nepovinným domácím úkolem.
  2. Počítání v Z_n. Složitosti aritmetických operací v Z_n. Handout č.2 a verze k tisku.
    Videozáznam přednášky: část MKR02a, část MKR02b, část MKR02c, část MKR02d a část MKR02e
    Scan ze 2.cvičení s nepovinným domácím úkolem.
  3. RSA šifrování. Útoky na protokol RSA. Handout č.3 a verze k tisku.
    Videozáznam přednášky: část MKR03a, část MKR03b, část MKR03c, část MKR03d a část MKR03e
    Scan ze 3.cvičení s nepovinným domácím úkolem.
    Scan ze 4.cvičení s nepovinným domácím úkolem.
  4. Abelovy grupy. Handout č.4 a verze k tisku.
    Videozáznam přednášky: část MKR04a, část MKR04b, část MKR04c, část MKR04d a část MKR04e
    Omluvte, prosím, sníženou kvalitu zvuku u nahrávek 4. týdne.
    Scan z 5.cvičení s nepovinným domácím úkolem.
  5. Řád prvku v grupě, cyklické grupy. Handout č.5 a verze k tisku.
    Videozáznam přednášky: část MKR05a, část MKR05b
    Scan ze 6.cvičení s nepovinným domácím úkolem.
  6. Struktura grup Z_n^*. Handout č.6 a verze k tisku.
    Videozáznam přednášky: část MKR06a, část MKR06b, část MKR06c
    Scan ze 7.cvičení s nepovinným domácím úkolem.
  7. Diskrétní logaritmus, Diffie-Hellmanův protokol. Handout č.7 a verze k tisku.
    Videozáznam přednášky: část MKR07a, část MKR07b, část MKR07c, část MKR07d
    Scan z 8.cvičení s nepovinným domácím úkolem.
    Scan z 9.cvičení s nepovinným domácím úkolem.
  8. Eliptické křivky a problém diskrétního logaritmu na eliptické křivce. Handout č.13 a verze k tisku.
    Videozáznam přednášky: část MKR13
    Scan z 10.cvičení s nepovinným domácím úkolem.
  9. Generování náhodných čísel a prvočísel, pravděpodobnostní algoritmy. Handout č.8 a verze k tisku.
    Videozáznam přednášky: část MKR08
  10. Testy prvočíselnosti. Carmichaelova čísla. Handout č.9 a verze k tisku.
    Videozáznam přednášky: část MKR09a, část MKR09b, část MKR09c
    Scan z 11.cvičení s nepovinným domácím úkolem.
  11. Faktorizace se znalostí Eulerovy funkce. Handout č.10 a verze k tisku.
    Videozáznam přednášky: část MKR10
    Scan z 11.cvičení s nepovinným domácím úkolem.
  12. Subexponenciální algoritmus pro diskrétní logaritmus. Handout č.11 a verze k tisku.
    Videozáznam přednášky: část MKR11a, část MKR11b, část MKR11c
    Scan ze 12.cvičení s nepovinným domácím úkolem.
  13. Subexponenciální algoritmus pro faktorizaci, kvadratické síto. Handout č.12 a verze k tisku.
    Videozáznam přednášky: část MKR12a, část MKR12b
    Scan ze 13.cvičení s nepovinným domácím úkolem.
  14. Bezpečnost kryptosystémů ve světle kvantových počítačů. Přednášky Štěpána Holuba, MFF UK.
  15. Stručná historie kryptografie. Handout č.0 a verze k tisku.
    Videozáznam přednášky: část MKR00a, část MKR00b, část MKR00c, část MKR00d

Literatura

  • V.Shoup, A Computational introduction to number theory and algebra, Cambridge University Press, 2008. Kniha je volně dostupná zde.
  • D.Boneh, Twenty Years of Attacks on the RSA Cryptosystem. Ke stažení zde.
  • D.Hankerson, A.J.Menezes, S.Vanstone, Guide to elliptic curve cryptography, Springer, 2004.
  • V.Shoup, D.Boneh, A Graduate Course of Applied Cryptography, 2020. Ke stažení zde.
  • S.Singh, Kniha kódů a šifer, Dokořán a Agro, 2009.

Zápočet a zkouška

  • Nutnou podmínkou k udělení zápočtu je napsat aspoň z 50% správně semestrální test. Test se bude psát v 9. či v 10. týdnu semestru, obsahem testu bude látka odpřednášená v první polovině semestru, viz Handout č. 1-7. V případě neúspěchu je možný jeden opravný pokus.
  • Dále je pro získání zápočtu nutná aktivní aspoň 70% účast na cvičeních. Účast na přednáškách je také naléhavě doporučena.
  • Zkoušku mohou skládat pouze ti studenti, kteří získali zápočet.
  • Zkouška má písemnou a ústní část, obě části jsou povinné.
  • Student bude připuštěn k ústní zkoušce pouze tehdy, když písemný test napsal aspoň z 50% správně. V opačném případě student u zkoušky neuspěl.
  • Obsahem zkoušky bude látka probraná na přednáškách a cvičeních.
  • Ukázka zkouškové písemky Kalkulačky jsou povoleny pro sčítání, násobení a umocňování modulo n, ostatní výpočty musí být rozepsány krok za krokem. Postup výpočtu musí být okomentován a zdůvodněn, samotná čísla nestačí. Písemná část trvá 150 minut.
    V roce 2021 bude písemka zkrácena na 120 minut, příklady budou většinou obsahovat pouze části a), b).

Další materiály ke studiu