Matematikai kriptográfia és kódelmélet (BMETE91AM33) - 2015

Segédanyag a kódelméletről (V.15-03-24). és az aszimmetrikus rejtjelezőről (javítva: 2015-05-05)

Házi feladatok

1. 1.5 1, (nem kötelező: 2.4). Beadási határidő: 2015-02-24
2. 3.18, 3.19. Beadási határidő: 2015-03-03
3. 3.22 vagy 4.9, és 4.5. Beadási határidő: 2015-03-10
4. 5.5. Beadási határidő: 2015-03-17
5. 6.4. Beadási határidő: 2015-03-24
6. 9.3, 9.6. Beadási határidő: 2015-03-31
7. p₁, p₂, …, p_n, q₁, q₂, …, q_n valószínűségeloszlások. Mutassuk meg, hogy ha p₁ ≥ p₂ ≥ … ≥ p_n, és q₁', q₂', …, q_n' a q₁, q₂, …, q_n egy permutációja, akkor a ∑_i p_iq_i' összeg maximális, ha q₁' ≥ q₂' ≥ … ≥ q_n'.
8. Bizonyítsuk be, hogy ha (G,E,D) tökéletesen biztonságos az M nyílt szövegtér fölött, és a G által meghatározott kulcstér K, akkor |K| ≥ |M|.
9. Végezzünk el egy RSA-számolást, visszfejtéskor a kínai maradéktétellel.
10. Igazoljuk az RSA ellen kis d esetén támadó Wiener-tételt!

Vizsgakérdések

1. Zajmentes és zajos csatornakódolási tételek, csatornamodellek, dekódolás (ML, MAP)
2. Elemi blokkkódok és paramétereik, korlátok a kód méretére (Singleton, Hamming)
3. Lineáris kód, duális kód tulajdonságai, kódtávolság és H kapcsolata
4. Mit értünk szindróma dekódoláson?
5. Szimplex- és Hamming-kód, elsőrendű bináris Reed-Muller-kód, Hadamard-dekódolás. Igazoljuk, hogy a Hamming-kód perfekt!
6. A ciklikus kód tulajdonságai. Mi a kapcsolat ciklikus kód és duálisa között?
7. A BCH-kód és az általánosított Reed-Solomon-kód legfontosabb tulajdonságai.
8. Súlyfüggvény, MacWilliams-tétel (a bizonyítás ötlete részletezés nélkül).
9. Kódok konstrukciója kódból, ternér Golay-kód konstrukciója
10. Mit jelent a tökéletes, a számítási és a szemantikai biztonság? Az OTP tökéletes biztonsága.
11. Vigenère-kód és kriptoanalízise (Kasiski, Friedman)
12. PRG jósolhatósága, biztonságossága, és a belőle képzett folyó titkosítás szemantikai biztonsága.
13. Mit értünk Feistel-típusú titkosításon, hol és hogyan használjuk, mit tudunk róla? A blokktitkosító használatának módjai!
14. Makacs számelméleti problémák és egyirányú kiaskapufüggvények
15. Az RSA-függvény, támadások ellene, Wiener-támadás
16. Az elliptikus görbékre épülő kriptográfia alapjai: pontművelet, diszkrét logaritmus elliptikus görbén.
17. Egyirányú kiskapufüggvényből hogyan készítünk nyilvános kulcsú titkosító rendszert, hibrid rendszer (nyilvános és szimmetrikus kulcsúból).
18. ElGamal kriptorendszer

Szabadonválasztott témák (néhány ötlet, bármi más is lehet)

1. Információelméleti alapfogalmak: entrópia, feltételes entrópia,...
2. Plotkin korlát, egyéb korlátok
3. Bináris Golay-kód
4. MAC (message authentication code)
5. Mindennapi gyakorlatban használt kódolási algoritmusok (pl. CD, QR-kód)
6. Hitelesített titkosítás
7. Digitális aláírás
8. Titokmegosztási sémák, vizuális titokmegosztás,
9. A kriptográfiában használt diszkrét log és faktorizálhatóság algoritmikus bonyolultsága
10. Zero knowledge proof
11. Kvantumkriptográfia alapjai, Shor-algoritmus