Kódování a základy kryptografie

Momentální iterace programu přednášek a hrubý nástřel budoucího skripta vypadá takto:

1. Kódování zpráv. Základní pojmy -- abeceda, zpráva, kód, kódování, dekódování. Prefixové kódy. Blokové kódy. Informační poměr, redundance. Informační a kontrolní znaky. Systematické kódování.
2. Bezpečnostní kódy. Objevování a opravování chyb. Hammingova vzdálenost, minimální vzdálenost. Shluky chyb. Lineární kódy. Generující a kontrolní matice.
3. Polynomy, okruhy polynomů, kořeny, ireducibilita. Cyklické kódy. Generující a kontrolní polynom. Generující kořeny.
4. Konstrukce kódů. Rozšíření, zúžení, zvětšení, zmenšení, direktní součin, direktní součet, prokládání. Některé praktické aspekty. Volba vhodného kódování. Příklady kódů použitých v praxi.
   (? Dekódování. Dekódování maximální pravděpodobnosti. Standardní dekódování, dekódování pomocí syndromů. ?)
5. Kódy pro kompresi dat. Huffmanovo kódování. Shannon-Fanovo kódování, aritmetické kódování (zmínka). Slovníkové metody komprese dat (pro informaci a srovnání, pouze stručná zmínka). Používané programy pro kompresi dat (zmínka, případně použité kódování).
6. Základy teorie informace. Sdělovací kanály, šum. Shannonův teorém. Entropie. Binární symetrický kanál. Pravděpodobnost nezachycené (zbytkové) chyby.
7. Algebraická tělesa. Vlastnosti. Tělesa Z_p. Charakteristika, řád prvku, primitivní prvek, minimální polynom. Diskrétní logaritmus. Galoisova tělesa.
8. Jemný úvod do kryptografie: Jednoduchá záměna, transpozice, knižní šifry. Enigma, kód Navaho. Symetrické a asymetrické šifry. Blokové šifry, proudové šifry.
9. Kryptologická matematika: Teorie čísel. Invertovatelnost. Prvočísla. Faktorizace. Eliptické prostory. Diferenciální a lineární kryptoanalýza. Eliptická kryptoanalýza.
10. Symetrická kryptografie: Blokové šifry. Operační módy. Proudové šifry. Linear Feedback Shift Register. DES, AES, IDEA. Hashovací funkce? Blowfish, Twofish, Serpent? Další méně frekventované blokové šifry?
11. Asymetrická kryptografie: Jednocestné funkce (one-way functions). Diffie-Hellmanův algoritmus. RSA, ElGamal. Problém batohu. Digitální podpis. DSA.
12. Šifrování veřejným klíčem: Princip dvou klíčů. Man in the middle attack. PGP, OpenPGP, GnuPG.
13. Náhodná a pseudonáhodná čisla. Kvazináhodná čísla. Hashování a ověřování integrity (CRC32, MD5, SHA, HMAC).
14. Ochrana komunikačních kanálů: Zabezpečení komunikace (IPsec, SSL/TLS, WEP). Virtuální privátní sítě (VPN).

Vzhledem k reorganizaci výuky na 13 týdnů něco z látky vypustíme, co to ale bude, v tento moment ještě nevíme.

Prozatím vyřazeno

• Ekvivalence kódů. Duální kód. Objevování chyb, syndrom. Hammingovy kódy. Golayův kod. Reedovy-Mullerovy kody.
• BCH kódy. Definice, vlastnosti. Plánovaná a minimální vzdálenost BCH kódu. Binární a nebinární BCH kódy. Reedovy-Solomonovy kódy.
• Konvoluční kódy. Turbo kódy. LDPC kódy. Měkké rozhodování. Iterativní dekódování.

Texty ke stažení

Někdy patrně bude k předmětu k dispozici i skriptum. Je skoro hotové už několik let, níže jsou vám k dispozici jednotlivé kapitoly. berte prosím na vědomí, že jde o vývojové verze skripta, mohou tedy obsahovat nešťastné formulace nebo i naprosté nesmysly. Za každé upozornění budeme samozřejmě rádi a přinese vám i nějaké body.

• Kódování. Zatím není k dispozici.
• Krypto - úvod. Přednáška 9 a 10, ke stažení zde.
• Krypto - blokové šifry. Přednáška 11 a 12, ke stažení zde
• Krypto - asymetrické šifry. Přednáška 13, ke stažení zde

Informace ke klasifikovanému zápočtu

Seznam okruhů k zápočtu pro ZS 2013/2014 je ke stažení zde. Aktuální seznam okruhů pro ZS 2013/2014 se bude patrně o něco lišit, závisí to na tom, co přesně odpřednášíme.

V případě dlouhodobé nepřítomnosti studenta budeme jako kompenzaci za neúčast na přednáškách vyžadovat vypracování semestrální práce. Archivní témata ze ZS 2010/2011 jsou uvedena níže.

Vzorová zápočtová písemka je ke stažení zde. Celkem z ní můžete získat 20 bodů, časový limit je 90 minut. Hodnocení je podle následující tabulky:

Termíny zápočtových písemek budou v pravý okamžik uvedeny v KOSu.

Samostatné úlohy (pro studenty v cizině, kteří si přejí absolvovat předmět a nemohou navštěvovat přednášky) na výběr v ZS 2010/2011:

• Moderní samoopravné kódy (ke stažení zde)
• Symetrické blokové šifry Blowfish a Twofish (ke stažení zde)
• Symetrické blokové šifry Serpent a Skipjack (ke stažení zde)

Seznam literatury

1. ADÁMEK J.: Kódování. Matematika pro vysoké školy technické, sešit XXXI. SNTL, Praha, 1989, 191pp.
2. ADÁMEK J.: Kódování a teorie informace. Skripta ČVUT, Praha, 1991, 209pp.
3. ADÁMEK J.: Foundations of coding: theory and applications of error-correcting codes, with an introduction to cryptography and information theory. Wiley, 1991, 336pp.
4. CVRČEK D.: Kryptologie a informační bezpečnost. Draft verze skripta VUT FIT, Brno, 2005, 59pp. Dostupné z WWW: http://www.xinta-download.ic.cz/VUT/KIB/KIB_prednasky_v_cestine.pdf.
5. HANKERSON D.R., HOFFMAN G., LEONARD D.A., LINDNER C.C., PHELPS K.T., RODGER C.A., WALL J.R.: Coding Theory and Cryptography: The Essentials, volume 234 of Pure And Applied Mathematics. Taylor & Francis, 2nd edition, 2000, 368pp.
6. MORELOS-ZARAGOZA R.H.: The Art of Error-Correcting Coding. John Wiley & Sons, 2nd edition, 2006, 263pp.
7. MOLLIN R.A.: An Introduction to Cryptography. Chapman & Hall/CRC, 2001, 373pp.
8. MOLLIN R.A.: An Introduction to Cryptography, Second Edition. Taylor & Francis, 2006, 413pp.
9. MOON T.K.: Error Correction Coding: Mathematical Methods and Algorithms. John Wiley & Sons, 2005, 800pp.

Lucie Kárná a Jan Přikryl, prikryl@fd.cvut.cz