Kriptográfia (BMEVIHI9366)

Tematika

  1. Komplexitáselmélet kriptográfiai szemmel: fogalmi bevezető és ismétlés
    P, NP, BPP komplexitásosztály, P != NP sejtés, NP-teljesség, hatékony számítás, elhanyagolhatóan - nem elhanyagolható kicsi (szuperpolinomiális), az orákulumos gép, nehéz probléma és kriptográfia (legrosszabb eset, átlagos eset)
    nehéz problémák: egész szám faktorizációja, gyökvonás probléma, diszkrét logaritmus probléma, hátizsák probléma
  2. Bizonyítástechnikák: redukció (hatékonyság és gyakorlati használhatóság), hibrid bizonyítás.
  3. A bizonyított biztonság elve.
    Nyilvános kulcsú rejtjelezés biztonsági fogalmai, tételei: szemantikai biztonság (SS), üzenet megkülönböztető biztonság (IND-CPA/CCA1/CCA2, LoR-), rejtett üzenet módosíthatatlansága biztonság (NM-CPA/CCA1/CCA2).
    F2 (SS), F3 (IND-CPA), F4 (IND-CCA0), F5 (IND-CCA00), F6 (IND-CCA2), F7 (IND-CPA)
  4. Egyirányú függvény (OWF).
    Gyenge és erős egyirányú függvény. Hossz-tartó OWF. Nem-egyenletes OWF.
    Egyirányú függvény jelöltek: egész szám faktorizáció, véletlen lineáris kód dekódolása, részletösszeg probléma.
    Egyirányú fügvénykollekció és példái: RSA, Rabin függvény, Rabin permutáció, diszkrét logaritmus.
    Egyirányú csapda permutáció: RSA.
    F6(14, OWF létezés), F1 (11, gyenge OWF), F7(csapda perm.)
  5. RSA és támadásai F2-3(25)
  6. Keménybit. Keménybit és egyirányúság kapcsolata. Goldreich-Levin keménybit tétel és következményei. Kemény függvény. Keménybitek számának növelése.
  7. Goldwasser-Micali rejtjelezés és biztonsága. Az RSA keménybitje. Az egyirányú csapda permutáció és a szemantikai biztonságú nyilvános kulcsú rejtjelezés.
  8. A véletlen megközelítései: Kolmogorov, számítással megkülönböztethetetlen.
    Az eloszlások megkülönböztethetetlensége tételkör: statisztikai közelség (variációs távolság) vs. poly-idejű (algoritmikus) közelség ill. megkülönböztethetetlenség. Mintanagyság növelése.
    F1
  9. PRG (álvéletlen generátor) konstrukciók. PRG létezése és a OWF létezése. F5(14)
  10. A standard PRF (álvéletlen függvény) konstrukció. Születésnapi paradoxon és a PRF megkülönböztethetőség. PRF és PRP, mint szimmetrikus kulcsú rejtjelező modellje. PRF a kulcs inputjában egyirányú függvény
    F3(mini DES), F9(17)
  11. Luby-Rackoff PRP (álvéletlen permutáció) konstrukció. DES és a PRP kontrukció: 2,3,4 réteg esete.
    F4(12, 3 réteg)
  12. A véletlenítés szerepe a rejtjelezésben. Az RSA biztonság feltételezései és biztonsági implikációi. Az RSA ismert támadásai.
  13. Diszkrét logaritmusképzés, DDH és CDH probléma, az El-Gamal rejtjelező és biztonsága.
  14. Véletlen orákulum. Bizonyítás véletlen orákulum modellben (r.o.m.).
    F1(PRG in r.o.m.), F2(OWF in r.o.m.)
  15. Biztonságos szimmetrikus kulcsú rejtjelezés: támadó erőforrásai.
    F2(11, sec. symm.crypto vs. P != NP), F8(16, sec.publ. impl. sec. symm.)
  16. Kulcsfejtő támadó. PRF (PRP) modelltől megkülönböztethetőség (PRF/PRP CPA,CCA). IND- vagy LoR -CPA/CCA biztonság fogalom. Nyílt szöveg visszafejtő támadás.
    F8 (LoR-CPA), F9 (szövegfejtő)
  17. Standard szimmetrikus kulcsú blokkrejtjelezés módok biztonsága: ECB, CBC, CTR$, CTRC.
    F1 (ECB), F2 (CBC)
  18. Biztonságos MAC sémák véletlen orákulum modellben.
    F5.14-21 (klasszikus)
  19. Digitális aláírás biztonsága, bizonyíthatóság kérdései. Plain RSA, Hash-and -Sign, Full Domain Hashing, PSS-0. Bizonyítás véletlen orákulum modellben.
    F1-7(23, 25)
  20. Hash függvények biztonsági követelmények. Hash függvénykollekció. UOWHF. Véletlen hash orakulum.
    F5.1-13 (klasszikus), F1-5 (UOWHF)
  21. Hatékony bizonyítható biztonságú nyilvános kulcsú rejtjelezők: RSA-OAEP, Cramer-Shoup kód.