Kryptografické systémy, ZS 2014/15

Zkouška a zápočet

Během semestru budete moci získat až 50 bodů za domácí úkoly a za aktivitu na cvičeních. U zkoušky pak můžete získat dalších 50 bodů. K tomu, abyste uspěli, je třeba získat u zkoušky alespoň 30 bodů a celkem alespoň 60 bodů. Známka se pak určí z celkového počtu bodů: 100–90 bodů výborně, 89–75 bodů velmi dobře, 74–60 bodů dobře. Zápočet je jen formální, získáváte ho automaticky složením zkoušky.

Zkouška je ústní. Vylosujete si dvě nebo tři otázky a dostanete čas na přípravu poznámek. Seznam otázek.

Kdo od jiného opíše nebo kdo jinému poskytne řešení nebo část řešení domácího úkolu nebo kdo se dopustí jakékoliv jiné formy podvádění, ztratí body za předmětný domácí úkol.

Obsah přednášek

Přednáška 5. 1. 2015: Digitální podpis. Diffie-Hellmanův protokol, ElGamalův šifrovací systém a ElGamalovo podpisové schéma (slajdy).
Přednáška 15. 12.: Known-message útok na CBC-MAC. Kryptografie s veřejným klíčem - RSA (slajdy). Faktorizace modulu N ze znalosti exponentů e a d.
Přednáška 8. 12.: Hashovací funkce (úvodní slajdy). Narozeninový paradox. Složitost hledání vzoru a kolize hrubou silou. Merkleovo-Damgårdovo schéma a důkaz tvrzení o jeho bezkolizkosti. MAC.
Přednáška 1. 12.: Proudové šifry. Posuvné registry s lineární zpětnou vazbou. Šifra A5/1 (slajdy).
Přednáška 24. 11.: Operační režimy blokových šifer (ECB, CBC, CFB, CFB-l, OFB, CTR). Ciphertext stealing v ECB režimu.; Domácí úkol není.
Přednáška 17. 11. odpadá: Den boje studentů za svobodu a demokracii.
Přednáška 10. 11.: Double DES a Triple DES. Meet-in-the-middle útok. DES-X. Počítání v tělese GF(2⁸). Šifra AES (slajdy).
Přednáška 3. 11.: Absolutně bezpečné šifry - dokončení, další typy bezpečnosti. Šifra DES.; Skripta k Shannonově teorii.
Přednáška 27. 10.: Podmíněná entropie, vzájemná informace, vzdálenost jednoznačnosti, absolutně bezpečné šifry.
Přednáška 20. 10.: Huffmanovo kódování a základní vlastnosti entropie.
Přednáška 13. 10.: Budování složitějších šifer. Úvod do teorie pravděpodobnosti.
Přednáška 6. 10.: Cíle kryptografie. Jednoduché šifry a jejich prolamování. Typy útoků.

Domácí úkoly

Řešení domácích úkolů můžete odevzdávat emailem nebo osobně před začátkem přednášky. Výsledné hodnocení svých domácích úkolů najdete v SISu v aplikaci Grupíček.

Zadání. 5 bodů. Termín odevzdání: 13. 10. 2014, 12:20.
Zadání. 5 bodů. Termín odevzdání: 20. 10. 2014, 12:20.
(Rozhodl jsem se, že úlohu o Hillově a transpoziční šifře zařadím jako součást domácího úkolu, čili nejedná se o bonusovou úlohu.)
Zadání. 5 bodů. Termín odevzdání: 27. 10. 2014, 12:20.
Zadání. 5 bodů. Termín odevzdání: 3. 11. 2014, 12:20.
Zadání. 5 bodů. Termín odevzdání: 10. 11. 2014, 12:20.
Zadání. 5 bodů. Termín odevzdání: 24. 11. 2014, 12:20.
Zadání bylo zasláno emailem. 5 bodů. Termín odevzdání: 8. 12. 2014, 12:20.
Nápověda: Řešení úlohy o A5/1 je jednoznačně určeno. Délka LFSR je 4 až 7.
Při rekonstrukci LFSR si můžete usnadnit práci tak, že soustavu vyřešíte pomocí počítače, například v programu Mathematica příkazem LinearSolve[matice_soustavy, vektor_pravych_stran, Modulus->2].
Zadání. 5 bodů. Termín odevzdání: 15. 12. 2014, 12:20. Dodatečně lze úkol odevzdat do 18. 1. 2015, 18:00, za 4 body.
Zadání bylo zasláno emailem. 5 bodů. Termín odevzdání: 5. 1. 2015, 12:20.
Pro mocnění v Pythonu doporučuji použít funkci pow. Například a^b mod N spočtete jako pow(a, b, N).

Studijní materiály

Skripta a slajdy z přednášek

Shannonova teorie
Šifra AES
Šifra A5/1 (Aktualizováno 3. 12. 2014.)
Hashovací funkce – úvod
Kryptografie s veřejným klíčem – RSA
Diffieho-Hellmanův protokol, ElGamalův šifrovací systém a podpisové schéma

Jazyk

Frekvence písmen, bigramů, trigramů v českém jazyce

Šifry

Články

A. Biryukov, A. Shamir, D. Wagner: Real Time Cryptanalysis of A5/1 on a PC. 2001.
E. Barkan, E. Biham, N. Keller: Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication. 2003, 2006.
W. Diffie, M. E. Hellman: New directions in cryptography. 1976.
D. Boneh: Twenty years of attacks on the RSA cryptosystem. 1999.