Kriptográfia (BMEVIHI9366)
Tematika
- 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
- Bizonyítástechnikák: redukció (hatékonyság és gyakorlati használhatóság), hibrid bizonyítás.
- 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)
- 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.)
- RSA és támadásai F2-3(25)
- 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.
- 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.
- 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
- PRG (álvéletlen generátor) konstrukciók. PRG létezése és a OWF létezése. F5(14)
- 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)
- Luby-Rackoff PRP (álvéletlen permutáció) konstrukció. DES és a PRP kontrukció: 2,3,4 réteg esete.
F4(12, 3 réteg)
- 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.
- Diszkrét logaritmusképzés, DDH és CDH probléma, az El-Gamal rejtjelező és biztonsága.
- 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.)
- 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.)
- 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ő)
- Standard szimmetrikus kulcsú blokkrejtjelezés módok biztonsága: ECB, CBC, CTR$, CTRC.
F1 (ECB), F2 (CBC)
- Biztonságos MAC sémák véletlen orákulum modellben.
F5.14-21 (klasszikus)
- 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)
- 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)
- Hatékony bizonyítható biztonságú nyilvános kulcsú rejtjelezők:
RSA-OAEP, Cramer-Shoup kód.